102 Dalmatians: Puppies to the Rescue
Decompilation Source Reference | GitLab repository
Loading...
Searching...
No Matches
commands.c
Go to the documentation of this file.
1/* Recovered game implementation; original addresses identify provenance. */
16#include "pcdogs/entity/types.h"
17#include "pcdogs/game/types.h"
19#include "pcdogs/math/types.h"
25#include "pcdogs/scene/types.h"
27#include <math.h>
28#include <stdarg.h>
29#include <string.h>
30
31// Original pcdogs.exe: no direct counterpart (decomp helper)
32// Accumulates three signed products modulo 64 bits and returns the low 32 bits after shifting the sum right by 12.
33static int32_t Math_DotProduct3Q12(int32_t ax, int32_t ay, int32_t az, int32_t bx, int32_t by, int32_t bz)
34{
35 uint64_t sum = (uint64_t)((int64_t)ax * bx) + (uint64_t)((int64_t)ay * by) + (uint64_t)((int64_t)az * bz);
36
37 return (int32_t)(uint32_t)(sum >> MATH_Q12_SHIFT);
38}
39
40// Original pcdogs.exe: 0x403d10
41// Appends a command with two selectors, speed, and a copied position to the staging buffer. Callers must keep the unchecked command count below 100; selector enum meanings remain unconfirmed.
42void Navigation_AddCommand(uint8_t command_type, int16_t target_selector_a, int16_t target_selector_b, int32_t speed, struct Math_Vec3I32 const *position)
43{
44 struct EntityNavigationWorkListBuffer *command_type_buffer =
46
47 // The next buffer swap resets the count; callers must leave room in the 100-entry array.
48 command_type_buffer->nav_commands[command_type_buffer->nav_command_count].command_type =
49 (uint32_t)command_type;
50
51 struct EntityNavigationWorkListBuffer *first_selector_buffer =
53
54 // The first selector is copied unchanged; its enum meaning remains unconfirmed.
55 first_selector_buffer->nav_commands[first_selector_buffer->nav_command_count].target_selector_a =
56 target_selector_a;
57
58 struct EntityNavigationWorkListBuffer *second_selector_buffer =
60
61 second_selector_buffer->nav_commands[second_selector_buffer->nav_command_count].target_selector_b =
62 target_selector_b;
63
64 struct EntityNavigationWorkListBuffer *speed_buffer =
66
67 speed_buffer->nav_commands[speed_buffer->nav_command_count].speed = speed;
68
69 struct EntityNavigationWorkListBuffer *position_buffer =
71 int32_t command_index = position_buffer->nav_command_count;
72
73 position_buffer->nav_commands[command_index].pos.x =
74 position->x;
75 position_buffer->nav_commands[command_index].pos.y =
76 position->y;
77 position_buffer->nav_commands[command_index].pos.z =
78 position->z;
79
80 struct EntityNavigationWorkListBuffer *count_buffer =
82
83 // Increment queue index (NavigationCommand entries are 0x18=24 bytes)
84 count_buffer->nav_command_count += 1;
85}
86
87// Original pcdogs.exe: 0x403da0
88// Queues a team-derived damage command and determines whether a reaction is allowed, extending forced animation for airborne targets. The command remains queued when later entity or team checks return false.
89char Navigation_QueueDamageResponse(struct Actor_State *actor, struct Component_Instance *damage_component)
90{
91 // Get owner actor from component for team-based pathfinding restrictions
92 struct Actor_State *damage_owner = Component_GetOwnerActor((struct Actor_State *)(damage_component));
93 int16_t target_selector_a;
94
95 if (!damage_owner || !(damage_owner->behavior_flags & ACTOR_BEHAVIOR_GROUND_TRACKING))
96 target_selector_a = NAVIGATION_COMMAND_DEFAULT_SELECTOR;
97 else
98 target_selector_a = ((struct Actor_MovementRecordView *)damage_owner->record_ptr)->entity_index + 1;
99
100 int32_t owner_entity_index = (int32_t)((struct Player_ControllerRecordView *)actor->record_ptr)->owner_entity_index;
101 struct Entity *target_entity =
102 &pkg_resource_current_level_data->entity_array[owner_entity_index];
103 // Team ID used for collision avoidance bitmask check
104 int32_t damage_team = Component_GetTeamID((struct Actor_State *)(damage_component));
105
106 if (damage_team < 0)
107 {
108 return 0;
109 }
110
111 uint8_t command_type = 0xff - (uint8_t)damage_team;
112
113 // These later rejection checks do not undo the queued command.
114 Navigation_AddCommand(command_type, target_selector_a, (uint16_t)owner_entity_index + 1,
116
117 if (target_entity->flags & ENTITY_FLAG_DAMAGE_REACTION_DISABLED || target_entity->team_bitmask[(damage_team - 1) >> 3] & (char)(1 << ((damage_team - 1) & 7)))
118 {
119 return 0;
120 }
121
122 if (Component_IsAirborneTarget((struct Actor_State *)(damage_component)))
123
125
126 return 1;
127}
128
129// Original pcdogs.exe: 0x439bc0
130// Averages the three or four indexed collision vertices, scales their coordinates, and applies the node transform and origin to produce a world-space center.
131void Nav_CalculatePolygonCenter(struct Collision_Node *node, struct Collision_Polygon *polygon, struct Math_Vec3I32 *out_center)
132{
133 int32_t x = 0, y = 0, z = 0;
134 int count = (polygon->flags & COLLISION_POLYGON_TRIANGLE) ? 3 : 4;
135
136 for (int i = 0; i < count; ++i)
137 {
138 const struct Collision_Vertex *vertex = &node->vertices[polygon->vertex_idx[i]];
139
140 x += vertex->pos.x;
141 y += vertex->pos.y;
142 z += vertex->pos.z;
143 }
144
145 x = (x * 64) / count;
146 y = (y * 64) / count;
147 z = (z * 64) / count;
148
149 const struct Math_Matrix3x3I16 *transform = &node->transform_matrix;
150
151 out_center->x = node->origin.x + Math_DotProduct3Q12(transform->m00, transform->m01, transform->m02, x, y, z);
152 out_center->y = node->origin.y + Math_DotProduct3Q12(transform->m10, transform->m11, transform->m12, x, y, z);
153 out_center->z = node->origin.z + Math_DotProduct3Q12(transform->m20, transform->m21, transform->m22, x, y, z);
154}
155
156// Expands dynamic goals and static neighbors into the ordered open set, updating costs, packed parent links, and path depth while testing direct shortcuts. Assumes valid neighbor ordering and indices, an extra goal node, usable projection divisors, and successful open-set allocation on paths that dereference new entries.
157void Nav_RelaxPathEdges(struct Tree_Map *open_set, struct Nav_Network *nav_network,
158 struct Nav_OpenSetEntry *current_state, int32_t skip_dynamic_targets,
159 int32_t initial_shortcut_x, int32_t initial_shortcut_z)
160{
161 struct Math_Vec3I32 shortcut_delta = {initial_shortcut_x, 0, initial_shortcut_z};
162 struct Nav_OpenSetEntry *current_open_entry = current_state;
163 int32_t neighbor_count;
164
165 // Edge list iteration: bits 0-4 = edge index, bits 5-15 = dest node
166 //
167 // Iterate through edge list for current node
168 // Read edge count from NavNode at offset +0x0E
169 neighbor_count = (uint16_t)nav_network->nodes[(int32_t)current_open_entry->node_id].neighbor_count;
170
171 if (!neighbor_count)
172 return;
173
174 int32_t neighbor_index = neighbor_count - 1;
175 int32_t saved_neighbor_index = neighbor_index;
176
177 if (neighbor_count - 1 < 0)
178 return;
179
180 for (; neighbor_index >= 0; neighbor_index -= 1, saved_neighbor_index = neighbor_index, current_open_entry = current_state)
181 {
182 int32_t packed_neighbor;
183 struct Nav_Node *current_nav_node =
184 &nav_network->nodes[(int32_t)current_open_entry->node_id];
185
186 packed_neighbor = (uint16_t)current_nav_node->neighbor_list[neighbor_index].packed_id;
187
188 uint32_t destination_id = packed_neighbor >> NAVIGATION_LINK_NODE_SHIFT; // node_index = packed_id >> 5; chain_link = packed_id & 0x1F
189 int16_t goal_destination_id = (uint16_t)destination_id;
190
191 if (destination_id < NAVIGATION_ENTITY_GOAL_FIRST)
192 break;
193
194 struct Math_Vec3I32 *goal_position;
195 struct Math_Vec3I32 *goal_position_alias;
196
198 {
199 struct Powerup_Entry *powerup = &pkg_resource_current_level_data->powerup_list[destination_id - NAVIGATION_POWERUP_GOAL_FIRST];
200
202 continue;
203
204 char powerup_type = powerup->powerup_type;
205
207 continue;
208
209 goal_position = (struct Math_Vec3I32 *)&powerup->pos;
210 goal_position_alias = (struct Math_Vec3I32 *)&powerup->pos;
211 }
212 else
213 {
214 struct Entity *entity_array = pkg_resource_current_level_data->entity_array;
215
217 continue;
218
219 goal_position_alias = &entity_array[destination_id - NAVIGATION_ENTITY_GOAL_FIRST].bonus_respawn_pos;
220 goal_position = goal_position_alias;
221 }
222
223 struct Nav_NeighborEntry *neighbor_list = current_nav_node->neighbor_list;
224 int32_t edge_cost = (uint16_t)(neighbor_list[neighbor_index].cost);
225 int32_t projection_z = current_nav_node->pos.z;
226 int32_t projection_x = current_nav_node->pos.x;
227 // Calculate g-cost = parent cost + edge distance (bytes 2-3 of edge)
228 uint32_t goal_cost = edge_cost + current_open_entry->cost;
229 struct Math_Vec3I32 goal_projection_point;
230
231 goal_projection_point.x = projection_x;
232 goal_projection_point.y = current_nav_node->pos.y;
233
234 uint8_t link_bits = neighbor_list[saved_neighbor_index].packed_id;
235
236 goal_projection_point.z = projection_z;
237
238 int32_t projection_edge_selector = link_bits & NAVIGATION_LINK_EDGE_MASK;
239 uint32_t projection_neighbor_or_sentinel = projection_edge_selector - 1;
240 struct Math_Vec3I32 projection_delta;
241
242 if (projection_edge_selector - 1 >= 0)
243 {
244 int32_t packed_projection_neighbor = (uint16_t)(neighbor_list[projection_edge_selector - 1].packed_id);
245
246 shortcut_delta.x = projection_x - goal_position_alias->x;
247 shortcut_delta.y = goal_projection_point.y - goal_position_alias->y;
248
249 uint32_t projection_neighbor_id = packed_projection_neighbor >> NAVIGATION_LINK_NODE_SHIFT;
250
251 projection_neighbor_or_sentinel = projection_neighbor_id;
252 shortcut_delta.z = projection_z - goal_position_alias->z;
253
254 struct Nav_Node *projection_neighbor = &nav_network->nodes[projection_neighbor_id];
255 int32_t neighbor_position_x = projection_neighbor->pos.x;
256
257 projection_delta.x = neighbor_position_x;
258 projection_delta.y = projection_neighbor->pos.y;
259 projection_delta.z = projection_neighbor->pos.z;
260
261 int64_t start_projection_cross_x_wide = (int64_t)(neighbor_position_x - projection_x) * shortcut_delta.x;
262 int64_t start_projection_cross_z_wide = (int64_t)(projection_z - projection_delta.z) * shortcut_delta.z;
263 int32_t projection_cross_numerator =
264 ((uint32_t)((uint64_t)start_projection_cross_x_wide >> MATH_Q12_SHIFT)) - ((uint32_t)((uint64_t)start_projection_cross_z_wide >> MATH_Q12_SHIFT));
265 int32_t projection_neighbor_x = projection_delta.x;
266 int64_t end_projection_cross_x_wide = (int64_t)(projection_neighbor_x - projection_x) * (projection_neighbor_x - goal_position_alias->x);
267 int32_t projection_neighbor_z = projection_delta.z;
268 int64_t end_projection_cross_z_wide = (int64_t)(projection_z - projection_neighbor_z) * (projection_neighbor_z - goal_position_alias->z);
269 int32_t projection_fraction_q12 = ((int64_t)projection_cross_numerator * MATH_Q12_ONE) / (int32_t)(((uint32_t)((uint64_t)end_projection_cross_z_wide >> MATH_Q12_SHIFT)) - ((uint32_t)((uint64_t)end_projection_cross_x_wide >> MATH_Q12_SHIFT)) + (uint32_t)projection_cross_numerator);
270
271 projection_delta = (struct Math_Vec3I32){
272 .x = projection_delta.x - projection_x,
273 .y = projection_delta.y - goal_projection_point.y,
274 .z = projection_delta.z - projection_z};
275
276 int64_t projection_x_scaled_wide = (int64_t)projection_fraction_q12 * projection_delta.x;
277
278 projection_delta.x = (uint32_t)((uint64_t)projection_x_scaled_wide >> MATH_Q12_SHIFT);
279
280 int64_t projection_y_scaled_wide = (int64_t)projection_fraction_q12 * projection_delta.y;
281
282 projection_delta.y = (uint32_t)((uint64_t)projection_y_scaled_wide >> MATH_Q12_SHIFT);
283
284 int64_t projection_z_scaled_wide = (int64_t)projection_fraction_q12 * projection_delta.z;
285 int32_t projected_offset_z = (uint32_t)((uint64_t)projection_z_scaled_wide >> MATH_Q12_SHIFT);
286
287 projection_delta.z = projected_offset_z;
288
289 if (!current_state->path_depth)
290 {
291 struct Nav_Node *seed_neighbor = &nav_network->nodes[projection_neighbor_id];
292
293 if (!seed_neighbor->pathfind_state || seed_neighbor->parent_link != NAVIGATION_LINK_NO_PARENT)
294 shortcut_delta = (struct Math_Vec3I32){
295 .x = projection_delta.x,
296 .y = projection_delta.y,
297 .z = projected_offset_z};
298 else
299 {
300 struct Math_Vec3I32 *path_end_for_seed = g_boneTrailPathEnd;
301
302 shortcut_delta.x = path_end_for_seed[-1].x - projection_x;
303 shortcut_delta.y = path_end_for_seed[-1].y - goal_projection_point.y;
304 shortcut_delta.z =
305 (uint32_t)path_end_for_seed[-1].z - projection_z;
306
307 int32_t shortcut_length_squared =
308 (int32_t)(((uint64_t)((int64_t)shortcut_delta.x * shortcut_delta.x) + (uint64_t)((int64_t)shortcut_delta.y * shortcut_delta.y) + (uint64_t)((int64_t)shortcut_delta.z * shortcut_delta.z)) >> MATH_Q12_SHIFT);
309 int32_t projection_length_squared =
310 (int32_t)(((uint64_t)((int64_t)projection_delta.x * projection_delta.x) + (uint64_t)((int64_t)projection_delta.y * projection_delta.y) + (uint64_t)((int64_t)projection_delta.z * projection_delta.z)) >> MATH_Q12_SHIFT);
311 int32_t shorter_length_squared;
312
313 shorter_length_squared = shortcut_length_squared > projection_length_squared ? projection_length_squared : shortcut_length_squared;
314
315 int32_t cost_distance_reduction = Math_SqrtFP12(shorter_length_squared) >> 5;
316
317 cost_distance_reduction &= ~1;
318 goal_cost -= cost_distance_reduction;
319
320 int32_t projected_point_x = goal_projection_point.x + projection_delta.x;
321 int32_t projected_offset_y = projection_delta.y;
322
323 shortcut_delta.x = projected_point_x;
324
325 int32_t projected_point_y = projected_offset_y + goal_projection_point.y;
326
327 projected_offset_z = projection_delta.z;
328 shortcut_delta.y = projected_point_y;
329
330 int32_t projected_point_z = projected_offset_z + goal_projection_point.z;
331 struct Math_Vec3I32 *path_end_for_shortcut = g_boneTrailPathEnd;
332
333 shortcut_delta.z = projected_point_z;
334 shortcut_delta.x =
335 path_end_for_shortcut[-1].x - projected_point_x;
336 goal_position_alias = goal_position;
337 // Line-of-sight shortcut: avoid intermediate nodes if direct path clear
338 //
339 // Calculate line-of-sight shortcut with collision check
340 projection_x = goal_projection_point.x;
341 shortcut_delta.y = path_end_for_shortcut[-1].y - projected_point_y;
342 projection_z = goal_projection_point.z;
343 shortcut_delta.z =
344 (uint32_t)path_end_for_shortcut[-1].z - projected_point_z;
345 }
346 }
347
348 projection_x += projection_delta.x;
349 projection_z += projected_offset_z;
350 goal_projection_point = (struct Math_Vec3I32){
351 .x = projection_x,
352 .y = goal_projection_point.y + projection_delta.y,
353 .z = projection_z};
354 }
355
356 bool shortcut_valid = false;
357
358 if (!current_state->path_depth)
359 {
360 shortcut_delta.y = 0;
361
362 if (((int32_t)(((uint64_t)((int64_t)shortcut_delta.x * shortcut_delta.x) + (uint64_t)((int64_t)shortcut_delta.y * shortcut_delta.y) + (uint64_t)((int64_t)shortcut_delta.z * shortcut_delta.z)) >> MATH_Q12_SHIFT)) < NAVIGATION_SHORTCUT_DISTANCE_SQUARED_LIMIT)
363 {
364 int32_t goal_projection_x = goal_projection_point.x;
365
366 projection_delta.x = goal_position->x - goal_projection_x;
367
368 int32_t goal_projection_y = goal_projection_point.y;
369
370 projection_delta.y = goal_position->y - goal_projection_y;
371
372 int32_t goal_projection_z = goal_projection_point.z;
373
374 projection_delta.z = goal_position->z - goal_projection_z;
375
376 struct Math_Vec3I32 *path_end_for_start = g_boneTrailPathEnd;
377 struct Math_Vec3I32 *shortcut_start_position;
378
379 if ((uintptr_t)path_end_for_start <= (uintptr_t)&g_boneTrailTargetPosition)
380 {
381 shortcut_start_position = &path_end_for_start[-1];
382 shortcut_delta.x = goal_projection_x - path_end_for_start[-1].x;
383 shortcut_delta.y = goal_projection_y - path_end_for_start[-1].y;
384 shortcut_delta.z =
385 goal_projection_z - (uint32_t)path_end_for_start[-1].z;
386 }
387 else
388 {
389 shortcut_delta.x = path_end_for_start[-1].x - path_end_for_start[-2].x;
390 shortcut_start_position = &path_end_for_start[-2];
391 shortcut_delta.y = path_end_for_start[-1].y - path_end_for_start[-2].y;
392 shortcut_delta.z = (uint32_t)path_end_for_start[-1].z - path_end_for_start[-2].z;
393 }
394
395 int64_t goal_start_dot_x_wide = (int64_t)projection_delta.x * shortcut_delta.x;
396 int64_t goal_start_dot_z_wide = (int64_t)projection_delta.z * shortcut_delta.z;
397
398 if ((int32_t)(((uint32_t)((uint64_t)goal_start_dot_z_wide >> MATH_Q12_SHIFT)) + ((uint32_t)((uint64_t)goal_start_dot_x_wide >> MATH_Q12_SHIFT))) < 0)
399 {
400 projection_delta.y = 0;
401
402 int32_t goal_direction_length = Math_SqrtFP12((int32_t)(((uint64_t)((int64_t)projection_delta.x * projection_delta.x) + (uint64_t)((int64_t)projection_delta.y * projection_delta.y) + (uint64_t)((int64_t)projection_delta.z * projection_delta.z)) >> MATH_Q12_SHIFT));
403
404 if (goal_direction_length)
405 {
406 int32_t goal_direction_inverse_length = INT64_C(0x100000000) / goal_direction_length;
407 int64_t goal_direction_scaled_x_wide = (int64_t)goal_direction_inverse_length * projection_delta.x;
408
409 projection_delta.x = (int32_t)((uint32_t)((uint64_t)goal_direction_scaled_x_wide >> MATH_Q12_SHIFT)) >> 8;
410
411 int64_t goal_direction_scaled_y_wide = (int64_t)goal_direction_inverse_length * projection_delta.y;
412
413 projection_delta.y = (int32_t)((uint32_t)((uint64_t)goal_direction_scaled_y_wide >> MATH_Q12_SHIFT)) >> 8;
414
415 int64_t goal_direction_scaled_z_wide = (int64_t)goal_direction_inverse_length * projection_delta.z;
416
417 projection_delta.z = (int32_t)((uint32_t)((uint64_t)goal_direction_scaled_z_wide >> MATH_Q12_SHIFT)) >> 8;
418 }
419 else
420 memset(&projection_delta, 0, 0xc);
421
422 struct Math_Vec3I32 *shortcut_start = shortcut_start_position;
423 struct Math_Vec3I32 *checked_goal_position = goal_position;
424 int64_t goal_cross_zx_wide = (int64_t)projection_delta.z * (shortcut_start->x - checked_goal_position->x);
425 int64_t goal_cross_xz_wide = (int64_t)projection_delta.x * (shortcut_start->z - checked_goal_position->z);
426
427 if (((uint32_t)((uint64_t)goal_cross_zx_wide >> MATH_Q12_SHIFT)) - ((uint32_t)((uint64_t)goal_cross_xz_wide >> MATH_Q12_SHIFT)) + NAVIGATION_SHORTCUT_LATERAL_LIMIT_Q12 > NAVIGATION_SHORTCUT_LATERAL_RANGE_Q12)
428 {
429 shortcut_delta.y = 0;
430
431 int32_t start_direction_length = Math_SqrtFP12((int32_t)(((uint64_t)((int64_t)shortcut_delta.x * shortcut_delta.x) + (uint64_t)((int64_t)shortcut_delta.y * shortcut_delta.y) + (uint64_t)((int64_t)shortcut_delta.z * shortcut_delta.z)) >> MATH_Q12_SHIFT));
432
433 if (start_direction_length)
434 {
435 int32_t start_direction_inverse_length = INT64_C(0x100000000) / start_direction_length;
436 int64_t start_direction_scaled_x_wide = (int64_t)start_direction_inverse_length * shortcut_delta.x;
437
438 shortcut_delta.x = (int32_t)((uint32_t)((uint64_t)start_direction_scaled_x_wide >> MATH_Q12_SHIFT)) >> 8;
439
440 int64_t start_direction_scaled_y_wide = (int64_t)start_direction_inverse_length * shortcut_delta.y;
441
442 shortcut_delta.y = (int32_t)((uint32_t)((uint64_t)start_direction_scaled_y_wide >> MATH_Q12_SHIFT)) >> 8;
443
444 int64_t start_direction_scaled_z_wide = (int64_t)start_direction_inverse_length * shortcut_delta.z;
445
446 shortcut_delta.z = (int32_t)((uint32_t)((uint64_t)start_direction_scaled_z_wide >> MATH_Q12_SHIFT)) >> 8;
447 }
448 else
449 memset(&shortcut_delta, 0, 0xc);
450
451 shortcut_start = shortcut_start_position;
452 checked_goal_position = goal_position;
453
454 int64_t start_cross_zx_wide = (int64_t)shortcut_delta.z * (shortcut_start->x - checked_goal_position->x);
455 int64_t start_cross_xz_wide = (int64_t)shortcut_delta.x * (shortcut_start->z - checked_goal_position->z);
456
457 if (((uint32_t)((uint64_t)start_cross_zx_wide >> MATH_Q12_SHIFT)) - ((uint32_t)((uint64_t)start_cross_xz_wide >> MATH_Q12_SHIFT)) + NAVIGATION_SHORTCUT_LATERAL_LIMIT_Q12 <= NAVIGATION_SHORTCUT_LATERAL_RANGE_Q12)
458 {
459 shortcut_valid = true;
460 }
461 }
462 else
463 shortcut_valid = true;
464
465 if (shortcut_valid)
466 {
467 if (!Physics_CalculateMovementWithCollision(shortcut_start, checked_goal_position,
468 NULL, NAVIGATION_SHORTCUT_COLLISION_RADIUS_Q6, 1))
469 {
470 shortcut_delta.x = checked_goal_position->x - shortcut_start->x;
471 shortcut_delta.y = checked_goal_position->y - shortcut_start->y;
472 shortcut_delta.z = checked_goal_position->z - shortcut_start->z;
473
474 goal_cost = Math_SqrtFP12((int32_t)(((uint64_t)((int64_t)shortcut_delta.x * shortcut_delta.x) + (uint64_t)((int64_t)shortcut_delta.y * shortcut_delta.y) + (uint64_t)((int64_t)shortcut_delta.z * shortcut_delta.z)) >> MATH_Q12_SHIFT)) >> 6;
475 }
476 else
477 shortcut_valid = false;
478 }
479 }
480 }
481
482 projection_x = goal_projection_point.x;
483 goal_position_alias = goal_position;
484 projection_z = goal_projection_point.z;
485 }
486
487 struct Nav_OpenSetEntry *pathfind_state =
488 // Update open set: insert new or update existing if better path found
489 //
490 // Insert or update node in open set priority queue
491 nav_network->nodes[nav_network->node_count].pathfind_state;
492 struct Nav_OpenSetEntry *goal_open_entry = pathfind_state;
493
494 if (!pathfind_state || goal_cost < pathfind_state->cost)
495 {
496 if (!pathfind_state)
497 {
498 struct Nav_OpenSetEntry *new_goal_open_entry = Tree_AllocateMapNode(open_set);
499
500 goal_open_entry = new_goal_open_entry;
501
502 if (new_goal_open_entry)
503 {
504 nav_network->nodes[nav_network->node_count].pathfind_state =
505 new_goal_open_entry;
506 new_goal_open_entry->node_id = nav_network->node_count;
507 new_goal_open_entry->cost = goal_cost;
508 Tree_InitializeMapNode(open_set, new_goal_open_entry);
509 }
510 }
511 else
512 {
513 pathfind_state->cost = goal_cost;
514 Tree_FixupMapAfterInsert(open_set, pathfind_state);
515 }
516
517 nav_network->nodes[nav_network->node_count].neighbor_count = goal_destination_id;
518 nav_network->nodes[nav_network->node_count].neighbor_list = (struct Nav_NeighborEntry *)(goal_position_alias);
519
520 if ((int32_t)projection_neighbor_or_sentinel >= 0)
521 nav_network->nodes[nav_network->node_count].pos = (struct Math_Vec3I32){
522 .x = projection_x,
523 .y = goal_projection_point.y,
524 .z = projection_z};
525
526 uint16_t parent_node_bits = current_state->node_id << NAVIGATION_LINK_NODE_SHIFT;
527
528 nav_network->nodes[nav_network->node_count].parent_link = parent_node_bits | (uint16_t)saved_neighbor_index;
529
530 uint16_t path_depth = current_state->path_depth;
531
532 if (path_depth || !shortcut_valid)
533 {
534 goal_open_entry->path_depth = path_depth + 1;
535
536 struct Nav_Node *nodes = nav_network->nodes;
537 struct Nav_NeighborEntry *current_neighbors =
538 nodes[(int32_t)current_state->node_id].neighbor_list;
539 uint8_t parent_link_bits = current_neighbors[saved_neighbor_index].flags_and_node_low;
540 int32_t parent_projection_edge_selector = parent_link_bits & NAVIGATION_LINK_EDGE_MASK;
541
542 if (parent_projection_edge_selector - 1 >= 0)
543 {
544 uint32_t parent_projection_node_index;
545
546 if (!current_state->path_depth && current_state->cost)
547 {
548 int32_t packed_parent_projection_neighbor;
549
550 packed_parent_projection_neighbor = (uint16_t)
551 current_neighbors[parent_projection_edge_selector - 1]
552 .packed_id;
553 parent_projection_node_index = packed_parent_projection_neighbor >> NAVIGATION_LINK_NODE_SHIFT;
554 }
555
556 if (current_state->path_depth || !current_state->cost || !nodes[parent_projection_node_index].pathfind_state || nodes[parent_projection_node_index].parent_link != NAVIGATION_LINK_NO_PARENT)
557 goal_open_entry->path_depth = path_depth + 2;
558 }
559 }
560 else
561 goal_open_entry->path_depth = NAVIGATION_DIRECT_PATH_DEPTH;
562 }
563
564 neighbor_index = saved_neighbor_index;
565 }
566
567 if (neighbor_index < 0)
568 return;
569
570 int32_t previous_static_neighbor_index;
571
572 do
573 {
574 struct Nav_Node *static_nodes = nav_network->nodes;
575 struct Nav_NeighborEntry *neighbor_edge =
576 &static_nodes[(int32_t)current_state->node_id].neighbor_list[neighbor_index];
577 int32_t static_edge_cost = (uint16_t)(neighbor_edge->cost);
578 uint32_t static_total_cost = static_edge_cost + current_state->cost;
579 int32_t packed_static_neighbor = (uint16_t)(neighbor_edge->packed_id);
580 uint32_t static_neighbor_id = packed_static_neighbor >> NAVIGATION_LINK_NODE_SHIFT;
581 struct Nav_OpenSetEntry *neighbor_open_entry = static_nodes[static_neighbor_id].pathfind_state;
582
583 if (!neighbor_open_entry || ((uintptr_t)neighbor_open_entry != UINTPTR_MAX && static_total_cost < neighbor_open_entry->cost))
584 {
585 if (!neighbor_open_entry)
586 {
587 neighbor_open_entry = Tree_AllocateMapNode(open_set);
588
589 if (neighbor_open_entry)
590 {
591 nav_network->nodes[static_neighbor_id].pathfind_state = neighbor_open_entry;
592 neighbor_open_entry->node_id = (uint16_t)static_neighbor_id;
593 neighbor_open_entry->cost = static_total_cost;
594 Tree_InitializeMapNode(open_set, neighbor_open_entry);
595 }
596 }
597 else
598 {
599 neighbor_open_entry->cost = static_total_cost;
600 Tree_FixupMapAfterInsert(open_set, neighbor_open_entry);
601 }
602
603 nav_network->nodes[static_neighbor_id].parent_link = current_state->node_id << NAVIGATION_LINK_NODE_SHIFT | (uint16_t)saved_neighbor_index;
604 neighbor_index = saved_neighbor_index;
605 neighbor_open_entry->path_depth = current_state->path_depth + 1;
606 }
607
608 previous_static_neighbor_index = neighbor_index;
609 neighbor_index -= 1;
610 saved_neighbor_index = neighbor_index;
611 } while (previous_static_neighbor_index);
612}
#define ACTOR_BEHAVIOR_GROUND_TRACKING
Definition constants.h:12
#define g_boneTrailPathEnd
Definition globals.h:34
void * Tree_AllocateMapNode(struct Tree_Map *tree)
Definition tree.c:244
int32_t Tree_FixupMapAfterInsert(struct Tree_Map *tree, void *node_payload)
Definition tree.c:215
void Tree_InitializeMapNode(struct Tree_Map *tree, void *node_payload)
Definition tree.c:10
#define COLLISION_POLYGON_TRIANGLE
Definition constants.h:26
char Navigation_QueueDamageResponse(struct Actor_State *actor, struct Component_Instance *damage_component)
Definition commands.c:89
static int32_t Math_DotProduct3Q12(int32_t ax, int32_t ay, int32_t az, int32_t bx, int32_t by, int32_t bz)
Definition commands.c:33
void Navigation_AddCommand(uint8_t command_type, int16_t target_selector_a, int16_t target_selector_b, int32_t speed, struct Math_Vec3I32 const *position)
Definition commands.c:42
void Nav_CalculatePolygonCenter(struct Collision_Node *node, struct Collision_Polygon *polygon, struct Math_Vec3I32 *out_center)
Definition commands.c:131
void Nav_RelaxPathEdges(struct Tree_Map *open_set, struct Nav_Network *nav_network, struct Nav_OpenSetEntry *current_state, int32_t skip_dynamic_targets, int32_t initial_shortcut_x, int32_t initial_shortcut_z)
Definition commands.c:157
struct Actor_State * Component_GetOwnerActor(struct Actor_State *actor)
Definition lifecycle.c:39
BOOL Component_IsAirborneTarget(struct Actor_State *actor)
Definition collision.c:376
int32_t Component_GetTeamID(struct Actor_State *actor)
Definition properties.c:28
#define ENTITY_FLAG_NAVIGATION_GOAL_ENABLED
Definition constants.h:23
#define ENTITY_FLAG_RESTORE_DEFAULTS
Definition constants.h:18
#define ENTITY_FLAG_DAMAGE_REACTION_DISABLED
Definition constants.h:27
#define EntityNavigationWorkList_StagingBufferPtr
Definition globals.h:15
#define MATH_Q12_SHIFT
Definition constants.h:8
#define MATH_Q12_ONE
Definition constants.h:9
int32_t Math_SqrtFP12(uint32_t value)
#define NAVIGATION_POWERUP_GOAL_FIRST
Definition constants.h:6
#define NAVIGATION_LINK_NODE_SHIFT
Definition constants.h:7
#define NAVIGATION_LINK_NO_PARENT
Definition constants.h:9
#define NAVIGATION_ENTITY_GOAL_COUNT
Definition constants.h:5
#define NAVIGATION_DIRECT_PATH_DEPTH
Definition constants.h:10
#define NAVIGATION_COMMAND_DEFAULT_SELECTOR
Definition constants.h:11
#define NAVIGATION_COMMAND_UNLIMITED_SPEED
Definition constants.h:12
#define NAVIGATION_AIRBORNE_REACTION_FRAMES
Definition constants.h:13
#define NAVIGATION_ENTITY_GOAL_FIRST
Definition constants.h:4
#define NAVIGATION_LINK_EDGE_MASK
Definition constants.h:8
#define pkg_resource_current_level_data
Definition globals.h:117
#define POWERUP_ENTRY_COLLECTED
Definition constants.h:6
#define POWERUP_ENTRY_DISABLED
Definition constants.h:7
@ POWERUP_INVENTORY_FIRST
Definition constants.h:17
int32_t behavior_flags
Definition types.h:407
void * record_ptr
Definition types.h:477
struct Collision_Vertex * vertices
Definition types.h:292
struct Math_Matrix3x3I16 transform_matrix
Definition types.h:281
struct Math_Vec3I32 origin
Definition types.h:283
uint16_t vertex_idx[0x4]
Definition types.h:61
uint16_t flags
Definition types.h:66
int16_t z
Definition types.h:111
struct Collision_Vertex::@111126275124057154070202104324102117233165176236::@061322026074334072070347216127267241215241121036 pos
int16_t x
Definition types.h:109
int16_t y
Definition types.h:110
struct Nav_Command nav_commands[0x64]
Definition types.h:135
Definition types.h:22
uint32_t flags
Definition types.h:25
struct Math_Vec3I32 bonus_respawn_pos
Definition types.h:35
struct Math_Vec3I32 * position_ptr
Definition types.h:78
uint8_t team_bitmask[0x10]
Definition types.h:108
int16_t m21
Definition types.h:169
int16_t m00
Definition types.h:162
int16_t m01
Definition types.h:163
int16_t m12
Definition types.h:167
int16_t m11
Definition types.h:166
int16_t m20
Definition types.h:168
int16_t m22
Definition types.h:170
int16_t m02
Definition types.h:164
int16_t m10
Definition types.h:165
int32_t y
Definition types.h:471
int32_t x
Definition types.h:470
int32_t z
Definition types.h:472
int16_t target_selector_b
Definition types.h:73
int16_t target_selector_a
Definition types.h:72
struct Math_Vec3I32 pos
Definition types.h:75
uint32_t command_type
Definition types.h:71
int32_t speed
Definition types.h:74
int16_t cost
Definition types.h:22
uint8_t flags_and_node_low
Definition types.h:17
uint16_t packed_id
Definition types.h:13
struct Nav_Node * nodes
Definition types.h:35
int32_t node_count
Definition types.h:34
struct Math_Vec3I32 pos
Definition types.h:103
uint16_t parent_link
Definition types.h:104
struct Nav_NeighborEntry * neighbor_list
Definition types.h:107
struct Nav_OpenSetEntry * pathfind_state
Definition types.h:106
int16_t neighbor_count
Definition types.h:105
int16_t path_depth
Definition types.h:47
int16_t node_id
Definition types.h:46
uint32_t cost
Definition types.h:45
Definition types.h:9
struct Powerup_Entry::@336143272047254075051102357366017247347220271357 pos
uint8_t powerup_type
Definition types.h:14
uint8_t flags
Definition types.h:15