1 /*
2 ===========================================================================
3 Copyright (C) 1999-2005 Id Software, Inc.
4 Copyright (C) 2000-2006 Tim Angus
5
6 This file is part of Tremulous.
7
8 Tremulous is free software; you can redistribute it
9 and/or modify it under the terms of the GNU General Public License as
10 published by the Free Software Foundation; either version 2 of the License,
11 or (at your option) any later version.
12
13 Tremulous is distributed in the hope that it will be
14 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with Tremulous; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
21 ===========================================================================
22 */
23
24 /*****************************************************************************
25 * name: be_aas_route.c
26 *
27 * desc: AAS
28 *
29 * $Archive: /MissionPack/code/botlib/be_aas_route.c $
30 *
31 *****************************************************************************/
32
33 #include "../qcommon/q_shared.h"
34 #include "l_utils.h"
35 #include "l_memory.h"
36 #include "l_log.h"
37 #include "l_crc.h"
38 #include "l_libvar.h"
39 #include "l_script.h"
40 #include "l_precomp.h"
41 #include "l_struct.h"
42 #include "aasfile.h"
43 #include "botlib.h"
44 #include "be_aas.h"
45 #include "be_aas_funcs.h"
46 #include "be_interface.h"
47 #include "be_aas_def.h"
48
49 #define ROUTING_DEBUG
50
51 //travel time in hundreths of a second = distance * 100 / speed
52 #define DISTANCEFACTOR_CROUCH 1.3f //crouch speed = 100
53 #define DISTANCEFACTOR_SWIM 1 //should be 0.66, swim speed = 150
54 #define DISTANCEFACTOR_WALK 0.33f //walk speed = 300
55
56 //cache refresh time
57 #define CACHE_REFRESHTIME 15.0f //15 seconds refresh time
58
59 //maximum number of routing updates each frame
60 #define MAX_FRAMEROUTINGUPDATES 10
61
62
63 /*
64
65 area routing cache:
66 stores the distances within one cluster to a specific goal area
67 this goal area is in this same cluster and could be a cluster portal
68 for every cluster there's a list with routing cache for every area
69 in that cluster (including the portals of that cluster)
70 area cache stores aasworld.clusters[?].numreachabilityareas travel times
71
72 portal routing cache:
73 stores the distances of all portals to a specific goal area
74 this goal area could be in any cluster and could also be a cluster portal
75 for every area (aasworld.numareas) the portal cache stores
76 aasworld.numportals travel times
77
78 */
79
80 #ifdef ROUTING_DEBUG
81 int numareacacheupdates;
82 int numportalcacheupdates;
83 #endif //ROUTING_DEBUG
84
85 int routingcachesize;
86 int max_routingcachesize;
87
88 //===========================================================================
89 //
90 // Parameter: -
91 // Returns: -
92 // Changes Globals: -
93 //===========================================================================
94 #ifdef ROUTING_DEBUG
AAS_RoutingInfo(void)95 void AAS_RoutingInfo(void)
96 {
97 botimport.Print(PRT_MESSAGE, "%d area cache updates\n", numareacacheupdates);
98 botimport.Print(PRT_MESSAGE, "%d portal cache updates\n", numportalcacheupdates);
99 botimport.Print(PRT_MESSAGE, "%d bytes routing cache\n", routingcachesize);
100 } //end of the function AAS_RoutingInfo
101 #endif //ROUTING_DEBUG
102 //===========================================================================
103 // returns the number of the area in the cluster
104 // assumes the given area is in the given cluster or a portal of the cluster
105 //
106 // Parameter: -
107 // Returns: -
108 // Changes Globals: -
109 //===========================================================================
AAS_ClusterAreaNum(int cluster,int areanum)110 ID_INLINE int AAS_ClusterAreaNum(int cluster, int areanum)
111 {
112 int side, areacluster;
113
114 areacluster = aasworld.areasettings[areanum].cluster;
115 if (areacluster > 0) return aasworld.areasettings[areanum].clusterareanum;
116 else
117 {
118 /*#ifdef ROUTING_DEBUG
119 if (aasworld.portals[-areacluster].frontcluster != cluster &&
120 aasworld.portals[-areacluster].backcluster != cluster)
121 {
122 botimport.Print(PRT_ERROR, "portal %d: does not belong to cluster %d\n"
123 , -areacluster, cluster);
124 } //end if
125 #endif //ROUTING_DEBUG*/
126 side = aasworld.portals[-areacluster].frontcluster != cluster;
127 return aasworld.portals[-areacluster].clusterareanum[side];
128 } //end else
129 } //end of the function AAS_ClusterAreaNum
130 //===========================================================================
131 //
132 // Parameter: -
133 // Returns: -
134 // Changes Globals: -
135 //===========================================================================
AAS_InitTravelFlagFromType(void)136 void AAS_InitTravelFlagFromType(void)
137 {
138 int i;
139
140 for (i = 0; i < MAX_TRAVELTYPES; i++)
141 {
142 aasworld.travelflagfortype[i] = TFL_INVALID;
143 } //end for
144 aasworld.travelflagfortype[TRAVEL_INVALID] = TFL_INVALID;
145 aasworld.travelflagfortype[TRAVEL_WALK] = TFL_WALK;
146 aasworld.travelflagfortype[TRAVEL_CROUCH] = TFL_CROUCH;
147 aasworld.travelflagfortype[TRAVEL_BARRIERJUMP] = TFL_BARRIERJUMP;
148 aasworld.travelflagfortype[TRAVEL_JUMP] = TFL_JUMP;
149 aasworld.travelflagfortype[TRAVEL_LADDER] = TFL_LADDER;
150 aasworld.travelflagfortype[TRAVEL_WALKOFFLEDGE] = TFL_WALKOFFLEDGE;
151 aasworld.travelflagfortype[TRAVEL_SWIM] = TFL_SWIM;
152 aasworld.travelflagfortype[TRAVEL_WATERJUMP] = TFL_WATERJUMP;
153 aasworld.travelflagfortype[TRAVEL_TELEPORT] = TFL_TELEPORT;
154 aasworld.travelflagfortype[TRAVEL_ELEVATOR] = TFL_ELEVATOR;
155 aasworld.travelflagfortype[TRAVEL_ROCKETJUMP] = TFL_ROCKETJUMP;
156 aasworld.travelflagfortype[TRAVEL_BFGJUMP] = TFL_BFGJUMP;
157 aasworld.travelflagfortype[TRAVEL_GRAPPLEHOOK] = TFL_GRAPPLEHOOK;
158 aasworld.travelflagfortype[TRAVEL_DOUBLEJUMP] = TFL_DOUBLEJUMP;
159 aasworld.travelflagfortype[TRAVEL_RAMPJUMP] = TFL_RAMPJUMP;
160 aasworld.travelflagfortype[TRAVEL_STRAFEJUMP] = TFL_STRAFEJUMP;
161 aasworld.travelflagfortype[TRAVEL_JUMPPAD] = TFL_JUMPPAD;
162 aasworld.travelflagfortype[TRAVEL_FUNCBOB] = TFL_FUNCBOB;
163 } //end of the function AAS_InitTravelFlagFromType
164 //===========================================================================
165 //
166 // Parameter: -
167 // Returns: -
168 // Changes Globals: -
169 //===========================================================================
AAS_TravelFlagForType_inline(int traveltype)170 ID_INLINE int AAS_TravelFlagForType_inline(int traveltype)
171 {
172 int tfl;
173
174 tfl = 0;
175 if (tfl & TRAVELFLAG_NOTTEAM1)
176 tfl |= TFL_NOTTEAM1;
177 if (tfl & TRAVELFLAG_NOTTEAM2)
178 tfl |= TFL_NOTTEAM2;
179 traveltype &= TRAVELTYPE_MASK;
180 if (traveltype < 0 || traveltype >= MAX_TRAVELTYPES)
181 return TFL_INVALID;
182 tfl |= aasworld.travelflagfortype[traveltype];
183 return tfl;
184 } //end of the function AAS_TravelFlagForType_inline
185 //===========================================================================
186 //
187 // Parameter: -
188 // Returns: -
189 // Changes Globals: -
190 //===========================================================================
AAS_TravelFlagForType(int traveltype)191 int AAS_TravelFlagForType(int traveltype)
192 {
193 return AAS_TravelFlagForType_inline(traveltype);
194 } //end of the function AAS_TravelFlagForType_inline
195 //===========================================================================
196 //
197 // Parameter: -
198 // Returns: -
199 // Changes Globals: -
200 //===========================================================================
AAS_UnlinkCache(aas_routingcache_t * cache)201 void AAS_UnlinkCache(aas_routingcache_t *cache)
202 {
203 if (cache->time_next) cache->time_next->time_prev = cache->time_prev;
204 else aasworld.newestcache = cache->time_prev;
205 if (cache->time_prev) cache->time_prev->time_next = cache->time_next;
206 else aasworld.oldestcache = cache->time_next;
207 cache->time_next = NULL;
208 cache->time_prev = NULL;
209 } //end of the function AAS_UnlinkCache
210 //===========================================================================
211 //
212 // Parameter: -
213 // Returns: -
214 // Changes Globals: -
215 //===========================================================================
AAS_LinkCache(aas_routingcache_t * cache)216 void AAS_LinkCache(aas_routingcache_t *cache)
217 {
218 if (aasworld.newestcache)
219 {
220 aasworld.newestcache->time_next = cache;
221 cache->time_prev = aasworld.newestcache;
222 } //end if
223 else
224 {
225 aasworld.oldestcache = cache;
226 cache->time_prev = NULL;
227 } //end else
228 cache->time_next = NULL;
229 aasworld.newestcache = cache;
230 } //end of the function AAS_LinkCache
231 //===========================================================================
232 //
233 // Parameter: -
234 // Returns: -
235 // Changes Globals: -
236 //===========================================================================
AAS_FreeRoutingCache(aas_routingcache_t * cache)237 void AAS_FreeRoutingCache(aas_routingcache_t *cache)
238 {
239 AAS_UnlinkCache(cache);
240 routingcachesize -= cache->size;
241 FreeMemory(cache);
242 } //end of the function AAS_FreeRoutingCache
243 //===========================================================================
244 //
245 // Parameter: -
246 // Returns: -
247 // Changes Globals: -
248 //===========================================================================
AAS_RemoveRoutingCacheInCluster(int clusternum)249 void AAS_RemoveRoutingCacheInCluster( int clusternum )
250 {
251 int i;
252 aas_routingcache_t *cache, *nextcache;
253 aas_cluster_t *cluster;
254
255 if (!aasworld.clusterareacache)
256 return;
257 cluster = &aasworld.clusters[clusternum];
258 for (i = 0; i < cluster->numareas; i++)
259 {
260 for (cache = aasworld.clusterareacache[clusternum][i]; cache; cache = nextcache)
261 {
262 nextcache = cache->next;
263 AAS_FreeRoutingCache(cache);
264 } //end for
265 aasworld.clusterareacache[clusternum][i] = NULL;
266 } //end for
267 } //end of the function AAS_RemoveRoutingCacheInCluster
268 //===========================================================================
269 //
270 // Parameter: -
271 // Returns: -
272 // Changes Globals: -
273 //===========================================================================
AAS_RemoveRoutingCacheUsingArea(int areanum)274 void AAS_RemoveRoutingCacheUsingArea( int areanum )
275 {
276 int i, clusternum;
277 aas_routingcache_t *cache, *nextcache;
278
279 clusternum = aasworld.areasettings[areanum].cluster;
280 if (clusternum > 0)
281 {
282 //remove all the cache in the cluster the area is in
283 AAS_RemoveRoutingCacheInCluster( clusternum );
284 } //end if
285 else
286 {
287 // if this is a portal remove all cache in both the front and back cluster
288 AAS_RemoveRoutingCacheInCluster( aasworld.portals[-clusternum].frontcluster );
289 AAS_RemoveRoutingCacheInCluster( aasworld.portals[-clusternum].backcluster );
290 } //end else
291 // remove all portal cache
292 for (i = 0; i < aasworld.numareas; i++)
293 {
294 //refresh portal cache
295 for (cache = aasworld.portalcache[i]; cache; cache = nextcache)
296 {
297 nextcache = cache->next;
298 AAS_FreeRoutingCache(cache);
299 } //end for
300 aasworld.portalcache[i] = NULL;
301 } //end for
302 } //end of the function AAS_RemoveRoutingCacheUsingArea
303 //===========================================================================
304 //
305 // Parameter: -
306 // Returns: -
307 // Changes Globals: -
308 //===========================================================================
AAS_EnableRoutingArea(int areanum,int enable)309 int AAS_EnableRoutingArea(int areanum, int enable)
310 {
311 int flags;
312
313 if (areanum <= 0 || areanum >= aasworld.numareas)
314 {
315 if (bot_developer)
316 {
317 botimport.Print(PRT_ERROR, "AAS_EnableRoutingArea: areanum %d out of range\n", areanum);
318 } //end if
319 return 0;
320 } //end if
321 flags = aasworld.areasettings[areanum].areaflags & AREA_DISABLED;
322 if (enable < 0)
323 return !flags;
324
325 if (enable)
326 aasworld.areasettings[areanum].areaflags &= ~AREA_DISABLED;
327 else
328 aasworld.areasettings[areanum].areaflags |= AREA_DISABLED;
329 // if the status of the area changed
330 if ( (flags & AREA_DISABLED) != (aasworld.areasettings[areanum].areaflags & AREA_DISABLED) )
331 {
332 //remove all routing cache involving this area
333 AAS_RemoveRoutingCacheUsingArea( areanum );
334 } //end if
335 return !flags;
336 } //end of the function AAS_EnableRoutingArea
337 //===========================================================================
338 //
339 // Parameter: -
340 // Returns: -
341 // Changes Globals: -
342 //===========================================================================
AAS_RoutingTime(void)343 ID_INLINE float AAS_RoutingTime(void)
344 {
345 return AAS_Time();
346 } //end of the function AAS_RoutingTime
347 //===========================================================================
348 //
349 // Parameter: -
350 // Returns: -
351 // Changes Globals: -
352 //===========================================================================
AAS_GetAreaContentsTravelFlags(int areanum)353 int AAS_GetAreaContentsTravelFlags(int areanum)
354 {
355 int contents, tfl;
356
357 contents = aasworld.areasettings[areanum].contents;
358 tfl = 0;
359 if (contents & AREACONTENTS_WATER)
360 tfl |= TFL_WATER;
361 else if (contents & AREACONTENTS_SLIME)
362 tfl |= TFL_SLIME;
363 else if (contents & AREACONTENTS_LAVA)
364 tfl |= TFL_LAVA;
365 else
366 tfl |= TFL_AIR;
367 if (contents & AREACONTENTS_DONOTENTER)
368 tfl |= TFL_DONOTENTER;
369 if (contents & AREACONTENTS_NOTTEAM1)
370 tfl |= TFL_NOTTEAM1;
371 if (contents & AREACONTENTS_NOTTEAM2)
372 tfl |= TFL_NOTTEAM2;
373 if (aasworld.areasettings[areanum].areaflags & AREA_BRIDGE)
374 tfl |= TFL_BRIDGE;
375 return tfl;
376 } //end of the function AAS_GetAreaContentsTravelFlags
377 //===========================================================================
378 //
379 // Parameter: -
380 // Returns: -
381 // Changes Globals: -
382 //===========================================================================
AAS_AreaContentsTravelFlags_inline(int areanum)383 ID_INLINE int AAS_AreaContentsTravelFlags_inline(int areanum)
384 {
385 return aasworld.areacontentstravelflags[areanum];
386 } //end of the function AAS_AreaContentsTravelFlags
387 //===========================================================================
388 //
389 // Parameter: -
390 // Returns: -
391 // Changes Globals: -
392 //===========================================================================
AAS_AreaContentsTravelFlags(int areanum)393 int AAS_AreaContentsTravelFlags(int areanum)
394 {
395 return aasworld.areacontentstravelflags[areanum];
396 } //end of the function AAS_AreaContentsTravelFlags
397 //===========================================================================
398 //
399 // Parameter: -
400 // Returns: -
401 // Changes Globals: -
402 //===========================================================================
AAS_InitAreaContentsTravelFlags(void)403 void AAS_InitAreaContentsTravelFlags(void)
404 {
405 int i;
406
407 if (aasworld.areacontentstravelflags) FreeMemory(aasworld.areacontentstravelflags);
408 aasworld.areacontentstravelflags = (int *) GetClearedMemory(aasworld.numareas * sizeof(int));
409 //
410 for (i = 0; i < aasworld.numareas; i++) {
411 aasworld.areacontentstravelflags[i] = AAS_GetAreaContentsTravelFlags(i);
412 }
413 } //end of the function AAS_InitAreaContentsTravelFlags
414 //===========================================================================
415 //
416 // Parameter: -
417 // Returns: -
418 // Changes Globals: -
419 //===========================================================================
AAS_CreateReversedReachability(void)420 void AAS_CreateReversedReachability(void)
421 {
422 int i, n;
423 aas_reversedlink_t *revlink;
424 aas_reachability_t *reach;
425 aas_areasettings_t *settings;
426 char *ptr;
427 #ifdef DEBUG
428 int starttime;
429
430 starttime = Sys_MilliSeconds();
431 #endif
432 //free reversed links that have already been created
433 if (aasworld.reversedreachability) FreeMemory(aasworld.reversedreachability);
434 //allocate memory for the reversed reachability links
435 ptr = (char *) GetClearedMemory(aasworld.numareas * sizeof(aas_reversedreachability_t) +
436 aasworld.reachabilitysize * sizeof(aas_reversedlink_t));
437 //
438 aasworld.reversedreachability = (aas_reversedreachability_t *) ptr;
439 //pointer to the memory for the reversed links
440 ptr += aasworld.numareas * sizeof(aas_reversedreachability_t);
441 //check all reachabilities of all areas
442 for (i = 1; i < aasworld.numareas; i++)
443 {
444 //settings of the area
445 settings = &aasworld.areasettings[i];
446 //
447 if (settings->numreachableareas >= 128)
448 botimport.Print(PRT_WARNING, "area %d has more than 128 reachabilities\n", i);
449 //create reversed links for the reachabilities
450 for (n = 0; n < settings->numreachableareas && n < 128; n++)
451 {
452 //reachability link
453 reach = &aasworld.reachability[settings->firstreachablearea + n];
454 //
455 revlink = (aas_reversedlink_t *) ptr;
456 ptr += sizeof(aas_reversedlink_t);
457 //
458 revlink->areanum = i;
459 revlink->linknum = settings->firstreachablearea + n;
460 revlink->next = aasworld.reversedreachability[reach->areanum].first;
461 aasworld.reversedreachability[reach->areanum].first = revlink;
462 aasworld.reversedreachability[reach->areanum].numlinks++;
463 } //end for
464 } //end for
465 #ifdef DEBUG
466 botimport.Print(PRT_MESSAGE, "reversed reachability %d msec\n", Sys_MilliSeconds() - starttime);
467 #endif
468 } //end of the function AAS_CreateReversedReachability
469 //===========================================================================
470 //
471 // Parameter: -
472 // Returns: -
473 // Changes Globals: -
474 //===========================================================================
AAS_AreaTravelTime(int areanum,vec3_t start,vec3_t end)475 unsigned short int AAS_AreaTravelTime(int areanum, vec3_t start, vec3_t end)
476 {
477 int intdist;
478 float dist;
479 vec3_t dir;
480
481 VectorSubtract(start, end, dir);
482 dist = VectorLength(dir);
483 //if crouch only area
484 if (AAS_AreaCrouch(areanum)) dist *= DISTANCEFACTOR_CROUCH;
485 //if swim area
486 else if (AAS_AreaSwim(areanum)) dist *= DISTANCEFACTOR_SWIM;
487 //normal walk area
488 else dist *= DISTANCEFACTOR_WALK;
489 //
490 intdist = (int) dist;
491 //make sure the distance isn't zero
492 if (intdist <= 0) intdist = 1;
493 return intdist;
494 } //end of the function AAS_AreaTravelTime
495 //===========================================================================
496 //
497 // Parameter: -
498 // Returns: -
499 // Changes Globals: -
500 //===========================================================================
AAS_CalculateAreaTravelTimes(void)501 void AAS_CalculateAreaTravelTimes(void)
502 {
503 int i, l, n, size;
504 char *ptr;
505 vec3_t end;
506 aas_reversedreachability_t *revreach;
507 aas_reversedlink_t *revlink;
508 aas_reachability_t *reach;
509 aas_areasettings_t *settings;
510 int starttime;
511
512 starttime = Sys_MilliSeconds();
513 //if there are still area travel times, free the memory
514 if (aasworld.areatraveltimes) FreeMemory(aasworld.areatraveltimes);
515 //get the total size of all the area travel times
516 size = aasworld.numareas * sizeof(unsigned short **);
517 for (i = 0; i < aasworld.numareas; i++)
518 {
519 revreach = &aasworld.reversedreachability[i];
520 //settings of the area
521 settings = &aasworld.areasettings[i];
522 //
523 size += settings->numreachableareas * sizeof(unsigned short *);
524 //
525 size += settings->numreachableareas *
526 PAD(revreach->numlinks, sizeof(long)) * sizeof(unsigned short);
527 } //end for
528 //allocate memory for the area travel times
529 ptr = (char *) GetClearedMemory(size);
530 aasworld.areatraveltimes = (unsigned short ***) ptr;
531 ptr += aasworld.numareas * sizeof(unsigned short **);
532 //calcluate the travel times for all the areas
533 for (i = 0; i < aasworld.numareas; i++)
534 {
535 //reversed reachabilities of this area
536 revreach = &aasworld.reversedreachability[i];
537 //settings of the area
538 settings = &aasworld.areasettings[i];
539 //
540 aasworld.areatraveltimes[i] = (unsigned short **) ptr;
541 ptr += settings->numreachableareas * sizeof(unsigned short *);
542 //
543 for (l = 0; l < settings->numreachableareas; l++)
544 {
545 aasworld.areatraveltimes[i][l] = (unsigned short *) ptr;
546 ptr += PAD(revreach->numlinks, sizeof(long)) * sizeof(unsigned short);
547 //reachability link
548 reach = &aasworld.reachability[settings->firstreachablearea + l];
549 //
550 for (n = 0, revlink = revreach->first; revlink; revlink = revlink->next, n++)
551 {
552 VectorCopy(aasworld.reachability[revlink->linknum].end, end);
553 //
554 aasworld.areatraveltimes[i][l][n] = AAS_AreaTravelTime(i, end, reach->start);
555 } //end for
556 } //end for
557 } //end for
558 #ifdef DEBUG
559 botimport.Print(PRT_MESSAGE, "area travel times %d msec\n", Sys_MilliSeconds() - starttime);
560 #endif
561 } //end of the function AAS_CalculateAreaTravelTimes
562 //===========================================================================
563 //
564 // Parameter: -
565 // Returns: -
566 // Changes Globals: -
567 //===========================================================================
AAS_PortalMaxTravelTime(int portalnum)568 int AAS_PortalMaxTravelTime(int portalnum)
569 {
570 int l, n, t, maxt;
571 aas_portal_t *portal;
572 aas_reversedreachability_t *revreach;
573 aas_reversedlink_t *revlink;
574 aas_areasettings_t *settings;
575
576 portal = &aasworld.portals[portalnum];
577 //reversed reachabilities of this portal area
578 revreach = &aasworld.reversedreachability[portal->areanum];
579 //settings of the portal area
580 settings = &aasworld.areasettings[portal->areanum];
581 //
582 maxt = 0;
583 for (l = 0; l < settings->numreachableareas; l++)
584 {
585 for (n = 0, revlink = revreach->first; revlink; revlink = revlink->next, n++)
586 {
587 t = aasworld.areatraveltimes[portal->areanum][l][n];
588 if (t > maxt)
589 {
590 maxt = t;
591 } //end if
592 } //end for
593 } //end for
594 return maxt;
595 } //end of the function AAS_PortalMaxTravelTime
596 //===========================================================================
597 //
598 // Parameter: -
599 // Returns: -
600 // Changes Globals: -
601 //===========================================================================
AAS_InitPortalMaxTravelTimes(void)602 void AAS_InitPortalMaxTravelTimes(void)
603 {
604 int i;
605
606 if (aasworld.portalmaxtraveltimes) FreeMemory(aasworld.portalmaxtraveltimes);
607
608 aasworld.portalmaxtraveltimes = (int *) GetClearedMemory(aasworld.numportals * sizeof(int));
609
610 for (i = 0; i < aasworld.numportals; i++)
611 {
612 aasworld.portalmaxtraveltimes[i] = AAS_PortalMaxTravelTime(i);
613 //botimport.Print(PRT_MESSAGE, "portal %d max tt = %d\n", i, aasworld.portalmaxtraveltimes[i]);
614 } //end for
615 } //end of the function AAS_InitPortalMaxTravelTimes
616 //===========================================================================
617 //
618 // Parameter: -
619 // Returns: -
620 // Changes Globals: -
621 //===========================================================================
622 /*
623 int AAS_FreeOldestCache(void)
624 {
625 int i, j, bestcluster, bestarea, freed;
626 float besttime;
627 aas_routingcache_t *cache, *bestcache;
628
629 freed = qfalse;
630 besttime = 999999999;
631 bestcache = NULL;
632 bestcluster = 0;
633 bestarea = 0;
634 //refresh cluster cache
635 for (i = 0; i < aasworld.numclusters; i++)
636 {
637 for (j = 0; j < aasworld.clusters[i].numareas; j++)
638 {
639 for (cache = aasworld.clusterareacache[i][j]; cache; cache = cache->next)
640 {
641 //never remove cache leading towards a portal
642 if (aasworld.areasettings[cache->areanum].cluster < 0) continue;
643 //if this cache is older than the cache we found so far
644 if (cache->time < besttime)
645 {
646 bestcache = cache;
647 bestcluster = i;
648 bestarea = j;
649 besttime = cache->time;
650 } //end if
651 } //end for
652 } //end for
653 } //end for
654 if (bestcache)
655 {
656 cache = bestcache;
657 if (cache->prev) cache->prev->next = cache->next;
658 else aasworld.clusterareacache[bestcluster][bestarea] = cache->next;
659 if (cache->next) cache->next->prev = cache->prev;
660 AAS_FreeRoutingCache(cache);
661 freed = qtrue;
662 } //end if
663 besttime = 999999999;
664 bestcache = NULL;
665 bestarea = 0;
666 for (i = 0; i < aasworld.numareas; i++)
667 {
668 //refresh portal cache
669 for (cache = aasworld.portalcache[i]; cache; cache = cache->next)
670 {
671 if (cache->time < besttime)
672 {
673 bestcache = cache;
674 bestarea = i;
675 besttime = cache->time;
676 } //end if
677 } //end for
678 } //end for
679 if (bestcache)
680 {
681 cache = bestcache;
682 if (cache->prev) cache->prev->next = cache->next;
683 else aasworld.portalcache[bestarea] = cache->next;
684 if (cache->next) cache->next->prev = cache->prev;
685 AAS_FreeRoutingCache(cache);
686 freed = qtrue;
687 } //end if
688 return freed;
689 } //end of the function AAS_FreeOldestCache
690 */
691 //===========================================================================
692 //
693 // Parameter: -
694 // Returns: -
695 // Changes Globals: -
696 //===========================================================================
AAS_FreeOldestCache(void)697 int AAS_FreeOldestCache(void)
698 {
699 int clusterareanum;
700 aas_routingcache_t *cache;
701
702 for (cache = aasworld.oldestcache; cache; cache = cache->time_next) {
703 // never free area cache leading towards a portal
704 if (cache->type == CACHETYPE_AREA && aasworld.areasettings[cache->areanum].cluster < 0) {
705 continue;
706 }
707 break;
708 }
709 if (cache) {
710 // unlink the cache
711 if (cache->type == CACHETYPE_AREA) {
712 //number of the area in the cluster
713 clusterareanum = AAS_ClusterAreaNum(cache->cluster, cache->areanum);
714 // unlink from cluster area cache
715 if (cache->prev) cache->prev->next = cache->next;
716 else aasworld.clusterareacache[cache->cluster][clusterareanum] = cache->next;
717 if (cache->next) cache->next->prev = cache->prev;
718 }
719 else {
720 // unlink from portal cache
721 if (cache->prev) cache->prev->next = cache->next;
722 else aasworld.portalcache[cache->areanum] = cache->next;
723 if (cache->next) cache->next->prev = cache->prev;
724 }
725 AAS_FreeRoutingCache(cache);
726 return qtrue;
727 }
728 return qfalse;
729 } //end of the function AAS_FreeOldestCache
730 //===========================================================================
731 //
732 // Parameter: -
733 // Returns: -
734 // Changes Globals: -
735 //===========================================================================
AAS_AllocRoutingCache(int numtraveltimes)736 aas_routingcache_t *AAS_AllocRoutingCache(int numtraveltimes)
737 {
738 aas_routingcache_t *cache;
739 int size;
740
741 //
742 size = sizeof(aas_routingcache_t)
743 + numtraveltimes * sizeof(unsigned short int)
744 + numtraveltimes * sizeof(unsigned char);
745 //
746 routingcachesize += size;
747 //
748 cache = (aas_routingcache_t *) GetClearedMemory(size);
749 cache->reachabilities = (unsigned char *) cache + sizeof(aas_routingcache_t)
750 + numtraveltimes * sizeof(unsigned short int);
751 cache->size = size;
752 return cache;
753 } //end of the function AAS_AllocRoutingCache
754 //===========================================================================
755 //
756 // Parameter: -
757 // Returns: -
758 // Changes Globals: -
759 //===========================================================================
AAS_FreeAllClusterAreaCache(void)760 void AAS_FreeAllClusterAreaCache(void)
761 {
762 int i, j;
763 aas_routingcache_t *cache, *nextcache;
764 aas_cluster_t *cluster;
765
766 //free all cluster cache if existing
767 if (!aasworld.clusterareacache) return;
768 //free caches
769 for (i = 0; i < aasworld.numclusters; i++)
770 {
771 cluster = &aasworld.clusters[i];
772 for (j = 0; j < cluster->numareas; j++)
773 {
774 for (cache = aasworld.clusterareacache[i][j]; cache; cache = nextcache)
775 {
776 nextcache = cache->next;
777 AAS_FreeRoutingCache(cache);
778 } //end for
779 aasworld.clusterareacache[i][j] = NULL;
780 } //end for
781 } //end for
782 //free the cluster cache array
783 FreeMemory(aasworld.clusterareacache);
784 aasworld.clusterareacache = NULL;
785 } //end of the function AAS_FreeAllClusterAreaCache
786 //===========================================================================
787 //
788 // Parameter: -
789 // Returns: -
790 // Changes Globals: -
791 //===========================================================================
AAS_InitClusterAreaCache(void)792 void AAS_InitClusterAreaCache(void)
793 {
794 int i, size;
795 char *ptr;
796
797 //
798 for (size = 0, i = 0; i < aasworld.numclusters; i++)
799 {
800 size += aasworld.clusters[i].numareas;
801 } //end for
802 //two dimensional array with pointers for every cluster to routing cache
803 //for every area in that cluster
804 ptr = (char *) GetClearedMemory(
805 aasworld.numclusters * sizeof(aas_routingcache_t **) +
806 size * sizeof(aas_routingcache_t *));
807 aasworld.clusterareacache = (aas_routingcache_t ***) ptr;
808 ptr += aasworld.numclusters * sizeof(aas_routingcache_t **);
809 for (i = 0; i < aasworld.numclusters; i++)
810 {
811 aasworld.clusterareacache[i] = (aas_routingcache_t **) ptr;
812 ptr += aasworld.clusters[i].numareas * sizeof(aas_routingcache_t *);
813 } //end for
814 } //end of the function AAS_InitClusterAreaCache
815 //===========================================================================
816 //
817 // Parameter: -
818 // Returns: -
819 // Changes Globals: -
820 //===========================================================================
AAS_FreeAllPortalCache(void)821 void AAS_FreeAllPortalCache(void)
822 {
823 int i;
824 aas_routingcache_t *cache, *nextcache;
825
826 //free all portal cache if existing
827 if (!aasworld.portalcache) return;
828 //free portal caches
829 for (i = 0; i < aasworld.numareas; i++)
830 {
831 for (cache = aasworld.portalcache[i]; cache; cache = nextcache)
832 {
833 nextcache = cache->next;
834 AAS_FreeRoutingCache(cache);
835 } //end for
836 aasworld.portalcache[i] = NULL;
837 } //end for
838 FreeMemory(aasworld.portalcache);
839 aasworld.portalcache = NULL;
840 } //end of the function AAS_FreeAllPortalCache
841 //===========================================================================
842 //
843 // Parameter: -
844 // Returns: -
845 // Changes Globals: -
846 //===========================================================================
AAS_InitPortalCache(void)847 void AAS_InitPortalCache(void)
848 {
849 //
850 aasworld.portalcache = (aas_routingcache_t **) GetClearedMemory(
851 aasworld.numareas * sizeof(aas_routingcache_t *));
852 } //end of the function AAS_InitPortalCache
853 //===========================================================================
854 //
855 // Parameter: -
856 // Returns: -
857 // Changes Globals: -
858 //===========================================================================
AAS_InitRoutingUpdate(void)859 void AAS_InitRoutingUpdate(void)
860 {
861 int i, maxreachabilityareas;
862
863 //free routing update fields if already existing
864 if (aasworld.areaupdate) FreeMemory(aasworld.areaupdate);
865 //
866 maxreachabilityareas = 0;
867 for (i = 0; i < aasworld.numclusters; i++)
868 {
869 if (aasworld.clusters[i].numreachabilityareas > maxreachabilityareas)
870 {
871 maxreachabilityareas = aasworld.clusters[i].numreachabilityareas;
872 } //end if
873 } //end for
874 //allocate memory for the routing update fields
875 aasworld.areaupdate = (aas_routingupdate_t *) GetClearedMemory(
876 maxreachabilityareas * sizeof(aas_routingupdate_t));
877 //
878 if (aasworld.portalupdate) FreeMemory(aasworld.portalupdate);
879 //allocate memory for the portal update fields
880 aasworld.portalupdate = (aas_routingupdate_t *) GetClearedMemory(
881 (aasworld.numportals+1) * sizeof(aas_routingupdate_t));
882 } //end of the function AAS_InitRoutingUpdate
883 //===========================================================================
884 //
885 // Parameter: -
886 // Returns: -
887 // Changes Globals: -
888 //===========================================================================
AAS_CreateAllRoutingCache(void)889 void AAS_CreateAllRoutingCache(void)
890 {
891 int i, j, t;
892
893 aasworld.initialized = qtrue;
894 botimport.Print(PRT_MESSAGE, "AAS_CreateAllRoutingCache\n");
895 for (i = 1; i < aasworld.numareas; i++)
896 {
897 if (!AAS_AreaReachability(i)) continue;
898 for (j = 1; j < aasworld.numareas; j++)
899 {
900 if (i == j) continue;
901 if (!AAS_AreaReachability(j)) continue;
902 t = AAS_AreaTravelTimeToGoalArea(i, aasworld.areas[i].center, j, TFL_DEFAULT);
903 //Log_Write("traveltime from %d to %d is %d", i, j, t);
904 } //end for
905 } //end for
906 aasworld.initialized = qfalse;
907 } //end of the function AAS_CreateAllRoutingCache
908 //===========================================================================
909 //
910 // Parameter: -
911 // Returns: -
912 // Changes Globals: -
913 //===========================================================================
914
915 //the route cache header
916 //this header is followed by numportalcache + numareacache aas_routingcache_t
917 //structures that store routing cache
918 typedef struct routecacheheader_s
919 {
920 int ident;
921 int version;
922 int numareas;
923 int numclusters;
924 int areacrc;
925 int clustercrc;
926 int numportalcache;
927 int numareacache;
928 } routecacheheader_t;
929
930 #define RCID (('C'<<24)+('R'<<16)+('E'<<8)+'M')
931 #define RCVERSION 2
932
933 //void AAS_DecompressVis(byte *in, int numareas, byte *decompressed);
934 //int AAS_CompressVis(byte *vis, int numareas, byte *dest);
935
AAS_WriteRouteCache(void)936 void AAS_WriteRouteCache(void)
937 {
938 int i, j, numportalcache, numareacache, totalsize;
939 aas_routingcache_t *cache;
940 aas_cluster_t *cluster;
941 fileHandle_t fp;
942 char filename[MAX_QPATH];
943 routecacheheader_t routecacheheader;
944
945 numportalcache = 0;
946 for (i = 0; i < aasworld.numareas; i++)
947 {
948 for (cache = aasworld.portalcache[i]; cache; cache = cache->next)
949 {
950 numportalcache++;
951 } //end for
952 } //end for
953 numareacache = 0;
954 for (i = 0; i < aasworld.numclusters; i++)
955 {
956 cluster = &aasworld.clusters[i];
957 for (j = 0; j < cluster->numareas; j++)
958 {
959 for (cache = aasworld.clusterareacache[i][j]; cache; cache = cache->next)
960 {
961 numareacache++;
962 } //end for
963 } //end for
964 } //end for
965 // open the file for writing
966 Com_sprintf(filename, MAX_QPATH, "maps/%s.rcd", aasworld.mapname);
967 botimport.FS_FOpenFile( filename, &fp, FS_WRITE );
968 if (!fp)
969 {
970 AAS_Error("Unable to open file: %s\n", filename);
971 return;
972 } //end if
973 //create the header
974 routecacheheader.ident = RCID;
975 routecacheheader.version = RCVERSION;
976 routecacheheader.numareas = aasworld.numareas;
977 routecacheheader.numclusters = aasworld.numclusters;
978 routecacheheader.areacrc = CRC_ProcessString( (unsigned char *)aasworld.areas, sizeof(aas_area_t) * aasworld.numareas );
979 routecacheheader.clustercrc = CRC_ProcessString( (unsigned char *)aasworld.clusters, sizeof(aas_cluster_t) * aasworld.numclusters );
980 routecacheheader.numportalcache = numportalcache;
981 routecacheheader.numareacache = numareacache;
982 //write the header
983 botimport.FS_Write(&routecacheheader, sizeof(routecacheheader_t), fp);
984 //
985 totalsize = 0;
986 //write all the cache
987 for (i = 0; i < aasworld.numareas; i++)
988 {
989 for (cache = aasworld.portalcache[i]; cache; cache = cache->next)
990 {
991 botimport.FS_Write(cache, cache->size, fp);
992 totalsize += cache->size;
993 } //end for
994 } //end for
995 for (i = 0; i < aasworld.numclusters; i++)
996 {
997 cluster = &aasworld.clusters[i];
998 for (j = 0; j < cluster->numareas; j++)
999 {
1000 for (cache = aasworld.clusterareacache[i][j]; cache; cache = cache->next)
1001 {
1002 botimport.FS_Write(cache, cache->size, fp);
1003 totalsize += cache->size;
1004 } //end for
1005 } //end for
1006 } //end for
1007 // write the visareas
1008 /*
1009 for (i = 0; i < aasworld.numareas; i++)
1010 {
1011 if (!aasworld.areavisibility[i]) {
1012 size = 0;
1013 botimport.FS_Write(&size, sizeof(int), fp);
1014 continue;
1015 }
1016 AAS_DecompressVis( aasworld.areavisibility[i], aasworld.numareas, aasworld.decompressedvis );
1017 size = AAS_CompressVis( aasworld.decompressedvis, aasworld.numareas, aasworld.decompressedvis );
1018 botimport.FS_Write(&size, sizeof(int), fp);
1019 botimport.FS_Write(aasworld.decompressedvis, size, fp);
1020 }
1021 */
1022 //
1023 botimport.FS_FCloseFile(fp);
1024 botimport.Print(PRT_MESSAGE, "\nroute cache written to %s\n", filename);
1025 botimport.Print(PRT_MESSAGE, "written %d bytes of routing cache\n", totalsize);
1026 } //end of the function AAS_WriteRouteCache
1027 //===========================================================================
1028 //
1029 // Parameter: -
1030 // Returns: -
1031 // Changes Globals: -
1032 //===========================================================================
AAS_ReadCache(fileHandle_t fp)1033 aas_routingcache_t *AAS_ReadCache(fileHandle_t fp)
1034 {
1035 int size;
1036 aas_routingcache_t *cache;
1037
1038 botimport.FS_Read(&size, sizeof(size), fp);
1039 cache = (aas_routingcache_t *) GetMemory(size);
1040 cache->size = size;
1041 botimport.FS_Read((unsigned char *)cache + sizeof(size), size - sizeof(size), fp);
1042 cache->reachabilities = (unsigned char *) cache + sizeof(aas_routingcache_t) - sizeof(unsigned short) +
1043 (size - sizeof(aas_routingcache_t) + sizeof(unsigned short)) / 3 * 2;
1044 return cache;
1045 } //end of the function AAS_ReadCache
1046 //===========================================================================
1047 //
1048 // Parameter: -
1049 // Returns: -
1050 // Changes Globals: -
1051 //===========================================================================
AAS_ReadRouteCache(void)1052 int AAS_ReadRouteCache(void)
1053 {
1054 int i, clusterareanum;//, size;
1055 fileHandle_t fp;
1056 char filename[MAX_QPATH];
1057 routecacheheader_t routecacheheader;
1058 aas_routingcache_t *cache;
1059
1060 Com_sprintf(filename, MAX_QPATH, "maps/%s.rcd", aasworld.mapname);
1061 botimport.FS_FOpenFile( filename, &fp, FS_READ );
1062 if (!fp)
1063 {
1064 return qfalse;
1065 } //end if
1066 botimport.FS_Read(&routecacheheader, sizeof(routecacheheader_t), fp );
1067 if (routecacheheader.ident != RCID)
1068 {
1069 AAS_Error("%s is not a route cache dump\n");
1070 return qfalse;
1071 } //end if
1072 if (routecacheheader.version != RCVERSION)
1073 {
1074 AAS_Error("route cache dump has wrong version %d, should be %d", routecacheheader.version, RCVERSION);
1075 return qfalse;
1076 } //end if
1077 if (routecacheheader.numareas != aasworld.numareas)
1078 {
1079 //AAS_Error("route cache dump has wrong number of areas\n");
1080 return qfalse;
1081 } //end if
1082 if (routecacheheader.numclusters != aasworld.numclusters)
1083 {
1084 //AAS_Error("route cache dump has wrong number of clusters\n");
1085 return qfalse;
1086 } //end if
1087 if (routecacheheader.areacrc !=
1088 CRC_ProcessString( (unsigned char *)aasworld.areas, sizeof(aas_area_t) * aasworld.numareas ))
1089 {
1090 //AAS_Error("route cache dump area CRC incorrect\n");
1091 return qfalse;
1092 } //end if
1093 if (routecacheheader.clustercrc !=
1094 CRC_ProcessString( (unsigned char *)aasworld.clusters, sizeof(aas_cluster_t) * aasworld.numclusters ))
1095 {
1096 //AAS_Error("route cache dump cluster CRC incorrect\n");
1097 return qfalse;
1098 } //end if
1099 //read all the portal cache
1100 for (i = 0; i < routecacheheader.numportalcache; i++)
1101 {
1102 cache = AAS_ReadCache(fp);
1103 cache->next = aasworld.portalcache[cache->areanum];
1104 cache->prev = NULL;
1105 if (aasworld.portalcache[cache->areanum])
1106 aasworld.portalcache[cache->areanum]->prev = cache;
1107 aasworld.portalcache[cache->areanum] = cache;
1108 } //end for
1109 //read all the cluster area cache
1110 for (i = 0; i < routecacheheader.numareacache; i++)
1111 {
1112 cache = AAS_ReadCache(fp);
1113 clusterareanum = AAS_ClusterAreaNum(cache->cluster, cache->areanum);
1114 cache->next = aasworld.clusterareacache[cache->cluster][clusterareanum];
1115 cache->prev = NULL;
1116 if (aasworld.clusterareacache[cache->cluster][clusterareanum])
1117 aasworld.clusterareacache[cache->cluster][clusterareanum]->prev = cache;
1118 aasworld.clusterareacache[cache->cluster][clusterareanum] = cache;
1119 } //end for
1120 // read the visareas
1121 /*
1122 aasworld.areavisibility = (byte **) GetClearedMemory(aasworld.numareas * sizeof(byte *));
1123 aasworld.decompressedvis = (byte *) GetClearedMemory(aasworld.numareas * sizeof(byte));
1124 for (i = 0; i < aasworld.numareas; i++)
1125 {
1126 botimport.FS_Read(&size, sizeof(size), fp );
1127 if (size) {
1128 aasworld.areavisibility[i] = (byte *) GetMemory(size);
1129 botimport.FS_Read(aasworld.areavisibility[i], size, fp );
1130 }
1131 }
1132 */
1133 //
1134 botimport.FS_FCloseFile(fp);
1135 return qtrue;
1136 } //end of the function AAS_ReadRouteCache
1137 //===========================================================================
1138 //
1139 // Parameter: -
1140 // Returns: -
1141 // Changes Globals: -
1142 //===========================================================================
1143 #define MAX_REACHABILITYPASSAREAS 32
1144
AAS_InitReachabilityAreas(void)1145 void AAS_InitReachabilityAreas(void)
1146 {
1147 int i, j, numareas, areas[MAX_REACHABILITYPASSAREAS];
1148 int numreachareas;
1149 aas_reachability_t *reach;
1150 vec3_t start, end;
1151
1152 if (aasworld.reachabilityareas)
1153 FreeMemory(aasworld.reachabilityareas);
1154 if (aasworld.reachabilityareaindex)
1155 FreeMemory(aasworld.reachabilityareaindex);
1156
1157 aasworld.reachabilityareas = (aas_reachabilityareas_t *)
1158 GetClearedMemory(aasworld.reachabilitysize * sizeof(aas_reachabilityareas_t));
1159 aasworld.reachabilityareaindex = (int *)
1160 GetClearedMemory(aasworld.reachabilitysize * MAX_REACHABILITYPASSAREAS * sizeof(int));
1161 numreachareas = 0;
1162 for (i = 0; i < aasworld.reachabilitysize; i++)
1163 {
1164 reach = &aasworld.reachability[i];
1165 numareas = 0;
1166 switch(reach->traveltype & TRAVELTYPE_MASK)
1167 {
1168 //trace areas from start to end
1169 case TRAVEL_BARRIERJUMP:
1170 case TRAVEL_WATERJUMP:
1171 VectorCopy(reach->start, end);
1172 end[2] = reach->end[2];
1173 numareas = AAS_TraceAreas(reach->start, end, areas, NULL, MAX_REACHABILITYPASSAREAS);
1174 break;
1175 case TRAVEL_WALKOFFLEDGE:
1176 VectorCopy(reach->end, start);
1177 start[2] = reach->start[2];
1178 numareas = AAS_TraceAreas(start, reach->end, areas, NULL, MAX_REACHABILITYPASSAREAS);
1179 break;
1180 case TRAVEL_GRAPPLEHOOK:
1181 numareas = AAS_TraceAreas(reach->start, reach->end, areas, NULL, MAX_REACHABILITYPASSAREAS);
1182 break;
1183
1184 //trace arch
1185 case TRAVEL_JUMP: break;
1186 case TRAVEL_ROCKETJUMP: break;
1187 case TRAVEL_BFGJUMP: break;
1188 case TRAVEL_JUMPPAD: break;
1189
1190 //trace from reach->start to entity center, along entity movement
1191 //and from entity center to reach->end
1192 case TRAVEL_ELEVATOR: break;
1193 case TRAVEL_FUNCBOB: break;
1194
1195 //no areas in between
1196 case TRAVEL_WALK: break;
1197 case TRAVEL_CROUCH: break;
1198 case TRAVEL_LADDER: break;
1199 case TRAVEL_SWIM: break;
1200 case TRAVEL_TELEPORT: break;
1201 default: break;
1202 } //end switch
1203 aasworld.reachabilityareas[i].firstarea = numreachareas;
1204 aasworld.reachabilityareas[i].numareas = numareas;
1205 for (j = 0; j < numareas; j++)
1206 {
1207 aasworld.reachabilityareaindex[numreachareas++] = areas[j];
1208 } //end for
1209 } //end for
1210 } //end of the function AAS_InitReachabilityAreas
1211 //===========================================================================
1212 //
1213 // Parameter: -
1214 // Returns: -
1215 // Changes Globals: -
1216 //===========================================================================
AAS_InitRouting(void)1217 void AAS_InitRouting(void)
1218 {
1219 AAS_InitTravelFlagFromType();
1220 //
1221 AAS_InitAreaContentsTravelFlags();
1222 //initialize the routing update fields
1223 AAS_InitRoutingUpdate();
1224 //create reversed reachability links used by the routing update algorithm
1225 AAS_CreateReversedReachability();
1226 //initialize the cluster cache
1227 AAS_InitClusterAreaCache();
1228 //initialize portal cache
1229 AAS_InitPortalCache();
1230 //initialize the area travel times
1231 AAS_CalculateAreaTravelTimes();
1232 //calculate the maximum travel times through portals
1233 AAS_InitPortalMaxTravelTimes();
1234 //get the areas reachabilities go through
1235 AAS_InitReachabilityAreas();
1236 //
1237 #ifdef ROUTING_DEBUG
1238 numareacacheupdates = 0;
1239 numportalcacheupdates = 0;
1240 #endif //ROUTING_DEBUG
1241 //
1242 routingcachesize = 0;
1243 max_routingcachesize = 1024 * (int) LibVarValue("max_routingcache", "4096");
1244 // read any routing cache if available
1245 AAS_ReadRouteCache();
1246 } //end of the function AAS_InitRouting
1247 //===========================================================================
1248 //
1249 // Parameter: -
1250 // Returns: -
1251 // Changes Globals: -
1252 //===========================================================================
AAS_FreeRoutingCaches(void)1253 void AAS_FreeRoutingCaches(void)
1254 {
1255 // free all the existing cluster area cache
1256 AAS_FreeAllClusterAreaCache();
1257 // free all the existing portal cache
1258 AAS_FreeAllPortalCache();
1259 // free cached travel times within areas
1260 if (aasworld.areatraveltimes) FreeMemory(aasworld.areatraveltimes);
1261 aasworld.areatraveltimes = NULL;
1262 // free cached maximum travel time through cluster portals
1263 if (aasworld.portalmaxtraveltimes) FreeMemory(aasworld.portalmaxtraveltimes);
1264 aasworld.portalmaxtraveltimes = NULL;
1265 // free reversed reachability links
1266 if (aasworld.reversedreachability) FreeMemory(aasworld.reversedreachability);
1267 aasworld.reversedreachability = NULL;
1268 // free routing algorithm memory
1269 if (aasworld.areaupdate) FreeMemory(aasworld.areaupdate);
1270 aasworld.areaupdate = NULL;
1271 if (aasworld.portalupdate) FreeMemory(aasworld.portalupdate);
1272 aasworld.portalupdate = NULL;
1273 // free lists with areas the reachabilities go through
1274 if (aasworld.reachabilityareas) FreeMemory(aasworld.reachabilityareas);
1275 aasworld.reachabilityareas = NULL;
1276 // free the reachability area index
1277 if (aasworld.reachabilityareaindex) FreeMemory(aasworld.reachabilityareaindex);
1278 aasworld.reachabilityareaindex = NULL;
1279 // free area contents travel flags look up table
1280 if (aasworld.areacontentstravelflags) FreeMemory(aasworld.areacontentstravelflags);
1281 aasworld.areacontentstravelflags = NULL;
1282 } //end of the function AAS_FreeRoutingCaches
1283 //===========================================================================
1284 // update the given routing cache
1285 //
1286 // Parameter: areacache : routing cache to update
1287 // Returns: -
1288 // Changes Globals: -
1289 //===========================================================================
AAS_UpdateAreaRoutingCache(aas_routingcache_t * areacache)1290 void AAS_UpdateAreaRoutingCache(aas_routingcache_t *areacache)
1291 {
1292 int i, nextareanum, cluster, badtravelflags, clusterareanum, linknum;
1293 int numreachabilityareas;
1294 unsigned short int t, startareatraveltimes[128]; //NOTE: not more than 128 reachabilities per area allowed
1295 aas_routingupdate_t *updateliststart, *updatelistend, *curupdate, *nextupdate;
1296 aas_reachability_t *reach;
1297 aas_reversedreachability_t *revreach;
1298 aas_reversedlink_t *revlink;
1299
1300 #ifdef ROUTING_DEBUG
1301 numareacacheupdates++;
1302 #endif //ROUTING_DEBUG
1303 //number of reachability areas within this cluster
1304 numreachabilityareas = aasworld.clusters[areacache->cluster].numreachabilityareas;
1305 //
1306 aasworld.frameroutingupdates++;
1307 //clear the routing update fields
1308 // Com_Memset(aasworld.areaupdate, 0, aasworld.numareas * sizeof(aas_routingupdate_t));
1309 //
1310 badtravelflags = ~areacache->travelflags;
1311 //
1312 clusterareanum = AAS_ClusterAreaNum(areacache->cluster, areacache->areanum);
1313 if (clusterareanum >= numreachabilityareas) return;
1314 //
1315 Com_Memset(startareatraveltimes, 0, sizeof(startareatraveltimes));
1316 //
1317 curupdate = &aasworld.areaupdate[clusterareanum];
1318 curupdate->areanum = areacache->areanum;
1319 //VectorCopy(areacache->origin, curupdate->start);
1320 curupdate->areatraveltimes = startareatraveltimes;
1321 curupdate->tmptraveltime = areacache->starttraveltime;
1322 //
1323 areacache->traveltimes[clusterareanum] = areacache->starttraveltime;
1324 //put the area to start with in the current read list
1325 curupdate->next = NULL;
1326 curupdate->prev = NULL;
1327 updateliststart = curupdate;
1328 updatelistend = curupdate;
1329 //while there are updates in the current list
1330 while (updateliststart)
1331 {
1332 curupdate = updateliststart;
1333 //
1334 if (curupdate->next) curupdate->next->prev = NULL;
1335 else updatelistend = NULL;
1336 updateliststart = curupdate->next;
1337 //
1338 curupdate->inlist = qfalse;
1339 //check all reversed reachability links
1340 revreach = &aasworld.reversedreachability[curupdate->areanum];
1341 //
1342 for (i = 0, revlink = revreach->first; revlink; revlink = revlink->next, i++)
1343 {
1344 linknum = revlink->linknum;
1345 reach = &aasworld.reachability[linknum];
1346 //if there is used an undesired travel type
1347 if (AAS_TravelFlagForType_inline(reach->traveltype) & badtravelflags) continue;
1348 //if not allowed to enter the next area
1349 if (aasworld.areasettings[reach->areanum].areaflags & AREA_DISABLED) continue;
1350 //if the next area has a not allowed travel flag
1351 if (AAS_AreaContentsTravelFlags_inline(reach->areanum) & badtravelflags) continue;
1352 //number of the area the reversed reachability leads to
1353 nextareanum = revlink->areanum;
1354 //get the cluster number of the area
1355 cluster = aasworld.areasettings[nextareanum].cluster;
1356 //don't leave the cluster
1357 if (cluster > 0 && cluster != areacache->cluster) continue;
1358 //get the number of the area in the cluster
1359 clusterareanum = AAS_ClusterAreaNum(areacache->cluster, nextareanum);
1360 if (clusterareanum >= numreachabilityareas) continue;
1361 //time already travelled plus the traveltime through
1362 //the current area plus the travel time from the reachability
1363 t = curupdate->tmptraveltime +
1364 //AAS_AreaTravelTime(curupdate->areanum, curupdate->start, reach->end) +
1365 curupdate->areatraveltimes[i] +
1366 reach->traveltime;
1367 //
1368 if (!areacache->traveltimes[clusterareanum] ||
1369 areacache->traveltimes[clusterareanum] > t)
1370 {
1371 areacache->traveltimes[clusterareanum] = t;
1372 areacache->reachabilities[clusterareanum] = linknum - aasworld.areasettings[nextareanum].firstreachablearea;
1373 nextupdate = &aasworld.areaupdate[clusterareanum];
1374 nextupdate->areanum = nextareanum;
1375 nextupdate->tmptraveltime = t;
1376 //VectorCopy(reach->start, nextupdate->start);
1377 nextupdate->areatraveltimes = aasworld.areatraveltimes[nextareanum][linknum -
1378 aasworld.areasettings[nextareanum].firstreachablearea];
1379 if (!nextupdate->inlist)
1380 {
1381 // we add the update to the end of the list
1382 // we could also use a B+ tree to have a real sorted list
1383 // on travel time which makes for faster routing updates
1384 nextupdate->next = NULL;
1385 nextupdate->prev = updatelistend;
1386 if (updatelistend) updatelistend->next = nextupdate;
1387 else updateliststart = nextupdate;
1388 updatelistend = nextupdate;
1389 nextupdate->inlist = qtrue;
1390 } //end if
1391 } //end if
1392 } //end for
1393 } //end while
1394 } //end of the function AAS_UpdateAreaRoutingCache
1395 //===========================================================================
1396 //
1397 // Parameter: -
1398 // Returns: -
1399 // Changes Globals: -
1400 //===========================================================================
AAS_GetAreaRoutingCache(int clusternum,int areanum,int travelflags)1401 aas_routingcache_t *AAS_GetAreaRoutingCache(int clusternum, int areanum, int travelflags)
1402 {
1403 int clusterareanum;
1404 aas_routingcache_t *cache, *clustercache;
1405
1406 //number of the area in the cluster
1407 clusterareanum = AAS_ClusterAreaNum(clusternum, areanum);
1408 //pointer to the cache for the area in the cluster
1409 clustercache = aasworld.clusterareacache[clusternum][clusterareanum];
1410 //find the cache without undesired travel flags
1411 for (cache = clustercache; cache; cache = cache->next)
1412 {
1413 //if there aren't used any undesired travel types for the cache
1414 if (cache->travelflags == travelflags) break;
1415 } //end for
1416 //if there was no cache
1417 if (!cache)
1418 {
1419 cache = AAS_AllocRoutingCache(aasworld.clusters[clusternum].numreachabilityareas);
1420 cache->cluster = clusternum;
1421 cache->areanum = areanum;
1422 VectorCopy(aasworld.areas[areanum].center, cache->origin);
1423 cache->starttraveltime = 1;
1424 cache->travelflags = travelflags;
1425 cache->prev = NULL;
1426 cache->next = clustercache;
1427 if (clustercache) clustercache->prev = cache;
1428 aasworld.clusterareacache[clusternum][clusterareanum] = cache;
1429 AAS_UpdateAreaRoutingCache(cache);
1430 } //end if
1431 else
1432 {
1433 AAS_UnlinkCache(cache);
1434 } //end else
1435 //the cache has been accessed
1436 cache->time = AAS_RoutingTime();
1437 cache->type = CACHETYPE_AREA;
1438 AAS_LinkCache(cache);
1439 return cache;
1440 } //end of the function AAS_GetAreaRoutingCache
1441 //===========================================================================
1442 //
1443 // Parameter: -
1444 // Returns: -
1445 // Changes Globals: -
1446 //===========================================================================
AAS_UpdatePortalRoutingCache(aas_routingcache_t * portalcache)1447 void AAS_UpdatePortalRoutingCache(aas_routingcache_t *portalcache)
1448 {
1449 int i, portalnum, clusterareanum, clusternum;
1450 unsigned short int t;
1451 aas_portal_t *portal;
1452 aas_cluster_t *cluster;
1453 aas_routingcache_t *cache;
1454 aas_routingupdate_t *updateliststart, *updatelistend, *curupdate, *nextupdate;
1455
1456 #ifdef ROUTING_DEBUG
1457 numportalcacheupdates++;
1458 #endif //ROUTING_DEBUG
1459 //clear the routing update fields
1460 // Com_Memset(aasworld.portalupdate, 0, (aasworld.numportals+1) * sizeof(aas_routingupdate_t));
1461 //
1462 curupdate = &aasworld.portalupdate[aasworld.numportals];
1463 curupdate->cluster = portalcache->cluster;
1464 curupdate->areanum = portalcache->areanum;
1465 curupdate->tmptraveltime = portalcache->starttraveltime;
1466 //if the start area is a cluster portal, store the travel time for that portal
1467 clusternum = aasworld.areasettings[portalcache->areanum].cluster;
1468 if (clusternum < 0)
1469 {
1470 portalcache->traveltimes[-clusternum] = portalcache->starttraveltime;
1471 } //end if
1472 //put the area to start with in the current read list
1473 curupdate->next = NULL;
1474 curupdate->prev = NULL;
1475 updateliststart = curupdate;
1476 updatelistend = curupdate;
1477 //while there are updates in the current list
1478 while (updateliststart)
1479 {
1480 curupdate = updateliststart;
1481 //remove the current update from the list
1482 if (curupdate->next) curupdate->next->prev = NULL;
1483 else updatelistend = NULL;
1484 updateliststart = curupdate->next;
1485 //current update is removed from the list
1486 curupdate->inlist = qfalse;
1487 //
1488 cluster = &aasworld.clusters[curupdate->cluster];
1489 //
1490 cache = AAS_GetAreaRoutingCache(curupdate->cluster,
1491 curupdate->areanum, portalcache->travelflags);
1492 //take all portals of the cluster
1493 for (i = 0; i < cluster->numportals; i++)
1494 {
1495 portalnum = aasworld.portalindex[cluster->firstportal + i];
1496 portal = &aasworld.portals[portalnum];
1497 //if this is the portal of the current update continue
1498 if (portal->areanum == curupdate->areanum) continue;
1499 //
1500 clusterareanum = AAS_ClusterAreaNum(curupdate->cluster, portal->areanum);
1501 if (clusterareanum >= cluster->numreachabilityareas) continue;
1502 //
1503 t = cache->traveltimes[clusterareanum];
1504 if (!t) continue;
1505 t += curupdate->tmptraveltime;
1506 //
1507 if (!portalcache->traveltimes[portalnum] ||
1508 portalcache->traveltimes[portalnum] > t)
1509 {
1510 portalcache->traveltimes[portalnum] = t;
1511 nextupdate = &aasworld.portalupdate[portalnum];
1512 if (portal->frontcluster == curupdate->cluster)
1513 {
1514 nextupdate->cluster = portal->backcluster;
1515 } //end if
1516 else
1517 {
1518 nextupdate->cluster = portal->frontcluster;
1519 } //end else
1520 nextupdate->areanum = portal->areanum;
1521 //add travel time through the actual portal area for the next update
1522 nextupdate->tmptraveltime = t + aasworld.portalmaxtraveltimes[portalnum];
1523 if (!nextupdate->inlist)
1524 {
1525 // we add the update to the end of the list
1526 // we could also use a B+ tree to have a real sorted list
1527 // on travel time which makes for faster routing updates
1528 nextupdate->next = NULL;
1529 nextupdate->prev = updatelistend;
1530 if (updatelistend) updatelistend->next = nextupdate;
1531 else updateliststart = nextupdate;
1532 updatelistend = nextupdate;
1533 nextupdate->inlist = qtrue;
1534 } //end if
1535 } //end if
1536 } //end for
1537 } //end while
1538 } //end of the function AAS_UpdatePortalRoutingCache
1539 //===========================================================================
1540 //
1541 // Parameter: -
1542 // Returns: -
1543 // Changes Globals: -
1544 //===========================================================================
AAS_GetPortalRoutingCache(int clusternum,int areanum,int travelflags)1545 aas_routingcache_t *AAS_GetPortalRoutingCache(int clusternum, int areanum, int travelflags)
1546 {
1547 aas_routingcache_t *cache;
1548
1549 //find the cached portal routing if existing
1550 for (cache = aasworld.portalcache[areanum]; cache; cache = cache->next)
1551 {
1552 if (cache->travelflags == travelflags) break;
1553 } //end for
1554 //if the portal routing isn't cached
1555 if (!cache)
1556 {
1557 cache = AAS_AllocRoutingCache(aasworld.numportals);
1558 cache->cluster = clusternum;
1559 cache->areanum = areanum;
1560 VectorCopy(aasworld.areas[areanum].center, cache->origin);
1561 cache->starttraveltime = 1;
1562 cache->travelflags = travelflags;
1563 //add the cache to the cache list
1564 cache->prev = NULL;
1565 cache->next = aasworld.portalcache[areanum];
1566 if (aasworld.portalcache[areanum]) aasworld.portalcache[areanum]->prev = cache;
1567 aasworld.portalcache[areanum] = cache;
1568 //update the cache
1569 AAS_UpdatePortalRoutingCache(cache);
1570 } //end if
1571 else
1572 {
1573 AAS_UnlinkCache(cache);
1574 } //end else
1575 //the cache has been accessed
1576 cache->time = AAS_RoutingTime();
1577 cache->type = CACHETYPE_PORTAL;
1578 AAS_LinkCache(cache);
1579 return cache;
1580 } //end of the function AAS_GetPortalRoutingCache
1581 //===========================================================================
1582 //
1583 // Parameter: -
1584 // Returns: -
1585 // Changes Globals: -
1586 //===========================================================================
AAS_AreaRouteToGoalArea(int areanum,vec3_t origin,int goalareanum,int travelflags,int * traveltime,int * reachnum)1587 int AAS_AreaRouteToGoalArea(int areanum, vec3_t origin, int goalareanum, int travelflags, int *traveltime, int *reachnum)
1588 {
1589 int clusternum, goalclusternum, portalnum, i, clusterareanum, bestreachnum;
1590 unsigned short int t, besttime;
1591 aas_portal_t *portal;
1592 aas_cluster_t *cluster;
1593 aas_routingcache_t *areacache, *portalcache;
1594 aas_reachability_t *reach;
1595
1596 if (!aasworld.initialized) return qfalse;
1597
1598 if (areanum == goalareanum)
1599 {
1600 *traveltime = 1;
1601 *reachnum = 0;
1602 return qtrue;
1603 }
1604 //
1605 if (areanum <= 0 || areanum >= aasworld.numareas)
1606 {
1607 if (bot_developer)
1608 {
1609 botimport.Print(PRT_ERROR, "AAS_AreaTravelTimeToGoalArea: areanum %d out of range\n", areanum);
1610 } //end if
1611 return qfalse;
1612 } //end if
1613 if (goalareanum <= 0 || goalareanum >= aasworld.numareas)
1614 {
1615 if (bot_developer)
1616 {
1617 botimport.Print(PRT_ERROR, "AAS_AreaTravelTimeToGoalArea: goalareanum %d out of range\n", goalareanum);
1618 } //end if
1619 return qfalse;
1620 } //end if
1621 // make sure the routing cache doesn't grow to large
1622 while(AvailableMemory() < 1 * 1024 * 1024) {
1623 if (!AAS_FreeOldestCache()) break;
1624 }
1625 //
1626 if (AAS_AreaDoNotEnter(areanum) || AAS_AreaDoNotEnter(goalareanum))
1627 {
1628 travelflags |= TFL_DONOTENTER;
1629 } //end if
1630 //NOTE: the number of routing updates is limited per frame
1631 /*
1632 if (aasworld.frameroutingupdates > MAX_FRAMEROUTINGUPDATES)
1633 {
1634 #ifdef DEBUG
1635 //Log_Write("WARNING: AAS_AreaTravelTimeToGoalArea: frame routing updates overflowed");
1636 #endif
1637 return 0;
1638 } //end if
1639 */
1640 //
1641 clusternum = aasworld.areasettings[areanum].cluster;
1642 goalclusternum = aasworld.areasettings[goalareanum].cluster;
1643 //check if the area is a portal of the goal area cluster
1644 if (clusternum < 0 && goalclusternum > 0)
1645 {
1646 portal = &aasworld.portals[-clusternum];
1647 if (portal->frontcluster == goalclusternum ||
1648 portal->backcluster == goalclusternum)
1649 {
1650 clusternum = goalclusternum;
1651 } //end if
1652 } //end if
1653 //check if the goalarea is a portal of the area cluster
1654 else if (clusternum > 0 && goalclusternum < 0)
1655 {
1656 portal = &aasworld.portals[-goalclusternum];
1657 if (portal->frontcluster == clusternum ||
1658 portal->backcluster == clusternum)
1659 {
1660 goalclusternum = clusternum;
1661 } //end if
1662 } //end if
1663 //if both areas are in the same cluster
1664 //NOTE: there might be a shorter route via another cluster!!! but we don't care
1665 if (clusternum > 0 && goalclusternum > 0 && clusternum == goalclusternum)
1666 {
1667 //
1668 areacache = AAS_GetAreaRoutingCache(clusternum, goalareanum, travelflags);
1669 //the number of the area in the cluster
1670 clusterareanum = AAS_ClusterAreaNum(clusternum, areanum);
1671 //the cluster the area is in
1672 cluster = &aasworld.clusters[clusternum];
1673 //if the area is NOT a reachability area
1674 if (clusterareanum >= cluster->numreachabilityareas) return 0;
1675 //if it is possible to travel to the goal area through this cluster
1676 if (areacache->traveltimes[clusterareanum] != 0)
1677 {
1678 *reachnum = aasworld.areasettings[areanum].firstreachablearea +
1679 areacache->reachabilities[clusterareanum];
1680 if (!origin) {
1681 *traveltime = areacache->traveltimes[clusterareanum];
1682 return qtrue;
1683 }
1684 reach = &aasworld.reachability[*reachnum];
1685 *traveltime = areacache->traveltimes[clusterareanum] +
1686 AAS_AreaTravelTime(areanum, origin, reach->start);
1687 //
1688 return qtrue;
1689 } //end if
1690 } //end if
1691 //
1692 clusternum = aasworld.areasettings[areanum].cluster;
1693 goalclusternum = aasworld.areasettings[goalareanum].cluster;
1694 //if the goal area is a portal
1695 if (goalclusternum < 0)
1696 {
1697 //just assume the goal area is part of the front cluster
1698 portal = &aasworld.portals[-goalclusternum];
1699 goalclusternum = portal->frontcluster;
1700 } //end if
1701 //get the portal routing cache
1702 portalcache = AAS_GetPortalRoutingCache(goalclusternum, goalareanum, travelflags);
1703 //if the area is a cluster portal, read directly from the portal cache
1704 if (clusternum < 0)
1705 {
1706 *traveltime = portalcache->traveltimes[-clusternum];
1707 *reachnum = aasworld.areasettings[areanum].firstreachablearea +
1708 portalcache->reachabilities[-clusternum];
1709 return qtrue;
1710 } //end if
1711 //
1712 besttime = 0;
1713 bestreachnum = -1;
1714 //the cluster the area is in
1715 cluster = &aasworld.clusters[clusternum];
1716 //find the portal of the area cluster leading towards the goal area
1717 for (i = 0; i < cluster->numportals; i++)
1718 {
1719 portalnum = aasworld.portalindex[cluster->firstportal + i];
1720 //if the goal area isn't reachable from the portal
1721 if (!portalcache->traveltimes[portalnum]) continue;
1722 //
1723 portal = &aasworld.portals[portalnum];
1724 //get the cache of the portal area
1725 areacache = AAS_GetAreaRoutingCache(clusternum, portal->areanum, travelflags);
1726 //current area inside the current cluster
1727 clusterareanum = AAS_ClusterAreaNum(clusternum, areanum);
1728 //if the area is NOT a reachability area
1729 if (clusterareanum >= cluster->numreachabilityareas) continue;
1730 //if the portal is NOT reachable from this area
1731 if (!areacache->traveltimes[clusterareanum]) continue;
1732 //total travel time is the travel time the portal area is from
1733 //the goal area plus the travel time towards the portal area
1734 t = portalcache->traveltimes[portalnum] + areacache->traveltimes[clusterareanum];
1735 //FIXME: add the exact travel time through the actual portal area
1736 //NOTE: for now we just add the largest travel time through the portal area
1737 // because we can't directly calculate the exact travel time
1738 // to be more specific we don't know which reachability was used to travel
1739 // into the portal area
1740 t += aasworld.portalmaxtraveltimes[portalnum];
1741 //
1742 if (origin)
1743 {
1744 *reachnum = aasworld.areasettings[areanum].firstreachablearea +
1745 areacache->reachabilities[clusterareanum];
1746 reach = aasworld.reachability + *reachnum;
1747 t += AAS_AreaTravelTime(areanum, origin, reach->start);
1748 } //end if
1749 //if the time is better than the one already found
1750 if (!besttime || t < besttime)
1751 {
1752 bestreachnum = *reachnum;
1753 besttime = t;
1754 } //end if
1755 } //end for
1756 if (bestreachnum < 0) {
1757 return qfalse;
1758 }
1759 *reachnum = bestreachnum;
1760 *traveltime = besttime;
1761 return qtrue;
1762 } //end of the function AAS_AreaRouteToGoalArea
1763 //===========================================================================
1764 //
1765 // Parameter: -
1766 // Returns: -
1767 // Changes Globals: -
1768 //===========================================================================
AAS_AreaTravelTimeToGoalArea(int areanum,vec3_t origin,int goalareanum,int travelflags)1769 int AAS_AreaTravelTimeToGoalArea(int areanum, vec3_t origin, int goalareanum, int travelflags)
1770 {
1771 int traveltime, reachnum;
1772
1773 if (AAS_AreaRouteToGoalArea(areanum, origin, goalareanum, travelflags, &traveltime, &reachnum))
1774 {
1775 return traveltime;
1776 }
1777 return 0;
1778 } //end of the function AAS_AreaTravelTimeToGoalArea
1779 //===========================================================================
1780 //
1781 // Parameter: -
1782 // Returns: -
1783 // Changes Globals: -
1784 //===========================================================================
AAS_AreaReachabilityToGoalArea(int areanum,vec3_t origin,int goalareanum,int travelflags)1785 int AAS_AreaReachabilityToGoalArea(int areanum, vec3_t origin, int goalareanum, int travelflags)
1786 {
1787 int traveltime, reachnum;
1788
1789 if (AAS_AreaRouteToGoalArea(areanum, origin, goalareanum, travelflags, &traveltime, &reachnum))
1790 {
1791 return reachnum;
1792 }
1793 return 0;
1794 } //end of the function AAS_AreaReachabilityToGoalArea
1795 //===========================================================================
1796 // predict the route and stop on one of the stop events
1797 //
1798 // Parameter: -
1799 // Returns: -
1800 // Changes Globals: -
1801 //===========================================================================
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)1802 int AAS_PredictRoute(struct aas_predictroute_s *route, int areanum, vec3_t origin,
1803 int goalareanum, int travelflags, int maxareas, int maxtime,
1804 int stopevent, int stopcontents, int stoptfl, int stopareanum)
1805 {
1806 int curareanum, reachnum, i, j, testareanum;
1807 vec3_t curorigin;
1808 aas_reachability_t *reach;
1809 aas_reachabilityareas_t *reachareas;
1810
1811 //init output
1812 route->stopevent = RSE_NONE;
1813 route->endarea = goalareanum;
1814 route->endcontents = 0;
1815 route->endtravelflags = 0;
1816 VectorCopy(origin, route->endpos);
1817 route->time = 0;
1818
1819 curareanum = areanum;
1820 VectorCopy(origin, curorigin);
1821
1822 for (i = 0; curareanum != goalareanum && (!maxareas || i < maxareas) && i < aasworld.numareas; i++)
1823 {
1824 reachnum = AAS_AreaReachabilityToGoalArea(curareanum, curorigin, goalareanum, travelflags);
1825 if (!reachnum)
1826 {
1827 route->stopevent = RSE_NOROUTE;
1828 return qfalse;
1829 } //end if
1830 reach = &aasworld.reachability[reachnum];
1831 //
1832 if (stopevent & RSE_USETRAVELTYPE)
1833 {
1834 if (AAS_TravelFlagForType_inline(reach->traveltype) & stoptfl)
1835 {
1836 route->stopevent = RSE_USETRAVELTYPE;
1837 route->endarea = curareanum;
1838 route->endcontents = aasworld.areasettings[curareanum].contents;
1839 route->endtravelflags = AAS_TravelFlagForType_inline(reach->traveltype);
1840 VectorCopy(reach->start, route->endpos);
1841 return qtrue;
1842 } //end if
1843 if (AAS_AreaContentsTravelFlags_inline(reach->areanum) & stoptfl)
1844 {
1845 route->stopevent = RSE_USETRAVELTYPE;
1846 route->endarea = reach->areanum;
1847 route->endcontents = aasworld.areasettings[reach->areanum].contents;
1848 route->endtravelflags = AAS_AreaContentsTravelFlags_inline(reach->areanum);
1849 VectorCopy(reach->end, route->endpos);
1850 route->time += AAS_AreaTravelTime(areanum, origin, reach->start);
1851 route->time += reach->traveltime;
1852 return qtrue;
1853 } //end if
1854 } //end if
1855 reachareas = &aasworld.reachabilityareas[reachnum];
1856 for (j = 0; j < reachareas->numareas + 1; j++)
1857 {
1858 if (j >= reachareas->numareas)
1859 testareanum = reach->areanum;
1860 else
1861 testareanum = aasworld.reachabilityareaindex[reachareas->firstarea + j];
1862 if (stopevent & RSE_ENTERCONTENTS)
1863 {
1864 if (aasworld.areasettings[testareanum].contents & stopcontents)
1865 {
1866 route->stopevent = RSE_ENTERCONTENTS;
1867 route->endarea = testareanum;
1868 route->endcontents = aasworld.areasettings[testareanum].contents;
1869 VectorCopy(reach->end, route->endpos);
1870 route->time += AAS_AreaTravelTime(areanum, origin, reach->start);
1871 route->time += reach->traveltime;
1872 return qtrue;
1873 } //end if
1874 } //end if
1875 if (stopevent & RSE_ENTERAREA)
1876 {
1877 if (testareanum == stopareanum)
1878 {
1879 route->stopevent = RSE_ENTERAREA;
1880 route->endarea = testareanum;
1881 route->endcontents = aasworld.areasettings[testareanum].contents;
1882 VectorCopy(reach->start, route->endpos);
1883 return qtrue;
1884 } //end if
1885 } //end if
1886 } //end for
1887
1888 route->time += AAS_AreaTravelTime(areanum, origin, reach->start);
1889 route->time += reach->traveltime;
1890 route->endarea = reach->areanum;
1891 route->endcontents = aasworld.areasettings[reach->areanum].contents;
1892 route->endtravelflags = AAS_TravelFlagForType_inline(reach->traveltype);
1893 VectorCopy(reach->end, route->endpos);
1894 //
1895 curareanum = reach->areanum;
1896 VectorCopy(reach->end, curorigin);
1897 //
1898 if (maxtime && route->time > maxtime)
1899 break;
1900 } //end while
1901 if (curareanum != goalareanum)
1902 return qfalse;
1903 return qtrue;
1904 } //end of the function AAS_PredictRoute
1905 //===========================================================================
1906 //
1907 // Parameter: -
1908 // Returns: -
1909 // Changes Globals: -
1910 //===========================================================================
AAS_BridgeWalkable(int areanum)1911 int AAS_BridgeWalkable(int areanum)
1912 {
1913 return qfalse;
1914 } //end of the function AAS_BridgeWalkable
1915 //===========================================================================
1916 //
1917 // Parameter: -
1918 // Returns: -
1919 // Changes Globals: -
1920 //===========================================================================
AAS_ReachabilityFromNum(int num,struct aas_reachability_s * reach)1921 void AAS_ReachabilityFromNum(int num, struct aas_reachability_s *reach)
1922 {
1923 if (!aasworld.initialized)
1924 {
1925 Com_Memset(reach, 0, sizeof(aas_reachability_t));
1926 return;
1927 } //end if
1928 if (num < 0 || num >= aasworld.reachabilitysize)
1929 {
1930 Com_Memset(reach, 0, sizeof(aas_reachability_t));
1931 return;
1932 } //end if
1933 Com_Memcpy(reach, &aasworld.reachability[num], sizeof(aas_reachability_t));;
1934 } //end of the function AAS_ReachabilityFromNum
1935 //===========================================================================
1936 //
1937 // Parameter: -
1938 // Returns: -
1939 // Changes Globals: -
1940 //===========================================================================
AAS_NextAreaReachability(int areanum,int reachnum)1941 int AAS_NextAreaReachability(int areanum, int reachnum)
1942 {
1943 aas_areasettings_t *settings;
1944
1945 if (!aasworld.initialized) return 0;
1946
1947 if (areanum <= 0 || areanum >= aasworld.numareas)
1948 {
1949 botimport.Print(PRT_ERROR, "AAS_NextAreaReachability: areanum %d out of range\n", areanum);
1950 return 0;
1951 } //end if
1952
1953 settings = &aasworld.areasettings[areanum];
1954 if (!reachnum)
1955 {
1956 return settings->firstreachablearea;
1957 } //end if
1958 if (reachnum < settings->firstreachablearea)
1959 {
1960 botimport.Print(PRT_FATAL, "AAS_NextAreaReachability: reachnum < settings->firstreachableara");
1961 return 0;
1962 } //end if
1963 reachnum++;
1964 if (reachnum >= settings->firstreachablearea + settings->numreachableareas)
1965 {
1966 return 0;
1967 } //end if
1968 return reachnum;
1969 } //end of the function AAS_NextAreaReachability
1970 //===========================================================================
1971 //
1972 // Parameter: -
1973 // Returns: -
1974 // Changes Globals: -
1975 //===========================================================================
AAS_NextModelReachability(int num,int modelnum)1976 int AAS_NextModelReachability(int num, int modelnum)
1977 {
1978 int i;
1979
1980 if (num <= 0) num = 1;
1981 else if (num >= aasworld.reachabilitysize) return 0;
1982 else num++;
1983 //
1984 for (i = num; i < aasworld.reachabilitysize; i++)
1985 {
1986 if ((aasworld.reachability[i].traveltype & TRAVELTYPE_MASK) == TRAVEL_ELEVATOR)
1987 {
1988 if (aasworld.reachability[i].facenum == modelnum) return i;
1989 } //end if
1990 else if ((aasworld.reachability[i].traveltype & TRAVELTYPE_MASK) == TRAVEL_FUNCBOB)
1991 {
1992 if ((aasworld.reachability[i].facenum & 0x0000FFFF) == modelnum) return i;
1993 } //end if
1994 } //end for
1995 return 0;
1996 } //end of the function AAS_NextModelReachability
1997 //===========================================================================
1998 //
1999 // Parameter: -
2000 // Returns: -
2001 // Changes Globals: -
2002 //===========================================================================
AAS_RandomGoalArea(int areanum,int travelflags,int * goalareanum,vec3_t goalorigin)2003 int AAS_RandomGoalArea(int areanum, int travelflags, int *goalareanum, vec3_t goalorigin)
2004 {
2005 int i, n, t;
2006 vec3_t start, end;
2007 aas_trace_t trace;
2008
2009 //if the area has no reachabilities
2010 if (!AAS_AreaReachability(areanum)) return qfalse;
2011 //
2012 n = aasworld.numareas * random();
2013 for (i = 0; i < aasworld.numareas; i++)
2014 {
2015 if (n <= 0) n = 1;
2016 if (n >= aasworld.numareas) n = 1;
2017 if (AAS_AreaReachability(n))
2018 {
2019 t = AAS_AreaTravelTimeToGoalArea(areanum, aasworld.areas[areanum].center, n, travelflags);
2020 //if the goal is reachable
2021 if (t > 0)
2022 {
2023 if (AAS_AreaSwim(n))
2024 {
2025 *goalareanum = n;
2026 VectorCopy(aasworld.areas[n].center, goalorigin);
2027 //botimport.Print(PRT_MESSAGE, "found random goal area %d\n", *goalareanum);
2028 return qtrue;
2029 } //end if
2030 VectorCopy(aasworld.areas[n].center, start);
2031 if (!AAS_PointAreaNum(start))
2032 Log_Write("area %d center %f %f %f in solid?", n, start[0], start[1], start[2]);
2033 VectorCopy(start, end);
2034 end[2] -= 300;
2035 trace = AAS_TraceClientBBox(start, end, PRESENCE_CROUCH, -1);
2036 if (!trace.startsolid && trace.fraction < 1 && AAS_PointAreaNum(trace.endpos) == n)
2037 {
2038 if (AAS_AreaGroundFaceArea(n) > 300)
2039 {
2040 *goalareanum = n;
2041 VectorCopy(trace.endpos, goalorigin);
2042 //botimport.Print(PRT_MESSAGE, "found random goal area %d\n", *goalareanum);
2043 return qtrue;
2044 } //end if
2045 } //end if
2046 } //end if
2047 } //end if
2048 n++;
2049 } //end for
2050 return qfalse;
2051 } //end of the function AAS_RandomGoalArea
2052 //===========================================================================
2053 //
2054 // Parameter: -
2055 // Returns: -
2056 // Changes Globals: -
2057 //===========================================================================
AAS_AreaVisible(int srcarea,int destarea)2058 int AAS_AreaVisible(int srcarea, int destarea)
2059 {
2060 return qfalse;
2061 } //end of the function AAS_AreaVisible
2062 //===========================================================================
2063 //
2064 // Parameter: -
2065 // Returns: -
2066 // Changes Globals: -
2067 //===========================================================================
DistancePointToLine(vec3_t v1,vec3_t v2,vec3_t point)2068 float DistancePointToLine(vec3_t v1, vec3_t v2, vec3_t point)
2069 {
2070 vec3_t vec, p2;
2071
2072 AAS_ProjectPointOntoVector(point, v1, v2, p2);
2073 VectorSubtract(point, p2, vec);
2074 return VectorLength(vec);
2075 } //end of the function DistancePointToLine
2076 //===========================================================================
2077 //
2078 // Parameter: -
2079 // Returns: -
2080 // Changes Globals: -
2081 //===========================================================================
AAS_NearestHideArea(int srcnum,vec3_t origin,int areanum,int enemynum,vec3_t enemyorigin,int enemyareanum,int travelflags)2082 int AAS_NearestHideArea(int srcnum, vec3_t origin, int areanum, int enemynum, vec3_t enemyorigin, int enemyareanum, int travelflags)
2083 {
2084 int i, j, nextareanum, badtravelflags, numreach, bestarea;
2085 unsigned short int t, besttraveltime;
2086 static unsigned short int *hidetraveltimes;
2087 aas_routingupdate_t *updateliststart, *updatelistend, *curupdate, *nextupdate;
2088 aas_reachability_t *reach;
2089 float dist1, dist2;
2090 vec3_t v1, v2, p;
2091 qboolean startVisible;
2092
2093 //
2094 if (!hidetraveltimes)
2095 {
2096 hidetraveltimes = (unsigned short int *) GetClearedMemory(aasworld.numareas * sizeof(unsigned short int));
2097 } //end if
2098 else
2099 {
2100 Com_Memset(hidetraveltimes, 0, aasworld.numareas * sizeof(unsigned short int));
2101 } //end else
2102 besttraveltime = 0;
2103 bestarea = 0;
2104 //assume visible
2105 startVisible = qtrue;
2106 //
2107 badtravelflags = ~travelflags;
2108 //
2109 curupdate = &aasworld.areaupdate[areanum];
2110 curupdate->areanum = areanum;
2111 VectorCopy(origin, curupdate->start);
2112 curupdate->areatraveltimes = aasworld.areatraveltimes[areanum][0];
2113 curupdate->tmptraveltime = 0;
2114 //put the area to start with in the current read list
2115 curupdate->next = NULL;
2116 curupdate->prev = NULL;
2117 updateliststart = curupdate;
2118 updatelistend = curupdate;
2119 //while there are updates in the list
2120 while (updateliststart)
2121 {
2122 curupdate = updateliststart;
2123 //
2124 if (curupdate->next) curupdate->next->prev = NULL;
2125 else updatelistend = NULL;
2126 updateliststart = curupdate->next;
2127 //
2128 curupdate->inlist = qfalse;
2129 //check all reversed reachability links
2130 numreach = aasworld.areasettings[curupdate->areanum].numreachableareas;
2131 reach = &aasworld.reachability[aasworld.areasettings[curupdate->areanum].firstreachablearea];
2132 //
2133 for (i = 0; i < numreach; i++, reach++)
2134 {
2135 //if an undesired travel type is used
2136 if (AAS_TravelFlagForType_inline(reach->traveltype) & badtravelflags) continue;
2137 //
2138 if (AAS_AreaContentsTravelFlags_inline(reach->areanum) & badtravelflags) continue;
2139 //number of the area the reachability leads to
2140 nextareanum = reach->areanum;
2141 // if this moves us into the enemies area, skip it
2142 if (nextareanum == enemyareanum) continue;
2143 //time already travelled plus the traveltime through
2144 //the current area plus the travel time from the reachability
2145 t = curupdate->tmptraveltime +
2146 AAS_AreaTravelTime(curupdate->areanum, curupdate->start, reach->start) +
2147 reach->traveltime;
2148
2149 //avoid going near the enemy
2150 AAS_ProjectPointOntoVector(enemyorigin, curupdate->start, reach->end, p);
2151 for (j = 0; j < 3; j++)
2152 if ((p[j] > curupdate->start[j] && p[j] > reach->end[j]) ||
2153 (p[j] < curupdate->start[j] && p[j] < reach->end[j]))
2154 break;
2155 if (j < 3)
2156 {
2157 VectorSubtract(enemyorigin, reach->end, v2);
2158 } //end if
2159 else
2160 {
2161 VectorSubtract(enemyorigin, p, v2);
2162 } //end else
2163 dist2 = VectorLength(v2);
2164 //never go through the enemy
2165 if (dist2 < 40) continue;
2166 //
2167 VectorSubtract(enemyorigin, curupdate->start, v1);
2168 dist1 = VectorLength(v1);
2169 //
2170 if (dist2 < dist1)
2171 {
2172 t += (dist1 - dist2) * 10;
2173 }
2174 // if we weren't visible when starting, make sure we don't move into their view
2175 if (!startVisible && AAS_AreaVisible(enemyareanum, nextareanum)) {
2176 continue;
2177 }
2178 //
2179 if (besttraveltime && t >= besttraveltime) continue;
2180 //
2181 if (!hidetraveltimes[nextareanum] ||
2182 hidetraveltimes[nextareanum] > t)
2183 {
2184 //if the nextarea is not visible from the enemy area
2185 if (!AAS_AreaVisible(enemyareanum, nextareanum))
2186 {
2187 besttraveltime = t;
2188 bestarea = nextareanum;
2189 } //end if
2190 hidetraveltimes[nextareanum] = t;
2191 nextupdate = &aasworld.areaupdate[nextareanum];
2192 nextupdate->areanum = nextareanum;
2193 nextupdate->tmptraveltime = t;
2194 //remember where we entered this area
2195 VectorCopy(reach->end, nextupdate->start);
2196 //if this update is not in the list yet
2197 if (!nextupdate->inlist)
2198 {
2199 //add the new update to the end of the list
2200 nextupdate->next = NULL;
2201 nextupdate->prev = updatelistend;
2202 if (updatelistend) updatelistend->next = nextupdate;
2203 else updateliststart = nextupdate;
2204 updatelistend = nextupdate;
2205 nextupdate->inlist = qtrue;
2206 } //end if
2207 } //end if
2208 } //end for
2209 } //end while
2210 return bestarea;
2211 } //end of the function AAS_NearestHideArea
2212