Uninformed search · 6 min read
Depth-First Search
Commits to a direction, backtracks only when stuck. A stack instead of a queue: systematic but goal-blind, great at finding a route and poor at finding a good one.
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 46 states checked
Why it is Uninformed
Depth-First Search is Breadth-First Search with the queue swapped for a stack. It is still Uninformed: it explores space-time states exhaustively within the tick horizon without aiming at the exit or weighing risk.
Unlike Random Walk, Depth-First Search keeps a visited set, so it will not thrash the same (x, y, tick) forever. Unlike Breadth-First Search, the first neighbour pushed has nothing to do with fewest ticks. Expect long, winding routes.
How it picks the next move
Push the entrance at tick 0 onto a stack. Pop the newest state. If it is the exit, reconstruct and stop. Push legal neighbours at tick + 1 (walkable, not visited, not a learned "x,y,phase" death). Keep plunging down whichever branch was pushed last until boxed in, then backtrack via the stack.
The red squares in the animation are hard bans for this plan. Depth-First Search will snake around them, but not because it scored them as risky. They are simply illegal expansions.
What it stores after a fail
Identical learning loop to the other searches: catch, store cone cells as "x,y,phase", replan from scratch with a bigger blacklist. Phase matters. A death at tick 6 does not forbid the same tile at tick 10 unless phase 10 was also learned.
Depth-First Search may find a totally different winding route after a single blacklist update, because its expansion order is brittle. That is a feature of stack order, not of clever retiming.
More uninformed search
Try it live
Run this algorithm on a built-in level, or paint your own grid and guards.