Uninformed search · 6 min read
Bidirectional Search
Search from entrance and exit until the waves meet. Two Breadth-First Search fronts meet in the middle on the spatial grid, then the joined route is walked tick by tick.
Why this category
Real search over space-time states, but blind to where the exit is. Order comes only from the frontier structure (queue, stack, or iterative deepening), not from a goal heuristic.
How it explores
Exploring: 2 of 45 states checked
Why this category
Bidirectional Search is Uninformed: it grows a Breadth-First Search from the entrance and another from the exit until the waves touch. There is no distance-to-exit heuristic steering either front — only FIFO expansion on walkable cells.
Cells that appear in the learned death set at any patrol phase are treated as walls for this spatial meet-in-the-middle. That is a conservative ban, not a soft risk score.
How it picks the next move
Alternate expanding one layer from the start front and one from the goal front. When a cell is reached by both, rebuild the path from entrance to the meeting cell and from exit to the meeting cell, then join them.
The joined spatial list is rasterised into orthogonal neighbour steps with rising ticks, still obeying "x,y,phase" bans. The walk you see is that rasterised route, not a teleport along line of sight.
What it stores after a fail
Catch, store cone as "x,y,phase", replan. Because any-phase presence becomes a spatial wall, a death can permanently remove a corridor from Bidirectional Search even when another phase would have been safe — unlike A* Search, which can retime through the same cell.
No positive safe list is kept. Empty memory means both fronts see the full walkable grid.
More uninformed search
Try it live
Run this algorithm on a built-in level, or paint your own grid and guards.