1 #pragma once 2 3 #include "defines.h" 4 #include "mathlib.h" 5 #include "shared.h" 6 #include "../common/filesys.h" 7 8 /* 9 ============================================================== 10 MAP CONFIGURATION 11 ============================================================== 12 */ 13 14 /** 15 * @brief plane_t structure 16 */ 17 typedef struct cBspPlane_s { 18 vec3_t normal; 19 float dist; 20 byte type; /**< for fast side tests */ 21 } cBspPlane_t; 22 23 typedef struct cBspModel_s { 24 vec3_t mins, maxs; /**< the absolute mins and maxs values of the bmodel */ 25 vec3_t origin, angles, shift; /**< used to orient doors and rotating entities */ 26 int32_t headnode; 27 /** @note Not used by ufo2map */ 28 int tile; /**< which tile in assembly */ 29 /** @note Used only by ufo2map */ 30 int firstface, numfaces; /**< submodels just draw faces without walking the bsp tree */ 31 } cBspModel_t; 32 33 /** @sa dBspTexinfo_t */ 34 typedef struct cBspSurface_s { 35 char name[MAX_QPATH]; /**< the texture name */ 36 uint32_t surfaceFlags; /**< surface flags SURF_* */ 37 uint32_t value; /**< currently not used except in loading CMod_LoadSurfaces */ 38 byte* lightmap; /**< lightmap samples for server side visibility lookup */ 39 } cBspSurface_t; 40 41 typedef struct cBspNode_s { 42 cBspPlane_t* plane; 43 vec3_t mins, maxs; 44 int32_t children[2]; /**< negative numbers are leafs */ 45 } cBspNode_t; 46 47 typedef struct cBspBrushSide_s { 48 cBspPlane_t* plane; 49 cBspSurface_t* surface; 50 } cBspBrushSide_t; 51 52 typedef struct cBspLeaf_s { 53 uint32_t contentFlags; 54 unsigned short firstleafbrush; 55 unsigned short numleafbrushes; 56 } cBspLeaf_t; 57 58 typedef struct cBspBrush_s { 59 uint32_t contentFlags; /**< the CONTENTS_* mask */ 60 int numsides; /**< number of sides for this models - start to count from firstbrushside */ 61 int firstbrushside; /**< first brush in the list of this model */ 62 int checkcount; /**< to avoid repeated testings */ 63 } cBspBrush_t; 64 65 /** 66 * @brief Data for line tracing (?) 67 */ 68 typedef struct tnode_s { 69 int type; 70 vec3_t normal; 71 float dist; 72 int32_t children[2]; 73 int pad; 74 } tnode_t; 75 76 typedef struct chead_s { 77 int cnode; 78 int level; 79 } cBspHead_t; 80 81 /** 82 * @brief Stores the data of a map tile, mostly the BSP stuff 83 */ 84 class MapTile { 85 public: 86 char name[MAX_QPATH]; 87 int idx; 88 89 int numbrushsides; 90 cBspBrushSide_t* brushsides; 91 92 int numtexinfo; 93 cBspSurface_t* surfaces; 94 95 int numplanes; 96 cBspPlane_t* planes; /* numplanes + 12 for box hull */ 97 98 int numnodes; 99 cBspNode_t* nodes; /* numnodes + 6 for box hull */ 100 101 int numleafs; 102 cBspLeaf_t* leafs; 103 int emptyleaf; 104 105 int numleafbrushes; 106 unsigned short* leafbrushes; 107 108 int nummodels; 109 cBspModel_t* models; 110 111 int numbrushes; 112 cBspBrush_t* brushes; 113 114 /* tracing box */ 115 cBspPlane_t* box_planes; 116 int box_headnode; 117 cBspBrush_t* box_brush; 118 cBspLeaf_t* box_leaf; 119 120 /* line tracing */ 121 tnode_t* tnodes; 122 int numtheads; 123 intptr_t thead[LEVEL_MAX]; 124 int theadlevel[LEVEL_MAX]; 125 126 int numcheads; 127 cBspHead_t cheads[MAX_MAP_NODES]; 128 129 ipos3_t wpMins; 130 ipos3_t wpMaxs; 131 132 byte lightquant; 133 byte* lightdata; 134 }; 135 136 /** 137 * @brief Pathfinding routing structure and tile layout 138 * @note Comments strongly WIP! 139 * 140 * ROUTE 141 * Information stored in "route" 142 * 143 * connections (see Grid_MoveCheck) 144 * mask description 145 * 0x10 0001 0000 connection to +x (height ignored?) 146 * 0x20 0010 0000 connection to -x (height ignored?) 147 * 0x40 0100 0000 connection to +y (height ignored?) 148 * 0x80 1000 0000 connection to -y (height ignored?) 149 * 150 * See "h = map->route[z][y][x] & 0x0F;" and "if (map->route[az][ay][ax] & 0x0F) > h)" in CM_UpdateConnection 151 * 0x0F 0000 1111 some height info? 152 * 153 * FALL 154 * Information about how much you'll fall down from x,y position? 155 * I THINK as long as a bit is set you will fall down ... 156 * See "while (map->fall[ny][nx] & (1 << z)) z--;" in Grid_MoveMark 157 * 158 * STEP 159 * 160 * 0000 0000 161 * Access with "step[y][x] & (1 << z)" 162 * Guess: 163 * Each bit if set to 0 if a unit can step on it (e.g. ground or chair) or it's 1 if there is a wall or similar (i.e. it's blocked). 164 * GERD THINKS it shows stairs and step-on stuff 165 * Search for "sh = (map->step[y][x] & (1 << z)) ? sh_big : sh_low;" and similar. 166 * "sh" seems to mean "step height" 167 * 168 * AREA 169 * The needed TUs to walk to a given position. (See Grid_MoveLength) 170 * 171 * AREASTORED 172 * The stored mask (the cached move) of the routing data. (See Grid_MoveLength) 173 * 174 * TILE LAYOUT AND PATHING 175 * Maps are comprised of tiles. Each tile has a number of levels corresponding to entities in game. 176 * All static entities in the tile are located in levels 0-255, with the main world located in 0. 177 * Levels 256-258 are reserved, see LEVEL_* constants in src/shared/shared.h. Non-static entities 178 * (ET_BREAKABLE and ET_ROTATING, ET_DOOR, etc.) are contained in levels 259 and above. These entities' 179 * models are named *##, beginning from 1, and each corresponds to level LEVEL_MAX - 1 + ##. 180 * 181 * The code that handles the pathing has separate checks for the static and non-static levels in a tile. 182 * The static levels have their bounds precalculated by CM_MakeTracingNodes and stored in tile->theads. 183 * The other levels are checked in the fly when Grid_CheckUnit is called. 184 * 185 */ 186 typedef struct routing_s { 187 byte _stepup[PATHFINDING_HEIGHT][PATHFINDING_WIDTH][PATHFINDING_WIDTH][CORE_DIRECTIONS]; 188 byte _route[PATHFINDING_HEIGHT][PATHFINDING_WIDTH][PATHFINDING_WIDTH][CORE_DIRECTIONS]; 189 signed char _floor[PATHFINDING_HEIGHT][PATHFINDING_WIDTH][PATHFINDING_WIDTH]; 190 byte _ceil[PATHFINDING_HEIGHT][PATHFINDING_WIDTH][PATHFINDING_WIDTH]; 191 setStepuprouting_s192 inline void setStepup (const int x, const int y, const int z, const int dir, const int val) { 193 _stepup[z][y][x][dir] = val; 194 } getStepuprouting_s195 inline byte getStepup (const int x, const int y, const int z, const int dir) const { 196 return _stepup[z][y][x][dir]; 197 } 198 setConnrouting_s199 inline void setConn (const int x, const int y, const int z, const int dir, const int val) { 200 _route[z][y][x][dir] = val; 201 } getConnrouting_s202 inline byte getConn (const int x, const int y, const int z, const int dir) const { 203 return _route[z][y][x][dir]; 204 } 205 setCeilingrouting_s206 inline void setCeiling (const int x, const int y, const int z, const int val) { 207 _ceil[z][y][x] = val; 208 } getCeilingrouting_s209 inline byte getCeiling (const int x, const int y, const int z) const { 210 return _ceil[z][y][x]; 211 } getCeilingrouting_s212 inline byte getCeiling (const pos3_t pos) const { 213 return getCeiling(pos[0], pos[1], pos[2]); 214 } 215 setFloorrouting_s216 inline void setFloor (const int x, const int y, const int z, const int val) { 217 _floor[z][y][x] = val; 218 } getFloorrouting_s219 inline signed char getFloor (const int x, const int y, const int z) const { 220 return _floor[z][y][x]; 221 } getFloorrouting_s222 inline signed char getFloor (const pos3_t pos) const { 223 return getFloor(pos[0], pos[1], pos[2]); 224 } 225 } routing_t; 226 227 /** @brief The home of the routing tables 228 * 229 * The purpose of this class is 230 * 1. to hide the actual dimensions of the map. Atm we allocate the maximum mapsize, This is about to change. 231 * 2. to hide the way the info for different actor sizes is handled. That will changen in the future. 232 */ 233 /* A special bit mask indicating that the stepup causes the actor to rise a cell. */ 234 #define PATHFINDING_BIG_STEPUP 0x80 235 /* A special bit mask indicating that the stepup causes the actor to walk down a cell. */ 236 #define PATHFINDING_BIG_STEPDOWN 0x40 237 238 class Routing 239 { 240 routing_t routes[ACTOR_MAX_SIZE]; /**< routing table */ 241 public: 242 Routing()243 Routing () { 244 init(); 245 } init()246 inline void init () { 247 OBJZERO(*this); 248 } setFloor(const int actorSize,const int x,const int y,const int z,const int val)249 inline void setFloor (const int actorSize, const int x, const int y, const int z, const int val) { 250 routes[actorSize - 1].setFloor(x, y, z, val); 251 } getFloor(const actorSizeEnum_t actorSize,const pos3_t pos)252 inline signed char getFloor (const actorSizeEnum_t actorSize, const pos3_t pos) const { 253 return routes[actorSize - 1].getFloor(pos); 254 } getFloor(const actorSizeEnum_t actorSize,const int x,const int y,const int z)255 inline signed char getFloor (const actorSizeEnum_t actorSize, const int x, const int y, const int z) const { 256 return routes[actorSize - 1].getFloor(x, y, z); 257 } 258 setCeiling(const actorSizeEnum_t actorSize,const int x,const int y,const int z,const int val)259 inline void setCeiling (const actorSizeEnum_t actorSize, const int x, const int y, const int z, const int val) { 260 routes[actorSize - 1].setCeiling(x, y, z, val); 261 } getCeiling(const int actorSize,const pos3_t pos)262 inline byte getCeiling (const int actorSize, const pos3_t pos) const { 263 return routes[actorSize - 1].getCeiling(pos); 264 } getCeiling(const int actorSize,const int x,const int y,const int z)265 inline byte getCeiling (const int actorSize, const int x, const int y, const int z) const { 266 return routes[actorSize - 1].getCeiling(x, y, z); 267 } 268 setFilled(const actorSizeEnum_t actorSize,const int x,const int y,const int lowZ,const int highZ)269 inline void setFilled (const actorSizeEnum_t actorSize, const int x, const int y, const int lowZ, const int highZ) 270 { 271 int i; 272 for (i = lowZ; i <= highZ; i++) { 273 routes[actorSize - 1].setFloor(x, y, i, CELL_HEIGHT); /* There is no floor in this cell. */ 274 routes[actorSize - 1].setCeiling(x, y, i, 0); /* There is no ceiling, the true indicator of a filled cell. */ 275 } 276 } 277 setConn(const int actorSize,const int x,const int y,const int z,const int dir,const int val)278 inline void setConn (const int actorSize, const int x, const int y, const int z, const int dir, const int val) { 279 routes[actorSize - 1].setConn(x, y, z, dir, val); 280 } getConn(const int actorSize,const int x,const int y,const int z,const int dir)281 inline byte getConn (const int actorSize, const int x, const int y, const int z, const int dir) const { 282 return routes[actorSize - 1].getConn(x, y, z, dir); 283 } getConn(const actorSizeEnum_t actorSize,const pos3_t pos,const int dir)284 inline byte getConn (const actorSizeEnum_t actorSize, const pos3_t pos, const int dir) const { 285 return routes[actorSize - 1].getConn(pos[0], pos[1], pos[2], dir); 286 } 287 setStepup(const int actorSize,const int x,const int y,const int z,const int dir,const int val)288 inline void setStepup (const int actorSize, const int x, const int y, const int z, const int dir, const int val) { 289 routes[actorSize - 1].setStepup(x, y, z, dir, val); 290 } getStepup(const int actorSize,const int x,const int y,const int z,const int dir)291 inline byte getStepup (const int actorSize, const int x, const int y, const int z, const int dir) const { 292 return routes[actorSize - 1].getStepup(x, y, z, dir); 293 } 294 /** @brief return the value without the flags for z-level change */ getStepupHeight(const int actorSize,const int x,const int y,const int z,const int dir)295 inline byte getStepupHeight (const int actorSize, const int x, const int y, const int z, const int dir) const { 296 return routes[actorSize - 1].getStepup(x, y, z, dir) & ~(PATHFINDING_BIG_STEPDOWN | PATHFINDING_BIG_STEPUP); 297 } isStepDownLevel(const actorSizeEnum_t actorSize,const pos3_t pos,const int dir)298 inline byte isStepDownLevel (const actorSizeEnum_t actorSize, const pos3_t pos, const int dir) const { 299 return routes[actorSize - 1].getStepup(pos[0], pos[1], pos[2], dir) & PATHFINDING_BIG_STEPDOWN; 300 } isStepUpLevel(const actorSizeEnum_t actorSize,const pos3_t pos,const int dir)301 inline byte isStepUpLevel (const actorSizeEnum_t actorSize, const pos3_t pos, const int dir) const { 302 return routes[actorSize - 1].getStepup(pos[0], pos[1], pos[2], dir) & PATHFINDING_BIG_STEPUP; 303 } 304 305 /** note: not sure if this function qualifies for being inlined. But if we didn't, 306 * we'd have to link routing.cpp to radiant, which is probably worse. */ copyPosData(const Routing & other,actorSizeEnum_t actorSize,const int x,const int y,const int z,const int sX,const int sY,const int sZ)307 inline void copyPosData (const Routing &other, actorSizeEnum_t actorSize, const int x, const int y, const int z, const int sX, const int sY, const int sZ) 308 { 309 setFloor(actorSize, x, y, z, other.getFloor(actorSize, x - sX, y - sY, z - sZ)); 310 setCeiling(actorSize, x, y, z, other.getCeiling(actorSize, x - sX, y - sY, z - sZ)); 311 int dir; 312 for (dir = 0; dir < CORE_DIRECTIONS; dir++) { 313 setConn(actorSize, x, y, z, dir, other.getConn(actorSize, x - sX, y - sY, z - sZ, dir)); 314 setStepup(actorSize, x, y, z, dir, other.getStepup(actorSize, x - sX, y - sY, z - sZ, dir)); 315 } 316 } 317 }; 318 319 typedef struct mapData_s { 320 /** @note holds all entity data as a single parsable string */ 321 char mapEntityString[MAX_MAP_ENTSTRING]; 322 323 /** @note holds the number of inline entities, e.g. ET_DOOR */ 324 int numInline; 325 326 unsigned mapChecksum; 327 328 /** @brief Used to track where rerouting needs to occur. 329 * @todo not threadsafe */ 330 byte reroute[ACTOR_MAX_SIZE][PATHFINDING_WIDTH][PATHFINDING_WIDTH]; 331 Routing routing; 332 333 /** 334 * @note The vectors are from 0 up to 2*MAX_WORLD_WIDTH - but not negative 335 * @note holds the smallest bounding box that will contain the map 336 * @sa CL_ClampCamToMap 337 * @sa CL_OutsideMap 338 * @sa CMod_GetMapSize 339 * @sa SV_ClearWorld 340 */ 341 AABB mapBox; 342 } mapData_t; 343 344 typedef struct { 345 vec3_t mins, maxs; 346 vec3_t origin; /**< for sounds or lights */ 347 int32_t headnode; 348 int firstface, numfaces; /**< submodels just draw faces without walking the bsp tree */ 349 } dBspModel_t; 350 351 typedef struct { 352 float point[3]; 353 } dBspVertex_t; 354 355 typedef struct { 356 vec3_t normal; 357 } dBspNormal_t; 358 359 /** 360 * @note 0-2 are axial planes 361 */ 362 typedef struct { 363 vec3_t normal; /**< normal vector */ 364 float dist; /**< distance from origin */ 365 int type; /**< PLANE_X - PLANE_ANYZ */ 366 } dBspPlane_t; 367 368 typedef struct { 369 int32_t planenum; /**< index into the planes array */ 370 int32_t children[2]; /**< negative numbers are -(leafs + 1), not nodes */ 371 short mins[3]; /**< for frustum culling */ 372 short maxs[3]; /**< for frustum culling */ 373 unsigned short firstface; /**< index into the faces array */ 374 unsigned short numfaces; /**< counting both sides */ 375 } dBspNode_t; 376 377 /** @sa cBspSurface_t */ 378 typedef struct texinfo_s { 379 float vecs[2][4]; /**< [s/t][xyz offset] */ 380 uint32_t surfaceFlags; /**< miptex flags + overrides */ 381 uint32_t value; /**< light emission, etc */ 382 char texture[32]; /**< texture name */ 383 } dBspTexinfo_t; 384 385 /** 386 * @note note that edge 0 is never used, because negative edge nums are used for 387 * counterclockwise use of the edge in a face 388 */ 389 typedef struct { 390 unsigned short v[2]; /**< vertex indices */ 391 } dBspEdge_t; 392 393 typedef struct { 394 uint16_t planenum; /**< planenum is used in lighting stage, but not in ufo */ 395 short side; 396 397 int firstedge; /**< we must support > 64k edges */ 398 short numedges; 399 short texinfo; /**< index in the global texinfo array */ 400 401 /** lighting info */ 402 int lightofs[LIGHTMAP_MAX]; /**< start of [surfsize] samples */ 403 } dBspSurface_t; 404 405 /** @brief convex region of space in the BSP tree */ 406 typedef struct { 407 uint32_t contentFlags; /**< OR of all brushes */ 408 409 short area; 410 411 short mins[3]; /**< for frustum culling */ 412 short maxs[3]; /**< for frustum culling */ 413 414 uint16_t firstleafbrush; 415 uint16_t numleafbrushes; 416 } dBspLeaf_t; 417 418 typedef struct { 419 uint16_t planenum; /**< facing out of the leaf 420 * index info the planes array for this side */ 421 short texinfo; 422 } dBspBrushSide_t; 423 424 typedef struct { 425 int firstbrushside; 426 int numsides; 427 uint32_t contentFlags; /**< OR of all brushes */ 428 } dBspBrush_t; 429 430 typedef struct { 431 /* tracing box */ 432 dBspPlane_t* box_planes; 433 int box_headnode; 434 dBspBrush_t* box_brush; 435 dBspLeaf_t* box_leaf; 436 437 /* line tracing */ 438 tnode_t* tnodes; 439 int numtheads; 440 int thead[LEVEL_MAX]; 441 int theadlevel[LEVEL_MAX]; 442 443 /* Used by TR_TileBoxTrace */ 444 int numcheads; 445 cBspHead_t cheads[MAX_MAP_NODES]; 446 447 /* ---- */ 448 int entdatasize; 449 char entdata[MAX_MAP_ENTSTRING]; 450 451 int routedatasize; 452 byte routedata[MAX_MAP_ROUTING]; 453 454 int lightdatasize[LIGHTMAP_MAX]; 455 byte lightdata[LIGHTMAP_MAX][MAX_MAP_LIGHTING]; 456 457 int nummodels; 458 dBspModel_t models[MAX_MAP_MODELS]; 459 460 int numleafs; 461 dBspLeaf_t leafs[MAX_MAP_LEAFS]; 462 int emptyleaf; 463 464 int numplanes; 465 dBspPlane_t planes[MAX_MAP_PLANES]; 466 467 int numnormals; 468 dBspNormal_t normals[MAX_MAP_VERTS]; 469 470 int numvertexes; 471 dBspVertex_t vertexes[MAX_MAP_VERTS]; 472 473 int numnodes; 474 dBspNode_t nodes[MAX_MAP_NODES]; 475 476 int numtexinfo; 477 dBspTexinfo_t texinfo[MAX_MAP_TEXINFO]; 478 479 int numfaces; 480 dBspSurface_t faces[MAX_MAP_FACES]; 481 482 int numedges; 483 dBspEdge_t edges[MAX_MAP_EDGES]; 484 485 int numleafbrushes; 486 unsigned short leafbrushes[MAX_MAP_LEAFBRUSHES]; 487 488 /** 489 * references the edges array 490 * positive or negative values are possible. 491 * the absolute value is the index into the edges array 492 * positive: the edge is defined from the first to the second vertex 493 * negative: the second to the first vertex 494 */ 495 int numsurfedges; 496 int surfedges[MAX_MAP_SURFEDGES]; 497 498 int numbrushes; 499 dBspBrush_t dbrushes[MAX_MAP_BRUSHES]; 500 cBspBrush_t brushes[MAX_MAP_BRUSHES]; 501 502 int numbrushsides; 503 dBspBrushSide_t brushsides[MAX_MAP_BRUSHSIDES]; 504 } dMapTile_t; 505