Quake III Arena: code/botlib/be_aas

00735 {
00736     aas_routingcache_t *cache;
00737     int size;
00738 
00739     //
00740     size = sizeof(aas_routingcache_t)
00741                         + numtraveltimes * sizeof(unsigned short int)
00742                         + numtraveltimes * sizeof(unsigned char);
00743     //
00744     routingcachesize += size;
00745     //
00746     cache = (aas_routingcache_t *) GetClearedMemory(size);
00747     cache->reachabilities = (unsigned char *) cache + sizeof(aas_routingcache_t)
00748                                 + numtraveltimes * sizeof(unsigned short int);
00749     cache->size = size;
00750     return cache;
00751 } //end of the function AAS_AllocRoutingCache

00393 {
00394     return aasworld.areacontentstravelflags[areanum];
00395 } //end of the function AAS_AreaContentsTravelFlags

00383 {
00384     return aasworld.areacontentstravelflags[areanum];
00385 } //end of the function AAS_AreaContentsTravelFlags

01784 {
01785     int traveltime, reachnum;
01786 
01787     if (AAS_AreaRouteToGoalArea(areanum, origin, goalareanum, travelflags, &traveltime, &reachnum))
01788     {
01789         return reachnum;
01790     }
01791     return 0;
01792 } //end of the function AAS_AreaReachabilityToGoalArea

