Uninformed search · 6 min read
Iterative Deepening Depth-First Search
Depth-First Search, repeated with a rising limit. Depth-First Search repeated with a rising depth limit so the first success is at the shallowest workable depth.
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 47 states checked
Why this category
Iterative Deepening Depth-First Search sits under Uninformed search. Each deepening pass is ordinary Depth-First Search with a hard depth cap: limit 1, then 2, then 3, up to the tick horizon. No heuristic aims at the exit. Order still comes from the stack.
The rising limit is why it behaves like Breadth-First Search on success depth while keeping Depth-First Search memory. That is still Uninformed: the exit direction never enters the priority.
How it picks the next move
Planning loops over depthLimit from 1 to maxTicks. Inside a pass, push the entrance at tick 0 onto a stack and expand neighbours at tick + 1, skipping walls, visited space-time keys, and learned "x,y,phase" deaths. Stop a pass when the stack empties or the exit is found within the limit.
The first pass that reaches the exit reconstructs that path. Later deeper passes are never needed for that attempt.
What it stores after a fail
Same death calendar as everyone else: cone cells stored as "x,y,T % period". The next attempt restarts iterative deepening with a larger blacklist.
Because each deepening pass is goal-blind, a new ban can force a completely different winding route once a deeper limit finally clears the exit. Phase still matters: banned at phase 6 does not forbid phase 10.
More uninformed search
Try it live
Run this algorithm on a built-in level, or paint your own grid and guards.