neo/game/ai/AAS_routing.cpp

   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 */
  47 idRoutingCache::idRoutingCache( int size ) {
  48         areaNum = 0;
  49         cluster = 0;
  50         next = prev = NULL;
  51         time_next = time_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 */
  67 idRoutingCache::~idRoutingCache( void ) {
  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 */
 109 void idAASLocal::CalculateAreaTravelTimes(void) {
 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
 118                 if ( !(file->GetArea( n ).flags & (AREA_REACHABLE_WALK|AREA_REACHABLE_FLY)) ) {
 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
 139                 if ( !(file->GetArea( n ).flags & (AREA_REACHABLE_WALK|AREA_REACHABLE_FLY)) ) {
 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
 166                         file->SetPortalMaxTravelTime( -file->GetArea( n ).cluster, maxt );
 167                 }
 168         }
 169
 170         assert( ( (unsigned int) bytePtr - (unsigned int) areaTravelTimes ) <= numAreaTravelTimes * sizeof( unsigned short ) );
 171 }
 172
 173 /*
 174 ============
 175 idAASLocal::DeleteAreaTravelTimes
 176 ============
 177 */
 178 void idAASLocal::DeleteAreaTravelTimes( void ) {
 179         Mem_Free( areaTravelTimes );
 180         areaTravelTimes = NULL;
 181         numAreaTravelTimes = 0;
 182 }
 183
 184 /*
 185 ============
 186 idAASLocal::SetupRoutingCache
 187 ============
 188 */
 189 void idAASLocal::SetupRoutingCache( void ) {
 190         int i;
 191         byte *bytePtr;
 192
 193         areaCacheIndexSize = 0;
 194         for ( i = 0; i < file->GetNumClusters(); i++ ) {
 195                 areaCacheIndexSize += file->GetCluster( i ).numReachableAreas;
 196         }
 197         areaCacheIndex = (idRoutingCache ***) Mem_ClearedAlloc( file->GetNumClusters() * sizeof( idRoutingCache ** ) +
 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
 205         portalCacheIndexSize = file->GetNumAreas();
 206         portalCacheIndex = (idRoutingCache **) Mem_ClearedAlloc( portalCacheIndexSize * sizeof( idRoutingCache * ) );
 207
 208         areaUpdate = (idRoutingUpdate *) Mem_ClearedAlloc( file->GetNumAreas() * sizeof( idRoutingUpdate ) );
 209         portalUpdate = (idRoutingUpdate *) Mem_ClearedAlloc( (file->GetNumPortals()+1) * sizeof( idRoutingUpdate ) );
 210
 211         goalAreaTravelTimes = (unsigned short *) Mem_ClearedAlloc( file->GetNumAreas() * sizeof( unsigned short ) );
 212
 213         cacheListStart = cacheListEnd = NULL;
 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 */
 240 void idAASLocal::DeletePortalCache( void ) {
 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 */
 258 void idAASLocal::ShutdownRoutingCache( void ) {
 259         int i;
 260
 261         for ( i = 0; i < file->GetNumClusters(); i++ ) {
 262                 DeleteClusterCache( i );
 263         }
 264
 265         DeletePortalCache();
 266
 267         Mem_Free( areaCacheIndex );
 268         areaCacheIndex = NULL;
 269         areaCacheIndexSize = 0;
 270         Mem_Free( portalCacheIndex );
 271         portalCacheIndex = NULL;
 272         portalCacheIndexSize = 0;
 273         Mem_Free( areaUpdate );
 274         areaUpdate = NULL;
 275         Mem_Free( portalUpdate );
 276         portalUpdate = NULL;
 277         Mem_Free( goalAreaTravelTimes );
 278         goalAreaTravelTimes = NULL;
 279
 280         cacheListStart = cacheListEnd = NULL;
 281         totalCacheMemory = 0;
 282 }
 283
 284 /*
 285 ============
 286 idAASLocal::SetupRouting
 287 ============
 288 */
 289 bool idAASLocal::SetupRouting( void ) {
 290         CalculateAreaTravelTimes();
 291         SetupRoutingCache();
 292         return true;
 293 }
 294
 295 /*
 296 ============
 297 idAASLocal::ShutdownRouting
 298 ============
 299 */
 300 void idAASLocal::ShutdownRouting( void ) {
 301         DeleteAreaTravelTimes();
 302         ShutdownRoutingCache();
 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 */
 340 void idAASLocal::RemoveRoutingCacheUsingArea( int areaNum ) {
 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         }
 353         DeletePortalCache();
 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
 385         file->RemoveAreaTravelFlag( areaNum, TFL_INVALID );
 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 */
 537 aasHandle_t idAASLocal::AddObstacle( const idBounds &bounds ) {
 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 */
 559 void idAASLocal::RemoveObstacle( const aasHandle_t handle ) {
 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 */
 576 void idAASLocal::RemoveAllObstacles( void ) {
 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         }
 587         obstacleList.Clear();
 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 */
 623 void idAASLocal::UnlinkCache( idRoutingCache *cache ) const {
 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
 649         assert( cacheListStart );
 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 */
 711 void idAASLocal::UpdateAreaRoutingCache( idRoutingCache *areaCache ) const {
 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 ) {
 803                                                 nextUpdate->tmpTravelTime += LEDGE_TRAVELTIME_PANALTY;
 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 */
 868 void idAASLocal::UpdatePortalRoutingCache( idRoutingCache *portalCache ) const {
 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
1022         while( totalCacheMemory > MAX_ROUTING_CACHE_MEMORY ) {
1023                 DeleteOldestCache();
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 }