john/McRogueFace

Fork 0

Pathfinding with entity collision labels #302

New issue

Closed

opened 2026-03-15 00:32:02 +00:00 by john · 1 comment

john commented

2026-03-15 00:32:02 +00:00

Owner

Summary

Extend A* and Dijkstra pathfinding to optionally treat entities with a specific label as impassable obstacles. This enables collision-aware pathfinding without modifying the grid's walkability layer.

Proposed API

Entity-level (uses entity defaults from #252)

path = entity.find_path(destination, collide="solid")
# Uses entity's default walkability layer
# Treats cells occupied by "solid"-labeled entities as unwalkable
# Excludes self from collision check
# Returns AStarPath or None

Grid-level (explicit parameters)

path = grid.find_path(start, end, collide="solid")
# walkability layer parameter deferred to #252
# collide parameter adds entity collision on top of terrain walkability

dmap = grid.get_dijkstra_map(root, collide="solid")
# Dijkstra map with entity collision
# Cache key includes collide label

Implementation

Before computing A*/Dijkstra, build a transient walkability map:

Start with the grid's walkability data (TCOD map)
Query all entities with the collide label via spatial hash
Mark their cell_pos cells (including multi-tile #236) as unwalkable
Exclude the pathfinding entity itself from collision
Compute A*/Dijkstra on the transient map
Restore or discard the transient map

Transient map approach

Option A: Copy TCOD map — create a temporary copy, modify it, compute, discard. Simple but allocates.

Option B: Mark-and-restore — record which cells were changed, modify in place, compute, restore. No allocation but must be careful about concurrent access.

Option A is safer and clearer. For 8192×8192 grids (#252 target), the TCOD map copy is ~67MB. Consider a sparse approach: only copy the cells that need modification (the occupied cells), using TCOD's per-cell setters.

Optimal approach for large grids

Create TCOD path/dijkstra with the existing map
Before computing, temporarily set occupied cells to unwalkable via TCOD_map_set_properties()
Compute pathfinding
Restore the original walkability for those cells

This modifies only O(entities) cells rather than copying the entire map.

Cache invalidation

Dijkstra maps with collision labels must be invalidated when:

Any entity with the collision label moves (changes cell_pos)
An entity gains or loses the collision label

grid.step() handles this automatically after processing all turns.

Dependencies

#296 (entity labels)
#295 (cell_pos for accurate cell occupancy)
Interacts with #252 (entity default walkability layer)

Files likely affected

src/UIGridPathfinding.h/cpp — add collide parameter to find_path() and get_dijkstra_map()
src/UIGrid.h/cpp — Python method bindings
src/UIEntity.h/cpp — entity.find_path() method

## Summary Extend A* and Dijkstra pathfinding to optionally treat entities with a specific label as impassable obstacles. This enables collision-aware pathfinding without modifying the grid's walkability layer. ## Proposed API ### Entity-level (uses entity defaults from #252) ```python path = entity.find_path(destination, collide="solid") # Uses entity's default walkability layer # Treats cells occupied by "solid"-labeled entities as unwalkable # Excludes self from collision check # Returns AStarPath or None ``` ### Grid-level (explicit parameters) ```python path = grid.find_path(start, end, collide="solid") # walkability layer parameter deferred to #252 # collide parameter adds entity collision on top of terrain walkability dmap = grid.get_dijkstra_map(root, collide="solid") # Dijkstra map with entity collision # Cache key includes collide label ``` ## Implementation Before computing A*/Dijkstra, build a transient walkability map: 1. Start with the grid's walkability data (TCOD map) 2. Query all entities with the `collide` label via spatial hash 3. Mark their `cell_pos` cells (including multi-tile #236) as unwalkable 4. Exclude the pathfinding entity itself from collision 5. Compute A*/Dijkstra on the transient map 6. Restore or discard the transient map ### Transient map approach Option A: **Copy TCOD map** — create a temporary copy, modify it, compute, discard. Simple but allocates. Option B: **Mark-and-restore** — record which cells were changed, modify in place, compute, restore. No allocation but must be careful about concurrent access. Option A is safer and clearer. For 8192×8192 grids (#252 target), the TCOD map copy is ~67MB. Consider a sparse approach: only copy the cells that need modification (the occupied cells), using TCOD's per-cell setters. ### Optimal approach for large grids 1. Create TCOD path/dijkstra with the existing map 2. Before computing, temporarily set occupied cells to unwalkable via `TCOD_map_set_properties()` 3. Compute pathfinding 4. Restore the original walkability for those cells This modifies only O(entities) cells rather than copying the entire map. ## Cache invalidation Dijkstra maps with collision labels must be invalidated when: - Any entity with the collision label moves (changes `cell_pos`) - An entity gains or loses the collision label `grid.step()` handles this automatically after processing all turns. ## Dependencies - #296 (entity labels) - #295 (`cell_pos` for accurate cell occupancy) - Interacts with #252 (entity default walkability layer) ## Files likely affected - `src/UIGridPathfinding.h/cpp` — add `collide` parameter to `find_path()` and `get_dijkstra_map()` - `src/UIGrid.h/cpp` — Python method bindings - `src/UIEntity.h/cpp` — `entity.find_path()` method

john added a new dependency

2026-03-15 00:32:55 +00:00

#295 Entity cell_pos — integer logical position decoupled from render position

john added a new dependency

2026-03-15 00:32:56 +00:00

#296 Entity labels — multi-tag string set for collision and trigger grouping

john referenced this issue

2026-03-15 20:18:26 +00:00

Entity labels — multi-tag string set for collision and trigger grouping #296

john referenced this issue

2026-03-15 20:18:41 +00:00

grid.step() — turn manager for entity behaviors #301

john commented

2026-03-15 20:18:45 +00:00

Author

Owner

Roadmap context

Part of the Grid & Entity Overhaul Roadmap (docs/GRID_ENTITY_OVERHAUL_ROADMAP.md), Phase 3b (parallel track alongside behavior struct #300).

For large grids (targeting 8192x8192): do NOT copy the TCOD map. Instead, mark-and-restore O(entities) cells. See roadmap for implementation details.

Designed with #252 (Grid/GridView) API in mind — entity.find_path() will use entity's default walkability layer once #252 lands.

## Roadmap context Part of the Grid & Entity Overhaul Roadmap (`docs/GRID_ENTITY_OVERHAUL_ROADMAP.md`), **Phase 3b** (parallel track alongside behavior struct #300). For large grids (targeting 8192x8192): do NOT copy the TCOD map. Instead, mark-and-restore O(entities) cells. See roadmap for implementation details. Designed with #252 (Grid/GridView) API in mind — `entity.find_path()` will use entity's default walkability layer once #252 lands.

john referenced this issue from a commit

2026-04-02 05:34:26 +00:00

Add collision label support for pathfinding (closes #302)

john closed this issue

2026-04-02 05:34:26 +00:00