Bug Summary

File:common/grid.cpp
Location:line 356, column 3
Description:Value stored to 'heightChange' is never read

Annotated Source Code

1/**
2 * @file
3 * @brief Grid oriented movement and scanning
4 */
5
6/*
7Copyright (C) 1997-2001 Id Software, Inc.
8
9This program is free software; you can redistribute it and/or
10modify it under the terms of the GNU General Public License
11as published by the Free Software Foundation; either version 2
12of the License, or (at your option) any later version.
13
14This program is distributed in the hope that it will be useful,
15but WITHOUT ANY WARRANTY; without even the implied warranty of
16MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
17
18See the GNU General Public License for more details.
19
20You should have received a copy of the GNU General Public License
21along with this program; if not, write to the Free Software
22Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
23
24*/
25
26#include "common.h"
27#include "grid.h"
28#include "tracing.h"
29#include "routing.h"
30#include "pqueue.h"
31
32/** @note these are the TUs used to intentionally move in a given direction. Falling not included. */
33static const int TUsUsed[] = {
34 TU_MOVE_STRAIGHT2, /* E */
35 TU_MOVE_STRAIGHT2, /* W */
36 TU_MOVE_STRAIGHT2, /* N */
37 TU_MOVE_STRAIGHT2, /* S */
38 TU_MOVE_DIAGONAL3, /* NE */
39 TU_MOVE_DIAGONAL3, /* SW */
40 TU_MOVE_DIAGONAL3, /* NW */
41 TU_MOVE_DIAGONAL3, /* SE */
42 TU_MOVE_CLIMB4, /* UP */
43 TU_MOVE_CLIMB4, /* DOWN */
44 TU_CROUCH3, /* STAND */
45 TU_CROUCH3, /* CROUCH */
46 0, /* ??? */
47 TU_MOVE_FALL0, /* FALL */
48 0, /* ??? */
49 0, /* ??? */
50 TU_MOVE_STRAIGHT2 * TU_FLYING_MOVING_FACTOR2, /* FLY UP & E */
51 TU_MOVE_STRAIGHT2 * TU_FLYING_MOVING_FACTOR2, /* FLY UP & W */
52 TU_MOVE_STRAIGHT2 * TU_FLYING_MOVING_FACTOR2, /* FLY UP & N */
53 TU_MOVE_STRAIGHT2 * TU_FLYING_MOVING_FACTOR2, /* FLY UP & S */
54 TU_MOVE_DIAGONAL3 * TU_FLYING_MOVING_FACTOR2, /* FLY UP & NE */
55 TU_MOVE_DIAGONAL3 * TU_FLYING_MOVING_FACTOR2, /* FLY UP & SW */
56 TU_MOVE_DIAGONAL3 * TU_FLYING_MOVING_FACTOR2, /* FLY UP & NW */
57 TU_MOVE_DIAGONAL3 * TU_FLYING_MOVING_FACTOR2, /* FLY UP & SE */
58 TU_MOVE_STRAIGHT2 * TU_FLYING_MOVING_FACTOR2, /* FLY LEVEL & E */
59 TU_MOVE_STRAIGHT2 * TU_FLYING_MOVING_FACTOR2, /* FLY LEVEL & W */
60 TU_MOVE_STRAIGHT2 * TU_FLYING_MOVING_FACTOR2, /* FLY LEVEL & N */
61 TU_MOVE_STRAIGHT2 * TU_FLYING_MOVING_FACTOR2, /* FLY LEVEL & S */
62 TU_MOVE_DIAGONAL3 * TU_FLYING_MOVING_FACTOR2, /* FLY LEVEL & NE */
63 TU_MOVE_DIAGONAL3 * TU_FLYING_MOVING_FACTOR2, /* FLY LEVEL & SW */
64 TU_MOVE_DIAGONAL3 * TU_FLYING_MOVING_FACTOR2, /* FLY LEVEL & NW */
65 TU_MOVE_DIAGONAL3 * TU_FLYING_MOVING_FACTOR2, /* FLY LEVEL & SE */
66 TU_MOVE_STRAIGHT2 * TU_FLYING_MOVING_FACTOR2, /* FLY DOWN & E */
67 TU_MOVE_STRAIGHT2 * TU_FLYING_MOVING_FACTOR2, /* FLY DOWN & W */
68 TU_MOVE_STRAIGHT2 * TU_FLYING_MOVING_FACTOR2, /* FLY DOWN & N */
69 TU_MOVE_STRAIGHT2 * TU_FLYING_MOVING_FACTOR2, /* FLY DOWN & S */
70 TU_MOVE_DIAGONAL3 * TU_FLYING_MOVING_FACTOR2, /* FLY DOWN & NE */
71 TU_MOVE_DIAGONAL3 * TU_FLYING_MOVING_FACTOR2, /* FLY DOWN & SW */
72 TU_MOVE_DIAGONAL3 * TU_FLYING_MOVING_FACTOR2, /* FLY DOWN & NW */
73 TU_MOVE_DIAGONAL3 * TU_FLYING_MOVING_FACTOR2 /* FLY DOWN & SE */
74};
75CASSERT(lengthof(TUsUsed) == PATHFINDING_DIRECTIONS)extern int ASSERT_COMPILE[(((sizeof(TUsUsed) / sizeof(*(TUsUsed
))) == 40) != 0) * 2 - 1]
;
76
77/**
78* @brief Checks one field (square) on the grid of the given routing data (i.e. the map).
79 * @param[in] exclude Exclude this position from the forbidden list check
80 * @param[in] actorSize width of the actor in cells
81 * @param[in] path Pointer to client or server side pathing table (clPathMap, svPathMap)
82 * @param[in] x Field in x direction
83 * @param[in] y Field in y direction
84 * @param[in] z Field in z direction
85 * @sa Grid_MoveMark
86 * @sa G_BuildForbiddenList
87 * @sa CL_BuildForbiddenList
88 * @return true if one can't walk there (i.e. the field [and attached fields for e.g. 2x2 units] is/are blocked by entries in
89 * the forbidden list) otherwise false.
90 */
91static bool Grid_CheckForbidden (const pos3_t exclude, const actorSizeEnum_t actorSize, pathing_t *path, int x, int y, int z)
92{
93 pos_t **p;
94 int i;
95 actorSizeEnum_t size;
96 int fx, fy, fz; /**< Holding variables for the forbidden x and y */
97 byte *forbiddenSize;
98
99 for (i = 0, p = path->fblist; i < path->fblength / 2; i++, p += 2) {
100 /* Skip initial position. */
101 if (VectorCompare((*p), exclude)(((*p))[0]==(exclude)[0]?((*p))[1]==(exclude)[1]?((*p))[2]==(
exclude)[2]?1:0:0:0)
) {
102 continue;
103 }
104
105 forbiddenSize = *(p + 1);
106 memcpy(&size, forbiddenSize, sizeof(size));
107 fx = (*p)[0];
108 fy = (*p)[1];
109 fz = (*p)[2];
110
111 if (fx + size <= x || x + actorSize <= fx)
112 continue; /* x bounds do not intersect */
113 if (fy + size <= y || y + actorSize <= fy)
114 continue; /* y bounds do not intersect */
115 if (z == fz) {
116 return true; /* confirmed intersection */
117 }
118 }
119 return false;
120}
121
122static void Grid_SetMoveData (pathing_t *path, const pos3_t toPos, const int c, const byte length, const int dir, const int oz, const int oc, priorityQueue_t *pqueue)
123{
124 pos4_t dummy;
125
126 RT_AREA_TEST_POS(path, toPos, c)(__builtin_expect(!((toPos)[2] < 8), 0) ? __assert_rtn(__func__
, "src/common/grid.cpp", 126, "(toPos)[2] < PATHFINDING_HEIGHT"
) : (void)0); (__builtin_expect(!((c) == 0 || (c) == 1), 0) ?
__assert_rtn(__func__, "src/common/grid.cpp", 126, "(c) == 0 || (c) == 1"
) : (void)0);
;
127 RT_AREA_POS(path, toPos, c)((path)->area[(c)][(toPos)[2]][(toPos)[1]][(toPos)[0]]) = length; /**< Store TUs for this square. */
128 RT_AREA_FROM_POS(path, toPos, c)((path)->areaFrom[(c)][(toPos)[2]][(toPos)[1]][(toPos)[0]]
)
= makeDV(dir, oz)(((dir) << 8) | ((oz) & 0x0007)); /**< Store origination information for this square. */
129
130 Vector4Set(dummy, toPos[0], toPos[1], toPos[2], c)((dummy)[0]=(toPos[0]), (dummy)[1]=(toPos[1]), (dummy)[2]=(toPos
[2]), (dummy)[3]=(c))
;
131 /** @todo add heuristic for A* algorithm */
132 PQueuePush(pqueue, dummy, length);
133}
134
135/**
136 * @brief a struct holding the relevant data to check if we can move between two adjacent cells
137 */
138typedef struct step_s {
139 const routing_t *map;
140 bool flier;
141
142 /** @todo has_ladder_climb should return true if
143 * 1) There is a ladder in the new cell in the specified direction. */
144 bool hasLadderToClimb; /**< Indicates if there is a ladder present providing ability to climb. */
145
146 /** @todo has_ladder_support should return true if
147 * 1) There is a ladder in the new cell in the specified direction or
148 * 2) There is a ladder in any direction in the cell below the new cell and no ladder in the new cell itself. */
149 bool hasLadderSupport; /**< Indicates if there is a ladder present providing support. */
150
151 actorSizeEnum_t actorSize;
152 int actorHeight; /**< The actor's height in QUANT units. */
153 int actorCrouchedHeight;
154
155} step_t;
156
157/**
158 * @brief Initialize the step_t data
159 * @param[in] step The struct describing the move
160 * @param[in] map Pointer to client or server side routing table (clMap, svMap)
161 * @param[in] actorSize Give the field size of the actor (e.g. for 2x2 units) to check linked fields as well.
162 * @param[in] crouchingState Whether the actor is currently crouching, 1 is yes, 0 is no.
163 * @param[in] dir Direction vector index (see DIRECTIONS and dvecs)
164 * @return false if dir is irrelevant or something went wrong
165 */
166static bool Grid_StepInit (step_t *step, const routing_t *map, const actorSizeEnum_t actorSize, const byte crouchingState, const int dir)
167{
168 step->map = map;
169 /** @todo flier should return true if the actor can fly. */
170 step->flier = false; /**< This can be keyed into whether an actor can fly or not to allow flying */
171 step->hasLadderToClimb = false;
172 step->hasLadderSupport = false;
173 step->actorSize = actorSize;
174 /** @note This is the actor's height in QUANT units. */
175 /** @todo actor_height is currently the fixed height of a 1x1 actor. This needs to be adjusted
176 * to the actor's actual height. */
177 step->actorHeight = ModelCeilingToQuant((float)(crouchingState ? PLAYER_CROUCHING_HEIGHT : PLAYER_STANDING_HEIGHT))(floor(((float)(crouchingState ? (5 - -24) : (20 - -24))) / 4
))
; /**< The actor's height */
178 step->actorCrouchedHeight = ModelCeilingToQuant((float)(PLAYER_CROUCHING_HEIGHT))(floor(((float)((5 - -24))) / 4));
179
180 /* Ensure that dir is in bounds. */
181 assert(dir >= 0 && dir < PATHFINDING_DIRECTIONS)(__builtin_expect(!(dir >= 0 && dir < 40), 0) ?
__assert_rtn(__func__, "src/common/grid.cpp", 181, "dir >= 0 && dir < PATHFINDING_DIRECTIONS"
) : (void)0)
;
182
183 /* IMPORTANT: only fliers can use directions higher than NON_FLYING_DIRECTIONS. */
184 if (!step->flier && dir >= FLYING_DIRECTIONS16) {
185 return false;
186 }
187
188 /* We cannot fly and crouch at the same time. This will also cause an actor to stand to fly. */
189 if (crouchingState && dir >= FLYING_DIRECTIONS16) {
190 return false;
191 }
192
193 return true;
194}
195
196
197/**
198 * @brief Calculate the cell the we end up in if moving in the give dir
199 * @param[in] step The struct describing the move
200 * @param[in] pos Current location in the map.
201 * @param[in] toPos The position we are moving to with this step.
202 * @param[in] dir Direction vector index (see DIRECTIONS and dvecs)
203 * @return false if we can't fly there
204 */
205static bool Grid_StepCalcNewPos (step_t *step, const pos3_t pos, pos3_t toPos, const int dir)
206{
207 toPos[0] = pos[0] + dvecs[dir][0]; /**< "new" x value = starting x value + difference from chosen direction */
208 toPos[1] = pos[1] + dvecs[dir][1]; /**< "new" y value = starting y value + difference from chosen direction */
209 toPos[2] = pos[2] + dvecs[dir][2]; /**< "new" z value = starting z value + difference from chosen direction */
210
211 /* Connection checks. If we cannot move in the desired direction, then bail. */
212 /* Range check of new values (all sizes) */
213 /* "comparison is always false due to limited range of data type" */
214 /* Only activate this check if PATHFINDING_WIDTH or pos3_t changes */
215/* if (toPos[0] < 0 || toPos[0] > PATHFINDING_WIDTH - actorSize
216 || toPos[1] < 0 || toPos[1] > PATHFINDING_WIDTH - actorSize
217 || toPos[2] < 0 {
218 return false;
219 } */
220 if (toPos[2] > PATHFINDING_HEIGHT8) {
221 return false;
222 }
223 return true;
224}
225
226/**
227 * @brief Checks if we can walk in the given direction
228 * First test for opening height availablilty. Then test for stepup compatibility. Last test for fall.
229 * @note Fliers use this code only when they are walking.
230 * @param[in] step The struct describing the move
231 * @param[in] path Pointer to client or server side pathing table (clPathMap, svPathMap)
232 * @param[in] pos Current location in the map.
233 * @param[in] toPos The position we are moving to with this step.
234 * @param[in] dir Direction vector index (see DIRECTIONS and dvecs)
235 * @param[in] crouchingState Whether the actor is currently crouching, 1 is yes, 0 is no.
236 * @return false if we can't fly there
237 */
238static bool Grid_StepCheckWalkingDirections (step_t *step, pathing_t *path, const pos3_t pos, pos3_t toPos, const int dir, const byte crouchingState)
239{
240 int nx, ny, nz;
241 int passageHeight;
242 const actorSizeEnum_t actorSize = step->actorSize;
243 /** @todo falling_height should be replaced with an arbitrary max falling height based on the actor. */
244 const int fallingHeight = PATHFINDING_MAX_FALL16;/**<This is the maximum height that an actor can fall. */
245 const int stepup = RT_STEPUP_POS(step->map, actorSize, pos, dir)step->map[(actorSize) - 1].stepup[(pos)[2]][(pos)[1]][(pos
)[0]][(dir)]
; /**< The stepup needed to get to/through the passage */
246 const int stepupHeight = stepup & ~(PATHFINDING_BIG_STEPDOWN0x40 | PATHFINDING_BIG_STEPUP0x80); /**< The actual stepup height without the level flags */
247 int heightChange;
248 /** @todo actor_stepup_height should be replaced with an arbitrary max stepup height based on the actor. */
249 int actorStepupHeight = PATHFINDING_MAX_STEPUP4;
250
251 /* This is the standard passage height for all units trying to move horizontally. */
252 RT_CONN_TEST_POS(step->map, actorSize, pos, dir)(__builtin_expect(!((actorSize) > 0), 0) ? __assert_rtn(__func__
, "src/common/grid.cpp", 252, "(actorSize) > ACTOR_SIZE_INVALID"
) : (void)0); (__builtin_expect(!((actorSize) <= (2)), 0) ?
__assert_rtn(__func__, "src/common/grid.cpp", 252, "(actorSize) <= ACTOR_MAX_SIZE"
) : (void)0); (__builtin_expect(!((pos)[2] < 8), 0) ? __assert_rtn
(__func__, "src/common/grid.cpp", 252, "(pos)[2] < PATHFINDING_HEIGHT"
) : (void)0); (__builtin_expect(!((dir) >= 0), 0) ? __assert_rtn
(__func__, "src/common/grid.cpp", 252, "(dir) >= 0") : (void
)0); (__builtin_expect(!((dir) < 8), 0) ? __assert_rtn(__func__
, "src/common/grid.cpp", 252, "(dir) < CORE_DIRECTIONS") :
(void)0);
;
253 passageHeight = RT_CONN_POS(step->map, actorSize, pos, dir)(int)(step->map[(actorSize) - 1].route[(pos)[2]][(pos)[1]]
[(pos)[0]][(dir)])
;
254 if (passageHeight < step->actorHeight) {
255#if 0
256/** I know this code could be streamlined, but until I understand it myself, plz leave it like it is !*/
257 int dvFlagsNew = 0;
258 if (!crouchingState /* not in std crouch mode */
259 && passageHeight >= step->actorCrouchedHeight) { /* and passage is tall enough for crouching ? */
260 /* we should try autocrouching */
261 int dvFlagsOld = getDVflags(RT_AREA_POS(path, pos, crouchingState))(((((path)->area[(crouchingState)][(pos)[2]][(pos)[1]][(pos
)[0]])) & 0x00F0) >> 4)
;
262 int toHeight = RT_CEILING_POS(step->map, actorSize, toPos)step->map[(actorSize) - 1].ceil[(toPos)[2]][(toPos)[1]][(toPos
)[0]]
- RT_FLOOR_POS(step->map, actorSize, toPos)step->map[(actorSize) - 1].floor[(toPos)[2]][(toPos)[1]][(
toPos)[0]]
;
263 int tuCr = Grid_GetTUsForDirection(dir, 1); /* 1 means crouched */
264 int newTUs = 0;
265
266 if (toHeight >= step->actorHeight) { /* can we stand in the new cell ? */
267 if ((dvFlagsOld & DV_FLAG_AUTOCROUCH0x01) /* already in auto-crouch mode ? */
268 || (dvFlagsOld & DV_FLAG_AUTOCROUCHED0x02)) {
269 dvFlagsNew |= DV_FLAG_AUTOCROUCHED0x02; /* keep that ! */
270 newTUs = tuCr + TU_CROUCH3; /* TUs for crouching plus getting up */
271 }
272 else {
273 dvFlagsNew |= DV_FLAG_AUTODIVE0x04;
274 newTUs = tuCr + 2 * TU_CROUCH3; /* TUs for crouching plus getting down and up */
275 }
276 }
277 else { /* we can't stand there */
278 if (dvFlagsOld & DV_FLAG_AUTOCROUCHED0x02) {
279 dvFlagsNew |= DV_FLAG_AUTOCROUCHED0x02; /* keep that ! */
280 newTUs = tuCr; /* TUs just for crouching */
281 }
282 else {
283 dvFlagsNew |= DV_FLAG_AUTOCROUCH0x01; /* get down ! */
284 newTUs = tuCr + TU_CROUCH3; /* TUs for crouching plus getting down */
285 }
286 }
287 }
288 else
289#endif
290 return false; /* Passage is not tall enough. */
291 }
292
293 /* If we are moving horizontally, use the stepup requirement of the floors.
294 * The new z coordinate may need to be adjusted from stepup.
295 * Also, actor_stepup_height must be at least the cell's positive stepup value to move that direction. */
296 /* If the actor cannot reach stepup, then we can't go this way. */
297 if (actorStepupHeight < stepupHeight) {
298 return false; /* Actor cannot stepup high enough. */
299 }
300
301 nx = toPos[0];
302 ny = toPos[1];
303 nz = toPos[2];
304
305 if ((stepup & PATHFINDING_BIG_STEPUP0x80) && toPos[2] < PATHFINDING_HEIGHT8 - 1) {
306 Com_DPrintf(DEBUG_PATHING0x0800, "Grid_MoveMark: Stepping up into higher cell.\n");
307 toPos[2]++;
308 /**
309 * @note If you need to know about how pathfinding works, you need to understand the
310 * following brief. It may cause nausea, but is an important concept.
311 *
312 * @brief OK, now some crazy tests:
313 * Because of the grid based nature of this game, each cell can have at most only ONE
314 * floor that can be stood upon. If an actor can walk down a slope that is in the
315 * same level, and actor should be able to walk on (and not fall into) the slope that
316 * decends a game level. BUT it is possible for an actor to be able to crawl under a
317 * floor that can be stood on, with this opening being in the same cell as the floor.
318 * SO to prevent any conflicts, we will move down a floor under the following conditions:
319 * - The STEPDOWN flag is set
320 * - The floor in the immediately adjacent cell is lower than the current floor, but not
321 * more than CELL_HEIGHT units (in QUANT units) below the current floor.
322 * - The actor's stepup value is at least the inverse stepup value. This is the stepup
323 * FROM the cell we are moving towards back into the cell we are starting in. This
324 * ensures that the actor can actually WALK BACK.
325 * If the actor does not have a high enough stepup but meets all the other requirements to
326 * descend the level, the actor will move into a fall state, provided that there is no
327 * floor in the adjacent cell.
328 *
329 * This will prevent actors from walking under a floor in the same cell in order to fall
330 * to the floor beneath. They will need to be able to step down into the cell or will
331 * not be able to use the opening.
332 */
333 } else if ((stepup & PATHFINDING_BIG_STEPDOWN0x40) && toPos[2] > 0
334 && actorStepupHeight >= (RT_STEPUP(step->map, actorSize, nx, ny, nz - 1, dir ^ 1)step->map[(actorSize) - 1].stepup[(nz - 1)][(ny)][(nx)][(dir
^ 1)]
& ~(PATHFINDING_BIG_STEPDOWN0x40 | PATHFINDING_BIG_STEPUP0x80))) {
335 toPos[2]--; /* Stepping down into lower cell. */
336 }
337
338 heightChange = RT_FLOOR_POS(step->map, actorSize, toPos)step->map[(actorSize) - 1].floor[(toPos)[2]][(toPos)[1]][(
toPos)[0]]
- RT_FLOOR_POS(step->map, actorSize, pos)step->map[(actorSize) - 1].floor[(pos)[2]][(pos)[1]][(pos)
[0]]
+ (toPos[2] - pos[2]) * CELL_HEIGHT(64 / 4);
339
340 /* If the actor tries to fall more than falling_height, then prohibit the move. */
341 if (heightChange < -fallingHeight && !step->hasLadderSupport) {
342 return false; /* Too far a drop without a ladder. */
343 }
344
345 /* If we are walking normally, we can fall if we move into a cell that does not
346 * have its STEPDOWN flag set and has a negative floor:
347 * Set heightChange to 0.
348 * The actor enters the cell.
349 * The actor will be forced to fall (dir 13) from the destination cell to the cell below. */
350 if (RT_FLOOR_POS(step->map, actorSize, toPos)step->map[(actorSize) - 1].floor[(toPos)[2]][(toPos)[1]][(
toPos)[0]]
< 0) {
351 /* We cannot fall if STEPDOWN is defined. */
352 if (stepup & PATHFINDING_BIG_STEPDOWN0x40) {
353 return false; /* There is stepdown from here. */
354 }
355 Com_DPrintf(DEBUG_PATHING0x0800, "Grid_MoveMark: Preparing for a fall. change:%i fall:%i\n", heightChange, -actorStepupHeight);
356 heightChange = 0;
Value stored to 'heightChange' is never read
357 toPos[2]--;
358 }
359 return true;
360}
361
362/**
363 * @brief Checks if we can move in the given flying direction
364 * @param[in] step The struct describing the move
365 * @param[in] pos Current location in the map.
366 * @param[in] toPos The position we are moving to with this step.
367 * @param[in] dir Direction vector index (see DIRECTIONS and dvecs)
368 * @return false if we can't fly there
369 */
370static bool Grid_StepCheckFlyingDirections (step_t *step, const pos3_t pos, const pos3_t toPos, const int dir)
371{
372 const int coreDir = dir % CORE_DIRECTIONS8; /**< The compass direction of this flying move */
373 int neededHeight;
374 int passageHeight;
375 const actorSizeEnum_t actorSize = step->actorSize;
376
377 if (toPos[2] > pos[2]) {
378 /* If the actor is moving up, check the passage at the current cell.
379 * The minimum height is the actor's height plus the distance from the current floor to the top of the cell. */
380 neededHeight = step->actorHeight + CELL_HEIGHT(64 / 4) - std::max((const signed char)0, RT_FLOOR_POS(step->map, actorSize, pos)step->map[(actorSize) - 1].floor[(pos)[2]][(pos)[1]][(pos)
[0]]
);
381 RT_CONN_TEST_POS(step->map, actorSize, pos, coreDir)(__builtin_expect(!((actorSize) > 0), 0) ? __assert_rtn(__func__
, "src/common/grid.cpp", 381, "(actorSize) > ACTOR_SIZE_INVALID"
) : (void)0); (__builtin_expect(!((actorSize) <= (2)), 0) ?
__assert_rtn(__func__, "src/common/grid.cpp", 381, "(actorSize) <= ACTOR_MAX_SIZE"
) : (void)0); (__builtin_expect(!((pos)[2] < 8), 0) ? __assert_rtn
(__func__, "src/common/grid.cpp", 381, "(pos)[2] < PATHFINDING_HEIGHT"
) : (void)0); (__builtin_expect(!((coreDir) >= 0), 0) ? __assert_rtn
(__func__, "src/common/grid.cpp", 381, "(coreDir) >= 0") :
(void)0); (__builtin_expect(!((coreDir) < 8), 0) ? __assert_rtn
(__func__, "src/common/grid.cpp", 381, "(coreDir) < CORE_DIRECTIONS"
) : (void)0);
;
382 passageHeight = RT_CONN_POS(step->map, actorSize, pos, coreDir)(int)(step->map[(actorSize) - 1].route[(pos)[2]][(pos)[1]]
[(pos)[0]][(coreDir)])
;
383 } else if (toPos[2] < pos[2]) {
384 /* If the actor is moving down, check from the destination cell back. *
385 * The minimum height is the actor's height plus the distance from the destination floor to the top of the cell. */
386 neededHeight = step->actorHeight + CELL_HEIGHT(64 / 4) - std::max((const signed char)0, RT_FLOOR_POS(step->map, actorSize, toPos)step->map[(actorSize) - 1].floor[(toPos)[2]][(toPos)[1]][(
toPos)[0]]
);
387 RT_CONN_TEST_POS(step->map, actorSize, toPos, coreDir ^ 1)(__builtin_expect(!((actorSize) > 0), 0) ? __assert_rtn(__func__
, "src/common/grid.cpp", 387, "(actorSize) > ACTOR_SIZE_INVALID"
) : (void)0); (__builtin_expect(!((actorSize) <= (2)), 0) ?
__assert_rtn(__func__, "src/common/grid.cpp", 387, "(actorSize) <= ACTOR_MAX_SIZE"
) : (void)0); (__builtin_expect(!((toPos)[2] < 8), 0) ? __assert_rtn
(__func__, "src/common/grid.cpp", 387, "(toPos)[2] < PATHFINDING_HEIGHT"
) : (void)0); (__builtin_expect(!((coreDir ^ 1) >= 0), 0) ?
__assert_rtn(__func__, "src/common/grid.cpp", 387, "(coreDir ^ 1) >= 0"
) : (void)0); (__builtin_expect(!((coreDir ^ 1) < 8), 0) ?
__assert_rtn(__func__, "src/common/grid.cpp", 387, "(coreDir ^ 1) < CORE_DIRECTIONS"
) : (void)0);
;
388 passageHeight = RT_CONN_POS(step->map, actorSize, toPos, coreDir ^ 1)(int)(step->map[(actorSize) - 1].route[(toPos)[2]][(toPos)
[1]][(toPos)[0]][(coreDir ^ 1)])
;
389 } else {
390 neededHeight = step->actorHeight;
391 RT_CONN_TEST_POS(step->map, actorSize, pos, coreDir)(__builtin_expect(!((actorSize) > 0), 0) ? __assert_rtn(__func__
, "src/common/grid.cpp", 391, "(actorSize) > ACTOR_SIZE_INVALID"
) : (void)0); (__builtin_expect(!((actorSize) <= (2)), 0) ?
__assert_rtn(__func__, "src/common/grid.cpp", 391, "(actorSize) <= ACTOR_MAX_SIZE"
) : (void)0); (__builtin_expect(!((pos)[2] < 8), 0) ? __assert_rtn
(__func__, "src/common/grid.cpp", 391, "(pos)[2] < PATHFINDING_HEIGHT"
) : (void)0); (__builtin_expect(!((coreDir) >= 0), 0) ? __assert_rtn
(__func__, "src/common/grid.cpp", 391, "(coreDir) >= 0") :
(void)0); (__builtin_expect(!((coreDir) < 8), 0) ? __assert_rtn
(__func__, "src/common/grid.cpp", 391, "(coreDir) < CORE_DIRECTIONS"
) : (void)0);
;
392 passageHeight = RT_CONN_POS(step->map, actorSize, pos, coreDir)(int)(step->map[(actorSize) - 1].route[(pos)[2]][(pos)[1]]
[(pos)[0]][(coreDir)])
;
393 }
394 if (passageHeight < neededHeight) {
395 return false;
396 }
397 return true;
398}
399
400/**
401 * @brief Checks if we can move in the given vertical direction
402 * @param[in] step The struct describing the move
403 * @param[in] pos Current location in the map.
404 * @param[in] dir Direction vector index (see DIRECTIONS and dvecs)
405 * @return false if we can't move there
406 */
407static bool Grid_StepCheckVerticalDirections (step_t *step, const pos3_t pos, const int dir)
408{
409 if (dir == DIRECTION_FALL13) {
410 if (step->flier) {
411 /* Fliers cannot fall intentionally. */
412 return false;
413 } else if (RT_FLOOR_POS(step->map, step->actorSize, pos)step->map[(step->actorSize) - 1].floor[(pos)[2]][(pos)[
1]][(pos)[0]]
>= 0) {
414 /* We cannot fall if there is a floor in this cell. */
415 return false;
416 } else if (step->hasLadderSupport) {
417 /* The actor can't fall if there is ladder support. */
418 return false;
419 }
420 } else if (dir == DIRECTION_CLIMB_UP8) {
421 if (step->flier && QuantToModel(RT_CEILING_POS(step->map, step->actorSize, pos))((step->map[(step->actorSize) - 1].ceil[(pos)[2]][(pos)
[1]][(pos)[0]]) * 4)
< UNIT_HEIGHT64 * 2 - PLAYER_HEIGHT(64 - 16)) { /* Not enough headroom to fly up. */
422 return false;
423 }
424 /* If the actor is not a flyer and tries to move up, there must be a ladder. */
425 if (dir == DIRECTION_CLIMB_UP8 && !step->hasLadderToClimb) {
426 return false;
427 }
428 } else if (dir == DIRECTION_CLIMB_DOWN9) {
429 if (step->flier) {
430 if (RT_FLOOR_POS(step->map, step->actorSize, pos)step->map[(step->actorSize) - 1].floor[(pos)[2]][(pos)[
1]][(pos)[0]]
>= 0 ) { /* Can't fly down through a floor. */
431 return false;
432 }
433 } else {
434 /* If the actor is not a flyer and tries to move down, there must be a ladder. */
435 if (!step->hasLadderToClimb) {
436 return false;
437 }
438 }
439 }
440 return true;
441}
442
443/**
444 * @param[in] map Pointer to client or server side routing table (clMap, svMap)
445 * @param[in] exclude Exclude this position from the forbidden list check
446 * @param[in] actorSize Give the field size of the actor (e.g. for 2x2 units) to check linked fields as well.
447 * @param[in,out] path Pointer to client or server side pathing table (clMap, svMap)
448 * @param[in] pos Current location in the map.
449 * @param[in] crouchingState Whether the actor is currently crouching, 1 is yes, 0 is no.
450 * @param[in] dir Direction vector index (see DIRECTIONS and dvecs)
451 * @param[in,out] pqueue Priority queue (heap) to insert the now reached tiles for reconsidering
452 * @sa Grid_CheckForbidden
453 */
454static void Grid_MoveMark (const routing_t *map, const pos3_t exclude, const actorSizeEnum_t actorSize, pathing_t *path, const pos3_t pos, byte crouchingState, const int dir, priorityQueue_t *pqueue)
455{
456 step_t step_;
457 step_t *step = &step_; /* temporary solution */
458 pos3_t toPos;
459 byte TUsSoFar, TUsForMove, TUsAfter;
460
461 if (!Grid_StepInit(step, map, actorSize, crouchingState, dir))
462 return; /* either dir is irrelevant or something worse happened */
463
464 TUsSoFar = RT_AREA_POS(path, pos, crouchingState)((path)->area[(crouchingState)][(pos)[2]][(pos)[1]][(pos)[
0]])
;
465 /* Find the number of TUs used (normally) to move in this direction. */
466 TUsForMove = Grid_GetTUsForDirection(dir, crouchingState);
467
468 /* calculate the position we would normally end up if moving in the given dir. */
469 if (!Grid_StepCalcNewPos(step, pos, toPos, dir)) {
470 return;
471 }
472 /* If there is no passageway (or rather lack of a wall) to the desired cell, then return. */
473 /* If the flier is moving up or down diagonally, then passage height will also adjust */
474 if (dir >= FLYING_DIRECTIONS16) {
475 if (!Grid_StepCheckFlyingDirections(step, pos, toPos, dir)) {
476 return;
477 }
478 } else if (dir < CORE_DIRECTIONS8) {
479 /** note that this function may modify toPos ! */
480 if (!Grid_StepCheckWalkingDirections(step, path, pos, toPos, dir, crouchingState)) {
481 return;
482 }
483 } else {
484 /* else there is no movement that uses passages. */
485 /* If we are falling, the height difference is the floor value. */
486 if (!Grid_StepCheckVerticalDirections(step, pos, dir)) {
487 return;
488 }
489 }
490
491 /* OK, at this point we are certain of a few things:
492 * There is not a wall obstructing access to the destination cell.
493 * If the actor is not a flier, the actor will not rise more than actor_stepup_height or fall more than
494 * falling_height, unless climbing.
495 *
496 * If the actor is a flier, as long as there is a passage, it can be moved through.
497 * There are no floor difference restrictions for fliers, only obstructions. */
498
499 /* nz can't move out of bounds */
500 if (toPos[2] >= PATHFINDING_HEIGHT8)
501 toPos[2] = PATHFINDING_HEIGHT8 - 1;
502
503 /* Now add the TUs needed to get to the originating cell. */
504 TUsAfter = TUsSoFar + TUsForMove;
505
506 /* Is this a better move into this cell? */
507 RT_AREA_TEST_POS(path, toPos, crouchingState)(__builtin_expect(!((toPos)[2] < 8), 0) ? __assert_rtn(__func__
, "src/common/grid.cpp", 507, "(toPos)[2] < PATHFINDING_HEIGHT"
) : (void)0); (__builtin_expect(!((crouchingState) == 0 || (crouchingState
) == 1), 0) ? __assert_rtn(__func__, "src/common/grid.cpp", 507
, "(crouchingState) == 0 || (crouchingState) == 1") : (void)0
);
;
508 if (RT_AREA_POS(path, toPos, crouchingState)((path)->area[(crouchingState)][(toPos)[2]][(toPos)[1]][(toPos
)[0]])
<= TUsAfter) {
509 return; /* This move is not optimum. */
510 }
511
512 /* Test for forbidden (by other entities) areas. */
513 if (Grid_CheckForbidden(exclude, actorSize, path, toPos[0], toPos[1], toPos[2])) {
514 return; /* That spot is occupied. */
515 }
516
517 /* Store move. */
518 if (pqueue) {
519 Grid_SetMoveData(path, toPos, crouchingState, TUsAfter, dir, pos[2], crouchingState, pqueue);
520 }
521}
522
523
524/**
525 * @brief Recalculate the pathing table for the given actor(-position)
526 * @param[in] map Pointer to client or server side routing table (clMap, svMap)
527 * @param[in] actorSize The size of thing to calc the move for (e.g. size=2 means 2x2).
528 * The plan is to have the 'origin' in 2x2 units in the bottom-left (towards the lower coordinates) corner of the 2x2 square.
529 * @param[in,out] path Pointer to client or server side pathing table (clMap, svMap)
530 * @param[in] from The position to start the calculation from.
531 * @param[in] distance The maximum TUs away from 'from' to calculate move-information for
532 * @param[in] crouchingState Whether the actor is currently crouching, 1 is yes, 0 is no.
533 * @param[in] fb_list Forbidden list (entities are standing at those points)
534 * @param[in] fb_length Length of forbidden list
535 * @sa Grid_MoveMark
536 * @sa G_MoveCalc
537 * @sa CL_ConditionalMoveCalc
538 */
539void Grid_MoveCalc (const routing_t *map, const actorSizeEnum_t actorSize, pathing_t *path, const pos3_t from, byte crouchingState, int distance, byte ** fb_list, int fb_length)
540{
541 int dir;
542 int count;
543 priorityQueue_t pqueue;
544 pos4_t epos; /**< Extended position; includes crouching state */
545 pos3_t pos;
546 /* this is the position of the current actor- so the actor can stand in the cell it is in when pathfinding */
547 pos3_t excludeFromForbiddenList;
548
549 /* reset move data */
550 OBJSET(path->area, ROUTING_NOT_REACHABLE)(memset(&(path->area), (0xFF), sizeof(path->area)));
551 OBJSET(path->areaFrom, ROUTING_NOT_REACHABLE)(memset(&(path->areaFrom), (0xFF), sizeof(path->areaFrom
)))
;
552 path->fblist = fb_list;
553 path->fblength = fb_length;
554
555 if (distance > MAX_ROUTE33 + 3) /* +3 is added to calc at least one square (diagonal) more */
556 distance = MAX_ROUTE33 + 3; /* and later show one step beyond the walkable path in red */
557
558 /* Prepare exclusion of starting-location (i.e. this should be ent-pos or le-pos) in Grid_CheckForbidden */
559 VectorCopy(from, excludeFromForbiddenList)((excludeFromForbiddenList)[0]=(from)[0],(excludeFromForbiddenList
)[1]=(from)[1],(excludeFromForbiddenList)[2]=(from)[2])
;
560
561 PQueueInitialise(&pqueue, 1024);
562 Vector4Set(epos, from[0], from[1], from[2], crouchingState)((epos)[0]=(from[0]), (epos)[1]=(from[1]), (epos)[2]=(from[2]
), (epos)[3]=(crouchingState))
;
563 PQueuePush(&pqueue, epos, 0);
564
565 /* Confirm bounds */
566 assert((from[2]) < PATHFINDING_HEIGHT)(__builtin_expect(!((from[2]) < 8), 0) ? __assert_rtn(__func__
, "src/common/grid.cpp", 566, "(from[2]) < PATHFINDING_HEIGHT"
) : (void)0)
;
567 assert(crouchingState == 0 || crouchingState == 1)(__builtin_expect(!(crouchingState == 0 || crouchingState == 1
), 0) ? __assert_rtn(__func__, "src/common/grid.cpp", 567, "crouchingState == 0 || crouchingState == 1"
) : (void)0)
; /* s.a. ACTOR_MAX_STATES */
568
569 /* set starting position to 0 TUs.*/
570 RT_AREA_POS(path, from, crouchingState)((path)->area[(crouchingState)][(from)[2]][(from)[1]][(from
)[0]])
= 0;
571
572 Com_DPrintf(DEBUG_PATHING0x0800, "Grid_MoveCalc: Start at (%i %i %i) c:%i\n", from[0], from[1], from[2], crouchingState);
573
574 count = 0;
575 while (!PQueueIsEmpty(&pqueue)((&pqueue)->currentSize == 0)) {
576 byte TUsSoFar;
577 PQueuePop(&pqueue, epos);
578 VectorCopy(epos, pos)((pos)[0]=(epos)[0],(pos)[1]=(epos)[1],(pos)[2]=(epos)[2]);
579 count++;
580
581 /* if reaching that square already took too many TUs,
582 * don't bother to reach new squares *from* there. */
583 TUsSoFar = RT_AREA_POS(path, pos, crouchingState)((path)->area[(crouchingState)][(pos)[2]][(pos)[1]][(pos)[
0]])
;
584 if (TUsSoFar >= distance || TUsSoFar >= MAX_MOVELENGTH60)
585 continue;
586
587 for (dir = 0; dir < PATHFINDING_DIRECTIONS40; dir++) {
588 /* Directions 12, 14, and 15 are currently undefined. */
589 if (dir == 12 || dir == 14 || dir == 15)
590 continue;
591 /* If this is a crouching or crouching move, forget it. */
592 if (dir == DIRECTION_STAND_UP10 || dir == DIRECTION_CROUCH11)
593 continue;
594
595 Grid_MoveMark(map, excludeFromForbiddenList, actorSize, path, pos, epos[3], dir, &pqueue);
596 }
597 }
598 /* Com_Printf("Loop: %i", count); */
599 PQueueFree(&pqueue);
600
601 Com_DPrintf(DEBUG_PATHING0x0800, "Grid_MoveCalc: Done\n\n");
602}
603
604/**
605 * @brief Caches the calculated move
606 * @param[in] path Pointer to client or server side pathing table (clPathMap, svPathMap)
607 * @sa AI_ActorThink
608 */
609void Grid_MoveStore (pathing_t *path)
610{
611 memcpy(path->areaStored, path->area, sizeof(path->areaStored));
612}
613
614
615/**
616 * @brief Return the needed TUs to walk to a given position
617 * @param[in] path Pointer to client or server side pathing table (clPathMap, svPathMap)
618 * @param[in] to Position to walk to
619 * @param[in] crouchingState Whether the actor is currently crouching, 1 is yes, 0 is no.
620 * @param[in] stored Use the stored mask (the cached move) of the routing data
621 * @return ROUTING_NOT_REACHABLE if the move isn't possible
622 * @return length of move otherwise (TUs)
623 */
624pos_t Grid_MoveLength (const pathing_t *path, const pos3_t to, byte crouchingState, bool stored)
625{
626#ifdef PARANOID
627 if (to[2] >= PATHFINDING_HEIGHT8) {
628 Com_DPrintf(DEBUG_PATHING0x0800, "Grid_MoveLength: WARNING to[2] = %i(>= HEIGHT)\n", to[2]);
629 return ROUTING_NOT_REACHABLE0xFF;
630 }
631#endif
632 /* Confirm bounds */
633 assert(to[2] < PATHFINDING_HEIGHT)(__builtin_expect(!(to[2] < 8), 0) ? __assert_rtn(__func__
, "src/common/grid.cpp", 633, "to[2] < PATHFINDING_HEIGHT"
) : (void)0)
;
634 assert(crouchingState == 0 || crouchingState == 1)(__builtin_expect(!(crouchingState == 0 || crouchingState == 1
), 0) ? __assert_rtn(__func__, "src/common/grid.cpp", 634, "crouchingState == 0 || crouchingState == 1"
) : (void)0)
; /* s.a. ACTOR_MAX_STATES */
635
636 if (!stored)
637 return RT_AREA_POS(path, to, crouchingState)((path)->area[(crouchingState)][(to)[2]][(to)[1]][(to)[0]]
)
;
638 else
639 return RT_SAREA(path, to[0], to[1], to[2], crouchingState)((path)->areaStored[(crouchingState)][(to[2])][(to[1])][(to
[0])])
;
640}
641
642
643/**
644 * @brief Get the direction to use to move to a position (used to reconstruct the path)
645 * @param[in] path Pointer to client or server side pathing table (le->PathMap, svPathMap)
646 * @param[in] toPos The desired location
647 * @param[in] crouchingState Whether the actor is currently crouching, 1 is yes, 0 is no.
648 * @return a direction vector (see dvecs and DIRECTIONS)
649 * @sa Grid_MoveCheck
650 */
651int Grid_MoveNext (const pathing_t *path, const pos3_t toPos, byte crouchingState)
652{
653 const pos_t l = RT_AREA_POS(path, toPos, crouchingState)((path)->area[(crouchingState)][(toPos)[2]][(toPos)[1]][(toPos
)[0]])
; /**< Get TUs for this square */
654
655 /* Check to see if the TUs needed to move here are greater than 0 and less then ROUTING_NOT_REACHABLE */
656 if (!l || l == ROUTING_NOT_REACHABLE0xFF) {
657 /* ROUTING_UNREACHABLE means, not possible/reachable */
658 return ROUTING_UNREACHABLE-1;
659 }
660
661 /* Return the information indicating how the actor got to this cell */
662 return RT_AREA_FROM_POS(path, toPos, crouchingState)((path)->areaFrom[(crouchingState)][(toPos)[2]][(toPos)[1]
][(toPos)[0]])
;
663}
664
665
666/**
667 * @brief Returns the height of the floor in a cell.
668 * @param[in] map Pointer to client or server side routing table (clMap, svMap)
669 * @param[in] actorSize width of the actor in cells
670 * @param[in] pos Position in the map to check the height
671 * @return The actual model height of the cell's ceiling.
672 */
673unsigned int Grid_Ceiling (const routing_t *map, const actorSizeEnum_t actorSize, const pos3_t pos)
674{
675 /* max 8 levels */
676 if (pos[2] >= PATHFINDING_HEIGHT8) {
677 Com_Printf("Grid_Height: Warning: z level is bigger than %i: %i\n",
678 (PATHFINDING_HEIGHT8 - 1), pos[2]);
679 }
680 return QuantToModel(RT_CEILING(map, actorSize, pos[0], pos[1], pos[2] & 7))((map[(actorSize) - 1].ceil[(pos[2] & 7)][(pos[1])][(pos[
0])]) * 4)
;
681}
682
683
684/**
685 * @brief Returns the height of the floor in a cell.
686 * @param[in] map Pointer to client or server side routing table (clMap, svMap)
687 * @param[in] actorSize width of the actor in cells
688 * @param[in] pos Position in the map to check the height
689 * @return The actual model height of the cell's ceiling.
690 */
691int Grid_Height (const routing_t *map, const actorSizeEnum_t actorSize, const pos3_t pos)
692{
693 /* max 8 levels */
694 if (pos[2] >= PATHFINDING_HEIGHT8) {
695 Com_Printf("Grid_Height: Warning: z level is bigger than %i: %i\n",
696 (PATHFINDING_HEIGHT8 - 1), pos[2]);
697 }
698 return QuantToModel(RT_CEILING(map, actorSize, pos[0], pos[1], pos[2] & (PATHFINDING_HEIGHT - 1))((map[(actorSize) - 1].ceil[(pos[2] & (8 - 1))][(pos[1])]
[(pos[0])] - map[(actorSize) - 1].floor[(pos[2] & (8 - 1)
)][(pos[1])][(pos[0])]) * 4)
699 - RT_FLOOR(map, actorSize, pos[0], pos[1], pos[2] & (PATHFINDING_HEIGHT - 1)))((map[(actorSize) - 1].ceil[(pos[2] & (8 - 1))][(pos[1])]
[(pos[0])] - map[(actorSize) - 1].floor[(pos[2] & (8 - 1)
)][(pos[1])][(pos[0])]) * 4)
;
700}
701
702
703/**
704 * @brief Returns the height of the floor in a cell.
705 * @param[in] map Pointer to client or server side routing table (clMap, svMap)
706 * @param[in] actorSize width of the actor in cells
707 * @param[in] pos Position in the map to check the height
708 * @return The actual model height of the cell's floor.
709 */
710int Grid_Floor (const routing_t *map, const actorSizeEnum_t actorSize, const pos3_t pos)
711{
712 /* max 8 levels */
713 if (pos[2] >= PATHFINDING_HEIGHT8) {
714 Com_Printf("Grid_Floor: Warning: z level is bigger than %i: %i\n",
715 (PATHFINDING_HEIGHT8 - 1), pos[2]);
716 }
717 return QuantToModel(RT_FLOOR(map, actorSize, pos[0], pos[1], pos[2] & (PATHFINDING_HEIGHT - 1)))((map[(actorSize) - 1].floor[(pos[2] & (8 - 1))][(pos[1])
][(pos[0])]) * 4)
;
718}
719
720
721/**
722 * @brief Returns the maximum height of an obstruction that an actor can travel over.
723 * @param[in] map Pointer to client or server side routing table (clMap, svMap)
724 * @param[in] actorSize width of the actor in cells
725 * @param[in] pos Position in the map to check the height
726 * @param[in] dir the direction in which we are moving
727 * @return The actual model height increase needed to move into an adjacent cell.
728 */
729pos_t Grid_StepUp (const routing_t *map, const actorSizeEnum_t actorSize, const pos3_t pos, const int dir)
730{
731 /* max 8 levels */
732 if (pos[2] >= PATHFINDING_HEIGHT8) {
733 Com_Printf("Grid_StepUp: Warning: z level is bigger than 7: %i\n", pos[2]);
734 }
735 return QuantToModel(RT_STEPUP(map, actorSize, pos[0], pos[1], pos[2] & (PATHFINDING_HEIGHT - 1), dir))((map[(actorSize) - 1].stepup[(pos[2] & (8 - 1))][(pos[1]
)][(pos[0])][(dir)]) * 4)
;
736}
737
738
739/**
740 * @brief Returns the amounts of TUs that are needed to perform one step into the given direction.
741 * @param[in] dir the direction in which we are moving
742 * @param[in] crouched The crouching state of the actor
743 * @return The TUs needed to move there.
744 */
745int Grid_GetTUsForDirection (const int dir, const int crouched)
746{
747 assert(dir >= 0 && dir < PATHFINDING_DIRECTIONS)(__builtin_expect(!(dir >= 0 && dir < 40), 0) ?
__assert_rtn(__func__, "src/common/grid.cpp", 747, "dir >= 0 && dir < PATHFINDING_DIRECTIONS"
) : (void)0)
;
748 if (crouched && dir < CORE_DIRECTIONS8)
749 return TUsUsed[dir] * TU_CROUCH_MOVING_FACTOR1.5;
750 else
751 return TUsUsed[dir];
752}
753
754
755/**
756 * @brief Returns non-zero if the cell is filled (solid) and cannot be entered.
757 * @param[in] map Pointer to client or server side routing table (clMap, svMap)
758 * @param[in] actorSize width of the actor in cells
759 * @param[in] pos Position in the map to check for filling
760 * @return 0 if the cell is vacant (of the world model), non-zero otherwise.
761 */
762int Grid_Filled (const routing_t *map, const actorSizeEnum_t actorSize, const pos3_t pos)
763{
764 /* max 8 levels */
765 assert(pos[2] < PATHFINDING_HEIGHT)(__builtin_expect(!(pos[2] < 8), 0) ? __assert_rtn(__func__
, "src/common/grid.cpp", 765, "pos[2] < PATHFINDING_HEIGHT"
) : (void)0)
;
766 return RT_FILLED(map, pos[0], pos[1], pos[2], actorSize)(map[(pos[0]) - 1].ceil[(actorSize)][(pos[2])][(pos[1])] - map
[(pos[0]) - 1].floor[(actorSize)][(pos[2])][(pos[1])] < 6)
;
767}
768
769
770/**
771 * @brief Calculated the new height level when something falls down from a certain position.
772 * @param[in] map Pointer to client or server side routing table (clMap, svMap)
773 * @param[in] pos Position in the map to start the fall (starting height is the z-value in this position)
774 * @param[in] actorSize Give the field size of the actor (e.g. for 2x2 units) to check linked fields as well.
775 * @return New z (height) value.
776 * @return 0xFF if an error occurred.
777 */
778pos_t Grid_Fall (const routing_t *map, const actorSizeEnum_t actorSize, const pos3_t pos)
779{
780 int z = pos[2], base, diff;
781 bool flier = false; /** @todo if an actor can fly, then set this to true. */
782
783 /* Is z off the map? */
784 if (z >= PATHFINDING_HEIGHT8) {
785 Com_DPrintf(DEBUG_PATHING0x0800, "Grid_Fall: z (height) out of bounds): z=%i max=%i\n", z, PATHFINDING_HEIGHT8);
786 return 0xFF;
787 }
788
789 /* If we can fly, then obviously we won't fall. */
790 if (flier)
791 return z;
792
793 /* Easy math- get the floor, integer divide by CELL_HEIGHT, add to z.
794 * If z < 0, we are going down.
795 * If z >= CELL_HEIGHT, we are going up.
796 * If 0 <= z <= CELL_HEIGHT, then z / 16 = 0, no change. */
797 base = RT_FLOOR(map, actorSize, pos[0], pos[1], z)map[(actorSize) - 1].floor[(z)][(pos[1])][(pos[0])];
798 /* Hack to deal with negative numbers- otherwise rounds toward 0 instead of down. */
799 diff = base < 0 ? (base - (CELL_HEIGHT(64 / 4) - 1)) / CELL_HEIGHT(64 / 4) : base / CELL_HEIGHT(64 / 4);
800 z += diff;
801 /* The tracing code will set locations without a floor to -1. Compensate for that. */
802 if (z < 0)
803 z = 0;
804 else if (z >= PATHFINDING_HEIGHT8)
805 z = PATHFINDING_HEIGHT8 - 1;
806 return z;
807}
808
809/**
810 * @brief Converts a grid position to world coordinates
811 * @sa Grid_Height
812 * @param[in] map The routing map
813 * @param[in] actorSize width of the actor in cells
814 * @param[in] pos The grid position
815 * @param[out] vec The world vector
816 */
817void Grid_PosToVec (const routing_t *map, const actorSizeEnum_t actorSize, const pos3_t pos, vec3_t vec)
818{
819 SizedPosToVec(pos, actorSize, vec){ (__builtin_expect(!(actorSize > 0), 0) ? __assert_rtn(__func__
, "src/common/grid.cpp", 819, "actorSize > ACTOR_SIZE_INVALID"
) : (void)0); (__builtin_expect(!(actorSize <= (2)), 0) ? __assert_rtn
(__func__, "src/common/grid.cpp", 819, "actorSize <= ACTOR_MAX_SIZE"
) : (void)0); vec[0] = ((int)pos[0] - 128) * 32 + (32 * actorSize
) / 2; vec[1] = ((int)pos[1] - 128) * 32 + (32 * actorSize) /
2; vec[2] = (int)pos[2] * 64 + 64 / 2; }
;
820#ifdef PARANOID
821 if (pos[2] >= PATHFINDING_HEIGHT8)
822 Com_Printf("Grid_PosToVec: Warning - z level bigger than 7 (%i - source: %.02f)\n", pos[2], vec[2]);
823#endif
824 /* Clamp the floor value between 0 and UNIT_HEIGHT */
825 const int gridFloor = Grid_Floor(map, actorSize, pos);
826 vec[2] += std::max(0, std::min(UNIT_HEIGHT64, gridFloor));
827}
828
829
830/**
831 * @brief This function recalculates the routing in and around the box bounded by min and max.
832 * @sa CMod_LoadRouting
833 * @sa Grid_RecalcRouting
834 * @param[in] mapTiles List of tiles the current (RMA-)map is composed of
835 * @param[in] map The routing map (either server or client map)
836 * @param[in] min The lower extents of the box to recalc routing for
837 * @param[in] max The upper extents of the box to recalc routing for
838 * @param[in] list The local models list (a local model has a name starting with * followed by the model number)
839 */
840void Grid_RecalcBoxRouting (mapTiles_t *mapTiles, routing_t *map, const pos3_t min, const pos3_t max, const char **list)
841{
842 int x, y, z, actorSize, dir;
843
844 Com_DPrintf(DEBUG_PATHING0x0800, "rerouting (%i %i %i) (%i %i %i)\n",
845 (int)min[0], (int)min[1], (int)min[2],
846 (int)max[0], (int)max[1], (int)max[2]);
847
848 /* check unit heights */
849 for (actorSize = 1; actorSize <= ACTOR_MAX_SIZE(2); actorSize++) {
850 const int maxY = max[1] + actorSize;
851 const int maxX = max[0] + actorSize;
852 /* Offset the initial X and Y to compensate for larger actors when needed. */
853 for (y = std::max(min[1] - actorSize + 1, 0); y < maxY; y++) {
854 for (x = std::max(min[0] - actorSize + 1, 0); x < maxX; x++) {
855 /** @note RT_CheckCell goes from top (7) to bottom (0) */
856 for (z = max[2]; z >= 0; z--) {
857 const int newZ = RT_CheckCell(mapTiles, map, actorSize, x, y, z, list);
858 assert(newZ <= z)(__builtin_expect(!(newZ <= z), 0) ? __assert_rtn(__func__
, "src/common/grid.cpp", 858, "newZ <= z") : (void)0)
;
859 z = newZ;
860 }
861 }
862 }
863 }
864
865 /* check connections */
866 for (actorSize = 1; actorSize <= ACTOR_MAX_SIZE(2); actorSize++) {
867 const int minX = std::max(min[0] - actorSize, 0);
868 const int minY = std::max(min[1] - actorSize, 0);
869 const int maxX = std::min(max[0] + actorSize, PATHFINDING_WIDTH((4096 / 32) * 2) - 1);
870 const int maxY = std::min(max[1] + actorSize, PATHFINDING_WIDTH((4096 / 32) * 2) - 1);
871 /* Offset the initial X and Y to compensate for larger actors when needed.
872 * Also sweep further out to catch the walls back into our box. */
873 for (y = minY; y <= maxY; y++) {
874 for (x = minX; x <= maxX; x++) {
875 for (dir = 0; dir < CORE_DIRECTIONS8; dir++) {
876 /** @note The new version of RT_UpdateConnectionColumn can work bidirectional, so we can
877 * trace every other dir, unless we are on the edge. */
878#if RT_IS_BIDIRECTIONAL0 == 1
879 if ((dir & 1) && x != minX && x != maxX && y != minY && y != maxY)
880 continue;
881#endif
882 /* for places outside the model box, skip dirs that can not be affected by the model */
883 if (x > max[0] && dir != 1 && dir != 5 && dir != 6)
884 continue;
885 if (y > max[1] && dir != 3 && dir != 5 && dir != 7)
886 continue;
887 if (actorSize == ACTOR_SIZE_NORMAL1) {
888 if (x < min[0] && dir != 0 && dir != 4 && dir != 7)
889 continue;
890 if (y < min[1] && dir != 2 && dir != 4 && dir != 6)
891 continue;
892 } else {
893 /* the position of 2x2 actors is their lower left cell */
894 if (x < min[0] - 1 && dir != 0 && dir != 4 && dir != 7)
895 continue;
896 if (y < min[1] - 1 && dir != 2 && dir != 4 && dir != 6)
897 continue;
898 }
899 RT_UpdateConnectionColumn(mapTiles, map, actorSize, x, y, dir, list);
900 }
901 }
902 }
903 }
904}
905
906
907/**
908 * @brief This function recalculates the routing surrounding the entity name.
909 * @sa CM_InlineModel
910 * @sa CM_CheckUnit
911 * @sa CM_UpdateConnection
912 * @sa CMod_LoadSubmodels
913 * @sa Grid_RecalcBoxRouting
914 * @param[in] mapTiles List of tiles the current (RMA-)map is composed of
915 * @param[in] map The routing map (either server or client map)
916 * @param[in] name Name of the inline model to compute the mins/maxs for
917 * @param[in] list The local models list (a local model has a name starting with * followed by the model number)
918 */
919void Grid_RecalcRouting (mapTiles_t *mapTiles, routing_t *map, const char *name, const char **list)
920{
921 const cBspModel_t *model;
922 pos3_t min, max;
923 unsigned int i;
924 double start, end;
925
926 start = time(NULL__null);
927
928 /* get inline model, if it is one */
929 if (*name != '*') {
930 Com_Printf("Called Grid_RecalcRouting with no inline model\n");
931 return;
932 }
933 model = CM_InlineModel(mapTiles, name);
934 if (!model) {
935 Com_Printf("Called Grid_RecalcRouting with invalid inline model name '%s'\n", name);
936 return;
937 }
938
939 Com_DPrintf(DEBUG_PATHING0x0800, "Model:%s origin(%f,%f,%f) angles(%f,%f,%f) mins(%f,%f,%f) maxs(%f,%f,%f)\n", name,
940 model->origin[0], model->origin[1], model->origin[2],
941 model->angles[0], model->angles[1], model->angles[2],
942 model->mins[0], model->mins[1], model->mins[2],
943 model->maxs[0], model->maxs[1], model->maxs[2]);
944
945 /* get the target model's dimensions */
946 if (VectorNotEmpty(model->angles)(!(((fabs(((((model->angles)))[0])-((vec3_origin)[0]))<
0.0000000001)?(fabs(((((model->angles)))[1])-((vec3_origin
)[1]))<0.0000000001)?(fabs(((((model->angles)))[2])-((vec3_origin
)[2]))<0.0000000001)?1:0:0:0)))
) {
947 vec3_t minVec, maxVec;
948 vec3_t centerVec, halfVec, newCenterVec;
949 vec3_t m[3];
950
951 /* Find the center of the extents. */
952 VectorCenterFromMinsMaxs(model->mins, model->maxs, centerVec);
953
954 /* Find the half height and half width of the extents. */
955 VectorSubtract(model->maxs, centerVec, halfVec)((halfVec)[0]=(model->maxs)[0]-(centerVec)[0],(halfVec)[1]
=(model->maxs)[1]-(centerVec)[1],(halfVec)[2]=(model->maxs
)[2]-(centerVec)[2])
;
956
957 /* Rotate the center about the origin. */
958 VectorCreateRotationMatrix(model->angles, m);
959 VectorRotate(m, centerVec, newCenterVec);
960
961 /* Set minVec and maxVec to bound around newCenterVec at halfVec size. */
962 VectorSubtract(newCenterVec, halfVec, minVec)((minVec)[0]=(newCenterVec)[0]-(halfVec)[0],(minVec)[1]=(newCenterVec
)[1]-(halfVec)[1],(minVec)[2]=(newCenterVec)[2]-(halfVec)[2])
;
963 VectorAdd(newCenterVec, halfVec, maxVec)((maxVec)[0]=(newCenterVec)[0]+(halfVec)[0],(maxVec)[1]=(newCenterVec
)[1]+(halfVec)[1],(maxVec)[2]=(newCenterVec)[2]+(halfVec)[2])
;
964
965 /* Now offset by origin then convert to position (Doors do not have 0 origins) */
966 VectorAdd(minVec, model->origin, minVec)((minVec)[0]=(minVec)[0]+(model->origin)[0],(minVec)[1]=(minVec
)[1]+(model->origin)[1],(minVec)[2]=(minVec)[2]+(model->
origin)[2])
;
967 VecToPos(minVec, min)( (min)[0] = ((int)(minVec)[0] + 4096) / 32, (min)[1] = ((int
)(minVec)[1] + 4096) / 32, (min)[2] = std::min((8 - 1), ((int
)(minVec)[2] / 64)) )
;
968 VectorAdd(maxVec, model->origin, maxVec)((maxVec)[0]=(maxVec)[0]+(model->origin)[0],(maxVec)[1]=(maxVec
)[1]+(model->origin)[1],(maxVec)[2]=(maxVec)[2]+(model->
origin)[2])
;
969 VecToPos(maxVec, max)( (max)[0] = ((int)(maxVec)[0] + 4096) / 32, (max)[1] = ((int
)(maxVec)[1] + 4096) / 32, (max)[2] = std::min((8 - 1), ((int
)(maxVec)[2] / 64)) )
;
970 } else { /* normal */
971 vec3_t temp;
972 /* Now offset by origin then convert to position (Doors do not have 0 origins) */
973 VectorAdd(model->mins, model->origin, temp)((temp)[0]=(model->mins)[0]+(model->origin)[0],(temp)[1
]=(model->mins)[1]+(model->origin)[1],(temp)[2]=(model->
mins)[2]+(model->origin)[2])
;
974 VecToPos(temp, min)( (min)[0] = ((int)(temp)[0] + 4096) / 32, (min)[1] = ((int)(
temp)[1] + 4096) / 32, (min)[2] = std::min((8 - 1), ((int)(temp
)[2] / 64)) )
;
975 VectorAdd(model->maxs, model->origin, temp)((temp)[0]=(model->maxs)[0]+(model->origin)[0],(temp)[1
]=(model->maxs)[1]+(model->origin)[1],(temp)[2]=(model->
maxs)[2]+(model->origin)[2])
;
976 VecToPos(temp, max)( (max)[0] = ((int)(temp)[0] + 4096) / 32, (max)[1] = ((int)(
temp)[1] + 4096) / 32, (max)[2] = std::min((8 - 1), ((int)(temp
)[2] / 64)) )
;
977 }
978
979 /* fit min/max into the world size */
980 max[0] = std::min(max[0], (pos_t)(PATHFINDING_WIDTH((4096 / 32) * 2) - 1));
981 max[1] = std::min(max[1], (pos_t)(PATHFINDING_WIDTH((4096 / 32) * 2) - 1));
982 max[2] = std::min(max[2], (pos_t)(PATHFINDING_HEIGHT8 - 1));
983 for (i = 0; i < 3; i++)
984 min[i] = std::max(min[i], (pos_t)0);
985
986 /* We now have the dimensions, call the generic rerouting function. */
987 Grid_RecalcBoxRouting(mapTiles, map, min, max, list);
988
989 end = time(NULL__null);
990 Com_DPrintf(DEBUG_ROUTING0x1000, "Retracing for model %s between (%i, %i, %i) and (%i, %i %i) in %5.1fs\n",
991 name, min[0], min[1], min[2], max[0], max[1], max[2], end - start);
992}