diff options
Diffstat (limited to 'code/botlib/be_aas_route.c')
| -rwxr-xr-x | code/botlib/be_aas_route.c | 2209 |
1 files changed, 2209 insertions, 0 deletions
diff --git a/code/botlib/be_aas_route.c b/code/botlib/be_aas_route.c new file mode 100755 index 0000000..441984d --- /dev/null +++ b/code/botlib/be_aas_route.c @@ -0,0 +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
|