File: | common/grid.cpp |
Location: | line 356, column 3 |
Description: | Value stored to 'heightChange' is never read |
1 | /** |
2 | * @file |
3 | * @brief Grid oriented movement and scanning |
4 | */ |
5 | |
6 | /* |
7 | Copyright (C) 1997-2001 Id Software, Inc. |
8 | |
9 | This program is free software; you can redistribute it and/or |
10 | modify it under the terms of the GNU General Public License |
11 | as published by the Free Software Foundation; either version 2 |
12 | of the License, or (at your option) any later version. |
13 | |
14 | This program is distributed in the hope that it will be useful, |
15 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
16 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. |
17 | |
18 | See the GNU General Public License for more details. |
19 | |
20 | You should have received a copy of the GNU General Public License |
21 | along with this program; if not, write to the Free Software |
22 | Foundation, 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. */ |
33 | static 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 | }; |
75 | CASSERT(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 | */ |
91 | static 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 | |
122 | static 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 | */ |
138 | typedef 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 | */ |
166 | static 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 | */ |
205 | static 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 | */ |
238 | static 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 | */ |
370 | static 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 | */ |
407 | static 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 | */ |
454 | static 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 | */ |
539 | void 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 | */ |
609 | void 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 | */ |
624 | pos_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 | */ |
651 | int 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 | */ |
673 | unsigned 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 | */ |
691 | int 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 | */ |
710 | int 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 | */ |
729 | pos_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 | */ |
745 | int 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 | */ |
762 | int 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 | */ |
778 | pos_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 | */ |
817 | void 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 | */ |
840 | void 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 | */ |
919 | void 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 | } |