File: | common/routing.cpp |
Location: | line 1262, column 18 |
Description: | The left operand of '-' is a garbage value |
1 | /** | ||
2 | * @file | ||
3 | * @brief grid pathfinding and routing | ||
4 | */ | ||
5 | |||
6 | /* | ||
7 | All original material Copyright (C) 2002-2011 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 | #include "common.h" | ||
29 | #include "routing.h" | ||
30 | |||
31 | /* | ||
32 | =============================================================================== | ||
33 | MAP TRACING DEBUGGING TABLES | ||
34 | =============================================================================== | ||
35 | */ | ||
36 | |||
37 | bool debugTrace = false; | ||
38 | |||
39 | /* | ||
40 | ========================================================== | ||
41 | LOCAL CONSTANTS | ||
42 | ========================================================== | ||
43 | */ | ||
44 | |||
45 | #define RT_NO_OPENING-1 -1 | ||
46 | |||
47 | /* Width of the box required to stand in a cell by an actor's feet. */ | ||
48 | #define halfMicrostepSize(4 / 2 - (0.03125)) (PATHFINDING_MICROSTEP_SIZE4 / 2 - DIST_EPSILON(0.03125)) | ||
49 | /* This is a template for the extents of the box used by an actor's feet. */ | ||
50 | static const box_t footBox = {{-halfMicrostepSize(4 / 2 - (0.03125)), -halfMicrostepSize(4 / 2 - (0.03125)), 0}, | ||
51 | { halfMicrostepSize(4 / 2 - (0.03125)), halfMicrostepSize(4 / 2 - (0.03125)), 0}}; | ||
52 | |||
53 | /* Width of the box required to stand in a cell by an actor's torso. */ | ||
54 | #define half1x1Width(32 * 1 / 2 - 5 - (0.03125)) (UNIT_SIZE32 * 1 / 2 - WALL_SIZE5 - DIST_EPSILON(0.03125)) | ||
55 | #define half2x2Width(32 * 2 / 2 - 5 - (0.03125)) (UNIT_SIZE32 * 2 / 2 - WALL_SIZE5 - DIST_EPSILON(0.03125)) | ||
56 | /* These are templates for the extents of the box used by an actor's torso. */ | ||
57 | static const box_t actor1x1Box = {{-half1x1Width(32 * 1 / 2 - 5 - (0.03125)), -half1x1Width(32 * 1 / 2 - 5 - (0.03125)), 0}, | ||
58 | { half1x1Width(32 * 1 / 2 - 5 - (0.03125)), half1x1Width(32 * 1 / 2 - 5 - (0.03125)), 0}}; | ||
59 | static const box_t actor2x2Box = {{-half2x2Width(32 * 2 / 2 - 5 - (0.03125)), -half2x2Width(32 * 2 / 2 - 5 - (0.03125)), 0}, | ||
60 | { half2x2Width(32 * 2 / 2 - 5 - (0.03125)), half2x2Width(32 * 2 / 2 - 5 - (0.03125)), 0}}; | ||
61 | |||
62 | /* | ||
63 | ========================================================== | ||
64 | LOCAL TYPES | ||
65 | ========================================================== | ||
66 | */ | ||
67 | |||
68 | /** | ||
69 | * @brief RT_data_s contains the essential data that is passed to most of the RT_* functions | ||
70 | */ | ||
71 | typedef struct RT_data_s { | ||
72 | mapTiles_t *mapTiles; | ||
73 | routing_t *map; /**< The routing table */ | ||
74 | actorSizeEnum_t actorSize; /**< The size of the actor, in cells */ | ||
75 | const char **list; /**< The local models list */ | ||
76 | } RT_data_t; | ||
77 | |||
78 | static inline void RT_ConnSet (RT_data_t *rtd, const int x, const int y, const int z, const int dir, const int val) | ||
79 | { | ||
80 | RT_CONN(rtd->map, rtd->actorSize, x, y, z, dir)rtd->map[(rtd->actorSize) - 1].route[(z)][(y)][(x)][(dir )] = val; | ||
81 | } | ||
82 | |||
83 | static inline void RT_StepupSet (RT_data_t *rtd, const int x, const int y, const int z, const int dir, const int val) | ||
84 | { | ||
85 | RT_STEPUP(rtd->map, rtd->actorSize, x, y, z, dir)rtd->map[(rtd->actorSize) - 1].stepup[(z)][(y)][(x)][(dir )] = val; | ||
86 | } | ||
87 | |||
88 | static inline void RT_ConnSetNoGo (RT_data_t *rtd, const int x, const int y, const int z, const int dir) | ||
89 | { | ||
90 | RT_ConnSet(rtd, x, y, z, dir, 0); | ||
91 | RT_STEPUP(rtd->map, rtd->actorSize, x, y, z, dir)rtd->map[(rtd->actorSize) - 1].stepup[(z)][(y)][(x)][(dir )] = PATHFINDING_NO_STEPUP(2 * (64 / 4)); | ||
92 | } | ||
93 | |||
94 | /** | ||
95 | * @brief A 'place' is a part of a grid column where an actor can exist | ||
96 | * Unlike for a grid-cell, floor and ceiling are absolute values | ||
97 | */ | ||
98 | typedef struct place_s { | ||
99 | pos3_t cell; /**< coordinates of the grid-cell this was derived from. */ | ||
100 | int floor; /**< The floor of the place, given in absolute QUANTs */ | ||
101 | int ceiling; /**< The ceiling of it, given in absolute QUANTs. */ | ||
102 | int floorZ; /**< The level (0-7) of the floor. */ | ||
103 | bool usable;/**< does an actor fit in here ? */ | ||
104 | } place_t; | ||
105 | |||
106 | static inline void RT_PlaceInit (const routing_t *map, const actorSizeEnum_t actorSize, place_t *p, const int x, const int y, const int z) | ||
107 | { | ||
108 | const int relCeiling = RT_CEILING(map, actorSize, x, y, z)map[(actorSize) - 1].ceil[(z)][(y)][(x)]; | ||
109 | p->cell[0] = x; | ||
110 | p->cell[1] = y; | ||
111 | p->cell[2] = z; | ||
112 | p->floor = RT_FLOOR(map, actorSize, x, y, z)map[(actorSize) - 1].floor[(z)][(y)][(x)] + z * CELL_HEIGHT(64 / 4); | ||
113 | p->ceiling = relCeiling + z * CELL_HEIGHT(64 / 4); | ||
114 | p->floorZ = std::max(0, p->floor / CELL_HEIGHT(64 / 4)) ; | ||
115 | p->usable = (relCeiling && p->floor > -1 && p->ceiling - p->floor >= PATHFINDING_MIN_OPENING6) ? true : false; | ||
116 | } | ||
117 | |||
118 | static inline bool RT_PlaceIsUsable (const place_t* p) | ||
119 | { | ||
120 | return p->usable; | ||
121 | } | ||
122 | |||
123 | static inline bool RT_PlaceDoesIntersectEnough (const place_t* p, const place_t* other) | ||
124 | { | ||
125 | return (std::min(p->ceiling, other->ceiling) - std::max(p->floor, other->floor) >= PATHFINDING_MIN_OPENING6); | ||
126 | } | ||
127 | |||
128 | /** | ||
129 | * @brief This function detects a special stairway situation, where one place is right | ||
130 | * in front of a stairway and has a floor at eg. 1 and a ceiling at eg. 16. | ||
131 | * The other place has the beginning of the stairway, so the floor is at eg. 6 | ||
132 | * and the ceiling is that of the higher level, eg. 32. | ||
133 | */ | ||
134 | static inline int RT_PlaceIsShifted (const place_t* p, const place_t* other) | ||
135 | { | ||
136 | if (!RT_PlaceIsUsable(p) || !RT_PlaceIsUsable(other)) | ||
137 | return 0; | ||
138 | if (p->floor < other->floor && p->ceiling < other->ceiling) | ||
139 | return 1; /* stepping up */ | ||
140 | if (p->floor > other->floor && p->ceiling > other->ceiling) | ||
141 | return 2; /* stepping down */ | ||
142 | return 0; | ||
143 | } | ||
144 | |||
145 | /** | ||
146 | * @brief An 'opening' describes the connection between two adjacent spaces where an actor can exist in a cell | ||
147 | * @note Note that if size is @c 0, the other members are undefined. They may contain reasonable values, though | ||
148 | */ | ||
149 | typedef struct opening_s { | ||
150 | int size; /**< The opening size (max actor height) that can travel this passage. */ | ||
151 | int base; /**< The base height of the opening, given in abs QUANTs */ | ||
152 | int stepup; /**< The stepup needed to travel through this passage in this direction. */ | ||
153 | int invstepup; /**< The stepup needed to travel through this passage in the opposite direction. */ | ||
154 | } opening_t; | ||
155 | |||
156 | /* | ||
157 | ========================================================== | ||
158 | GRID ORIENTED MOVEMENT AND SCANNING | ||
159 | ========================================================== | ||
160 | */ | ||
161 | |||
162 | #ifdef DEBUG1 | ||
163 | /** | ||
164 | * @brief Dumps contents of a map to console for inspection. | ||
165 | * @sa Grid_RecalcRouting | ||
166 | * @param[in] map The routing map (either server or client map) | ||
167 | * @param[in] actorSize The size of the actor along the X and Y axis in cell units | ||
168 | * @param[in] lx The low end of the x range updated | ||
169 | * @param[in] ly The low end of the y range updated | ||
170 | * @param[in] lz The low end of the z range updated | ||
171 | * @param[in] hx The high end of the x range updated | ||
172 | * @param[in] hy The high end of the y range updated | ||
173 | * @param[in] hz The high end of the z range updated | ||
174 | */ | ||
175 | static void RT_DumpMap (const routing_t *map, actorSizeEnum_t actorSize, int lx, int ly, int lz, int hx, int hy, int hz) | ||
176 | { | ||
177 | int x, y, z; | ||
178 | |||
179 | Com_Printf("\nRT_DumpMap (%i %i %i) (%i %i %i)\n", lx, ly, lz, hx, hy, hz); | ||
180 | for (z = hz; z >= lz; --z) { | ||
181 | Com_Printf("\nLayer %i:\n ", z); | ||
182 | for (x = lx; x <= hx; ++x) { | ||
183 | Com_Printf("%9i", x); | ||
184 | } | ||
185 | Com_Printf("\n"); | ||
186 | for (y = hy; y >= ly; --y) { | ||
187 | Com_Printf("%3i ", y); | ||
188 | for (x = lx; x <= hx; ++x) { | ||
189 | Com_Printf("%s%s%s%s " | ||
190 | , RT_CONN_NX(map, actorSize, x, y, z)(map[(actorSize) - 1].route[(z)][(y)][(x)][(1)]) ? "w" : " " | ||
191 | , RT_CONN_PY(map, actorSize, x, y, z)(map[(actorSize) - 1].route[(z)][(y)][(x)][(2)]) ? "n" : " " | ||
192 | , RT_CONN_NY(map, actorSize, x, y, z)(map[(actorSize) - 1].route[(z)][(y)][(x)][(3)]) ? "s" : " " | ||
193 | , RT_CONN_PX(map, actorSize, x, y, z)(map[(actorSize) - 1].route[(z)][(y)][(x)][(0)]) ? "e" : " " | ||
194 | ); | ||
195 | } | ||
196 | Com_Printf("\n"); | ||
197 | } | ||
198 | } | ||
199 | } | ||
200 | |||
201 | /** | ||
202 | * @brief Dumps contents of the entire client map to console for inspection. | ||
203 | * @param[in] map A pointer to the map being dumped | ||
204 | */ | ||
205 | void RT_DumpWholeMap (mapTiles_t *mapTiles, const routing_t *map) | ||
206 | { | ||
207 | box_t box; | ||
208 | vec3_t normal, origin; | ||
209 | pos3_t start, end, test; | ||
210 | trace_t trace; | ||
211 | int i; | ||
212 | |||
213 | /* Initialize start, end, and normal */ | ||
214 | VectorClear(start)((start)[0]=(start)[1]=(start)[2]=0); | ||
215 | VectorSet(end, PATHFINDING_WIDTH - 1, PATHFINDING_WIDTH - 1, PATHFINDING_HEIGHT - 1)((end)[0]=(((4096 / 32) * 2) - 1), (end)[1]=(((4096 / 32) * 2 ) - 1), (end)[2]=(8 - 1)); | ||
216 | VectorSet(normal, UNIT_SIZE / 2, UNIT_SIZE / 2, UNIT_HEIGHT / 2)((normal)[0]=(32 / 2), (normal)[1]=(32 / 2), (normal)[2]=(64 / 2)); | ||
217 | VectorClear(origin)((origin)[0]=(origin)[1]=(origin)[2]=0); | ||
218 | |||
219 | for (i = 0; i < 3; i++) { | ||
220 | /* Lower positive boundary */ | ||
221 | while (end[i] > start[i]) { | ||
222 | /* Adjust ceiling */ | ||
223 | VectorCopy(start, test)((test)[0]=(start)[0],(test)[1]=(start)[1],(test)[2]=(start)[ 2]); | ||
224 | test[i] = end[i] - 1; /* test is now one floor lower than end */ | ||
225 | /* Prep boundary box */ | ||
226 | PosToVec(test, box.mins)( (box.mins)[0] = ((int)(test)[0] - (4096 / 32)) * 32 + 32 / 2 , (box.mins)[1] = ((int)(test)[1] - (4096 / 32)) * 32 + 32 / 2 , (box.mins)[2] = (int)(test)[2] * 64 + 64 / 2 ); | ||
227 | VectorSubtract(box.mins, normal, box.mins)((box.mins)[0]=(box.mins)[0]-(normal)[0],(box.mins)[1]=(box.mins )[1]-(normal)[1],(box.mins)[2]=(box.mins)[2]-(normal)[2]); | ||
228 | PosToVec(end, box.maxs)( (box.maxs)[0] = ((int)(end)[0] - (4096 / 32)) * 32 + 32 / 2 , (box.maxs)[1] = ((int)(end)[1] - (4096 / 32)) * 32 + 32 / 2 , (box.maxs)[2] = (int)(end)[2] * 64 + 64 / 2 ); | ||
229 | VectorAdd(box.maxs, normal, box.maxs)((box.maxs)[0]=(box.maxs)[0]+(normal)[0],(box.maxs)[1]=(box.maxs )[1]+(normal)[1],(box.maxs)[2]=(box.maxs)[2]+(normal)[2]); | ||
230 | /* Test for stuff in a small box, if there is something then exit while */ | ||
231 | trace = RT_COMPLETEBOXTRACE_SIZE(mapTiles, origin, origin, &box, NULL)CM_EntCompleteBoxTrace((mapTiles), (origin),(origin),(&box ),0x1FF, (-1), 0, (__null)); | ||
232 | if (trace.fraction < 1.0) | ||
233 | break; | ||
234 | /* There is nothing, lower the boundary. */ | ||
235 | end[i]--; | ||
236 | } | ||
237 | |||
238 | /* Raise negative boundary */ | ||
239 | while (end[i] > start[i]) { | ||
240 | /* Adjust ceiling */ | ||
241 | VectorCopy(end, test)((test)[0]=(end)[0],(test)[1]=(end)[1],(test)[2]=(end)[2]); | ||
242 | test[i] = start[i] + 1; /* test is now one floor lower than end */ | ||
243 | /* Prep boundary box */ | ||
244 | PosToVec(start, box.mins)( (box.mins)[0] = ((int)(start)[0] - (4096 / 32)) * 32 + 32 / 2, (box.mins)[1] = ((int)(start)[1] - (4096 / 32)) * 32 + 32 / 2, (box.mins)[2] = (int)(start)[2] * 64 + 64 / 2 ); | ||
245 | VectorSubtract(box.mins, normal, box.mins)((box.mins)[0]=(box.mins)[0]-(normal)[0],(box.mins)[1]=(box.mins )[1]-(normal)[1],(box.mins)[2]=(box.mins)[2]-(normal)[2]); | ||
246 | PosToVec(test, box.maxs)( (box.maxs)[0] = ((int)(test)[0] - (4096 / 32)) * 32 + 32 / 2 , (box.maxs)[1] = ((int)(test)[1] - (4096 / 32)) * 32 + 32 / 2 , (box.maxs)[2] = (int)(test)[2] * 64 + 64 / 2 ); | ||
247 | VectorAdd(box.maxs, normal, box.maxs)((box.maxs)[0]=(box.maxs)[0]+(normal)[0],(box.maxs)[1]=(box.maxs )[1]+(normal)[1],(box.maxs)[2]=(box.maxs)[2]+(normal)[2]); | ||
248 | /* Test for stuff in a small box, if there is something then exit while */ | ||
249 | trace = RT_COMPLETEBOXTRACE_SIZE(mapTiles, origin, origin, &box, NULL)CM_EntCompleteBoxTrace((mapTiles), (origin),(origin),(&box ),0x1FF, (-1), 0, (__null)); | ||
250 | if (trace.fraction < 1.0) | ||
251 | break; | ||
252 | /* There is nothing, raise the boundary. */ | ||
253 | start[i]++; | ||
254 | } | ||
255 | } | ||
256 | |||
257 | /* Dump the client map */ | ||
258 | RT_DumpMap(map, 0, start[0], start[1], start[2], end[0], end[1], end[2]); | ||
259 | } | ||
260 | #endif | ||
261 | |||
262 | /** | ||
263 | * @brief Calculate the map size via model data and store grid size | ||
264 | * in map_min and map_max. This is done with every new map load | ||
265 | * @param[in] mapTiles List of tiles the current (RMA-)map is composed of | ||
266 | * @param[out] map_min The lower extents of the current map. | ||
267 | * @param[out] map_max The upper extents of the current map. | ||
268 | * @sa CMod_LoadRouting | ||
269 | * @sa DoRouting | ||
270 | */ | ||
271 | void RT_GetMapSize (mapTiles_t *mapTiles, vec3_t map_min, vec3_t map_max) | ||
272 | { | ||
273 | box_t box; | ||
274 | const vec3_t normal = {UNIT_SIZE32 / 2, UNIT_SIZE32 / 2, UNIT_HEIGHT64 / 2}; | ||
275 | pos3_t start, end, test; | ||
276 | vec3_t origin; | ||
277 | int i; | ||
278 | trace_t trace; | ||
279 | |||
280 | /* Initialize start, end, and normal */ | ||
281 | VectorSet(start, 0, 0, 0)((start)[0]=(0), (start)[1]=(0), (start)[2]=(0)); | ||
282 | VectorSet(end, PATHFINDING_WIDTH - 1, PATHFINDING_WIDTH - 1, PATHFINDING_HEIGHT - 1)((end)[0]=(((4096 / 32) * 2) - 1), (end)[1]=(((4096 / 32) * 2 ) - 1), (end)[2]=(8 - 1)); | ||
283 | VectorCopy(vec3_origin, origin)((origin)[0]=(vec3_origin)[0],(origin)[1]=(vec3_origin)[1],(origin )[2]=(vec3_origin)[2]); | ||
284 | |||
285 | for (i = 0; i < 3; i++) { | ||
286 | /* Lower positive boundary */ | ||
287 | while (end[i] > start[i]) { | ||
288 | /* Adjust ceiling */ | ||
289 | VectorCopy(start, test)((test)[0]=(start)[0],(test)[1]=(start)[1],(test)[2]=(start)[ 2]); | ||
290 | test[i] = end[i]; /* the box from test to end is now one cell high */ | ||
291 | /* Prep boundary box */ | ||
292 | PosToVec(test, box.mins)( (box.mins)[0] = ((int)(test)[0] - (4096 / 32)) * 32 + 32 / 2 , (box.mins)[1] = ((int)(test)[1] - (4096 / 32)) * 32 + 32 / 2 , (box.mins)[2] = (int)(test)[2] * 64 + 64 / 2 ); | ||
293 | VectorSubtract(box.mins, normal, box.mins)((box.mins)[0]=(box.mins)[0]-(normal)[0],(box.mins)[1]=(box.mins )[1]-(normal)[1],(box.mins)[2]=(box.mins)[2]-(normal)[2]); | ||
294 | PosToVec(end, box.maxs)( (box.maxs)[0] = ((int)(end)[0] - (4096 / 32)) * 32 + 32 / 2 , (box.maxs)[1] = ((int)(end)[1] - (4096 / 32)) * 32 + 32 / 2 , (box.maxs)[2] = (int)(end)[2] * 64 + 64 / 2 ); | ||
295 | VectorAdd(box.maxs, normal, box.maxs)((box.maxs)[0]=(box.maxs)[0]+(normal)[0],(box.maxs)[1]=(box.maxs )[1]+(normal)[1],(box.maxs)[2]=(box.maxs)[2]+(normal)[2]); | ||
296 | /* Test for stuff in a small box, if there is something then exit while */ | ||
297 | trace = RT_COMPLETEBOXTRACE_SIZE(mapTiles, origin, origin, &box, NULL)CM_EntCompleteBoxTrace((mapTiles), (origin),(origin),(&box ),0x1FF, (-1), 0, (__null)); | ||
298 | if (trace.fraction < 1.0) | ||
299 | break; | ||
300 | /* There is nothing, lower the boundary. */ | ||
301 | end[i]--; | ||
302 | } | ||
303 | |||
304 | /* Raise negative boundary */ | ||
305 | while (end[i] > start[i]) { | ||
306 | /* Adjust ceiling */ | ||
307 | VectorCopy(end, test)((test)[0]=(end)[0],(test)[1]=(end)[1],(test)[2]=(end)[2]); | ||
308 | test[i] = start[i]; /* the box from start to test is now one cell high */ | ||
309 | /* Prep boundary box */ | ||
310 | PosToVec(start, box.mins)( (box.mins)[0] = ((int)(start)[0] - (4096 / 32)) * 32 + 32 / 2, (box.mins)[1] = ((int)(start)[1] - (4096 / 32)) * 32 + 32 / 2, (box.mins)[2] = (int)(start)[2] * 64 + 64 / 2 ); | ||
311 | VectorSubtract(box.mins, normal, box.mins)((box.mins)[0]=(box.mins)[0]-(normal)[0],(box.mins)[1]=(box.mins )[1]-(normal)[1],(box.mins)[2]=(box.mins)[2]-(normal)[2]); | ||
312 | PosToVec(test, box.maxs)( (box.maxs)[0] = ((int)(test)[0] - (4096 / 32)) * 32 + 32 / 2 , (box.maxs)[1] = ((int)(test)[1] - (4096 / 32)) * 32 + 32 / 2 , (box.maxs)[2] = (int)(test)[2] * 64 + 64 / 2 ); | ||
313 | VectorAdd(box.maxs, normal, box.maxs)((box.maxs)[0]=(box.maxs)[0]+(normal)[0],(box.maxs)[1]=(box.maxs )[1]+(normal)[1],(box.maxs)[2]=(box.maxs)[2]+(normal)[2]); | ||
314 | /* Test for stuff in a small box, if there is something then exit while */ | ||
315 | trace = RT_COMPLETEBOXTRACE_SIZE(mapTiles, origin, origin, &box, NULL)CM_EntCompleteBoxTrace((mapTiles), (origin),(origin),(&box ),0x1FF, (-1), 0, (__null)); | ||
316 | if (trace.fraction < 1.0) | ||
317 | break; | ||
318 | /* There is nothing, raise the boundary. */ | ||
319 | start[i]++; | ||
320 | } | ||
321 | } | ||
322 | |||
323 | /* Com_Printf("Extents: (%i, %i, %i) to (%i, %i, %i)\n", start[0], start[1], start[2], end[0], end[1], end[2]); */ | ||
324 | |||
325 | /* convert to vectors */ | ||
326 | PosToVec(start, map_min)( (map_min)[0] = ((int)(start)[0] - (4096 / 32)) * 32 + 32 / 2 , (map_min)[1] = ((int)(start)[1] - (4096 / 32)) * 32 + 32 / 2 , (map_min)[2] = (int)(start)[2] * 64 + 64 / 2 ); | ||
327 | PosToVec(end, map_max)( (map_max)[0] = ((int)(end)[0] - (4096 / 32)) * 32 + 32 / 2, (map_max)[1] = ((int)(end)[1] - (4096 / 32)) * 32 + 32 / 2, ( map_max)[2] = (int)(end)[2] * 64 + 64 / 2 ); | ||
328 | |||
329 | /* Stretch to the exterior edges of our extents */ | ||
330 | VectorSubtract(map_min, normal, map_min)((map_min)[0]=(map_min)[0]-(normal)[0],(map_min)[1]=(map_min) [1]-(normal)[1],(map_min)[2]=(map_min)[2]-(normal)[2]); | ||
331 | VectorAdd(map_max, normal, map_max)((map_max)[0]=(map_max)[0]+(normal)[0],(map_max)[1]=(map_max) [1]+(normal)[1],(map_max)[2]=(map_max)[2]+(normal)[2]); | ||
332 | } | ||
333 | |||
334 | |||
335 | /* | ||
336 | =============================================================================== | ||
337 | NEW MAP TRACING FUNCTIONS | ||
338 | =============================================================================== | ||
339 | */ | ||
340 | |||
341 | /** | ||
342 | * @brief Check if pos is on solid ground | ||
343 | * @param[in] map The map's routing data | ||
344 | * @param[in] actorSize The size of the actor along the X and Y axis in cell units | ||
345 | * @param[in] pos The position to check below | ||
346 | * @return true if solid | ||
347 | * @sa CL_AddTargetingBox | ||
348 | * @todo see CL_ActorMoveMouse | ||
349 | */ | ||
350 | bool RT_AllCellsBelowAreFilled (const routing_t * map, const int actorSize, const pos3_t pos) | ||
351 | { | ||
352 | int i; | ||
353 | |||
354 | /* the -1 level is considered solid ground */ | ||
355 | if (pos[2] == 0) | ||
356 | return true; | ||
357 | |||
358 | for (i = 0; i < pos[2]; i++) { | ||
359 | if (RT_CEILING(map, actorSize, pos[0], pos[1], i)map[(actorSize) - 1].ceil[(i)][(pos[1])][(pos[0])] != 0) | ||
360 | return false; | ||
361 | } | ||
362 | return true; | ||
363 | } | ||
364 | |||
365 | /** | ||
366 | * @brief This function looks to see if an actor of a given size can occupy a cell(s) and if so | ||
367 | * identifies the floor and ceiling for that cell. If the cell has no floor, the floor will be negative | ||
368 | * with 0 indicating the base for the cell(s). If there is no ceiling in the cell, the first ceiling | ||
369 | * found above the current cell will be used. If there is no ceiling above the cell, the ceiling will | ||
370 | * be the top of the model. This function will also adjust all floor and ceiling values for all cells | ||
371 | * between the found floor and ceiling. | ||
372 | * @param[in] mapTiles List of tiles the current (RMA-)map is composed of | ||
373 | * @param[in] map The map's routing data | ||
374 | * @param[in] actorSize The size of the actor along the X and Y axis in cell units | ||
375 | * @param[in] x The x position in the routing arrays (0 - PATHFINDING_WIDTH-1) | ||
376 | * @param[in] y The y position in the routing arrays (0 - PATHFINDING_WIDTH-1) | ||
377 | * @param[in] z The z position in the routing arrays (0 - PATHFINDING_HEIGHT-1) | ||
378 | * @param[in] list The local models list (a local model has a name starting with * followed by the model number) | ||
379 | * @return The z value of the next cell to scan, usually the cell with the ceiling. | ||
380 | * @sa Grid_RecalcRouting | ||
381 | */ | ||
382 | int RT_CheckCell (mapTiles_t *mapTiles, routing_t * map, const int actorSize, const int x, const int y, const int z, const char **list) | ||
383 | { | ||
384 | /* Width of the box required to stand in a cell by an actor's torso. */ | ||
385 | const float halfActorWidth = UNIT_SIZE32 * actorSize / 2 - WALL_SIZE5 - DIST_EPSILON(0.03125); | ||
386 | /* This is a template for the extents of the box used by an actor's legs. */ | ||
387 | const box_t legBox = {{-halfMicrostepSize(4 / 2 - (0.03125)), -halfMicrostepSize(4 / 2 - (0.03125)), 0}, | ||
388 | { halfMicrostepSize(4 / 2 - (0.03125)), halfMicrostepSize(4 / 2 - (0.03125)), QuantToModel(PATHFINDING_LEGROOMHEIGHT)((4) * 4) - DIST_EPSILON(0.03125) * 2}}; | ||
389 | /* This is a template for the extents of the box used by an actor's torso. */ | ||
390 | const box_t torsoBox = {{-halfActorWidth, -halfActorWidth, QuantToModel(PATHFINDING_LEGROOMHEIGHT)((4) * 4)}, | ||
391 | { halfActorWidth, halfActorWidth, QuantToModel(PATHFINDING_MIN_OPENING)((6) * 4) - DIST_EPSILON(0.03125) * 2}}; | ||
392 | /* This is a template for the ceiling trace after an actor's torso space has been found. */ | ||
393 | const box_t ceilBox = {{-halfActorWidth, -halfActorWidth, 0}, | ||
394 | { halfActorWidth, halfActorWidth, 0}}; | ||
395 | |||
396 | vec3_t start, end; /* Start and end of the downward traces. */ | ||
397 | vec3_t tstart, tend; /* Start and end of the upward traces. */ | ||
398 | box_t box; /* Holds the exact bounds to be traced for legs and torso. */ | ||
399 | pos3_t pos; | ||
400 | float bottom, top; /* Floor and ceiling model distances from the cell base. (in mapunits) */ | ||
401 | #ifdef DEBUG1 | ||
402 | float initial; /* Cell floor and ceiling z coordinate. */ | ||
403 | #endif | ||
404 | int bottomQ, topQ; /* The floor and ceiling in QUANTs */ | ||
405 | int i; | ||
406 | int fz, cz; /* Floor and ceiling Z cell coordinates */ | ||
407 | trace_t tr; | ||
408 | |||
409 | assert(actorSize > ACTOR_SIZE_INVALID && actorSize <= ACTOR_MAX_SIZE)(__builtin_expect(!(actorSize > 0 && actorSize <= (2)), 0) ? __assert_rtn(__func__, "src/common/routing.cpp", 409 , "actorSize > ACTOR_SIZE_INVALID && actorSize <= ACTOR_MAX_SIZE" ) : (void)0); | ||
410 | assert(map)(__builtin_expect(!(map), 0) ? __assert_rtn(__func__, "src/common/routing.cpp" , 410, "map") : (void)0); | ||
411 | /* x and y cannot exceed PATHFINDING_WIDTH - actorSize */ | ||
412 | assert((x >= 0) && (x <= PATHFINDING_WIDTH - actorSize))(__builtin_expect(!((x >= 0) && (x <= ((4096 / 32 ) * 2) - actorSize)), 0) ? __assert_rtn(__func__, "src/common/routing.cpp" , 412, "(x >= 0) && (x <= PATHFINDING_WIDTH - actorSize)" ) : (void)0); | ||
413 | assert((y >= 0) && (y <= PATHFINDING_WIDTH - actorSize))(__builtin_expect(!((y >= 0) && (y <= ((4096 / 32 ) * 2) - actorSize)), 0) ? __assert_rtn(__func__, "src/common/routing.cpp" , 413, "(y >= 0) && (y <= PATHFINDING_WIDTH - actorSize)" ) : (void)0); | ||
414 | assert(z < PATHFINDING_HEIGHT)(__builtin_expect(!(z < 8), 0) ? __assert_rtn(__func__, "src/common/routing.cpp" , 414, "z < PATHFINDING_HEIGHT") : (void)0); | ||
415 | |||
416 | /* calculate tracing coordinates */ | ||
417 | VectorSet(pos, x, y, z)((pos)[0]=(x), (pos)[1]=(y), (pos)[2]=(z)); | ||
418 | SizedPosToVec(pos, actorSize, end){ (__builtin_expect(!(actorSize > 0), 0) ? __assert_rtn(__func__ , "src/common/routing.cpp", 418, "actorSize > ACTOR_SIZE_INVALID" ) : (void)0); (__builtin_expect(!(actorSize <= (2)), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 418, "actorSize <= ACTOR_MAX_SIZE" ) : (void)0); end[0] = ((int)pos[0] - 128) * 32 + (32 * actorSize ) / 2; end[1] = ((int)pos[1] - 128) * 32 + (32 * actorSize) / 2; end[2] = (int)pos[2] * 64 + 64 / 2; }; /* end is now at the center of the cells the actor occupies. */ | ||
419 | |||
420 | /* prepare fall down check */ | ||
421 | VectorCopy(end, start)((start)[0]=(end)[0],(start)[1]=(end)[1],(start)[2]=(end)[2]); | ||
422 | /* | ||
423 | * Adjust these points so that start to end is from the top of the cell to the bottom of the model. | ||
424 | */ | ||
425 | #ifdef DEBUG1 | ||
426 | initial = start[2] + UNIT_HEIGHT64 / 2; /* This is the top-most starting point in this cell. */ | ||
427 | #endif | ||
428 | start[2] += UNIT_HEIGHT64 / 2 - QUANT4; /* This one QUANT unit below initial. */ | ||
429 | end[2] = -UNIT_HEIGHT64 * 2; /* To the bottom of the model! (Plus some for good measure) */ | ||
430 | |||
431 | /* | ||
432 | * Trace for a floor. Steps: | ||
433 | * 1. Start at the top of the designated cell and scan toward the model's base. | ||
434 | * 2. If we do not find a brush, then this cell is bottomless and not enterable. | ||
435 | * 3. We have found an upward facing brush. Scan up PATHFINDING_LEGROOMHEIGHT height. | ||
436 | * 4. If we find anything, then this space is too small of an opening. Restart just below our current floor. | ||
437 | * 5. Trace up towards the model ceiling with a box as large as the actor. The first obstruction encountered | ||
438 | * marks the ceiling. If there are no obstructions, the model ceiling is the ceiling. | ||
439 | * 6. If the opening between the floor and the ceiling is not at least PATHFINDING_MIN_OPENING tall, then | ||
440 | * restart below the current floor. | ||
441 | */ | ||
442 | while (true) { /* Loop forever, we will exit if we hit the model bottom or find a valid floor. */ | ||
443 | if (debugTrace) | ||
444 | Com_Printf("[(%i, %i, %i, %i)]Casting floor (%f, %f, %f) to (%f, %f, %f)\n", | ||
445 | x, y, z, actorSize, start[0], start[1], start[2], end[0], end[1], end[2]); | ||
446 | |||
447 | tr = RT_COMPLETEBOXTRACE_PASSAGE(mapTiles, start, end, &footBox, list)CM_EntCompleteBoxTrace((mapTiles), (start),(end),(&footBox ),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000 | 0x0020 ), (list)); | ||
448 | if (tr.fraction >= 1.0) { | ||
449 | /* There is no brush underneath this starting point. */ | ||
450 | if (debugTrace) | ||
451 | Com_Printf("Reached bottom of map. No floor in cell(s). %f\n", tr.endpos[2]); | ||
452 | /* Mark all cells to the model base as filled. */ | ||
453 | for (i = z; i >= 0 ; i--) { | ||
454 | /* no floor in this cell, it is bottomless! */ | ||
455 | RT_FLOOR(map, actorSize, x, y, i)map[(actorSize) - 1].floor[(i)][(y)][(x)] = -1 - i * CELL_HEIGHT(64 / 4); /* There is no floor in this cell, place it at -1 below the model. */ | ||
456 | RT_CEILING(map, actorSize, x, y, i)map[(actorSize) - 1].ceil[(i)][(y)][(x)] = 0; /* There is no ceiling, the true indicator of a filled cell. */ | ||
457 | } | ||
458 | /* return 0 to indicate we just scanned the model bottom. */ | ||
459 | return 0; | ||
460 | } | ||
461 | |||
462 | /* We have hit a brush that faces up and can be stood on. Look for a ceiling. */ | ||
463 | bottom = tr.endpos[2]; /* record the floor position. */ | ||
464 | |||
465 | #ifdef DEBUG1 | ||
466 | assert(initial > bottom)(__builtin_expect(!(initial > bottom), 0) ? __assert_rtn(__func__ , "src/common/routing.cpp", 466, "initial > bottom") : (void )0); | ||
467 | #endif | ||
468 | |||
469 | if (debugTrace) | ||
470 | Com_Printf("Potential floor found at %f.\n", bottom); | ||
471 | |||
472 | /* Record the hit position in tstart for later use. */ | ||
473 | VectorCopy(tr.endpos, tstart)((tstart)[0]=(tr.endpos)[0],(tstart)[1]=(tr.endpos)[1],(tstart )[2]=(tr.endpos)[2]); | ||
474 | |||
475 | /* Prep the start and end of the "leg room" test. */ | ||
476 | VectorAdd(tstart, legBox.mins, box.mins)((box.mins)[0]=(tstart)[0]+(legBox.mins)[0],(box.mins)[1]=(tstart )[1]+(legBox.mins)[1],(box.mins)[2]=(tstart)[2]+(legBox.mins) [2]); /* Now bmins has the lower required foot space extent */ | ||
477 | VectorAdd(tstart, legBox.maxs, box.maxs)((box.maxs)[0]=(tstart)[0]+(legBox.maxs)[0],(box.maxs)[1]=(tstart )[1]+(legBox.maxs)[1],(box.maxs)[2]=(tstart)[2]+(legBox.maxs) [2]); /* Now bmaxs has the upper required foot space extent */ | ||
478 | |||
479 | if (debugTrace) | ||
480 | Com_Printf(" Casting leg room (%f, %f, %f) to (%f, %f, %f)\n", | ||
481 | box.mins[0], box.mins[1], box.mins[2], box.maxs[0], box.maxs[1], box.maxs[2]); | ||
482 | tr = RT_COMPLETEBOXTRACE_PASSAGE(mapTiles, vec3_origin, vec3_origin, &box, list)CM_EntCompleteBoxTrace((mapTiles), (vec3_origin),(vec3_origin ),(&box),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000 | 0x0020), (list)); | ||
483 | if (tr.fraction < 1.0) { | ||
484 | if (debugTrace) | ||
485 | Com_Printf("Cannot use found surface- leg obstruction found.\n"); | ||
486 | /* | ||
487 | * There is a premature obstruction. We can't use this as a floor. | ||
488 | * Check under start. We need to have at least the minimum amount of clearance from our ceiling, | ||
489 | * So start at that point. | ||
490 | */ | ||
491 | start[2] = bottom - QuantToModel(PATHFINDING_MIN_OPENING)((6) * 4); | ||
492 | /* Check in case we are trying to scan too close to the bottom of the model. */ | ||
493 | if (start[2] <= QuantToModel(PATHFINDING_MIN_OPENING)((6) * 4)) { | ||
494 | /* There is no brush underneath this starting point. */ | ||
495 | if (debugTrace) | ||
496 | Com_Printf("Reached bottom of map. No floor in cell(s).\n"); | ||
497 | /* Mark all cells to the model base as filled. */ | ||
498 | for (i = z; i >= 0 ; i--) { | ||
499 | /* no floor in this cell, it is bottomless! */ | ||
500 | RT_FLOOR(map, actorSize, x, y, i)map[(actorSize) - 1].floor[(i)][(y)][(x)] = CELL_HEIGHT(64 / 4); /* There is no floor in this cell. */ | ||
501 | RT_CEILING(map, actorSize, x, y, i)map[(actorSize) - 1].ceil[(i)][(y)][(x)] = 0; /* There is no ceiling, the true indicator of a filled cell. */ | ||
502 | } | ||
503 | /* return 0 to indicate we just scanned the model bottom. */ | ||
504 | return 0; | ||
505 | } | ||
506 | /* Restart */ | ||
507 | continue; | ||
508 | } | ||
509 | |||
510 | /* Prep the start and end of the "torso room" test. */ | ||
511 | VectorAdd(tstart, torsoBox.mins, box.mins)((box.mins)[0]=(tstart)[0]+(torsoBox.mins)[0],(box.mins)[1]=( tstart)[1]+(torsoBox.mins)[1],(box.mins)[2]=(tstart)[2]+(torsoBox .mins)[2]); /* Now bmins has the lower required torso space extent */ | ||
512 | VectorAdd(tstart, torsoBox.maxs, box.maxs)((box.maxs)[0]=(tstart)[0]+(torsoBox.maxs)[0],(box.maxs)[1]=( tstart)[1]+(torsoBox.maxs)[1],(box.maxs)[2]=(tstart)[2]+(torsoBox .maxs)[2]); /* Now bmaxs has the upper required torso space extent */ | ||
513 | |||
514 | if (debugTrace) | ||
515 | Com_Printf(" Casting torso room (%f, %f, %f) to (%f, %f, %f)\n", | ||
516 | box.mins[0], box.mins[1], box.mins[2], box.maxs[0], box.maxs[1], box.maxs[2]); | ||
517 | tr = RT_COMPLETEBOXTRACE_PASSAGE(mapTiles, vec3_origin, vec3_origin, &box, list)CM_EntCompleteBoxTrace((mapTiles), (vec3_origin),(vec3_origin ),(&box),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000 | 0x0020), (list)); | ||
518 | if (tr.fraction < 1.0) { | ||
519 | if (debugTrace) | ||
520 | Com_Printf("Cannot use found surface- torso obstruction found.\n"); | ||
521 | /* | ||
522 | * There is a premature obstruction. We can't use this as a floor. | ||
523 | * Check under start. We need to have at least the minimum amount of clearance from our ceiling, | ||
524 | * So start at that point. | ||
525 | */ | ||
526 | start[2] = bottom - QuantToModel(PATHFINDING_MIN_OPENING)((6) * 4); | ||
527 | /* Check in case we are trying to scan too close to the bottom of the model. */ | ||
528 | if (start[2] <= QuantToModel(PATHFINDING_MIN_OPENING)((6) * 4)) { | ||
529 | /* There is no brush underneath this starting point. */ | ||
530 | if (debugTrace) | ||
531 | Com_Printf("Reached bottom of map. No floor in cell(s).\n"); | ||
532 | /* Mark all cells to the model base as filled. */ | ||
533 | for (i = z; i >= 0 ; i--) { | ||
534 | /* no floor in this cell, it is bottomless! */ | ||
535 | RT_FLOOR(map, actorSize, x, y, i)map[(actorSize) - 1].floor[(i)][(y)][(x)] = CELL_HEIGHT(64 / 4); /* There is no floor in this cell. */ | ||
536 | RT_CEILING(map, actorSize, x, y, i)map[(actorSize) - 1].ceil[(i)][(y)][(x)] = 0; /* There is no ceiling, the true indicator of a filled cell. */ | ||
537 | } | ||
538 | /* return 0 to indicate we just scanned the model bottom. */ | ||
539 | return 0; | ||
540 | } | ||
541 | /* Restart */ | ||
542 | continue; | ||
543 | } | ||
544 | |||
545 | /* | ||
546 | * If we are here, then the immediate floor is unobstructed MIN_OPENING units high. | ||
547 | * This is a valid floor. Find the actual ceiling. | ||
548 | */ | ||
549 | |||
550 | tstart[2] = box.maxs[2]; /* The box trace for height starts at the top of the last trace. */ | ||
551 | VectorCopy(tstart, tend)((tend)[0]=(tstart)[0],(tend)[1]=(tstart)[1],(tend)[2]=(tstart )[2]); | ||
552 | tend[2] = PATHFINDING_HEIGHT8 * UNIT_HEIGHT64; /* tend now reaches the model ceiling. */ | ||
553 | |||
554 | if (debugTrace) | ||
555 | Com_Printf(" Casting ceiling (%f, %f, %f) to (%f, %f, %f)\n", | ||
556 | tstart[0], tstart[1], tstart[2], tend[0], tend[1], tend[2]); | ||
557 | |||
558 | tr = RT_COMPLETEBOXTRACE_PASSAGE(mapTiles, tstart, tend, &ceilBox, list)CM_EntCompleteBoxTrace((mapTiles), (tstart),(tend),(&ceilBox ),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000 | 0x0020 ), (list)); | ||
559 | |||
560 | /* We found the ceiling. */ | ||
561 | top = tr.endpos[2]; | ||
562 | |||
563 | /* | ||
564 | * There is one last possibility: | ||
565 | * If our found ceiling is above the cell we started the scan in, then we may have scanned up through another | ||
566 | * floor (one sided brush). If this is the case, we set the ceiling to QUANT below the floor of the above | ||
567 | * ceiling if it is lower than our found ceiling. | ||
568 | */ | ||
569 | if (tr.endpos[2] > (z + 1) * UNIT_HEIGHT64) { | ||
570 | const float topf = (z + 1) * UNIT_HEIGHT64 + QuantToModel(RT_FLOOR(map, actorSize, x, y, z + 1) - 1)((map[(actorSize) - 1].floor[(z + 1)][(y)][(x)] - 1) * 4); | ||
571 | top = std::min(tr.endpos[2], topf); | ||
572 | } | ||
573 | |||
574 | /* We found the ceiling. */ | ||
575 | top = tr.endpos[2]; | ||
576 | |||
577 | /* exit the infinite while loop */ | ||
578 | break; | ||
579 | } | ||
580 | |||
581 | assert(bottom <= top)(__builtin_expect(!(bottom <= top), 0) ? __assert_rtn(__func__ , "src/common/routing.cpp", 581, "bottom <= top") : (void) 0); | ||
582 | |||
583 | /* top and bottom are absolute model heights. Find the actual cell z coordinates for these heights. | ||
584 | * ...but before rounding, give back the DIST_EPSILON that was added by the trace. | ||
585 | * Actually, we have to give back two DIST_EPSILON to prevent rounding issues */ | ||
586 | bottom -= 2 * DIST_EPSILON(0.03125); | ||
587 | top += 2 * DIST_EPSILON(0.03125); | ||
588 | bottomQ = ModelFloorToQuant(bottom)(ceil((bottom) / 4)); /* Convert to QUANT units to ensure the floor is rounded up to the correct value. */ | ||
589 | topQ = ModelCeilingToQuant(top)(floor((top) / 4)); /* Convert to QUANT units to ensure the floor is rounded down to the correct value. */ | ||
590 | fz = floor(bottomQ / CELL_HEIGHT(64 / 4)); /* Ensure we round down to get the bottom-most affected cell */ | ||
591 | /** @note Remember that ceiling values of 1-16 belong to a cell. We need to adjust topQ by 1 to round to the correct z value. */ | ||
592 | cz = std::min(z, (int)(floor((topQ - 1) / CELL_HEIGHT(64 / 4)))); /* Use the lower of z or the calculated ceiling */ | ||
593 | |||
594 | assert(fz <= cz)(__builtin_expect(!(fz <= cz), 0) ? __assert_rtn(__func__, "src/common/routing.cpp", 594, "fz <= cz") : (void)0); | ||
595 | |||
596 | if (debugTrace) | ||
597 | Com_Printf("Valid ceiling found, bottom=%f, top=%f, fz=%i, cz=%i.\n", bottom, top, fz, cz); | ||
598 | |||
599 | /* Last, update the floors and ceilings of cells from (x, y, fz) to (x, y, cz) */ | ||
600 | for (i = fz; i <= cz; i++) { | ||
601 | /* Round up floor to keep feet out of model. */ | ||
602 | RT_FLOOR(map, actorSize, x, y, i)map[(actorSize) - 1].floor[(i)][(y)][(x)] = bottomQ - i * CELL_HEIGHT(64 / 4); | ||
603 | /* Round down ceiling to heep head out of model. Also offset by floor and max at 255. */ | ||
604 | RT_CEILING(map, actorSize, x, y, i)map[(actorSize) - 1].ceil[(i)][(y)][(x)] = topQ - i * CELL_HEIGHT(64 / 4); | ||
605 | if (debugTrace) { | ||
606 | Com_Printf("floor(%i, %i, %i, %i)=%i.\n", x, y, i, actorSize, RT_FLOOR(map, actorSize, x, y, i)map[(actorSize) - 1].floor[(i)][(y)][(x)]); | ||
607 | Com_Printf("ceil(%i, %i, %i, %i)=%i.\n", x, y, i, actorSize, RT_CEILING(map, actorSize, x, y, i)map[(actorSize) - 1].ceil[(i)][(y)][(x)]); | ||
608 | } | ||
609 | } | ||
610 | |||
611 | /* Also, update the floors of any filled cells immediately above the ceiling up to our original cell. */ | ||
612 | for (i = cz + 1; i <= z; i++) { | ||
613 | RT_FLOOR(map, actorSize, x, y, i)map[(actorSize) - 1].floor[(i)][(y)][(x)] = CELL_HEIGHT(64 / 4); /* There is no floor in this cell. */ | ||
614 | RT_CEILING(map, actorSize, x, y, i)map[(actorSize) - 1].ceil[(i)][(y)][(x)] = 0; /* There is no ceiling, the true indicator of a filled cell. */ | ||
615 | if (debugTrace) { | ||
616 | Com_Printf("floor(%i, %i, %i)=%i.\n", x, y, i, RT_FLOOR(map, actorSize, x, y, i)map[(actorSize) - 1].floor[(i)][(y)][(x)]); | ||
617 | Com_Printf("ceil(%i, %i, %i)=%i.\n", x, y, i, RT_CEILING(map, actorSize, x, y, i)map[(actorSize) - 1].ceil[(i)][(y)][(x)]); | ||
618 | } | ||
619 | } | ||
620 | |||
621 | /* Return the lowest z coordinate that we updated floors for. */ | ||
622 | return fz; | ||
623 | } | ||
624 | |||
625 | |||
626 | /** | ||
627 | * @brief Performs traces to find a passage between two points given an upper and lower bound. | ||
628 | * @param[in] rtd The essential routing data with map, actorsize, ents | ||
629 | * @param[in] dir Direction of movement | ||
630 | * @param[in] x Starting x coordinate | ||
631 | * @param[in] y Starting y coordinate | ||
632 | * @param[in] z Starting z coordinate | ||
633 | * @param[in] openingSize Absolute height in QUANT units of the opening. | ||
634 | * @param[in] openingBase Absolute height in QUANT units of the bottom of the opening. | ||
635 | * @param[in] stepup Required stepup to travel in this direction. | ||
636 | */ | ||
637 | static int RT_FillPassageData (RT_data_t *rtd, const int dir, const int x, const int y, const int z, const int openingSize, const int openingBase, const int stepup) | ||
638 | { | ||
639 | const int openingTop = openingBase + openingSize; | ||
640 | int fz, cz; /**< Floor and ceiling Z cell coordinates */ | ||
641 | int i; | ||
642 | |||
643 | /* Final interpretation: | ||
644 | * We now have the floor and the ceiling of the passage traveled between the two cells. | ||
645 | * This span may cover many cells vertically. We can use this to our advantage: | ||
646 | * +Like in the floor tracing, we can assign the direction value for multiple cells and | ||
647 | * skip some scans. | ||
648 | * +The value of each current cell will list the max allowed height of an actor in the passageway, | ||
649 | * which also can be used to see if an actor can fly upward. | ||
650 | * +The allowed height will be based off the floor in the cell or the bottom of the cell; we do not | ||
651 | * want super tall characters to fly through ceilings. | ||
652 | * +To see if an actor can fly down, we check the cells on level down to see if the diagonal movement | ||
653 | * can be made and that both have ceilings above the current level. | ||
654 | */ | ||
655 | |||
656 | fz = z; | ||
657 | cz = ceil((float)openingTop / CELL_HEIGHT(64 / 4)) - 1; | ||
658 | cz = std::min(PATHFINDING_HEIGHT8 - 1, cz); | ||
659 | |||
660 | /* last chance- if cz < z, then bail (and there is an error with the ceiling data somewhere */ | ||
661 | if (cz < z) { | ||
662 | /* We can't go this way. */ | ||
663 | RT_ConnSetNoGo(rtd, x, y, z, dir); | ||
664 | if (debugTrace) | ||
665 | Com_Printf("Passage found but below current cell, opening_base=%i, opening_top=%i, z = %i, cz = %i.\n", openingBase, openingTop, z, cz); | ||
666 | return z; | ||
667 | } | ||
668 | |||
669 | if (debugTrace) | ||
670 | Com_Printf("Passage found, opening_base=%i, opening_size=%i, opening_top=%i, stepup=%i. (%i to %i)\n", openingBase, openingSize, openingTop, stepup, fz, cz); | ||
671 | |||
672 | assert(fz <= z && z <= cz)(__builtin_expect(!(fz <= z && z <= cz), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 672, "fz <= z && z <= cz" ) : (void)0); | ||
673 | |||
674 | /* Last, update the routes of cells from (x, y, fz) to (x, y, cz) for direction dir */ | ||
675 | for (i = fz; i <= cz; i++) { | ||
676 | int oh; | ||
677 | RT_CONN_TEST(rtd->map, rtd->actorSize, x, y, i, dir)(__builtin_expect(!((rtd->actorSize) > 0), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 677, "(rtd->actorSize) > ACTOR_SIZE_INVALID" ) : (void)0); (__builtin_expect(!((rtd->actorSize) <= ( 2)), 0) ? __assert_rtn(__func__, "src/common/routing.cpp", 677 , "(rtd->actorSize) <= ACTOR_MAX_SIZE") : (void)0); (__builtin_expect (!((i) >= 0), 0) ? __assert_rtn(__func__, "src/common/routing.cpp" , 677, "(i) >= 0") : (void)0); (__builtin_expect(!((i) < 8), 0) ? __assert_rtn(__func__, "src/common/routing.cpp", 677 , "(i) < PATHFINDING_HEIGHT") : (void)0); (__builtin_expect (!((y) >= 0), 0) ? __assert_rtn(__func__, "src/common/routing.cpp" , 677, "(y) >= 0") : (void)0); (__builtin_expect(!((y) < ((4096 / 32) * 2)), 0) ? __assert_rtn(__func__, "src/common/routing.cpp" , 677, "(y) < PATHFINDING_WIDTH") : (void)0); (__builtin_expect (!((x) >= 0), 0) ? __assert_rtn(__func__, "src/common/routing.cpp" , 677, "(x) >= 0") : (void)0); (__builtin_expect(!((x) < ((4096 / 32) * 2)), 0) ? __assert_rtn(__func__, "src/common/routing.cpp" , 677, "(x) < PATHFINDING_WIDTH") : (void)0); (__builtin_expect (!((dir) >= 0), 0) ? __assert_rtn(__func__, "src/common/routing.cpp" , 677, "(dir) >= 0") : (void)0); (__builtin_expect(!((dir) < 8), 0) ? __assert_rtn(__func__, "src/common/routing.cpp" , 677, "(dir) < CORE_DIRECTIONS") : (void)0);; | ||
678 | /* Offset from the floor or the bottom of the current cell, whichever is higher. */ | ||
679 | oh = openingTop - std::max(openingBase, i * CELL_HEIGHT(64 / 4)); | ||
680 | /* Only if > 0 */ | ||
681 | assert (oh >= 0)(__builtin_expect(!(oh >= 0), 0) ? __assert_rtn(__func__, "src/common/routing.cpp" , 681, "oh >= 0") : (void)0); | ||
682 | RT_ConnSet(rtd, x, y, i, dir, oh); | ||
683 | /* The stepup is 0 for all cells that are not at the floor. */ | ||
684 | RT_StepupSet(rtd, x, y, i, dir, 0); | ||
685 | if (debugTrace) { | ||
686 | Com_Printf("RT_CONN for (%i, %i, %i) as:%i dir:%i = %i\n", x, y, i, rtd->actorSize, dir, RT_CONN(rtd->map, rtd->actorSize, x, y, i, dir)rtd->map[(rtd->actorSize) - 1].route[(i)][(y)][(x)][(dir )]); | ||
687 | } | ||
688 | } | ||
689 | |||
690 | RT_StepupSet(rtd, x, y, z, dir, stepup); | ||
691 | if (debugTrace) { | ||
692 | Com_Printf("Final RT_STEPUP for (%i, %i, %i) as:%i dir:%i = %i\n", x, y, z, rtd->actorSize, dir, stepup); | ||
693 | } | ||
694 | |||
695 | /* | ||
696 | * Return the highest z coordinate scanned- cz if fz==cz, z==cz, or the floor in cz is negative. | ||
697 | * Otherwise cz - 1 to recheck cz in case there is a floor in cz with its own ceiling. | ||
698 | */ | ||
699 | if (fz == cz || z == cz || RT_FLOOR(rtd->map, rtd->actorSize, x, y, cz)rtd->map[(rtd->actorSize) - 1].floor[(cz)][(y)][(x)] < 0) | ||
700 | return cz; | ||
701 | return cz - 1; | ||
702 | } | ||
703 | |||
704 | /** | ||
705 | * @brief Helper function to trace for walls | ||
706 | * @param[in] rtd The essential routing data with map, actorsize, ents | ||
707 | * @param[in] start The starting point of the trace, at the FLOOR'S CENTER. | ||
708 | * @param[in] end The end point of the trace, centered x and y at the destination but at the same height as start. | ||
709 | * @param[in] hi The upper height ABOVE THE FLOOR of the bounding box. | ||
710 | * @param[in] lo The lower height ABOVE THE FLOOR of the bounding box. | ||
711 | */ | ||
712 | static trace_t RT_ObstructedTrace (RT_data_t *rtd, const vec3_t start, const vec3_t end, int hi, int lo) | ||
713 | { | ||
714 | box_t box; /**< Tracing box extents */ | ||
715 | const float halfActorWidth = UNIT_SIZE32 * rtd->actorSize / 2 - WALL_SIZE5 - DIST_EPSILON(0.03125); | ||
716 | |||
717 | /* Configure the box trace extents. The box is relative to the original floor. */ | ||
718 | VectorSet(box.maxs, halfActorWidth, halfActorWidth, QuantToModel(hi) - DIST_EPSILON)((box.maxs)[0]=(halfActorWidth), (box.maxs)[1]=(halfActorWidth ), (box.maxs)[2]=(((hi) * 4) - (0.03125))); | ||
719 | VectorSet(box.mins, -halfActorWidth, -halfActorWidth, QuantToModel(lo) + DIST_EPSILON)((box.mins)[0]=(-halfActorWidth), (box.mins)[1]=(-halfActorWidth ), (box.mins)[2]=(((lo) * 4) + (0.03125))); | ||
720 | |||
721 | /* perform the trace, then return true if the trace was obstructed. */ | ||
722 | return RT_COMPLETEBOXTRACE_PASSAGE(rtd->mapTiles, start, end, &box, rtd->list)CM_EntCompleteBoxTrace((rtd->mapTiles), (start),(end),(& box),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000 | 0x0020 ), (rtd->list)); | ||
723 | } | ||
724 | |||
725 | |||
726 | /** | ||
727 | * @brief Performs a trace to find the floor of a passage a fraction of the way from start to end. | ||
728 | * @param[in] rtd The essential routing data with map, actorsize, ents | ||
729 | * @param[in] start The starting coordinate to search for a floor from. | ||
730 | * @param[in] end The starting coordinate to search for a floor from. | ||
731 | * @param[in] frac The fraction of the distance traveled from start to end, using (0.0 to 1.0). | ||
732 | * @param[in] startingHeight The starting height for this upward trace. | ||
733 | * @return The absolute height of the found floor in QUANT units. | ||
734 | */ | ||
735 | static int RT_FindOpeningFloorFrac (RT_data_t *rtd, const vec3_t start, const vec3_t end, const float frac, const int startingHeight) | ||
736 | { | ||
737 | vec3_t mstart, mend; /**< Midpoint line to trace across */ /**< Tracing box extents */ | ||
738 | trace_t tr; | ||
739 | const box_t* box = (rtd->actorSize == ACTOR_SIZE_NORMAL1 ? &actor1x1Box : &actor2x2Box); | ||
740 | |||
741 | /* Position mstart and mend at the fraction point */ | ||
742 | VectorInterpolation(start, end, frac, mstart)((mstart)[0]=(start)[0]+(frac)*((end)[0]-(start)[0]),(mstart) [1]=(start)[1]+(frac)*((end)[1]-(start)[1]),(mstart)[2]=(start )[2]+(frac)*((end)[2]-(start)[2])); | ||
743 | VectorCopy(mstart, mend)((mend)[0]=(mstart)[0],(mend)[1]=(mstart)[1],(mend)[2]=(mstart )[2]); | ||
744 | mstart[2] = QuantToModel(startingHeight)((startingHeight) * 4) + (QUANT4 / 2); /* Set at the starting height, plus a little more to keep us off a potential surface. */ | ||
745 | mend[2] = -QUANT4; /* Set below the model. */ | ||
746 | |||
747 | tr = RT_COMPLETEBOXTRACE_PASSAGE(rtd->mapTiles, mstart, mend, box, rtd->list)CM_EntCompleteBoxTrace((rtd->mapTiles), (mstart),(mend),(box ),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000 | 0x0020 ), (rtd->list)); | ||
748 | |||
749 | if (debugTrace) | ||
750 | Com_Printf("Brush found at %f.\n", tr.endpos[2]); | ||
751 | |||
752 | /* OK, now we have the floor height value in tr.endpos[2]. | ||
753 | * Divide by QUANT and round up. | ||
754 | */ | ||
755 | return ModelFloorToQuant(tr.endpos[2] - DIST_EPSILON)(ceil((tr.endpos[2] - (0.03125)) / 4)); | ||
756 | } | ||
757 | |||
758 | |||
759 | /** | ||
760 | * @brief Performs a trace to find the ceiling of a passage a fraction of the way from start to end. | ||
761 | * @param[in] rtd The essential routing data with map, actorsize, ents | ||
762 | * @param[in] start The starting coordinate to search for a ceiling from. | ||
763 | * @param[in] end The starting coordinate to search for a ceiling from. | ||
764 | * @param[in] frac The fraction of the distance traveled from start to end, using (0.0 to 1.0). | ||
765 | * @param[in] startingHeight The starting height for this upward trace. | ||
766 | * @return The absolute height of the found ceiling in QUANT units. | ||
767 | */ | ||
768 | static int RT_FindOpeningCeilingFrac (RT_data_t *rtd, const vec3_t start, const vec3_t end, const float frac, const int startingHeight) | ||
769 | { | ||
770 | vec3_t mstart, mend; /**< Midpoint line to trace across */ | ||
771 | trace_t tr; | ||
772 | const box_t* box = (rtd->actorSize == ACTOR_SIZE_NORMAL1 ? &actor1x1Box : &actor2x2Box); /**< Tracing box extents */ | ||
773 | |||
774 | /* Position mstart and mend at the midpoint */ | ||
775 | VectorInterpolation(start, end, frac, mstart)((mstart)[0]=(start)[0]+(frac)*((end)[0]-(start)[0]),(mstart) [1]=(start)[1]+(frac)*((end)[1]-(start)[1]),(mstart)[2]=(start )[2]+(frac)*((end)[2]-(start)[2])); | ||
776 | VectorCopy(mstart, mend)((mend)[0]=(mstart)[0],(mend)[1]=(mstart)[1],(mend)[2]=(mstart )[2]); | ||
777 | mstart[2] = QuantToModel(startingHeight)((startingHeight) * 4) - (QUANT4 / 2); /* Set at the starting height, minus a little more to keep us off a potential surface. */ | ||
778 | mend[2] = UNIT_HEIGHT64 * PATHFINDING_HEIGHT8 + QUANT4; /* Set above the model. */ | ||
779 | |||
780 | tr = RT_COMPLETEBOXTRACE_PASSAGE(rtd->mapTiles, mstart, mend, box, rtd->list)CM_EntCompleteBoxTrace((rtd->mapTiles), (mstart),(mend),(box ),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000 | 0x0020 ), (rtd->list)); | ||
781 | |||
782 | if (debugTrace) | ||
783 | Com_Printf("Brush found at %f.\n", tr.endpos[2]); | ||
784 | |||
785 | /* OK, now we have the floor height value in tr.endpos[2]. | ||
786 | * Divide by QUANT and round down. */ | ||
787 | return ModelCeilingToQuant(tr.endpos[2] + DIST_EPSILON)(floor((tr.endpos[2] + (0.03125)) / 4)); | ||
788 | } | ||
789 | |||
790 | |||
791 | /** | ||
792 | * @brief Performs traces to find the approximate floor of a passage. | ||
793 | * @param[in] rtd The essential routing data with map, actorsize, ents | ||
794 | * @param[in] start The starting coordinate to search for a floor from. | ||
795 | * @param[in] end The starting coordinate to search for a floor from. | ||
796 | * @param[in] startingHeight The starting height for this downward trace. | ||
797 | * @param[in] floorLimit The lowest limit of the found floor. | ||
798 | * @return The absolute height of the found floor in QUANT units. | ||
799 | */ | ||
800 | static int RT_FindOpeningFloor (RT_data_t *rtd, const vec3_t start, const vec3_t end, const int startingHeight, const int floorLimit) | ||
801 | { | ||
802 | /* Look for additional space below init_bottom, down to lowest_bottom. */ | ||
803 | int midfloor; | ||
804 | |||
805 | if (start[0] == end[0] || start[1] == end[1]) { | ||
806 | /* For orthogonal dirs, find the height at the midpoint. */ | ||
807 | midfloor = RT_FindOpeningFloorFrac(rtd, start, end, 0.5, startingHeight); | ||
808 | if (debugTrace) | ||
809 | Com_Printf("midfloor:%i.\n", midfloor); | ||
810 | } else { | ||
811 | int midfloor2; | ||
812 | |||
813 | /* If this is diagonal, trace the 1/3 and 2/3 points instead. */ | ||
814 | /* 1/3 point */ | ||
815 | midfloor = RT_FindOpeningFloorFrac(rtd, start, end, 0.33, startingHeight); | ||
816 | if (debugTrace) | ||
817 | Com_Printf("1/3floor:%i.\n", midfloor); | ||
818 | |||
819 | /* 2/3 point */ | ||
820 | midfloor2 = RT_FindOpeningFloorFrac(rtd, start, end, 0.66, startingHeight); | ||
821 | if (debugTrace) | ||
822 | Com_Printf("2/3floor:%i.\n", midfloor2); | ||
823 | midfloor = std::max(midfloor, midfloor2); | ||
824 | } | ||
825 | |||
826 | /* return the highest floor. */ | ||
827 | return std::max(floorLimit, midfloor); | ||
828 | } | ||
829 | |||
830 | |||
831 | /** | ||
832 | * @brief Performs traces to find the approximate ceiling of a passage. | ||
833 | * @param[in] rtd The essential routing data with map, actorsize, ents | ||
834 | * @param[in] start The starting coordinate to search for a ceiling from. | ||
835 | * @param[in] end The starting coordinate to search for a ceiling from. | ||
836 | * @param[in] startingHeight The starting height for this upward trace. | ||
837 | * @param[in] ceilLimit The highest the ceiling may be. | ||
838 | * @return The absolute height of the found ceiling in QUANT units. | ||
839 | */ | ||
840 | static int RT_FindOpeningCeiling (RT_data_t *rtd, const vec3_t start, const vec3_t end, const int startingHeight, const int ceilLimit) | ||
841 | { | ||
842 | int midceil; | ||
843 | |||
844 | if (start[0] == end[0] || start[1] == end[1]) { | ||
845 | /* For orthogonal dirs, find the height at the midpoint. */ | ||
846 | midceil = RT_FindOpeningCeilingFrac(rtd, start, end, 0.5, startingHeight); | ||
847 | if (debugTrace) | ||
848 | Com_Printf("midceil:%i.\n", midceil); | ||
849 | } else { | ||
850 | int midceil2; | ||
851 | |||
852 | /* If this is diagonal, trace the 1/3 and 2/3 points instead. */ | ||
853 | /* 1/3 point */ | ||
854 | midceil = RT_FindOpeningCeilingFrac(rtd, start, end, 0.33, startingHeight); | ||
855 | if (debugTrace) | ||
856 | Com_Printf("1/3ceil:%i.\n", midceil); | ||
857 | |||
858 | /* 2/3 point */ | ||
859 | midceil2 = RT_FindOpeningCeilingFrac(rtd, start, end, 0.66, startingHeight); | ||
860 | if (debugTrace) | ||
861 | Com_Printf("2/3ceil:%i.\n", midceil2); | ||
862 | midceil = std::min(midceil, midceil2); | ||
863 | } | ||
864 | |||
865 | /* return the lowest ceiling. */ | ||
866 | return std::min(ceilLimit, midceil); | ||
867 | } | ||
868 | |||
869 | |||
870 | static int RT_CalcNewZ (RT_data_t *rtd, const int ax, const int ay, const int top, const int hi) | ||
871 | { | ||
872 | int temp_z, adj_lo; | ||
873 | |||
874 | temp_z = floor((hi - 1) / CELL_HEIGHT(64 / 4)); | ||
875 | temp_z = std::min(temp_z, PATHFINDING_HEIGHT8 - 1); | ||
876 | adj_lo = RT_FLOOR(rtd->map, rtd->actorSize, ax, ay, temp_z)rtd->map[(rtd->actorSize) - 1].floor[(temp_z)][(ay)][(ax )] + temp_z * CELL_HEIGHT(64 / 4); | ||
877 | if (adj_lo > hi) { | ||
878 | temp_z--; | ||
879 | adj_lo = RT_FLOOR(rtd->map, rtd->actorSize, ax, ay, temp_z)rtd->map[(rtd->actorSize) - 1].floor[(temp_z)][(ay)][(ax )] + temp_z * CELL_HEIGHT(64 / 4); | ||
880 | } | ||
881 | /** | ||
882 | * @note Return a value only if there is a floor for the adjacent cell. | ||
883 | * Also the found adjacent lo must be at lease MIN_OPENING-MIN_STEPUP below | ||
884 | * the top. | ||
885 | */ | ||
886 | if (adj_lo >= 0 && top - adj_lo >= PATHFINDING_MIN_OPENING6 - PATHFINDING_MIN_STEPUP2) { | ||
887 | if (debugTrace) | ||
888 | Com_Printf("Found floor in destination cell: %i (%i).\n", adj_lo, temp_z); | ||
889 | return floor(adj_lo / CELL_HEIGHT(64 / 4)); | ||
890 | } | ||
891 | if (debugTrace) | ||
892 | Com_Printf("Skipping found floor in destination cell- not enough opening: %i (%i).\n", adj_lo, temp_z); | ||
893 | |||
894 | return RT_NO_OPENING-1; | ||
895 | } | ||
896 | |||
897 | |||
898 | /** | ||
899 | * @brief Performs actual trace to find a passage between two points given an upper and lower bound. | ||
900 | * @param[in] rtd The essential routing data with map, actorsize, ents | ||
901 | * @param[in] start Starting trace coordinate | ||
902 | * @param[in] end Ending trace coordinate | ||
903 | * @param[in] ax Ending x coordinate | ||
904 | * @param[in] ay Ending y coordinate | ||
905 | * @param[in] bottom Actual height of the starting floor. | ||
906 | * @param[in] top Actual height of the starting ceiling. | ||
907 | * @param[in] lo Actual height of the bottom of the slice trace. | ||
908 | * @param[in] hi Actual height of the top of the slice trace. | ||
909 | * @param[out] lo_val Actual height of the bottom of the found passage. | ||
910 | * @param[out] hi_val Actual height of the top of the found passage. | ||
911 | * @return The new z value of the actor after traveling in this direction from the starting location. | ||
912 | */ | ||
913 | static int RT_TraceOpening (RT_data_t *rtd, const vec3_t start, const vec3_t end, const int ax, const int ay, const int bottom, const int top, int lo, int hi, int *lo_val, int *hi_val) | ||
914 | { | ||
915 | trace_t tr = RT_ObstructedTrace(rtd, start, end, hi, lo); | ||
916 | if (tr.fraction >= 1.0) { | ||
917 | lo = RT_FindOpeningFloor(rtd, start, end, lo, bottom); | ||
918 | hi = RT_FindOpeningCeiling(rtd, start, end, hi, top); | ||
919 | if (hi - lo >= PATHFINDING_MIN_OPENING6) { | ||
920 | int temp_z; | ||
921 | if (lo == -1) { | ||
922 | if (debugTrace) | ||
923 | Com_Printf("Bailing- no floor in destination cell.\n"); | ||
924 | *lo_val = *hi_val = 0; | ||
925 | return RT_NO_OPENING-1; | ||
926 | } | ||
927 | /* This opening works, use it! */ | ||
928 | *lo_val = lo; | ||
929 | *hi_val = hi; | ||
930 | /* Find the floor for the highest adjacent cell in this passage. */ | ||
931 | temp_z = RT_CalcNewZ(rtd, ax, ay, top, hi); | ||
932 | if (temp_z != RT_NO_OPENING-1) | ||
933 | return temp_z; | ||
934 | } | ||
935 | } | ||
936 | *lo_val = *hi_val = hi; | ||
937 | return RT_NO_OPENING-1; | ||
938 | } | ||
939 | |||
940 | |||
941 | /** | ||
942 | * @brief Performs traces to find a passage between two points given an upper and lower bound. | ||
943 | * @param[in] rtd The essential routing data with map, actorsize, ents | ||
944 | * @param[in] from Starting place | ||
945 | * @param[in] ax Ending x coordinate | ||
946 | * @param[in] ay Ending y coordinate | ||
947 | * @param[in] bottom Actual height of the starting floor. | ||
948 | * @param[in] top Actual height of the starting ceiling. | ||
949 | * @param[out] lo_val Actual height of the bottom of the found passage. | ||
950 | * @param[out] hi_val Actual height of the top of the found passage. | ||
951 | * @return The new z value of the actor after traveling in this direction from the starting location. | ||
952 | */ | ||
953 | static int RT_FindOpening (RT_data_t *rtd, const place_t* from, const int ax, const int ay, const int bottom, const int top, int *lo_val, int *hi_val) | ||
954 | { | ||
955 | vec3_t start, end; | ||
956 | pos3_t pos; | ||
957 | int temp_z; | ||
958 | |||
959 | const int endfloor = RT_FLOOR(rtd->map, rtd->actorSize, ax, ay, from->cell[2])rtd->map[(rtd->actorSize) - 1].floor[(from->cell[2]) ][(ay)][(ax)] + from->cell[2] * CELL_HEIGHT(64 / 4); | ||
960 | const int hifloor = std::max(endfloor, bottom); | ||
961 | |||
962 | if (debugTrace) | ||
963 | Com_Printf("ef:%i t:%i b:%i\n", endfloor, top, bottom); | ||
964 | |||
965 | if (bottom == -1) { | ||
966 | if (debugTrace) | ||
967 | Com_Printf("Bailing- no floor in current cell.\n"); | ||
968 | *lo_val = *hi_val = 0; | ||
969 | return RT_NO_OPENING-1; | ||
970 | } | ||
971 | |||
972 | /* Initialize the starting vector */ | ||
973 | SizedPosToVec(from->cell, rtd->actorSize, start){ (__builtin_expect(!(rtd->actorSize > 0), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 973, "rtd->actorSize > ACTOR_SIZE_INVALID" ) : (void)0); (__builtin_expect(!(rtd->actorSize <= (2) ), 0) ? __assert_rtn(__func__, "src/common/routing.cpp", 973, "rtd->actorSize <= ACTOR_MAX_SIZE") : (void)0); start[ 0] = ((int)from->cell[0] - 128) * 32 + (32 * rtd->actorSize ) / 2; start[1] = ((int)from->cell[1] - 128) * 32 + (32 * rtd ->actorSize) / 2; start[2] = (int)from->cell[2] * 64 + 64 / 2; }; | ||
974 | |||
975 | /* Initialize the ending vector */ | ||
976 | VectorSet(pos, ax, ay, from->cell[2])((pos)[0]=(ax), (pos)[1]=(ay), (pos)[2]=(from->cell[2])); | ||
977 | SizedPosToVec(pos, rtd->actorSize, end){ (__builtin_expect(!(rtd->actorSize > 0), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 977, "rtd->actorSize > ACTOR_SIZE_INVALID" ) : (void)0); (__builtin_expect(!(rtd->actorSize <= (2) ), 0) ? __assert_rtn(__func__, "src/common/routing.cpp", 977, "rtd->actorSize <= ACTOR_MAX_SIZE") : (void)0); end[0] = ((int)pos[0] - 128) * 32 + (32 * rtd->actorSize) / 2; end [1] = ((int)pos[1] - 128) * 32 + (32 * rtd->actorSize) / 2 ; end[2] = (int)pos[2] * 64 + 64 / 2; }; | ||
978 | |||
979 | /* Initialize the z component of both vectors */ | ||
980 | start[2] = end[2] = 0; | ||
981 | |||
982 | /* shortcut: if both ceilings are the sky, we can check for walls | ||
983 | * AND determine the bottom of the passage in just one trace */ | ||
984 | if (from->ceiling >= PATHFINDING_HEIGHT8 * CELL_HEIGHT(64 / 4) | ||
985 | && from->cell[2] * CELL_HEIGHT(64 / 4) + RT_CEILING(rtd->map, rtd->actorSize, ax, ay, from->cell[2])rtd->map[(rtd->actorSize) - 1].ceil[(from->cell[2])] [(ay)][(ax)] >= PATHFINDING_HEIGHT8 * CELL_HEIGHT(64 / 4)) { | ||
986 | vec3_t sky, earth; | ||
987 | const box_t* box = (rtd->actorSize == ACTOR_SIZE_NORMAL1 ? &actor1x1Box : &actor2x2Box); | ||
988 | trace_t tr; | ||
989 | int tempBottom; | ||
990 | |||
991 | if (debugTrace) | ||
992 | Com_Printf("Using sky trace.\n"); | ||
993 | |||
994 | VectorInterpolation(start, end, 0.5, sky)((sky)[0]=(start)[0]+(0.5)*((end)[0]-(start)[0]),(sky)[1]=(start )[1]+(0.5)*((end)[1]-(start)[1]),(sky)[2]=(start)[2]+(0.5)*(( end)[2]-(start)[2])); /* center it halfway between the cells */ | ||
995 | VectorCopy(sky, earth)((earth)[0]=(sky)[0],(earth)[1]=(sky)[1],(earth)[2]=(sky)[2]); | ||
996 | sky[2] = UNIT_HEIGHT64 * PATHFINDING_HEIGHT8; /* Set to top of model. */ | ||
997 | earth[2] = QuantToModel(bottom)((bottom) * 4); | ||
998 | |||
999 | tr = RT_COMPLETEBOXTRACE_PASSAGE(rtd->mapTiles, sky, earth, box, rtd->list)CM_EntCompleteBoxTrace((rtd->mapTiles), (sky),(earth),(box ),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000 | 0x0020 ), (rtd->list)); | ||
1000 | tempBottom = ModelFloorToQuant(tr.endpos[2])(ceil((tr.endpos[2]) / 4)); | ||
1001 | if (tempBottom <= bottom + PATHFINDING_MIN_STEPUP2) { | ||
1002 | const int hi = bottom + PATHFINDING_MIN_OPENING6; | ||
1003 | if (debugTrace) | ||
1004 | Com_Printf("Found opening with sky trace.\n"); | ||
1005 | *lo_val = tempBottom; | ||
1006 | *hi_val = CELL_HEIGHT(64 / 4) * PATHFINDING_HEIGHT8; | ||
1007 | return RT_CalcNewZ(rtd, ax, ay, top, hi); | ||
1008 | } | ||
1009 | if (debugTrace) | ||
1010 | Com_Printf("Failed sky trace.\n"); | ||
1011 | } | ||
1012 | /* Warning: never try to make this an 'else if', or 'arched entry' situations will fail !! */ | ||
1013 | |||
1014 | /* Now calculate the "guaranteed" opening, if any. If the opening from | ||
1015 | * the floor to the ceiling is not too tall, there must be a section that | ||
1016 | * will always be vacant if there is a usable passage of any size and at | ||
1017 | * any height. */ | ||
1018 | if (top - bottom < PATHFINDING_MIN_OPENING6 * 2) { | ||
1019 | const int lo = top - PATHFINDING_MIN_OPENING6; | ||
1020 | const int hi = bottom + PATHFINDING_MIN_OPENING6; | ||
1021 | if (debugTrace) | ||
1022 | Com_Printf("Tracing closed space from %i to %i.\n", bottom, top); | ||
1023 | temp_z = RT_TraceOpening(rtd, start, end, ax, ay, hifloor, top, lo, hi, lo_val, hi_val); | ||
1024 | } else { | ||
1025 | /* There is no "guaranteed" opening, brute force search. */ | ||
1026 | int lo = bottom; | ||
1027 | temp_z = 0; | ||
1028 | while (lo <= top - PATHFINDING_MIN_OPENING6) { | ||
1029 | /* Check for a 1 QUANT opening. */ | ||
1030 | if (debugTrace) | ||
1031 | Com_Printf("Tracing open space from %i.\n", lo); | ||
1032 | temp_z = RT_TraceOpening(rtd, start, end, ax, ay, bottom, top, lo, lo + 1, lo_val, hi_val); | ||
1033 | if (temp_z != RT_NO_OPENING-1) | ||
1034 | break; | ||
1035 | /* Credit to Duke: We skip the minimum opening, as if there is a | ||
1036 | * viable opening, even one slice above, that opening would be open. */ | ||
1037 | lo = *hi_val + PATHFINDING_MIN_OPENING6; | ||
1038 | } | ||
1039 | } | ||
1040 | return temp_z; | ||
1041 | } | ||
1042 | |||
1043 | |||
1044 | /** | ||
1045 | * @brief Performs small traces to find places when an actor can step up. | ||
1046 | * @param[in] rtd The essential routing data with map, actorsize, ents | ||
1047 | * @param[in] from Starting place | ||
1048 | * @param[in] ax Ending x coordinate | ||
1049 | * @param[in] ay Ending y coordinate | ||
1050 | * @param[in] az Ending z coordinate | ||
1051 | * @param[in] stairwaySituation whether we are standing in front of a stairway | ||
1052 | * @param[out] opening descriptor of the opening found, if any | ||
1053 | * @return The change in floor height in QUANT units because of the additional trace. | ||
1054 | */ | ||
1055 | static int RT_MicroTrace (RT_data_t *rtd, const place_t* from, const int ax, const int ay, const int az, const int stairwaySituation, opening_t* opening) | ||
1056 | { | ||
1057 | /* OK, now we have a viable shot across. Run microstep tests now. */ | ||
1058 | /* Now calculate the stepup at the floor using microsteps. */ | ||
1059 | int top = opening->base + opening->size; | ||
1060 | signed char bases[UNIT_SIZE32 / PATHFINDING_MICROSTEP_SIZE4 + 1]; | ||
1061 | float sx, sy, ex, ey; | ||
1062 | /* Shortcut the value of UNIT_SIZE / PATHFINDING_MICROSTEP_SIZE. */ | ||
1063 | const int steps = UNIT_SIZE32 / PATHFINDING_MICROSTEP_SIZE4; | ||
1064 | trace_t tr; | ||
1065 | int i, current_h, highest_h, highest_i = 0, skipped, newBottom; | ||
1066 | vec3_t start, end; | ||
1067 | pos3_t pos; | ||
1068 | int last_step; | ||
1069 | |||
1070 | /* First prepare the two known end values. */ | ||
1071 | bases[0] = from->floor; | ||
1072 | const int floorVal = RT_FLOOR(rtd->map, rtd->actorSize, ax, ay, az)rtd->map[(rtd->actorSize) - 1].floor[(az)][(ay)][(ax)]; | ||
1073 | bases[steps] = last_step = std::max(0, floorVal) + az * CELL_HEIGHT(64 / 4); | ||
1074 | |||
1075 | /* Initialize the starting vector */ | ||
1076 | SizedPosToVec(from->cell, rtd->actorSize, start){ (__builtin_expect(!(rtd->actorSize > 0), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 1076, "rtd->actorSize > ACTOR_SIZE_INVALID" ) : (void)0); (__builtin_expect(!(rtd->actorSize <= (2) ), 0) ? __assert_rtn(__func__, "src/common/routing.cpp", 1076 , "rtd->actorSize <= ACTOR_MAX_SIZE") : (void)0); start [0] = ((int)from->cell[0] - 128) * 32 + (32 * rtd->actorSize ) / 2; start[1] = ((int)from->cell[1] - 128) * 32 + (32 * rtd ->actorSize) / 2; start[2] = (int)from->cell[2] * 64 + 64 / 2; }; | ||
1077 | |||
1078 | /* Initialize the ending vector */ | ||
1079 | VectorSet(pos, ax, ay, az)((pos)[0]=(ax), (pos)[1]=(ay), (pos)[2]=(az)); | ||
1080 | SizedPosToVec(pos, rtd->actorSize, end){ (__builtin_expect(!(rtd->actorSize > 0), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 1080, "rtd->actorSize > ACTOR_SIZE_INVALID" ) : (void)0); (__builtin_expect(!(rtd->actorSize <= (2) ), 0) ? __assert_rtn(__func__, "src/common/routing.cpp", 1080 , "rtd->actorSize <= ACTOR_MAX_SIZE") : (void)0); end[0 ] = ((int)pos[0] - 128) * 32 + (32 * rtd->actorSize) / 2; end [1] = ((int)pos[1] - 128) * 32 + (32 * rtd->actorSize) / 2 ; end[2] = (int)pos[2] * 64 + 64 / 2; }; | ||
1081 | |||
1082 | /* Now prep the z values for start and end. */ | ||
1083 | start[2] = QuantToModel(opening->base)((opening->base) * 4) + 1; /**< Just above the bottom of the found passage */ | ||
1084 | end[2] = -QUANT4; | ||
1085 | |||
1086 | /* Memorize the start and end x,y points */ | ||
1087 | sx = start[0]; | ||
1088 | sy = start[1]; | ||
1089 | ex = end[0]; | ||
1090 | ey = end[1]; | ||
1091 | |||
1092 | newBottom = std::max(bases[0], bases[steps]); | ||
1093 | /* Now calculate the rest of the microheights. */ | ||
1094 | for (i = 1; i < steps; i++) { | ||
1095 | start[0] = end[0] = sx + (ex - sx) * (i / (float)steps); | ||
1096 | start[1] = end[1] = sy + (ey - sy) * (i / (float)steps); | ||
1097 | |||
1098 | /* perform the trace, then return true if the trace was obstructed. */ | ||
1099 | tr = RT_COMPLETEBOXTRACE_PASSAGE(rtd->mapTiles, start, end, &footBox, rtd->list)CM_EntCompleteBoxTrace((rtd->mapTiles), (start),(end),(& footBox),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000 | 0x0020), (rtd->list)); | ||
1100 | if (tr.fraction >= 1.0) { | ||
1101 | bases[i] = -1; | ||
1102 | } else { | ||
1103 | bases[i] = ModelFloorToQuant(tr.endpos[2] - DIST_EPSILON)(ceil((tr.endpos[2] - (0.03125)) / 4)); | ||
1104 | /* Walking through glass fix: | ||
1105 | * It is possible to have an obstruction that can be skirted around diagonally | ||
1106 | * because the microtraces are so tiny. But, we have a full size trace in opening->base | ||
1107 | * that apporoximates where legroom ends. If the found floor of the middle microtrace is | ||
1108 | * too low, then set it to the worst case scenario floor based on base->opening. | ||
1109 | */ | ||
1110 | if (i == floor(steps / 2.0) && bases[i] < opening->base - PATHFINDING_MIN_STEPUP2) { | ||
1111 | if (debugTrace) | ||
1112 | Com_Printf("Adjusting middle trace- the known base is too high. \n"); | ||
1113 | bases[i] = opening->base - PATHFINDING_MIN_STEPUP2; | ||
1114 | } | ||
1115 | } | ||
1116 | |||
1117 | if (debugTrace) | ||
1118 | Com_Printf("Microstep %i from (%f, %f, %f) to (%f, %f, %f) = %i [%f]\n", | ||
1119 | i, start[0], start[1], start[2], end[0], end[1], end[2], bases[i], tr.endpos[2]);\ | ||
1120 | |||
1121 | newBottom = std::max(newBottom, (int)bases[i]); | ||
1122 | } | ||
1123 | |||
1124 | if (debugTrace) | ||
1125 | Com_Printf("z:%i az:%i bottom:%i new_bottom:%i top:%i bases[0]:%i bases[%i]:%i\n", from->cell[2], az, opening->base, newBottom, top, bases[0], steps, bases[steps]); | ||
1126 | |||
1127 | |||
1128 | /** @note This for loop is bi-directional: i may be decremented to retrace prior steps. */ | ||
1129 | /* Now find the maximum stepup moving from (x, y) to (ax, ay). */ | ||
1130 | /* Initialize stepup. */ | ||
1131 | current_h = bases[0]; | ||
1132 | highest_h = -1; | ||
1133 | highest_i = 1; | ||
1134 | opening->stepup = 0; /**< Was originally -CELL_HEIGHT, but stepup is needed to go UP, not down. */ | ||
1135 | skipped = 0; | ||
1136 | for (i = 1; i <= steps; i++) { | ||
1137 | if (debugTrace) | ||
1138 | Com_Printf("Tracing forward i:%i h:%i\n", i, current_h); | ||
1139 | /* If there is a rise, use it. */ | ||
1140 | if (bases[i] >= current_h || ++skipped > PATHFINDING_MICROSTEP_SKIP2) { | ||
1141 | if (skipped == PATHFINDING_MICROSTEP_SKIP2) { | ||
1142 | i = highest_i; | ||
1143 | if (debugTrace) | ||
1144 | Com_Printf(" Skipped too many steps, reverting to i:%i\n", i); | ||
1145 | } | ||
1146 | opening->stepup = std::max(opening->stepup, bases[i] - current_h); | ||
1147 | current_h = bases[i]; | ||
1148 | highest_h = -2; | ||
1149 | highest_i = i + 1; | ||
1150 | skipped = 0; | ||
1151 | if (debugTrace) | ||
1152 | Com_Printf(" Advancing b:%i stepup:%i\n", bases[i], opening->stepup); | ||
1153 | } else { | ||
1154 | /* We are skipping this step in case the actor can step over this lower step. */ | ||
1155 | /* Record the step in case it is the highest of the low steps. */ | ||
1156 | if (bases[i] > highest_h) { | ||
1157 | highest_h = bases[i]; | ||
1158 | highest_i = i; | ||
1159 | } | ||
1160 | if (debugTrace) | ||
1161 | Com_Printf(" Skipped because we are falling, skip:%i.\n", skipped); | ||
1162 | /* If this is the last iteration, make sure we go back and get our last stepup tests. */ | ||
1163 | if (i == steps) { | ||
1164 | skipped = PATHFINDING_MICROSTEP_SKIP2; | ||
1165 | i = highest_i - 1; | ||
1166 | if (debugTrace) | ||
1167 | Com_Printf(" Tripping skip counter to perform last tests.\n"); | ||
1168 | } | ||
1169 | } | ||
1170 | } | ||
1171 | |||
1172 | /** @note This for loop is bi-directional: i may be decremented to retrace prior steps. */ | ||
1173 | /* Now find the maximum stepup moving from (x, y) to (ax, ay). */ | ||
1174 | /* Initialize stepup. */ | ||
1175 | current_h = bases[steps]; | ||
1176 | highest_h = -1; | ||
1177 | highest_i = steps - 1; /**< Note that for this part of the code, this is the LOWEST i. */ | ||
1178 | opening->invstepup = 0; /**< Was originally -CELL_HEIGHT, but stepup is needed to go UP, not down. */ | ||
1179 | skipped = 0; | ||
1180 | for (i = steps - 1; i >= 0; i--) { | ||
1181 | if (debugTrace) | ||
1182 | Com_Printf("Tracing backward i:%i h:%i\n", i, current_h); | ||
1183 | /* If there is a rise, use it. */ | ||
1184 | if (bases[i] >= current_h || ++skipped > PATHFINDING_MICROSTEP_SKIP2) { | ||
1185 | if (skipped == PATHFINDING_MICROSTEP_SKIP2) { | ||
1186 | i = highest_i; | ||
1187 | if (debugTrace) | ||
1188 | Com_Printf(" Skipped too many steps, reverting to i:%i\n", i); | ||
1189 | } | ||
1190 | opening->invstepup = std::max(opening->invstepup, bases[i] - current_h); | ||
1191 | current_h = bases[i]; | ||
1192 | highest_h = -2; | ||
1193 | highest_i = i - 1; | ||
1194 | skipped = 0; | ||
1195 | if (debugTrace) | ||
1196 | Com_Printf(" Advancing b:%i stepup:%i\n", bases[i], opening->invstepup); | ||
1197 | } else { | ||
1198 | /* We are skipping this step in case the actor can step over this lower step. */ | ||
1199 | /* Record the step in case it is the highest of the low steps. */ | ||
1200 | if (bases[i] > highest_h) { | ||
1201 | highest_h = bases[i]; | ||
1202 | highest_i = i; | ||
1203 | } | ||
1204 | if (debugTrace) | ||
1205 | Com_Printf(" Skipped because we are falling, skip:%i.\n", skipped); | ||
1206 | /* If this is the last iteration, make sure we go back and get our last stepup tests. */ | ||
1207 | if (i == 0) { | ||
1208 | skipped = PATHFINDING_MICROSTEP_SKIP2; | ||
1209 | i = highest_i + 1; | ||
1210 | if (debugTrace) | ||
1211 | Com_Printf(" Tripping skip counter to perform last tests.\n"); | ||
1212 | } | ||
1213 | } | ||
1214 | } | ||
1215 | |||
1216 | if (stairwaySituation) { | ||
1217 | const int middle = bases[4]; /* terrible hack by Duke. This relies on PATHFINDING_MICROSTEP_SIZE being set to 4 !! */ | ||
1218 | |||
1219 | if (stairwaySituation == 1) { /* stepping up */ | ||
1220 | if (bases[1] <= middle && /* if nothing in the 1st part of the passage is higher than what's at the border */ | ||
1221 | bases[2] <= middle && | ||
1222 | bases[3] <= middle ) { | ||
1223 | if (debugTrace) | ||
1224 | Com_Printf("Addition granted by ugly stair hack-stepping up.\n"); | ||
1225 | return opening->base - middle; | ||
1226 | } | ||
1227 | } else if (stairwaySituation == 2) {/* stepping down */ | ||
1228 | if (bases[5] <= middle && /* same for the 2nd part of the passage */ | ||
1229 | bases[6] <= middle && | ||
1230 | bases[7] <= middle ) | ||
1231 | if (debugTrace) | ||
1232 | Com_Printf("Addition granted by ugly stair hack-stepping down.\n"); | ||
1233 | return opening->base - middle; | ||
1234 | } | ||
1235 | } | ||
1236 | |||
1237 | /* Return the confirmed passage opening. */ | ||
1238 | return opening->base - newBottom; | ||
1239 | } | ||
1240 | |||
1241 | |||
1242 | /** | ||
1243 | * @brief Performs traces to find a passage between two points given an upper and lower bound. | ||
1244 | * @param[in] rtd The essential routing data with map, actorsize, ents | ||
1245 | * @param[in] from Starting place | ||
1246 | * @param[in] to Ending place | ||
1247 | * @param[out] opening descriptor of the opening found, if any | ||
1248 | * @return The size in QUANT units of the detected opening. | ||
1249 | */ | ||
1250 | static int RT_TraceOnePassage (RT_data_t *rtd, const place_t* from, const place_t* to, opening_t* opening) | ||
1251 | { | ||
1252 | int hi; /**< absolute ceiling of the passage found. */ | ||
1253 | const int z = from->cell[2]; | ||
1254 | int az; /**< z height of the actor after moving in this direction. */ | ||
1255 | const int lower = std::max(from->floor, to->floor); | ||
1256 | const int upper = std::min(from->ceiling, to->ceiling); | ||
1257 | const int ax = to->cell[0]; | ||
1258 | const int ay = to->cell[1]; | ||
1259 | |||
1260 | RT_FindOpening(rtd, from, ax, ay, lower, upper, &opening->base, &hi); | ||
1261 | /* calc opening found so far and set stepup */ | ||
1262 | opening->size = hi - opening->base; | ||
| |||
1263 | az = to->floorZ; | ||
1264 | |||
1265 | /* We subtract MIN_STEPUP because that is foot space- | ||
1266 | * the opening there only needs to be the microtrace | ||
1267 | * wide and not the usual dimensions. | ||
1268 | */ | ||
1269 | if (az != RT_NO_OPENING-1 && opening->size >= PATHFINDING_MIN_OPENING6 - PATHFINDING_MIN_STEPUP2) { | ||
1270 | const int srcFloor = from->floor; | ||
1271 | const int dstFloor = RT_FLOOR(rtd->map, rtd->actorSize, ax, ay, az)rtd->map[(rtd->actorSize) - 1].floor[(az)][(ay)][(ax)] + az * CELL_HEIGHT(64 / 4); | ||
1272 | /* if we already have enough headroom, try to skip microtracing */ | ||
1273 | if (opening->size < ACTOR_MAX_HEIGHT((64 - 16) / 4) | ||
1274 | || abs(srcFloor - opening->base) > PATHFINDING_MIN_STEPUP2 | ||
1275 | || abs(dstFloor - opening->base) > PATHFINDING_MIN_STEPUP2) { | ||
1276 | int stairway = RT_PlaceIsShifted(from, to); | ||
1277 | /* This returns the total opening height, as the | ||
1278 | * microtrace may reveal more passage height from the foot space. */ | ||
1279 | const int bonusSize = RT_MicroTrace(rtd, from, ax, ay, az, stairway, opening); | ||
1280 | opening->base -= bonusSize; | ||
1281 | opening->size = hi - opening->base; /* re-calculate */ | ||
1282 | } else { | ||
1283 | /* Skipping microtracing, just set the stepup values. */ | ||
1284 | opening->stepup = std::max(0, opening->base - srcFloor); | ||
1285 | opening->invstepup = std::max(0, opening->base - dstFloor); | ||
1286 | } | ||
1287 | |||
1288 | /* Now place an upper bound on stepup */ | ||
1289 | if (opening->stepup > PATHFINDING_MAX_STEPUP4) { | ||
1290 | opening->stepup = PATHFINDING_NO_STEPUP(2 * (64 / 4)); | ||
1291 | } else { | ||
1292 | /* Add rise/fall bit as needed. */ | ||
1293 | if (az < z && opening->invstepup <= PATHFINDING_MAX_STEPUP4) | ||
1294 | /* BIG_STEPDOWN indicates 'walking down', don't set it if we're 'falling' */ | ||
1295 | opening->stepup |= PATHFINDING_BIG_STEPDOWN0x40; | ||
1296 | else if (az > z) | ||
1297 | opening->stepup |= PATHFINDING_BIG_STEPUP0x80; | ||
1298 | } | ||
1299 | |||
1300 | /* Now place an upper bound on stepup */ | ||
1301 | if (opening->invstepup > PATHFINDING_MAX_STEPUP4) { | ||
1302 | opening->invstepup = PATHFINDING_NO_STEPUP(2 * (64 / 4)); | ||
1303 | } else { | ||
1304 | /* Add rise/fall bit as needed. */ | ||
1305 | if (az > z) | ||
1306 | opening->invstepup |= PATHFINDING_BIG_STEPDOWN0x40; | ||
1307 | else if (az < z) | ||
1308 | opening->invstepup |= PATHFINDING_BIG_STEPUP0x80; | ||
1309 | } | ||
1310 | |||
1311 | if (opening->size >= PATHFINDING_MIN_OPENING6) { | ||
1312 | return opening->size; | ||
1313 | } | ||
1314 | } | ||
1315 | |||
1316 | if (debugTrace) | ||
1317 | Com_Printf(" No opening found.\n"); | ||
1318 | opening->stepup = PATHFINDING_NO_STEPUP(2 * (64 / 4)); | ||
1319 | opening->invstepup = PATHFINDING_NO_STEPUP(2 * (64 / 4)); | ||
1320 | return 0; | ||
1321 | } | ||
1322 | |||
1323 | /** | ||
1324 | * @brief Performs traces to find a passage between two points. | ||
1325 | * @param[in] rtd The essential routing data with map, actorsize, ents | ||
1326 | * @param[in] x Starting x coordinate | ||
1327 | * @param[in] y Starting y coordinate | ||
1328 | * @param[in] z Starting z coordinate | ||
1329 | * @param[in] ax Ending x coordinate | ||
1330 | * @param[in] ay Ending y coordinate | ||
1331 | * @param[out] opening descriptor of the opening found, if any | ||
1332 | */ | ||
1333 | static void RT_TracePassage (RT_data_t *rtd, const int x, const int y, const int z, const int ax, const int ay, opening_t* opening) | ||
1334 | { | ||
1335 | int aboveCeil, lowCeil; | ||
1336 | /** we don't need the cell below the adjacent cell because we should have already checked it */ | ||
1337 | place_t from, to, above; | ||
1338 | const place_t* placeToCheck = NULL__null; | ||
1339 | |||
1340 | RT_PlaceInit(rtd->map, rtd->actorSize, &from, x, y, z); | ||
1341 | RT_PlaceInit(rtd->map, rtd->actorSize, &to, ax, ay, z); | ||
1342 | |||
1343 | aboveCeil = (z < PATHFINDING_HEIGHT8 - 1) ? RT_CEILING(rtd->map, rtd->actorSize, ax, ay, z + 1)rtd->map[(rtd->actorSize) - 1].ceil[(z + 1)][(ay)][(ax) ] + (z + 1) * CELL_HEIGHT(64 / 4) : to.ceiling; | ||
| |||
1344 | lowCeil = std::min(from.ceiling, (RT_CEILING(rtd->map, rtd->actorSize, ax, ay, z)rtd->map[(rtd->actorSize) - 1].ceil[(z)][(ay)][(ax)] == 0 || to.ceiling - from.floor < PATHFINDING_MIN_OPENING6) ? aboveCeil : to.ceiling); | ||
| |||
1345 | |||
1346 | /* | ||
1347 | * First check the ceiling for the cell beneath the adjacent floor to see | ||
1348 | * if there is a potential opening. The difference between the | ||
1349 | * ceiling and the floor is at least PATHFINDING_MIN_OPENING tall, then | ||
1350 | * scan it to see if we can use it. If we can, then one of two things | ||
1351 | * will happen: | ||
1352 | * - The actual adjacent cell has no floor of its own, and we will walk | ||
1353 | * or fall into the cell below the adjacent cell anyway. | ||
1354 | * - There is a floor in the adjacent cell, but we will not be able to | ||
1355 | * walk into it anyway because there cannot be any steps if there is | ||
1356 | * a passage. An actor can walk down into the cell ONLY IF it's | ||
1357 | * negative stepup meets or exceeds the change in floor height. | ||
1358 | * No actors will be allowed to fall because they cannot temporarily | ||
1359 | * occupy the space beneath the floor in the adjacent cell to fall | ||
1360 | * (all actors in the cell must be ON TOP of the floor in the cell). | ||
1361 | * If there is no passage, then the obstruction may be used as steps to | ||
1362 | * climb up to the adjacent floor. | ||
1363 | */ | ||
1364 | if (RT_PlaceIsUsable(&to) && RT_PlaceDoesIntersectEnough(&from, &to)) { | ||
| |||
1365 | placeToCheck = &to; | ||
1366 | } else if (z < PATHFINDING_HEIGHT8 - 1) { | ||
| |||
1367 | RT_PlaceInit(rtd->map, rtd->actorSize, &above, ax, ay, z + 1); | ||
1368 | if (RT_PlaceIsUsable(&above) && RT_PlaceDoesIntersectEnough(&from, &above)) { | ||
| |||
1369 | placeToCheck = &above; | ||
1370 | } | ||
1371 | } | ||
1372 | if (!placeToCheck) { | ||
| |||
1373 | if (debugTrace) | ||
1374 | Com_Printf(" No opening found. c:%i lc:%i.\n", from.ceiling, lowCeil); | ||
1375 | /* If we got here, then there is no opening from floor to ceiling. */ | ||
1376 | opening->stepup = PATHFINDING_NO_STEPUP(2 * (64 / 4)); | ||
1377 | opening->invstepup = PATHFINDING_NO_STEPUP(2 * (64 / 4)); | ||
1378 | opening->base = lowCeil; | ||
1379 | opening->size = 0; | ||
1380 | return; | ||
1381 | } | ||
1382 | |||
1383 | /* | ||
1384 | * Now that we got here, we know that either the opening between the | ||
1385 | * ceiling below the adjacent cell and the current floor is too small or | ||
1386 | * obstructed. Try to move onto the adjacent floor. | ||
1387 | */ | ||
1388 | if (debugTrace) | ||
| |||
1389 | Com_Printf(" Testing up c:%i lc:%i.\n", from.ceiling, lowCeil); | ||
1390 | |||
1391 | RT_TraceOnePassage(rtd, &from, placeToCheck, opening); | ||
1392 | if (opening->size < PATHFINDING_MIN_OPENING6) { | ||
1393 | if (debugTrace) | ||
1394 | Com_Printf(" No opening found.\n"); | ||
1395 | /* If we got here, then there is no useable opening from floor to ceiling. */ | ||
1396 | opening->stepup = PATHFINDING_NO_STEPUP(2 * (64 / 4)); | ||
1397 | opening->invstepup = PATHFINDING_NO_STEPUP(2 * (64 / 4)); | ||
1398 | opening->base = lowCeil; | ||
1399 | opening->size = 0; | ||
1400 | } | ||
1401 | } | ||
1402 | |||
1403 | |||
1404 | /** | ||
1405 | * @brief Routing Function to update the connection between two fields | ||
1406 | * @param[in] rtd The essential routing data with map, actorsize, ents | ||
1407 | * @param[in] x The x position in the routing arrays (0 to PATHFINDING_WIDTH - actorSize) | ||
1408 | * @param[in] y The y position in the routing arrays (0 to PATHFINDING_WIDTH - actorSize) | ||
1409 | * @param[in] ax The x of the adjacent cell | ||
1410 | * @param[in] ay The y of the adjacent cell | ||
1411 | * @param[in] z The z position in the routing arrays (0 to PATHFINDING_HEIGHT - 1) | ||
1412 | * @param[in] dir The direction to test for a connection through | ||
1413 | */ | ||
1414 | static int RT_UpdateConnection (RT_data_t *rtd, const int x, const int y, const int ax, const int ay, const int z, const int dir) | ||
1415 | { | ||
1416 | const int ceiling = RT_CEILING(rtd->map, rtd->actorSize, x, y, z)rtd->map[(rtd->actorSize) - 1].ceil[(z)][(y)][(x)]; | ||
1417 | const int adjCeiling = RT_CEILING(rtd->map, rtd->actorSize, ax, ay, z)rtd->map[(rtd->actorSize) - 1].ceil[(z)][(ay)][(ax)]; | ||
1418 | const int extAdjCeiling = (z < PATHFINDING_HEIGHT8 - 1) ? RT_CEILING(rtd->map, rtd->actorSize, ax, ay, z + 1)rtd->map[(rtd->actorSize) - 1].ceil[(z + 1)][(ay)][(ax) ] : adjCeiling; | ||
| |||
1419 | const int absCeiling = ceiling + z * CELL_HEIGHT(64 / 4); | ||
1420 | const int absAdjCeiling = adjCeiling + z * CELL_HEIGHT(64 / 4); | ||
1421 | const int absExtAdjCeiling = (z < PATHFINDING_HEIGHT8 - 1) ? adjCeiling + (z + 1) * CELL_HEIGHT(64 / 4) : absCeiling; | ||
| |||
1422 | const int absFloor = RT_FLOOR(rtd->map, rtd->actorSize, x, y, z)rtd->map[(rtd->actorSize) - 1].floor[(z)][(y)][(x)] + z * CELL_HEIGHT(64 / 4); | ||
1423 | const int absAdjFloor = RT_FLOOR(rtd->map, rtd->actorSize, ax, ay, z)rtd->map[(rtd->actorSize) - 1].floor[(z)][(ay)][(ax)] + z * CELL_HEIGHT(64 / 4); | ||
1424 | opening_t opening; /** the opening between the two cells */ | ||
1425 | int new_z1, az = z; | ||
1426 | #if RT_IS_BIDIRECTIONAL0 == 1 | ||
1427 | int new_z2; | ||
1428 | #endif | ||
1429 | |||
1430 | if (debugTrace) | ||
| |||
1431 | Com_Printf("\n(%i, %i, %i) to (%i, %i, %i) as:%i\n", x, y, z, ax, ay, z, rtd->actorSize); | ||
1432 | |||
1433 | /** test if the adjacent cell and the cell above it are blocked by a loaded model */ | ||
1434 | if (adjCeiling == 0 && (extAdjCeiling == 0 || ceiling == 0)) { | ||
| |||
1435 | /* We can't go this way. */ | ||
1436 | RT_ConnSetNoGo(rtd, x, y, z, dir); | ||
1437 | #if RT_IS_BIDIRECTIONAL0 == 1 | ||
1438 | RT_ConnSetNoGo(rtd, ax, ay, z, dir ^ 1); | ||
1439 | #endif | ||
1440 | if (debugTrace) | ||
1441 | Com_Printf("Current cell filled. c:%i ac:%i\n", RT_CEILING(rtd->map, rtd->actorSize, x, y, z)rtd->map[(rtd->actorSize) - 1].ceil[(z)][(y)][(x)], RT_CEILING(rtd->map, rtd->actorSize, ax, ay, z)rtd->map[(rtd->actorSize) - 1].ceil[(z)][(ay)][(ax)]); | ||
1442 | return z; | ||
1443 | } | ||
1444 | |||
1445 | #if RT_IS_BIDIRECTIONAL0 == 1 | ||
1446 | /** In case the adjacent floor has no ceiling, swap the current and adjacent cells. */ | ||
1447 | if (ceiling == 0 && adjCeiling != 0) { | ||
1448 | return RT_UpdateConnection(rtd->map, actorSize, ax, ay, x, y, z, dir ^ 1); | ||
1449 | } | ||
1450 | #endif | ||
1451 | |||
1452 | /** | ||
1453 | * @note OK, simple test here. We know both cells have a ceiling, so they are both open. | ||
1454 | * If the absolute ceiling of one is below the absolute floor of the other, then there is no intersection. | ||
1455 | */ | ||
1456 | if (absCeiling < absAdjFloor || absExtAdjCeiling < absFloor) { | ||
| |||
1457 | /* We can't go this way. */ | ||
1458 | RT_ConnSetNoGo(rtd, x, y, z, dir); | ||
1459 | #if RT_IS_BIDIRECTIONAL0 == 1 | ||
1460 | RT_ConnSetNoGo(rtd, ax, ay, z, dir ^ 1); | ||
1461 | #endif | ||
1462 | if (debugTrace) | ||
1463 | Com_Printf("Ceiling lower than floor. f:%i c:%i af:%i ac:%i\n", absFloor, absCeiling, absAdjFloor, absAdjCeiling); | ||
1464 | return z; | ||
1465 | } | ||
1466 | |||
1467 | /** Find an opening. */ | ||
1468 | RT_TracePassage(rtd, x, y, z, ax, ay, &opening); | ||
1469 | if (debugTrace) { | ||
1470 | Com_Printf("Final RT_STEPUP for (%i, %i, %i) as:%i dir:%i = %i\n", x, y, z, rtd->actorSize, dir, opening.stepup); | ||
1471 | } | ||
1472 | /** Apply the data to the routing table. | ||
1473 | * We always call the fill function. If the passage cannot be traveled, the | ||
1474 | * function fills it in as unpassable. */ | ||
1475 | new_z1 = RT_FillPassageData(rtd, dir, x, y, z, opening.size, opening.base, opening.stepup); | ||
1476 | |||
1477 | if (opening.stepup & PATHFINDING_BIG_STEPUP0x80) { | ||
1478 | /* ^ 1 reverses the direction of dir */ | ||
1479 | #if RT_IS_BIDIRECTIONAL0 == 1 | ||
1480 | RT_ConnSetNoGo(rtd, ax, ay, z, dir ^ 1); | ||
1481 | #endif | ||
1482 | az++; | ||
1483 | } else if (opening.stepup & PATHFINDING_BIG_STEPDOWN0x40) { | ||
1484 | az--; | ||
1485 | } | ||
1486 | #if RT_IS_BIDIRECTIONAL0 == 1 | ||
1487 | new_z2 = RT_FillPassageData(rtd, dir ^ 1, ax, ay, az, opening.size, opening.base, opening.invstepup); | ||
1488 | if (new_z2 == az && az < z) | ||
1489 | new_z2++; | ||
1490 | return std::min(new_z1, new_z2); | ||
1491 | #else | ||
1492 | return new_z1; | ||
1493 | #endif | ||
1494 | } | ||
1495 | |||
1496 | |||
1497 | /** | ||
1498 | * @brief Routing Function to update the connection between two fields | ||
1499 | * @param[in] mapTiles List of tiles the current (RMA-)map is composed of | ||
1500 | * @param[in] map Routing table of the current loaded map | ||
1501 | * @param[in] actorSize The size of the actor, in units | ||
1502 | * @param[in] x The x position in the routing arrays (0 to PATHFINDING_WIDTH - actorSize) | ||
1503 | * @param[in] y The y position in the routing arrays (0 to PATHFINDING_WIDTH - actorSize) | ||
1504 | * @param[in] dir The direction to test for a connection through | ||
1505 | * @param[in] list The local models list (a local model has a name starting with * followed by the model number) | ||
1506 | */ | ||
1507 | void RT_UpdateConnectionColumn (mapTiles_t *mapTiles, routing_t * map, const int actorSize, const int x, const int y, const int dir, const char **list) | ||
1508 | { | ||
1509 | int z = 0; /**< The current z value that we are testing. */ | ||
1510 | RT_data_t rtd; /* the essential data passed down the calltree */ | ||
1511 | |||
1512 | /* get the neighbor cell's coordinates */ | ||
1513 | const int ax = x + dvecs[dir][0]; | ||
1514 | const int ay = y + dvecs[dir][1]; | ||
1515 | |||
1516 | assert(actorSize > ACTOR_SIZE_INVALID && actorSize <= ACTOR_MAX_SIZE)(__builtin_expect(!(actorSize > 0 && actorSize <= (2)), 0) ? __assert_rtn(__func__, "src/common/routing.cpp", 1516 , "actorSize > ACTOR_SIZE_INVALID && actorSize <= ACTOR_MAX_SIZE" ) : (void)0); | ||
1517 | assert(map)(__builtin_expect(!(map), 0) ? __assert_rtn(__func__, "src/common/routing.cpp" , 1517, "map") : (void)0); | ||
1518 | assert((x >= 0) && (x <= PATHFINDING_WIDTH - actorSize))(__builtin_expect(!((x >= 0) && (x <= ((4096 / 32 ) * 2) - actorSize)), 0) ? __assert_rtn(__func__, "src/common/routing.cpp" , 1518, "(x >= 0) && (x <= PATHFINDING_WIDTH - actorSize)" ) : (void)0); | ||
1519 | assert((y >= 0) && (y <= PATHFINDING_WIDTH - actorSize))(__builtin_expect(!((y >= 0) && (y <= ((4096 / 32 ) * 2) - actorSize)), 0) ? __assert_rtn(__func__, "src/common/routing.cpp" , 1519, "(y >= 0) && (y <= PATHFINDING_WIDTH - actorSize)" ) : (void)0); | ||
1520 | |||
1521 | #ifdef DEBUG1 | ||
1522 | /** @todo remove me */ | ||
1523 | /* just a place to place a breakpoint */ | ||
1524 | if (x == 135 && y == 120 && dir == 1) { | ||
1525 | z = 7; | ||
1526 | } | ||
1527 | #endif | ||
1528 | |||
1529 | /* Ensure that the current coordinates are valid. */ | ||
1530 | RT_CONN_TEST(map, actorSize, x, y, z, dir)(__builtin_expect(!((actorSize) > 0), 0) ? __assert_rtn(__func__ , "src/common/routing.cpp", 1530, "(actorSize) > ACTOR_SIZE_INVALID" ) : (void)0); (__builtin_expect(!((actorSize) <= (2)), 0) ? __assert_rtn(__func__, "src/common/routing.cpp", 1530, "(actorSize) <= ACTOR_MAX_SIZE" ) : (void)0); (__builtin_expect(!((z) >= 0), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 1530, "(z) >= 0") : ( void)0); (__builtin_expect(!((z) < 8), 0) ? __assert_rtn(__func__ , "src/common/routing.cpp", 1530, "(z) < PATHFINDING_HEIGHT" ) : (void)0); (__builtin_expect(!((y) >= 0), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 1530, "(y) >= 0") : ( void)0); (__builtin_expect(!((y) < ((4096 / 32) * 2)), 0) ? __assert_rtn(__func__, "src/common/routing.cpp", 1530, "(y) < PATHFINDING_WIDTH" ) : (void)0); (__builtin_expect(!((x) >= 0), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 1530, "(x) >= 0") : ( void)0); (__builtin_expect(!((x) < ((4096 / 32) * 2)), 0) ? __assert_rtn(__func__, "src/common/routing.cpp", 1530, "(x) < PATHFINDING_WIDTH" ) : (void)0); (__builtin_expect(!((dir) >= 0), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 1530, "(dir) >= 0") : (void)0); (__builtin_expect(!((dir) < 8), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 1530, "(dir) < CORE_DIRECTIONS" ) : (void)0);; | ||
1531 | |||
1532 | /* Com_Printf("At (%i, %i, %i) looking in direction %i with size %i\n", x, y, z, dir, actorSize); */ | ||
1533 | |||
1534 | /* build the param list passed to most of the RT_* functions */ | ||
1535 | rtd.mapTiles = mapTiles; | ||
1536 | rtd.map = map; | ||
1537 | rtd.actorSize = actorSize; | ||
1538 | rtd.list = list; | ||
1539 | |||
1540 | /* if our destination cell is out of bounds, bail. */ | ||
1541 | if (ax < 0 || ax > PATHFINDING_WIDTH((4096 / 32) * 2) - actorSize || ay < 0 || y > PATHFINDING_WIDTH((4096 / 32) * 2) - actorSize) { | ||
1542 | /* We can't go this way. */ | ||
1543 | RT_ConnSetNoGo(&rtd, x, y, z, dir); | ||
1544 | /* There is only one entry here: There is no inverse cell to store data for. */ | ||
1545 | if (debugTrace) | ||
1546 | Com_Printf("Destination cell non-existant.\n"); | ||
1547 | return; | ||
1548 | } | ||
1549 | |||
1550 | /* Ensure that the destination coordinates are valid. */ | ||
1551 | RT_CONN_TEST(map, actorSize, ax, ay, z, dir)(__builtin_expect(!((actorSize) > 0), 0) ? __assert_rtn(__func__ , "src/common/routing.cpp", 1551, "(actorSize) > ACTOR_SIZE_INVALID" ) : (void)0); (__builtin_expect(!((actorSize) <= (2)), 0) ? __assert_rtn(__func__, "src/common/routing.cpp", 1551, "(actorSize) <= ACTOR_MAX_SIZE" ) : (void)0); (__builtin_expect(!((z) >= 0), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 1551, "(z) >= 0") : ( void)0); (__builtin_expect(!((z) < 8), 0) ? __assert_rtn(__func__ , "src/common/routing.cpp", 1551, "(z) < PATHFINDING_HEIGHT" ) : (void)0); (__builtin_expect(!((ay) >= 0), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 1551, "(ay) >= 0") : ( void)0); (__builtin_expect(!((ay) < ((4096 / 32) * 2)), 0) ? __assert_rtn(__func__, "src/common/routing.cpp", 1551, "(ay) < PATHFINDING_WIDTH" ) : (void)0); (__builtin_expect(!((ax) >= 0), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 1551, "(ax) >= 0") : ( void)0); (__builtin_expect(!((ax) < ((4096 / 32) * 2)), 0) ? __assert_rtn(__func__, "src/common/routing.cpp", 1551, "(ax) < PATHFINDING_WIDTH" ) : (void)0); (__builtin_expect(!((dir) >= 0), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 1551, "(dir) >= 0") : (void)0); (__builtin_expect(!((dir) < 8), 0) ? __assert_rtn (__func__, "src/common/routing.cpp", 1551, "(dir) < CORE_DIRECTIONS" ) : (void)0);; | ||
1552 | |||
1553 | /* Main loop */ | ||
1554 | for (z = 0; z < PATHFINDING_HEIGHT8; z++) { | ||
1555 | /* The last z value processed by the tracing function. */ | ||
1556 | const int new_z = RT_UpdateConnection(&rtd, x, y, ax, ay, z, dir); | ||
1557 | assert(new_z >= z)(__builtin_expect(!(new_z >= z), 0) ? __assert_rtn(__func__ , "src/common/routing.cpp", 1557, "new_z >= z") : (void)0); | ||
1558 | z = new_z; | ||
1559 | } | ||
1560 | } | ||
1561 | |||
1562 | void RT_WriteCSVFiles (const routing_t *map, const char* baseFilename, const ipos3_t mins, const ipos3_t maxs) | ||
1563 | { | ||
1564 | char filename[MAX_OSPATH256], ext[MAX_OSPATH256]; | ||
1565 | qFILE f; | ||
1566 | int i, x, y, z; | ||
1567 | |||
1568 | /* An elevation files- dumps the floor and ceiling levels relative to each cell. */ | ||
1569 | for (i = 1; i <= ACTOR_MAX_SIZE(2); i++) { | ||
1570 | strncpy(filename, baseFilename, sizeof(filename) - 1); | ||
1571 | sprintf(ext, ".%i.elevation.csv", i); | ||
1572 | Com_DefaultExtension(filename, sizeof(filename), ext); | ||
1573 | FS_OpenFile(filename, &f, FILE_WRITE); | ||
1574 | if (!f.f) | ||
1575 | Sys_Error("Could not open file %s.", filename); | ||
1576 | FS_Printf(&f, ","); | ||
1577 | for (x = mins[0]; x <= maxs[0] - i + 1; x++) | ||
1578 | FS_Printf(&f, "x:%i,", x); | ||
1579 | FS_Printf(&f, "\n"); | ||
1580 | for (z = maxs[2]; z >= mins[2]; z--) { | ||
1581 | for (y = maxs[1]; y >= mins[1] - i + 1; y--) { | ||
1582 | FS_Printf(&f, "z:%i y:%i,", z ,y); | ||
1583 | for (x = mins[0]; x <= maxs[0] - i + 1; x++) { | ||
1584 | /* compare results */ | ||
1585 | FS_Printf(&f, "h:%i c:%i,", RT_FLOOR(map, i, x, y, z)map[(i) - 1].floor[(z)][(y)][(x)], RT_CEILING(map, i, x, y, z)map[(i) - 1].ceil[(z)][(y)][(x)]); | ||
1586 | } | ||
1587 | FS_Printf(&f, "\n"); | ||
1588 | } | ||
1589 | FS_Printf(&f, "\n"); | ||
1590 | } | ||
1591 | FS_CloseFile(&f); | ||
1592 | } | ||
1593 | |||
1594 | /* Output the walls/passage files. */ | ||
1595 | for (i = 1; i <= ACTOR_MAX_SIZE(2); i++) { | ||
1596 | strncpy(filename, baseFilename, sizeof(filename) - 1); | ||
1597 | sprintf(ext, ".%i.walls.csv", i); | ||
1598 | Com_DefaultExtension(filename, sizeof(filename), ext); | ||
1599 | FS_OpenFile(filename, &f, FILE_WRITE); | ||
1600 | if (!f.f) | ||
1601 | Sys_Error("Could not open file %s.", filename); | ||
1602 | FS_Printf(&f, ","); | ||
1603 | for (x = mins[0]; x <= maxs[0] - i + 1; x++) | ||
1604 | FS_Printf(&f, "x:%i,", x); | ||
1605 | FS_Printf(&f, "\n"); | ||
1606 | for (z = maxs[2]; z >= mins[2]; z--) { | ||
1607 | for (y = maxs[1]; y >= mins[1] - i + 1; y--) { | ||
1608 | FS_Printf(&f, "z:%i y:%i,", z ,y); | ||
1609 | for (x = mins[0]; x <= maxs[0] - i + 1; x++) { | ||
1610 | /* compare results */ | ||
1611 | FS_Printf(&f, "\""); | ||
1612 | |||
1613 | /* NW corner */ | ||
1614 | FS_Printf(&f, "%3i-%3i ", RT_CONN_NX_PY(map, i, x, y, z)(map[(i) - 1].route[(z)][(y)][(x)][(6)]), RT_STEPUP_NX_PY(map, i, x, y, z)(map[(i) - 1].stepup[(z)][(y)][(x)][(6)])); | ||
1615 | |||
1616 | /* N side */ | ||
1617 | FS_Printf(&f, "%3i-%3i ", RT_CONN_PY(map, i, x, y, z)(map[(i) - 1].route[(z)][(y)][(x)][(2)]), RT_STEPUP_PY(map, i, x, y, z)(map[(i) - 1].stepup[(z)][(y)][(x)][(2)])); | ||
1618 | |||
1619 | /* NE corner */ | ||
1620 | FS_Printf(&f, "%3i-%3i ", RT_CONN_PX_PY(map, i, x, y, z)(map[(i) - 1].route[(z)][(y)][(x)][(4)]), RT_STEPUP_PX_PY(map, i, x, y, z)(map[(i) - 1].stepup[(z)][(y)][(x)][(4)])); | ||
1621 | |||
1622 | FS_Printf(&f, "\n"); | ||
1623 | |||
1624 | /* W side */ | ||
1625 | FS_Printf(&f, "%3i-%3i ", RT_CONN_NX(map, i, x, y, z)(map[(i) - 1].route[(z)][(y)][(x)][(1)]), RT_STEPUP_NX(map, i, x, y, z)(map[(i) - 1].stepup[(z)][(y)][(x)][(1)])); | ||
1626 | |||
1627 | /* Center - display floor height */ | ||
1628 | FS_Printf(&f, "_%+2i_ ", RT_FLOOR(map, i, x, y, z)map[(i) - 1].floor[(z)][(y)][(x)]); | ||
1629 | |||
1630 | /* E side */ | ||
1631 | FS_Printf(&f, "%3i-%3i ", RT_CONN_PX(map, i, x, y, z)(map[(i) - 1].route[(z)][(y)][(x)][(0)]), RT_STEPUP_PX(map, i, x, y, z)(map[(i) - 1].stepup[(z)][(y)][(x)][(0)])); | ||
1632 | |||
1633 | FS_Printf(&f, "\n"); | ||
1634 | |||
1635 | /* SW corner */ | ||
1636 | FS_Printf(&f, "%3i-%3i ", RT_CONN_NX_NY(map, i, x, y, z)(map[(i) - 1].route[(z)][(y)][(x)][(5)]), RT_STEPUP_NX_NY(map, i, x, y, z)(map[(i) - 1].stepup[(z)][(y)][(x)][(5)])); | ||
1637 | |||
1638 | /* S side */ | ||
1639 | FS_Printf(&f, "%3i-%3i ", RT_CONN_NY(map, i, x, y, z)(map[(i) - 1].route[(z)][(y)][(x)][(3)]), RT_STEPUP_NY(map, i, x, y, z)(map[(i) - 1].stepup[(z)][(y)][(x)][(3)])); | ||
1640 | |||
1641 | /* SE corner */ | ||
1642 | FS_Printf(&f, "%3i-%3i ", RT_CONN_PX_NY(map, i, x, y, z)(map[(i) - 1].route[(z)][(y)][(x)][(7)]), RT_STEPUP_PX_NY(map, i, x, y, z)(map[(i) - 1].stepup[(z)][(y)][(x)][(7)])); | ||
1643 | |||
1644 | FS_Printf(&f, "\","); | ||
1645 | } | ||
1646 | FS_Printf(&f, "\n"); | ||
1647 | } | ||
1648 | FS_Printf(&f, "\n"); | ||
1649 | } | ||
1650 | FS_CloseFile(&f); | ||
1651 | } | ||
1652 | } | ||
1653 | |||
1654 | #ifdef DEBUG1 | ||
1655 | /** | ||
1656 | * @brief A debug function to be called from CL_DebugPath_f | ||
1657 | * @param[in] mapTiles List of tiles the current (RMA-)map is composed of | ||
1658 | * @param[in] map Routing table of the current loaded map | ||
1659 | * @param[in] actorSize The size of the actor, in units | ||
1660 | * @param[in] x The x position in the routing arrays (0 to PATHFINDING_WIDTH - actorSize) | ||
1661 | * @param[in] y The y position in the routing arrays (0 to PATHFINDING_WIDTH - actorSize) | ||
1662 | * @param[in] dir The direction to test for a connection through | ||
1663 | * @param[in] list The local models list (a local model has a name starting with * followed by the model number) | ||
1664 | */ | ||
1665 | int RT_DebugSpecial (mapTiles_t *mapTiles, routing_t * map, const int actorSize, const int x, const int y, const int dir, const char **list) | ||
1666 | { | ||
1667 | int z = 0; /**< The current z value that we are testing. */ | ||
1668 | int new_z; /**< The last z value processed by the tracing function. */ | ||
1669 | RT_data_t rtd; /* the essential data passed down the calltree */ | ||
1670 | |||
1671 | /* get the neighbor cell's coordinates */ | ||
1672 | const int ax = x + dvecs[dir][0]; | ||
1673 | const int ay = y + dvecs[dir][1]; | ||
1674 | |||
1675 | /* build the param list passed to most of the RT_* functions */ | ||
1676 | rtd.mapTiles = mapTiles; | ||
1677 | rtd.map = map; | ||
1678 | rtd.actorSize = actorSize; | ||
1679 | rtd.list = list; | ||
1680 | |||
1681 | new_z = RT_UpdateConnection(&rtd, x, y, ax, ay, z, dir); | ||
| |||
1682 | return new_z; | ||
1683 | } | ||
1684 | #endif |