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