newlines fixed

git-svn-id: svn://svn.icculus.org/quake3/trunk@6 edf5b092-35ff-0310-97b2-ce42778d08ea

1 files changed, 2209 insertions, 2209 deletions

diff --git a/code/botlib/be_aas_route.c b/code/botlib/be_aas_route.c
index 441984d..642be81 100755
--- a/code/botlib/be_aas_route.c
+++ b/code/botlib/be_aas_route.c
@@ -1,2209 +1,2209 @@
-/*

-===========================================================================

-Copyright (C) 1999-2005 Id Software, Inc.

-

-This file is part of Quake III Arena source code.

-

-Quake III Arena source code is free software; you can redistribute it

-and/or modify it under the terms of the GNU General Public License as

-published by the Free Software Foundation; either version 2 of the License,

-or (at your option) any later version.

-

-Quake III Arena source code is distributed in the hope that it will be

-useful, but WITHOUT ANY WARRANTY; without even the implied warranty of

-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

-GNU General Public License for more details.

-

-You should have received a copy of the GNU General Public License

-along with Foobar; if not, write to the Free Software

-Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

-===========================================================================

-*/

-

-/*****************************************************************************

- * name:		be_aas_route.c

- *

- * desc:		AAS

- *

- * $Archive: /MissionPack/code/botlib/be_aas_route.c $

- *

- *****************************************************************************/

-

-#include "../game/q_shared.h"

-#include "l_utils.h"

-#include "l_memory.h"

-#include "l_log.h"

-#include "l_crc.h"

-#include "l_libvar.h"

-#include "l_script.h"

-#include "l_precomp.h"

-#include "l_struct.h"

-#include "aasfile.h"

-#include "../game/botlib.h"

-#include "../game/be_aas.h"

-#include "be_aas_funcs.h"

-#include "be_interface.h"

-#include "be_aas_def.h"

-

-#define ROUTING_DEBUG

-

-//travel time in hundreths of a second = distance * 100 / speed

-#define DISTANCEFACTOR_CROUCH		1.3f		//crouch speed = 100

-#define DISTANCEFACTOR_SWIM			1		//should be 0.66, swim speed = 150

-#define DISTANCEFACTOR_WALK			0.33f	//walk speed = 300

-

-//cache refresh time

-#define CACHE_REFRESHTIME		15.0f	//15 seconds refresh time

-

-//maximum number of routing updates each frame

-#define MAX_FRAMEROUTINGUPDATES		10

-

-

-/*

-

-  area routing cache:

-  stores the distances within one cluster to a specific goal area

-  this goal area is in this same cluster and could be a cluster portal

-  for every cluster there's a list with routing cache for every area

-  in that cluster (including the portals of that cluster)

-  area cache stores aasworld.clusters[?].numreachabilityareas travel times

-

-  portal routing cache:

-  stores the distances of all portals to a specific goal area

-  this goal area could be in any cluster and could also be a cluster portal

-  for every area (aasworld.numareas) the portal cache stores

-  aasworld.numportals travel times

-

-*/

-

-#ifdef ROUTING_DEBUG

-int numareacacheupdates;

-int numportalcacheupdates;

-#endif //ROUTING_DEBUG

-

-int routingcachesize;

-int max_routingcachesize;

-

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-#ifdef ROUTING_DEBUG

-void AAS_RoutingInfo(void)

-{

-	botimport.Print(PRT_MESSAGE, "%d area cache updates\n", numareacacheupdates);

-	botimport.Print(PRT_MESSAGE, "%d portal cache updates\n", numportalcacheupdates);

-	botimport.Print(PRT_MESSAGE, "%d bytes routing cache\n", routingcachesize);

-} //end of the function AAS_RoutingInfo

-#endif //ROUTING_DEBUG

-//===========================================================================

-// returns the number of the area in the cluster

-// assumes the given area is in the given cluster or a portal of the cluster

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-__inline int AAS_ClusterAreaNum(int cluster, int areanum)

-{

-	int side, areacluster;

-

-	areacluster = aasworld.areasettings[areanum].cluster;

-	if (areacluster > 0) return aasworld.areasettings[areanum].clusterareanum;

-	else

-	{

-/*#ifdef ROUTING_DEBUG

-		if (aasworld.portals[-areacluster].frontcluster != cluster &&

-				aasworld.portals[-areacluster].backcluster != cluster)

-		{

-			botimport.Print(PRT_ERROR, "portal %d: does not belong to cluster %d\n"

-											, -areacluster, cluster);

-		} //end if

-#endif //ROUTING_DEBUG*/

-		side = aasworld.portals[-areacluster].frontcluster != cluster;

-		return aasworld.portals[-areacluster].clusterareanum[side];

-	} //end else

-} //end of the function AAS_ClusterAreaNum

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_InitTravelFlagFromType(void)

-{

-	int i;

-

-	for (i = 0; i < MAX_TRAVELTYPES; i++)

-	{

-		aasworld.travelflagfortype[i] = TFL_INVALID;

-	} //end for

-	aasworld.travelflagfortype[TRAVEL_INVALID] = TFL_INVALID;

-	aasworld.travelflagfortype[TRAVEL_WALK] = TFL_WALK;

-	aasworld.travelflagfortype[TRAVEL_CROUCH] = TFL_CROUCH;

-	aasworld.travelflagfortype[TRAVEL_BARRIERJUMP] = TFL_BARRIERJUMP;

-	aasworld.travelflagfortype[TRAVEL_JUMP] = TFL_JUMP;

-	aasworld.travelflagfortype[TRAVEL_LADDER] = TFL_LADDER;

-	aasworld.travelflagfortype[TRAVEL_WALKOFFLEDGE] = TFL_WALKOFFLEDGE;

-	aasworld.travelflagfortype[TRAVEL_SWIM] = TFL_SWIM;

-	aasworld.travelflagfortype[TRAVEL_WATERJUMP] = TFL_WATERJUMP;

-	aasworld.travelflagfortype[TRAVEL_TELEPORT] = TFL_TELEPORT;

-	aasworld.travelflagfortype[TRAVEL_ELEVATOR] = TFL_ELEVATOR;

-	aasworld.travelflagfortype[TRAVEL_ROCKETJUMP] = TFL_ROCKETJUMP;

-	aasworld.travelflagfortype[TRAVEL_BFGJUMP] = TFL_BFGJUMP;

-	aasworld.travelflagfortype[TRAVEL_GRAPPLEHOOK] = TFL_GRAPPLEHOOK;

-	aasworld.travelflagfortype[TRAVEL_DOUBLEJUMP] = TFL_DOUBLEJUMP;

-	aasworld.travelflagfortype[TRAVEL_RAMPJUMP] = TFL_RAMPJUMP;

-	aasworld.travelflagfortype[TRAVEL_STRAFEJUMP] = TFL_STRAFEJUMP;

-	aasworld.travelflagfortype[TRAVEL_JUMPPAD] = TFL_JUMPPAD;

-	aasworld.travelflagfortype[TRAVEL_FUNCBOB] = TFL_FUNCBOB;

-} //end of the function AAS_InitTravelFlagFromType

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-__inline int AAS_TravelFlagForType_inline(int traveltype)

-{

-	int tfl;

-

-	tfl = 0;

-	if (tfl & TRAVELFLAG_NOTTEAM1)

-		tfl |= TFL_NOTTEAM1;

-	if (tfl & TRAVELFLAG_NOTTEAM2)

-		tfl |= TFL_NOTTEAM2;

-	traveltype &= TRAVELTYPE_MASK;

-	if (traveltype < 0 || traveltype >= MAX_TRAVELTYPES)

-		return TFL_INVALID;

-	tfl |= aasworld.travelflagfortype[traveltype];

-	return tfl;

-} //end of the function AAS_TravelFlagForType_inline

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-int AAS_TravelFlagForType(int traveltype)

-{

-	return AAS_TravelFlagForType_inline(traveltype);

-} //end of the function AAS_TravelFlagForType_inline

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_UnlinkCache(aas_routingcache_t *cache)

-{

-	if (cache->time_next) cache->time_next->time_prev = cache->time_prev;

-	else aasworld.newestcache = cache->time_prev;

-	if (cache->time_prev) cache->time_prev->time_next = cache->time_next;

-	else aasworld.oldestcache = cache->time_next;

-	cache->time_next = NULL;

-	cache->time_prev = NULL;

-} //end of the function AAS_UnlinkCache

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_LinkCache(aas_routingcache_t *cache)

-{

-	if (aasworld.newestcache)

-	{

-		aasworld.newestcache->time_next = cache;

-		cache->time_prev = aasworld.newestcache;

-	} //end if

-	else

-	{

-		aasworld.oldestcache = cache;

-		cache->time_prev = NULL;

-	} //end else

-	cache->time_next = NULL;

-	aasworld.newestcache = cache;

-} //end of the function AAS_LinkCache

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_FreeRoutingCache(aas_routingcache_t *cache)

-{

-	AAS_UnlinkCache(cache);

-	routingcachesize -= cache->size;

-	FreeMemory(cache);

-} //end of the function AAS_FreeRoutingCache

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_RemoveRoutingCacheInCluster( int clusternum )

-{

-	int i;

-	aas_routingcache_t *cache, *nextcache;

-	aas_cluster_t *cluster;

-

-	if (!aasworld.clusterareacache)

-		return;

-	cluster = &aasworld.clusters[clusternum];

-	for (i = 0; i < cluster->numareas; i++)

-	{

-		for (cache = aasworld.clusterareacache[clusternum][i]; cache; cache = nextcache)

-		{

-			nextcache = cache->next;

-			AAS_FreeRoutingCache(cache);

-		} //end for

-		aasworld.clusterareacache[clusternum][i] = NULL;

-	} //end for

-} //end of the function AAS_RemoveRoutingCacheInCluster

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_RemoveRoutingCacheUsingArea( int areanum )

-{

-	int i, clusternum;

-	aas_routingcache_t *cache, *nextcache;

-

-	clusternum = aasworld.areasettings[areanum].cluster;

-	if (clusternum > 0)

-	{

-		//remove all the cache in the cluster the area is in

-		AAS_RemoveRoutingCacheInCluster( clusternum );

-	} //end if

-	else

-	{

-		// if this is a portal remove all cache in both the front and back cluster

-		AAS_RemoveRoutingCacheInCluster( aasworld.portals[-clusternum].frontcluster );

-		AAS_RemoveRoutingCacheInCluster( aasworld.portals[-clusternum].backcluster );

-	} //end else

-	// remove all portal cache

-	for (i = 0; i < aasworld.numareas; i++)

-	{

-		//refresh portal cache

-		for (cache = aasworld.portalcache[i]; cache; cache = nextcache)

-		{

-			nextcache = cache->next;

-			AAS_FreeRoutingCache(cache);

-		} //end for

-		aasworld.portalcache[i] = NULL;

-	} //end for

-} //end of the function AAS_RemoveRoutingCacheUsingArea

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-int AAS_EnableRoutingArea(int areanum, int enable)

-{

-	int flags;

-

-	if (areanum <= 0 || areanum >= aasworld.numareas)

-	{

-		if (bot_developer)

-		{

-			botimport.Print(PRT_ERROR, "AAS_EnableRoutingArea: areanum %d out of range\n", areanum);

-		} //end if

-		return 0;

-	} //end if

-	flags = aasworld.areasettings[areanum].areaflags & AREA_DISABLED;

-	if (enable < 0)

-		return !flags;

-

-	if (enable)

-		aasworld.areasettings[areanum].areaflags &= ~AREA_DISABLED;

-	else

-		aasworld.areasettings[areanum].areaflags |= AREA_DISABLED;

-	// if the status of the area changed

-	if ( (flags & AREA_DISABLED) != (aasworld.areasettings[areanum].areaflags & AREA_DISABLED) )

-	{

-		//remove all routing cache involving this area

-		AAS_RemoveRoutingCacheUsingArea( areanum );

-	} //end if

-	return !flags;

-} //end of the function AAS_EnableRoutingArea

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-__inline float AAS_RoutingTime(void)

-{

-	return AAS_Time();

-} //end of the function AAS_RoutingTime

-//===========================================================================

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-int AAS_GetAreaContentsTravelFlags(int areanum)

-{

-	int contents, tfl;

-

-	contents = aasworld.areasettings[areanum].contents;

-	tfl = 0;

-	if (contents & AREACONTENTS_WATER)

-		tfl |= TFL_WATER;

-	else if (contents & AREACONTENTS_SLIME)

-		tfl |= TFL_SLIME;

-	else if (contents & AREACONTENTS_LAVA)

-		tfl |= TFL_LAVA;

-	else

-		tfl |= TFL_AIR;

-	if (contents & AREACONTENTS_DONOTENTER)

-		tfl |= TFL_DONOTENTER;

-	if (contents & AREACONTENTS_NOTTEAM1)

-		tfl |= TFL_NOTTEAM1;

-	if (contents & AREACONTENTS_NOTTEAM2)

-		tfl |= TFL_NOTTEAM2;

-	if (aasworld.areasettings[areanum].areaflags & AREA_BRIDGE)

-		tfl |= TFL_BRIDGE;

-	return tfl;

-} //end of the function AAS_GetAreaContentsTravelFlags

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-__inline int AAS_AreaContentsTravelFlags_inline(int areanum)

-{

-	return aasworld.areacontentstravelflags[areanum];

-} //end of the function AAS_AreaContentsTravelFlags

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-int AAS_AreaContentsTravelFlags(int areanum)

-{

-	return aasworld.areacontentstravelflags[areanum];

-} //end of the function AAS_AreaContentsTravelFlags

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_InitAreaContentsTravelFlags(void)

-{

-	int i;

-

-	if (aasworld.areacontentstravelflags) FreeMemory(aasworld.areacontentstravelflags);

-	aasworld.areacontentstravelflags = (int *) GetClearedMemory(aasworld.numareas * sizeof(int));

-	//

-	for (i = 0; i < aasworld.numareas; i++) {

-		aasworld.areacontentstravelflags[i] = AAS_GetAreaContentsTravelFlags(i);

-	}

-} //end of the function AAS_InitAreaContentsTravelFlags

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_CreateReversedReachability(void)

-{

-	int i, n;

-	aas_reversedlink_t *revlink;

-	aas_reachability_t *reach;

-	aas_areasettings_t *settings;

-	char *ptr;

-#ifdef DEBUG

-	int starttime;

-

-	starttime = Sys_MilliSeconds();

-#endif

-	//free reversed links that have already been created

-	if (aasworld.reversedreachability) FreeMemory(aasworld.reversedreachability);

-	//allocate memory for the reversed reachability links

-	ptr = (char *) GetClearedMemory(aasworld.numareas * sizeof(aas_reversedreachability_t) +

-							aasworld.reachabilitysize * sizeof(aas_reversedlink_t));

-	//

-	aasworld.reversedreachability = (aas_reversedreachability_t *) ptr;

-	//pointer to the memory for the reversed links

-	ptr += aasworld.numareas * sizeof(aas_reversedreachability_t);

-	//check all reachabilities of all areas

-	for (i = 1; i < aasworld.numareas; i++)

-	{

-		//settings of the area

-		settings = &aasworld.areasettings[i];

-		//

-		if (settings->numreachableareas >= 128)

-			botimport.Print(PRT_WARNING, "area %d has more than 128 reachabilities\n", i);

-		//create reversed links for the reachabilities

-		for (n = 0; n < settings->numreachableareas && n < 128; n++)

-		{

-			//reachability link

-			reach = &aasworld.reachability[settings->firstreachablearea + n];

-			//

-			revlink = (aas_reversedlink_t *) ptr;

-			ptr += sizeof(aas_reversedlink_t);

-			//

-			revlink->areanum = i;

-			revlink->linknum = settings->firstreachablearea + n;

-			revlink->next = aasworld.reversedreachability[reach->areanum].first;

-			aasworld.reversedreachability[reach->areanum].first = revlink;

-			aasworld.reversedreachability[reach->areanum].numlinks++;

-		} //end for

-	} //end for

-#ifdef DEBUG

-	botimport.Print(PRT_MESSAGE, "reversed reachability %d msec\n", Sys_MilliSeconds() - starttime);

-#endif

-} //end of the function AAS_CreateReversedReachability

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-unsigned short int AAS_AreaTravelTime(int areanum, vec3_t start, vec3_t end)

-{

-	int intdist;

-	float dist;

-	vec3_t dir;

-

-	VectorSubtract(start, end, dir);

-	dist = VectorLength(dir);

-	//if crouch only area

-	if (AAS_AreaCrouch(areanum)) dist *= DISTANCEFACTOR_CROUCH;

-	//if swim area

-	else if (AAS_AreaSwim(areanum)) dist *= DISTANCEFACTOR_SWIM;

-	//normal walk area

-	else dist *= DISTANCEFACTOR_WALK;

-	//

-	intdist = (int) dist;

-	//make sure the distance isn't zero

-	if (intdist <= 0) intdist = 1;

-	return intdist;

-} //end of the function AAS_AreaTravelTime

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_CalculateAreaTravelTimes(void)

-{

-	int i, l, n, size;

-	char *ptr;

-	vec3_t end;

-	aas_reversedreachability_t *revreach;

-	aas_reversedlink_t *revlink;

-	aas_reachability_t *reach;

-	aas_areasettings_t *settings;

-	int starttime;

-

-	starttime = Sys_MilliSeconds();

-	//if there are still area travel times, free the memory

-	if (aasworld.areatraveltimes) FreeMemory(aasworld.areatraveltimes);

-	//get the total size of all the area travel times

-	size = aasworld.numareas * sizeof(unsigned short **);

-	for (i = 0; i < aasworld.numareas; i++)

-	{

-		revreach = &aasworld.reversedreachability[i];

-		//settings of the area

-		settings = &aasworld.areasettings[i];

-		//

-		size += settings->numreachableareas * sizeof(unsigned short *);

-		//

-		size += settings->numreachableareas * revreach->numlinks * sizeof(unsigned short);

-	} //end for

-	//allocate memory for the area travel times

-	ptr = (char *) GetClearedMemory(size);

-	aasworld.areatraveltimes = (unsigned short ***) ptr;

-	ptr += aasworld.numareas * sizeof(unsigned short **);

-	//calcluate the travel times for all the areas

-	for (i = 0; i < aasworld.numareas; i++)

-	{

-		//reversed reachabilities of this area

-		revreach = &aasworld.reversedreachability[i];

-		//settings of the area

-		settings = &aasworld.areasettings[i];

-		//

-		aasworld.areatraveltimes[i] = (unsigned short **) ptr;

-		ptr += settings->numreachableareas * sizeof(unsigned short *);

-		//

-		for (l = 0; l < settings->numreachableareas; l++)

-		{

-			aasworld.areatraveltimes[i][l] = (unsigned short *) ptr;

-			ptr += revreach->numlinks * sizeof(unsigned short);

-			//reachability link

-			reach = &aasworld.reachability[settings->firstreachablearea + l];

-			//

-			for (n = 0, revlink = revreach->first; revlink; revlink = revlink->next, n++)

-			{

-				VectorCopy(aasworld.reachability[revlink->linknum].end, end);

-				//

-				aasworld.areatraveltimes[i][l][n] = AAS_AreaTravelTime(i, end, reach->start);

-			} //end for

-		} //end for

-	} //end for

-#ifdef DEBUG

-	botimport.Print(PRT_MESSAGE, "area travel times %d msec\n", Sys_MilliSeconds() - starttime);

-#endif

-} //end of the function AAS_CalculateAreaTravelTimes

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-int AAS_PortalMaxTravelTime(int portalnum)