01586 {
01587     int clusternum, goalclusternum, portalnum, i, clusterareanum, bestreachnum;
01588     unsigned short int t, besttime;
01589     aas_portal_t *portal;
01590     aas_cluster_t *cluster;
01591     aas_routingcache_t *areacache, *portalcache;
01592     aas_reachability_t *reach;
01593 
01594     if (!aasworld.initialized) return qfalse;
01595 
01596     if (areanum == goalareanum)
01597     {
01598         *traveltime = 1;
01599         *reachnum = 0;
01600         return qtrue;
01601     }
01602     //
01603     if (areanum <= 0 || areanum >= aasworld.numareas)
01604     {
01605         if (bot_developer)
01606         {
01607             botimport.Print(PRT_ERROR, "AAS_AreaTravelTimeToGoalArea: areanum %d out of range\n", areanum);
01608         } //end if
01609         return qfalse;
01610     } //end if
01611     if (goalareanum <= 0 || goalareanum >= aasworld.numareas)
01612     {
01613         if (bot_developer)
01614         {
01615             botimport.Print(PRT_ERROR, "AAS_AreaTravelTimeToGoalArea: goalareanum %d out of range\n", goalareanum);
01616         } //end if
01617         return qfalse;
01618     } //end if
01619     // make sure the routing cache doesn't grow to large
01620     while(AvailableMemory() < 1 * 1024 * 1024) {
01621         if (!AAS_FreeOldestCache()) break;
01622     }
01623     //
01624     if (AAS_AreaDoNotEnter(areanum) || AAS_AreaDoNotEnter(goalareanum))
01625     {
01626         travelflags |= TFL_DONOTENTER;
01627     } //end if
01628     //NOTE: the number of routing updates is limited per frame
01629     /*
01630     if (aasworld.frameroutingupdates > MAX_FRAMEROUTINGUPDATES)
01631     {
01632 #ifdef DEBUG
01633         //Log_Write("WARNING: AAS_AreaTravelTimeToGoalArea: frame routing updates overflowed");
01634 #endif
01635         return 0;
01636     } //end if
01637     */
01638     //
01639     clusternum = aasworld.areasettings[areanum].cluster;
01640     goalclusternum = aasworld.areasettings[goalareanum].cluster;
01641     //check if the area is a portal of the goal area cluster
01642     if (clusternum < 0 && goalclusternum > 0)
01643     {
01644         portal = &aasworld.portals[-clusternum];
01645         if (portal->frontcluster == goalclusternum ||
01646                 portal->backcluster == goalclusternum)
01647         {
01648             clusternum = goalclusternum;
01649         } //end if
01650     } //end if
01651     //check if the goalarea is a portal of the area cluster
01652     else if (clusternum > 0 && goalclusternum < 0)
01653     {
01654         portal = &aasworld.portals[-goalclusternum];
01655         if (portal->frontcluster == clusternum ||
01656                 portal->backcluster == clusternum)
01657         {
01658             goalclusternum = clusternum;
01659         } //end if
01660     } //end if
01661     //if both areas are in the same cluster
01662     //NOTE: there might be a shorter route via another cluster!!! but we don't care
01663     if (clusternum > 0 && goalclusternum > 0 && clusternum == goalclusternum)
01664     {
01665         //
01666         areacache = AAS_GetAreaRoutingCache(clusternum, goalareanum, travelflags);
01667         //the number of the area in the cluster
01668         clusterareanum = AAS_ClusterAreaNum(clusternum, areanum);
01669         //the cluster the area is in
01670         cluster = &aasworld.clusters[clusternum];
01671         //if the area is NOT a reachability area
01672         if (clusterareanum >= cluster->numreachabilityareas) return 0;
01673         //if it is possible to travel to the goal area through this cluster
01674         if (areacache->traveltimes[clusterareanum] != 0)
01675         {
01676             *reachnum = aasworld.areasettings[areanum].firstreachablearea +
01677                             areacache->reachabilities[clusterareanum];
01678             if (!origin) {
01679                 *traveltime = areacache->traveltimes[clusterareanum];
01680                 return qtrue;
01681             }
01682             reach = &aasworld.reachability[*reachnum];
01683             *traveltime = areacache->traveltimes[clusterareanum] +
01684                             AAS_AreaTravelTime(areanum, origin, reach->start);
01685             //
01686             return qtrue;
01687         } //end if
01688     } //end if
01689     //
01690     clusternum = aasworld.areasettings[areanum].cluster;
01691     goalclusternum = aasworld.areasettings[goalareanum].cluster;
01692     //if the goal area is a portal
01693     if (goalclusternum < 0)
01694     {
01695         //just assume the goal area is part of the front cluster
01696         portal = &aasworld.portals[-goalclusternum];
01697         goalclusternum = portal->frontcluster;
01698     } //end if
01699     //get the portal routing cache
01700     portalcache = AAS_GetPortalRoutingCache(goalclusternum, goalareanum, travelflags);
01701     //if the area is a cluster portal, read directly from the portal cache
01702     if (clusternum < 0)
01703     {
01704         *traveltime = portalcache->traveltimes[-clusternum];
01705         *reachnum = aasworld.areasettings[areanum].firstreachablearea +
01706                         portalcache->reachabilities[-clusternum];
01707         return qtrue;
01708     } //end if
01709     //
01710     besttime = 0;
01711     bestreachnum = -1;
01712     //the cluster the area is in
01713     cluster = &aasworld.clusters[clusternum];
01714     //find the portal of the area cluster leading towards the goal area
01715     for (i = 0; i < cluster->numportals; i++)
01716     {
01717         portalnum = aasworld.portalindex[cluster->firstportal + i];
01718         //if the goal area isn't reachable from the portal
01719         if (!portalcache->traveltimes[portalnum]) continue;
01720         //
01721         portal = &aasworld.portals[portalnum];
01722         //get the cache of the portal area
01723         areacache = AAS_GetAreaRoutingCache(clusternum, portal->areanum, travelflags);
01724         //current area inside the current cluster
01725         clusterareanum = AAS_ClusterAreaNum(clusternum, areanum);
01726         //if the area is NOT a reachability area
01727         if (clusterareanum >= cluster->numreachabilityareas) continue;
01728         //if the portal is NOT reachable from this area
01729         if (!areacache->traveltimes[clusterareanum]) continue;
01730         //total travel time is the travel time the portal area is from
01731         //the goal area plus the travel time towards the portal area
01732         t = portalcache->traveltimes[portalnum] + areacache->traveltimes[clusterareanum];
01733         //FIXME: add the exact travel time through the actual portal area
01734         //NOTE: for now we just add the largest travel time through the portal area
01735         //      because we can't directly calculate the exact travel time
01736         //      to be more specific we don't know which reachability was used to travel
01737         //      into the portal area
01738         t += aasworld.portalmaxtraveltimes[portalnum];
01739         //
01740         if (origin)
01741         {
01742             *reachnum = aasworld.areasettings[areanum].firstreachablearea +
01743                             areacache->reachabilities[clusterareanum];
01744             reach = aasworld.reachability + *reachnum;
01745             t += AAS_AreaTravelTime(areanum, origin, reach->start);
01746         } //end if
01747         //if the time is better than the one already found
01748         if (!besttime || t < besttime)
01749         {
01750             bestreachnum = *reachnum;
01751             besttime = t;
01752         } //end if
01753     } //end for
01754     if (bestreachnum < 0) {
01755         return qfalse;
01756     }
01757     *reachnum = bestreachnum;
01758     *traveltime = besttime;
01759     return qtrue;
01760 } //end of the function AAS_AreaRouteToGoalArea

