Bug Summary

File:common/routing.cpp
Location:line 1262, column 18
Description:The left operand of '-' is a garbage value

Annotated Source Code

1/**
2 * @file
3 * @brief grid pathfinding and routing
4 */
5
6/*
7All original material Copyright (C) 2002-2011 UFO: Alien Invasion.
8
9Copyright (C) 1997-2001 Id Software, Inc.
10
11This program is free software; you can redistribute it and/or
12modify it under the terms of the GNU General Public License
13as published by the Free Software Foundation; either version 2
14of the License, or (at your option) any later version.
15
16This program is distributed in the hope that it will be useful,
17but WITHOUT ANY WARRANTY; without even the implied warranty of
18MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
19
20See the GNU General Public License for more details.
21
22You should have received a copy of the GNU General Public License
23along with this program; if not, write to the Free Software
24Foundation, 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===============================================================================
33MAP TRACING DEBUGGING TABLES
34===============================================================================
35*/
36
37bool 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. */
50static 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. */
57static 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}};
59static 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 */
71typedef 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
78static 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
83static 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
88static 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 */
98typedef 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
106static 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
118static inline bool RT_PlaceIsUsable (const place_t* p)
119{
120 return p->usable;
121}
122
123static 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 */
134static 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 */
149typedef 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 */
175static 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 */
205void 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)TR_SingleTileBoxTrace((mapTiles), (origin),(origin),(&box
),0x1FF, (-1), 0)
;
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)TR_SingleTileBoxTrace((mapTiles), (origin),(origin),(&box
),0x1FF, (-1), 0)
;
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 */
271void 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)TR_SingleTileBoxTrace((mapTiles), (origin),(origin),(&box
),0x1FF, (-1), 0)
;
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)TR_SingleTileBoxTrace((mapTiles), (origin),(origin),(&box
),0x1FF, (-1), 0)
;
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===============================================================================
337NEW 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 */
350bool 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 */
382int 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)TR_SingleTileBoxTrace((mapTiles), (start),(end),(&footBox
),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000 | 0x0020
))
;
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)TR_SingleTileBoxTrace((mapTiles), (vec3_origin),(vec3_origin)
,(&box),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000
| 0x0020))
;
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)TR_SingleTileBoxTrace((mapTiles), (vec3_origin),(vec3_origin)
,(&box),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000
| 0x0020))
;
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)TR_SingleTileBoxTrace((mapTiles), (tstart),(tend),(&ceilBox
),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000 | 0x0020
))
;
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 */
637static 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 */
712static 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)TR_SingleTileBoxTrace((rtd->mapTiles), (start),(end),(&
box),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000 | 0x0020
))
;
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 */
735static 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)TR_SingleTileBoxTrace((rtd->mapTiles), (mstart),(mend),(box
),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000 | 0x0020
))
;
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 */
768static 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)TR_SingleTileBoxTrace((rtd->mapTiles), (mstart),(mend),(box
),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000 | 0x0020
))
;
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 */
800static 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 */
840static 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
870static 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 */
913static 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 */
953static 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)TR_SingleTileBoxTrace((rtd->mapTiles), (sky),(earth),(box)
,0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000 | 0x0020
))
;
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*/
1055static 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)TR_SingleTileBoxTrace((rtd->mapTiles), (start),(end),(&
footBox),0x1FF, ((0x0001 | 0x0002) | 0x00010000), (0x00020000
| 0x0020))
;
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 */
1250static 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;
14
The left operand of '-' is a garbage value
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 */
1333static 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;
7
'?' condition is true
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);
8
'?' condition is true
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)) {
9
Taking false branch
1365 placeToCheck = &to;
1366 } else if (z < PATHFINDING_HEIGHT8 - 1) {
10
Taking true branch
1367 RT_PlaceInit(rtd->map, rtd->actorSize, &above, ax, ay, z + 1);
1368 if (RT_PlaceIsUsable(&above) && RT_PlaceDoesIntersectEnough(&from, &above)) {
11
Taking true branch
1369 placeToCheck = &above;
1370 }
1371 }
1372 if (!placeToCheck) {
12
Taking false branch
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)
13
Taking false branch
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 */
1414static 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;
2
'?' condition is true
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;
3
'?' condition is true
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)
4
Taking false branch
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)) {
5
Taking false branch
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) {
6
Taking false branch
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 */
1507void 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
1562void 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 */
1665int 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);
1
Calling 'RT_UpdateConnection'
1682 return new_z;
1683}
1684#endif