doom3-gpl
Doom 3 GPL source release
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
AAS_routing.cpp
Go to the documentation of this file.
1 /*
2 ===========================================================================
3 
4 Doom 3 GPL Source Code
5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
6 
7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
8 
9 Doom 3 Source Code is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
13 
14 Doom 3 Source Code is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18 
19 You should have received a copy of the GNU General Public License
20 along with Doom 3 Source Code. If not, see <http://www.gnu.org/licenses/>.
21 
22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code. If not, please request a copy in writing from id Software at the address below.
23 
24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
25 
26 ===========================================================================
27 */
28 
29 #include "../../idlib/precompiled.h"
30 #pragma hdrstop
31 
32 #include "AAS_local.h"
33 #include "../Game_local.h" // for print and error
34 
35 #define CACHETYPE_AREA 1
36 #define CACHETYPE_PORTAL 2
37 
38 #define MAX_ROUTING_CACHE_MEMORY (2*1024*1024)
39 
40 #define LEDGE_TRAVELTIME_PANALTY 250
41 
42 /*
43 ============
44 idRoutingCache::idRoutingCache
45 ============
46 */
48  areaNum = 0;
49  cluster = 0;
50  next = prev = NULL;
52  travelFlags = 0;
53  startTravelTime = 0;
54  type = 0;
55  this->size = size;
56  reachabilities = new byte[size];
57  memset( reachabilities, 0, size * sizeof( reachabilities[0] ) );
58  travelTimes = new unsigned short[size];
59  memset( travelTimes, 0, size * sizeof( travelTimes[0] ) );
60 }
61 
62 /*
63 ============
64 idRoutingCache::~idRoutingCache
65 ============
66 */
68  delete [] reachabilities;
69  delete [] travelTimes;
70 }
71 
72 /*
73 ============
74 idRoutingCache::Size
75 ============
76 */
77 int idRoutingCache::Size( void ) const {
78  return sizeof( idRoutingCache ) + size * sizeof( reachabilities[0] ) + size * sizeof( travelTimes[0] );
79 }
80 
81 /*
82 ============
83 idAASLocal::AreaTravelTime
84 ============
85 */
86 unsigned short idAASLocal::AreaTravelTime( int areaNum, const idVec3 &start, const idVec3 &end ) const {
87  float dist;
88 
89  dist = ( end - start ).Length();
90 
91  if ( file->GetArea( areaNum ).travelFlags & TFL_CROUCH ) {
92  dist *= 100.0f / 100.0f;
93  } else if ( file->GetArea( areaNum ).travelFlags & TFL_WATER ) {
94  dist *= 100.0f / 150.0f;
95  } else {
96  dist *= 100.0f / 300.0f;
97  }
98  if ( dist < 1.0f ) {
99  return 1;
100  }
101  return (unsigned short) idMath::FtoiFast( dist );
102 }
103 
104 /*
105 ============
106 idAASLocal::CalculateAreaTravelTimes
107 ============
108 */
110  int n, i, j, numReach, numRevReach, t, maxt;
111  byte *bytePtr;
112  idReachability *reach, *rev_reach;
113 
114  // get total memory for all area travel times
115  numAreaTravelTimes = 0;
116  for ( n = 0; n < file->GetNumAreas(); n++ ) {
117 
119  continue;
120  }
121 
122  numReach = 0;
123  for ( reach = file->GetArea( n ).reach; reach; reach = reach->next ) {
124  numReach++;
125  }
126 
127  numRevReach = 0;
128  for ( rev_reach = file->GetArea( n ).rev_reach; rev_reach; rev_reach = rev_reach->rev_next ) {
129  numRevReach++;
130  }
131  numAreaTravelTimes += numReach * numRevReach;
132  }
133 
134  areaTravelTimes = (unsigned short *) Mem_Alloc( numAreaTravelTimes * sizeof( unsigned short ) );
135  bytePtr = (byte *) areaTravelTimes;
136 
137  for ( n = 0; n < file->GetNumAreas(); n++ ) {
138 
140  continue;
141  }
142 
143  // for each reachability that starts in this area calculate the travel time
144  // towards all the reachabilities that lead towards this area
145  for ( maxt = i = 0, reach = file->GetArea( n ).reach; reach; reach = reach->next, i++ ) {
146  assert( i < MAX_REACH_PER_AREA );
147  if ( i >= MAX_REACH_PER_AREA ) {
148  gameLocal.Error( "i >= MAX_REACH_PER_AREA" );
149  }
150  reach->number = i;
151  reach->disableCount = 0;
152  reach->areaTravelTimes = (unsigned short *) bytePtr;
153  for ( j = 0, rev_reach = file->GetArea( n ).rev_reach; rev_reach; rev_reach = rev_reach->rev_next, j++ ) {
154  t = AreaTravelTime( n, reach->start, rev_reach->end );
155  reach->areaTravelTimes[j] = t;
156  if ( t > maxt ) {
157  maxt = t;
158  }
159  }
160  bytePtr += j * sizeof( unsigned short );
161  }
162 
163  // if this area is a portal
164  if ( file->GetArea( n ).cluster < 0 ) {
165  // set the maximum travel time through this portal
167  }
168  }
169 
170  assert( ( (unsigned int) bytePtr - (unsigned int) areaTravelTimes ) <= numAreaTravelTimes * sizeof( unsigned short ) );
171 }
172 
173 /*
174 ============
175 idAASLocal::DeleteAreaTravelTimes
176 ============
177 */
181  numAreaTravelTimes = 0;
182 }
183 
184 /*
185 ============
186 idAASLocal::SetupRoutingCache
187 ============
188 */
190  int i;
191  byte *bytePtr;
192 
193  areaCacheIndexSize = 0;
194  for ( i = 0; i < file->GetNumClusters(); i++ ) {
196  }
198  areaCacheIndexSize * sizeof( idRoutingCache *) );
199  bytePtr = ((byte *)areaCacheIndex) + file->GetNumClusters() * sizeof( idRoutingCache ** );
200  for ( i = 0; i < file->GetNumClusters(); i++ ) {
201  areaCacheIndex[i] = ( idRoutingCache ** ) bytePtr;
202  bytePtr += file->GetCluster( i ).numReachableAreas * sizeof( idRoutingCache * );
203  }
204 
207 
210 
211  goalAreaTravelTimes = (unsigned short *) Mem_ClearedAlloc( file->GetNumAreas() * sizeof( unsigned short ) );
212 
214  totalCacheMemory = 0;
215 }
216 
217 /*
218 ============
219 idAASLocal::DeleteClusterCache
220 ============
221 */
222 void idAASLocal::DeleteClusterCache( int clusterNum ) {
223  int i;
224  idRoutingCache *cache;
225 
226  for ( i = 0; i < file->GetCluster( clusterNum ).numReachableAreas; i++ ) {
227  for ( cache = areaCacheIndex[clusterNum][i]; cache; cache = areaCacheIndex[clusterNum][i] ) {
228  areaCacheIndex[clusterNum][i] = cache->next;
229  UnlinkCache( cache );
230  delete cache;
231  }
232  }
233 }
234 
235 /*
236 ============
237 idAASLocal::DeletePortalCache
238 ============
239 */
241  int i;
242  idRoutingCache *cache;
243 
244  for ( i = 0; i < file->GetNumAreas(); i++ ) {
245  for ( cache = portalCacheIndex[i]; cache; cache = portalCacheIndex[i] ) {
246  portalCacheIndex[i] = cache->next;
247  UnlinkCache( cache );
248  delete cache;
249  }
250  }
251 }
252 
253 /*
254 ============
255 idAASLocal::ShutdownRoutingCache
256 ============
257 */
259  int i;
260 
261  for ( i = 0; i < file->GetNumClusters(); i++ ) {
262  DeleteClusterCache( i );
263  }
264 
266 
269  areaCacheIndexSize = 0;
273  Mem_Free( areaUpdate );
274  areaUpdate = NULL;
276  portalUpdate = NULL;
279 
281  totalCacheMemory = 0;
282 }
283 
284 /*
285 ============
286 idAASLocal::SetupRouting
287 ============
288 */
292  return true;
293 }
294 
295 /*
296 ============
297 idAASLocal::ShutdownRouting
298 ============
299 */
303 }
304 
305 /*
306 ============
307 idAASLocal::RoutingStats
308 ============
309 */
310 void idAASLocal::RoutingStats( void ) const {
311  idRoutingCache *cache;
312  int numAreaCache, numPortalCache;
313  int totalAreaCacheMemory, totalPortalCacheMemory;
314 
315  numAreaCache = numPortalCache = 0;
316  totalAreaCacheMemory = totalPortalCacheMemory = 0;
317  for ( cache = cacheListStart; cache; cache = cache->time_next ) {
318  if ( cache->type == CACHETYPE_AREA ) {
319  numAreaCache++;
320  totalAreaCacheMemory += sizeof( idRoutingCache ) + cache->size * (sizeof( unsigned short ) + sizeof( byte ));
321  } else {
322  numPortalCache++;
323  totalPortalCacheMemory += sizeof( idRoutingCache ) + cache->size * (sizeof( unsigned short ) + sizeof( byte ));
324  }
325  }
326 
327  gameLocal.Printf( "%6d area cache (%d KB)\n", numAreaCache, totalAreaCacheMemory >> 10 );
328  gameLocal.Printf( "%6d portal cache (%d KB)\n", numPortalCache, totalPortalCacheMemory >> 10 );
329  gameLocal.Printf( "%6d total cache (%d KB)\n", numAreaCache + numPortalCache, totalCacheMemory >> 10 );
330  gameLocal.Printf( "%6d area travel times (%d KB)\n", numAreaTravelTimes, ( numAreaTravelTimes * sizeof( unsigned short ) ) >> 10 );
331  gameLocal.Printf( "%6d area cache entries (%d KB)\n", areaCacheIndexSize, ( areaCacheIndexSize * sizeof( idRoutingCache * ) ) >> 10 );
332  gameLocal.Printf( "%6d portal cache entries (%d KB)\n", portalCacheIndexSize, ( portalCacheIndexSize * sizeof( idRoutingCache * ) ) >> 10 );
333 }
334 
335 /*
336 ============
337 idAASLocal::RemoveRoutingCacheUsingArea
338 ============
339 */
341  int clusterNum;
342 
343  clusterNum = file->GetArea( areaNum ).cluster;
344  if ( clusterNum > 0 ) {
345  // remove all the cache in the cluster the area is in
346  DeleteClusterCache( clusterNum );
347  }
348  else {
349  // if this is a portal remove all cache in both the front and back cluster
350  DeleteClusterCache( file->GetPortal( -clusterNum ).clusters[0] );
351  DeleteClusterCache( file->GetPortal( -clusterNum ).clusters[1] );
352  }
354 }
355 
356 /*
357 ============
358 idAASLocal::DisableArea
359 ============
360 */
361 void idAASLocal::DisableArea( int areaNum ) {
362  assert( areaNum > 0 && areaNum < file->GetNumAreas() );
363 
364  if ( file->GetArea( areaNum ).travelFlags & TFL_INVALID ) {
365  return;
366  }
367 
368  file->SetAreaTravelFlag( areaNum, TFL_INVALID );
369 
370  RemoveRoutingCacheUsingArea( areaNum );
371 }
372 
373 /*
374 ============
375 idAASLocal::EnableArea
376 ============
377 */
378 void idAASLocal::EnableArea( int areaNum ) {
379  assert( areaNum > 0 && areaNum < file->GetNumAreas() );
380 
381  if ( !( file->GetArea( areaNum ).travelFlags & TFL_INVALID ) ) {
382  return;
383  }
384 
386 
387  RemoveRoutingCacheUsingArea( areaNum );
388 }
389 
390 /*
391 ============
392 idAASLocal::SetAreaState_r
393 ============
394 */
395 bool idAASLocal::SetAreaState_r( int nodeNum, const idBounds &bounds, const int areaContents, bool disabled ) {
396  int res;
397  const aasNode_t *node;
398  bool foundClusterPortal = false;
399 
400  while( nodeNum != 0 ) {
401  if ( nodeNum < 0 ) {
402  // if this area is a cluster portal
403  if ( file->GetArea( -nodeNum ).contents & areaContents ) {
404  if ( disabled ) {
405  DisableArea( -nodeNum );
406  } else {
407  EnableArea( -nodeNum );
408  }
409  foundClusterPortal |= true;
410  }
411  break;
412  }
413  node = &file->GetNode( nodeNum );
414  res = bounds.PlaneSide( file->GetPlane( node->planeNum ) );
415  if ( res == PLANESIDE_BACK ) {
416  nodeNum = node->children[1];
417  }
418  else if ( res == PLANESIDE_FRONT ) {
419  nodeNum = node->children[0];
420  }
421  else {
422  foundClusterPortal |= SetAreaState_r( node->children[1], bounds, areaContents, disabled );
423  nodeNum = node->children[0];
424  }
425  }
426 
427  return foundClusterPortal;
428 }
429 
430 /*
431 ============
432 idAASLocal::SetAreaState
433 ============
434 */
435 bool idAASLocal::SetAreaState( const idBounds &bounds, const int areaContents, bool disabled ) {
436  idBounds expBounds;
437 
438  if ( !file ) {
439  return false;
440  }
441 
442  expBounds[0] = bounds[0] - file->GetSettings().boundingBoxes[0][1];
443  expBounds[1] = bounds[1] - file->GetSettings().boundingBoxes[0][0];
444 
445  // find all areas within or touching the bounds with the given contents and disable/enable them for routing
446  return SetAreaState_r( 1, expBounds, areaContents, disabled );
447 }
448 
449 /*
450 ============
451 idAASLocal::GetBoundsAreas_r
452 ============
453 */
454 void idAASLocal::GetBoundsAreas_r( int nodeNum, const idBounds &bounds, idList<int> &areas ) const {
455  int res;
456  const aasNode_t *node;
457 
458  while( nodeNum != 0 ) {
459  if ( nodeNum < 0 ) {
460  areas.Append( -nodeNum );
461  break;
462  }
463  node = &file->GetNode( nodeNum );
464  res = bounds.PlaneSide( file->GetPlane( node->planeNum ) );
465  if ( res == PLANESIDE_BACK ) {
466  nodeNum = node->children[1];
467  }
468  else if ( res == PLANESIDE_FRONT ) {
469  nodeNum = node->children[0];
470  }
471  else {
472  GetBoundsAreas_r( node->children[1], bounds, areas );
473  nodeNum = node->children[0];
474  }
475  }
476 }
477 
478 /*
479 ============
480 idAASLocal::SetObstacleState
481 ============
482 */
483 void idAASLocal::SetObstacleState( const idRoutingObstacle *obstacle, bool enable ) {
484  int i;
485  const aasArea_t *area;
486  idReachability *reach, *rev_reach;
487  bool inside;
488 
489  for ( i = 0; i < obstacle->areas.Num(); i++ ) {
490 
491  RemoveRoutingCacheUsingArea( obstacle->areas[i] );
492 
493  area = &file->GetArea( obstacle->areas[i] );
494 
495  for ( rev_reach = area->rev_reach; rev_reach; rev_reach = rev_reach->rev_next ) {
496 
497  if ( rev_reach->travelType & TFL_INVALID ) {
498  continue;
499  }
500 
501  inside = false;
502 
503  if ( obstacle->bounds.ContainsPoint( rev_reach->end ) ) {
504  inside = true;
505  }
506  else {
507  for ( reach = area->reach; reach; reach = reach->next ) {
508  if ( obstacle->bounds.LineIntersection( rev_reach->end, reach->start ) ) {
509  inside = true;
510  break;
511  }
512  }
513  }
514 
515  if ( inside ) {
516  if ( enable ) {
517  rev_reach->disableCount--;
518  if ( rev_reach->disableCount <= 0 ) {
519  rev_reach->travelType &= ~TFL_INVALID;
520  rev_reach->disableCount = 0;
521  }
522  }
523  else {
524  rev_reach->travelType |= TFL_INVALID;
525  rev_reach->disableCount++;
526  }
527  }
528  }
529  }
530 }
531 
532 /*
533 ============
534 idAASLocal::AddObstacle
535 ============
536 */
538  idRoutingObstacle *obstacle;
539 
540  if ( !file ) {
541  return -1;
542  }
543 
544  obstacle = new idRoutingObstacle;
545  obstacle->bounds[0] = bounds[0] - file->GetSettings().boundingBoxes[0][1];
546  obstacle->bounds[1] = bounds[1] - file->GetSettings().boundingBoxes[0][0];
547  GetBoundsAreas_r( 1, obstacle->bounds, obstacle->areas );
548  SetObstacleState( obstacle, true );
549 
550  obstacleList.Append( obstacle );
551  return obstacleList.Num() - 1;
552 }
553 
554 /*
555 ============
556 idAASLocal::RemoveObstacle
557 ============
558 */
560  if ( !file ) {
561  return;
562  }
563  if ( ( handle >= 0 ) && ( handle < obstacleList.Num() ) ) {
564  SetObstacleState( obstacleList[handle], false );
565 
566  delete obstacleList[handle];
567  obstacleList.RemoveIndex( handle );
568  }
569 }
570 
571 /*
572 ============
573 idAASLocal::RemoveAllObstacles
574 ============
575 */
577  int i;
578 
579  if ( !file ) {
580  return;
581  }
582 
583  for ( i = 0; i < obstacleList.Num(); i++ ) {
584  SetObstacleState( obstacleList[i], false );
585  delete obstacleList[i];
586  }
588 }
589 
590 /*
591 ============
592 idAASLocal::LinkCache
593 
594  link the cache in the cache list sorted from oldest to newest cache
595 ============
596 */
597 void idAASLocal::LinkCache( idRoutingCache *cache ) const {
598 
599  // if the cache is already linked
600  if ( cache->time_next || cache->time_prev || cacheListStart == cache ) {
601  UnlinkCache( cache );
602  }
603 
604  totalCacheMemory += cache->Size();
605 
606  // add cache to the end of the list
607  cache->time_next = NULL;
608  cache->time_prev = cacheListEnd;
609  if ( cacheListEnd ) {
610  cacheListEnd->time_next = cache;
611  }
612  cacheListEnd = cache;
613  if ( !cacheListStart ) {
614  cacheListStart = cache;
615  }
616 }
617 
618 /*
619 ============
620 idAASLocal::UnlinkCache
621 ============
622 */
624 
625  totalCacheMemory -= cache->Size();
626 
627  // unlink the cache
628  if ( cache->time_next ) {
629  cache->time_next->time_prev = cache->time_prev;
630  } else {
631  cacheListEnd = cache->time_prev;
632  }
633  if ( cache->time_prev ) {
634  cache->time_prev->time_next = cache->time_next;
635  } else {
636  cacheListStart = cache->time_next;
637  }
638  cache->time_next = cache->time_prev = NULL;
639 }
640 
641 /*
642 ============
643 idAASLocal::DeleteOldestCache
644 ============
645 */
646 void idAASLocal::DeleteOldestCache( void ) const {
647  idRoutingCache *cache;
648 
650 
651  // unlink the oldest cache
652  cache = cacheListStart;
653  UnlinkCache( cache );
654 
655  // unlink the oldest cache from the area or portal cache index
656  if ( cache->next ) {
657  cache->next->prev = cache->prev;
658  }
659  if ( cache->prev ) {
660  cache->prev->next = cache->next;
661  }
662  else if ( cache->type == CACHETYPE_AREA ) {
663  areaCacheIndex[cache->cluster][ClusterAreaNum( cache->cluster, cache->areaNum )] = cache->next;
664  }
665  else if ( cache->type == CACHETYPE_PORTAL ) {
666  portalCacheIndex[cache->areaNum] = cache->next;
667  }
668 
669  delete cache;
670 }
671 
672 /*
673 ============
674 idAASLocal::GetAreaReachability
675 ============
676 */
677 idReachability *idAASLocal::GetAreaReachability( int areaNum, int reachabilityNum ) const {
678  idReachability *reach;
679 
680  for ( reach = file->GetArea( areaNum ).reach; reach; reach = reach->next ) {
681  if ( --reachabilityNum < 0 ) {
682  return reach;
683  }
684  }
685  return NULL;
686 }
687 
688 /*
689 ============
690 idAASLocal::ClusterAreaNum
691 ============
692 */
693 ID_INLINE int idAASLocal::ClusterAreaNum( int clusterNum, int areaNum ) const {
694  int side, areaCluster;
695 
696  areaCluster = file->GetArea( areaNum ).cluster;
697  if ( areaCluster > 0 ) {
698  return file->GetArea( areaNum ).clusterAreaNum;
699  }
700  else {
701  side = file->GetPortal( -areaCluster ).clusters[0] != clusterNum;
702  return file->GetPortal( -areaCluster ).clusterAreaNum[side];
703  }
704 }
705 
706 /*
707 ============
708 idAASLocal::UpdateAreaRoutingCache
709 ============
710 */
712  int i, nextAreaNum, cluster, badTravelFlags, clusterAreaNum, numReachableAreas;
713  unsigned short t, startAreaTravelTimes[MAX_REACH_PER_AREA];
714  idRoutingUpdate *updateListStart, *updateListEnd, *curUpdate, *nextUpdate;
715  idReachability *reach;
716  const aasArea_t *nextArea;
717 
718  // number of reachability areas within this cluster
719  numReachableAreas = file->GetCluster( areaCache->cluster ).numReachableAreas;
720 
721  // number of the start area within the cluster
722  clusterAreaNum = ClusterAreaNum( areaCache->cluster, areaCache->areaNum );
723  if ( clusterAreaNum >= numReachableAreas ) {
724  return;
725  }
726 
727  areaCache->travelTimes[clusterAreaNum] = areaCache->startTravelTime;
728  badTravelFlags = ~areaCache->travelFlags;
729  memset( startAreaTravelTimes, 0, sizeof( startAreaTravelTimes ) );
730 
731  // initialize first update
732  curUpdate = &areaUpdate[clusterAreaNum];
733  curUpdate->areaNum = areaCache->areaNum;
734  curUpdate->areaTravelTimes = startAreaTravelTimes;
735  curUpdate->tmpTravelTime = areaCache->startTravelTime;
736  curUpdate->next = NULL;
737  curUpdate->prev = NULL;
738  updateListStart = curUpdate;
739  updateListEnd = curUpdate;
740 
741  // while there are updates in the list
742  while( updateListStart ) {
743 
744  curUpdate = updateListStart;
745  if ( curUpdate->next ) {
746  curUpdate->next->prev = NULL;
747  }
748  else {
749  updateListEnd = NULL;
750  }
751  updateListStart = curUpdate->next;
752 
753  curUpdate->isInList = false;
754 
755  for ( i = 0, reach = file->GetArea( curUpdate->areaNum ).rev_reach; reach; reach = reach->rev_next, i++ ) {
756 
757  // if the reachability uses an undesired travel type
758  if ( reach->travelType & badTravelFlags ) {
759  continue;
760  }
761 
762  // next area the reversed reachability leads to
763  nextAreaNum = reach->fromAreaNum;
764  nextArea = &file->GetArea( nextAreaNum );
765 
766  // if traveling through the next area requires an undesired travel flag
767  if ( nextArea->travelFlags & badTravelFlags ) {
768  continue;
769  }
770 
771  // get the cluster number of the area
772  cluster = nextArea->cluster;
773  // don't leave the cluster, however do flood into cluster portals
774  if ( cluster > 0 && cluster != areaCache->cluster ) {
775  continue;
776  }
777 
778  // get the number of the area in the cluster
779  clusterAreaNum = ClusterAreaNum( areaCache->cluster, nextAreaNum );
780  if ( clusterAreaNum >= numReachableAreas ) {
781  continue; // should never happen
782  }
783 
784  assert( clusterAreaNum < areaCache->size );
785 
786  // time already travelled plus the traveltime through the current area
787  // plus the travel time of the reachability towards the next area
788  t = curUpdate->tmpTravelTime + curUpdate->areaTravelTimes[i] + reach->travelTime;
789 
790  if ( !areaCache->travelTimes[clusterAreaNum] || t < areaCache->travelTimes[clusterAreaNum] ) {
791 
792  areaCache->travelTimes[clusterAreaNum] = t;
793  areaCache->reachabilities[clusterAreaNum] = reach->number; // reversed reachability used to get into this area
794  nextUpdate = &areaUpdate[clusterAreaNum];
795  nextUpdate->areaNum = nextAreaNum;
796  nextUpdate->tmpTravelTime = t;
797  nextUpdate->areaTravelTimes = reach->areaTravelTimes;
798 
799  // if we are not allowed to fly
800  if ( badTravelFlags & TFL_FLY ) {
801  // avoid areas near ledges
802  if ( file->GetArea( nextAreaNum ).flags & AREA_LEDGE ) {
804  }
805  }
806 
807  if ( !nextUpdate->isInList ) {
808  nextUpdate->next = NULL;
809  nextUpdate->prev = updateListEnd;
810  if ( updateListEnd ) {
811  updateListEnd->next = nextUpdate;
812  }
813  else {
814  updateListStart = nextUpdate;
815  }
816  updateListEnd = nextUpdate;
817  nextUpdate->isInList = true;
818  }
819  }
820  }
821  }
822 }
823 
824 /*
825 ============
826 idAASLocal::GetAreaRoutingCache
827 ============
828 */
829 idRoutingCache *idAASLocal::GetAreaRoutingCache( int clusterNum, int areaNum, int travelFlags ) const {
830  int clusterAreaNum;
831  idRoutingCache *cache, *clusterCache;
832 
833  // number of the area in the cluster
834  clusterAreaNum = ClusterAreaNum( clusterNum, areaNum );
835  // pointer to the cache for the area in the cluster
836  clusterCache = areaCacheIndex[clusterNum][clusterAreaNum];
837  // check if cache without undesired travel flags already exists
838  for ( cache = clusterCache; cache; cache = cache->next ) {
839  if ( cache->travelFlags == travelFlags ) {
840  break;
841  }
842  }
843  // if no cache found
844  if ( !cache ) {
845  cache = new idRoutingCache( file->GetCluster( clusterNum ).numReachableAreas );
846  cache->type = CACHETYPE_AREA;
847  cache->cluster = clusterNum;
848  cache->areaNum = areaNum;
849  cache->startTravelTime = 1;
850  cache->travelFlags = travelFlags;
851  cache->prev = NULL;
852  cache->next = clusterCache;
853  if ( clusterCache ) {
854  clusterCache->prev = cache;
855  }
856  areaCacheIndex[clusterNum][clusterAreaNum] = cache;
857  UpdateAreaRoutingCache( cache );
858  }
859  LinkCache( cache );
860  return cache;
861 }
862 
863 /*
864 ============
865 idAASLocal::UpdatePortalRoutingCache
866 ============
867 */
869  int i, portalNum, clusterAreaNum;
870  unsigned short t;
871  const aasPortal_t *portal;
872  const aasCluster_t *cluster;
873  idRoutingCache *cache;
874  idRoutingUpdate *updateListStart, *updateListEnd, *curUpdate, *nextUpdate;
875 
876  curUpdate = &portalUpdate[ file->GetNumPortals() ];
877  curUpdate->cluster = portalCache->cluster;
878  curUpdate->areaNum = portalCache->areaNum;
879  curUpdate->tmpTravelTime = portalCache->startTravelTime;
880 
881  //put the area to start with in the current read list
882  curUpdate->next = NULL;
883  curUpdate->prev = NULL;
884  updateListStart = curUpdate;
885  updateListEnd = curUpdate;
886 
887  // while there are updates in the current list
888  while( updateListStart ) {
889 
890  curUpdate = updateListStart;
891  // remove the current update from the list
892  if ( curUpdate->next ) {
893  curUpdate->next->prev = NULL;
894  }
895  else {
896  updateListEnd = NULL;
897  }
898  updateListStart = curUpdate->next;
899  // current update is removed from the list
900  curUpdate->isInList = false;
901 
902  cluster = &file->GetCluster( curUpdate->cluster );
903  cache = GetAreaRoutingCache( curUpdate->cluster, curUpdate->areaNum, portalCache->travelFlags );
904 
905  // take all portals of the cluster
906  for ( i = 0; i < cluster->numPortals; i++ ) {
907  portalNum = file->GetPortalIndex( cluster->firstPortal + i );
908  assert( portalNum < portalCache->size );
909  portal = &file->GetPortal( portalNum );
910 
911  clusterAreaNum = ClusterAreaNum( curUpdate->cluster, portal->areaNum );
912  if ( clusterAreaNum >= cluster->numReachableAreas ) {
913  continue;
914  }
915 
916  t = cache->travelTimes[clusterAreaNum];
917  if ( t == 0 ) {
918  continue;
919  }
920  t += curUpdate->tmpTravelTime;
921 
922  if ( !portalCache->travelTimes[portalNum] || t < portalCache->travelTimes[portalNum] ) {
923 
924  portalCache->travelTimes[portalNum] = t;
925  portalCache->reachabilities[portalNum] = cache->reachabilities[clusterAreaNum];
926  nextUpdate = &portalUpdate[portalNum];
927  if ( portal->clusters[0] == curUpdate->cluster ) {
928  nextUpdate->cluster = portal->clusters[1];
929  }
930  else {
931  nextUpdate->cluster = portal->clusters[0];
932  }
933  nextUpdate->areaNum = portal->areaNum;
934  // add travel time through the actual portal area for the next update
935  nextUpdate->tmpTravelTime = t + portal->maxAreaTravelTime;
936 
937  if ( !nextUpdate->isInList ) {
938 
939  nextUpdate->next = NULL;
940  nextUpdate->prev = updateListEnd;
941  if ( updateListEnd ) {
942  updateListEnd->next = nextUpdate;
943  }
944  else {
945  updateListStart = nextUpdate;
946  }
947  updateListEnd = nextUpdate;
948  nextUpdate->isInList = true;
949  }
950  }
951  }
952  }
953 }
954 
955 /*
956 ============
957 idAASLocal::GetPortalRoutingCache
958 ============
959 */
960 idRoutingCache *idAASLocal::GetPortalRoutingCache( int clusterNum, int areaNum, int travelFlags ) const {
961  idRoutingCache *cache;
962 
963  // check if cache without undesired travel flags already exists
964  for ( cache = portalCacheIndex[areaNum]; cache; cache = cache->next ) {
965  if ( cache->travelFlags == travelFlags ) {
966  break;
967  }
968  }
969  // if no cache found
970  if ( !cache ) {
971  cache = new idRoutingCache( file->GetNumPortals() );
972  cache->type = CACHETYPE_PORTAL;
973  cache->cluster = clusterNum;
974  cache->areaNum = areaNum;
975  cache->startTravelTime = 1;
976  cache->travelFlags = travelFlags;
977  cache->prev = NULL;
978  cache->next = portalCacheIndex[areaNum];
979  if ( portalCacheIndex[areaNum] ) {
980  portalCacheIndex[areaNum]->prev = cache;
981  }
982  portalCacheIndex[areaNum] = cache;
983  UpdatePortalRoutingCache( cache );
984  }
985  LinkCache( cache );
986  return cache;
987 }
988 
989 /*
990 ============
991 idAASLocal::RouteToGoalArea
992 ============
993 */
994 bool idAASLocal::RouteToGoalArea( int areaNum, const idVec3 origin, int goalAreaNum, int travelFlags, int &travelTime, idReachability **reach ) const {
995  int clusterNum, goalClusterNum, portalNum, i, clusterAreaNum;
996  unsigned short int t, bestTime;
997  const aasPortal_t *portal;
998  const aasCluster_t *cluster;
999  idRoutingCache *areaCache, *portalCache, *clusterCache;
1000  idReachability *bestReach, *r, *nextr;
1001 
1002  travelTime = 0;
1003  *reach = NULL;
1004 
1005  if ( !file ) {
1006  return false;
1007  }
1008 
1009  if ( areaNum == goalAreaNum ) {
1010  return true;
1011  }
1012 
1013  if ( areaNum <= 0 || areaNum >= file->GetNumAreas() ) {
1014  gameLocal.Printf( "RouteToGoalArea: areaNum %d out of range\n", areaNum );
1015  return false;
1016  }
1017  if ( goalAreaNum <= 0 || goalAreaNum >= file->GetNumAreas() ) {
1018  gameLocal.Printf( "RouteToGoalArea: goalAreaNum %d out of range\n", goalAreaNum );
1019  return false;
1020  }
1021 
1024  }
1025 
1026  clusterNum = file->GetArea( areaNum ).cluster;
1027  goalClusterNum = file->GetArea( goalAreaNum ).cluster;
1028 
1029  // if the source area is a cluster portal, read directly from the portal cache
1030  if ( clusterNum < 0 ) {
1031  // if the goal area is a portal
1032  if ( goalClusterNum < 0 ) {
1033  // just assume the goal area is part of the front cluster
1034  portal = &file->GetPortal( -goalClusterNum );
1035  goalClusterNum = portal->clusters[0];
1036  }
1037  // get the portal routing cache
1038  portalCache = GetPortalRoutingCache( goalClusterNum, goalAreaNum, travelFlags );
1039  *reach = GetAreaReachability( areaNum, portalCache->reachabilities[-clusterNum] );
1040  travelTime = portalCache->travelTimes[-clusterNum] + AreaTravelTime( areaNum, origin, (*reach)->start );
1041  return true;
1042  }
1043 
1044  bestTime = 0;
1045  bestReach = NULL;
1046 
1047  // check if the goal area is a portal of the source area cluster
1048  if ( goalClusterNum < 0 ) {
1049  portal = &file->GetPortal( -goalClusterNum );
1050  if ( portal->clusters[0] == clusterNum || portal->clusters[1] == clusterNum) {
1051  goalClusterNum = clusterNum;
1052  }
1053  }
1054 
1055  // if both areas are in the same cluster
1056  if ( clusterNum > 0 && goalClusterNum > 0 && clusterNum == goalClusterNum ) {
1057  clusterCache = GetAreaRoutingCache( clusterNum, goalAreaNum, travelFlags );
1058  clusterAreaNum = ClusterAreaNum( clusterNum, areaNum );
1059  if ( clusterCache->travelTimes[clusterAreaNum] ) {
1060  bestReach = GetAreaReachability( areaNum, clusterCache->reachabilities[clusterAreaNum] );
1061  bestTime = clusterCache->travelTimes[clusterAreaNum] + AreaTravelTime( areaNum, origin, bestReach->start );
1062  }
1063  else {
1064  clusterCache = NULL;
1065  }
1066  }
1067  else {
1068  clusterCache = NULL;
1069  }
1070 
1071  clusterNum = file->GetArea( areaNum ).cluster;
1072  goalClusterNum = file->GetArea( goalAreaNum ).cluster;
1073 
1074  // if the goal area is a portal
1075  if ( goalClusterNum < 0 ) {
1076  // just assume the goal area is part of the front cluster
1077  portal = &file->GetPortal( -goalClusterNum );
1078  goalClusterNum = portal->clusters[0];
1079  }
1080  // get the portal routing cache
1081  portalCache = GetPortalRoutingCache( goalClusterNum, goalAreaNum, travelFlags );
1082 
1083  // the cluster the area is in
1084  cluster = &file->GetCluster( clusterNum );
1085  // current area inside the current cluster
1086  clusterAreaNum = ClusterAreaNum( clusterNum, areaNum );
1087  // if the area is not a reachable area
1088  if ( clusterAreaNum >= cluster->numReachableAreas) {
1089  return false;
1090  }
1091 
1092  // find the portal of the source area cluster leading towards the goal area
1093  for ( i = 0; i < cluster->numPortals; i++ ) {
1094  portalNum = file->GetPortalIndex( cluster->firstPortal + i );
1095 
1096  // if the goal area isn't reachable from the portal
1097  if ( !portalCache->travelTimes[portalNum] ) {
1098  continue;
1099  }
1100 
1101  portal = &file->GetPortal( portalNum );
1102  // get the cache of the portal area
1103  areaCache = GetAreaRoutingCache( clusterNum, portal->areaNum, travelFlags );
1104  // if the portal is not reachable from this area
1105  if ( !areaCache->travelTimes[clusterAreaNum] ) {
1106  continue;
1107  }
1108 
1109  r = GetAreaReachability( areaNum, areaCache->reachabilities[clusterAreaNum] );
1110 
1111  if ( clusterCache ) {
1112  // if the next reachability from the portal leads back into the cluster
1113  nextr = GetAreaReachability( portal->areaNum, portalCache->reachabilities[portalNum] );
1114  if ( file->GetArea( nextr->toAreaNum ).cluster < 0 || file->GetArea( nextr->toAreaNum ).cluster == clusterNum ) {
1115  continue;
1116  }
1117  }
1118 
1119  // the total travel time is the travel time from the portal area to the goal area
1120  // plus the travel time from the source area towards the portal area
1121  t = portalCache->travelTimes[portalNum] + areaCache->travelTimes[clusterAreaNum];
1122  // NOTE: Should add the exact travel time through the portal area.
1123  // However we add the largest travel time through the portal area.
1124  // We cannot directly calculate the exact travel time through the portal area
1125  // because the reachability used to travel into the portal area is not known.
1126  t += portal->maxAreaTravelTime;
1127 
1128  // if the time is better than the one already found
1129  if ( !bestTime || t < bestTime ) {
1130  bestReach = r;
1131  bestTime = t;
1132  }
1133  }
1134 
1135  if ( !bestReach ) {
1136  return false;
1137  }
1138 
1139  *reach = bestReach;
1140  travelTime = bestTime;
1141 
1142  return true;
1143 }
1144 
1145 /*
1146 ============
1147 idAASLocal::TravelTimeToGoalArea
1148 ============
1149 */
1150 int idAASLocal::TravelTimeToGoalArea( int areaNum, const idVec3 &origin, int goalAreaNum, int travelFlags ) const {
1151  int travelTime;
1152  idReachability *reach;
1153 
1154  if ( !file ) {
1155  return 0;
1156  }
1157 
1158  if ( !RouteToGoalArea( areaNum, origin, goalAreaNum, travelFlags, travelTime, &reach ) ) {
1159  return 0;
1160  }
1161  return travelTime;
1162 }
1163 
1164 /*
1165 ============
1166 idAASLocal::FindNearestGoal
1167 ============
1168 */
1169 bool idAASLocal::FindNearestGoal( aasGoal_t &goal, int areaNum, const idVec3 origin, const idVec3 &target, int travelFlags, aasObstacle_t *obstacles, int numObstacles, idAASCallback &callback ) const {
1170  int i, j, k, badTravelFlags, nextAreaNum, bestAreaNum;
1171  unsigned short t, bestTravelTime;
1172  idRoutingUpdate *updateListStart, *updateListEnd, *curUpdate, *nextUpdate;
1173  idReachability *reach;
1174  const aasArea_t *nextArea;
1175  idVec3 v1, v2, p;
1176  float targetDist, dist;
1177 
1178  if ( file == NULL || areaNum <= 0 ) {
1179  goal.areaNum = areaNum;
1180  goal.origin = origin;
1181  return false;
1182  }
1183 
1184  // if the first area is valid goal, just return the origin
1185  if ( callback.TestArea( this, areaNum ) ) {
1186  goal.areaNum = areaNum;
1187  goal.origin = origin;
1188  return true;
1189  }
1190 
1191  // setup obstacles
1192  for ( k = 0; k < numObstacles; k++ ) {
1193  obstacles[k].expAbsBounds[0] = obstacles[k].absBounds[0] - file->GetSettings().boundingBoxes[0][1];
1194  obstacles[k].expAbsBounds[1] = obstacles[k].absBounds[1] - file->GetSettings().boundingBoxes[0][0];
1195  }
1196 
1197  badTravelFlags = ~travelFlags;
1198  SIMDProcessor->Memset( goalAreaTravelTimes, 0, file->GetNumAreas() * sizeof( unsigned short ) );
1199 
1200  targetDist = (target - origin).Length();
1201 
1202  // initialize first update
1203  curUpdate = &areaUpdate[areaNum];
1204  curUpdate->areaNum = areaNum;
1205  curUpdate->tmpTravelTime = 0;
1206  curUpdate->start = origin;
1207  curUpdate->next = NULL;
1208  curUpdate->prev = NULL;
1209  updateListStart = curUpdate;
1210  updateListEnd = curUpdate;
1211 
1212  bestTravelTime = 0;
1213  bestAreaNum = 0;
1214 
1215  // while there are updates in the list
1216  while ( updateListStart ) {
1217 
1218  curUpdate = updateListStart;
1219  if ( curUpdate->next ) {
1220  curUpdate->next->prev = NULL;
1221  }
1222  else {
1223  updateListEnd = NULL;
1224  }
1225  updateListStart = curUpdate->next;
1226 
1227  curUpdate->isInList = false;
1228 
1229  // if we already found a closer location
1230  if ( bestTravelTime && curUpdate->tmpTravelTime >= bestTravelTime ) {
1231  continue;
1232  }
1233 
1234  for ( i = 0, reach = file->GetArea( curUpdate->areaNum ).reach; reach; reach = reach->next, i++ ) {
1235 
1236  // if the reachability uses an undesired travel type
1237  if ( reach->travelType & badTravelFlags ) {
1238  continue;
1239  }
1240 
1241  // next area the reversed reachability leads to
1242  nextAreaNum = reach->toAreaNum;
1243  nextArea = &file->GetArea( nextAreaNum );
1244 
1245  // if traveling through the next area requires an undesired travel flag
1246  if ( nextArea->travelFlags & badTravelFlags ) {
1247  continue;
1248  }
1249 
1250  t = curUpdate->tmpTravelTime +
1251  AreaTravelTime( curUpdate->areaNum, curUpdate->start, reach->start ) +
1252  reach->travelTime;
1253 
1254  // project target origin onto movement vector through the area
1255  v1 = reach->end - curUpdate->start;
1256  v1.Normalize();
1257  v2 = target - curUpdate->start;
1258  p = curUpdate->start + (v2 * v1) * v1;
1259 
1260  // get the point on the path closest to the target
1261  for ( j = 0; j < 3; j++ ) {
1262  if ( (p[j] > curUpdate->start[j] + 0.1f && p[j] > reach->end[j] + 0.1f) ||
1263  (p[j] < curUpdate->start[j] - 0.1f && p[j] < reach->end[j] - 0.1f) ) {
1264  break;
1265  }
1266  }
1267  if ( j >= 3 ) {
1268  dist = (target - p).Length();
1269  } else {
1270  dist = (target - reach->end).Length();
1271  }
1272 
1273  // avoid moving closer to the target
1274  if ( dist < targetDist ) {
1275  t += ( targetDist - dist ) * 10;
1276  }
1277 
1278  // if we already found a closer location
1279  if ( bestTravelTime && t >= bestTravelTime ) {
1280  continue;
1281  }
1282 
1283  // if this is not the best path towards the next area
1284  if ( goalAreaTravelTimes[nextAreaNum] && t >= goalAreaTravelTimes[nextAreaNum] ) {
1285  continue;
1286  }
1287 
1288  // path may not go through any obstacles
1289  for ( k = 0; k < numObstacles; k++ ) {
1290  // if the movement vector intersects the expanded obstacle bounds
1291  if ( obstacles[k].expAbsBounds.LineIntersection( curUpdate->start, reach->end ) ) {
1292  break;
1293  }
1294  }
1295  if ( k < numObstacles ) {
1296  continue;
1297  }
1298 
1299  goalAreaTravelTimes[nextAreaNum] = t;
1300  nextUpdate = &areaUpdate[nextAreaNum];
1301  nextUpdate->areaNum = nextAreaNum;
1302  nextUpdate->tmpTravelTime = t;
1303  nextUpdate->start = reach->end;
1304 
1305  // if we are not allowed to fly
1306  if ( badTravelFlags & TFL_FLY ) {
1307  // avoid areas near ledges
1308  if ( file->GetArea( nextAreaNum ).flags & AREA_LEDGE ) {
1309  nextUpdate->tmpTravelTime += LEDGE_TRAVELTIME_PANALTY;
1310  }
1311  }
1312 
1313  if ( !nextUpdate->isInList ) {
1314  nextUpdate->next = NULL;
1315  nextUpdate->prev = updateListEnd;
1316  if ( updateListEnd ) {
1317  updateListEnd->next = nextUpdate;
1318  } else {
1319  updateListStart = nextUpdate;
1320  }
1321  updateListEnd = nextUpdate;
1322  nextUpdate->isInList = true;
1323  }
1324 
1325  // don't put goal near a ledge
1326  if ( !( nextArea->flags & AREA_LEDGE ) ) {
1327 
1328  // add travel time through the area
1329  t += AreaTravelTime( reach->toAreaNum, reach->end, nextArea->center );
1330 
1331  if ( !bestTravelTime || t < bestTravelTime ) {
1332  // if the area is not visible to the target
1333  if ( callback.TestArea( this, reach->toAreaNum ) ) {
1334  bestTravelTime = t;
1335  bestAreaNum = reach->toAreaNum;
1336  }
1337  }
1338  }
1339  }
1340  }
1341 
1342  if ( bestAreaNum ) {
1343  goal.areaNum = bestAreaNum;
1344  goal.origin = AreaCenter( bestAreaNum );
1345  return true;
1346  }
1347 
1348  return false;
1349 }
idRoutingCache * GetPortalRoutingCache(int clusterNum, int areaNum, int travelFlags) const
void ShutdownRoutingCache(void)
unsigned short contents
Definition: AASFile.h:161
unsigned short maxAreaTravelTime
Definition: AASFile.h:180
idBounds absBounds
Definition: AAS.h:63
float Normalize(void)
Definition: Vector.h:646
#define LEDGE_TRAVELTIME_PANALTY
Definition: AAS_routing.cpp:40
const idAASSettings & GetSettings(void) const
Definition: AASFile.h:312
unsigned short * goalAreaTravelTimes
Definition: AAS_local.h:133
int children[2]
Definition: AASFile.h:172
assert(prefInfo.fullscreenBtn)
idVec3 center
Definition: AASFile.h:159
short toAreaNum
Definition: AASFile.h:96
void Printf(const char *fmt,...) const id_attribute((format(printf
Definition: Game_local.cpp:699
idReachability * rev_next
Definition: AASFile.h:105
bool SetAreaState_r(int nodeNum, const idBounds &bounds, const int areaContents, bool disabled)
void DeletePortalCache(void)
idList< idRoutingObstacle * > obstacleList
Definition: AAS_local.h:139
short fromAreaNum
Definition: AASFile.h:97
const aasPortal_t & GetPortal(int index)
Definition: AASFile.h:306
void void void void void Error(const char *fmt,...) const id_attribute((format(printf
Definition: Game_local.cpp:783
int areaNum
Definition: AAS.h:57
void RoutingStats(void) const
unsigned char * reachabilities
Definition: AAS_local.h:56
idList< int > areas
Definition: AAS_local.h:82
idRoutingCache * next
Definition: AAS_local.h:51
idRoutingCache * cacheListEnd
Definition: AAS_local.h:137
GLenum GLsizei n
Definition: glext.h:3705
idReachability * GetAreaReachability(int areaNum, int reachabilityNum) const
Definition: AAS.h:56
prefInfo callback
int numAreaTravelTimes
Definition: AAS_local.h:135
idRoutingUpdate * prev
Definition: AAS_local.h:71
idReachability * reach
Definition: AASFile.h:165
Definition: Vector.h:316
const aasCluster_t & GetCluster(int index) const
Definition: AASFile.h:310
short areaNum
Definition: AASFile.h:177
idRoutingCache * cacheListStart
Definition: AAS_local.h:136
GLuint GLuint GLsizei GLenum type
Definition: glext.h:2845
void SetObstacleState(const idRoutingObstacle *obstacle, bool enable)
idRoutingUpdate * portalUpdate
Definition: AAS_local.h:132
#define AREA_REACHABLE_FLY
Definition: AASFile.h:75
void GetBoundsAreas_r(int nodeNum, const idBounds &bounds, idList< int > &areas) const
virtual void VPCALL Memset(void *dst, const int val, const int count)=0
idRoutingUpdate * next
Definition: AAS_local.h:70
idRoutingCache(int size)
Definition: AAS_routing.cpp:47
void ShutdownRouting(void)
idBounds boundingBoxes[MAX_AAS_BOUNDING_BOXES]
Definition: AASFile.h:215
short cluster
Definition: AASFile.h:162
int i
Definition: process.py:33
idRoutingUpdate * areaUpdate
Definition: AAS_local.h:131
idVec3 start
Definition: AASFile.h:98
~idRoutingCache(void)
Definition: AAS_routing.cpp:67
short clusterAreaNum
Definition: AASFile.h:163
unsigned short * areaTravelTimes
Definition: AASFile.h:106
int areaCacheIndexSize
Definition: AAS_local.h:128
int portalCacheIndexSize
Definition: AAS_local.h:130
idRoutingCache * time_prev
Definition: AAS_local.h:54
#define CACHETYPE_AREA
Definition: AAS_routing.cpp:35
idAASFile * file
Definition: AAS_local.h:123
int GetNumPortals(void) const
Definition: AASFile.h:305
unsigned short planeNum
Definition: AASFile.h:171
unsigned short flags
Definition: AASFile.h:160
unsigned short startTravelTime
Definition: AAS_local.h:55
#define PLANESIDE_FRONT
Definition: Plane.h:53
void SetupRoutingCache(void)
void SetAreaTravelFlag(int index, int flag)
Definition: AASFile.h:315
GLfloat GLfloat GLfloat v2
Definition: glext.h:3608
idBounds expAbsBounds
Definition: AAS.h:64
void CalculateAreaTravelTimes(void)
int travelType
Definition: AASFile.h:95
#define TFL_FLY
Definition: AASFile.h:55
unsigned short travelTime
Definition: AASFile.h:101
short clusters[2]
Definition: AASFile.h:178
int numPortals
Definition: AASFile.h:187
idVec3 origin
Definition: AAS.h:58
virtual void RemoveAllObstacles(void)
static int FtoiFast(float f)
Definition: Math.h:801
const aasNode_t & GetNode(int index) const
Definition: AASFile.h:304
virtual aasHandle_t AddObstacle(const idBounds &bounds)
GLuint GLuint end
Definition: glext.h:2845
unsigned short * travelTimes
Definition: AAS_local.h:57
virtual bool RouteToGoalArea(int areaNum, const idVec3 origin, int goalAreaNum, int travelFlags, int &travelTime, idReachability **reach) const
#define TFL_CROUCH
Definition: AASFile.h:46
unsigned short * areaTravelTimes
Definition: AAS_local.h:134
idVec3 end
Definition: AASFile.h:99
#define PLANESIDE_BACK
Definition: Plane.h:54
#define NULL
Definition: Lib.h:88
unsigned short tmpTravelTime
Definition: AAS_local.h:67
#define MAX_REACH_PER_AREA
Definition: AASFile.h:87
int GetNumAreas(void) const
Definition: AASFile.h:301
int totalCacheMemory
Definition: AAS_local.h:138
virtual void RemoveObstacle(const aasHandle_t handle)
#define CACHETYPE_PORTAL
Definition: AAS_routing.cpp:36
#define AREA_LEDGE
Definition: AASFile.h:70
virtual bool FindNearestGoal(aasGoal_t &goal, int areaNum, const idVec3 origin, const idVec3 &target, int travelFlags, aasObstacle_t *obstacles, int numObstacles, idAASCallback &callback) const
void UpdatePortalRoutingCache(idRoutingCache *portalCache) const
idReachability * next
Definition: AASFile.h:104
int aasHandle_t
Definition: AAS.h:73
void Mem_Free(void *ptr)
Definition: Heap.cpp:1087
idVec3 start
Definition: AAS_local.h:69
bool SetupRouting(void)
int firstPortal
Definition: AASFile.h:188
unsigned short * areaTravelTimes
Definition: AAS_local.h:68
idGameLocal gameLocal
Definition: Game_local.cpp:64
void SetPortalMaxTravelTime(int index, int time)
Definition: AASFile.h:314
const aasIndex_t & GetPortalIndex(int index) const
Definition: AASFile.h:308
#define TFL_WATER
Definition: AASFile.h:57
GLfloat GLfloat v1
Definition: glext.h:3607
int Append(const type &obj)
Definition: List.h:646
GLdouble GLdouble GLdouble r
Definition: glext.h:2951
bool LineIntersection(const idVec3 &start, const idVec3 &end) const
Definition: Bounds.cpp:135
idReachability * rev_reach
Definition: AASFile.h:166
idBounds bounds
Definition: AAS_local.h:81
tuple f
Definition: idal.py:89
int Size(void) const
Definition: AAS_routing.cpp:77
short clusterAreaNum[2]
Definition: AASFile.h:179
void RemoveAreaTravelFlag(int index, int flag)
Definition: AASFile.h:316
int Num(void) const
Definition: List.h:265
#define AREA_REACHABLE_WALK
Definition: AASFile.h:74
bool RemoveIndex(int index)
Definition: List.h:849
unsigned char byte
Definition: Lib.h:75
idRoutingCache * time_next
Definition: AAS_local.h:53
void RemoveRoutingCacheUsingArea(int areaNum)
byte disableCount
Definition: AASFile.h:103
GLsizeiptr size
Definition: glext.h:3112
#define TFL_INVALID
Definition: AASFile.h:44
void UnlinkCache(idRoutingCache *cache) const
idRoutingCache *** areaCacheIndex
Definition: AAS_local.h:127
void UpdateAreaRoutingCache(idRoutingCache *areaCache) const
#define MAX_ROUTING_CACHE_MEMORY
Definition: AAS_routing.cpp:38
void * Mem_ClearedAlloc(const int size)
Definition: Heap.cpp:1149
GLuint res
Definition: glext.h:5385
int numReachableAreas
Definition: AASFile.h:186
unsigned short AreaTravelTime(int areaNum, const idVec3 &start, const idVec3 &end) const
Definition: AAS_routing.cpp:86
void EnableArea(int areaNum)
void * Mem_Alloc(const int size)
Definition: Heap.cpp:1067
void DeleteClusterCache(int clusterNum)
GLint j
Definition: qgl.h:264
const idPlane & GetPlane(int index) const
Definition: AASFile.h:290
idRoutingCache * prev
Definition: AAS_local.h:52
virtual bool TestArea(const class idAAS *aas, int areaNum)=0
void DeleteOldestCache(void) const
int PlaneSide(const idPlane &plane, const float epsilon=ON_EPSILON) const
Definition: Bounds.cpp:108
int GetNumClusters(void) const
Definition: AASFile.h:309
GLfloat GLfloat p
Definition: glext.h:4674
void LinkCache(idRoutingCache *cache) const
const aasArea_t & GetArea(int index)
Definition: AASFile.h:302
void DeleteAreaTravelTimes(void)
bool ContainsPoint(const idVec3 &p) const
Definition: Bounds.h:353
void DisableArea(int areaNum)
virtual bool SetAreaState(const idBounds &bounds, const int areaContents, bool disabled)
int travelFlags
Definition: AASFile.h:164
idRoutingCache * GetAreaRoutingCache(int clusterNum, int areaNum, int travelFlags) const
GLuint start
Definition: glext.h:2845
int ClusterAreaNum(int clusterNum, int areaNum) const
virtual idVec3 AreaCenter(int areaNum) const
Definition: AAS.cpp:187
GLdouble GLdouble t
Definition: glext.h:2943
idRoutingCache ** portalCacheIndex
Definition: AAS_local.h:129
void Clear(void)
Definition: List.h:184
idSIMDProcessor * SIMDProcessor
Definition: Simd.cpp:43
virtual int TravelTimeToGoalArea(int areaNum, const idVec3 &origin, int goalAreaNum, int travelFlags) const