00475 {
00476     int intdist;
00477     float dist;
00478     vec3_t dir;
00479 
00480     VectorSubtract(start, end, dir);
00481     dist = VectorLength(dir);
00482     //if crouch only area
00483     if (AAS_AreaCrouch(areanum)) dist *= DISTANCEFACTOR_CROUCH;
00484     //if swim area
00485     else if (AAS_AreaSwim(areanum)) dist *= DISTANCEFACTOR_SWIM;
00486     //normal walk area
00487     else dist *= DISTANCEFACTOR_WALK;
00488     //
00489     intdist = (int) dist;
00490     //make sure the distance isn't zero
00491     if (intdist <= 0) intdist = 1;
00492     return intdist;
00493 } //end of the function AAS_AreaTravelTime

01768 {
01769     int traveltime, reachnum;
01770 
01771     if (AAS_AreaRouteToGoalArea(areanum, origin, goalareanum, travelflags, &traveltime, &reachnum))
01772     {
01773         return traveltime;
01774     }
01775     return 0;
01776 } //end of the function AAS_AreaTravelTimeToGoalArea

02057 {
02058     return qfalse;
02059 } //end of the function AAS_AreaVisible

01910 {
01911     return qfalse;
01912 } //end of the function AAS_BridgeWalkable

00501 {
00502     int i, l, n, size;
00503     char *ptr;
00504     vec3_t end;
00505     aas_reversedreachability_t *revreach;
00506     aas_reversedlink_t *revlink;
00507     aas_reachability_t *reach;
00508     aas_areasettings_t *settings;
00509     int starttime;
00510 
00511     starttime = Sys_MilliSeconds();
00512     //if there are still area travel times, free the memory
00513     if (aasworld.areatraveltimes) FreeMemory(aasworld.areatraveltimes);
00514     //get the total size of all the area travel times
00515     size = aasworld.numareas * sizeof(unsigned short **);
00516     for (i = 0; i < aasworld.numareas; i++)
00517     {
00518         revreach = &aasworld.reversedreachability[i];
00519         //settings of the area
00520         settings = &aasworld.areasettings[i];
00521         //
00522         size += settings->numreachableareas * sizeof(unsigned short *);
00523         //
00524         size += settings->numreachableareas * revreach->numlinks * sizeof(unsigned short);
00525     } //end for
00526     //allocate memory for the area travel times
00527     ptr = (char *) GetClearedMemory(size);
00528     aasworld.areatraveltimes = (unsigned short ***) ptr;
00529     ptr += aasworld.numareas * sizeof(unsigned short **);
00530     //calcluate the travel times for all the areas
00531     for (i = 0; i < aasworld.numareas; i++)
00532     {
00533         //reversed reachabilities of this area
00534         revreach = &aasworld.reversedreachability[i];
00535         //settings of the area
00536         settings = &aasworld.areasettings[i];
00537         //
00538         aasworld.areatraveltimes[i] = (unsigned short **) ptr;
00539         ptr += settings->numreachableareas * sizeof(unsigned short *);
00540         //
00541         for (l = 0; l < settings->numreachableareas; l++)
00542         {
00543             aasworld.areatraveltimes[i][l] = (unsigned short *) ptr;
00544             ptr += revreach->numlinks * sizeof(unsigned short);
00545             //reachability link
00546             reach = &aasworld.reachability[settings->firstreachablearea + l];
00547             //
00548             for (n = 0, revlink = revreach->first; revlink; revlink = revlink->next, n++)
00549             {
00550                 VectorCopy(aasworld.reachability[revlink->linknum].end, end);
00551                 //
00552                 aasworld.areatraveltimes[i][l][n] = AAS_AreaTravelTime(i, end, reach->start);
00553             } //end for
00554         } //end for
00555     } //end for
00556 #ifdef DEBUG
00557     botimport.Print(PRT_MESSAGE, "area travel times %d msec\n", Sys_MilliSeconds() - starttime);
00558 #endif
00559 } //end of the function AAS_CalculateAreaTravelTimes

