john/McRogueFace

Fork 0

Behavior pathfinding architecture — support A*↔Dijkstra spectrum, multi-root, and custom heuristics #315

New issue

Open

opened 2026-04-18 01:03:01 +00:00 by john · 0 comments

john commented

2026-04-18 01:03:01 +00:00

Owner

Context

The Phase 3 behavior system (#300, #302) uses DijkstraMap as the distance-field source for SEEK/FLEE behaviors. This works, but it hard-wires the behavior system to one end of the pathfinding cost/accuracy spectrum. The engine already ships both DijkstraMap (exhaustive field from a root, via Grid.get_dijkstra_map()) and AStarPath (directed search with heuristic, via Grid.find_path()). Behaviors should be free to use either — or anything in between.

The pathfinding spectrum

With a heuristic function h(x, y → goal):

h = 0 → A* degenerates into Dijkstra (explores everything, optimal)
h = true_distance → A* is perfect (direct line, optimal)
Anything in between → weighted A*: faster than Dijkstra, potentially suboptimal vs. true A*, tunable per use case

A single A* implementation with a pluggable heuristic covers the whole spectrum. That is the design behind the libtcod-headless branch feature/pathfinding-nextgen-demo.

Upstream features — `libtcod-headless` branch `feature/pathfinding-nextgen-demo`

All four commits already exist on the branch; this ticket brings them into McRogueFace as first-class Python API and demonstrates them in the behavior system.

Custom A* heuristic callback (commit `a4080eba`)

TCOD_heuristic_func_t — callback type float(int x, int y, int gx, int gy, void* userdata)
TCOD_path_new_using_function_ex(...) — create pathfinder with custom heuristic and weight
TCOD_path_set_heuristic(...) — swap heuristics on an existing pathfinder
Heuristic dispatch in TCOD_path_set_cells() checks for a custom function before falling back to Euclidean

Built-in heuristics (commit `8bb0a468`)

Five pre-built functions passable to the callback slot:

euclidean (default, admissible, slowest-but-optimal)
manhattan (admissible on 4-connected grids)
chebyshev (admissible on 8-connected grids with cost-1 diagonals)
diagonal (octile — admissible on 8-connected grids with √2 diagonals)
zero (explicitly converts A* into Dijkstra — single code path, no branching required)

Multi-root Dijkstra (commit `b61b87e1`)

TCOD_dijkstra_compute_multi(...) — distance field from N root positions simultaneously, cell value = distance to nearest root
TCOD_dijkstra_compute_masked(...) — takes a uint8_t bitmap mask of roots (perfect fit for a DiscreteMap over the grid)
Refactored internal loop shared with single-root compute; no duplication

Use cases:

"Distance to any enemy with label threat" — one pass instead of N
"Distance to any of the player's allies" — FLEE target
"Distance to any exit tile" — navigation aid

Flee utilities (commit `162412af`)

TCOD_dijkstra_invert(...) — transforms a distance map into a safety map (far = high value). Close cells become dangerous, far cells become safe.
TCOD_dijkstra_get_descent(...) — follow the gradient to the nearest lower-distance neighbor. One-step lookahead.

Together these enable FLEE in three lines: compute multi-root Dijkstra from threats → invert → descent from current cell → move there.

Engine-side work

1. `PathProvider` abstraction on `EntityBehavior`

Currently the behavior struct types its path field as DijkstraMap (see #300, ROADMAP Phase 3a). Replace with a handle that can wrap any of:

Backing	Use case
`AStarPath`	Directed search to one goal
`DijkstraMap` (single root)	Omnidirectional field from one source
Multi-root Dijkstra	Field from any-of-N sources (labels, exits, threats)
Weighted A* + custom heuristic	Continuous spectrum tuning
Inverted Dijkstra + descent	FLEE

Common interface:

next_step(from_pos) -> cell | none
is_stale() -> bool
recompute()
to_heightmap() -> HeightMap (for persistence — companion to #294's DiscreteMap serialization)

2. SEEK / FLEE behavior redesign

Separate target policy from pathfinding policy:

Target policy: label, label-set, fixed cell, multi-cell, entity reference
Pathfinding policy: engine choice + heuristic + weight + collision label

Grid/turn manager resolves target → cells, hands to a PathProvider, asks for next step each turn.

3. Python surface

# Heuristic enum matching libtcod built-ins
mcrfpy.Heuristic.EUCLIDEAN
mcrfpy.Heuristic.MANHATTAN
mcrfpy.Heuristic.CHEBYSHEV
mcrfpy.Heuristic.DIAGONAL
mcrfpy.Heuristic.ZERO  # A* → Dijkstra

# Extend find_path with heuristic + weight
path = grid.find_path(start, goal,
                      heuristic=mcrfpy.Heuristic.MANHATTAN,
                      weight=1.2,
                      collide="solid")
# Or pass a Python callable
path = grid.find_path(start, goal,
                      heuristic=lambda x, y, gx, gy: abs(x-gx) + abs(y-gy))

# Multi-root Dijkstra
dmap = grid.get_dijkstra_map(roots=[(5,5), (10,10), (20,3)],
                             collide="solid")
# Or via DiscreteMap mask
mask = mcrfpy.DiscreteMap(size=grid.grid_size)
# ... mark cells ...
dmap = grid.get_dijkstra_map(roots=mask, collide="solid")

# HeightMap flee utilities (wrapping TCOD_dijkstra_invert / get_descent)
safety = dmap.to_heightmap().inverted()
next_cell = safety.descent_from(entity.cell_pos)

Demo strategy

The nextgen branch isn't merged upstream yet. The fastest path to upstream merge is demonstrating the features inside a real engine. McRogueFace behaviors are a natural fit: a side-by-side demo showing Dijkstra flood vs. weighted A* vs. multi-root flee, animated with guard entities, would be compelling review material.

Plan:

Ship this ticket against the feature/pathfinding-nextgen-demo submodule branch
Include a demo scene in tests/demo/screens/ (pathfinding comparison with live entity movement)
File an upstream PR to libtcod with the McRogueFace demo as reference
Once upstream, roll the submodule forward to the merged revision

#300 — Behavior data struct — currently holds DijkstraMap; becomes PathProvider
#302 — Pathfinding with collision labels — keep collision semantics, extend to any pathfinder
#294 — entity.perspective_map (companion Phase 4.5 — visibility storage, orthogonal to this)

Dependencies

Requires libtcod-headless branch feature/pathfinding-nextgen-demo in the submodule (or building against it directly until upstream merges).
No dependency on #294. These can ship in either order.

Out of scope

GOAP / utility AI / behavior trees — this ticket is about path computation, not goal selection
Navmesh / hierarchical pathfinding — grid-based only
Pathfinding cache invalidation policy — keep current scheme, extend cache key to include heuristic choice

## Context The Phase 3 behavior system (#300, #302) uses `DijkstraMap` as the distance-field source for SEEK/FLEE behaviors. This works, but it hard-wires the behavior system to one end of the pathfinding cost/accuracy spectrum. The engine already ships both `DijkstraMap` (exhaustive field from a root, via `Grid.get_dijkstra_map()`) and `AStarPath` (directed search with heuristic, via `Grid.find_path()`). Behaviors should be free to use either — or anything in between. ## The pathfinding spectrum With a heuristic function `h(x, y → goal)`: - `h = 0` → A* degenerates into Dijkstra (explores everything, optimal) - `h = true_distance` → A* is perfect (direct line, optimal) - Anything in between → **weighted A***: faster than Dijkstra, potentially suboptimal vs. true A*, tunable per use case A single A* implementation with a pluggable heuristic covers the whole spectrum. That is the design behind the `libtcod-headless` branch `feature/pathfinding-nextgen-demo`. ## Upstream features — `libtcod-headless` branch `feature/pathfinding-nextgen-demo` All four commits already exist on the branch; this ticket brings them into McRogueFace as first-class Python API and demonstrates them in the behavior system. ### Custom A* heuristic callback (commit `a4080eba`) - `TCOD_heuristic_func_t` — callback type `float(int x, int y, int gx, int gy, void* userdata)` - `TCOD_path_new_using_function_ex(...)` — create pathfinder with custom heuristic and weight - `TCOD_path_set_heuristic(...)` — swap heuristics on an existing pathfinder - Heuristic dispatch in `TCOD_path_set_cells()` checks for a custom function before falling back to Euclidean ### Built-in heuristics (commit `8bb0a468`) Five pre-built functions passable to the callback slot: - `euclidean` (default, admissible, slowest-but-optimal) - `manhattan` (admissible on 4-connected grids) - `chebyshev` (admissible on 8-connected grids with cost-1 diagonals) - `diagonal` (octile — admissible on 8-connected grids with √2 diagonals) - `zero` (explicitly converts A* into Dijkstra — single code path, no branching required) ### Multi-root Dijkstra (commit `b61b87e1`) - `TCOD_dijkstra_compute_multi(...)` — distance field from **N** root positions simultaneously, cell value = distance to nearest root - `TCOD_dijkstra_compute_masked(...)` — takes a `uint8_t` bitmap mask of roots (perfect fit for a DiscreteMap over the grid) - Refactored internal loop shared with single-root compute; no duplication Use cases: - "Distance to any enemy with label `threat`" — one pass instead of N - "Distance to any of the player's allies" — FLEE target - "Distance to any exit tile" — navigation aid ### Flee utilities (commit `162412af`) - `TCOD_dijkstra_invert(...)` — transforms a distance map into a safety map (far = high value). Close cells become dangerous, far cells become safe. - `TCOD_dijkstra_get_descent(...)` — follow the gradient to the nearest lower-distance neighbor. One-step lookahead. Together these enable FLEE in three lines: compute multi-root Dijkstra from threats → invert → descent from current cell → move there. ## Engine-side work ### 1. `PathProvider` abstraction on `EntityBehavior` Currently the behavior struct types its path field as `DijkstraMap` (see #300, ROADMAP Phase 3a). Replace with a handle that can wrap any of: | Backing | Use case | |---|---| | `AStarPath` | Directed search to one goal | | `DijkstraMap` (single root) | Omnidirectional field from one source | | Multi-root Dijkstra | Field from any-of-N sources (labels, exits, threats) | | Weighted A* + custom heuristic | Continuous spectrum tuning | | Inverted Dijkstra + descent | FLEE | Common interface: - `next_step(from_pos) -> cell | none` - `is_stale() -> bool` - `recompute()` - `to_heightmap() -> HeightMap` (for persistence — companion to #294's DiscreteMap serialization) ### 2. SEEK / FLEE behavior redesign Separate **target policy** from **pathfinding policy**: - **Target policy**: label, label-set, fixed cell, multi-cell, entity reference - **Pathfinding policy**: engine choice + heuristic + weight + collision label Grid/turn manager resolves target → cells, hands to a PathProvider, asks for next step each turn. ### 3. Python surface ```python # Heuristic enum matching libtcod built-ins mcrfpy.Heuristic.EUCLIDEAN mcrfpy.Heuristic.MANHATTAN mcrfpy.Heuristic.CHEBYSHEV mcrfpy.Heuristic.DIAGONAL mcrfpy.Heuristic.ZERO # A* → Dijkstra # Extend find_path with heuristic + weight path = grid.find_path(start, goal, heuristic=mcrfpy.Heuristic.MANHATTAN, weight=1.2, collide="solid") # Or pass a Python callable path = grid.find_path(start, goal, heuristic=lambda x, y, gx, gy: abs(x-gx) + abs(y-gy)) # Multi-root Dijkstra dmap = grid.get_dijkstra_map(roots=[(5,5), (10,10), (20,3)], collide="solid") # Or via DiscreteMap mask mask = mcrfpy.DiscreteMap(size=grid.grid_size) # ... mark cells ... dmap = grid.get_dijkstra_map(roots=mask, collide="solid") # HeightMap flee utilities (wrapping TCOD_dijkstra_invert / get_descent) safety = dmap.to_heightmap().inverted() next_cell = safety.descent_from(entity.cell_pos) ``` ## Demo strategy The nextgen branch isn't merged upstream yet. **The fastest path to upstream merge is demonstrating the features inside a real engine.** McRogueFace behaviors are a natural fit: a side-by-side demo showing Dijkstra flood vs. weighted A* vs. multi-root flee, animated with guard entities, would be compelling review material. Plan: 1. Ship this ticket against the `feature/pathfinding-nextgen-demo` submodule branch 2. Include a demo scene in `tests/demo/screens/` (pathfinding comparison with live entity movement) 3. File an upstream PR to libtcod with the McRogueFace demo as reference 4. Once upstream, roll the submodule forward to the merged revision ## Related - #300 — Behavior data struct — currently holds `DijkstraMap`; becomes `PathProvider` - #302 — Pathfinding with collision labels — keep collision semantics, extend to any pathfinder - #294 — `entity.perspective_map` (companion Phase 4.5 — visibility storage, orthogonal to this) ## Dependencies - Requires `libtcod-headless` branch `feature/pathfinding-nextgen-demo` in the submodule (or building against it directly until upstream merges). - No dependency on #294. These can ship in either order. ## Out of scope - GOAP / utility AI / behavior trees — this ticket is about path **computation**, not goal selection - Navmesh / hierarchical pathfinding — grid-based only - Pathfinding cache invalidation policy — keep current scheme, extend cache key to include heuristic choice

john referenced this issue

2026-04-18 01:08:16 +00:00

Entity.gridstate as DiscreteMap reference #294

No milestone

No project

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference

john/McRogueFace#315

No description provided.

Rows
Columns

Behavior pathfinding architecture — support A*↔Dijkstra spectrum, multi-root, and custom heuristics #315

Context

The pathfinding spectrum

Upstream features — libtcod-headless branch feature/pathfinding-nextgen-demo

Custom A* heuristic callback (commit a4080eba)

Built-in heuristics (commit 8bb0a468)

Multi-root Dijkstra (commit b61b87e1)

Flee utilities (commit 162412af)