Back to legacygamers.net
WARPGATE

Pathfinding

CPathFinder (A*), CWalkGrid, CQuadTree, C3dAttr

Functions 80Code 25 KBAddresses 0x00748410 to 0x010ACF60Group Systems
80 functions
AddressSizeNameDescription
0x00748410200C3dAttr__CreateFactory function for C3dAttr (3D map attribute data). Allocates 0x128-byte object, calls constructor FUN_00aeda10, sets vtable PTR_FUN_0111ac08, initializes vector members (0x47-0x49) and parameters (mode=0, count=0, type=5).
0x007484E0853C3dAttr__LoadFromFileLoads 3D attribute data from a .gat file. Validates magic header, reads version (must be v1.x with subversion < 4), reads width/height, resizes attribute grid, reads 0x14-byte attribute cells. For version >= 1.3, clears high bit of cell flags. Logs error for unsupported versions.
0x00748860112C3dAttr__scalar_deleting_destructorScalar deleting destructor for C3dAttr. Calls destructor FUN_00748b20, sets vtable to PTR_FUN_0111aabc, conditionally frees 0x128 bytes.
0x00748A70148C3dAttr__constructorConstructor for C3dAttr. Calls base constructor FUN_00aeda10, sets vtable to C3dAttr__scalar_deleting_destructor vtable, initializes vector (0x47-0x49 = begin/end/capacity), and grid parameters (width=0, height=0, cellSize=5).
0x00748B20151C3dAttr__destructorDestructor for C3dAttr. Frees the attribute cell vector buffer and resets begin/end/capacity to 0.
0x00748BC0180C3dAttr__ResizeResizes the 3D attribute grid. Calls virtual clear (vtable+0x18), then resizes the internal vector to width*height 0x14-byte cells, stores width/height at offsets 0x110/0x114.
0x00748C80165C3dAttr__GetCellTypeGets the terrain type at world coordinates. Converts float coordinates to grid cell indices using cell size and half-width/height offset. Returns the type field (offset 0x10 in cell). Returns 1 (walkable) if out of bounds.
0x00748D3067C3dAttr__GetCellPtrReturns pointer to the attribute cell at grid position (param_2, param_3). Validates bounds against width (0x110) and height (0x114). Returns 0 if out of bounds. Cell data starts at offset 0x11C (vector begin), each cell is 0x14 bytes.
0x00748D80261C3dAttr__GetInterpolatedHeightCalculates interpolated height at world position (param_2, param_3). Converts to grid coordinates, then bilinearly interpolates between the 4 corner heights of the cell (stored as floats at offsets 0-0xC in each 0x14-byte cell). Returns 0.0 if out of bounds.
0x00748E90316C3dAttr__GetHeightMinMaxComputes min and max height values across a rectangular region of cells specified by param_2 (x1,y1,x2,y2). Iterates all cells in the rectangle, checking all 4 corner heights per cell. Outputs min to param_3 and max to param_4. Initializes min=999999, max=-999999.
0x00748FD0107C3dAttr__GridToWorldConverts grid cell coordinates to world coordinates. Subtracts half the grid dimensions (width/2, height/2) and multiplies by cell size (offset 0x118). Output stored in param_4[0] (x) and param_4[1] (y).
0x00749040605C3dAttr__GetInterpolatedHeightBarycentricCalculates interpolated terrain height using barycentric interpolation across a triangle formed by 3 cell corners. Converts world coords to grid, gets cell corner heights, computes barycentric coordinates for sub-cell position, and returns weighted height. Returns 0 if out of bounds.
0x007492A086C3dAttr__IsCellWalkableChecks if a grid cell at (param_2, param_3) is walkable. Returns true (1) if cell type is not 1 (blocked) and not 5 (water). Returns false (0) if blocked, water, or out of bounds.
0x00749300485C3dAttr__RaycastHeightRaycasts against the terrain to find height at a point. Gets cell corners, builds two triangles from the cell quad, and performs ray-triangle intersection tests. Returns the closest intersection height or 0 if no hit.
0x00ABFD601028CWalkGrid__check_cell_collisionChecks ray collision against a walk grid cell at (param_3, param_4). For each of 3 sub-cells (offsets 0x40, 0x48, 0x44), extracts 4 corner vertices (at stride 0x20), tests ray intersection via CRay__intersect_triangle_alt for two triangles. If intersection distance < param_5, marks cell as collided (offset 0x94 = 1).
0x00AC0180127CWalkGrid__world_to_cellConverts world coordinates (param_2, param_3) to grid cell indices. Divides by cell size (offset 0x10), floors, and adds half grid dimensions (offsets 8, 0xC) to center the grid.
0x00AC09B0209CWalkGrid__get_cell_colorGets cell color (RGB bytes) at world coordinates. Converts world X/Z to grid indices via floor division. Returns color from cell at offset 0x50-0x52 within the 0x54-byte cell structure. Out-of-bounds returns 0xFF,0xFF,0xFF (white).
0x00AC0A90417CWalkGrid__get_cell_quad_positionsGets 4 corner world positions for a cell quad. Input is doubled indices (param_2/2, param_3/2 = actual cell). Computes XZ from cell size, Y initially 0. Calls C3dAttr__GetCellPtr for actual height data, fills param_4 with 4 vec3 corners. Returns 1 if valid.
0x00AC0C40248CWalkGrid__get_half_cell_quad_positionsGets 4 corner positions for a half-cell quad (used for higher-resolution rendering). Uses half cell size (cellSize * 0.5). Similar to get_cell_quad_positions but at doubled resolution. Fills param_4 with 4 vec3 corners.
0x00AC0D40237CWalkGrid__get_cell_vertices_with_heightGets cell vertices (4 corners, 12 floats each) from the 0x54-byte cell structure at offsets 0x40. Copies vertex positions from stride-0x20 source. Also fetches height data from parent's 0x14-byte height array at offset 0x11C.
0x00AC0E30100CWalkGrid__get_cell_heights_to_bufferReads height values from the parent's height data array (offset 0x11C in parent at offset 4). Writes 4 height floats at stride 0xC into param_2 buffer. Bounds-checked against grid dimensions.
0x00AC0EA0353CWalkGrid__get_height_range_for_regionGets min/max height for a rectangular region of cells. param_2 is [x1, y1, x2, y2] bounds. Iterates all cells in region, reads 4 heights per cell (offsets 4, 0x24, 0x44, 0x64 in vertex data). Returns min in param_3, max in param_4. Out-of-bounds or empty returns 0,0.
0x00AC1010241CWalkGrid__get_cell_height_rangeGets min/max height for a single cell at (param_2, param_3). Reads 4 vertex heights at offsets 4, 0x24, 0x44, 0x64. Returns min in param_4, max in param_5. Out-of-bounds returns 0,0.
0x00AC1130134CWalkGrid__get_lightmap_colorGets lightmap color for a cell vertex. Input doubled indices. Reads RGB floats from lightmap buffer (offset 0x70, 12 bytes per entry). Returns default 1.0, 1.0, 1.0 if out-of-bounds or no lightmap data.
0x00AC11D0435CWalkGrid__get_vertex_color_rgbaGets RGBA vertex color for a cell corner. Uses doubled indices, selects one of 4 sub-quadrants based on parity of x/y. Reads from cell's vertex data at offset 0x8C (sub-offsets 0x28-0x37 for the 4 quadrants). Returns 0xFF for all channels if out-of-bounds or no data.
0x00AC1390122CWalkGrid__get_shadow_valueGets shadow/ambient occlusion value for a cell. Maps cell indices to shadow grid (coarser resolution via offsets 0x88/0x8C). Clamps to grid bounds. Returns float from shadow array at offset 0x90.
0x00AC141020CWalkGrid__ensure_loadedEnsures walk grid data is loaded. If offset 0x14 is null, triggers virtual load (vfunc 0x4C) and rechecks. Returns the loaded data pointer.
0x00AC1430214CWalkGrid__update_animated_texturesUpdates animated textures for walk grid surfaces. Iterates texture entries (0x24 bytes each, offset 0x9C-0xA0). Increments frame counter, wraps animation cycle. Builds texture filename via snprintf with frame index, loads via stub_005717a0. Updates rotation angle with wrap at 360 degrees.
0x00AC154090CWalkGrid__cell_to_shadow_indexConverts cell indices to shadow grid index. Divides by cell-to-shadow ratio, clamps to shadow grid bounds, returns linear index into shadow array.
0x00AC15A0287CWalkGrid__render_ground_cellsRenders ground cells within a region (param_3 = [x1,y1,x2,y2]). Iterates cells, skips already-rendered (frame stamp at offset 0x4C). For each cell with sub-cell 0x40, calls render_water_cell_animated and render_ground_quad. Also renders sub-cells 0x48 and 0x44 via render_ground_quad.
0x00AC16D059CWalkGrid__render_grid_overlayRenders a grid overlay texture on a cell. Loads grid.tga texture, passes to CWalkGrid__render_textured_quad with predefined UV coordinates from DAT_01347eb0.
0x00AC1720640CWalkGrid__render_textured_quadRenders a textured quad on a walk grid cell. Gets cell corners, interpolates positions for sub-cells based on parity. Projects 4 vertices to screen space, applies UV from texture and param_6 UV scale table. Enqueues as alpha-blended mesh (type 5/6).
0x00AC19A0885CWalkGrid__render_ground_cells_with_frustumRenders ground cells with full frustum culling. For each cell in region, projects 4 vertices, performs screen-space frustum test (min/max X, Y, depth checks). Renders vertex data with UV, color (alpha=0x80), and texture. Processes sub-cells 0x48 and 0x44 via render_ground_quad_simple.
0x00AC1D302037CWalkGrid__render_ground_quadRenders a single ground quad. Projects 4 vertices to screen, performs frustum culling if param_3 set. Applies ambient lighting to vertex colors (DAT_016fda88/90). Handles shadow mapping option (0x77). If shadow enabled and DAT_01311ec4 set, enqueues to post-process queue. Otherwise renders as standard ground mesh (type 0x800) with optional lightmap (type 0x1000).
0x00AC2530646CWalkGrid__render_ground_quad_simpleRenders a ground quad without shadow or ambient color processing. Projects 4 vertices, performs frustum culling if param_3 set. Copies UV and color data directly from source vertices. Enqueues as ground mesh (type 0x800).
0x00AC27C0952CWalkGrid__render_water_cellRenders a water cell with shadow and wave modulation. Gets shadow value, applies wave height via vec3_normalize with time-based offsets. Modifies vertex heights based on shadow. Projects vertices, checks backface via cross product. Colors based on light type (type 4 = custom RGB, else 0x90FFFFFF). Computes UV from 4x4 atlas position. Enqueues as alpha mesh.
0x00AC2B801154CWalkGrid__render_water_cell_animatedRenders water cell with animated texture. Similar to render_water_cell but uses per-texture animation data from offset 0x9C array (wave speed, amplitude, phase). Applies animated wave height. Marks mesh for alpha blending. Uses texture from animated texture entry.
0x00AC309057CWalkGrid__set_lightmap_colorSets lightmap color for a cell. Writes 3 floats (RGB) at offset 0x70 buffer, indexed by (width * param_3 * 2 + param_2) * 12 bytes. No-op if no lightmap buffer (offset 0x70 == 0x74).
0x00AC30D0582CWalkGrid__add_water_layerAdds a water layer to the walk grid. If version flag (0x114) is set and version >= 8, copies bulk water data from file (counts at 0x148/0x14C, vertex/face arrays). Otherwise appends single water entry to 36-byte and dword vectors. Calls virtual update (vfunc 0x4C). Sets multi-layer flag (0x2A).
0x00AC332080CWalkGrid__set_water_paramsSets water parameters. Stores: type (0x38), speed (0x48), wave height (0x3C), wave speed (0x40), angle (0x44, mod 360), animation type (0x4C).
0x00AC3380640CWalkGrid__render_effect_quadRenders a textured effect quad on a walk grid cell. Same structure as render_textured_quad but with depth bias via DAT_0115926c and different UV handling. Projects 4 vertices, assigns UV from texture and param_6 table. Enqueues as alpha mesh.
0x00AC3610646CWalkGrid__render_cursor_cellRenders a cursor/selection indicator on a walk grid cell. Computes half-cell positions with overlap margin. Gets height from C3dAttr__GetCellPtr. Sets fixed UV (0-1 range). Assigns uniform color (param_5). Enqueues as alpha-blended mesh with texture param_6.
0x00AD7E70248CPathFinder__init_tree_containersInitializes pathfinder tree containers at offsets 0x1078 and 0x1090. Allocates 0x2C and 0x18 byte sentinel nodes for two red-black trees. Zeroes out associated vectors and flags.
0x00AD7F70110CPathFinder__init_six_fieldsInitializes a 6-field (24-byte) structure to all zeroes. Returns pointer to the initialized struct. Used for pathfinding state initialization.
0x00AD85A0326CPathFinder__dtorCPathFinder destructor. Cleans up movement data, calls virtual destructors on tracked objects, destroys the open set tree and node pool, frees all three vectors (4-byte, 16-byte, 28-byte), then destroys and frees the main 0x2C-byte tree sentinel.
0x00AD87A0333CPathFinder__build_path_resultBuilds the final path result from a linked list of path nodes. Counts nodes, resizes the result vector if needed, copies waypoint coordinates (x, y, direction) in reverse order into the vector. Computes movement timing with distance-based interpolation and direction flags.
0x00AD88F01066CPathFinder__find_path_astarA* pathfinding implementation. Takes start/goal coordinates, expands neighbors in 8 directions (cardinal cost 10, diagonal cost 14), uses min-heap priority queue sorted by estimated total cost (offset 0x10). Checks walkability via FUN_00ad9550 and collision via FUN_00ad9610. Returns 1 on success (path found), 0 on failure. Builds result path via CPathFinder__build_path_result.
0x00AD8D2066CPathFinder__get_waypoint_at_indexGets waypoint data at a given index from the path result vector (16-byte elements). Copies the first two fields (x, y coords) to output params. Returns 1 on success, 0 if index out of bounds or empty.
0x00AD8D7026CPathFinder__get_last_waypoint_directionGets the direction field from the last waypoint in the path result vector. Reads the last 4 bytes of the last 16-byte element (offset -4 from end).
0x00AD8D9023CPathFinder__get_last_waypoint_timestampGets the timestamp/timing field from the last waypoint in the path result vector. Returns the second-to-last field of the last 16-byte element, or -1 if empty.
0x00AD8DD0321CPathFinder__allocate_nodeAllocates a pathfinding node from the node pool. If dynamic allocation is enabled (flag at offset 0x1080), uses a resizable 0x1C-byte vector; otherwise uses a fixed inline array of 149 (0x95) nodes at offset +0x10. Returns pointer to the next available node slot, incrementing the count at offset +0xC.
0x00AD8F20257CPathFinder__get_position_at_timeGets interpolated position along the path at a given timestamp. Searches through waypoint segments to find which segment contains the timestamp, outputs direction and interpolated x/y float coordinates. Returns segment index, 0 if before first segment, -1 if past end or empty.
0x00AD9030646CPathFinder__get_or_create_nodeGets or creates a pathfinding node for a given (x,y) cell. Looks up position in the node map (red-black tree keyed by linearized coordinate). If found, returns existing node. If not found, allocates a new node from the pool, initializes it with coordinates and cost=0, inserts into the tree, and returns it. Returns NULL if pool is exhausted.
0x00AD92C0467CPathFinder__get_interpolated_positionInterpolates position along the path at a given time value. Searches path segments for the time range containing the query time, then linearly interpolates x/y coordinates within that segment. Returns segment index, stores direction from halfway point of segment. Handles first segment specially using stored origin position. Returns -1 if past end.
0x00AD94A096CPathFinder__calc_arrival_timeCalculates arrival time for a path segment. Computes Euclidean distance between start position (stored in param_2 fields) and next waypoint, converts to time units, and adds to base time param_1.
0x00AD9550158CPathFinder__is_cell_walkableChecks if a cell at (param_4, param_5) is walkable for pathfinding. Validates bounds against map dimensions (offsets 0x110, 0x114), gets cell via C3dAttr__GetCellPtr, rejects type 1 (unwalkable) and type 5 (unless direction is diagonal=0xC). For diagonal moves, also checks both intermediate cardinal cells for walkability.
0x00AD9610322CPathFinder__try_expand_neighborTries to expand a neighbor cell during A* search. Gets or creates a node for (param_4, param_5), computes g-cost = parent cost + step cost (param_3), h-cost = Manhattan distance * 10 to goal. If node is new (status 0), sets it up and pushes to open set. If node exists with higher g-cost, updates it and re-heapifies. Direction stored in field[6]. Returns 1 on success, 0 if node allocation fails.
0x00AD976087CPathFinder__open_set_pushPushes a node pointer onto the open set (min-heap priority queue). If the vector is full, reallocates via FUN_00ad76e0. After appending, calls pathfind_heap_push_up to maintain heap ordering by cost field (offset 0x10).
0x00AD9840181CPathFinder__reset_search_stateResets the pathfinder search state for a new search. Clears the node map (red-black tree at offset 0x1090) by traversing and freeing all 0x18-byte nodes. Clears the open set vector (offsets 0x1098/0x109C). Also resets the waypoint result vector (0x1084/0x1088).
0x00AD99108CPathFinder__reset_node_pool_indexResets the pathfinder node pool allocation index (field 0x0C / offset 3) to zero, effectively resetting the pool for a new search.
0x00AD992012CPathFinder__set_map_pointerSets the map/attribute data pointer (field 0) of the pathfinder object.
0x00AD993013CPathFinder__set_node_pool_indexSets the pathfinder node pool allocation index (field 0x0C). Used to track how many nodes have been allocated from the pool.
0x00AD994017CPathFinder__set_start_xSets the pathfinder start X coordinate at offset 0x10.
0x00AD996017CPathFinder__set_start_ySets the pathfinder start Y coordinate at offset 0x14.
0x00AD9980504C3dAttr__load_or_get_cachedLoads or retrieves a cached C3dAttr map attribute object by filename string. Looks up the filename in a string-keyed red-black tree (map cache). If found, returns existing. If not, allocates a new C3dAttr (0x128 bytes), constructs it, inserts into cache tree, loads map data via virtual call at vtable+0x14, and stores pointer. Returns 1 on success, 0 on allocation failure.
0x00ADA4F0139CQuadTreeNode__ctorCQuadTreeNode constructor. Sets vtable pointer to PTR_FUN_011598e0, allocates a 0x0C-byte circular linked list sentinel for children/objects, initializes 4 child pointers (fields 5-8) and bounds fields (9-10) to zero.
0x00ADA58067CQuadTreeNode__free_list_sentinelFrees the 0x0C-byte linked list sentinel node at field offset+4 if non-null. SEH-protected. Used by CQuadTreeNode cleanup.
0x00ADA5D078CQuadTreeNode__free_list_sentinel_sehSEH-wrapped variant that frees the 0x0C-byte linked list sentinel node at field offset+4 if non-null. Used by CQuadTreeNode cleanup.
0x00ADA620103CQuadTreeNode__destroy_linked_listDestroys all nodes in a CQuadTreeNode's linked list of 0x0C-byte nodes. Clears tail pointer, traverses and frees each node, then frees the sentinel/head node.
0x00ADA690134CQuadTreeNode__dtorCQuadTreeNode destructor. Resets vtable, calls cleanup to free contained objects and child nodes, then destroys the linked list of 0x0C-byte nodes at field[9].
0x00ADA72035CQuadTreeNode__scalar_deleting_dtorCQuadTreeNode scalar deleting destructor. Calls CQuadTreeNode__dtor then conditionally frees the 0x2C-byte object memory if bit 0 of param_2 is set.
0x00ADA750251CQuadTreeNode__insert_objectInserts an object into a quad tree leaf node. Traverses child nodes by comparing object position (param_2 float coordinates) against midpoints to find the correct leaf. At the leaf, allocates a 0x0C-byte list node, stores the object pointer, and links it into the leaf's doubly-linked list. Increments the node's object count at field[0x28]. Throws if list exceeds max size.
0x00ADA850145CQuadTreeNode__clear_objects_and_childrenClears all objects from a quad tree node. Frees 0x28-byte object data for each list entry, then frees all 0x0C-byte list nodes and adjusts count. Destroys 4 child quad tree nodes via virtual destructors (offset 0x14-0x20), setting pointers to null.
0x00ADA8F0238CQuadTreeNode__find_object_atFinds an object at given (x,y) float coordinates in the quad tree. For leaf nodes, searches the object list for entries whose bounding box contains the point, returns the one with the highest z+height value. For internal nodes, recursively searches the best quadrant first, then tries other quadrants if not found. Returns object pointer or NULL.
0x00ADA9E063CQuadTreeNode__get_quadrant_indexDetermines which quadrant (0-3) a point falls in based on the node's midpoints. 0=top-left, 1=top-right, 2=bottom-right, 3=bottom-left. Uses field[0x0C]/2 as x midpoint, field[0x10]/2 as y midpoint.
0x00ADAA2056CQuadTreeObj__contains_pointTests if a 2D point (param_2, param_3) is within the axis-aligned bounding box defined by this object. Checks field[0]<=x<field[3] and field[1]<=y<field[4]. Returns 1 if inside, 0 otherwise.
0x00ADAA60344CQuadTreeNode__subdivideSubdivides a quad tree node recursively to a given depth. Clears existing children and objects, sets bounds from params. Creates 4 child CQuadTreeNode objects (0x2C bytes each), each covering one quadrant of the parent's bounds. Recursively subdivides each child to depth param_2-1. Base case: depth 0 = leaf node.
0x00CD3780680CPathfinder__find_nearest_walkable_cellFinds the nearest walkable cell along the line from player position to target. Uses Bresenham-like line traversal, checking 9 offsets around each cell (from a direction table). For each candidate cell, validates it's within map bounds, checks cell type (not 1 or 5), and verifies accessibility via FUN_00cd74b0. When found, verifies path exists with find_path_with_temp_buffer. Returns 1 on success with updated coordinates.
0x00CD6F00630CPathfinder__check_line_of_sightChecks line of sight between two cell positions using Bresenham line algorithm. Traverses cells from (param_2,param_3) to (param_4,param_5), checking each cell type. Returns 0 if blocked by type 1 (wall) cells. If param_6 is set, also blocks on out-of-bounds or non-walkable cells. Returns 1 if the path is clear.
0x010ACF6010thunk_to_CPathFinder__dtorThunk that calls CPathFinder__dtor to destroy the global pathfinder instance.