1 /** 2 * @file 3 * @brief grid pathfinding and routing 4 */ 5 6 /* 7 All original material Copyright (C) 2002-2013 UFO: Alien Invasion. 8 9 Copyright (C) 1997-2001 Id Software, Inc. 10 11 This program is free software; you can redistribute it and/or 12 modify it under the terms of the GNU General Public License 13 as published by the Free Software Foundation; either version 2 14 of the License, or (at your option) any later version. 15 16 This program is distributed in the hope that it will be useful, 17 but WITHOUT ANY WARRANTY; without even the implied warranty of 18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 19 20 See the GNU General Public License for more details. 21 22 You should have received a copy of the GNU General Public License 23 along with this program; if not, write to the Free Software 24 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 25 26 */ 27 28 #pragma once 29 30 /*============================================================== 31 GLOBAL TYPES 32 ==============================================================*/ 33 #if defined(COMPILE_MAP) 34 #define RT_COMPLETEBOXTRACE_SIZE(mapTiles,b,list) TR_SingleTileBoxTrace((mapTiles), Line(),(b),TRACING_ALL_VISIBLE_LEVELS, MASK_ALL, 0) 35 #define RT_COMPLETEBOXTRACE_PASSAGE(mapTiles,line,b,list) TR_SingleTileBoxTrace((mapTiles), (line),(b),TRACING_ALL_VISIBLE_LEVELS, MASK_IMPASSABLE, MASK_PASSABLE) 36 37 #elif defined(COMPILE_UFO) 38 #define RT_COMPLETEBOXTRACE_SIZE(mapTiles,b,list) CM_EntCompleteBoxTrace((mapTiles), Line(),(b),TRACING_ALL_VISIBLE_LEVELS, MASK_ALL, 0, (list)) 39 #define RT_COMPLETEBOXTRACE_PASSAGE(mapTiles,line,b,list) CM_EntCompleteBoxTrace((mapTiles), (line),(b),TRACING_ALL_VISIBLE_LEVELS, MASK_IMPASSABLE, MASK_PASSABLE, (list)) 40 41 #else 42 #error Either COMPILE_MAP or COMPILE_UFO must be defined in order for tracing.c to work. 43 #endif 44 45 /* Decide whether we are doing uni- or bidirectional conclusions from our traces. 46 * This constant is used in both a boolean and an integer way, 47 * so it must only be set to 0 or 1 ! */ 48 #define RT_IS_BIDIRECTIONAL 0 49 50 /*============================================================== 51 MACROS 52 ==============================================================*/ 53 /** 54 * @brief Some macros to access routing table values as described above. 55 * @note P/N = positive/negative; X/Y =direction 56 */ 57 /* route - Used by Grid_* only */ 58 /** @note IMPORTANT: actorSize is 1 or greater!!! */ 59 60 #define RT_CONN_PX(r, actorSize, x, y, z) (r.getConn(actorSize, x, y, z, 0)) 61 #define RT_CONN_NX(r, actorSize, x, y, z) (r.getConn(actorSize, x, y, z, 1)) 62 #define RT_CONN_PY(r, actorSize, x, y, z) (r.getConn(actorSize, x, y, z, 2)) 63 #define RT_CONN_NY(r, actorSize, x, y, z) (r.getConn(actorSize, x, y, z, 3)) 64 65 #define RT_CONN_PX_PY(r, actorSize, x, y, z) (r.getConn(actorSize, x, y, z, 4)) 66 #define RT_CONN_PX_NY(r, actorSize, x, y, z) (r.getConn(actorSize, x, y, z, 7)) 67 #define RT_CONN_NX_PY(r, actorSize, x, y, z) (r.getConn(actorSize, x, y, z, 6)) 68 #define RT_CONN_NX_NY(r, actorSize, x, y, z) (r.getConn(actorSize, x, y, z, 5)) 69 70 #define RT_STEPUP_PX(r, actorSize, x, y, z) (r.getStepup(actorSize, x, y, z, 0)) 71 #define RT_STEPUP_NX(r, actorSize, x, y, z) (r.getStepup(actorSize, x, y, z, 1)) 72 #define RT_STEPUP_PY(r, actorSize, x, y, z) (r.getStepup(actorSize, x, y, z, 2)) 73 #define RT_STEPUP_NY(r, actorSize, x, y, z) (r.getStepup(actorSize, x, y, z, 3)) 74 75 #define RT_STEPUP_PX_PY(r, actorSize, x, y, z) (r.getStepup(actorSize, x, y, z, 4)) 76 #define RT_STEPUP_PX_NY(r, actorSize, x, y, z) (r.getStepup(actorSize, x, y, z, 7)) 77 #define RT_STEPUP_NX_PY(r, actorSize, x, y, z) (r.getStepup(actorSize, x, y, z, 6)) 78 #define RT_STEPUP_NX_NY(r, actorSize, x, y, z) (r.getStepup(actorSize, x, y, z, 5)) 79 80 81 /** @brief These macros are meant to correctly convert from model units to QUANT units and back. */ 82 /* Surfaces used as floors are rounded up. */ 83 #define ModelFloorToQuant(x) (ceil((x) / QUANT)) 84 /* Surfaces used as ceilings are rounded down. */ 85 #define ModelCeilingToQuant(x) (floor((x) / QUANT)) 86 /* Going from QUANT units back to model units returns the approximation of the QUANT unit. */ 87 #define QuantToModel(x) ((x) * QUANT) 88 89 /** 90 * @brief SizedPosToVect locates the center of an actor based on size and position. 91 */ 92 #define SizedPosToVec(p, actorSize, v) { \ 93 assert(actorSize > ACTOR_SIZE_INVALID); \ 94 assert(actorSize <= ACTOR_MAX_SIZE); \ 95 v[0] = ((int)p[0] - 128) * UNIT_SIZE + (UNIT_SIZE * actorSize) / 2; \ 96 v[1] = ((int)p[1] - 128) * UNIT_SIZE + (UNIT_SIZE * actorSize) / 2; \ 97 v[2] = (int)p[2] * UNIT_HEIGHT + UNIT_HEIGHT / 2; \ 98 } 99 100 101 /* 102 =============================================================================== 103 SHARED EXTERNS (cmodel.c and ufo2map/routing.c) 104 =============================================================================== 105 */ 106 107 extern bool debugTrace; 108 109 /* 110 =============================================================================== 111 GAME RELATED TRACING 112 =============================================================================== 113 */ 114 115 116 int RT_CheckCell(mapTiles_t* mapTiles, Routing &routing, const int actorSize, const int x, const int y, const int z, const char** list); 117 void RT_UpdateConnectionColumn(mapTiles_t* mapTiles, Routing &routing, const int actorSize, const int x, const int y, const int dir, const char** list); 118 bool RT_AllCellsBelowAreFilled(const Routing &routing, const int actorSize, const pos3_t pos); 119 void RT_GetMapSize(mapTiles_t* mapTiles, vec3_t map_min, vec3_t map_max); 120 bool RT_CanActorStandHere(const Routing &routing, const int actorSize, const pos3_t pos); 121 122 123 /* 124 ========================================================== 125 DEBUGGING CODE 126 ========================================================== 127 */ 128 129 #ifdef DEBUG 130 void RT_DumpWholeMap(mapTiles_t* mapTiles, const Routing &routing); 131 int RT_DebugSpecial(mapTiles_t* mapTiles, Routing &routing, const int actorSize, const int x, const int y, const int dir, const char** list); 132 void RT_DebugPathDisplay (Routing &routing, const int actorSize, int x, int y, int z); 133 #endif 134 void RT_WriteCSVFiles(const Routing &routing, const char* baseFilename, const ipos3_t mins, const ipos3_t maxs); 135