motion planning · 01 May 2026

Wildfire: Grid A* vs. PRM in a Pursuit Game

python
planning

A competitive simulation between two planners. The “Wumpus” — a grid-based arsonist — walks an obstacle field igniting tetrominoes, while a firetruck with Ackermann steering chases the fires down and extinguishes them. The Wumpus plans with discrete A* on the grid; the truck plans over a Probabilistic Roadmap with Reeds-Shepp local connections. Five randomized 3600-second rounds decide a champion. Built for RBE 550 (Motion Planning) at WPI.

Simulation frame showing a grid field with burning obstacles, a firetruck, the Wumpus, and a roadmap graph of nodes and edges — Mid-simulation: orange/red cells are burning, the firetruck (blue) is en route to the nearest fire, the Wumpus (red) is off lighting new ones. The PRM graph is drawn in the background.

Full report (PDF) ↓ Explore the codebase ↓

The Ackermann kinematics, Reeds-Shepp trajectory generation, and two-phase collision checker carried over from the valet project the new work is the fire mechanics, the roadmap planner, and the two agents. Neither agent got a sophisticated high-level strategy on purpose — the point is the planners, not game theory.

Fire Mechanics

The field is 250 m × 250 m in 5 m cells, seeded with tetromino obstacles until 10% of cells are occupied. Each obstacle runs a small state machine:

State machine: Intact goes to Burning when ignited; Burning goes to Burned after 60 seconds or to Extinguished if the firetruck puts it out — Obstacle states. Neither terminal state can be reignited.

Ten seconds after ignition, a Wumpus-lit obstacle spreads fire to everything intact within 30 m; obstacles lit by spread only creep to their immediate grid neighbors. (Unlimited chain reactions were tested first — lighting a single obstacle auto-won the game for the Wumpus via cascade, so the rule was reined in.) A burning obstacle burns out after 60 seconds if the truck doesn’t get there first.

The Wumpus: Discrete A*

The Wumpus moves cell-to-cell and ignites obstacles adjacent to it, picking targets that trade off two objectives — far from the truck (so fires get time to spread) but not too far from itself:

score (𝑜) = 𝑑 (𝑝_{truck}, 𝑜) - 0.5 \cdot 𝑑 (𝑝_{wumpus}, 𝑜)

Navigation is textbook A* on the 50 × 50 occupancy grid with 8-connected moves and an octile-distance heuristic. Replanning happens whenever the target burns down on its own or the path runs out — and each replan costs so little it barely registers in the CPU budget.

The Firetruck: PRM

The truck is a Mercedes Unimog — 4.9 m long, 13 m minimum turning radius, 10 m/s top speed — which makes its planning problem fundamentally continuous. It gets a Probabilistic Roadmap built once at simulation start: 500 collision-free poses sampled by rejection, each connected to its 15 nearest neighbors (via a KDTree) when a Reeds-Shepp trajectory between them under 50 m long clears all obstacles at 1 m resolution.

A query then stitches: connect the start pose to the nearest reachable roadmap node, find an escapable goal pose — eight candidate headings are tried until one can connect back to the roadmap, so the truck never strands itself on arrival — run A* over the graph, generate dense Reeds-Shepp trajectories per segment, and smooth the result with 200 rounds of probabilistic shortcutting.

The escapability rule exists because unvalidated poses are traps:

Simulation frame with the firetruck wedged near obstacles, disconnected from the roadmap graph — The truck stopped at a pose with no collision-free Reeds-Shepp connection back to the roadmap — motionless for the rest of the run. The goal-pose escapability check prevents this; stopping mid-path to extinguish would reintroduce it, so the truck only extinguishes after arriving.

A rarer failure is the start pose itself being geometrically isolated from every sampled node — then the truck simply never moves:

Simulation frame where the firetruck's corner region is walled off from the rest of the field — A seed where the truck’s starting corner can’t reach the roadmap at all.

Results

Run	Seed	Wumpus	Truck	Winner	W-plan (s)	T-plan (s)
1	3235666703	264	214	Wumpus	0.039	2.809
2	3235666704	246	254	Truck	0.039	3.581
3	3235666705	236	260	Truck	0.036	2.790
4	3235666706	222	260	Truck	0.036	3.356
5	3235666707	276	230	Wumpus	0.034	2.831
Total		1244	1218	Truck 3–2	0.184	15.367

The truck took the series 3–2, but the efficiency story runs the other way: 1218 points over 15.4 s of planning ( 79 points per CPU-second) against the Wumpus’s 1244 points over 0.18 s ( 6900 points per CPU-second). Grid A* is orders of magnitude cheaper than building and querying a roadmap — the truck spends about a second up front on construction and another 1.5–2.5 s per run on queries.

Bar chart comparing total planning CPU time: the truck's PRM time towers over the Wumpus's A-star time — Cumulative planning CPU time per agent over all five runs.

Each planner fits its constraints: the Wumpus’s cell-by-cell motion is exactly what grid A* models, and its paths are grid-optimal by construction. The truck can’t turn tighter than 13 m, so only a planner with kinematically-correct local connections produces paths it can actually follow — and its paths are suboptimal at several levels (sparse sampling, k-nearest connectivity, partial smoothing), which matters less than reliably arriving.

The firetruck wins the fancy trophy.

References

Kavraki, L. E., Švestka, P., Latombe, J.-C., & Overmars, M. H. Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE T-RA, 1996.
Reeds, J. A. & Shepp, L. A. Optimal paths for a car that goes both forwards and backwards, Pacific Journal of Mathematics, 1990.
LaValle, S. M. Planning Algorithms, Cambridge University Press, 2006.
Geraerts, R. & Overmars, M. H. Creating High-quality Paths for Motion Planning, IJRR, 2007.