neo/tools/compilers/aas/AASReach.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 "AASFile.h"
  33 #include "AASFile_local.h"
  34 #include "AASReach.h"
  35
  36 #define INSIDEUNITS                                                     2.0f
  37 #define INSIDEUNITS_WALKEND                                     0.5f
  38 #define INSIDEUNITS_WALKSTART                           0.1f
  39 #define INSIDEUNITS_SWIMEND                                     0.5f
  40 #define INSIDEUNITS_FLYEND                                      0.5f
  41 #define INSIDEUNITS_WATERJUMP                           15.0f
  42
  43
  44 /*
  45 ================
  46 idAASReach::ReachabilityExists
  47 ================
  48 */
  49 bool idAASReach::ReachabilityExists( int fromAreaNum, int toAreaNum ) {
  50         aasArea_t *area;
  51         idReachability *reach;
  52
  53         area = &file->areas[fromAreaNum];
  54         for ( reach = area->reach; reach; reach = reach->next ) {
  55                 if ( reach->toAreaNum == toAreaNum ) {
  56                         return true;
  57                 }
  58         }
  59         return false;
  60 }
  61
  62 /*
  63 ================
  64 idAASReach::CanSwimInArea
  65 ================
  66 */
  67 ID_INLINE bool idAASReach::CanSwimInArea( int areaNum ) {
  68         return ( file->areas[areaNum].contents & AREACONTENTS_WATER ) != 0;
  69 }
  70
  71 /*
  72 ================
  73 idAASReach::AreaHasFloor
  74 ================
  75 */
  76 ID_INLINE bool idAASReach::AreaHasFloor( int areaNum ) {
  77         return ( file->areas[areaNum].flags & AREA_FLOOR ) != 0;
  78 }
  79
  80 /*
  81 ================
  82 idAASReach::AreaIsClusterPortal
  83 ================
  84 */
  85 ID_INLINE bool idAASReach::AreaIsClusterPortal( int areaNum ) {
  86         return ( file->areas[areaNum].contents & AREACONTENTS_CLUSTERPORTAL ) != 0;
  87 }
  88
  89 /*
  90 ================
  91 idAASReach::AddReachabilityToArea
  92 ================
  93 */
  94 void idAASReach::AddReachabilityToArea( idReachability *reach, int areaNum ) {
  95         aasArea_t *area;
  96
  97         area = &file->areas[areaNum];
  98         reach->next = area->reach;
  99         area->reach = reach;
 100         numReachabilities++;
 101 }
 102
 103 /*
 104 ================
 105 idAASReach::Reachability_Fly
 106 ================
 107 */
 108 void idAASReach::Reachability_Fly( int areaNum ) {
 109         int i, faceNum, otherAreaNum;
 110         aasArea_t *area;
 111         aasFace_t *face;
 112         idReachability_Fly *reach;
 113
 114         area = &file->areas[areaNum];
 115
 116         for ( i = 0; i < area->numFaces; i++ ) {
 117                 faceNum = file->faceIndex[area->firstFace + i];
 118                 face = &file->faces[abs(faceNum)];
 119
 120                 otherAreaNum = face->areas[INTSIGNBITNOTSET(faceNum)];
 121
 122                 if ( otherAreaNum == 0 ) {
 123                         continue;
 124                 }
 125
 126                 if ( ReachabilityExists( areaNum, otherAreaNum ) ) {
 127                         continue;
 128                 }
 129
 130                 // create reachability going through this face
 131                 reach = new idReachability_Fly();
 132                 reach->travelType = TFL_FLY;
 133                 reach->toAreaNum = otherAreaNum;
 134                 reach->fromAreaNum = areaNum;
 135                 reach->edgeNum = 0;
 136                 reach->travelTime = 1;
 137                 reach->start = file->FaceCenter( abs(faceNum) );
 138                 if ( faceNum < 0 ) {
 139                         reach->end = reach->start + file->planeList[face->planeNum].Normal() * INSIDEUNITS_FLYEND;
 140                 } else {
 141                         reach->end = reach->start - file->planeList[face->planeNum].Normal() * INSIDEUNITS_FLYEND;
 142                 }
 143                 AddReachabilityToArea( reach, areaNum );
 144         }
 145 }
 146
 147 /*
 148 ================
 149 idAASReach::Reachability_Swim
 150 ================
 151 */
 152 void idAASReach::Reachability_Swim( int areaNum ) {
 153         int i, faceNum, otherAreaNum;
 154         aasArea_t *area;
 155         aasFace_t *face;
 156         idReachability_Swim *reach;
 157
 158         if ( !CanSwimInArea( areaNum ) ) {
 159                 return;
 160         }
 161
 162         area = &file->areas[areaNum];
 163
 164         for ( i = 0; i < area->numFaces; i++ ) {
 165                 faceNum = file->faceIndex[area->firstFace + i];
 166                 face = &file->faces[abs(faceNum)];
 167
 168                 otherAreaNum = face->areas[INTSIGNBITNOTSET(faceNum)];
 169
 170                 if ( otherAreaNum == 0 ) {
 171                         continue;
 172                 }
 173
 174                 if ( !CanSwimInArea( otherAreaNum ) ) {
 175                         continue;
 176                 }
 177
 178                 if ( ReachabilityExists( areaNum, otherAreaNum ) ) {
 179                         continue;
 180                 }
 181
 182                 // create reachability going through this face
 183                 reach = new idReachability_Swim();
 184                 reach->travelType = TFL_SWIM;
 185                 reach->toAreaNum = otherAreaNum;
 186                 reach->fromAreaNum = areaNum;
 187                 reach->edgeNum = 0;
 188                 reach->travelTime = 1;
 189                 reach->start = file->FaceCenter( abs(faceNum) );
 190                 if ( faceNum < 0 ) {
 191                         reach->end = reach->start + file->planeList[face->planeNum].Normal() * INSIDEUNITS_SWIMEND;
 192                 } else {
 193                         reach->end = reach->start - file->planeList[face->planeNum].Normal() * INSIDEUNITS_SWIMEND;
 194                 }
 195                 AddReachabilityToArea( reach, areaNum );
 196         }
 197 }
 198
 199 /*
 200 ================
 201 idAASReach::Reachability_EqualFloorHeight
 202 ================
 203 */
 204 void idAASReach::Reachability_EqualFloorHeight( int areaNum ) {
 205         int i, k, l, m, n, faceNum, face1Num, face2Num, otherAreaNum, edge1Num, edge2Num;
 206         aasArea_t *area, *otherArea;
 207         aasFace_t *face, *face1, *face2;
 208         idReachability_Walk *reach;
 209
 210         if ( !AreaHasFloor( areaNum ) ) {
 211                 return;
 212         }
 213
 214         area = &file->areas[areaNum];
 215
 216         for ( i = 0; i < area->numFaces; i++ ) {
 217                 faceNum = file->faceIndex[area->firstFace + i];
 218                 face = &file->faces[abs(faceNum)];
 219
 220                 otherAreaNum = face->areas[INTSIGNBITNOTSET(faceNum)];
 221                 if ( !AreaHasFloor( otherAreaNum ) ) {
 222                         continue;
 223                 }
 224
 225                 otherArea = &file->areas[otherAreaNum];
 226
 227                 for ( k = 0; k < area->numFaces; k++ ) {
 228                         face1Num = file->faceIndex[area->firstFace + k];
 229                         face1 = &file->faces[abs(face1Num)];
 230
 231                         if ( !( face1->flags & FACE_FLOOR ) ) {
 232                                 continue;
 233                         }
 234                         for ( l = 0; l < otherArea->numFaces; l++ ) {
 235                                 face2Num = file->faceIndex[otherArea->firstFace + l];
 236                                 face2 = &file->faces[abs(face2Num)];
 237
 238                                 if ( !( face2->flags & FACE_FLOOR ) ) {
 239                                         continue;
 240                                 }
 241
 242                                 for ( m = 0; m < face1->numEdges; m++ ) {
 243                                         edge1Num = abs(file->edgeIndex[face1->firstEdge + m]);
 244                                         for ( n = 0; n < face2->numEdges; n++ ) {
 245                                                 edge2Num = abs(file->edgeIndex[face2->firstEdge + n]);
 246                                                 if ( edge1Num == edge2Num ) {
 247                                                         break;
 248                                                 }
 249                                         }
 250                                         if ( n < face2->numEdges ) {
 251                                                 break;
 252                                         }
 253                                 }
 254                                 if ( m < face1->numEdges ) {
 255                                         break;
 256                                 }
 257                         }
 258                         if ( l < otherArea->numFaces ) {
 259                                 break;
 260                         }
 261                 }
 262                 if ( k < area->numFaces ) {
 263                         // create reachability
 264                         reach = new idReachability_Walk();
 265                         reach->travelType = TFL_WALK;
 266                         reach->toAreaNum = otherAreaNum;
 267                         reach->fromAreaNum = areaNum;
 268                         reach->edgeNum = abs( edge1Num );
 269                         reach->travelTime = 1;
 270                         reach->start = file->EdgeCenter( edge1Num );
 271                         if ( faceNum < 0 ) {
 272                                 reach->end = reach->start + file->planeList[face->planeNum].Normal() * INSIDEUNITS_WALKEND;
 273                         }
 274                         else {
 275                                 reach->end = reach->start - file->planeList[face->planeNum].Normal() * INSIDEUNITS_WALKEND;
 276                         }
 277                         AddReachabilityToArea( reach, areaNum );
 278                 }
 279         }
 280 }
 281
 282 /*
 283 ================
 284 idAASReach::Reachability_Step_Barrier_WaterJump_WalkOffLedge
 285 ================
 286 */
 287 bool idAASReach::Reachability_Step_Barrier_WaterJump_WalkOffLedge( int area1num, int area2num ) {
 288         int i, j, k, l, edge1Num, edge2Num, areas[10];
 289         int floor_bestArea1FloorEdgeNum, floor_bestArea2FloorEdgeNum, floor_foundReach;
 290         int water_bestArea1FloorEdgeNum, water_bestArea2FloorEdgeNum, water_foundReach;
 291         int side1, faceSide1, floorFace1Num;
 292         float dist, dist1, dist2, diff, invGravityDot, orthogonalDot;
 293         float x1, x2, x3, x4, y1, y2, y3, y4, tmp, y;
 294         float length, floor_bestLength, water_bestLength, floor_bestDist, water_bestDist;
 295         idVec3 v1, v2, v3, v4, tmpv, p1area1, p1area2, p2area1, p2area2;
 296         idVec3 normal, orthogonal, edgeVec, start, end;
 297         idVec3 floor_bestStart, floor_bestEnd, floor_bestNormal;
 298         idVec3 water_bestStart, water_bestEnd, water_bestNormal;
 299         idVec3 testPoint;
 300         idPlane *plane;
 301         aasArea_t *area1, *area2;
 302         aasFace_t *floorFace1, *floorFace2, *floor_bestFace1, *water_bestFace1;
 303         aasEdge_t *edge1, *edge2;
 304         idReachability_Walk *walkReach;
 305         idReachability_BarrierJump *barrierJumpReach;
 306         idReachability_WaterJump *waterJumpReach;
 307         idReachability_WalkOffLedge *walkOffLedgeReach;
 308         aasTrace_t trace;
 309
 310         // must be able to walk or swim in the first area
 311         if ( !AreaHasFloor( area1num ) && !CanSwimInArea( area1num ) ) {
 312                 return false;
 313         }
 314
 315         if ( !AreaHasFloor( area2num ) && !CanSwimInArea( area2num ) ) {
 316                 return false;
 317         }
 318
 319         area1 = &file->areas[area1num];
 320         area2 = &file->areas[area2num];
 321
 322         // if the areas are not near anough in the x-y direction
 323         for ( i = 0; i < 2; i++ ) {
 324                 if ( area1->bounds[0][i] > area2->bounds[1][i] + 2.0f ) {
 325                         return false;
 326                 }
 327                 if ( area1->bounds[1][i] < area2->bounds[0][i] - 2.0f ) {
 328                         return false;
 329                 }
 330         }
 331
 332         floor_foundReach = false;
 333         floor_bestDist = 99999;
 334         floor_bestLength = 0;
 335         floor_bestArea2FloorEdgeNum = 0;
 336
 337         water_foundReach = false;
 338         water_bestDist = 99999;
 339         water_bestLength = 0;
 340         water_bestArea2FloorEdgeNum = 0;
 341
 342         for ( i = 0; i < area1->numFaces; i++ ) {
 343                 floorFace1Num = file->faceIndex[area1->firstFace + i];
 344                 faceSide1 = floorFace1Num < 0;
 345                 floorFace1 = &file->faces[abs(floorFace1Num)];
 346
 347                 // if this isn't a floor face
 348                 if ( !(floorFace1->flags & FACE_FLOOR) ) {
 349
 350                         // if we can swim in the first area
 351                         if ( CanSwimInArea( area1num ) ) {
 352
 353                                 // face plane must be more or less horizontal
 354                                 plane = &file->planeList[ floorFace1->planeNum ^ (!faceSide1) ];
 355                                 if ( plane->Normal() * file->settings.invGravityDir < file->settings.minFloorCos ) {
 356                                         continue;
 357                                 }
 358                         }
 359                         else {
 360                                 // if we can't swim in the area it must be a ground face
 361                                 continue;
 362                         }
 363                 }
 364
 365                 for ( k = 0; k < floorFace1->numEdges; k++ ) {
 366                         edge1Num = file->edgeIndex[floorFace1->firstEdge + k];
 367                         side1 = (edge1Num < 0);
 368                         // NOTE: for water faces we must take the side area 1 is on into
 369                         // account because the face is shared and doesn't have to be oriented correctly
 370                         if ( !(floorFace1->flags & FACE_FLOOR) ) {
 371                                 side1 = (side1 == faceSide1);
 372                         }
 373                         edge1Num = abs(edge1Num);
 374                         edge1 = &file->edges[edge1Num];
 375                         // vertices of the edge
 376                         v1 = file->vertices[edge1->vertexNum[!side1]];
 377                         v2 = file->vertices[edge1->vertexNum[side1]];
 378                         // get a vertical plane through the edge
 379                         // NOTE: normal is pointing into area 2 because the face edges are stored counter clockwise
 380                         edgeVec = v2 - v1;
 381                         normal = edgeVec.Cross( file->settings.invGravityDir );
 382                         normal.Normalize();
 383                         dist = normal * v1;
 384
 385                         // check the faces from the second area
 386                         for ( j = 0; j < area2->numFaces; j++ ) {
 387                                 floorFace2 = &file->faces[abs(file->faceIndex[area2->firstFace + j])];
 388                                 // must be a ground face
 389                                 if ( !(floorFace2->flags & FACE_FLOOR) ) {
 390                                         continue;
 391                                 }
 392                                 // check the edges of this ground face
 393                                 for ( l = 0; l < floorFace2->numEdges; l++ ) {
 394                                         edge2Num = abs(file->edgeIndex[floorFace2->firstEdge + l]);
 395                                         edge2 = &file->edges[edge2Num];
 396                                         // vertices of the edge
 397                                         v3 = file->vertices[edge2->vertexNum[0]];
 398                                         v4 = file->vertices[edge2->vertexNum[1]];
 399                                         // check the distance between the two points and the vertical plane through the edge of area1
 400                                         diff = normal * v3 - dist;
 401                                         if ( diff < -0.2f || diff > 0.2f ) {
 402                                                 continue;
 403                                         }
 404                                         diff = normal * v4 - dist;
 405                                         if ( diff < -0.2f || diff > 0.2f ) {
 406                                                 continue;
 407                                         }
 408
 409                                         // project the two ground edges into the step side plane
 410                                         // and calculate the shortest distance between the two
 411                                         // edges if they overlap in the direction orthogonal to
 412                                         // the gravity direction
 413                                         orthogonal = file->settings.invGravityDir.Cross( normal );
 414                                         invGravityDot = file->settings.invGravityDir * file->settings.invGravityDir;
 415                                         orthogonalDot = orthogonal * orthogonal;
 416                                         // projection into the step plane
 417                                         // NOTE: since gravity is vertical this is just the z coordinate
 418                                         y1 = v1[2];//(v1 * file->settings.invGravity) / invGravityDot;
 419                                         y2 = v2[2];//(v2 * file->settings.invGravity) / invGravityDot;
 420                                         y3 = v3[2];//(v3 * file->settings.invGravity) / invGravityDot;
 421                                         y4 = v4[2];//(v4 * file->settings.invGravity) / invGravityDot;
 422
 423                                         x1 = (v1 * orthogonal) / orthogonalDot;
 424                                         x2 = (v2 * orthogonal) / orthogonalDot;
 425                                         x3 = (v3 * orthogonal) / orthogonalDot;
 426                                         x4 = (v4 * orthogonal) / orthogonalDot;
 427
 428                                         if ( x1 > x2 ) {
 429                                                 tmp = x1; x1 = x2; x2 = tmp;
 430                                                 tmp = y1; y1 = y2; y2 = tmp;
 431                                                 tmpv = v1; v1 = v2; v2 = tmpv;
 432                                         }
 433                                         if ( x3 > x4 ) {
 434                                                 tmp = x3; x3 = x4; x4 = tmp;
 435                                                 tmp = y3; y3 = y4; y4 = tmp;
 436                                                 tmpv = v3; v3 = v4; v4 = tmpv;
 437                                         }
 438                                         // if the two projected edge lines have no overlap
 439                                         if ( x2 <= x3 || x4 <= x1 ) {
 440                                                 continue;
 441                                         }
 442                                         // if the two lines fully overlap
 443                                         if ( (x1 - 0.5f < x3 && x4 < x2 + 0.5f) && (x3 - 0.5f < x1 && x2 < x4 + 0.5f) ) {
 444                                                 dist1 = y3 - y1;
 445                                                 dist2 = y4 - y2;
 446                                                 p1area1 = v1;
 447                                                 p2area1 = v2;
 448                                                 p1area2 = v3;
 449                                                 p2area2 = v4;
 450                                         }
 451                                         else {
 452                                                 // if the points are equal
 453                                                 if ( x1 > x3 - 0.1f && x1 < x3 + 0.1f ) {
 454                                                         dist1 = y3 - y1;
 455                                                         p1area1 = v1;
 456                                                         p1area2 = v3;
 457                                                 }
 458                                                 else if ( x1 < x3 ) {
 459                                                         y = y1 + (x3 - x1) * (y2 - y1) / (x2 - x1);
 460                                                         dist1 = y3 - y;
 461                                                         p1area1 = v3;
 462                                                         p1area1[2] = y;
 463                                                         p1area2 = v3;
 464                                                 }
 465                                                 else {
 466                                                         y = y3 + (x1 - x3) * (y4 - y3) / (x4 - x3);
 467                                                         dist1 = y - y1;
 468                                                         p1area1 = v1;
 469                                                         p1area2 = v1;
 470                                                         p1area2[2] = y;
 471                                                 }
 472                                                 // if the points are equal
 473                                                 if ( x2 > x4 - 0.1f && x2 < x4 + 0.1f ) {
 474                                                         dist2 = y4 - y2;
 475                                                         p2area1 = v2;
 476                                                         p2area2 = v4;
 477                                                 }
 478                                                 else if ( x2 < x4 ) {
 479                                                         y = y3 + (x2 - x3) * (y4 - y3) / (x4 - x3);
 480                                                         dist2 = y - y2;
 481                                                         p2area1 = v2;
 482                                                         p2area2 = v2;
 483                                                         p2area2[2] = y;
 484                                                 }
 485                                                 else {
 486                                                         y = y1 + (x4 - x1) * (y2 - y1) / (x2 - x1);
 487                                                         dist2 = y4 - y;
 488                                                         p2area1 = v4;
 489                                                         p2area1[2] = y;
 490                                                         p2area2 = v4;
 491                                                 }
 492                                         }
 493
 494                                         // if both distances are pretty much equal then we take the middle of the points
 495                                         if ( dist1 > dist2 - 1.0f && dist1 < dist2 + 1.0f ) {
 496                                                 dist = dist1;
 497                                                 start = ( p1area1 + p2area1 ) * 0.5f;
 498                                                 end = ( p1area2 + p2area2 ) * 0.5f;
 499                                         }
 500                                         else if (dist1 < dist2) {
 501                                                 dist = dist1;
 502                                                 start = p1area1;
 503                                                 end = p1area2;
 504                                         }
 505                                         else {
 506                                                 dist = dist2;
 507                                                 start = p2area1;
 508                                                 end = p2area2;
 509                                         }
 510
 511                                         // get the length of the overlapping part of the edges of the two areas
 512                                         length = (p2area2 - p1area2).Length();
 513
 514                                         if ( floorFace1->flags & FACE_FLOOR ) {
 515                                                 // if the vertical distance is smaller
 516                                                 if ( dist < floor_bestDist ||
 517                                                                 // or the vertical distance is pretty much the same
 518                                                                 // but the overlapping part of the edges is longer
 519                                                                 (dist < floor_bestDist + 1.0f && length > floor_bestLength) ) {
 520                                                         floor_bestDist = dist;
 521                                                         floor_bestLength = length;
 522                                                         floor_foundReach = true;
 523                                                         floor_bestArea1FloorEdgeNum = edge1Num;
 524                                                         floor_bestArea2FloorEdgeNum = edge2Num;
 525                                                         floor_bestFace1 = floorFace1;
 526                                                         floor_bestStart = start;
 527                                                         floor_bestNormal = normal;
 528                                                         floor_bestEnd = end;
 529                                                 }
 530                                         }
 531                                         else {
 532                                                 // if the vertical distance is smaller
 533                                                 if ( dist < water_bestDist ||
 534                                                                 //or the vertical distance is pretty much the same
 535                                                                 //but the overlapping part of the edges is longer
 536                                                                 (dist < water_bestDist + 1.0f && length > water_bestLength) ) {
 537                                                         water_bestDist = dist;
 538                                                         water_bestLength = length;
 539                                                         water_foundReach = true;
 540                                                         water_bestArea1FloorEdgeNum = edge1Num;
 541                                                         water_bestArea2FloorEdgeNum = edge2Num;
 542                                                         water_bestFace1 = floorFace1;
 543                                                         water_bestStart = start;        // best start point in area1
 544                                                         water_bestNormal = normal;      // normal is pointing into area2
 545                                                         water_bestEnd = end;            // best point towards area2
 546                                                 }
 547                                         }
 548                                 }
 549                         }
 550                 }
 551         }
 552         //
 553         // NOTE: swim reachabilities should already be filtered out
 554         //
 555         // Steps
 556         //
 557         //         ---------
 558         //         |          step height -> TFL_WALK
 559         // --------|
 560         //
 561         //         ---------
 562         // ~~~~~~~~|          step height and low water -> TFL_WALK
 563         // --------|
 564         //
 565         // ~~~~~~~~~~~~~~~~~~
 566         //         ---------
 567         //         |          step height and low water up to the step -> TFL_WALK
 568         // --------|
 569         //
 570         // check for a step reachability
 571         if ( floor_foundReach ) {
 572                 // if area2 is higher but lower than the maximum step height
 573                 // NOTE: floor_bestDist >= 0 also catches equal floor reachabilities
 574                 if ( floor_bestDist >= 0 && floor_bestDist < file->settings.maxStepHeight ) {
 575                         // create walk reachability from area1 to area2
 576                         walkReach = new idReachability_Walk();
 577                         walkReach->travelType = TFL_WALK;
 578                         walkReach->toAreaNum = area2num;
 579                         walkReach->fromAreaNum = area1num;
 580                         walkReach->start = floor_bestStart + INSIDEUNITS_WALKSTART * floor_bestNormal;
 581                         walkReach->end = floor_bestEnd + INSIDEUNITS_WALKEND * floor_bestNormal;
 582                         walkReach->edgeNum = abs( floor_bestArea1FloorEdgeNum );
 583                         walkReach->travelTime = 0;
 584                         if ( area2->flags & AREA_CROUCH ) {
 585                                 walkReach->travelTime += file->settings.tt_startCrouching;
 586                         }
 587                         AddReachabilityToArea( walkReach, area1num );
 588                         return true;
 589                 }
 590         }
 591         //
 592         // Water Jumps
 593         //
 594         //         ---------
 595         //         |
 596         // ~~~~~~~~|
 597         //         |
 598         //         |          higher than step height and water up to waterjump height -> TFL_WATERJUMP
 599         // --------|
 600         //
 601         // ~~~~~~~~~~~~~~~~~~
 602         //         ---------
 603         //         |
 604         //         |
 605         //         |
 606         //         |          higher than step height and low water up to the step -> TFL_WATERJUMP
 607         // --------|
 608         //
 609         // check for a waterjump reachability
 610         if ( water_foundReach ) {
 611                 // get a test point a little bit towards area1
 612                 testPoint = water_bestEnd - INSIDEUNITS * water_bestNormal;
 613                 // go down the maximum waterjump height
 614                 testPoint[2] -= file->settings.maxWaterJumpHeight;
 615                 // if there IS water the sv_maxwaterjump height below the bestend point
 616                 if ( area1->flags & AREA_LIQUID ) {
 617                         // don't create rediculous water jump reachabilities from areas very far below the water surface
 618                         if ( water_bestDist < file->settings.maxWaterJumpHeight + 24 ) {
 619                                 // water jumping from or towards a crouch only areas is not possible
 620                                 if ( !(area1->flags & AREA_CROUCH) && !(area2->flags & AREA_CROUCH) ) {
 621                                         // create water jump reachability from area1 to area2
 622                                         waterJumpReach = new idReachability_WaterJump();
 623                                         waterJumpReach->travelType = TFL_WATERJUMP;
 624                                         waterJumpReach->toAreaNum = area2num;
 625                                         waterJumpReach->fromAreaNum = area1num;
 626                                         waterJumpReach->start = water_bestStart;
 627                                         waterJumpReach->end = water_bestEnd + INSIDEUNITS_WATERJUMP * water_bestNormal;
 628                                         waterJumpReach->edgeNum = abs( floor_bestArea1FloorEdgeNum );
 629                                         waterJumpReach->travelTime = file->settings.tt_waterJump;
 630                                         AddReachabilityToArea( waterJumpReach, area1num );
 631                                         return true;
 632                                 }
 633                         }
 634                 }
 635         }
 636         //
 637         // Barrier Jumps
 638         //
 639         //         ---------
 640         //         |
 641         //         |
 642         //         |
 643         //         |         higher than max step height lower than max barrier height -> TFL_BARRIERJUMP
 644         // --------|
 645         //
 646         //         ---------
 647         //         |
 648         //         |
 649         //         |
 650         // ~~~~~~~~|         higher than max step height lower than max barrier height
 651         // --------|         and a thin layer of water in the area to jump from -> TFL_BARRIERJUMP
 652         //
 653         // check for a barrier jump reachability
 654         if ( floor_foundReach ) {
 655                 //if area2 is higher but lower than the maximum barrier jump height
 656                 if ( floor_bestDist > 0 && floor_bestDist < file->settings.maxBarrierHeight ) {
 657                         //if no water in area1 or a very thin layer of water on the ground
 658                         if ( !water_foundReach || (floor_bestDist - water_bestDist < 16) ) {
 659                                 // cannot perform a barrier jump towards or from a crouch area
 660                                 if ( !(area1->flags & AREA_CROUCH) && !(area2->flags & AREA_CROUCH) ) {
 661                                         // create barrier jump reachability from area1 to area2
 662                                         barrierJumpReach = new idReachability_BarrierJump();
 663                                         barrierJumpReach->travelType = TFL_BARRIERJUMP;
 664                                         barrierJumpReach->toAreaNum = area2num;
 665                                         barrierJumpReach->fromAreaNum = area1num;
 666                                         barrierJumpReach->start = floor_bestStart + INSIDEUNITS_WALKSTART * floor_bestNormal;
 667                                         barrierJumpReach->end = floor_bestEnd + INSIDEUNITS_WALKEND * floor_bestNormal;
 668                                         barrierJumpReach->edgeNum = abs( floor_bestArea1FloorEdgeNum );
 669                                         barrierJumpReach->travelTime = file->settings.tt_barrierJump;
 670                                         AddReachabilityToArea( barrierJumpReach, area1num );
 671                                         return true;
 672                                 }
 673                         }
 674                 }
 675         }
 676         //
 677         // Walk and Walk Off Ledge
 678         //
 679         // --------|
 680         //         |          can walk or step back -> TFL_WALK
 681         //         ---------
 682         //
 683         // --------|
 684         //         |
 685         //         |
 686         //         |
 687         //         |          cannot walk/step back -> TFL_WALKOFFLEDGE
 688         //         ---------
 689         //
 690         // --------|
 691         //         |
 692         //         |~~~~~~~~
 693         //         |
 694         //         |          cannot step back but can waterjump back -> TFL_WALKOFFLEDGE
 695         //         ---------  FIXME: create TFL_WALK reach??
 696         //
 697         // check for a walk or walk off ledge reachability
 698         if ( floor_foundReach ) {
 699                 if ( floor_bestDist < 0 ) {
 700                         if ( floor_bestDist > -file->settings.maxStepHeight ) {
 701                                 // create walk reachability from area1 to area2
 702                                 walkReach = new idReachability_Walk();
 703                                 walkReach->travelType = TFL_WALK;
 704                                 walkReach->toAreaNum = area2num;
 705                                 walkReach->fromAreaNum = area1num;
 706                                 walkReach->start = floor_bestStart + INSIDEUNITS_WALKSTART * floor_bestNormal;
 707                                 walkReach->end = floor_bestEnd + INSIDEUNITS_WALKEND * floor_bestNormal;
 708                                 walkReach->edgeNum = abs( floor_bestArea1FloorEdgeNum );
 709                                 walkReach->travelTime = 1;
 710                                 AddReachabilityToArea( walkReach, area1num );
 711                                 return true;
 712                         }
 713                         // if no maximum fall height set or less than the max
 714                         if ( !file->settings.maxFallHeight || idMath::Fabs(floor_bestDist) < file->settings.maxFallHeight ) {
 715                                 // trace a bounding box vertically to check for solids
 716                                 floor_bestEnd += INSIDEUNITS * floor_bestNormal;
 717                                 start = floor_bestEnd;
 718                                 start[2] = floor_bestStart[2];
 719                                 end = floor_bestEnd;
 720                                 end[2] += 4;
 721                                 trace.areas = areas;
 722                                 trace.maxAreas = sizeof(areas) / sizeof(int);
 723                                 file->Trace( trace, start, end );
 724                                 // if the trace didn't start in solid and nothing was hit
 725                                 if ( trace.lastAreaNum && trace.fraction >= 1.0f ) {
 726                                         // the trace end point must be in the goal area
 727                                         if ( trace.lastAreaNum == area2num ) {
 728                                                 // don't create reachability if going through a cluster portal
 729                                                 for (i = 0; i < trace.numAreas; i++) {
 730                                                         if ( AreaIsClusterPortal( trace.areas[i] ) ) {
 731                                                                 break;
 732                                                         }
 733                                                 }
 734                                                 if ( i >= trace.numAreas ) {
 735                                                         // create a walk off ledge reachability from area1 to area2
 736                                                         walkOffLedgeReach = new idReachability_WalkOffLedge();
 737                                                         walkOffLedgeReach->travelType = TFL_WALKOFFLEDGE;
 738                                                         walkOffLedgeReach->toAreaNum = area2num;
 739                                                         walkOffLedgeReach->fromAreaNum = area1num;
 740                                                         walkOffLedgeReach->start = floor_bestStart;
 741                                                         walkOffLedgeReach->end = floor_bestEnd;
 742                                                         walkOffLedgeReach->edgeNum = abs( floor_bestArea1FloorEdgeNum );
 743                                                         walkOffLedgeReach->travelTime = file->settings.tt_startWalkOffLedge + idMath::Fabs(floor_bestDist) * 50 / file->settings.gravityValue;
 744                                                         AddReachabilityToArea( walkOffLedgeReach, area1num );
 745                                                         return true;
 746                                                 }
 747                                         }
 748                                 }
 749                         }
 750                 }
 751         }
 752         return false;
 753 }
 754
 755 /*
 756 ================
 757 idAASReach::Reachability_WalkOffLedge
 758 ================
 759 */
 760 void idAASReach::Reachability_WalkOffLedge( int areaNum ) {
 761         int i, j, faceNum, edgeNum, side, reachAreaNum, p, areas[10];
 762         aasArea_t *area;
 763         aasFace_t *face;
 764         aasEdge_t *edge;
 765         idPlane *plane;
 766         idVec3 v1, v2, mid, dir, testEnd;
 767         idReachability_WalkOffLedge *reach;
 768         aasTrace_t trace;
 769
 770         if ( !AreaHasFloor( areaNum ) || CanSwimInArea( areaNum ) ) {
 771                 return;
 772         }
 773
 774         area = &file->areas[areaNum];
 775
 776         for ( i = 0; i < area->numFaces; i++ ) {
 777                 faceNum = file->faceIndex[area->firstFace + i];
 778                 face = &file->faces[abs(faceNum)];
 779
 780                 // face must be a floor face
 781                 if ( !(face->flags & FACE_FLOOR) ) {
 782                         continue;
 783                 }
 784
 785                 for ( j = 0; j < face->numEdges; j++ ) {
 786
 787                         edgeNum = file->edgeIndex[face->firstEdge + j];
 788                         edge = &file->edges[abs(edgeNum)];
 789
 790                         //if ( !(edge->flags & EDGE_LEDGE) ) {
 791                         //      continue;
 792                         //}
 793
 794                         side = edgeNum < 0;
 795
 796                         v1 = file->vertices[edge->vertexNum[side]];
 797                         v2 = file->vertices[edge->vertexNum[!side]];
 798
 799                         plane = &file->planeList[face->planeNum ^ INTSIGNBITSET(faceNum) ];
 800
 801                         // get the direction into the other area
 802                         dir = plane->Normal().Cross( v2 - v1 );
 803                         dir.Normalize();
 804
 805                         mid = ( v1 + v2 ) * 0.5f;
 806                         testEnd = mid + INSIDEUNITS_WALKEND * dir;
 807                         testEnd[2] -= file->settings.maxFallHeight + 1.0f;
 808                         trace.areas = areas;
 809                         trace.maxAreas = sizeof(areas) / sizeof(int);
 810                         file->Trace( trace, mid, testEnd );
 811
 812                         reachAreaNum = trace.lastAreaNum;
 813                         if ( !reachAreaNum || reachAreaNum == areaNum ) {
 814                                 continue;
 815                         }
 816                         if ( idMath::Fabs( mid[2] - trace.endpos[2] ) > file->settings.maxFallHeight ) {
 817                                 continue;
 818                         }
 819                         if ( !AreaHasFloor( reachAreaNum ) && !CanSwimInArea( reachAreaNum ) ) {
 820                                 continue;
 821                         }
 822                         if ( ReachabilityExists( areaNum, reachAreaNum) ) {
 823                                 continue;
 824                         }
 825                         // if not going through a cluster portal
 826                         for ( p = 0; p < trace.numAreas; p++ ) {
 827                                 if ( AreaIsClusterPortal( trace.areas[p] ) ) {
 828                                         break;
 829                                 }
 830                         }
 831                         if ( p < trace.numAreas ) {
 832                                 continue;
 833                         }
 834
 835                         reach = new idReachability_WalkOffLedge();
 836                         reach->travelType = TFL_WALKOFFLEDGE;
 837                         reach->toAreaNum = reachAreaNum;
 838                         reach->fromAreaNum = areaNum;
 839                         reach->start = mid;
 840                         reach->end = trace.endpos;
 841                         reach->edgeNum = abs( edgeNum );
 842                         reach->travelTime = file->settings.tt_startWalkOffLedge + idMath::Fabs(mid[2] - trace.endpos[2]) * 50 / file->settings.gravityValue;
 843                         AddReachabilityToArea( reach, areaNum );
 844                 }
 845         }
 846 }
 847
 848 /*
 849 ================
 850 idAASReach::FlagReachableAreas
 851 ================
 852 */
 853 void idAASReach::FlagReachableAreas( idAASFileLocal *file ) {
 854         int i, numReachableAreas;
 855
 856         numReachableAreas = 0;
 857         for ( i = 1; i < file->areas.Num(); i++ ) {
 858
 859                 if ( ( file->areas[i].flags & ( AREA_FLOOR | AREA_LADDER ) ) ||
 860                                 ( file->areas[i].contents & AREACONTENTS_WATER ) ) {
 861                         file->areas[i].flags |= AREA_REACHABLE_WALK;
 862                 }
 863                 if ( file->GetSettings().allowFlyReachabilities ) {
 864                         file->areas[i].flags |= AREA_REACHABLE_FLY;
 865                 }
 866                 numReachableAreas++;
 867         }
 868
 869         common->Printf( "%6d reachable areas\n", numReachableAreas );
 870 }
 871
 872 /*
 873 ================
 874 idAASReach::Build
 875 ================
 876 */
 877 bool idAASReach::Build( const idMapFile *mapFile, idAASFileLocal *file ) {
 878         int i, j, lastPercent, percent;
 879
 880         this->mapFile = mapFile;
 881         this->file = file;
 882         numReachabilities = 0;
 883
 884         common->Printf( "[Reachability]\n" );
 885
 886         // delete all existing reachabilities
 887         file->DeleteReachabilities();
 888
 889         FlagReachableAreas( file );
 890
 891         for ( i = 1; i < file->areas.Num(); i++ ) {
 892                 if ( !( file->areas[i].flags & AREA_REACHABLE_WALK ) ) {
 893                         continue;
 894                 }
 895                 if ( file->GetSettings().allowSwimReachabilities ) {
 896                         Reachability_Swim( i );
 897                 }
 898                 Reachability_EqualFloorHeight( i );
 899         }
 900
 901         lastPercent = -1;
 902         for ( i = 1; i < file->areas.Num(); i++ ) {
 903
 904                 if ( !( file->areas[i].flags & AREA_REACHABLE_WALK ) ) {
 905                         continue;
 906                 }
 907
 908                 for ( j = 0; j < file->areas.Num(); j++ ) {
 909                         if ( i == j ) {
 910                                 continue;
 911                         }
 912
 913                         if ( !( file->areas[j].flags & AREA_REACHABLE_WALK ) ) {
 914                                 continue;
 915                         }
 916
 917                         if ( ReachabilityExists( i, j ) ) {
 918                                 continue;
 919                         }
 920                         if ( Reachability_Step_Barrier_WaterJump_WalkOffLedge( i, j ) ) {
 921                                 continue;
 922                         }
 923                 }
 924
 925                 //Reachability_WalkOffLedge( i );
 926
 927                 percent = 100 * i / file->areas.Num();
 928                 if ( percent > lastPercent ) {
 929                         common->Printf( "\r%6d%%", percent );
 930                         lastPercent = percent;
 931                 }
 932         }
 933
 934         if ( file->GetSettings().allowFlyReachabilities ) {
 935                 for ( i = 1; i < file->areas.Num(); i++ ) {
 936                         Reachability_Fly( i );
 937                 }
 938         }
 939
 940         file->LinkReversedReachability();
 941
 942         common->Printf( "\r%6d reachabilities\n", numReachabilities );
 943
 944         return true;
 945 }