-{

-	int l, n, t, maxt;

-	aas_portal_t *portal;

-	aas_reversedreachability_t *revreach;

-	aas_reversedlink_t *revlink;

-	aas_areasettings_t *settings;

-

-	portal = &aasworld.portals[portalnum];

-	//reversed reachabilities of this portal area

-	revreach = &aasworld.reversedreachability[portal->areanum];

-	//settings of the portal area

-	settings = &aasworld.areasettings[portal->areanum];

-	//

-	maxt = 0;

-	for (l = 0; l < settings->numreachableareas; l++)

-	{

-		for (n = 0, revlink = revreach->first; revlink; revlink = revlink->next, n++)

-		{

-			t = aasworld.areatraveltimes[portal->areanum][l][n];

-			if (t > maxt)

-			{

-				maxt = t;

-			} //end if

-		} //end for

-	} //end for

-	return maxt;

-} //end of the function AAS_PortalMaxTravelTime

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_InitPortalMaxTravelTimes(void)

-{

-	int i;

-

-	if (aasworld.portalmaxtraveltimes) FreeMemory(aasworld.portalmaxtraveltimes);

-

-	aasworld.portalmaxtraveltimes = (int *) GetClearedMemory(aasworld.numportals * sizeof(int));

-

-	for (i = 0; i < aasworld.numportals; i++)

-	{

-		aasworld.portalmaxtraveltimes[i] = AAS_PortalMaxTravelTime(i);

-		//botimport.Print(PRT_MESSAGE, "portal %d max tt = %d\n", i, aasworld.portalmaxtraveltimes[i]);

-	} //end for

-} //end of the function AAS_InitPortalMaxTravelTimes

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-/*

-int AAS_FreeOldestCache(void)

-{

-	int i, j, bestcluster, bestarea, freed;

-	float besttime;

-	aas_routingcache_t *cache, *bestcache;

-

-	freed = qfalse;

-	besttime = 999999999;

-	bestcache = NULL;

-	bestcluster = 0;

-	bestarea = 0;

-	//refresh cluster cache

-	for (i = 0; i < aasworld.numclusters; i++)

-	{

-		for (j = 0; j < aasworld.clusters[i].numareas; j++)

-		{

-			for (cache = aasworld.clusterareacache[i][j]; cache; cache = cache->next)

-			{

-				//never remove cache leading towards a portal

-				if (aasworld.areasettings[cache->areanum].cluster < 0) continue;

-				//if this cache is older than the cache we found so far

-				if (cache->time < besttime)

-				{

-					bestcache = cache;

-					bestcluster = i;

-					bestarea = j;

-					besttime = cache->time;

-				} //end if

-			} //end for

-		} //end for

-	} //end for

-	if (bestcache)

-	{

-		cache = bestcache;

-		if (cache->prev) cache->prev->next = cache->next;

-		else aasworld.clusterareacache[bestcluster][bestarea] = cache->next;

-		if (cache->next) cache->next->prev = cache->prev;

-		AAS_FreeRoutingCache(cache);

-		freed = qtrue;

-	} //end if

-	besttime = 999999999;

-	bestcache = NULL;

-	bestarea = 0;

-	for (i = 0; i < aasworld.numareas; i++)

-	{

-		//refresh portal cache

-		for (cache = aasworld.portalcache[i]; cache; cache = cache->next)

-		{

-			if (cache->time < besttime)

-			{

-				bestcache = cache;

-				bestarea = i;

-				besttime = cache->time;

-			} //end if

-		} //end for

-	} //end for

-	if (bestcache)

-	{

-		cache = bestcache;

-		if (cache->prev) cache->prev->next = cache->next;

-		else aasworld.portalcache[bestarea] = cache->next;

-		if (cache->next) cache->next->prev = cache->prev;

-		AAS_FreeRoutingCache(cache);

-		freed = qtrue;

-	} //end if

-	return freed;

-} //end of the function AAS_FreeOldestCache

-*/

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-int AAS_FreeOldestCache(void)

-{

-	int clusterareanum;

-	aas_routingcache_t *cache;

-

-	for (cache = aasworld.oldestcache; cache; cache = cache->time_next) {

-		// never free area cache leading towards a portal

-		if (cache->type == CACHETYPE_AREA && aasworld.areasettings[cache->areanum].cluster < 0) {

-			continue;

-		}

-		break;

-	}

-	if (cache) {

-		// unlink the cache

-		if (cache->type == CACHETYPE_AREA) {

-			//number of the area in the cluster

-			clusterareanum = AAS_ClusterAreaNum(cache->cluster, cache->areanum);

-			// unlink from cluster area cache

-			if (cache->prev) cache->prev->next = cache->next;

-			else aasworld.clusterareacache[cache->cluster][clusterareanum] = cache->next;

-			if (cache->next) cache->next->prev = cache->prev;

-		}

-		else {

-			// unlink from portal cache

-			if (cache->prev) cache->prev->next = cache->next;

-			else aasworld.portalcache[cache->areanum] = cache->next;

-			if (cache->next) cache->next->prev = cache->prev;

-		}

-		AAS_FreeRoutingCache(cache);

-		return qtrue;

-	}

-	return qfalse;

-} //end of the function AAS_FreeOldestCache

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-aas_routingcache_t *AAS_AllocRoutingCache(int numtraveltimes)

-{

-	aas_routingcache_t *cache;

-	int size;

-

-	//

-	size = sizeof(aas_routingcache_t)

-						+ numtraveltimes * sizeof(unsigned short int)

-						+ numtraveltimes * sizeof(unsigned char);

-	//

-	routingcachesize += size;

-	//

-	cache = (aas_routingcache_t *) GetClearedMemory(size);

-	cache->reachabilities = (unsigned char *) cache + sizeof(aas_routingcache_t)

-								+ numtraveltimes * sizeof(unsigned short int);

-	cache->size = size;

-	return cache;

-} //end of the function AAS_AllocRoutingCache

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_FreeAllClusterAreaCache(void)

-{

-	int i, j;

-	aas_routingcache_t *cache, *nextcache;

-	aas_cluster_t *cluster;

-

-	//free all cluster cache if existing

-	if (!aasworld.clusterareacache) return;

-	//free caches

-	for (i = 0; i < aasworld.numclusters; i++)

-	{

-		cluster = &aasworld.clusters[i];

-		for (j = 0; j < cluster->numareas; j++)

-		{

-			for (cache = aasworld.clusterareacache[i][j]; cache; cache = nextcache)

-			{

-				nextcache = cache->next;

-				AAS_FreeRoutingCache(cache);

-			} //end for

-			aasworld.clusterareacache[i][j] = NULL;

-		} //end for

-	} //end for

-	//free the cluster cache array

-	FreeMemory(aasworld.clusterareacache);

-	aasworld.clusterareacache = NULL;

-} //end of the function AAS_FreeAllClusterAreaCache

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_InitClusterAreaCache(void)

-{

-	int i, size;

-	char *ptr;

-

-	//

-	for (size = 0, i = 0; i < aasworld.numclusters; i++)

-	{

-		size += aasworld.clusters[i].numareas;

-	} //end for

-	//two dimensional array with pointers for every cluster to routing cache

-	//for every area in that cluster

-	ptr = (char *) GetClearedMemory(

-				aasworld.numclusters * sizeof(aas_routingcache_t **) +

-				size * sizeof(aas_routingcache_t *));

-	aasworld.clusterareacache = (aas_routingcache_t ***) ptr;

-	ptr += aasworld.numclusters * sizeof(aas_routingcache_t **);

-	for (i = 0; i < aasworld.numclusters; i++)

-	{

-		aasworld.clusterareacache[i] = (aas_routingcache_t **) ptr;

-		ptr += aasworld.clusters[i].numareas * sizeof(aas_routingcache_t *);

-	} //end for

-} //end of the function AAS_InitClusterAreaCache

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_FreeAllPortalCache(void)

-{

-	int i;

-	aas_routingcache_t *cache, *nextcache;

-

-	//free all portal cache if existing

-	if (!aasworld.portalcache) return;

-	//free portal caches

-	for (i = 0; i < aasworld.numareas; i++)

-	{

-		for (cache = aasworld.portalcache[i]; cache; cache = nextcache)

-		{

-			nextcache = cache->next;

-			AAS_FreeRoutingCache(cache);

-		} //end for

-		aasworld.portalcache[i] = NULL;

-	} //end for

-	FreeMemory(aasworld.portalcache);

-	aasworld.portalcache = NULL;

-} //end of the function AAS_FreeAllPortalCache

-//===========================================================================

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-void AAS_InitPortalCache(void)

-{

-	//

-	aasworld.portalcache = (aas_routingcache_t **) GetClearedMemory(

-								aasworld.numareas * sizeof(aas_routingcache_t *));

-} //end of the function AAS_InitPortalCache

-//===========================================================================

-//

-// Parameter:				-

-// Returns:					-

-// Changes Globals:		-

-//===========================================================================

-void AAS_InitRoutingUpdate(void)

-{

-	int i, maxreachabilityareas;

-

-	//free routing update fields if already existing

-	if (aasworld.areaupdate) FreeMemory(aasworld.areaupdate);

-	//

-	maxreachabilityareas = 0;

-	for (i = 0; i < aasworld.numclusters; i++)

-	{

-		if (aasworld.clusters[i].numreachabilityareas > maxreachabilityareas)

-		{

-			maxreachabilityareas = aasworld.clusters[i].numreachabilityareas;

-		} //end if

-	} //end for

-	//allocate memory for the routing update fields

-	aasworld.areaupdate = (aas_routingupdate_t *) GetClearedMemory(

-									maxreachabilityareas * sizeof(aas_routingupdate_t));

-	//

-	if (aasworld.portalupdate) FreeMemory(aasworld.portalupdate);

-	//allocate memory for the portal update fields

-	aasworld.portalupdate = (aas_routingupdate_t *) GetClearedMemory(

-									(aasworld.numportals+1) * sizeof(aas_routingupdate_t));

-} //end of the function AAS_InitRoutingUpdate

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_CreateAllRoutingCache(void)

-{

-	int i, j, t;

-

-	aasworld.initialized = qtrue;

-	botimport.Print(PRT_MESSAGE, "AAS_CreateAllRoutingCache\n");

-	for (i = 1; i < aasworld.numareas; i++)

-	{

-		if (!AAS_AreaReachability(i)) continue;

-		for (j = 1; j < aasworld.numareas; j++)

-		{

-			if (i == j) continue;

-			if (!AAS_AreaReachability(j)) continue;

-			t = AAS_AreaTravelTimeToGoalArea(i, aasworld.areas[i].center, j, TFL_DEFAULT);

-			//Log_Write("traveltime from %d to %d is %d", i, j, t);

-		} //end for

-	} //end for

-	aasworld.initialized = qfalse;

-} //end of the function AAS_CreateAllRoutingCache

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-

-//the route cache header

-//this header is followed by numportalcache + numareacache aas_routingcache_t

-//structures that store routing cache

-typedef struct routecacheheader_s

-{

-	int ident;

-	int version;

-	int numareas;

-	int numclusters;

-	int areacrc;

-	int clustercrc;

-	int numportalcache;

-	int numareacache;

-} routecacheheader_t;

-

-#define RCID						(('C'<<24)+('R'<<16)+('E'<<8)+'M')

-#define RCVERSION					2

-

-//void AAS_DecompressVis(byte *in, int numareas, byte *decompressed);

-//int AAS_CompressVis(byte *vis, int numareas, byte *dest);

-

-void AAS_WriteRouteCache(void)

-{

-	int i, j, numportalcache, numareacache, totalsize;

-	aas_routingcache_t *cache;

-	aas_cluster_t *cluster;

-	fileHandle_t fp;

-	char filename[MAX_QPATH];

-	routecacheheader_t routecacheheader;

-

-	numportalcache = 0;

-	for (i = 0; i < aasworld.numareas; i++)

-	{

-		for (cache = aasworld.portalcache[i]; cache; cache = cache->next)

-		{

-			numportalcache++;

-		} //end for

-	} //end for

-	numareacache = 0;

-	for (i = 0; i < aasworld.numclusters; i++)

-	{

-		cluster = &aasworld.clusters[i];

-		for (j = 0; j < cluster->numareas; j++)

-		{

-			for (cache = aasworld.clusterareacache[i][j]; cache; cache = cache->next)

-			{

-				numareacache++;

-			} //end for

-		} //end for

-	} //end for

-	// open the file for writing

-	Com_sprintf(filename, MAX_QPATH, "maps/%s.rcd", aasworld.mapname);

-	botimport.FS_FOpenFile( filename, &fp, FS_WRITE );

-	if (!fp)

-	{

-		AAS_Error("Unable to open file: %s\n", filename);

-		return;

-	} //end if

-	//create the header

-	routecacheheader.ident = RCID;

-	routecacheheader.version = RCVERSION;

-	routecacheheader.numareas = aasworld.numareas;

-	routecacheheader.numclusters = aasworld.numclusters;

-	routecacheheader.areacrc = CRC_ProcessString( (unsigned char *)aasworld.areas, sizeof(aas_area_t) * aasworld.numareas );

-	routecacheheader.clustercrc = CRC_ProcessString( (unsigned char *)aasworld.clusters, sizeof(aas_cluster_t) * aasworld.numclusters );

-	routecacheheader.numportalcache = numportalcache;

-	routecacheheader.numareacache = numareacache;

-	//write the header

-	botimport.FS_Write(&routecacheheader, sizeof(routecacheheader_t), fp);

-	//

-	totalsize = 0;

-	//write all the cache

-	for (i = 0; i < aasworld.numareas; i++)

-	{

-		for (cache = aasworld.portalcache[i]; cache; cache = cache->next)

-		{

-			botimport.FS_Write(cache, cache->size, fp);

-			totalsize += cache->size;

-		} //end for

-	} //end for

-	for (i = 0; i < aasworld.numclusters; i++)

-	{

-		cluster = &aasworld.clusters[i];

-		for (j = 0; j < cluster->numareas; j++)

-		{

-			for (cache = aasworld.clusterareacache[i][j]; cache; cache = cache->next)

-			{

-				botimport.FS_Write(cache, cache->size, fp);

-				totalsize += cache->size;

-			} //end for

-		} //end for

-	} //end for

-	// write the visareas

-	/*

-	for (i = 0; i < aasworld.numareas; i++)

-	{

-		if (!aasworld.areavisibility[i]) {

-			size = 0;

-			botimport.FS_Write(&size, sizeof(int), fp);

-			continue;

-		}

-		AAS_DecompressVis( aasworld.areavisibility[i], aasworld.numareas, aasworld.decompressedvis );

-		size = AAS_CompressVis( aasworld.decompressedvis, aasworld.numareas, aasworld.decompressedvis );

-		botimport.FS_Write(&size, sizeof(int), fp);

-		botimport.FS_Write(aasworld.decompressedvis, size, fp);

-	}

-	*/

-	//

-	botimport.FS_FCloseFile(fp);

-	botimport.Print(PRT_MESSAGE, "\nroute cache written to %s\n", filename);

-	botimport.Print(PRT_MESSAGE, "written %d bytes of routing cache\n", totalsize);

-} //end of the function AAS_WriteRouteCache

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-aas_routingcache_t *AAS_ReadCache(fileHandle_t fp)

-{

-	int size;

-	aas_routingcache_t *cache;

-

-	botimport.FS_Read(&size, sizeof(size), fp);

-	cache = (aas_routingcache_t *) GetMemory(size);

-	cache->size = size;

-	botimport.FS_Read((unsigned char *)cache + sizeof(size), size - sizeof(size), fp);

-	cache->reachabilities = (unsigned char *) cache + sizeof(aas_routingcache_t) - sizeof(unsigned short) +

-		(size - sizeof(aas_routingcache_t) + sizeof(unsigned short)) / 3 * 2;

-	return cache;

-} //end of the function AAS_ReadCache

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-int AAS_ReadRouteCache(void)

-{

-	int i, clusterareanum;//, size;

-	fileHandle_t fp;

-	char filename[MAX_QPATH];

-	routecacheheader_t routecacheheader;

-	aas_routingcache_t *cache;

-

-	Com_sprintf(filename, MAX_QPATH, "maps/%s.rcd", aasworld.mapname);

-	botimport.FS_FOpenFile( filename, &fp, FS_READ );

-	if (!fp)

-	{

-		return qfalse;

-	} //end if

-	botimport.FS_Read(&routecacheheader, sizeof(routecacheheader_t), fp );

-	if (routecacheheader.ident != RCID)

-	{

-		AAS_Error("%s is not a route cache dump\n");

-		return qfalse;

-	} //end if

-	if (routecacheheader.version != RCVERSION)

-	{

-		AAS_Error("route cache dump has wrong version %d, should be %d", routecacheheader.version, RCVERSION);

-		return qfalse;

-	} //end if

-	if (routecacheheader.numareas != aasworld.numareas)

-	{

-		//AAS_Error("route cache dump has wrong number of areas\n");

-		return qfalse;

-	} //end if

-	if (routecacheheader.numclusters != aasworld.numclusters)

-	{

-		//AAS_Error("route cache dump has wrong number of clusters\n");

-		return qfalse;

-	} //end if

-	if (routecacheheader.areacrc !=

-		CRC_ProcessString( (unsigned char *)aasworld.areas, sizeof(aas_area_t) * aasworld.numareas ))

-	{

-		//AAS_Error("route cache dump area CRC incorrect\n");

-		return qfalse;

-	} //end if

-	if (routecacheheader.clustercrc !=

-		CRC_ProcessString( (unsigned char *)aasworld.clusters, sizeof(aas_cluster_t) * aasworld.numclusters ))

-	{

-		//AAS_Error("route cache dump cluster CRC incorrect\n");

-		return qfalse;

-	} //end if

-	//read all the portal cache

-	for (i = 0; i < routecacheheader.numportalcache; i++)

-	{

-		cache = AAS_ReadCache(fp);

-		cache->next = aasworld.portalcache[cache->areanum];

-		cache->prev = NULL;

-		if (aasworld.portalcache[cache->areanum])

-			aasworld.portalcache[cache->areanum]->prev = cache;

-		aasworld.portalcache[cache->areanum] = cache;

-	} //end for

-	//read all the cluster area cache

-	for (i = 0; i < routecacheheader.numareacache; i++)

-	{

-		cache = AAS_ReadCache(fp);

-		clusterareanum = AAS_ClusterAreaNum(cache->cluster, cache->areanum);

-		cache->next = aasworld.clusterareacache[cache->cluster][clusterareanum];

-		cache->prev = NULL;

-		if (aasworld.clusterareacache[cache->cluster][clusterareanum])

-			aasworld.clusterareacache[cache->cluster][clusterareanum]->prev = cache;

-		aasworld.clusterareacache[cache->cluster][clusterareanum] = cache;

-	} //end for

-	// read the visareas

-	/*

-	aasworld.areavisibility = (byte **) GetClearedMemory(aasworld.numareas * sizeof(byte *));

-	aasworld.decompressedvis = (byte *) GetClearedMemory(aasworld.numareas * sizeof(byte));

-	for (i = 0; i < aasworld.numareas; i++)

-	{

-		botimport.FS_Read(&size, sizeof(size), fp );

-		if (size) {

-			aasworld.areavisibility[i] = (byte *) GetMemory(size);

-			botimport.FS_Read(aasworld.areavisibility[i], size, fp );

-		}

-	}

-	*/

-	//

-	botimport.FS_FCloseFile(fp);

-	return qtrue;

-} //end of the function AAS_ReadRouteCache

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-#define MAX_REACHABILITYPASSAREAS		32

-

-void AAS_InitReachabilityAreas(void)

