prj/cam/src/ai/aipathdb.h

   1 /*
   2 @Copyright Looking Glass Studios, Inc.
   3 1996,1997,1998,1999,2000 Unpublished Work.
   4 */
   5
   6 ///////////////////////////////////////////////////////////////////////////////
   7 // $Header: r:/t2repos/thief2/src/ai/aipathdb.h,v 1.27 2000/03/01 13:02:52 bfarquha Exp $
   8 //
   9 //
  10 //
  11
  12 #ifndef __AIPATHDB_H
  13 #define __AIPATHDB_H
  14
  15 #include <aipthbas.h>
  16 #include <aipthzon.h>
  17 #include <aiokbits.h>
  18
  19 #include <dbmem.h>
  20
  21 #pragma pack(1)
  22 #pragma once
  23
  24 #define HUGE_Z    ((float)5.10)
  25
  26 // Anything less than 2 feet high will use SmallCreature links.
  27 #define AIPATHDB_SmallCreatureHeight 0.5
  28
  29
  30 F_DECLARE_INTERFACE(ITagFile);
  31 class cAIPath;
  32
  33 ///////////////////////////////////////////////////////////////////////////////
  34
  35 BOOL AIPathFindDBBuild();
  36
  37 void AIPathFindUpdate();
  38
  39 void AIPathFindMTWaypointHit(ObjID movingTerrain, ObjID waypoint);
  40 void AIPathFindMTWaypointLeft(ObjID movingTerrain);
  41
  42 void AIPathFindRead(ITagFile *);
  43 void AIPathFindWrite(ITagFile *);
  44
  45 // Given flee point, return flee region, else -1.
  46 int AIGetFleeRegion(ObjID id);
  47
  48 ///////////////////////////////////////////////////////////////////////////////
  49
  50 struct sAICellLineIntersect
  51 {
  52    unsigned   n;
  53    mxs_vector intersects[2];
  54 };
  55
  56 ///////////////////////////////////////////////////////////////////////////////
  57
  58 struct sAIExternCell
  59 {
  60    struct sPlane
  61    {
  62       mxs_vector normal;
  63       float      constant;
  64    };
  65
  66    sPlane     plane;
  67    unsigned   nVertices;
  68    mxs_vector vertices[1];
  69 };
  70
  71 inline sAIExternCell * AINewExternCell(unsigned nVertices)
  72 {
  73    sAIExternCell * p = (sAIExternCell *)malloc(sizeof(sAIExternCell) + sizeof(mxs_vector) * nVertices);
  74    p->nVertices      = nVertices;
  75    return p;
  76 };
  77
  78 inline sAIExternCell * AINewExternCell(const mxs_vector & normal, float constant, unsigned nVertices)
  79 {
  80    sAIExternCell * p = AINewExternCell(nVertices);
  81    p->plane.normal   = normal;
  82    p->plane.constant = constant;
  83    return p;
  84 };
  85
  86
  87 struct sFleeRegionData
  88 {
  89    int nRegionId;
  90    ObjID id;
  91 };
  92
  93 class cFleeRegionsHash : public cHashSet<sFleeRegionData *, const ObjID, cHashFunctions>
  94 {
  95 public:
  96    virtual tHashSetKey GetKey(tHashSetNode p) const
  97    {
  98       return (tHashSetKey) ((sFleeRegionData *)p)->id;
  99    }
 100 };
 101
 102
 103
 104 struct sZoneDatabase
 105 {
 106    cZonePairTable                         m_ZonePairTable;
 107    int                                    m_nZones;
 108
 109    // array of zones for each cell
 110    cAIPathArray<tAIPathZone>              m_CellZones;
 111 };
 112
 113
 114
 115 ///////////////////////////////////////////////////////////////////////////////
 116 //
 117 // CLASS: cAIPathDB
 118 //
 119
 120 class cAIPathDB
 121 {
 122 public:
 123
 124    cAIPathDB();
 125
 126    void Init();
 127    void Term();
 128
 129    ////////////////////////////////////
 130
 131    unsigned NumCells() const;
 132
 133    const sAIPathCell *     GetCell(const tAIPathCellID cell) const;
 134    sAIPathCell *           AccessCell(const tAIPathCellID cell);
 135    const sAIPathCellLink * GetCellLink(tAIPathCell2CellLinkID linkId) const;
 136
 137    const mxs_vector & GetCenter(const tAIPathCellID cell, mxs_vector * pCenter) const;
 138    const mxs_vector & GetCenter(const tAIPathCellID cell) const;
 139
 140    const sAIPathCellPlane * GetCellPlane(const tAIPathCellID cell) const;
 141    const sAIPathCellPlane * GetCellPlane(const sAIPathCell * pCell) const;
 142
 143    ////////////////////////////////////
 144
 145    const mxs_vector & GetCellVertex(tAIPathCellID cell, int index) const;
 146    tAIPathVertexID    GetCellVertexID(tAIPathCellID cell, int index) const;
 147 #if 0
 148    int                GetCellEdgeInfo(tAIPathCellID cell, int index) const;
 149 #endif
 150    void               GetCellVertexFull(tAIPathCellID cell, int index, mxs_vector * pVertex, tAIPathVertexID * pVertexID) const;
 151 #if 0
 152    BOOL               IsCellEdgeLinked(tAIPathCellID cell, int index) const;
 153 #endif
 154    const mxs_vector & GetVertex(tAIPathVertexID id) const;
 155    int                GetVertexInfo(tAIPathVertexID id) const;
 156
 157    ////////////////////////////////////
 158
 159    ObjID GetCellDoor(tAIPathCellID cell);
 160
 161    ////////////////////////////////////
 162
 163    sbool IsUnpathable(tAIPathCellID cell);
 164    sbool IsBelowDoor(tAIPathCellID cell);
 165    sbool IsBlockedOBB(tAIPathCellID cell);
 166    sbool IsActiveMovingTerrain(tAIPathCellID cell);
 167
 168    ////////////////////////////////////
 169
 170    void MarkBegin();
 171    void Mark(tAIPathCellID cell);
 172    void Unmark(tAIPathCellID cell);
 173    BOOL GetMark(tAIPathCellID cell);
 174    void MarkEnd();
 175
 176    ////////////////////////////////////
 177
 178    // wsf: doen't use condition bits for zones.
 179    BOOL          CanPathfindBetweenZones(eAIPathZoneType ZoneType, tAIPathZone zone1, tAIPathZone zone2, tAIPathOkBits okBits);
 180
 181    tAIPathZone   GetCellZone(eAIPathZoneType ZoneType, tAIPathCellID cell);
 182    tAIPathOkBits GetZoneOkBits(eAIPathZoneType ZoneType, tAIPathZone zone1, tAIPathZone zone2);
 183    void          SetZoneOkBits(eAIPathZoneType ZoneType, tAIPathZone zone1, tAIPathZone zone2, tAIPathOkBits okBits);
 184
 185    ////////////////////////////////////
 186
 187    float GetZAtXY(const sAIPathCell * pCell, const mxs_vector & pt) const;
 188    float GetZAtXY(const tAIPathCellID cell, const mxs_vector & pt) const;
 189
 190    float GetHighestZ(tAIPathCellID cell) const;
 191    float GetLowestZ(tAIPathCellID cell) const;
 192
 193    ////////////////////////////////////
 194
 195    float ComputeArea(tAIPathCellID cell) const;
 196
 197    ////////////////////////////////////
 198
 199    void DeleteCell(tAIPathCellID cell);
 200    void GetCell(tAIPathCellID cell, sAIExternCell **);
 201    BOOL AddOBBCell(sAIExternCell *, tAIPathCellID cell = 0, BOOL movable = FALSE);
 202
 203    int GetLineIntersections(tAIPathCellID cell, const mxs_vector & line1, const mxs_vector & line2, sAICellLineIntersect * pIntersect) const;
 204    BOOL SplitCellByLine(tAIPathCellID cell, const mxs_vector & line1, const mxs_vector & line2);
 205    BOOL SplitCell(tAIPathCellID cell, const mxs_vector & pt1, const mxs_vector & pt2);
 206
 207    // @TBD (toml 08-24-98):    void Compact();
 208
 209    ////////////////////////////////////
 210
 211 private:
 212
 213    friend BOOL AIPathFind(const cMxsVector & fromLocation, tAIPathCellID startCell,
 214                           const cMxsVector & toLocation, tAIPathCellID endCell,
 215                           cAIPath * pPath, tAIPathOkBits OkBits, tAIPathOkBits okCondBits = 0);
 216
 217 public:
 218    // array of cells
 219    cAIPathArray<sAIPathCell>              m_Cells;           // 1..count, zero is invalid
 220    tAIPathCellID                          m_nCells;
 221
 222    // array of cell plane info
 223    cAIPathArray<sAIPathCellPlane>         m_Planes;
 224    tAIPathCellID                          m_nPlanes;
 225
 226    // array of links between cells
 227    cAIPathArray<sAIPathCellLink>          m_Links;  // 1..count, zero is invalid
 228    tAIPathCell2CellLinkID                 m_nLinks;
 229
 230    // array of vertices
 231    cAIPathArray<sAIPathVertex>            m_Vertices;         // 1..count, zero is invalid
 232    tAIPathVertexID                        m_nVertices;
 233
 234    // array of vertices owned by cells
 235    cAIPathArray<sAIPathCell2VertexLink>   m_CellVertices;// 1..count, zero is invalid
 236    tAIPathCell2VertexLinkID               m_nCellVertices;
 237
 238    // array of object hints
 239    cAIPathArray<tAIPathCellID>            m_ObjHints;
 240    int                                    m_nObjHints;
 241
 242    // mapping of objects to the cells they've created
 243    cAIPathArray<sAIPathCellObjMap>        m_CellObjMap;
 244    int                                    m_nCellObjMaps;
 245
 246    sZoneDatabase                          m_ZoneDatabases[kAIZone_Num];
 247
 248    // Cell to door mapping
 249    cAICellDoorTable                       m_CellToDoorsTable;
 250    cAIPathArray<sAICellDoor>              m_CellDoors;
 251
 252    // List of all movable cells
 253    cDynClassArray<sAIMovableCell>         m_MovableCells;
 254
 255    // scratch arrays for database searching/traversing
 256    cAIPathArray<sbool>                    m_Marks;
 257    cDynArray_<tAIPathCellID, 128>         m_MarkedCells;
 258    int                                    m_nMarkedCells;
 259    cAIPathArray<ushort>                   m_BestCostToReach;
 260
 261    cFleeRegionsHash                       m_FleeRegions;
 262    int                                    m_nNumFleeRegions;
 263 };
 264
 265 extern cAIPathDB g_AIPathDB;
 266
 267 ///////////////////////////////////////////////////////////////////////////////
 268
 269 inline unsigned cAIPathDB::NumCells() const
 270 {
 271    return m_nCells;
 272 }
 273
 274 ///////////////////////////////////////
 275
 276 inline const sAIPathCell * cAIPathDB::GetCell(const tAIPathCellID cell) const
 277 {
 278    return &m_Cells[cell];
 279 }
 280
 281 ///////////////////////////////////////
 282
 283 inline const sAIPathCellLink * cAIPathDB::GetCellLink(tAIPathCell2CellLinkID linkId) const
 284 {
 285    return &m_Links[linkId];
 286 }
 287
 288 ///////////////////////////////////////
 289
 290 inline sAIPathCell * cAIPathDB::AccessCell(const tAIPathCellID cell)
 291 {
 292    return &m_Cells[cell];
 293 }
 294
 295 ///////////////////////////////////////
 296
 297 inline const mxs_vector & cAIPathDB::GetCenter(const tAIPathCellID cell, mxs_vector * pCenter) const
 298 {
 299    return (*pCenter = m_Cells[cell].center);
 300 }
 301
 302 ///////////////////////////////////////
 303
 304 inline const mxs_vector & cAIPathDB::GetCenter(const tAIPathCellID cell) const
 305 {
 306    return m_Cells[cell].center;
 307 }
 308
 309 ///////////////////////////////////////
 310
 311 inline const sAIPathCellPlane * cAIPathDB::GetCellPlane(const tAIPathCellID cell) const
 312 {
 313    return &m_Planes[m_Cells[cell].plane];
 314 }
 315
 316 ///////////////////////////////////////
 317
 318 inline const sAIPathCellPlane * cAIPathDB::GetCellPlane(const sAIPathCell * pCell) const
 319 {
 320    return &m_Planes[pCell->plane];
 321 }
 322
 323 ///////////////////////////////////////
 324
 325 inline float cAIPathDB::GetZAtXY(const sAIPathCell * pCell, const mxs_vector & pt) const
 326 {
 327    const sAIPathCellPlane * pPlane = &m_Planes[pCell->plane];
 328    return ((-pPlane->constant - pPlane->normal.x * pt.x - pPlane->normal.y * pt.y) / pPlane->normal.z);
 329 }
 330
 331 ///////////////////////////////////////
 332
 333 inline float cAIPathDB::GetZAtXY(const tAIPathCellID cell, const mxs_vector & pt) const
 334 {
 335    return GetZAtXY(&m_Cells[cell], pt);
 336 }
 337
 338 ///////////////////////////////////////
 339
 340 // Normalize a vertex index.
 341 #define cAIPathDB_NormalizeVertexIndex(i) \
 342    { \
 343       const int _nVertices = m_Cells[cell].vertexCount; \
 344       \
 345       if (index == _nVertices) \
 346          index = 0; \
 347       else if (index > _nVertices) \
 348          index %= _nVertices; \
 349       else if (index < 0) \
 350          index = _nVertices + (index % _nVertices); \
 351    }
 352
 353 ///////////////////////////////////////
 354
 355 inline const mxs_vector & cAIPathDB::GetCellVertex(tAIPathCellID cell, int index) const
 356 {
 357    cAIPathDB_NormalizeVertexIndex(index);
 358    return m_Vertices[m_CellVertices[m_Cells[cell].firstVertex + index].id].pt;
 359 }
 360
 361 ///////////////////////////////////////
 362
 363 inline tAIPathVertexID cAIPathDB::GetCellVertexID(tAIPathCellID cell, int index) const
 364 {
 365    cAIPathDB_NormalizeVertexIndex(index);
 366    return m_CellVertices[m_Cells[cell].firstVertex + index].id;
 367 }
 368
 369 ///////////////////////////////////////
 370
 371 inline void cAIPathDB::GetCellVertexFull(tAIPathCellID cell, int index, mxs_vector * pVertex, tAIPathVertexID * pVertexID) const
 372 {
 373    cAIPathDB_NormalizeVertexIndex(index);
 374    *pVertexID = m_CellVertices[m_Cells[cell].firstVertex + index].id;
 375    *pVertex   = m_Vertices[*pVertexID].pt;
 376 }
 377
 378 ///////////////////////////////////////
 379 #if 0
 380 inline int cAIPathDB::GetCellEdgeInfo(tAIPathCellID cell, int index) const
 381 {
 382    cAIPathDB_NormalizeVertexIndex(index);
 383    return m_CellVertices[m_Cells[cell].firstVertex + index].edgeInfo;
 384 }
 385 #endif
 386 ///////////////////////////////////////
 387 #if 0
 388 inline BOOL cAIPathDB::IsCellEdgeLinked(tAIPathCellID cell, int index) const
 389 {
 390    return m_CellVertices[m_Cells[cell].firstVertex + index].hasLinks;
 391 }
 392 #endif
 393 ///////////////////////////////////////
 394
 395 inline const mxs_vector & cAIPathDB::GetVertex(tAIPathVertexID id) const
 396 {
 397    return m_Vertices[id].pt;
 398 }
 399
 400 ///////////////////////////////////////
 401
 402 inline int cAIPathDB::GetVertexInfo(tAIPathVertexID id) const
 403 {
 404    return m_Vertices[id].ptInfo;
 405 }
 406
 407 ///////////////////////////////////////
 408
 409 inline ObjID cAIPathDB::GetCellDoor(tAIPathCellID cell)
 410 {
 411    sAICellDoor * pCellDoor = m_CellToDoorsTable.Search(cell);
 412    if (!pCellDoor)
 413       return OBJ_NULL;
 414    return pCellDoor->door;
 415 }
 416
 417 ///////////////////////////////////////
 418
 419 inline sbool cAIPathDB::IsUnpathable(tAIPathCellID cell)
 420 {
 421    return (m_Cells[cell].pathFlags & kAIPF_Unpathable);
 422 }
 423
 424 ///////////////////////////////////////
 425
 426 inline sbool cAIPathDB::IsBelowDoor(tAIPathCellID cell)
 427 {
 428    return (m_Cells[cell].pathFlags & kAIPF_BelowDoor);
 429 }
 430
 431 ///////////////////////////////////////
 432
 433 inline sbool cAIPathDB::IsBlockedOBB(tAIPathCellID cell)
 434 {
 435    return (m_Cells[cell].pathFlags & kAIPF_BlockingOBB);
 436 }
 437
 438 ///////////////////////////////////////
 439
 440 inline sbool cAIPathDB::IsActiveMovingTerrain(tAIPathCellID cell)
 441 {
 442    return (m_Cells[cell].pathFlags & kAIPF_ActiveMovingTerrain);
 443 }
 444
 445 ///////////////////////////////////////
 446
 447 inline void cAIPathDB::MarkBegin()
 448 {
 449    m_nMarkedCells = 0;
 450 }
 451
 452 ///////////////////////////////////////
 453
 454 inline void cAIPathDB::Mark(tAIPathCellID cell)
 455 {
 456    m_Marks[cell] = TRUE;
 457    if (m_MarkedCells.Size() == m_nMarkedCells)
 458       m_MarkedCells.Grow(16);
 459    m_MarkedCells[m_nMarkedCells] = cell;
 460    m_nMarkedCells++;
 461 }
 462
 463 ///////////////////////////////////////
 464
 465 inline void cAIPathDB::Unmark(tAIPathCellID cell)
 466 {
 467    m_Marks[cell] = FALSE;
 468 }
 469
 470 ///////////////////////////////////////
 471
 472 inline BOOL cAIPathDB::GetMark(tAIPathCellID cell)
 473 {
 474    return m_Marks[cell];
 475 }
 476
 477 ///////////////////////////////////////
 478
 479 inline void cAIPathDB::MarkEnd()
 480 {
 481    register int                         i   = m_nMarkedCells;
 482    register sbool * const               pm  = m_Marks.AsPointer();
 483    register const tAIPathCellID * const pid = m_MarkedCells.AsPointer();
 484
 485    while (--i >= 0)
 486       *(pm + *(pid + i)) = FALSE;
 487 }
 488
 489 ///////////////////////////////////////////////////////////////////////////////
 490
 491 inline BOOL cAIPathDB::CanPathfindBetweenZones(eAIPathZoneType ZoneType, tAIPathZone zone1, tAIPathZone zone2, tAIPathOkBits okBits)
 492 {
 493    if (zone1 == zone2)
 494       return TRUE;
 495
 496    if (zone1 == AI_ZONE_ALL || zone2 == AI_ZONE_ALL)
 497       return TRUE;
 498
 499    if (zone1 == AI_ZONE_SOLO || zone2 == AI_ZONE_SOLO)
 500       return FALSE;
 501
 502    // the okbits must satisfy all okbits between the zones
 503    tAIPathOkBits zoneOkBits = GetZoneOkBits(ZoneType, zone1, zone2);
 504
 505    if ((zoneOkBits != 0) && ((zoneOkBits & okBits & kNoConditionMask) == zoneOkBits))
 506       return TRUE;
 507    else
 508       return FALSE;
 509 }
 510
 511 ////////////////////////////////////////
 512
 513 inline tAIPathZone cAIPathDB::GetCellZone(eAIPathZoneType ZoneType, tAIPathCellID cell)
 514 {
 515    if (cell < m_ZoneDatabases[ZoneType].m_CellZones.Size())
 516       return m_ZoneDatabases[ZoneType].m_CellZones[cell];
 517    else
 518       return 0;
 519 }
 520
 521 ////////////////////////////////////////
 522
 523 inline tAIPathOkBits cAIPathDB::GetZoneOkBits(eAIPathZoneType ZoneType, tAIPathZone zone1, tAIPathZone zone2)
 524 {
 525    if (zone1 == AI_ZONE_SOLO || zone2 == AI_ZONE_SOLO)
 526       return 0;
 527
 528    int key = (zone1 << 16) | zone2;
 529
 530    sZoneOkBitsMap *pMap = m_ZoneDatabases[ZoneType].m_ZonePairTable.Search(key);
 531
 532    if (pMap == NULL)
 533       return 0;
 534    else
 535       return pMap->okBits;
 536 }
 537
 538 ////////////////////////////////////////
 539
 540 inline void cAIPathDB::SetZoneOkBits(eAIPathZoneType ZoneType, tAIPathZone zone1, tAIPathZone zone2, tAIPathOkBits okBits)
 541 {
 542    if (zone1 == AI_ZONE_SOLO || zone2 == AI_ZONE_SOLO)
 543       return;
 544
 545    sZoneOkBitsMap *pMap = new sZoneOkBitsMap;
 546
 547    pMap->key = (zone1 << 16) | zone2;
 548    pMap->okBits = okBits;
 549
 550    m_ZoneDatabases[ZoneType].m_ZonePairTable.RemoveByKey(pMap->key);
 551    m_ZoneDatabases[ZoneType].m_ZonePairTable.Insert(pMap);
 552 }
 553
 554 ///////////////////////////////////////////////////////////////////////////////
 555
 556 #pragma pack()
 557
 558 #include <undbmem.h>
 559
 560 #endif /* !__AIPATHDB_H */