Sampling / stochastic · 7 min read
RRT / RRT*
Grows a random tree, then shortens edges. Sample random walkable cells, grow a tree with line-of-sight edges, rewire shorter links, then rasterise.
Why this category
Sampling / stochastic. Grow random trees or roll out simulated futures instead of exhaustively expanding every state.
How it explores
Exploring: 2 of 32 states checked
Why this category
RRT / RRT* sits under Sampling / stochastic. It does not expand every legal space-time state. It grows a tree by sampling random clear cells (with a bias toward the exit), connecting when line of sight is free, and rewiring nearby nodes when a shorter path appears.
That is why it shares a bucket with Monte Carlo Tree Search: random structure instead of exhaustive frontiers.
How it picks the next move
Up to a few hundred iterations: sample the exit about one time in ten, otherwise a random walkable cell that is not banned at any learned phase. Connect the nearest tree node if line of sight clears. Rewire neighbours within a small radius when the new node offers a cheaper cost.
When the exit joins the tree, walk parents back to the entrance and rasterise the waypoint list into orthogonal, tick-safe steps.
What it stores after a fail
Only the shared death calendar persists across attempts. The tree itself is rebuilt from scratch each call.
New "x,y,phase" keys shrink the walkable sample set (any-phase spatial walls) so later trees grow around corridors that already killed you.
More sampling / stochastic
Try it live
Run this algorithm on a built-in level, or paint your own grid and guards.