-{

-	int i, j, numareas, areas[MAX_REACHABILITYPASSAREAS];

-	int numreachareas;

-	aas_reachability_t *reach;

-	vec3_t start, end;

-

-	if (aasworld.reachabilityareas)

-		FreeMemory(aasworld.reachabilityareas);

-	if (aasworld.reachabilityareaindex)

-		FreeMemory(aasworld.reachabilityareaindex);

-

-	aasworld.reachabilityareas = (aas_reachabilityareas_t *)

-				GetClearedMemory(aasworld.reachabilitysize * sizeof(aas_reachabilityareas_t));

-	aasworld.reachabilityareaindex = (int *)

-				GetClearedMemory(aasworld.reachabilitysize * MAX_REACHABILITYPASSAREAS * sizeof(int));

-	numreachareas = 0;

-	for (i = 0; i < aasworld.reachabilitysize; i++)

-	{

-		reach = &aasworld.reachability[i];

-		numareas = 0;

-		switch(reach->traveltype & TRAVELTYPE_MASK)

-		{

-			//trace areas from start to end

-			case TRAVEL_BARRIERJUMP:

-			case TRAVEL_WATERJUMP:

-				VectorCopy(reach->start, end);

-				end[2] = reach->end[2];

-				numareas = AAS_TraceAreas(reach->start, end, areas, NULL, MAX_REACHABILITYPASSAREAS);

-				break;

-			case TRAVEL_WALKOFFLEDGE:

-				VectorCopy(reach->end, start);

-				start[2] = reach->start[2];

-				numareas = AAS_TraceAreas(start, reach->end, areas, NULL, MAX_REACHABILITYPASSAREAS);

-				break;

-			case TRAVEL_GRAPPLEHOOK:

-				numareas = AAS_TraceAreas(reach->start, reach->end, areas, NULL, MAX_REACHABILITYPASSAREAS);

-				break;

-

-			//trace arch

-			case TRAVEL_JUMP: break;

-			case TRAVEL_ROCKETJUMP: break;

-			case TRAVEL_BFGJUMP: break;

-			case TRAVEL_JUMPPAD: break;

-

-			//trace from reach->start to entity center, along entity movement

-			//and from entity center to reach->end

-			case TRAVEL_ELEVATOR: break;

-			case TRAVEL_FUNCBOB: break;

-

-			//no areas in between

-			case TRAVEL_WALK: break;

-			case TRAVEL_CROUCH: break;

-			case TRAVEL_LADDER: break;

-			case TRAVEL_SWIM: break;

-			case TRAVEL_TELEPORT: break;

-			default: break;

-		} //end switch

-		aasworld.reachabilityareas[i].firstarea = numreachareas;

-		aasworld.reachabilityareas[i].numareas = numareas;

-		for (j = 0; j < numareas; j++)

-		{

-			aasworld.reachabilityareaindex[numreachareas++] = areas[j];

-		} //end for

-	} //end for

-} //end of the function AAS_InitReachabilityAreas

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_InitRouting(void)

-{

-	AAS_InitTravelFlagFromType();

-	//

-	AAS_InitAreaContentsTravelFlags();

-	//initialize the routing update fields

-	AAS_InitRoutingUpdate();

-	//create reversed reachability links used by the routing update algorithm

-	AAS_CreateReversedReachability();

-	//initialize the cluster cache

-	AAS_InitClusterAreaCache();

-	//initialize portal cache

-	AAS_InitPortalCache();

-	//initialize the area travel times

-	AAS_CalculateAreaTravelTimes();

-	//calculate the maximum travel times through portals

-	AAS_InitPortalMaxTravelTimes();

-	//get the areas reachabilities go through

-	AAS_InitReachabilityAreas();

-	//

-#ifdef ROUTING_DEBUG

-	numareacacheupdates = 0;

-	numportalcacheupdates = 0;

-#endif //ROUTING_DEBUG

-	//

-	routingcachesize = 0;

-	max_routingcachesize = 1024 * (int) LibVarValue("max_routingcache", "4096");

-	// read any routing cache if available

-	AAS_ReadRouteCache();

-} //end of the function AAS_InitRouting

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_FreeRoutingCaches(void)

-{

-	// free all the existing cluster area cache

-	AAS_FreeAllClusterAreaCache();

-	// free all the existing portal cache

-	AAS_FreeAllPortalCache();

-	// free cached travel times within areas

-	if (aasworld.areatraveltimes) FreeMemory(aasworld.areatraveltimes);

-	aasworld.areatraveltimes = NULL;

-	// free cached maximum travel time through cluster portals

-	if (aasworld.portalmaxtraveltimes) FreeMemory(aasworld.portalmaxtraveltimes);

-	aasworld.portalmaxtraveltimes = NULL;

-	// free reversed reachability links

-	if (aasworld.reversedreachability) FreeMemory(aasworld.reversedreachability);

-	aasworld.reversedreachability = NULL;

-	// free routing algorithm memory

-	if (aasworld.areaupdate) FreeMemory(aasworld.areaupdate);

-	aasworld.areaupdate = NULL;

-	if (aasworld.portalupdate) FreeMemory(aasworld.portalupdate);

-	aasworld.portalupdate = NULL;

-	// free lists with areas the reachabilities go through

-	if (aasworld.reachabilityareas) FreeMemory(aasworld.reachabilityareas);

-	aasworld.reachabilityareas = NULL;

-	// free the reachability area index

-	if (aasworld.reachabilityareaindex) FreeMemory(aasworld.reachabilityareaindex);

-	aasworld.reachabilityareaindex = NULL;

-	// free area contents travel flags look up table

-	if (aasworld.areacontentstravelflags) FreeMemory(aasworld.areacontentstravelflags);

-	aasworld.areacontentstravelflags = NULL;

-} //end of the function AAS_FreeRoutingCaches

-//===========================================================================

-// update the given routing cache

-//

-// Parameter:			areacache		: routing cache to update

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_UpdateAreaRoutingCache(aas_routingcache_t *areacache)

-{

-	int i, nextareanum, cluster, badtravelflags, clusterareanum, linknum;

-	int numreachabilityareas;

-	unsigned short int t, startareatraveltimes[128]; //NOTE: not more than 128 reachabilities per area allowed

-	aas_routingupdate_t *updateliststart, *updatelistend, *curupdate, *nextupdate;

-	aas_reachability_t *reach;

-	aas_reversedreachability_t *revreach;

-	aas_reversedlink_t *revlink;

-

-#ifdef ROUTING_DEBUG

-	numareacacheupdates++;

-#endif //ROUTING_DEBUG

-	//number of reachability areas within this cluster

-	numreachabilityareas = aasworld.clusters[areacache->cluster].numreachabilityareas;

-	//

-	aasworld.frameroutingupdates++;

-	//clear the routing update fields

-//	Com_Memset(aasworld.areaupdate, 0, aasworld.numareas * sizeof(aas_routingupdate_t));

-	//

-	badtravelflags = ~areacache->travelflags;

-	//

-	clusterareanum = AAS_ClusterAreaNum(areacache->cluster, areacache->areanum);

-	if (clusterareanum >= numreachabilityareas) return;

-	//

-	Com_Memset(startareatraveltimes, 0, sizeof(startareatraveltimes));

-	//

-	curupdate = &aasworld.areaupdate[clusterareanum];

-	curupdate->areanum = areacache->areanum;

-	//VectorCopy(areacache->origin, curupdate->start);

-	curupdate->areatraveltimes = startareatraveltimes;

-	curupdate->tmptraveltime = areacache->starttraveltime;

-	//

-	areacache->traveltimes[clusterareanum] = areacache->starttraveltime;

-	//put the area to start with in the current read list

-	curupdate->next = NULL;

-	curupdate->prev = NULL;

-	updateliststart = curupdate;

-	updatelistend = curupdate;

-	//while there are updates in the current list

-	while (updateliststart)

-	{

-		curupdate = updateliststart;

-		//

-		if (curupdate->next) curupdate->next->prev = NULL;

-		else updatelistend = NULL;

-		updateliststart = curupdate->next;

-		//

-		curupdate->inlist = qfalse;

-		//check all reversed reachability links

-		revreach = &aasworld.reversedreachability[curupdate->areanum];

-		//

-		for (i = 0, revlink = revreach->first; revlink; revlink = revlink->next, i++)

-		{

-			linknum = revlink->linknum;

-			reach = &aasworld.reachability[linknum];

-			//if there is used an undesired travel type

-			if (AAS_TravelFlagForType_inline(reach->traveltype) & badtravelflags) continue;

-			//if not allowed to enter the next area

-			if (aasworld.areasettings[reach->areanum].areaflags & AREA_DISABLED) continue;

-			//if the next area has a not allowed travel flag

-			if (AAS_AreaContentsTravelFlags_inline(reach->areanum) & badtravelflags) continue;

-			//number of the area the reversed reachability leads to

-			nextareanum = revlink->areanum;

-			//get the cluster number of the area

-			cluster = aasworld.areasettings[nextareanum].cluster;

-			//don't leave the cluster

-			if (cluster > 0 && cluster != areacache->cluster) continue;

-			//get the number of the area in the cluster

-			clusterareanum = AAS_ClusterAreaNum(areacache->cluster, nextareanum);

-			if (clusterareanum >= numreachabilityareas) continue;

-			//time already travelled plus the traveltime through

-			//the current area plus the travel time from the reachability

-			t = curupdate->tmptraveltime +

-						//AAS_AreaTravelTime(curupdate->areanum, curupdate->start, reach->end) +

-						curupdate->areatraveltimes[i] +

-							reach->traveltime;

-			//

-			if (!areacache->traveltimes[clusterareanum] ||

-					areacache->traveltimes[clusterareanum] > t)

-			{

-				areacache->traveltimes[clusterareanum] = t;

-				areacache->reachabilities[clusterareanum] = linknum - aasworld.areasettings[nextareanum].firstreachablearea;

-				nextupdate = &aasworld.areaupdate[clusterareanum];

-				nextupdate->areanum = nextareanum;

-				nextupdate->tmptraveltime = t;

-				//VectorCopy(reach->start, nextupdate->start);

-				nextupdate->areatraveltimes = aasworld.areatraveltimes[nextareanum][linknum -

-													aasworld.areasettings[nextareanum].firstreachablearea];

-				if (!nextupdate->inlist)

-				{

-					// we add the update to the end of the list

-					// we could also use a B+ tree to have a real sorted list

-					// on travel time which makes for faster routing updates

-					nextupdate->next = NULL;

-					nextupdate->prev = updatelistend;

-					if (updatelistend) updatelistend->next = nextupdate;

-					else updateliststart = nextupdate;

-					updatelistend = nextupdate;

-					nextupdate->inlist = qtrue;

-				} //end if

-			} //end if

-		} //end for

-	} //end while

-} //end of the function AAS_UpdateAreaRoutingCache

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-aas_routingcache_t *AAS_GetAreaRoutingCache(int clusternum, int areanum, int travelflags)

-{

-	int clusterareanum;

-	aas_routingcache_t *cache, *clustercache;

-

-	//number of the area in the cluster

-	clusterareanum = AAS_ClusterAreaNum(clusternum, areanum);

-	//pointer to the cache for the area in the cluster

-	clustercache = aasworld.clusterareacache[clusternum][clusterareanum];

-	//find the cache without undesired travel flags

-	for (cache = clustercache; cache; cache = cache->next)

-	{

-		//if there aren't used any undesired travel types for the cache

-		if (cache->travelflags == travelflags) break;

-	} //end for

-	//if there was no cache

-	if (!cache)

-	{

-		cache = AAS_AllocRoutingCache(aasworld.clusters[clusternum].numreachabilityareas);

-		cache->cluster = clusternum;

-		cache->areanum = areanum;

-		VectorCopy(aasworld.areas[areanum].center, cache->origin);

-		cache->starttraveltime = 1;

-		cache->travelflags = travelflags;

-		cache->prev = NULL;

-		cache->next = clustercache;

-		if (clustercache) clustercache->prev = cache;

-		aasworld.clusterareacache[clusternum][clusterareanum] = cache;

-		AAS_UpdateAreaRoutingCache(cache);

-	} //end if

-	else

-	{

-		AAS_UnlinkCache(cache);

-	} //end else

-	//the cache has been accessed

-	cache->time = AAS_RoutingTime();

-	cache->type = CACHETYPE_AREA;

-	AAS_LinkCache(cache);

-	return cache;

-} //end of the function AAS_GetAreaRoutingCache

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_UpdatePortalRoutingCache(aas_routingcache_t *portalcache)

-{

-	int i, portalnum, clusterareanum, clusternum;

-	unsigned short int t;

-	aas_portal_t *portal;

-	aas_cluster_t *cluster;

-	aas_routingcache_t *cache;

-	aas_routingupdate_t *updateliststart, *updatelistend, *curupdate, *nextupdate;

-

-#ifdef ROUTING_DEBUG

-	numportalcacheupdates++;

-#endif //ROUTING_DEBUG

-	//clear the routing update fields

-//	Com_Memset(aasworld.portalupdate, 0, (aasworld.numportals+1) * sizeof(aas_routingupdate_t));

-	//

-	curupdate = &aasworld.portalupdate[aasworld.numportals];

-	curupdate->cluster = portalcache->cluster;

-	curupdate->areanum = portalcache->areanum;

-	curupdate->tmptraveltime = portalcache->starttraveltime;

-	//if the start area is a cluster portal, store the travel time for that portal

-	clusternum = aasworld.areasettings[portalcache->areanum].cluster;

-	if (clusternum < 0)

-	{

-		portalcache->traveltimes[-clusternum] = portalcache->starttraveltime;

-	} //end if

-	//put the area to start with in the current read list

-	curupdate->next = NULL;

-	curupdate->prev = NULL;

-	updateliststart = curupdate;

-	updatelistend = curupdate;

-	//while there are updates in the current list

-	while (updateliststart)

-	{

-		curupdate = updateliststart;

-		//remove the current update from the list

-		if (curupdate->next) curupdate->next->prev = NULL;

-		else updatelistend = NULL;

-		updateliststart = curupdate->next;

-		//current update is removed from the list

-		curupdate->inlist = qfalse;

-		//

-		cluster = &aasworld.clusters[curupdate->cluster];

-		//

-		cache = AAS_GetAreaRoutingCache(curupdate->cluster,

-								curupdate->areanum, portalcache->travelflags);

-		//take all portals of the cluster

-		for (i = 0; i < cluster->numportals; i++)

-		{

-			portalnum = aasworld.portalindex[cluster->firstportal + i];

-			portal = &aasworld.portals[portalnum];

-			//if this is the portal of the current update continue

-			if (portal->areanum == curupdate->areanum) continue;

-			//

-			clusterareanum = AAS_ClusterAreaNum(curupdate->cluster, portal->areanum);

-			if (clusterareanum >= cluster->numreachabilityareas) continue;

-			//

-			t = cache->traveltimes[clusterareanum];

-			if (!t) continue;

-			t += curupdate->tmptraveltime;

-			//

-			if (!portalcache->traveltimes[portalnum] ||

-					portalcache->traveltimes[portalnum] > t)

-			{

-				portalcache->traveltimes[portalnum] = t;

-				nextupdate = &aasworld.portalupdate[portalnum];

-				if (portal->frontcluster == curupdate->cluster)

-				{

-					nextupdate->cluster = portal->backcluster;

-				} //end if

-				else

-				{

-					nextupdate->cluster = portal->frontcluster;

-				} //end else

-				nextupdate->areanum = portal->areanum;

-				//add travel time through the actual portal area for the next update

-				nextupdate->tmptraveltime = t + aasworld.portalmaxtraveltimes[portalnum];

-				if (!nextupdate->inlist)

-				{

-					// we add the update to the end of the list

-					// we could also use a B+ tree to have a real sorted list

-					// on travel time which makes for faster routing updates

-					nextupdate->next = NULL;

-					nextupdate->prev = updatelistend;

-					if (updatelistend) updatelistend->next = nextupdate;

-					else updateliststart = nextupdate;

-					updatelistend = nextupdate;

-					nextupdate->inlist = qtrue;

-				} //end if

-			} //end if

-		} //end for

-	} //end while

-} //end of the function AAS_UpdatePortalRoutingCache

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-aas_routingcache_t *AAS_GetPortalRoutingCache(int clusternum, int areanum, int travelflags)

-{

-	aas_routingcache_t *cache;

-

-	//find the cached portal routing if existing

-	for (cache = aasworld.portalcache[areanum]; cache; cache = cache->next)

-	{

-		if (cache->travelflags == travelflags) break;

-	} //end for

-	//if the portal routing isn't cached

-	if (!cache)

-	{

-		cache = AAS_AllocRoutingCache(aasworld.numportals);

-		cache->cluster = clusternum;

-		cache->areanum = areanum;

-		VectorCopy(aasworld.areas[areanum].center, cache->origin);

-		cache->starttraveltime = 1;

-		cache->travelflags = travelflags;

-		//add the cache to the cache list

-		cache->prev = NULL;

-		cache->next = aasworld.portalcache[areanum];

-		if (aasworld.portalcache[areanum]) aasworld.portalcache[areanum]->prev = cache;

-		aasworld.portalcache[areanum] = cache;

-		//update the cache

-		AAS_UpdatePortalRoutingCache(cache);

-	} //end if

-	else

-	{

-		AAS_UnlinkCache(cache);

-	} //end else

-	//the cache has been accessed

-	cache->time = AAS_RoutingTime();

-	cache->type = CACHETYPE_PORTAL;

-	AAS_LinkCache(cache);

-	return cache;

-} //end of the function AAS_GetPortalRoutingCache

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-int AAS_AreaRouteToGoalArea(int areanum, vec3_t origin, int goalareanum, int travelflags, int *traveltime, int *reachnum)