00110 {
00111     int side, areacluster;
00112 
00113     areacluster = aasworld.areasettings[areanum].cluster;
00114     if (areacluster > 0) return aasworld.areasettings[areanum].clusterareanum;
00115     else
00116     {
00117 /*#ifdef ROUTING_DEBUG
00118         if (aasworld.portals[-areacluster].frontcluster != cluster &&
00119                 aasworld.portals[-areacluster].backcluster != cluster)
00120         {
00121             botimport.Print(PRT_ERROR, "portal %d: does not belong to cluster %d\n"
00122                                             , -areacluster, cluster);
00123         } //end if
00124 #endif //ROUTING_DEBUG*/
00125         side = aasworld.portals[-areacluster].frontcluster != cluster;
00126         return aasworld.portals[-areacluster].clusterareanum[side];
00127     } //end else
00128 } //end of the function AAS_ClusterAreaNum

00888 {
00889     int i, j, t;
00890 
00891     aasworld.initialized = qtrue;
00892     botimport.Print(PRT_MESSAGE, "AAS_CreateAllRoutingCache\n");
00893     for (i = 1; i < aasworld.numareas; i++)
00894     {
00895         if (!AAS_AreaReachability(i)) continue;
00896         for (j = 1; j < aasworld.numareas; j++)
00897         {
00898             if (i == j) continue;
00899             if (!AAS_AreaReachability(j)) continue;
00900             t = AAS_AreaTravelTimeToGoalArea(i, aasworld.areas[i].center, j, TFL_DEFAULT);
00901             //Log_Write("traveltime from %d to %d is %d", i, j, t);
00902         } //end for
00903     } //end for
00904     aasworld.initialized = qfalse;
00905 } //end of the function AAS_CreateAllRoutingCache

00420 {
00421     int i, n;
00422     aas_reversedlink_t *revlink;
00423     aas_reachability_t *reach;
00424     aas_areasettings_t *settings;
00425     char *ptr;
00426 #ifdef DEBUG
00427     int starttime;
00428 
00429     starttime = Sys_MilliSeconds();
00430 #endif
00431     //free reversed links that have already been created
00432     if (aasworld.reversedreachability) FreeMemory(aasworld.reversedreachability);
00433     //allocate memory for the reversed reachability links
00434     ptr = (char *) GetClearedMemory(aasworld.numareas * sizeof(aas_reversedreachability_t) +
00435                             aasworld.reachabilitysize * sizeof(aas_reversedlink_t));
00436     //
00437     aasworld.reversedreachability = (aas_reversedreachability_t *) ptr;
00438     //pointer to the memory for the reversed links
00439     ptr += aasworld.numareas * sizeof(aas_reversedreachability_t);
00440     //check all reachabilities of all areas
00441     for (i = 1; i < aasworld.numareas; i++)
00442     {
00443         //settings of the area
00444         settings = &aasworld.areasettings[i];
00445         //
00446         if (settings->numreachableareas >= 128)
00447             botimport.Print(PRT_WARNING, "area %d has more than 128 reachabilities\n", i);
00448         //create reversed links for the reachabilities
00449         for (n = 0; n < settings->numreachableareas && n < 128; n++)
00450         {
00451             //reachability link
00452             reach = &aasworld.reachability[settings->firstreachablearea + n];
00453             //
00454             revlink = (aas_reversedlink_t *) ptr;
00455             ptr += sizeof(aas_reversedlink_t);
00456             //
00457             revlink->areanum = i;
00458             revlink->linknum = settings->firstreachablearea + n;
00459             revlink->next = aasworld.reversedreachability[reach->areanum].first;
00460             aasworld.reversedreachability[reach->areanum].first = revlink;
00461             aasworld.reversedreachability[reach->areanum].numlinks++;
00462         } //end for
00463     } //end for
00464 #ifdef DEBUG
00465     botimport.Print(PRT_MESSAGE, "reversed reachability %d msec\n", Sys_MilliSeconds() - starttime);
00466 #endif
00467 } //end of the function AAS_CreateReversedReachability

