neo/game/ai/AAS_pathing.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
  34 #define SUBSAMPLE_WALK_PATH             1
  35 #define SUBSAMPLE_FLY_PATH              0
  36
  37 const int               maxWalkPathIterations           = 10;
  38 const float             maxWalkPathDistance                     = 500.0f;
  39 const float             walkPathSampleDistance          = 8.0f;
  40
  41 const int               maxFlyPathIterations            = 10;
  42 const float             maxFlyPathDistance                      = 500.0f;
  43 const float             flyPathSampleDistance           = 8.0f;
  44
  45
  46 /*
  47 ============
  48 idAASLocal::EdgeSplitPoint
  49
  50   calculates split point of the edge with the plane
  51   returns true if the split point is between the edge vertices
  52 ============
  53 */
  54 bool idAASLocal::EdgeSplitPoint( idVec3 &split, int edgeNum, const idPlane &plane ) const {
  55         const aasEdge_t *edge;
  56         idVec3 v1, v2;
  57         float d1, d2;
  58
  59         edge = &file->GetEdge( edgeNum );
  60         v1 = file->GetVertex( edge->vertexNum[0] );
  61         v2 = file->GetVertex( edge->vertexNum[1] );
  62         d1 = v1 * plane.Normal() - plane.Dist();
  63         d2 = v2 * plane.Normal() - plane.Dist();
  64
  65         //if ( (d1 < CM_CLIP_EPSILON && d2 < CM_CLIP_EPSILON) || (d1 > -CM_CLIP_EPSILON && d2 > -CM_CLIP_EPSILON) ) {
  66         if ( FLOATSIGNBITSET( d1 ) == FLOATSIGNBITSET( d2 ) ) {
  67                 return false;
  68         }
  69         split = v1 + (d1 / (d1 - d2)) * (v2 - v1);
  70         return true;
  71 }
  72
  73 /*
  74 ============
  75 idAASLocal::FloorEdgeSplitPoint
  76
  77   calculates either the closest or furthest point on the floor of the area which also lies on the pathPlane
  78   the point has to be on the front side of the frontPlane to be valid
  79 ============
  80 */
  81 bool idAASLocal::FloorEdgeSplitPoint( idVec3 &bestSplit, int areaNum, const idPlane &pathPlane, const idPlane &frontPlane, bool closest ) const {
  82         int i, j, faceNum, edgeNum;
  83         const aasArea_t *area;
  84         const aasFace_t *face;
  85         idVec3 split;
  86         float dist, bestDist;
  87
  88         if ( closest ) {
  89                 bestDist = maxWalkPathDistance;
  90         } else {
  91                 bestDist = -0.1f;
  92         }
  93
  94         area = &file->GetArea( areaNum );
  95
  96         for ( i = 0; i < area->numFaces; i++ ) {
  97                 faceNum = file->GetFaceIndex( area->firstFace + i );
  98                 face = &file->GetFace( abs(faceNum) );
  99
 100                 if ( !(face->flags & FACE_FLOOR ) ) {
 101                         continue;
 102                 }
 103
 104                 for ( j = 0; j < face->numEdges; j++ ) {
 105                         edgeNum = file->GetEdgeIndex( face->firstEdge + j );
 106
 107                         if ( !EdgeSplitPoint( split, abs( edgeNum ), pathPlane ) ) {
 108                                 continue;
 109                         }
 110                         dist = frontPlane.Distance( split );
 111                         if ( closest ) {
 112                                 if ( dist >= -0.1f && dist < bestDist ) {
 113                                         bestDist = dist;
 114                                         bestSplit = split;
 115                                 }
 116                         } else {
 117                                 if ( dist > bestDist ) {
 118                                         bestDist = dist;
 119                                         bestSplit = split;
 120                                 }
 121                         }
 122                 }
 123         }
 124
 125         if ( closest ) {
 126                 return ( bestDist < maxWalkPathDistance );
 127         } else {
 128                 return ( bestDist > -0.1f );
 129         }
 130 }
 131
 132 /*
 133 ============
 134 idAASLocal::WalkPathValid
 135
 136   returns true if one can walk in a straight line between origin and goalOrigin
 137 ============
 138 */
 139 bool idAASLocal::WalkPathValid( int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags, idVec3 &endPos, int &endAreaNum ) const {
 140         int curAreaNum, lastAreaNum, lastAreas[4], lastAreaIndex;
 141         idPlane pathPlane, frontPlane, farPlane;
 142         idReachability *reach;
 143         const aasArea_t *area;
 144         idVec3 p, dir;
 145
 146         if ( file == NULL ) {
 147                 endPos = goalOrigin;
 148                 endAreaNum = 0;
 149                 return true;
 150         }
 151
 152         lastAreas[0] = lastAreas[1] = lastAreas[2] = lastAreas[3] = areaNum;
 153         lastAreaIndex = 0;
 154
 155         pathPlane.SetNormal( (goalOrigin - origin).Cross( file->GetSettings().gravityDir ) );
 156         pathPlane.Normalize();
 157         pathPlane.FitThroughPoint( origin );
 158
 159         frontPlane.SetNormal( goalOrigin - origin );
 160         frontPlane.Normalize();
 161         frontPlane.FitThroughPoint( origin );
 162
 163         farPlane.SetNormal( frontPlane.Normal() );
 164         farPlane.FitThroughPoint( goalOrigin );
 165
 166         curAreaNum = areaNum;
 167         lastAreaNum = curAreaNum;
 168
 169         while ( 1 ) {
 170
 171                 // find the furthest floor face split point on the path
 172                 if ( !FloorEdgeSplitPoint( endPos, curAreaNum, pathPlane, frontPlane, false ) ) {
 173                         endPos = origin;
 174                 }
 175
 176                 // if we found a point near or further than the goal we're done
 177                 if ( farPlane.Distance( endPos ) > -0.5f ) {
 178                         break;
 179                 }
 180
 181                 // if we reached the goal area we're done
 182                 if ( curAreaNum == goalAreaNum ) {
 183                         break;
 184                 }
 185
 186                 frontPlane.SetDist( frontPlane.Normal() * endPos );
 187
 188                 area = &file->GetArea( curAreaNum );
 189
 190                 for ( reach = area->reach; reach; reach = reach->next ) {
 191                         if ( reach->travelType != TFL_WALK ) {
 192                                 continue;
 193                         }
 194
 195                         // if the reachability goes back to a previous area
 196                         if ( reach->toAreaNum == lastAreas[0] || reach->toAreaNum == lastAreas[1] ||
 197                                         reach->toAreaNum == lastAreas[2] || reach->toAreaNum == lastAreas[3] ) {
 198                                 continue;
 199                         }
 200
 201                         // if undesired travel flags are required to travel through the area
 202                         if ( file->GetArea( reach->toAreaNum ).travelFlags & ~travelFlags ) {
 203                                 continue;
 204                         }
 205
 206                         // don't optimize through an area near a ledge
 207                         if ( file->GetArea( reach->toAreaNum ).flags & AREA_LEDGE ) {
 208                                 continue;
 209                         }
 210
 211                         // find the closest floor face split point on the path
 212                         if ( !FloorEdgeSplitPoint( p, reach->toAreaNum, pathPlane, frontPlane, true ) ) {
 213                                 continue;
 214                         }
 215
 216                         // direction parallel to gravity
 217                         dir = ( file->GetSettings().gravityDir * endPos * file->GetSettings().gravityDir ) -
 218                                                 ( file->GetSettings().gravityDir * p * file->GetSettings().gravityDir );
 219                         if ( dir.LengthSqr() > Square( file->GetSettings().maxStepHeight ) ) {
 220                                 continue;
 221                         }
 222
 223                         // direction orthogonal to gravity
 224                         dir = endPos - p - dir;
 225                         if ( dir.LengthSqr() > Square( 0.2f ) ) {
 226                                 continue;
 227                         }
 228
 229                         break;
 230                 }
 231
 232                 if ( !reach ) {
 233                         return false;
 234                 }
 235
 236                 lastAreas[lastAreaIndex] = curAreaNum;
 237                 lastAreaIndex = ( lastAreaIndex + 1 ) & 3;
 238
 239                 curAreaNum = reach->toAreaNum;
 240         }
 241
 242         endAreaNum = curAreaNum;
 243
 244         return true;
 245 }
 246
 247 /*
 248 ============
 249 idAASLocal::SubSampleWalkPath
 250 ============
 251 */
 252 idVec3 idAASLocal::SubSampleWalkPath( int areaNum, const idVec3 &origin, const idVec3 &start, const idVec3 &end, int travelFlags, int &endAreaNum ) const {
 253         int i, numSamples, curAreaNum;
 254         idVec3 dir, point, nextPoint, endPos;
 255
 256         dir = end - start;
 257         numSamples = (int) (dir.Length() / walkPathSampleDistance) + 1;
 258
 259         point = start;
 260         for ( i = 1; i < numSamples; i++ ) {
 261                 nextPoint = start + dir * ((float) i / numSamples);
 262                 if ( (point - nextPoint).LengthSqr() > Square( maxWalkPathDistance ) ) {
 263                         return point;
 264                 }
 265                 if ( !idAASLocal::WalkPathValid( areaNum, origin, 0, nextPoint, travelFlags, endPos, curAreaNum ) ) {
 266                         return point;
 267                 }
 268                 point = nextPoint;
 269                 endAreaNum = curAreaNum;
 270         }
 271         return point;
 272 }
 273
 274 /*
 275 ============
 276 idAASLocal::WalkPathToGoal
 277
 278   FIXME: don't stop optimizing on first failure ?
 279 ============
 280 */
 281 bool idAASLocal::WalkPathToGoal( aasPath_t &path, int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags ) const {
 282         int i, travelTime, curAreaNum, lastAreas[4], lastAreaIndex, endAreaNum;
 283         idReachability *reach;
 284         idVec3 endPos;
 285
 286         path.type = PATHTYPE_WALK;
 287         path.moveGoal = origin;
 288         path.moveAreaNum = areaNum;
 289         path.secondaryGoal = origin;
 290         path.reachability = NULL;
 291
 292         if ( file == NULL || areaNum == goalAreaNum ) {
 293                 path.moveGoal = goalOrigin;
 294                 return true;
 295         }
 296
 297         lastAreas[0] = lastAreas[1] = lastAreas[2] = lastAreas[3] = areaNum;
 298         lastAreaIndex = 0;
 299
 300         curAreaNum = areaNum;
 301
 302         for ( i = 0; i < maxWalkPathIterations; i++ ) {
 303
 304                 if ( !idAASLocal::RouteToGoalArea( curAreaNum, path.moveGoal, goalAreaNum, travelFlags, travelTime, &reach ) ) {
 305                         break;
 306                 }
 307
 308                 if ( !reach ) {
 309                         return false;
 310                 }
 311
 312                 // no need to check through the first area
 313                 if ( areaNum != curAreaNum ) {
 314                         // only optimize a limited distance ahead
 315                         if ( (reach->start - origin).LengthSqr() > Square( maxWalkPathDistance ) ) {
 316 #if SUBSAMPLE_WALK_PATH
 317                                 path.moveGoal = SubSampleWalkPath( areaNum, origin, path.moveGoal, reach->start, travelFlags, path.moveAreaNum );
 318 #endif
 319                                 return true;
 320                         }
 321
 322                         if ( !idAASLocal::WalkPathValid( areaNum, origin, 0, reach->start, travelFlags, endPos, endAreaNum ) ) {
 323 #if SUBSAMPLE_WALK_PATH
 324                                 path.moveGoal = SubSampleWalkPath( areaNum, origin, path.moveGoal, reach->start, travelFlags, path.moveAreaNum );
 325 #endif
 326                                 return true;
 327                         }
 328                 }
 329
 330                 path.moveGoal = reach->start;
 331                 path.moveAreaNum = curAreaNum;
 332
 333                 if ( reach->travelType != TFL_WALK ) {
 334                         break;
 335                 }
 336
 337                 if ( !idAASLocal::WalkPathValid( areaNum, origin, 0, reach->end, travelFlags, endPos, endAreaNum ) ) {
 338                         return true;
 339                 }
 340
 341                 path.moveGoal = reach->end;
 342                 path.moveAreaNum = reach->toAreaNum;
 343
 344                 if ( reach->toAreaNum == goalAreaNum ) {
 345                         if ( !idAASLocal::WalkPathValid( areaNum, origin, 0, goalOrigin, travelFlags, endPos, endAreaNum ) ) {
 346 #if SUBSAMPLE_WALK_PATH
 347                                 path.moveGoal = SubSampleWalkPath( areaNum, origin, path.moveGoal, goalOrigin, travelFlags, path.moveAreaNum );
 348 #endif
 349                                 return true;
 350                         }
 351                         path.moveGoal = goalOrigin;
 352                         path.moveAreaNum = goalAreaNum;
 353                         return true;
 354                 }
 355
 356                 lastAreas[lastAreaIndex] = curAreaNum;
 357                 lastAreaIndex = ( lastAreaIndex + 1 ) & 3;
 358
 359                 curAreaNum = reach->toAreaNum;
 360
 361                 if ( curAreaNum == lastAreas[0] || curAreaNum == lastAreas[1] ||
 362                                 curAreaNum == lastAreas[2] || curAreaNum == lastAreas[3] ) {
 363                         common->Warning( "idAASLocal::WalkPathToGoal: local routing minimum going from area %d to area %d", areaNum, goalAreaNum );
 364                         break;
 365                 }
 366         }
 367
 368         if ( !reach ) {
 369                 return false;
 370         }
 371
 372         switch( reach->travelType ) {
 373                 case TFL_WALKOFFLEDGE:
 374                         path.type = PATHTYPE_WALKOFFLEDGE;
 375                         path.secondaryGoal = reach->end;
 376                         path.reachability = reach;
 377                         break;
 378                 case TFL_BARRIERJUMP:
 379                         path.type |= PATHTYPE_BARRIERJUMP;
 380                         path.secondaryGoal = reach->end;
 381                         path.reachability = reach;
 382                         break;
 383                 case TFL_JUMP:
 384                         path.type |= PATHTYPE_JUMP;
 385                         path.secondaryGoal = reach->end;
 386                         path.reachability = reach;
 387                         break;
 388                 default:
 389                         break;
 390         }
 391
 392         return true;
 393 }
 394
 395 /*
 396 ============
 397 idAASLocal::FlyPathValid
 398
 399   returns true if one can fly in a straight line between origin and goalOrigin
 400 ============
 401 */
 402 bool idAASLocal::FlyPathValid( int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags, idVec3 &endPos, int &endAreaNum ) const {
 403         aasTrace_t trace;
 404
 405         if ( file == NULL ) {
 406                 endPos = goalOrigin;
 407                 endAreaNum = 0;
 408                 return true;
 409         }
 410
 411         file->Trace( trace, origin, goalOrigin );
 412
 413         endPos = trace.endpos;
 414         endAreaNum = trace.lastAreaNum;
 415
 416         if ( trace.fraction >= 1.0f ) {
 417                 return true;
 418         }
 419
 420         return false;
 421 }
 422
 423 /*
 424 ============
 425 idAASLocal::SubSampleFlyPath
 426 ============
 427 */
 428 idVec3 idAASLocal::SubSampleFlyPath( int areaNum, const idVec3 &origin, const idVec3 &start, const idVec3 &end, int travelFlags, int &endAreaNum ) const {
 429         int i, numSamples, curAreaNum;
 430         idVec3 dir, point, nextPoint, endPos;
 431
 432         dir = end - start;
 433         numSamples = (int) (dir.Length() / flyPathSampleDistance) + 1;
 434
 435         point = start;
 436         for ( i = 1; i < numSamples; i++ ) {
 437                 nextPoint = start + dir * ((float) i / numSamples);
 438                 if ( (point - nextPoint).LengthSqr() > Square( maxFlyPathDistance ) ) {
 439                         return point;
 440                 }
 441                 if ( !idAASLocal::FlyPathValid( areaNum, origin, 0, nextPoint, travelFlags, endPos, curAreaNum ) ) {
 442                         return point;
 443                 }
 444                 point = nextPoint;
 445                 endAreaNum = curAreaNum;
 446         }
 447         return point;
 448 }
 449
 450 /*
 451 ============
 452 idAASLocal::FlyPathToGoal
 453
 454   FIXME: don't stop optimizing on first failure ?
 455 ============
 456 */
 457 bool idAASLocal::FlyPathToGoal( aasPath_t &path, int areaNum, const idVec3 &origin, int goalAreaNum, const idVec3 &goalOrigin, int travelFlags ) const {
 458         int i, travelTime, curAreaNum, lastAreas[4], lastAreaIndex, endAreaNum;
 459         idReachability *reach;
 460         idVec3 endPos;
 461
 462         path.type = PATHTYPE_WALK;
 463         path.moveGoal = origin;
 464         path.moveAreaNum = areaNum;
 465         path.secondaryGoal = origin;
 466         path.reachability = NULL;
 467
 468         if ( file == NULL || areaNum == goalAreaNum ) {
 469                 path.moveGoal = goalOrigin;
 470                 return true;
 471         }
 472
 473         lastAreas[0] = lastAreas[1] = lastAreas[2] = lastAreas[3] = areaNum;
 474         lastAreaIndex = 0;
 475
 476         curAreaNum = areaNum;
 477
 478         for ( i = 0; i < maxFlyPathIterations; i++ ) {
 479
 480                 if ( !idAASLocal::RouteToGoalArea( curAreaNum, path.moveGoal, goalAreaNum, travelFlags, travelTime, &reach ) ) {
 481                         break;
 482                 }
 483
 484                 if ( !reach ) {
 485                         return false;
 486                 }
 487
 488                 // no need to check through the first area
 489                 if ( areaNum != curAreaNum ) {
 490                         if ( (reach->start - origin).LengthSqr() > Square( maxFlyPathDistance ) ) {
 491 #if SUBSAMPLE_FLY_PATH
 492                                 path.moveGoal = SubSampleFlyPath( areaNum, origin, path.moveGoal, reach->start, travelFlags, path.moveAreaNum );
 493 #endif
 494                                 return true;
 495                         }
 496
 497                         if ( !idAASLocal::FlyPathValid( areaNum, origin, 0, reach->start, travelFlags, endPos, endAreaNum ) ) {
 498 #if SUBSAMPLE_FLY_PATH
 499                                 path.moveGoal = SubSampleFlyPath( areaNum, origin, path.moveGoal, reach->start, travelFlags, path.moveAreaNum );
 500 #endif
 501                                 return true;
 502                         }
 503                 }
 504
 505                 path.moveGoal = reach->start;
 506                 path.moveAreaNum = curAreaNum;
 507
 508                 if ( !idAASLocal::FlyPathValid( areaNum, origin, 0, reach->end, travelFlags, endPos, endAreaNum ) ) {
 509                         return true;
 510                 }
 511
 512                 path.moveGoal = reach->end;
 513                 path.moveAreaNum = reach->toAreaNum;
 514
 515                 if ( reach->toAreaNum == goalAreaNum ) {
 516                         if ( !idAASLocal::FlyPathValid( areaNum, origin, 0, goalOrigin, travelFlags, endPos, endAreaNum ) ) {
 517 #if SUBSAMPLE_FLY_PATH
 518                                 path.moveGoal = SubSampleFlyPath( areaNum, origin, path.moveGoal, goalOrigin, travelFlags, path.moveAreaNum );
 519 #endif
 520                                 return true;
 521                         }
 522                         path.moveGoal = goalOrigin;
 523                         path.moveAreaNum = goalAreaNum;
 524                         return true;
 525                 }
 526
 527                 lastAreas[lastAreaIndex] = curAreaNum;
 528                 lastAreaIndex = ( lastAreaIndex + 1 ) & 3;
 529
 530                 curAreaNum = reach->toAreaNum;
 531
 532                 if ( curAreaNum == lastAreas[0] || curAreaNum == lastAreas[1] ||
 533                                 curAreaNum == lastAreas[2] || curAreaNum == lastAreas[3] ) {
 534                         common->Warning( "idAASLocal::FlyPathToGoal: local routing minimum going from area %d to area %d", areaNum, goalAreaNum );
 535                         break;
 536                 }
 537         }
 538
 539         if ( !reach ) {
 540                 return false;
 541         }
 542
 543         return true;
 544 }
 545
 546 typedef struct wallEdge_s {
 547         int                                     edgeNum;
 548         int                                     verts[2];
 549         struct wallEdge_s *     next;
 550 } wallEdge_t;
 551
 552 /*
 553 ============
 554 idAASLocal::SortWallEdges
 555 ============
 556 */
 557 void idAASLocal::SortWallEdges( int *edges, int numEdges ) const {
 558         int i, j, k, numSequences;
 559         wallEdge_t **sequenceFirst, **sequenceLast, *wallEdges, *wallEdge;
 560
 561         wallEdges = (wallEdge_t *) _alloca16( numEdges * sizeof( wallEdge_t ) );
 562         sequenceFirst = (wallEdge_t **)_alloca16( numEdges * sizeof( wallEdge_t * ) );
 563         sequenceLast = (wallEdge_t **)_alloca16( numEdges * sizeof( wallEdge_t * ) );
 564
 565         for ( i = 0; i < numEdges; i++ ) {
 566                 wallEdges[i].edgeNum = edges[i];
 567                 GetEdgeVertexNumbers( edges[i], wallEdges[i].verts );
 568                 wallEdges[i].next = NULL;
 569                 sequenceFirst[i] = &wallEdges[i];
 570                 sequenceLast[i] = &wallEdges[i];
 571         }
 572         numSequences = numEdges;
 573
 574         for ( i = 0; i < numSequences; i++ ) {
 575                 for ( j = i+1; j < numSequences; j++ ) {
 576                         if ( sequenceFirst[i]->verts[0] == sequenceLast[j]->verts[1] ) {
 577                                 sequenceLast[j]->next = sequenceFirst[i];
 578                                 sequenceFirst[i] = sequenceFirst[j];
 579                                 break;
 580                         }
 581                         if ( sequenceLast[i]->verts[1] == sequenceFirst[j]->verts[0] ) {
 582                                 sequenceLast[i]->next = sequenceFirst[j];
 583                                 break;
 584                         }
 585                 }
 586                 if ( j < numSequences ) {
 587                         numSequences--;
 588                         for ( k = j; k < numSequences; k++ ) {
 589                                 sequenceFirst[k] = sequenceFirst[k+1];
 590                                 sequenceLast[k] = sequenceLast[k+1];
 591                         }
 592                         i = -1;
 593                 }
 594         }
 595
 596         k = 0;
 597         for ( i = 0; i < numSequences; i++ ) {
 598                 for ( wallEdge = sequenceFirst[i]; wallEdge; wallEdge = wallEdge->next ) {
 599                         edges[k++] = wallEdge->edgeNum;
 600                 }
 601         }
 602 }
 603
 604 /*
 605 ============
 606 idAASLocal::GetWallEdges
 607 ============
 608 */
 609 int idAASLocal::GetWallEdges( int areaNum, const idBounds &bounds, int travelFlags, int *edges, int maxEdges ) const {
 610         int i, j, k, l, face1Num, face2Num, edge1Num, edge2Num, numEdges, absEdge1Num;
 611         int *areaQueue, curArea, queueStart, queueEnd;
 612         byte *areasVisited;
 613         const aasArea_t *area;
 614         const aasFace_t *face1, *face2;
 615         idReachability *reach;
 616
 617         if ( !file ) {
 618                 return 0;
 619         }
 620
 621         numEdges = 0;
 622
 623         areasVisited = (byte *) _alloca16( file->GetNumAreas() );
 624         memset( areasVisited, 0, file->GetNumAreas() * sizeof( byte ) );
 625         areaQueue = (int *) _alloca16( file->GetNumAreas() * sizeof( int ) );
 626
 627         queueStart = -1;
 628         queueEnd = 0;
 629         areaQueue[0] = areaNum;
 630         areasVisited[areaNum] = true;
 631
 632         for ( curArea = areaNum; queueStart < queueEnd; curArea = areaQueue[++queueStart] ) {
 633
 634                 area = &file->GetArea( curArea );
 635
 636                 for ( i = 0; i < area->numFaces; i++ ) {
 637                         face1Num = file->GetFaceIndex( area->firstFace + i );
 638                         face1 = &file->GetFace( abs(face1Num) );
 639
 640                         if ( !(face1->flags & FACE_FLOOR ) ) {
 641                                 continue;
 642                         }
 643
 644                         for ( j = 0; j < face1->numEdges; j++ ) {
 645                                 edge1Num = file->GetEdgeIndex( face1->firstEdge + j );
 646                                 absEdge1Num = abs( edge1Num );
 647
 648                                 // test if the edge is shared by another floor face of this area
 649                                 for ( k = 0; k < area->numFaces; k++ ) {
 650                                         if ( k == i ) {
 651                                                 continue;
 652                                         }
 653                                         face2Num = file->GetFaceIndex( area->firstFace + k );
 654                                         face2 = &file->GetFace( abs(face2Num) );
 655
 656                                         if ( !(face2->flags & FACE_FLOOR ) ) {
 657                                                 continue;
 658                                         }
 659
 660                                         for ( l = 0; l < face2->numEdges; l++ ) {
 661                                                 edge2Num = abs( file->GetEdgeIndex( face2->firstEdge + l ) );
 662                                                 if ( edge2Num == absEdge1Num ) {
 663                                                         break;
 664                                                 }
 665                                         }
 666                                         if ( l < face2->numEdges ) {
 667                                                 break;
 668                                         }
 669                                 }
 670                                 if ( k < area->numFaces ) {
 671                                         continue;
 672                                 }
 673
 674                                 // test if the edge is used by a reachability
 675                                 for ( reach = area->reach; reach; reach = reach->next ) {
 676                                         if ( reach->travelType & travelFlags ) {
 677                                                 if ( reach->edgeNum == absEdge1Num ) {
 678                                                         break;
 679                                                 }
 680                                         }
 681                                 }
 682                                 if ( reach ) {
 683                                         continue;
 684                                 }
 685
 686                                 // test if the edge is already in the list
 687                                 for ( k = 0; k < numEdges; k++ ) {
 688                                         if ( edge1Num == edges[k] ) {
 689                                                 break;
 690                                         }
 691                                 }
 692                                 if ( k < numEdges ) {
 693                                         continue;
 694                                 }
 695
 696                                 // add the edge to the list
 697                                 edges[numEdges++] = edge1Num;
 698                                 if ( numEdges >= maxEdges ) {
 699                                         return numEdges;
 700                                 }
 701                         }
 702                 }
 703
 704                 // add new areas to the queue
 705                 for ( reach = area->reach; reach; reach = reach->next ) {
 706                         if ( reach->travelType & travelFlags ) {
 707                                 // if the area the reachability leads to hasn't been visited yet and the area bounds touch the search bounds
 708                                 if ( !areasVisited[reach->toAreaNum] && bounds.IntersectsBounds( file->GetArea( reach->toAreaNum ).bounds ) ) {
 709                                         areaQueue[queueEnd++] = reach->toAreaNum;
 710                                         areasVisited[reach->toAreaNum] = true;
 711                                 }
 712                         }
 713                 }
 714         }
 715         return numEdges;
 716 }