-{

-	int clusternum, goalclusternum, portalnum, i, clusterareanum, bestreachnum;

-	unsigned short int t, besttime;

-	aas_portal_t *portal;

-	aas_cluster_t *cluster;

-	aas_routingcache_t *areacache, *portalcache;

-	aas_reachability_t *reach;

-

-	if (!aasworld.initialized) return qfalse;

-

-	if (areanum == goalareanum)

-	{

-		*traveltime = 1;

-		*reachnum = 0;

-		return qtrue;

-	}

-	//

-	if (areanum <= 0 || areanum >= aasworld.numareas)

-	{

-		if (bot_developer)

-		{

-			botimport.Print(PRT_ERROR, "AAS_AreaTravelTimeToGoalArea: areanum %d out of range\n", areanum);

-		} //end if

-		return qfalse;

-	} //end if

-	if (goalareanum <= 0 || goalareanum >= aasworld.numareas)

-	{

-		if (bot_developer)

-		{

-			botimport.Print(PRT_ERROR, "AAS_AreaTravelTimeToGoalArea: goalareanum %d out of range\n", goalareanum);

-		} //end if

-		return qfalse;

-	} //end if

-	// make sure the routing cache doesn't grow to large

-	while(AvailableMemory() < 1 * 1024 * 1024) {

-		if (!AAS_FreeOldestCache()) break;

-	}

-	//

-	if (AAS_AreaDoNotEnter(areanum) || AAS_AreaDoNotEnter(goalareanum))

-	{

-		travelflags |= TFL_DONOTENTER;

-	} //end if

-	//NOTE: the number of routing updates is limited per frame

-	/*

-	if (aasworld.frameroutingupdates > MAX_FRAMEROUTINGUPDATES)

-	{

-#ifdef DEBUG

-		//Log_Write("WARNING: AAS_AreaTravelTimeToGoalArea: frame routing updates overflowed");

-#endif

-		return 0;

-	} //end if

-	*/

-	//

-	clusternum = aasworld.areasettings[areanum].cluster;

-	goalclusternum = aasworld.areasettings[goalareanum].cluster;

-	//check if the area is a portal of the goal area cluster

-	if (clusternum < 0 && goalclusternum > 0)

-	{

-		portal = &aasworld.portals[-clusternum];

-		if (portal->frontcluster == goalclusternum ||

-				portal->backcluster == goalclusternum)

-		{

-			clusternum = goalclusternum;

-		} //end if

-	} //end if

-	//check if the goalarea is a portal of the area cluster

-	else if (clusternum > 0 && goalclusternum < 0)

-	{

-		portal = &aasworld.portals[-goalclusternum];

-		if (portal->frontcluster == clusternum ||

-				portal->backcluster == clusternum)

-		{

-			goalclusternum = clusternum;

-		} //end if

-	} //end if

-	//if both areas are in the same cluster

-	//NOTE: there might be a shorter route via another cluster!!! but we don't care

-	if (clusternum > 0 && goalclusternum > 0 && clusternum == goalclusternum)

-	{

-		//

-		areacache = AAS_GetAreaRoutingCache(clusternum, goalareanum, travelflags);

-		//the number of the area in the cluster

-		clusterareanum = AAS_ClusterAreaNum(clusternum, areanum);

-		//the cluster the area is in

-		cluster = &aasworld.clusters[clusternum];

-		//if the area is NOT a reachability area

-		if (clusterareanum >= cluster->numreachabilityareas) return 0;

-		//if it is possible to travel to the goal area through this cluster

-		if (areacache->traveltimes[clusterareanum] != 0)

-		{

-			*reachnum = aasworld.areasettings[areanum].firstreachablearea +

-							areacache->reachabilities[clusterareanum];

-			if (!origin) {

-				*traveltime = areacache->traveltimes[clusterareanum];

-				return qtrue;

-			}

-			reach = &aasworld.reachability[*reachnum];

-			*traveltime = areacache->traveltimes[clusterareanum] +

-							AAS_AreaTravelTime(areanum, origin, reach->start);

-			//

-			return qtrue;

-		} //end if

-	} //end if

-	//

-	clusternum = aasworld.areasettings[areanum].cluster;

-	goalclusternum = aasworld.areasettings[goalareanum].cluster;

-	//if the goal area is a portal

-	if (goalclusternum < 0)

-	{

-		//just assume the goal area is part of the front cluster

-		portal = &aasworld.portals[-goalclusternum];

-		goalclusternum = portal->frontcluster;

-	} //end if

-	//get the portal routing cache

-	portalcache = AAS_GetPortalRoutingCache(goalclusternum, goalareanum, travelflags);

-	//if the area is a cluster portal, read directly from the portal cache

-	if (clusternum < 0)

-	{

-		*traveltime = portalcache->traveltimes[-clusternum];

-		*reachnum = aasworld.areasettings[areanum].firstreachablearea +

-						portalcache->reachabilities[-clusternum];

-		return qtrue;

-	} //end if

-	//

-	besttime = 0;

-	bestreachnum = -1;

-	//the cluster the area is in

-	cluster = &aasworld.clusters[clusternum];

-	//find the portal of the area cluster leading towards the goal area

-	for (i = 0; i < cluster->numportals; i++)

-	{

-		portalnum = aasworld.portalindex[cluster->firstportal + i];

-		//if the goal area isn't reachable from the portal

-		if (!portalcache->traveltimes[portalnum]) continue;

-		//

-		portal = &aasworld.portals[portalnum];

-		//get the cache of the portal area

-		areacache = AAS_GetAreaRoutingCache(clusternum, portal->areanum, travelflags);

-		//current area inside the current cluster

-		clusterareanum = AAS_ClusterAreaNum(clusternum, areanum);

-		//if the area is NOT a reachability area

-		if (clusterareanum >= cluster->numreachabilityareas) continue;

-		//if the portal is NOT reachable from this area

-		if (!areacache->traveltimes[clusterareanum]) continue;

-		//total travel time is the travel time the portal area is from

-		//the goal area plus the travel time towards the portal area

-		t = portalcache->traveltimes[portalnum] + areacache->traveltimes[clusterareanum];

-		//FIXME: add the exact travel time through the actual portal area

-		//NOTE: for now we just add the largest travel time through the portal area

-		//		because we can't directly calculate the exact travel time

-		//		to be more specific we don't know which reachability was used to travel

-		//		into the portal area

-		t += aasworld.portalmaxtraveltimes[portalnum];

-		//

-		if (origin)

-		{

-			*reachnum = aasworld.areasettings[areanum].firstreachablearea +

-							areacache->reachabilities[clusterareanum];

-			reach = aasworld.reachability + *reachnum;

-			t += AAS_AreaTravelTime(areanum, origin, reach->start);

-		} //end if

-		//if the time is better than the one already found

-		if (!besttime || t < besttime)

-		{

-			bestreachnum = *reachnum;

-			besttime = t;

-		} //end if

-	} //end for

-	if (bestreachnum < 0) {

-		return qfalse;

-	}

-	*reachnum = bestreachnum;

-	*traveltime = besttime;

-	return qtrue;

-} //end of the function AAS_AreaRouteToGoalArea

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-int AAS_AreaTravelTimeToGoalArea(int areanum, vec3_t origin, int goalareanum, int travelflags)

-{

-	int traveltime, reachnum;

-

-	if (AAS_AreaRouteToGoalArea(areanum, origin, goalareanum, travelflags, &traveltime, &reachnum))

-	{

-		return traveltime;

-	}

-	return 0;

-} //end of the function AAS_AreaTravelTimeToGoalArea

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-int AAS_AreaReachabilityToGoalArea(int areanum, vec3_t origin, int goalareanum, int travelflags)

-{

-	int traveltime, reachnum;

-

-	if (AAS_AreaRouteToGoalArea(areanum, origin, goalareanum, travelflags, &traveltime, &reachnum))

-	{

-		return reachnum;

-	}

-	return 0;

-} //end of the function AAS_AreaReachabilityToGoalArea

-//===========================================================================

-// predict the route and stop on one of the stop events

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-int AAS_PredictRoute(struct aas_predictroute_s *route, int areanum, vec3_t origin,

-							int goalareanum, int travelflags, int maxareas, int maxtime,

-							int stopevent, int stopcontents, int stoptfl, int stopareanum)

-{

-	int curareanum, reachnum, i, j, testareanum;

-	vec3_t curorigin;

-	aas_reachability_t *reach;

-	aas_reachabilityareas_t *reachareas;

-

-	//init output

-	route->stopevent = RSE_NONE;

-	route->endarea = goalareanum;

-	route->endcontents = 0;

-	route->endtravelflags = 0;

-	VectorCopy(origin, route->endpos);

-	route->time = 0;

-

-	curareanum = areanum;

-	VectorCopy(origin, curorigin);

-

-	for (i = 0; curareanum != goalareanum && (!maxareas || i < maxareas) && i < aasworld.numareas; i++)

-	{

-		reachnum = AAS_AreaReachabilityToGoalArea(curareanum, curorigin, goalareanum, travelflags);

-		if (!reachnum)

-		{

-			route->stopevent = RSE_NOROUTE;

-			return qfalse;

-		} //end if

-		reach = &aasworld.reachability[reachnum];

-		//

-		if (stopevent & RSE_USETRAVELTYPE)

-		{

-			if (AAS_TravelFlagForType_inline(reach->traveltype) & stoptfl)

-			{

-				route->stopevent = RSE_USETRAVELTYPE;

-				route->endarea = curareanum;

-				route->endcontents = aasworld.areasettings[curareanum].contents;

-				route->endtravelflags = AAS_TravelFlagForType_inline(reach->traveltype);

-				VectorCopy(reach->start, route->endpos);

-				return qtrue;

-			} //end if

-			if (AAS_AreaContentsTravelFlags_inline(reach->areanum) & stoptfl)

-			{

-				route->stopevent = RSE_USETRAVELTYPE;

-				route->endarea = reach->areanum;

-				route->endcontents = aasworld.areasettings[reach->areanum].contents;

-				route->endtravelflags = AAS_AreaContentsTravelFlags_inline(reach->areanum);

-				VectorCopy(reach->end, route->endpos);

-				route->time += AAS_AreaTravelTime(areanum, origin, reach->start);

-				route->time += reach->traveltime;

-				return qtrue;

-			} //end if

-		} //end if

-		reachareas = &aasworld.reachabilityareas[reachnum];

-		for (j = 0; j < reachareas->numareas + 1; j++)

-		{

-			if (j >= reachareas->numareas)

-				testareanum = reach->areanum;

-			else

-				testareanum = aasworld.reachabilityareaindex[reachareas->firstarea + j];

-			if (stopevent & RSE_ENTERCONTENTS)

-			{

-				if (aasworld.areasettings[testareanum].contents & stopcontents)

-				{

-					route->stopevent = RSE_ENTERCONTENTS;

-					route->endarea = testareanum;

-					route->endcontents = aasworld.areasettings[testareanum].contents;

-					VectorCopy(reach->end, route->endpos);

-					route->time += AAS_AreaTravelTime(areanum, origin, reach->start);

-					route->time += reach->traveltime;

-					return qtrue;

-				} //end if

-			} //end if

-			if (stopevent & RSE_ENTERAREA)

-			{

-				if (testareanum == stopareanum)

-				{

-					route->stopevent = RSE_ENTERAREA;

-					route->endarea = testareanum;

-					route->endcontents = aasworld.areasettings[testareanum].contents;

-					VectorCopy(reach->start, route->endpos);

-					return qtrue;

-				} //end if

-			} //end if

-		} //end for

-

-		route->time += AAS_AreaTravelTime(areanum, origin, reach->start);

-		route->time += reach->traveltime;

-		route->endarea = reach->areanum;

-		route->endcontents = aasworld.areasettings[reach->areanum].contents;

-		route->endtravelflags = AAS_TravelFlagForType_inline(reach->traveltype);

-		VectorCopy(reach->end, route->endpos);

-		//

-		curareanum = reach->areanum;

-		VectorCopy(reach->end, curorigin);

-		//

-		if (maxtime && route->time > maxtime)

-			break;

-	} //end while

-	if (curareanum != goalareanum)

-		return qfalse;

-	return qtrue;

-} //end of the function AAS_PredictRoute

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-int AAS_BridgeWalkable(int areanum)

-{

-	return qfalse;

-} //end of the function AAS_BridgeWalkable

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-void AAS_ReachabilityFromNum(int num, struct aas_reachability_s *reach)

-{

-	if (!aasworld.initialized)

-	{

-		Com_Memset(reach, 0, sizeof(aas_reachability_t));

-		return;

-	} //end if

-	if (num < 0 || num >= aasworld.reachabilitysize)

-	{

-		Com_Memset(reach, 0, sizeof(aas_reachability_t));

-		return;

-	} //end if

-	Com_Memcpy(reach, &aasworld.reachability[num], sizeof(aas_reachability_t));;

-} //end of the function AAS_ReachabilityFromNum

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-int AAS_NextAreaReachability(int areanum, int reachnum)

-{

-	aas_areasettings_t *settings;

-

-	if (!aasworld.initialized) return 0;

-

-	if (areanum <= 0 || areanum >= aasworld.numareas)

-	{

-		botimport.Print(PRT_ERROR, "AAS_NextAreaReachability: areanum %d out of range\n", areanum);

-		return 0;

-	} //end if

-

-	settings = &aasworld.areasettings[areanum];

-	if (!reachnum)

-	{

-		return settings->firstreachablearea;

-	} //end if

-	if (reachnum < settings->firstreachablearea)

-	{

-		botimport.Print(PRT_FATAL, "AAS_NextAreaReachability: reachnum < settings->firstreachableara");

-		return 0;

-	} //end if

-	reachnum++;

-	if (reachnum >= settings->firstreachablearea + settings->numreachableareas)

-	{

-		return 0;

-	} //end if

-	return reachnum;

-} //end of the function AAS_NextAreaReachability

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-int AAS_NextModelReachability(int num, int modelnum)

-{

-	int i;

-

-	if (num <= 0) num = 1;

-	else if (num >= aasworld.reachabilitysize) return 0;

-	else num++;

-	//

-	for (i = num; i < aasworld.reachabilitysize; i++)

-	{

-		if ((aasworld.reachability[i].traveltype & TRAVELTYPE_MASK) == TRAVEL_ELEVATOR)

-		{

-			if (aasworld.reachability[i].facenum == modelnum) return i;

-		} //end if

-		else if ((aasworld.reachability[i].traveltype & TRAVELTYPE_MASK) == TRAVEL_FUNCBOB)

-		{

-			if ((aasworld.reachability[i].facenum & 0x0000FFFF) == modelnum) return i;

-		} //end if

-	} //end for

-	return 0;

-} //end of the function AAS_NextModelReachability

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-int AAS_RandomGoalArea(int areanum, int travelflags, int *goalareanum, vec3_t goalorigin)

-{

-	int i, n, t;

-	vec3_t start, end;

-	aas_trace_t trace;

-

-	//if the area has no reachabilities

-	if (!AAS_AreaReachability(areanum)) return qfalse;

-	//

-	n = aasworld.numareas * random();

-	for (i = 0; i < aasworld.numareas; i++)

-	{

-		if (n <= 0) n = 1;

-		if (n >= aasworld.numareas) n = 1;

-		if (AAS_AreaReachability(n))

-		{

-			t = AAS_AreaTravelTimeToGoalArea(areanum, aasworld.areas[areanum].center, n, travelflags);

-			//if the goal is reachable

-			if (t > 0)

-			{

-				if (AAS_AreaSwim(n))

-				{

-					*goalareanum = n;

-					VectorCopy(aasworld.areas[n].center, goalorigin);

-					//botimport.Print(PRT_MESSAGE, "found random goal area %d\n", *goalareanum);

-					return qtrue;

-				} //end if

-				VectorCopy(aasworld.areas[n].center, start);

-				if (!AAS_PointAreaNum(start))

-					Log_Write("area %d center %f %f %f in solid?", n, start[0], start[1], start[2]);

-				VectorCopy(start, end);

-				end[2] -= 300;

-				trace = AAS_TraceClientBBox(start, end, PRESENCE_CROUCH, -1);

-				if (!trace.startsolid && trace.fraction < 1 && AAS_PointAreaNum(trace.endpos) == n)

-				{

-					if (AAS_AreaGroundFaceArea(n) > 300)

-					{

-						*goalareanum = n;

-						VectorCopy(trace.endpos, goalorigin);

-						//botimport.Print(PRT_MESSAGE, "found random goal area %d\n", *goalareanum);

-						return qtrue;

-					} //end if

-				} //end if

-			} //end if

-		} //end if

-		n++;

-	} //end for

-	return qfalse;

-} //end of the function AAS_RandomGoalArea

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-int AAS_AreaVisible(int srcarea, int destarea)

-{

-	return qfalse;

-} //end of the function AAS_AreaVisible

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-float DistancePointToLine(vec3_t v1, vec3_t v2, vec3_t point)

-{

-	vec3_t vec, p2;

-

-	AAS_ProjectPointOntoVector(point, v1, v2, p2);

-	VectorSubtract(point, p2, vec);

-	return VectorLength(vec);

-} //end of the function DistancePointToLine

-//===========================================================================

-//

-// Parameter:			-

-// Returns:				-

-// Changes Globals:		-

-//===========================================================================

-int AAS_NearestHideArea(int srcnum, vec3_t origin, int areanum, int enemynum, vec3_t enemyorigin, int enemyareanum, int travelflags)

-{

-	int i, j, nextareanum, badtravelflags, numreach, bestarea;

-	unsigned short int t, besttraveltime;

-	static unsigned short int *hidetraveltimes;

-	aas_routingupdate_t *updateliststart, *updatelistend, *curupdate, *nextupdate;

-	aas_reachability_t *reach;

-	float dist1, dist2;

-	vec3_t v1, v2, p;

-	qboolean startVisible;

-

-	//

-	if (!hidetraveltimes)

-	{

-		hidetraveltimes = (unsigned short int *) GetClearedMemory(aasworld.numareas * sizeof(unsigned short int));

-	} //end if

-	else

-	{

-		Com_Memset(hidetraveltimes, 0, aasworld.numareas * sizeof(unsigned short int));

-	} //end else

-	besttraveltime = 0;

-	bestarea = 0;

-	//assume visible

-	startVisible = qtrue;

-	//

-	badtravelflags = ~travelflags;

-	//

-	curupdate = &aasworld.areaupdate[areanum];

-	curupdate->areanum = areanum;

-	VectorCopy(origin, curupdate->start);

-	curupdate->areatraveltimes = aasworld.areatraveltimes[areanum][0];

-	curupdate->tmptraveltime = 0;

-	//put the area to start with in the current read list

-	curupdate->next = NULL;

-	curupdate->prev = NULL;

-	updateliststart = curupdate;

-	updatelistend = curupdate;

-	//while there are updates in the list

-	while (updateliststart)

-	{

-		curupdate = updateliststart;

-		//

-		if (curupdate->next) curupdate->next->prev = NULL;

-		else updatelistend = NULL;

-		updateliststart = curupdate->next;

-		//

-		curupdate->inlist = qfalse;

-		//check all reversed reachability links

-		numreach = aasworld.areasettings[curupdate->areanum].numreachableareas;

-		reach = &aasworld.reachability[aasworld.areasettings[curupdate->areanum].firstreachablearea];

-		//

-		for (i = 0; i < numreach; i++, reach++)

-		{

-			//if an undesired travel type is used

-			if (AAS_TravelFlagForType_inline(reach->traveltype) & badtravelflags) continue;

-			//

-			if (AAS_AreaContentsTravelFlags_inline(reach->areanum) & badtravelflags) continue;

-			//number of the area the reachability leads to

-			nextareanum = reach->areanum;

-			// if this moves us into the enemies area, skip it

-			if (nextareanum == enemyareanum) continue;

-			//time already travelled plus the traveltime through

-			//the current area plus the travel time from the reachability

-			t = curupdate->tmptraveltime +

-						AAS_AreaTravelTime(curupdate->areanum, curupdate->start, reach->start) +

-							reach->traveltime;

-

-			//avoid going near the enemy

-			AAS_ProjectPointOntoVector(enemyorigin, curupdate->start, reach->end, p);

-			for (j = 0; j < 3; j++)

-				if ((p[j] > curupdate->start[j] && p[j] > reach->end[j]) ||

-					(p[j] < curupdate->start[j] && p[j] < reach->end[j]))

-					break;

-			if (j < 3)

-			{

-				VectorSubtract(enemyorigin, reach->end, v2);

-			} //end if

-			else

-			{

-				VectorSubtract(enemyorigin, p, v2);

-			} //end else

-			dist2 = VectorLength(v2);

-			//never go through the enemy

-			if (dist2 < 40) continue;

-			//

-			VectorSubtract(enemyorigin, curupdate->start, v1);

-			dist1 = VectorLength(v1);

-			//

-			if (dist2 < dist1)

-			{

-				t += (dist1 - dist2) * 10;

-			}

-			// if we weren't visible when starting, make sure we don't move into their view

-			if (!startVisible && AAS_AreaVisible(enemyareanum, nextareanum)) {

-				continue;

-			}

-			//

-			if (besttraveltime && t >= besttraveltime) continue;

-			//

-			if (!hidetraveltimes[nextareanum] ||

-					hidetraveltimes[nextareanum] > t)

-			{

-				//if the nextarea is not visible from the enemy area

-				if (!AAS_AreaVisible(enemyareanum, nextareanum))

-				{

-					besttraveltime = t;

-					bestarea = nextareanum;

-				} //end if

-				hidetraveltimes[nextareanum] = t;

-				nextupdate = &aasworld.areaupdate[nextareanum];

-				nextupdate->areanum = nextareanum;

-				nextupdate->tmptraveltime = t;

-				//remember where we entered this area

-				VectorCopy(reach->end, nextupdate->start);

-				//if this update is not in the list yet

-				if (!nextupdate->inlist)

-				{

-					//add the new update to the end of the list

-					nextupdate->next = NULL;

-					nextupdate->prev = updatelistend;

-					if (updatelistend) updatelistend->next = nextupdate;

-					else updateliststart = nextupdate;

-					updatelistend = nextupdate;

-					nextupdate->inlist = qtrue;

-				} //end if

-			} //end if

-		} //end for

-	} //end while

-	return bestarea;

-} //end of the function AAS_NearestHideArea