00309 {
00310     int flags;
00311 
00312     if (areanum <= 0 || areanum >= aasworld.numareas)
00313     {
00314         if (bot_developer)
00315         {
00316             botimport.Print(PRT_ERROR, "AAS_EnableRoutingArea: areanum %d out of range\n", areanum);
00317         } //end if
00318         return 0;
00319     } //end if
00320     flags = aasworld.areasettings[areanum].areaflags & AREA_DISABLED;
00321     if (enable < 0)
00322         return !flags;
00323 
00324     if (enable)
00325         aasworld.areasettings[areanum].areaflags &= ~AREA_DISABLED;
00326     else
00327         aasworld.areasettings[areanum].areaflags |= AREA_DISABLED;
00328     // if the status of the area changed
00329     if ( (flags & AREA_DISABLED) != (aasworld.areasettings[areanum].areaflags & AREA_DISABLED) )
00330     {
00331         //remove all routing cache involving this area
00332         AAS_RemoveRoutingCacheUsingArea( areanum );
00333     } //end if
00334     return !flags;
00335 } //end of the function AAS_EnableRoutingArea

00759 {
00760     int i, j;
00761     aas_routingcache_t *cache, *nextcache;
00762     aas_cluster_t *cluster;
00763 
00764     //free all cluster cache if existing
00765     if (!aasworld.clusterareacache) return;
00766     //free caches
00767     for (i = 0; i < aasworld.numclusters; i++)
00768     {
00769         cluster = &aasworld.clusters[i];
00770         for (j = 0; j < cluster->numareas; j++)
00771         {
00772             for (cache = aasworld.clusterareacache[i][j]; cache; cache = nextcache)
00773             {
00774                 nextcache = cache->next;
00775                 AAS_FreeRoutingCache(cache);
00776             } //end for
00777             aasworld.clusterareacache[i][j] = NULL;
00778         } //end for
00779     } //end for
00780     //free the cluster cache array
00781     FreeMemory(aasworld.clusterareacache);
00782     aasworld.clusterareacache = NULL;
00783 } //end of the function AAS_FreeAllClusterAreaCache

00820 {
00821     int i;
00822     aas_routingcache_t *cache, *nextcache;
00823 
00824     //free all portal cache if existing
00825     if (!aasworld.portalcache) return;
00826     //free portal caches
00827     for (i = 0; i < aasworld.numareas; i++)
00828     {
00829         for (cache = aasworld.portalcache[i]; cache; cache = nextcache)
00830         {
00831             nextcache = cache->next;
00832             AAS_FreeRoutingCache(cache);
00833         } //end for
00834         aasworld.portalcache[i] = NULL;
00835     } //end for
00836     FreeMemory(aasworld.portalcache);
00837     aasworld.portalcache = NULL;
00838 } //end of the function AAS_FreeAllPortalCache

