Informed search · 6 min read
D* Lite
Replans when the death map grows. A teaching stand-in for D* Lite: reuse a cached route until the death map grows, then replan with A* Search.
Why this category
Search that orders expansion using extra knowledge: path cost (including soft patrol risk), straight-line distance to the exit, jump pruning, or both.
How it explores
Exploring: 2 of 31 states checked
Why this category
D* Lite belongs under Informed search. Textbook D* Lite incrementally repairs a plan when edge costs change. This demo simplifies that story: keep the last successful path while the known-unsafe set size is unchanged, otherwise re-run A* Search with cost-so-far plus distance-to-exit.
The category is still Informed because expansion uses the same knowledge as A* Search. The lesson is "replan when the map of deaths grows," not a full rhs/g priority queue.
How it picks the next move
If a cached path still clears every "x,y,tick % period" check, return it. Otherwise run A* Search over space-time with soft patrol risk in the edge cost, hard bans from the death calendar, and priority g + h.
First time the exit is expanded, reconstruct and cache the result for the current unsafe-set size.
What it stores after a fail
Engine memory is still only the death calendar. Separately, this algorithm keeps a module-level cache of the last plan keyed by how many unsafe keys exist.
When a new catch grows that set, the cache is invalidated and A* Search replans from scratch with the larger blacklist — the educational stand-in for dynamic repair.
More informed search
Try it live
Run this algorithm on a built-in level, or paint your own grid and guards.