+/*
+===========================================================================
+Copyright (C) 1999-2005 Id Software, Inc.
+
+This file is part of Quake III Arena source code.
+
+Quake III Arena source code is free software; you can redistribute it
+and/or modify it under the terms of the GNU General Public License as
+published by the Free Software Foundation; either version 2 of the License,
+or (at your option) any later version.
+
+Quake III Arena source code is distributed in the hope that it will be
+useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with Foobar; if not, write to the Free Software
+Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+===========================================================================
+*/
+
+/*****************************************************************************
+ * name:		be_aas_route.c
+ *
+ * desc:		AAS
+ *
+ * $Archive: /MissionPack/code/botlib/be_aas_route.c $
+ *
+ *****************************************************************************/
+
+#include "../game/q_shared.h"
+#include "l_utils.h"
+#include "l_memory.h"
+#include "l_log.h"
+#include "l_crc.h"
+#include "l_libvar.h"
+#include "l_script.h"
+#include "l_precomp.h"
+#include "l_struct.h"
+#include "aasfile.h"
+#include "../game/botlib.h"
+#include "../game/be_aas.h"
+#include "be_aas_funcs.h"
+#include "be_interface.h"
+#include "be_aas_def.h"
+
+#define ROUTING_DEBUG
+
+//travel time in hundreths of a second = distance * 100 / speed
+#define DISTANCEFACTOR_CROUCH		1.3f		//crouch speed = 100
+#define DISTANCEFACTOR_SWIM			1		//should be 0.66, swim speed = 150
+#define DISTANCEFACTOR_WALK			0.33f	//walk speed = 300
+
+//cache refresh time
+#define CACHE_REFRESHTIME		15.0f	//15 seconds refresh time
+
+//maximum number of routing updates each frame
+#define MAX_FRAMEROUTINGUPDATES		10
+
+
+/*
+
+  area routing cache:
+  stores the distances within one cluster to a specific goal area
+  this goal area is in this same cluster and could be a cluster portal
+  for every cluster there's a list with routing cache for every area
+  in that cluster (including the portals of that cluster)
+  area cache stores aasworld.clusters[?].numreachabilityareas travel times
+
+  portal routing cache:
+  stores the distances of all portals to a specific goal area
+  this goal area could be in any cluster and could also be a cluster portal
+  for every area (aasworld.numareas) the portal cache stores
+  aasworld.numportals travel times
+
+*/
+
+#ifdef ROUTING_DEBUG
+int numareacacheupdates;
+int numportalcacheupdates;
+#endif //ROUTING_DEBUG
+
+int routingcachesize;
+int max_routingcachesize;
+
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+#ifdef ROUTING_DEBUG
+void AAS_RoutingInfo(void)
+{
+	botimport.Print(PRT_MESSAGE, "%d area cache updates\n", numareacacheupdates);
+	botimport.Print(PRT_MESSAGE, "%d portal cache updates\n", numportalcacheupdates);
+	botimport.Print(PRT_MESSAGE, "%d bytes routing cache\n", routingcachesize);
+} //end of the function AAS_RoutingInfo
+#endif //ROUTING_DEBUG
+//===========================================================================
+// returns the number of the area in the cluster
+// assumes the given area is in the given cluster or a portal of the cluster
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+__inline int AAS_ClusterAreaNum(int cluster, int areanum)
+{
+	int side, areacluster;
+
+	areacluster = aasworld.areasettings[areanum].cluster;
+	if (areacluster > 0) return aasworld.areasettings[areanum].clusterareanum;
+	else
+	{
+/*#ifdef ROUTING_DEBUG
+		if (aasworld.portals[-areacluster].frontcluster != cluster &&
+				aasworld.portals[-areacluster].backcluster != cluster)
+		{
+			botimport.Print(PRT_ERROR, "portal %d: does not belong to cluster %d\n"
+											, -areacluster, cluster);
+		} //end if
+#endif //ROUTING_DEBUG*/
+		side = aasworld.portals[-areacluster].frontcluster != cluster;
+		return aasworld.portals[-areacluster].clusterareanum[side];
+	} //end else
+} //end of the function AAS_ClusterAreaNum
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_InitTravelFlagFromType(void)
+{
+	int i;
+
+	for (i = 0; i < MAX_TRAVELTYPES; i++)
+	{
+		aasworld.travelflagfortype[i] = TFL_INVALID;
+	} //end for
+	aasworld.travelflagfortype[TRAVEL_INVALID] = TFL_INVALID;
+	aasworld.travelflagfortype[TRAVEL_WALK] = TFL_WALK;
+	aasworld.travelflagfortype[TRAVEL_CROUCH] = TFL_CROUCH;
+	aasworld.travelflagfortype[TRAVEL_BARRIERJUMP] = TFL_BARRIERJUMP;
+	aasworld.travelflagfortype[TRAVEL_JUMP] = TFL_JUMP;
+	aasworld.travelflagfortype[TRAVEL_LADDER] = TFL_LADDER;
+	aasworld.travelflagfortype[TRAVEL_WALKOFFLEDGE] = TFL_WALKOFFLEDGE;
+	aasworld.travelflagfortype[TRAVEL_SWIM] = TFL_SWIM;
+	aasworld.travelflagfortype[TRAVEL_WATERJUMP] = TFL_WATERJUMP;
+	aasworld.travelflagfortype[TRAVEL_TELEPORT] = TFL_TELEPORT;
+	aasworld.travelflagfortype[TRAVEL_ELEVATOR] = TFL_ELEVATOR;
+	aasworld.travelflagfortype[TRAVEL_ROCKETJUMP] = TFL_ROCKETJUMP;
+	aasworld.travelflagfortype[TRAVEL_BFGJUMP] = TFL_BFGJUMP;
+	aasworld.travelflagfortype[TRAVEL_GRAPPLEHOOK] = TFL_GRAPPLEHOOK;
+	aasworld.travelflagfortype[TRAVEL_DOUBLEJUMP] = TFL_DOUBLEJUMP;
+	aasworld.travelflagfortype[TRAVEL_RAMPJUMP] = TFL_RAMPJUMP;
+	aasworld.travelflagfortype[TRAVEL_STRAFEJUMP] = TFL_STRAFEJUMP;
+	aasworld.travelflagfortype[TRAVEL_JUMPPAD] = TFL_JUMPPAD;
+	aasworld.travelflagfortype[TRAVEL_FUNCBOB] = TFL_FUNCBOB;
+} //end of the function AAS_InitTravelFlagFromType
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+__inline int AAS_TravelFlagForType_inline(int traveltype)
+{
+	int tfl;
+
+	tfl = 0;
+	if (tfl & TRAVELFLAG_NOTTEAM1)
+		tfl |= TFL_NOTTEAM1;
+	if (tfl & TRAVELFLAG_NOTTEAM2)
+		tfl |= TFL_NOTTEAM2;
+	traveltype &= TRAVELTYPE_MASK;
+	if (traveltype < 0 || traveltype >= MAX_TRAVELTYPES)
+		return TFL_INVALID;
+	tfl |= aasworld.travelflagfortype[traveltype];
+	return tfl;
+} //end of the function AAS_TravelFlagForType_inline
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+int AAS_TravelFlagForType(int traveltype)
+{
+	return AAS_TravelFlagForType_inline(traveltype);
+} //end of the function AAS_TravelFlagForType_inline
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_UnlinkCache(aas_routingcache_t *cache)
+{
+	if (cache->time_next) cache->time_next->time_prev = cache->time_prev;
+	else aasworld.newestcache = cache->time_prev;
+	if (cache->time_prev) cache->time_prev->time_next = cache->time_next;
+	else aasworld.oldestcache = cache->time_next;
+	cache->time_next = NULL;
+	cache->time_prev = NULL;
+} //end of the function AAS_UnlinkCache
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_LinkCache(aas_routingcache_t *cache)
+{
+	if (aasworld.newestcache)
+	{
+		aasworld.newestcache->time_next = cache;
+		cache->time_prev = aasworld.newestcache;
+	} //end if
+	else
+	{
+		aasworld.oldestcache = cache;
+		cache->time_prev = NULL;
+	} //end else
+	cache->time_next = NULL;
+	aasworld.newestcache = cache;
+} //end of the function AAS_LinkCache
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_FreeRoutingCache(aas_routingcache_t *cache)
+{
+	AAS_UnlinkCache(cache);
+	routingcachesize -= cache->size;
+	FreeMemory(cache);
+} //end of the function AAS_FreeRoutingCache
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_RemoveRoutingCacheInCluster( int clusternum )
+{
+	int i;
+	aas_routingcache_t *cache, *nextcache;
+	aas_cluster_t *cluster;
+
+	if (!aasworld.clusterareacache)
+		return;
+	cluster = &aasworld.clusters[clusternum];
+	for (i = 0; i < cluster->numareas; i++)
+	{
+		for (cache = aasworld.clusterareacache[clusternum][i]; cache; cache = nextcache)
+		{
+			nextcache = cache->next;
+			AAS_FreeRoutingCache(cache);
+		} //end for
+		aasworld.clusterareacache[clusternum][i] = NULL;
+	} //end for
+} //end of the function AAS_RemoveRoutingCacheInCluster
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_RemoveRoutingCacheUsingArea( int areanum )
+{
+	int i, clusternum;
+	aas_routingcache_t *cache, *nextcache;
+
+	clusternum = aasworld.areasettings[areanum].cluster;
+	if (clusternum > 0)
+	{
+		//remove all the cache in the cluster the area is in
+		AAS_RemoveRoutingCacheInCluster( clusternum );
+	} //end if
+	else
+	{
+		// if this is a portal remove all cache in both the front and back cluster
+		AAS_RemoveRoutingCacheInCluster( aasworld.portals[-clusternum].frontcluster );
+		AAS_RemoveRoutingCacheInCluster( aasworld.portals[-clusternum].backcluster );
+	} //end else
+	// remove all portal cache
+	for (i = 0; i < aasworld.numareas; i++)
+	{
+		//refresh portal cache
+		for (cache = aasworld.portalcache[i]; cache; cache = nextcache)
+		{
+			nextcache = cache->next;
+			AAS_FreeRoutingCache(cache);
+		} //end for
+		aasworld.portalcache[i] = NULL;
+	} //end for
+} //end of the function AAS_RemoveRoutingCacheUsingArea
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+int AAS_EnableRoutingArea(int areanum, int enable)
+{
+	int flags;
+
+	if (areanum <= 0 || areanum >= aasworld.numareas)
+	{
+		if (bot_developer)
+		{
+			botimport.Print(PRT_ERROR, "AAS_EnableRoutingArea: areanum %d out of range\n", areanum);
+		} //end if
+		return 0;
+	} //end if
+	flags = aasworld.areasettings[areanum].areaflags & AREA_DISABLED;
+	if (enable < 0)
+		return !flags;
+
+	if (enable)
+		aasworld.areasettings[areanum].areaflags &= ~AREA_DISABLED;
+	else
+		aasworld.areasettings[areanum].areaflags |= AREA_DISABLED;
+	// if the status of the area changed
+	if ( (flags & AREA_DISABLED) != (aasworld.areasettings[areanum].areaflags & AREA_DISABLED) )
+	{
+		//remove all routing cache involving this area
+		AAS_RemoveRoutingCacheUsingArea( areanum );
+	} //end if
+	return !flags;
+} //end of the function AAS_EnableRoutingArea
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+__inline float AAS_RoutingTime(void)
+{
+	return AAS_Time();
+} //end of the function AAS_RoutingTime
+//===========================================================================
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+int AAS_GetAreaContentsTravelFlags(int areanum)
+{
+	int contents, tfl;
+
+	contents = aasworld.areasettings[areanum].contents;
+	tfl = 0;
+	if (contents & AREACONTENTS_WATER)
+		tfl |= TFL_WATER;
+	else if (contents & AREACONTENTS_SLIME)
+		tfl |= TFL_SLIME;
+	else if (contents & AREACONTENTS_LAVA)
+		tfl |= TFL_LAVA;
+	else
+		tfl |= TFL_AIR;
+	if (contents & AREACONTENTS_DONOTENTER)
+		tfl |= TFL_DONOTENTER;
+	if (contents & AREACONTENTS_NOTTEAM1)
+		tfl |= TFL_NOTTEAM1;
+	if (contents & AREACONTENTS_NOTTEAM2)
+		tfl |= TFL_NOTTEAM2;
+	if (aasworld.areasettings[areanum].areaflags & AREA_BRIDGE)
+		tfl |= TFL_BRIDGE;
+	return tfl;
+} //end of the function AAS_GetAreaContentsTravelFlags
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+__inline int AAS_AreaContentsTravelFlags_inline(int areanum)
+{
+	return aasworld.areacontentstravelflags[areanum];
+} //end of the function AAS_AreaContentsTravelFlags
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+int AAS_AreaContentsTravelFlags(int areanum)
+{
+	return aasworld.areacontentstravelflags[areanum];
+} //end of the function AAS_AreaContentsTravelFlags
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_InitAreaContentsTravelFlags(void)
+{
+	int i;
+
+	if (aasworld.areacontentstravelflags) FreeMemory(aasworld.areacontentstravelflags);
+	aasworld.areacontentstravelflags = (int *) GetClearedMemory(aasworld.numareas * sizeof(int));
+	//
+	for (i = 0; i < aasworld.numareas; i++) {
+		aasworld.areacontentstravelflags[i] = AAS_GetAreaContentsTravelFlags(i);
+	}
+} //end of the function AAS_InitAreaContentsTravelFlags
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_CreateReversedReachability(void)
+{
+	int i, n;
+	aas_reversedlink_t *revlink;
+	aas_reachability_t *reach;
+	aas_areasettings_t *settings;
+	char *ptr;
+#ifdef DEBUG
+	int starttime;
+
+	starttime = Sys_MilliSeconds();
+#endif
+	//free reversed links that have already been created
+	if (aasworld.reversedreachability) FreeMemory(aasworld.reversedreachability);
+	//allocate memory for the reversed reachability links
+	ptr = (char *) GetClearedMemory(aasworld.numareas * sizeof(aas_reversedreachability_t) +
+							aasworld.reachabilitysize * sizeof(aas_reversedlink_t));
+	//
+	aasworld.reversedreachability = (aas_reversedreachability_t *) ptr;
+	//pointer to the memory for the reversed links
+	ptr += aasworld.numareas * sizeof(aas_reversedreachability_t);
+	//check all reachabilities of all areas
+	for (i = 1; i < aasworld.numareas; i++)
+	{
+		//settings of the area
+		settings = &aasworld.areasettings[i];
+		//
+		if (settings->numreachableareas >= 128)
+			botimport.Print(PRT_WARNING, "area %d has more than 128 reachabilities\n", i);
+		//create reversed links for the reachabilities
+		for (n = 0; n < settings->numreachableareas && n < 128; n++)
+		{
+			//reachability link
+			reach = &aasworld.reachability[settings->firstreachablearea + n];
+			//
+			revlink = (aas_reversedlink_t *) ptr;
+			ptr += sizeof(aas_reversedlink_t);
+			//
+			revlink->areanum = i;
+			revlink->linknum = settings->firstreachablearea + n;
+			revlink->next = aasworld.reversedreachability[reach->areanum].first;
+			aasworld.reversedreachability[reach->areanum].first = revlink;
+			aasworld.reversedreachability[reach->areanum].numlinks++;
+		} //end for
+	} //end for
+#ifdef DEBUG
+	botimport.Print(PRT_MESSAGE, "reversed reachability %d msec\n", Sys_MilliSeconds() - starttime);
+#endif
+} //end of the function AAS_CreateReversedReachability
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+unsigned short int AAS_AreaTravelTime(int areanum, vec3_t start, vec3_t end)
+{
+	int intdist;
+	float dist;
+	vec3_t dir;
+
+	VectorSubtract(start, end, dir);
+	dist = VectorLength(dir);
+	//if crouch only area
+	if (AAS_AreaCrouch(areanum)) dist *= DISTANCEFACTOR_CROUCH;
+	//if swim area
+	else if (AAS_AreaSwim(areanum)) dist *= DISTANCEFACTOR_SWIM;
+	//normal walk area
+	else dist *= DISTANCEFACTOR_WALK;
+	//
+	intdist = (int) dist;
+	//make sure the distance isn't zero
+	if (intdist <= 0) intdist = 1;
+	return intdist;
+} //end of the function AAS_AreaTravelTime
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_CalculateAreaTravelTimes(void)
+{
+	int i, l, n, size;
+	char *ptr;
+	vec3_t end;
+	aas_reversedreachability_t *revreach;
+	aas_reversedlink_t *revlink;
+	aas_reachability_t *reach;
+	aas_areasettings_t *settings;
+	int starttime;
+
+	starttime = Sys_MilliSeconds();
+	//if there are still area travel times, free the memory
+	if (aasworld.areatraveltimes) FreeMemory(aasworld.areatraveltimes);
+	//get the total size of all the area travel times
+	size = aasworld.numareas * sizeof(unsigned short **);
+	for (i = 0; i < aasworld.numareas; i++)
+	{
+		revreach = &aasworld.reversedreachability[i];
+		//settings of the area
+		settings = &aasworld.areasettings[i];
+		//
+		size += settings->numreachableareas * sizeof(unsigned short *);
+		//
+		size += settings->numreachableareas * revreach->numlinks * sizeof(unsigned short);
+	} //end for
+	//allocate memory for the area travel times
+	ptr = (char *) GetClearedMemory(size);
+	aasworld.areatraveltimes = (unsigned short ***) ptr;
+	ptr += aasworld.numareas * sizeof(unsigned short **);
+	//calcluate the travel times for all the areas
+	for (i = 0; i < aasworld.numareas; i++)
+	{
+		//reversed reachabilities of this area
+		revreach = &aasworld.reversedreachability[i];
+		//settings of the area
+		settings = &aasworld.areasettings[i];
+		//
+		aasworld.areatraveltimes[i] = (unsigned short **) ptr;
+		ptr += settings->numreachableareas * sizeof(unsigned short *);
+		//
+		for (l = 0; l < settings->numreachableareas; l++)
+		{
+			aasworld.areatraveltimes[i][l] = (unsigned short *) ptr;
+			ptr += revreach->numlinks * sizeof(unsigned short);
+			//reachability link
+			reach = &aasworld.reachability[settings->firstreachablearea + l];
+			//
+			for (n = 0, revlink = revreach->first; revlink; revlink = revlink->next, n++)
+			{
+				VectorCopy(aasworld.reachability[revlink->linknum].end, end);
+				//
+				aasworld.areatraveltimes[i][l][n] = AAS_AreaTravelTime(i, end, reach->start);
+			} //end for
+		} //end for
+	} //end for
+#ifdef DEBUG
+	botimport.Print(PRT_MESSAGE, "area travel times %d msec\n", Sys_MilliSeconds() - starttime);
+#endif
+} //end of the function AAS_CalculateAreaTravelTimes
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+int AAS_PortalMaxTravelTime(int portalnum)
+{
+	int l, n, t, maxt;
+	aas_portal_t *portal;
+	aas_reversedreachability_t *revreach;
+	aas_reversedlink_t *revlink;
+	aas_areasettings_t *settings;
+
+	portal = &aasworld.portals[portalnum];
+	//reversed reachabilities of this portal area
+	revreach = &aasworld.reversedreachability[portal->areanum];
+	//settings of the portal area
+	settings = &aasworld.areasettings[portal->areanum];
+	//
+	maxt = 0;
+	for (l = 0; l < settings->numreachableareas; l++)
+	{
+		for (n = 0, revlink = revreach->first; revlink; revlink = revlink->next, n++)
+		{
+			t = aasworld.areatraveltimes[portal->areanum][l][n];
+			if (t > maxt)
+			{
+				maxt = t;
+			} //end if
+		} //end for
+	} //end for
+	return maxt;
+} //end of the function AAS_PortalMaxTravelTime
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_InitPortalMaxTravelTimes(void)
+{
+	int i;
+
+	if (aasworld.portalmaxtraveltimes) FreeMemory(aasworld.portalmaxtraveltimes);
+
+	aasworld.portalmaxtraveltimes = (int *) GetClearedMemory(aasworld.numportals * sizeof(int));
+
+	for (i = 0; i < aasworld.numportals; i++)
+	{
+		aasworld.portalmaxtraveltimes[i] = AAS_PortalMaxTravelTime(i);
+		//botimport.Print(PRT_MESSAGE, "portal %d max tt = %d\n", i, aasworld.portalmaxtraveltimes[i]);
+	} //end for
+} //end of the function AAS_InitPortalMaxTravelTimes
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+/*
+int AAS_FreeOldestCache(void)
+{
+	int i, j, bestcluster, bestarea, freed;
+	float besttime;
+	aas_routingcache_t *cache, *bestcache;
+
+	freed = qfalse;
+	besttime = 999999999;
+	bestcache = NULL;
+	bestcluster = 0;
+	bestarea = 0;
+	//refresh cluster cache
+	for (i = 0; i < aasworld.numclusters; i++)
+	{
+		for (j = 0; j < aasworld.clusters[i].numareas; j++)
+		{
+			for (cache = aasworld.clusterareacache[i][j]; cache; cache = cache->next)
+			{
+				//never remove cache leading towards a portal
+				if (aasworld.areasettings[cache->areanum].cluster < 0) continue;
+				//if this cache is older than the cache we found so far
+				if (cache->time < besttime)
+				{
+					bestcache = cache;
+					bestcluster = i;
+					bestarea = j;
+					besttime = cache->time;
+				} //end if
+			} //end for
+		} //end for
+	} //end for
+	if (bestcache)
+	{
+		cache = bestcache;
+		if (cache->prev) cache->prev->next = cache->next;
+		else aasworld.clusterareacache[bestcluster][bestarea] = cache->next;
+		if (cache->next) cache->next->prev = cache->prev;
+		AAS_FreeRoutingCache(cache);
+		freed = qtrue;
+	} //end if
+	besttime = 999999999;
+	bestcache = NULL;
+	bestarea = 0;
+	for (i = 0; i < aasworld.numareas; i++)
+	{
+		//refresh portal cache
+		for (cache = aasworld.portalcache[i]; cache; cache = cache->next)
+		{
+			if (cache->time < besttime)
+			{
+				bestcache = cache;
+				bestarea = i;
+				besttime = cache->time;
+			} //end if
+		} //end for
+	} //end for
+	if (bestcache)
+	{
+		cache = bestcache;
+		if (cache->prev) cache->prev->next = cache->next;
+		else aasworld.portalcache[bestarea] = cache->next;
+		if (cache->next) cache->next->prev = cache->prev;
+		AAS_FreeRoutingCache(cache);
+		freed = qtrue;
+	} //end if
+	return freed;
+} //end of the function AAS_FreeOldestCache
+*/
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+int AAS_FreeOldestCache(void)
+{
+	int clusterareanum;
+	aas_routingcache_t *cache;
+
+	for (cache = aasworld.oldestcache; cache; cache = cache->time_next) {
+		// never free area cache leading towards a portal
+		if (cache->type == CACHETYPE_AREA && aasworld.areasettings[cache->areanum].cluster < 0) {
+			continue;
+		}
+		break;
+	}
+	if (cache) {
+		// unlink the cache
+		if (cache->type == CACHETYPE_AREA) {
+			//number of the area in the cluster
+			clusterareanum = AAS_ClusterAreaNum(cache->cluster, cache->areanum);
+			// unlink from cluster area cache
+			if (cache->prev) cache->prev->next = cache->next;
+			else aasworld.clusterareacache[cache->cluster][clusterareanum] = cache->next;
+			if (cache->next) cache->next->prev = cache->prev;
+		}
+		else {
+			// unlink from portal cache
+			if (cache->prev) cache->prev->next = cache->next;
+			else aasworld.portalcache[cache->areanum] = cache->next;
+			if (cache->next) cache->next->prev = cache->prev;
+		}
+		AAS_FreeRoutingCache(cache);
+		return qtrue;
+	}
+	return qfalse;
+} //end of the function AAS_FreeOldestCache
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+aas_routingcache_t *AAS_AllocRoutingCache(int numtraveltimes)
+{
+	aas_routingcache_t *cache;
+	int size;
+
+	//
+	size = sizeof(aas_routingcache_t)
+						+ numtraveltimes * sizeof(unsigned short int)
+						+ numtraveltimes * sizeof(unsigned char);
+	//
+	routingcachesize += size;
+	//
+	cache = (aas_routingcache_t *) GetClearedMemory(size);
+	cache->reachabilities = (unsigned char *) cache + sizeof(aas_routingcache_t)
+								+ numtraveltimes * sizeof(unsigned short int);
+	cache->size = size;
+	return cache;
+} //end of the function AAS_AllocRoutingCache
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_FreeAllClusterAreaCache(void)
+{
+	int i, j;
+	aas_routingcache_t *cache, *nextcache;
+	aas_cluster_t *cluster;
+
+	//free all cluster cache if existing
+	if (!aasworld.clusterareacache) return;
+	//free caches
+	for (i = 0; i < aasworld.numclusters; i++)
+	{
+		cluster = &aasworld.clusters[i];
+		for (j = 0; j < cluster->numareas; j++)
+		{
+			for (cache = aasworld.clusterareacache[i][j]; cache; cache = nextcache)
+			{
+				nextcache = cache->next;
+				AAS_FreeRoutingCache(cache);
+			} //end for
+			aasworld.clusterareacache[i][j] = NULL;
+		} //end for
+	} //end for
+	//free the cluster cache array
+	FreeMemory(aasworld.clusterareacache);
+	aasworld.clusterareacache = NULL;
+} //end of the function AAS_FreeAllClusterAreaCache
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_InitClusterAreaCache(void)
+{
+	int i, size;
+	char *ptr;
+
+	//
+	for (size = 0, i = 0; i < aasworld.numclusters; i++)
+	{
+		size += aasworld.clusters[i].numareas;
+	} //end for
+	//two dimensional array with pointers for every cluster to routing cache
+	//for every area in that cluster
+	ptr = (char *) GetClearedMemory(
+				aasworld.numclusters * sizeof(aas_routingcache_t **) +
+				size * sizeof(aas_routingcache_t *));
+	aasworld.clusterareacache = (aas_routingcache_t ***) ptr;
+	ptr += aasworld.numclusters * sizeof(aas_routingcache_t **);
+	for (i = 0; i < aasworld.numclusters; i++)
+	{
+		aasworld.clusterareacache[i] = (aas_routingcache_t **) ptr;
+		ptr += aasworld.clusters[i].numareas * sizeof(aas_routingcache_t *);
+	} //end for
+} //end of the function AAS_InitClusterAreaCache
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_FreeAllPortalCache(void)
+{
+	int i;
+	aas_routingcache_t *cache, *nextcache;
+
+	//free all portal cache if existing
+	if (!aasworld.portalcache) return;
+	//free portal caches
+	for (i = 0; i < aasworld.numareas; i++)
+	{
+		for (cache = aasworld.portalcache[i]; cache; cache = nextcache)
+		{
+			nextcache = cache->next;
+			AAS_FreeRoutingCache(cache);
+		} //end for
+		aasworld.portalcache[i] = NULL;
+	} //end for
+	FreeMemory(aasworld.portalcache);
+	aasworld.portalcache = NULL;
+} //end of the function AAS_FreeAllPortalCache
+//===========================================================================
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+void AAS_InitPortalCache(void)
+{
+	//
+	aasworld.portalcache = (aas_routingcache_t **) GetClearedMemory(
+								aasworld.numareas * sizeof(aas_routingcache_t *));
+} //end of the function AAS_InitPortalCache
+//===========================================================================
+//
+// Parameter:				-
+// Returns:					-
+// Changes Globals:		-
+//===========================================================================
+void AAS_InitRoutingUpdate(void)
+{
+	int i, maxreachabilityareas;
+
+	//free routing update fields if already existing
+	if (aasworld.areaupdate) FreeMemory(aasworld.areaupdate);
+	//
+	maxreachabilityareas = 0;
+	for (i = 0; i < aasworld.numclusters; i++)
+	{
+		if (aasworld.clusters[i].numreachabilityareas > maxreachabilityareas)
+		{
+			maxreachabilityareas = aasworld.clusters[i].numreachabilityareas;
+		} //end if
+	} //end for
+	//allocate memory for the routing update fields
+	aasworld.areaupdate = (aas_routingupdate_t *) GetClearedMemory(
+									maxreachabilityareas * sizeof(aas_routingupdate_t));
+	//
+	if (aasworld.portalupdate) FreeMemory(aasworld.portalupdate);
+	//allocate memory for the portal update fields
+	aasworld.portalupdate = (aas_routingupdate_t *) GetClearedMemory(
+									(aasworld.numportals+1) * sizeof(aas_routingupdate_t));
+} //end of the function AAS_InitRoutingUpdate
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_CreateAllRoutingCache(void)
+{
+	int i, j, t;
+
+	aasworld.initialized = qtrue;
+	botimport.Print(PRT_MESSAGE, "AAS_CreateAllRoutingCache\n");
+	for (i = 1; i < aasworld.numareas; i++)
+	{
+		if (!AAS_AreaReachability(i)) continue;
+		for (j = 1; j < aasworld.numareas; j++)
+		{
+			if (i == j) continue;
+			if (!AAS_AreaReachability(j)) continue;
+			t = AAS_AreaTravelTimeToGoalArea(i, aasworld.areas[i].center, j, TFL_DEFAULT);
+			//Log_Write("traveltime from %d to %d is %d", i, j, t);
+		} //end for
+	} //end for
+	aasworld.initialized = qfalse;
+} //end of the function AAS_CreateAllRoutingCache
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+
+//the route cache header
+//this header is followed by numportalcache + numareacache aas_routingcache_t
+//structures that store routing cache
+typedef struct routecacheheader_s
+{
+	int ident;
+	int version;
+	int numareas;
+	int numclusters;
+	int areacrc;
+	int clustercrc;
+	int numportalcache;
+	int numareacache;
+} routecacheheader_t;
+
+#define RCID						(('C'<<24)+('R'<<16)+('E'<<8)+'M')
+#define RCVERSION					2
+
+//void AAS_DecompressVis(byte *in, int numareas, byte *decompressed);
+//int AAS_CompressVis(byte *vis, int numareas, byte *dest);
+
+void AAS_WriteRouteCache(void)
+{
+	int i, j, numportalcache, numareacache, totalsize;
+	aas_routingcache_t *cache;
+	aas_cluster_t *cluster;
+	fileHandle_t fp;
+	char filename[MAX_QPATH];
+	routecacheheader_t routecacheheader;
+
+	numportalcache = 0;
+	for (i = 0; i < aasworld.numareas; i++)
+	{
+		for (cache = aasworld.portalcache[i]; cache; cache = cache->next)
+		{
+			numportalcache++;
+		} //end for
+	} //end for
+	numareacache = 0;
+	for (i = 0; i < aasworld.numclusters; i++)
+	{
+		cluster = &aasworld.clusters[i];
+		for (j = 0; j < cluster->numareas; j++)
+		{
+			for (cache = aasworld.clusterareacache[i][j]; cache; cache = cache->next)
+			{
+				numareacache++;
+			} //end for
+		} //end for
+	} //end for
+	// open the file for writing
+	Com_sprintf(filename, MAX_QPATH, "maps/%s.rcd", aasworld.mapname);
+	botimport.FS_FOpenFile( filename, &fp, FS_WRITE );
+	if (!fp)
+	{
+		AAS_Error("Unable to open file: %s\n", filename);
+		return;
+	} //end if
+	//create the header
+	routecacheheader.ident = RCID;
+	routecacheheader.version = RCVERSION;
+	routecacheheader.numareas = aasworld.numareas;
+	routecacheheader.numclusters = aasworld.numclusters;
+	routecacheheader.areacrc = CRC_ProcessString( (unsigned char *)aasworld.areas, sizeof(aas_area_t) * aasworld.numareas );
+	routecacheheader.clustercrc = CRC_ProcessString( (unsigned char *)aasworld.clusters, sizeof(aas_cluster_t) * aasworld.numclusters );
+	routecacheheader.numportalcache = numportalcache;
+	routecacheheader.numareacache = numareacache;
+	//write the header
+	botimport.FS_Write(&routecacheheader, sizeof(routecacheheader_t), fp);
+	//
+	totalsize = 0;
+	//write all the cache
+	for (i = 0; i < aasworld.numareas; i++)
+	{
+		for (cache = aasworld.portalcache[i]; cache; cache = cache->next)
+		{
+			botimport.FS_Write(cache, cache->size, fp);
+			totalsize += cache->size;
+		} //end for
+	} //end for
+	for (i = 0; i < aasworld.numclusters; i++)
+	{
+		cluster = &aasworld.clusters[i];
+		for (j = 0; j < cluster->numareas; j++)
+		{
+			for (cache = aasworld.clusterareacache[i][j]; cache; cache = cache->next)
+			{
+				botimport.FS_Write(cache, cache->size, fp);
+				totalsize += cache->size;
+			} //end for
+		} //end for
+	} //end for
+	// write the visareas
+	/*
+	for (i = 0; i < aasworld.numareas; i++)
+	{
+		if (!aasworld.areavisibility[i]) {
+			size = 0;
+			botimport.FS_Write(&size, sizeof(int), fp);
+			continue;
+		}
+		AAS_DecompressVis( aasworld.areavisibility[i], aasworld.numareas, aasworld.decompressedvis );
+		size = AAS_CompressVis( aasworld.decompressedvis, aasworld.numareas, aasworld.decompressedvis );
+		botimport.FS_Write(&size, sizeof(int), fp);
+		botimport.FS_Write(aasworld.decompressedvis, size, fp);
+	}
+	*/
+	//
+	botimport.FS_FCloseFile(fp);
+	botimport.Print(PRT_MESSAGE, "\nroute cache written to %s\n", filename);
+	botimport.Print(PRT_MESSAGE, "written %d bytes of routing cache\n", totalsize);
+} //end of the function AAS_WriteRouteCache
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+aas_routingcache_t *AAS_ReadCache(fileHandle_t fp)
+{
+	int size;
+	aas_routingcache_t *cache;
+
+	botimport.FS_Read(&size, sizeof(size), fp);
+	cache = (aas_routingcache_t *) GetMemory(size);
+	cache->size = size;
+	botimport.FS_Read((unsigned char *)cache + sizeof(size), size - sizeof(size), fp);
+	cache->reachabilities = (unsigned char *) cache + sizeof(aas_routingcache_t) - sizeof(unsigned short) +
+		(size - sizeof(aas_routingcache_t) + sizeof(unsigned short)) / 3 * 2;
+	return cache;
+} //end of the function AAS_ReadCache
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+int AAS_ReadRouteCache(void)
+{
+	int i, clusterareanum;//, size;
+	fileHandle_t fp;
+	char filename[MAX_QPATH];
+	routecacheheader_t routecacheheader;
+	aas_routingcache_t *cache;
+
+	Com_sprintf(filename, MAX_QPATH, "maps/%s.rcd", aasworld.mapname);
+	botimport.FS_FOpenFile( filename, &fp, FS_READ );
+	if (!fp)
+	{
+		return qfalse;
+	} //end if
+	botimport.FS_Read(&routecacheheader, sizeof(routecacheheader_t), fp );
+	if (routecacheheader.ident != RCID)
+	{
+		AAS_Error("%s is not a route cache dump\n");
+		return qfalse;
+	} //end if
+	if (routecacheheader.version != RCVERSION)
+	{
+		AAS_Error("route cache dump has wrong version %d, should be %d", routecacheheader.version, RCVERSION);
+		return qfalse;
+	} //end if
+	if (routecacheheader.numareas != aasworld.numareas)
+	{
+		//AAS_Error("route cache dump has wrong number of areas\n");
+		return qfalse;
+	} //end if
+	if (routecacheheader.numclusters != aasworld.numclusters)
+	{
+		//AAS_Error("route cache dump has wrong number of clusters\n");
+		return qfalse;
+	} //end if
+	if (routecacheheader.areacrc !=
+		CRC_ProcessString( (unsigned char *)aasworld.areas, sizeof(aas_area_t) * aasworld.numareas ))
+	{
+		//AAS_Error("route cache dump area CRC incorrect\n");
+		return qfalse;
+	} //end if
+	if (routecacheheader.clustercrc !=
+		CRC_ProcessString( (unsigned char *)aasworld.clusters, sizeof(aas_cluster_t) * aasworld.numclusters ))
+	{
+		//AAS_Error("route cache dump cluster CRC incorrect\n");
+		return qfalse;
+	} //end if
+	//read all the portal cache
+	for (i = 0; i < routecacheheader.numportalcache; i++)
+	{
+		cache = AAS_ReadCache(fp);
+		cache->next = aasworld.portalcache[cache->areanum];
+		cache->prev = NULL;
+		if (aasworld.portalcache[cache->areanum])
+			aasworld.portalcache[cache->areanum]->prev = cache;
+		aasworld.portalcache[cache->areanum] = cache;
+	} //end for
+	//read all the cluster area cache
+	for (i = 0; i < routecacheheader.numareacache; i++)
+	{
+		cache = AAS_ReadCache(fp);
+		clusterareanum = AAS_ClusterAreaNum(cache->cluster, cache->areanum);
+		cache->next = aasworld.clusterareacache[cache->cluster][clusterareanum];
+		cache->prev = NULL;
+		if (aasworld.clusterareacache[cache->cluster][clusterareanum])
+			aasworld.clusterareacache[cache->cluster][clusterareanum]->prev = cache;
+		aasworld.clusterareacache[cache->cluster][clusterareanum] = cache;
+	} //end for
+	// read the visareas
+	/*
+	aasworld.areavisibility = (byte **) GetClearedMemory(aasworld.numareas * sizeof(byte *));
+	aasworld.decompressedvis = (byte *) GetClearedMemory(aasworld.numareas * sizeof(byte));
+	for (i = 0; i < aasworld.numareas; i++)
+	{
+		botimport.FS_Read(&size, sizeof(size), fp );
+		if (size) {
+			aasworld.areavisibility[i] = (byte *) GetMemory(size);
+			botimport.FS_Read(aasworld.areavisibility[i], size, fp );
+		}
+	}
+	*/
+	//
+	botimport.FS_FCloseFile(fp);
+	return qtrue;
+} //end of the function AAS_ReadRouteCache
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+#define MAX_REACHABILITYPASSAREAS		32
+
+void AAS_InitReachabilityAreas(void)
+{
+	int i, j, numareas, areas[MAX_REACHABILITYPASSAREAS];
+	int numreachareas;
+	aas_reachability_t *reach;
+	vec3_t start, end;
+
+	if (aasworld.reachabilityareas)
+		FreeMemory(aasworld.reachabilityareas);
+	if (aasworld.reachabilityareaindex)
+		FreeMemory(aasworld.reachabilityareaindex);
+
+	aasworld.reachabilityareas = (aas_reachabilityareas_t *)
+				GetClearedMemory(aasworld.reachabilitysize * sizeof(aas_reachabilityareas_t));
+	aasworld.reachabilityareaindex = (int *)
+				GetClearedMemory(aasworld.reachabilitysize * MAX_REACHABILITYPASSAREAS * sizeof(int));
+	numreachareas = 0;
+	for (i = 0; i < aasworld.reachabilitysize; i++)
+	{
+		reach = &aasworld.reachability[i];
+		numareas = 0;
+		switch(reach->traveltype & TRAVELTYPE_MASK)
+		{
+			//trace areas from start to end
+			case TRAVEL_BARRIERJUMP:
+			case TRAVEL_WATERJUMP:
+				VectorCopy(reach->start, end);
+				end[2] = reach->end[2];
+				numareas = AAS_TraceAreas(reach->start, end, areas, NULL, MAX_REACHABILITYPASSAREAS);
+				break;
+			case TRAVEL_WALKOFFLEDGE:
+				VectorCopy(reach->end, start);
+				start[2] = reach->start[2];
+				numareas = AAS_TraceAreas(start, reach->end, areas, NULL, MAX_REACHABILITYPASSAREAS);
+				break;
+			case TRAVEL_GRAPPLEHOOK:
+				numareas = AAS_TraceAreas(reach->start, reach->end, areas, NULL, MAX_REACHABILITYPASSAREAS);
+				break;
+
+			//trace arch
+			case TRAVEL_JUMP: break;
+			case TRAVEL_ROCKETJUMP: break;
+			case TRAVEL_BFGJUMP: break;
+			case TRAVEL_JUMPPAD: break;
+
+			//trace from reach->start to entity center, along entity movement
+			//and from entity center to reach->end
+			case TRAVEL_ELEVATOR: break;
+			case TRAVEL_FUNCBOB: break;
+
+			//no areas in between
+			case TRAVEL_WALK: break;
+			case TRAVEL_CROUCH: break;
+			case TRAVEL_LADDER: break;
+			case TRAVEL_SWIM: break;
+			case TRAVEL_TELEPORT: break;
+			default: break;
+		} //end switch
+		aasworld.reachabilityareas[i].firstarea = numreachareas;
+		aasworld.reachabilityareas[i].numareas = numareas;
+		for (j = 0; j < numareas; j++)
+		{
+			aasworld.reachabilityareaindex[numreachareas++] = areas[j];
+		} //end for
+	} //end for
+} //end of the function AAS_InitReachabilityAreas
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_InitRouting(void)
+{
+	AAS_InitTravelFlagFromType();
+	//
+	AAS_InitAreaContentsTravelFlags();
+	//initialize the routing update fields
+	AAS_InitRoutingUpdate();
+	//create reversed reachability links used by the routing update algorithm
+	AAS_CreateReversedReachability();
+	//initialize the cluster cache
+	AAS_InitClusterAreaCache();
+	//initialize portal cache
+	AAS_InitPortalCache();
+	//initialize the area travel times
+	AAS_CalculateAreaTravelTimes();
+	//calculate the maximum travel times through portals
+	AAS_InitPortalMaxTravelTimes();
+	//get the areas reachabilities go through
+	AAS_InitReachabilityAreas();
+	//
+#ifdef ROUTING_DEBUG
+	numareacacheupdates = 0;
+	numportalcacheupdates = 0;
+#endif //ROUTING_DEBUG
+	//
+	routingcachesize = 0;
+	max_routingcachesize = 1024 * (int) LibVarValue("max_routingcache", "4096");
+	// read any routing cache if available
+	AAS_ReadRouteCache();
+} //end of the function AAS_InitRouting
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_FreeRoutingCaches(void)
+{
+	// free all the existing cluster area cache
+	AAS_FreeAllClusterAreaCache();
+	// free all the existing portal cache
+	AAS_FreeAllPortalCache();
+	// free cached travel times within areas
+	if (aasworld.areatraveltimes) FreeMemory(aasworld.areatraveltimes);
+	aasworld.areatraveltimes = NULL;
+	// free cached maximum travel time through cluster portals
+	if (aasworld.portalmaxtraveltimes) FreeMemory(aasworld.portalmaxtraveltimes);
+	aasworld.portalmaxtraveltimes = NULL;
+	// free reversed reachability links
+	if (aasworld.reversedreachability) FreeMemory(aasworld.reversedreachability);
+	aasworld.reversedreachability = NULL;
+	// free routing algorithm memory
+	if (aasworld.areaupdate) FreeMemory(aasworld.areaupdate);
+	aasworld.areaupdate = NULL;
+	if (aasworld.portalupdate) FreeMemory(aasworld.portalupdate);
+	aasworld.portalupdate = NULL;
+	// free lists with areas the reachabilities go through
+	if (aasworld.reachabilityareas) FreeMemory(aasworld.reachabilityareas);
+	aasworld.reachabilityareas = NULL;
+	// free the reachability area index
+	if (aasworld.reachabilityareaindex) FreeMemory(aasworld.reachabilityareaindex);
+	aasworld.reachabilityareaindex = NULL;
+	// free area contents travel flags look up table
+	if (aasworld.areacontentstravelflags) FreeMemory(aasworld.areacontentstravelflags);
+	aasworld.areacontentstravelflags = NULL;
+} //end of the function AAS_FreeRoutingCaches
+//===========================================================================
+// update the given routing cache
+//
+// Parameter:			areacache		: routing cache to update
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_UpdateAreaRoutingCache(aas_routingcache_t *areacache)
+{
+	int i, nextareanum, cluster, badtravelflags, clusterareanum, linknum;
+	int numreachabilityareas;
+	unsigned short int t, startareatraveltimes[128]; //NOTE: not more than 128 reachabilities per area allowed
+	aas_routingupdate_t *updateliststart, *updatelistend, *curupdate, *nextupdate;
+	aas_reachability_t *reach;
+	aas_reversedreachability_t *revreach;
+	aas_reversedlink_t *revlink;
+
+#ifdef ROUTING_DEBUG
+	numareacacheupdates++;
+#endif //ROUTING_DEBUG
+	//number of reachability areas within this cluster
+	numreachabilityareas = aasworld.clusters[areacache->cluster].numreachabilityareas;
+	//
+	aasworld.frameroutingupdates++;
+	//clear the routing update fields
+//	Com_Memset(aasworld.areaupdate, 0, aasworld.numareas * sizeof(aas_routingupdate_t));
+	//
+	badtravelflags = ~areacache->travelflags;
+	//
+	clusterareanum = AAS_ClusterAreaNum(areacache->cluster, areacache->areanum);
+	if (clusterareanum >= numreachabilityareas) return;
+	//
+	Com_Memset(startareatraveltimes, 0, sizeof(startareatraveltimes));
+	//
+	curupdate = &aasworld.areaupdate[clusterareanum];
+	curupdate->areanum = areacache->areanum;
+	//VectorCopy(areacache->origin, curupdate->start);
+	curupdate->areatraveltimes = startareatraveltimes;
+	curupdate->tmptraveltime = areacache->starttraveltime;
+	//
+	areacache->traveltimes[clusterareanum] = areacache->starttraveltime;
+	//put the area to start with in the current read list
+	curupdate->next = NULL;
+	curupdate->prev = NULL;
+	updateliststart = curupdate;
+	updatelistend = curupdate;
+	//while there are updates in the current list
+	while (updateliststart)
+	{
+		curupdate = updateliststart;
+		//
+		if (curupdate->next) curupdate->next->prev = NULL;
+		else updatelistend = NULL;
+		updateliststart = curupdate->next;
+		//
+		curupdate->inlist = qfalse;
+		//check all reversed reachability links
+		revreach = &aasworld.reversedreachability[curupdate->areanum];
+		//
+		for (i = 0, revlink = revreach->first; revlink; revlink = revlink->next, i++)
+		{
+			linknum = revlink->linknum;
+			reach = &aasworld.reachability[linknum];
+			//if there is used an undesired travel type
+			if (AAS_TravelFlagForType_inline(reach->traveltype) & badtravelflags) continue;
+			//if not allowed to enter the next area
+			if (aasworld.areasettings[reach->areanum].areaflags & AREA_DISABLED) continue;
+			//if the next area has a not allowed travel flag
+			if (AAS_AreaContentsTravelFlags_inline(reach->areanum) & badtravelflags) continue;
+			//number of the area the reversed reachability leads to
+			nextareanum = revlink->areanum;
+			//get the cluster number of the area
+			cluster = aasworld.areasettings[nextareanum].cluster;
+			//don't leave the cluster
+			if (cluster > 0 && cluster != areacache->cluster) continue;
+			//get the number of the area in the cluster
+			clusterareanum = AAS_ClusterAreaNum(areacache->cluster, nextareanum);
+			if (clusterareanum >= numreachabilityareas) continue;
+			//time already travelled plus the traveltime through
+			//the current area plus the travel time from the reachability
+			t = curupdate->tmptraveltime +
+						//AAS_AreaTravelTime(curupdate->areanum, curupdate->start, reach->end) +
+						curupdate->areatraveltimes[i] +
+							reach->traveltime;
+			//
+			if (!areacache->traveltimes[clusterareanum] ||
+					areacache->traveltimes[clusterareanum] > t)
+			{
+				areacache->traveltimes[clusterareanum] = t;
+				areacache->reachabilities[clusterareanum] = linknum - aasworld.areasettings[nextareanum].firstreachablearea;
+				nextupdate = &aasworld.areaupdate[clusterareanum];
+				nextupdate->areanum = nextareanum;
+				nextupdate->tmptraveltime = t;
+				//VectorCopy(reach->start, nextupdate->start);
+				nextupdate->areatraveltimes = aasworld.areatraveltimes[nextareanum][linknum -
+													aasworld.areasettings[nextareanum].firstreachablearea];
+				if (!nextupdate->inlist)
+				{
+					// we add the update to the end of the list
+					// we could also use a B+ tree to have a real sorted list
+					// on travel time which makes for faster routing updates
+					nextupdate->next = NULL;
+					nextupdate->prev = updatelistend;
+					if (updatelistend) updatelistend->next = nextupdate;
+					else updateliststart = nextupdate;
+					updatelistend = nextupdate;
+					nextupdate->inlist = qtrue;
+				} //end if
+			} //end if
+		} //end for
+	} //end while
+} //end of the function AAS_UpdateAreaRoutingCache
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+aas_routingcache_t *AAS_GetAreaRoutingCache(int clusternum, int areanum, int travelflags)
+{
+	int clusterareanum;
+	aas_routingcache_t *cache, *clustercache;
+
+	//number of the area in the cluster
+	clusterareanum = AAS_ClusterAreaNum(clusternum, areanum);
+	//pointer to the cache for the area in the cluster
+	clustercache = aasworld.clusterareacache[clusternum][clusterareanum];
+	//find the cache without undesired travel flags
+	for (cache = clustercache; cache; cache = cache->next)
+	{
+		//if there aren't used any undesired travel types for the cache
+		if (cache->travelflags == travelflags) break;
+	} //end for
+	//if there was no cache
+	if (!cache)
+	{
+		cache = AAS_AllocRoutingCache(aasworld.clusters[clusternum].numreachabilityareas);
+		cache->cluster = clusternum;
+		cache->areanum = areanum;
+		VectorCopy(aasworld.areas[areanum].center, cache->origin);
+		cache->starttraveltime = 1;
+		cache->travelflags = travelflags;
+		cache->prev = NULL;
+		cache->next = clustercache;
+		if (clustercache) clustercache->prev = cache;
+		aasworld.clusterareacache[clusternum][clusterareanum] = cache;
+		AAS_UpdateAreaRoutingCache(cache);
+	} //end if
+	else
+	{
+		AAS_UnlinkCache(cache);
+	} //end else
+	//the cache has been accessed
+	cache->time = AAS_RoutingTime();
+	cache->type = CACHETYPE_AREA;
+	AAS_LinkCache(cache);
+	return cache;
+} //end of the function AAS_GetAreaRoutingCache
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_UpdatePortalRoutingCache(aas_routingcache_t *portalcache)
+{
+	int i, portalnum, clusterareanum, clusternum;
+	unsigned short int t;
+	aas_portal_t *portal;
+	aas_cluster_t *cluster;
+	aas_routingcache_t *cache;
+	aas_routingupdate_t *updateliststart, *updatelistend, *curupdate, *nextupdate;
+
+#ifdef ROUTING_DEBUG
+	numportalcacheupdates++;
+#endif //ROUTING_DEBUG
+	//clear the routing update fields
+//	Com_Memset(aasworld.portalupdate, 0, (aasworld.numportals+1) * sizeof(aas_routingupdate_t));
+	//
+	curupdate = &aasworld.portalupdate[aasworld.numportals];
+	curupdate->cluster = portalcache->cluster;
+	curupdate->areanum = portalcache->areanum;
+	curupdate->tmptraveltime = portalcache->starttraveltime;
+	//if the start area is a cluster portal, store the travel time for that portal
+	clusternum = aasworld.areasettings[portalcache->areanum].cluster;
+	if (clusternum < 0)
+	{
+		portalcache->traveltimes[-clusternum] = portalcache->starttraveltime;
+	} //end if
+	//put the area to start with in the current read list
+	curupdate->next = NULL;
+	curupdate->prev = NULL;
+	updateliststart = curupdate;
+	updatelistend = curupdate;
+	//while there are updates in the current list
+	while (updateliststart)
+	{
+		curupdate = updateliststart;
+		//remove the current update from the list
+		if (curupdate->next) curupdate->next->prev = NULL;
+		else updatelistend = NULL;
+		updateliststart = curupdate->next;
+		//current update is removed from the list
+		curupdate->inlist = qfalse;
+		//
+		cluster = &aasworld.clusters[curupdate->cluster];
+		//
+		cache = AAS_GetAreaRoutingCache(curupdate->cluster,
+								curupdate->areanum, portalcache->travelflags);
+		//take all portals of the cluster
+		for (i = 0; i < cluster->numportals; i++)
+		{
+			portalnum = aasworld.portalindex[cluster->firstportal + i];
+			portal = &aasworld.portals[portalnum];
+			//if this is the portal of the current update continue
+			if (portal->areanum == curupdate->areanum) continue;
+			//
+			clusterareanum = AAS_ClusterAreaNum(curupdate->cluster, portal->areanum);
+			if (clusterareanum >= cluster->numreachabilityareas) continue;
+			//
+			t = cache->traveltimes[clusterareanum];
+			if (!t) continue;
+			t += curupdate->tmptraveltime;
+			//
+			if (!portalcache->traveltimes[portalnum] ||
+					portalcache->traveltimes[portalnum] > t)
+			{
+				portalcache->traveltimes[portalnum] = t;
+				nextupdate = &aasworld.portalupdate[portalnum];
+				if (portal->frontcluster == curupdate->cluster)
+				{
+					nextupdate->cluster = portal->backcluster;
+				} //end if
+				else
+				{
+					nextupdate->cluster = portal->frontcluster;
+				} //end else
+				nextupdate->areanum = portal->areanum;
+				//add travel time through the actual portal area for the next update
+				nextupdate->tmptraveltime = t + aasworld.portalmaxtraveltimes[portalnum];
+				if (!nextupdate->inlist)
+				{
+					// we add the update to the end of the list
+					// we could also use a B+ tree to have a real sorted list
+					// on travel time which makes for faster routing updates
+					nextupdate->next = NULL;
+					nextupdate->prev = updatelistend;
+					if (updatelistend) updatelistend->next = nextupdate;
+					else updateliststart = nextupdate;
+					updatelistend = nextupdate;
+					nextupdate->inlist = qtrue;
+				} //end if
+			} //end if
+		} //end for
+	} //end while
+} //end of the function AAS_UpdatePortalRoutingCache
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+aas_routingcache_t *AAS_GetPortalRoutingCache(int clusternum, int areanum, int travelflags)
+{
+	aas_routingcache_t *cache;
+
+	//find the cached portal routing if existing
+	for (cache = aasworld.portalcache[areanum]; cache; cache = cache->next)
+	{
+		if (cache->travelflags == travelflags) break;
+	} //end for
+	//if the portal routing isn't cached
+	if (!cache)
+	{
+		cache = AAS_AllocRoutingCache(aasworld.numportals);
+		cache->cluster = clusternum;
+		cache->areanum = areanum;
+		VectorCopy(aasworld.areas[areanum].center, cache->origin);
+		cache->starttraveltime = 1;
+		cache->travelflags = travelflags;
+		//add the cache to the cache list
+		cache->prev = NULL;
+		cache->next = aasworld.portalcache[areanum];
+		if (aasworld.portalcache[areanum]) aasworld.portalcache[areanum]->prev = cache;
+		aasworld.portalcache[areanum] = cache;
+		//update the cache
+		AAS_UpdatePortalRoutingCache(cache);
+	} //end if
+	else
+	{
+		AAS_UnlinkCache(cache);
+	} //end else
+	//the cache has been accessed
+	cache->time = AAS_RoutingTime();
+	cache->type = CACHETYPE_PORTAL;
+	AAS_LinkCache(cache);
+	return cache;
+} //end of the function AAS_GetPortalRoutingCache
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+int AAS_AreaRouteToGoalArea(int areanum, vec3_t origin, int goalareanum, int travelflags, int *traveltime, int *reachnum)
+{
+	int clusternum, goalclusternum, portalnum, i, clusterareanum, bestreachnum;
+	unsigned short int t, besttime;
+	aas_portal_t *portal;
+	aas_cluster_t *cluster;
+	aas_routingcache_t *areacache, *portalcache;
+	aas_reachability_t *reach;
+
+	if (!aasworld.initialized) return qfalse;
+
+	if (areanum == goalareanum)
+	{
+		*traveltime = 1;
+		*reachnum = 0;
+		return qtrue;
+	}
+	//
+	if (areanum <= 0 || areanum >= aasworld.numareas)
+	{
+		if (bot_developer)
+		{
+			botimport.Print(PRT_ERROR, "AAS_AreaTravelTimeToGoalArea: areanum %d out of range\n", areanum);
+		} //end if
+		return qfalse;
+	} //end if
+	if (goalareanum <= 0 || goalareanum >= aasworld.numareas)
+	{
+		if (bot_developer)
+		{
+			botimport.Print(PRT_ERROR, "AAS_AreaTravelTimeToGoalArea: goalareanum %d out of range\n", goalareanum);
+		} //end if
+		return qfalse;
+	} //end if
+	// make sure the routing cache doesn't grow to large
+	while(AvailableMemory() < 1 * 1024 * 1024) {
+		if (!AAS_FreeOldestCache()) break;
+	}
+	//
+	if (AAS_AreaDoNotEnter(areanum) || AAS_AreaDoNotEnter(goalareanum))
+	{
+		travelflags |= TFL_DONOTENTER;
+	} //end if
+	//NOTE: the number of routing updates is limited per frame
+	/*
+	if (aasworld.frameroutingupdates > MAX_FRAMEROUTINGUPDATES)
+	{
+#ifdef DEBUG
+		//Log_Write("WARNING: AAS_AreaTravelTimeToGoalArea: frame routing updates overflowed");
+#endif
+		return 0;
+	} //end if
+	*/
+	//
+	clusternum = aasworld.areasettings[areanum].cluster;
+	goalclusternum = aasworld.areasettings[goalareanum].cluster;
+	//check if the area is a portal of the goal area cluster
+	if (clusternum < 0 && goalclusternum > 0)
+	{
+		portal = &aasworld.portals[-clusternum];
+		if (portal->frontcluster == goalclusternum ||
+				portal->backcluster == goalclusternum)
+		{
+			clusternum = goalclusternum;
+		} //end if
+	} //end if
+	//check if the goalarea is a portal of the area cluster
+	else if (clusternum > 0 && goalclusternum < 0)
+	{
+		portal = &aasworld.portals[-goalclusternum];
+		if (portal->frontcluster == clusternum ||
+				portal->backcluster == clusternum)
+		{
+			goalclusternum = clusternum;
+		} //end if
+	} //end if
+	//if both areas are in the same cluster
+	//NOTE: there might be a shorter route via another cluster!!! but we don't care
+	if (clusternum > 0 && goalclusternum > 0 && clusternum == goalclusternum)
+	{
+		//
+		areacache = AAS_GetAreaRoutingCache(clusternum, goalareanum, travelflags);
+		//the number of the area in the cluster
+		clusterareanum = AAS_ClusterAreaNum(clusternum, areanum);
+		//the cluster the area is in
+		cluster = &aasworld.clusters[clusternum];
+		//if the area is NOT a reachability area
+		if (clusterareanum >= cluster->numreachabilityareas) return 0;
+		//if it is possible to travel to the goal area through this cluster
+		if (areacache->traveltimes[clusterareanum] != 0)
+		{
+			*reachnum = aasworld.areasettings[areanum].firstreachablearea +
+							areacache->reachabilities[clusterareanum];
+			if (!origin) {
+				*traveltime = areacache->traveltimes[clusterareanum];
+				return qtrue;
+			}
+			reach = &aasworld.reachability[*reachnum];
+			*traveltime = areacache->traveltimes[clusterareanum] +
+							AAS_AreaTravelTime(areanum, origin, reach->start);
+			//
+			return qtrue;
+		} //end if
+	} //end if
+	//
+	clusternum = aasworld.areasettings[areanum].cluster;
+	goalclusternum = aasworld.areasettings[goalareanum].cluster;
+	//if the goal area is a portal
+	if (goalclusternum < 0)
+	{
+		//just assume the goal area is part of the front cluster
+		portal = &aasworld.portals[-goalclusternum];
+		goalclusternum = portal->frontcluster;
+	} //end if
+	//get the portal routing cache
+	portalcache = AAS_GetPortalRoutingCache(goalclusternum, goalareanum, travelflags);
+	//if the area is a cluster portal, read directly from the portal cache
+	if (clusternum < 0)
+	{
+		*traveltime = portalcache->traveltimes[-clusternum];
+		*reachnum = aasworld.areasettings[areanum].firstreachablearea +
+						portalcache->reachabilities[-clusternum];
+		return qtrue;
+	} //end if
+	//
+	besttime = 0;
+	bestreachnum = -1;
+	//the cluster the area is in
+	cluster = &aasworld.clusters[clusternum];
+	//find the portal of the area cluster leading towards the goal area
+	for (i = 0; i < cluster->numportals; i++)
+	{
+		portalnum = aasworld.portalindex[cluster->firstportal + i];
+		//if the goal area isn't reachable from the portal
+		if (!portalcache->traveltimes[portalnum]) continue;
+		//
+		portal = &aasworld.portals[portalnum];
+		//get the cache of the portal area
+		areacache = AAS_GetAreaRoutingCache(clusternum, portal->areanum, travelflags);
+		//current area inside the current cluster
+		clusterareanum = AAS_ClusterAreaNum(clusternum, areanum);
+		//if the area is NOT a reachability area
+		if (clusterareanum >= cluster->numreachabilityareas) continue;
+		//if the portal is NOT reachable from this area
+		if (!areacache->traveltimes[clusterareanum]) continue;
+		//total travel time is the travel time the portal area is from
+		//the goal area plus the travel time towards the portal area
+		t = portalcache->traveltimes[portalnum] + areacache->traveltimes[clusterareanum];
+		//FIXME: add the exact travel time through the actual portal area
+		//NOTE: for now we just add the largest travel time through the portal area
+		//		because we can't directly calculate the exact travel time
+		//		to be more specific we don't know which reachability was used to travel
+		//		into the portal area
+		t += aasworld.portalmaxtraveltimes[portalnum];
+		//
+		if (origin)
+		{
+			*reachnum = aasworld.areasettings[areanum].firstreachablearea +
+							areacache->reachabilities[clusterareanum];
+			reach = aasworld.reachability + *reachnum;
+			t += AAS_AreaTravelTime(areanum, origin, reach->start);
+		} //end if
+		//if the time is better than the one already found
+		if (!besttime || t < besttime)
+		{
+			bestreachnum = *reachnum;
+			besttime = t;
+		} //end if
+	} //end for
+	if (bestreachnum < 0) {
+		return qfalse;
+	}
+	*reachnum = bestreachnum;
+	*traveltime = besttime;
+	return qtrue;
+} //end of the function AAS_AreaRouteToGoalArea
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+int AAS_AreaTravelTimeToGoalArea(int areanum, vec3_t origin, int goalareanum, int travelflags)
+{
+	int traveltime, reachnum;
+
+	if (AAS_AreaRouteToGoalArea(areanum, origin, goalareanum, travelflags, &traveltime, &reachnum))
+	{
+		return traveltime;
+	}
+	return 0;
+} //end of the function AAS_AreaTravelTimeToGoalArea
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+int AAS_AreaReachabilityToGoalArea(int areanum, vec3_t origin, int goalareanum, int travelflags)
+{
+	int traveltime, reachnum;
+
+	if (AAS_AreaRouteToGoalArea(areanum, origin, goalareanum, travelflags, &traveltime, &reachnum))
+	{
+		return reachnum;
+	}
+	return 0;
+} //end of the function AAS_AreaReachabilityToGoalArea
+//===========================================================================
+// predict the route and stop on one of the stop events
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+int AAS_PredictRoute(struct aas_predictroute_s *route, int areanum, vec3_t origin,
+							int goalareanum, int travelflags, int maxareas, int maxtime,
+							int stopevent, int stopcontents, int stoptfl, int stopareanum)
+{
+	int curareanum, reachnum, i, j, testareanum;
+	vec3_t curorigin;
+	aas_reachability_t *reach;
+	aas_reachabilityareas_t *reachareas;
+
+	//init output
+	route->stopevent = RSE_NONE;
+	route->endarea = goalareanum;
+	route->endcontents = 0;
+	route->endtravelflags = 0;
+	VectorCopy(origin, route->endpos);
+	route->time = 0;
+
+	curareanum = areanum;
+	VectorCopy(origin, curorigin);
+
+	for (i = 0; curareanum != goalareanum && (!maxareas || i < maxareas) && i < aasworld.numareas; i++)
+	{
+		reachnum = AAS_AreaReachabilityToGoalArea(curareanum, curorigin, goalareanum, travelflags);
+		if (!reachnum)
+		{
+			route->stopevent = RSE_NOROUTE;
+			return qfalse;
+		} //end if
+		reach = &aasworld.reachability[reachnum];
+		//
+		if (stopevent & RSE_USETRAVELTYPE)
+		{
+			if (AAS_TravelFlagForType_inline(reach->traveltype) & stoptfl)
+			{
+				route->stopevent = RSE_USETRAVELTYPE;
+				route->endarea = curareanum;
+				route->endcontents = aasworld.areasettings[curareanum].contents;
+				route->endtravelflags = AAS_TravelFlagForType_inline(reach->traveltype);
+				VectorCopy(reach->start, route->endpos);
+				return qtrue;
+			} //end if
+			if (AAS_AreaContentsTravelFlags_inline(reach->areanum) & stoptfl)
+			{
+				route->stopevent = RSE_USETRAVELTYPE;
+				route->endarea = reach->areanum;
+				route->endcontents = aasworld.areasettings[reach->areanum].contents;
+				route->endtravelflags = AAS_AreaContentsTravelFlags_inline(reach->areanum);
+				VectorCopy(reach->end, route->endpos);
+				route->time += AAS_AreaTravelTime(areanum, origin, reach->start);
+				route->time += reach->traveltime;
+				return qtrue;
+			} //end if
+		} //end if
+		reachareas = &aasworld.reachabilityareas[reachnum];
+		for (j = 0; j < reachareas->numareas + 1; j++)
+		{
+			if (j >= reachareas->numareas)
+				testareanum = reach->areanum;
+			else
+				testareanum = aasworld.reachabilityareaindex[reachareas->firstarea + j];
+			if (stopevent & RSE_ENTERCONTENTS)
+			{
+				if (aasworld.areasettings[testareanum].contents & stopcontents)
+				{
+					route->stopevent = RSE_ENTERCONTENTS;
+					route->endarea = testareanum;
+					route->endcontents = aasworld.areasettings[testareanum].contents;
+					VectorCopy(reach->end, route->endpos);
+					route->time += AAS_AreaTravelTime(areanum, origin, reach->start);
+					route->time += reach->traveltime;
+					return qtrue;
+				} //end if
+			} //end if
+			if (stopevent & RSE_ENTERAREA)
+			{
+				if (testareanum == stopareanum)
+				{
+					route->stopevent = RSE_ENTERAREA;
+					route->endarea = testareanum;
+					route->endcontents = aasworld.areasettings[testareanum].contents;
+					VectorCopy(reach->start, route->endpos);
+					return qtrue;
+				} //end if
+			} //end if
+		} //end for
+
+		route->time += AAS_AreaTravelTime(areanum, origin, reach->start);
+		route->time += reach->traveltime;
+		route->endarea = reach->areanum;
+		route->endcontents = aasworld.areasettings[reach->areanum].contents;
+		route->endtravelflags = AAS_TravelFlagForType_inline(reach->traveltype);
+		VectorCopy(reach->end, route->endpos);
+		//
+		curareanum = reach->areanum;
+		VectorCopy(reach->end, curorigin);
+		//
+		if (maxtime && route->time > maxtime)
+			break;
+	} //end while
+	if (curareanum != goalareanum)
+		return qfalse;
+	return qtrue;
+} //end of the function AAS_PredictRoute
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+int AAS_BridgeWalkable(int areanum)
+{
+	return qfalse;
+} //end of the function AAS_BridgeWalkable
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+void AAS_ReachabilityFromNum(int num, struct aas_reachability_s *reach)
+{
+	if (!aasworld.initialized)
+	{
+		Com_Memset(reach, 0, sizeof(aas_reachability_t));
+		return;
+	} //end if
+	if (num < 0 || num >= aasworld.reachabilitysize)
+	{
+		Com_Memset(reach, 0, sizeof(aas_reachability_t));
+		return;
+	} //end if
+	Com_Memcpy(reach, &aasworld.reachability[num], sizeof(aas_reachability_t));;
+} //end of the function AAS_ReachabilityFromNum
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+int AAS_NextAreaReachability(int areanum, int reachnum)
+{
+	aas_areasettings_t *settings;
+
+	if (!aasworld.initialized) return 0;
+
+	if (areanum <= 0 || areanum >= aasworld.numareas)
+	{
+		botimport.Print(PRT_ERROR, "AAS_NextAreaReachability: areanum %d out of range\n", areanum);
+		return 0;
+	} //end if
+
+	settings = &aasworld.areasettings[areanum];
+	if (!reachnum)
+	{
+		return settings->firstreachablearea;
+	} //end if
+	if (reachnum < settings->firstreachablearea)
+	{
+		botimport.Print(PRT_FATAL, "AAS_NextAreaReachability: reachnum < settings->firstreachableara");
+		return 0;
+	} //end if
+	reachnum++;
+	if (reachnum >= settings->firstreachablearea + settings->numreachableareas)
+	{
+		return 0;
+	} //end if
+	return reachnum;
+} //end of the function AAS_NextAreaReachability
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+int AAS_NextModelReachability(int num, int modelnum)
+{
+	int i;
+
+	if (num <= 0) num = 1;
+	else if (num >= aasworld.reachabilitysize) return 0;
+	else num++;
+	//
+	for (i = num; i < aasworld.reachabilitysize; i++)
+	{
+		if ((aasworld.reachability[i].traveltype & TRAVELTYPE_MASK) == TRAVEL_ELEVATOR)
+		{
+			if (aasworld.reachability[i].facenum == modelnum) return i;
+		} //end if
+		else if ((aasworld.reachability[i].traveltype & TRAVELTYPE_MASK) == TRAVEL_FUNCBOB)
+		{
+			if ((aasworld.reachability[i].facenum & 0x0000FFFF) == modelnum) return i;
+		} //end if
+	} //end for
+	return 0;
+} //end of the function AAS_NextModelReachability
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+int AAS_RandomGoalArea(int areanum, int travelflags, int *goalareanum, vec3_t goalorigin)
+{
+	int i, n, t;
+	vec3_t start, end;
+	aas_trace_t trace;
+
+	//if the area has no reachabilities
+	if (!AAS_AreaReachability(areanum)) return qfalse;
+	//
+	n = aasworld.numareas * random();
+	for (i = 0; i < aasworld.numareas; i++)
+	{
+		if (n <= 0) n = 1;
+		if (n >= aasworld.numareas) n = 1;
+		if (AAS_AreaReachability(n))
+		{
+			t = AAS_AreaTravelTimeToGoalArea(areanum, aasworld.areas[areanum].center, n, travelflags);
+			//if the goal is reachable
+			if (t > 0)
+			{
+				if (AAS_AreaSwim(n))
+				{
+					*goalareanum = n;
+					VectorCopy(aasworld.areas[n].center, goalorigin);
+					//botimport.Print(PRT_MESSAGE, "found random goal area %d\n", *goalareanum);
+					return qtrue;
+				} //end if
+				VectorCopy(aasworld.areas[n].center, start);
+				if (!AAS_PointAreaNum(start))
+					Log_Write("area %d center %f %f %f in solid?", n, start[0], start[1], start[2]);
+				VectorCopy(start, end);
+				end[2] -= 300;
+				trace = AAS_TraceClientBBox(start, end, PRESENCE_CROUCH, -1);
+				if (!trace.startsolid && trace.fraction < 1 && AAS_PointAreaNum(trace.endpos) == n)
+				{
+					if (AAS_AreaGroundFaceArea(n) > 300)
+					{
+						*goalareanum = n;
+						VectorCopy(trace.endpos, goalorigin);
+						//botimport.Print(PRT_MESSAGE, "found random goal area %d\n", *goalareanum);
+						return qtrue;
+					} //end if
+				} //end if
+			} //end if
+		} //end if
+		n++;
+	} //end for
+	return qfalse;
+} //end of the function AAS_RandomGoalArea
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+int AAS_AreaVisible(int srcarea, int destarea)
+{
+	return qfalse;
+} //end of the function AAS_AreaVisible
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+float DistancePointToLine(vec3_t v1, vec3_t v2, vec3_t point)
+{
+	vec3_t vec, p2;
+
+	AAS_ProjectPointOntoVector(point, v1, v2, p2);
+	VectorSubtract(point, p2, vec);
+	return VectorLength(vec);
+} //end of the function DistancePointToLine
+//===========================================================================
+//
+// Parameter:			-
+// Returns:				-
+// Changes Globals:		-
+//===========================================================================
+int AAS_NearestHideArea(int srcnum, vec3_t origin, int areanum, int enemynum, vec3_t enemyorigin, int enemyareanum, int travelflags)
+{
+	int i, j, nextareanum, badtravelflags, numreach, bestarea;
+	unsigned short int t, besttraveltime;
+	static unsigned short int *hidetraveltimes;
+	aas_routingupdate_t *updateliststart, *updatelistend, *curupdate, *nextupdate;
+	aas_reachability_t *reach;
+	float dist1, dist2;
+	vec3_t v1, v2, p;
+	qboolean startVisible;
+
+	//
+	if (!hidetraveltimes)
+	{
+		hidetraveltimes = (unsigned short int *) GetClearedMemory(aasworld.numareas * sizeof(unsigned short int));
+	} //end if
+	else
+	{
+		Com_Memset(hidetraveltimes, 0, aasworld.numareas * sizeof(unsigned short int));
+	} //end else
+	besttraveltime = 0;
+	bestarea = 0;
+	//assume visible
+	startVisible = qtrue;
+	//
+	badtravelflags = ~travelflags;
+	//
+	curupdate = &aasworld.areaupdate[areanum];
+	curupdate->areanum = areanum;
+	VectorCopy(origin, curupdate->start);
+	curupdate->areatraveltimes = aasworld.areatraveltimes[areanum][0];
+	curupdate->tmptraveltime = 0;
+	//put the area to start with in the current read list
+	curupdate->next = NULL;
+	curupdate->prev = NULL;
+	updateliststart = curupdate;
+	updatelistend = curupdate;
+	//while there are updates in the list
+	while (updateliststart)
+	{
+		curupdate = updateliststart;
+		//
+		if (curupdate->next) curupdate->next->prev = NULL;
+		else updatelistend = NULL;
+		updateliststart = curupdate->next;
+		//
+		curupdate->inlist = qfalse;
+		//check all reversed reachability links
+		numreach = aasworld.areasettings[curupdate->areanum].numreachableareas;
+		reach = &aasworld.reachability[aasworld.areasettings[curupdate->areanum].firstreachablearea];
+		//
+		for (i = 0; i < numreach; i++, reach++)
+		{
+			//if an undesired travel type is used
+			if (AAS_TravelFlagForType_inline(reach->traveltype) & badtravelflags) continue;
+			//
+			if (AAS_AreaContentsTravelFlags_inline(reach->areanum) & badtravelflags) continue;
+			//number of the area the reachability leads to
+			nextareanum = reach->areanum;
+			// if this moves us into the enemies area, skip it
+			if (nextareanum == enemyareanum) continue;
+			//time already travelled plus the traveltime through
+			//the current area plus the travel time from the reachability
+			t = curupdate->tmptraveltime +
+						AAS_AreaTravelTime(curupdate->areanum, curupdate->start, reach->start) +
+							reach->traveltime;
+
+			//avoid going near the enemy
+			AAS_ProjectPointOntoVector(enemyorigin, curupdate->start, reach->end, p);
+			for (j = 0; j < 3; j++)
+				if ((p[j] > curupdate->start[j] && p[j] > reach->end[j]) ||
+					(p[j] < curupdate->start[j] && p[j] < reach->end[j]))
+					break;
+			if (j < 3)
+			{
+				VectorSubtract(enemyorigin, reach->end, v2);
+			} //end if
+			else
+			{
+				VectorSubtract(enemyorigin, p, v2);
+			} //end else
+			dist2 = VectorLength(v2);
+			//never go through the enemy
+			if (dist2 < 40) continue;
+			//
+			VectorSubtract(enemyorigin, curupdate->start, v1);
+			dist1 = VectorLength(v1);
+			//
+			if (dist2 < dist1)
+			{
+				t += (dist1 - dist2) * 10;
+			}
+			// if we weren't visible when starting, make sure we don't move into their view
+			if (!startVisible && AAS_AreaVisible(enemyareanum, nextareanum)) {
+				continue;
+			}
+			//
+			if (besttraveltime && t >= besttraveltime) continue;
+			//
+			if (!hidetraveltimes[nextareanum] ||
+					hidetraveltimes[nextareanum] > t)
+			{
+				//if the nextarea is not visible from the enemy area
+				if (!AAS_AreaVisible(enemyareanum, nextareanum))
+				{
+					besttraveltime = t;
+					bestarea = nextareanum;
+				} //end if
+				hidetraveltimes[nextareanum] = t;
+				nextupdate = &aasworld.areaupdate[nextareanum];
+				nextupdate->areanum = nextareanum;
+				nextupdate->tmptraveltime = t;
+				//remember where we entered this area
+				VectorCopy(reach->end, nextupdate->start);
+				//if this update is not in the list yet
+				if (!nextupdate->inlist)
+				{
+					//add the new update to the end of the list
+					nextupdate->next = NULL;
+					nextupdate->prev = updatelistend;
+					if (updatelistend) updatelistend->next = nextupdate;
+					else updateliststart = nextupdate;
+					updatelistend = nextupdate;
+					nextupdate->inlist = qtrue;
+				} //end if
+			} //end if
+		} //end for
+	} //end while
+	return bestarea;
+} //end of the function AAS_NearestHideArea