00696 {
00697     int clusterareanum;
00698     aas_routingcache_t *cache;
00699 
00700     for (cache = aasworld.oldestcache; cache; cache = cache->time_next) {
00701         // never free area cache leading towards a portal
00702         if (cache->type == CACHETYPE_AREA && aasworld.areasettings[cache->areanum].cluster < 0) {
00703             continue;
00704         }
00705         break;
00706     }
00707     if (cach


Data Structures
struct	routecacheheader_s
Defines
#define	CACHE_REFRESHTIME 15.0f
#define	DISTANCEFACTOR_CROUCH 1.3f
#define	DISTANCEFACTOR_SWIM 1
#define	DISTANCEFACTOR_WALK 0.33f
#define	MAX_FRAMEROUTINGUPDATES 10
#define	MAX_REACHABILITYPASSAREAS 32
#define	RCID (('C'<<24)+('R'<<16)+('E'<<8)+'M')
#define	RCVERSION 2
#define	ROUTING_DEBUG
Typedefs
typedef routecacheheader_s	routecacheheader_t
Functions
aas_routingcache_t *	AAS_AllocRoutingCache (int numtraveltimes)
int	AAS_AreaContentsTravelFlags (int areanum)
__inline int	AAS_AreaContentsTravelFlags_inline (int areanum)
int	AAS_AreaReachabilityToGoalArea (int areanum, vec3_t origin, int goalareanum, int travelflags)
int	AAS_AreaRouteToGoalArea (int areanum, vec3_t origin, int goalareanum, int travelflags, int traveltime, int reachnum)
unsigned short int	AAS_AreaTravelTime (int areanum, vec3_t start, vec3_t end)
int	AAS_AreaTravelTimeToGoalArea (int areanum, vec3_t origin, int goalareanum, int travelflags)
int	AAS_AreaVisible (int srcarea, int destarea)
int	AAS_BridgeWalkable (int areanum)
void	AAS_CalculateAreaTravelTimes (void)
__inline int	AAS_ClusterAreaNum (int cluster, int areanum)
void	AAS_CreateAllRoutingCache (void)
void	AAS_CreateReversedReachability (void)
int	AAS_EnableRoutingArea (int areanum, int enable)
void	AAS_FreeAllClusterAreaCache (void)
void	AAS_FreeAllPortalCache (void)
int	AAS_FreeOldestCache (void)
void	AAS_FreeRoutingCache (aas_routingcache_t *cache)
void	AAS_FreeRoutingCaches (void)
int	AAS_GetAreaContentsTravelFlags (int areanum)
aas_routingcache_t *	AAS_GetAreaRoutingCache (int clusternum, int areanum, int travelflags)
aas_routingcache_t *	AAS_GetPortalRoutingCache (int clusternum, int areanum, int travelflags)
void	AAS_InitAreaContentsTravelFlags (void)
void	AAS_InitClusterAreaCache (void)
void	AAS_InitPortalCache (void)
void	AAS_InitPortalMaxTravelTimes (void)
void	AAS_InitReachabilityAreas (void)
void	AAS_InitRouting (void)
void	AAS_InitRoutingUpdate (void)
void	AAS_InitTravelFlagFromType (void)
void	AAS_LinkCache (aas_routingcache_t *cache)
int	AAS_NearestHideArea (int srcnum, vec3_t origin, int areanum, int enemynum, vec3_t enemyorigin, int enemyareanum, int travelflags)
int	AAS_NextAreaReachability (int areanum, int reachnum)
int	AAS_NextModelReachability (int num, int modelnum)
int	AAS_PortalMaxTravelTime (int portalnum)
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	AAS_RandomGoalArea (int areanum, int travelflags, int *goalareanum, vec3_t goalorigin)
void	AAS_ReachabilityFromNum (int num, struct aas_reachability_s *reach)
aas_routingcache_t *	AAS_ReadCache (fileHandle_t fp)
int	AAS_ReadRouteCache (void)
void	AAS_RemoveRoutingCacheInCluster (int clusternum)
void	AAS_RemoveRoutingCacheUsingArea (int areanum)
void	AAS_RoutingInfo (void)
__inline float	AAS_RoutingTime (void)
int	AAS_TravelFlagForType (int traveltype)
__inline int	AAS_TravelFlagForType_inline (int traveltype)
void	AAS_UnlinkCache (aas_routingcache_t *cache)
void	AAS_UpdateAreaRoutingCache (aas_routingcache_t *areacache)
void	AAS_UpdatePortalRoutingCache (aas_routingcache_t *portalcache)
void	AAS_WriteRouteCache (void)
float	DistancePointToLine (vec3_t v1, vec3_t v2, vec3_t point)
Variables
int	max_routingcachesize
int	numareacacheupdates
int	numportalcacheupdates
int	routingcachesize

be_aas_route.c File Reference

Data Structures

Defines

Typedefs

Functions

Variables

Define Documentation

Typedef Documentation

Function Documentation