Constraint search · 7 min read
Conflict-Based Search
Plan, find a death conflict, ban it, replan. Plan as if deaths were unknown, find the first calendar conflict, add that ban, and replan — CBS-style.
Why this category
Constraint search. Resolve conflicts by adding bans and replanning (CBS-style).
How it explores
Exploring: 2 of 41 states checked
Why this category
Conflict-Based Search sits under Constraint search. Classic multi-agent Conflict-Based Search plans individuals, finds pairwise collisions, and adds constraints. Here the "conflicts" are collisions between a planned path and the learned death calendar.
That is why it is not filed with plain A* Search: the outer loop is constraint generation and replan, not a single informed expansion.
How it picks the next move
Start with an empty constraint set. Plan with A* Search ignoring the real knownUnsafe set. Walk the resulting path against the true death calendar. On the first "x,y,phase" hit, add that key to the constraint set and replan.
Repeat until the path is clean or planning fails. The walk you execute is the first conflict-free A* Search route.
What it stores after a fail
Engine memory is still the catching cone as "x,y,phase". Conflict-Based Search then treats those keys as the conflict source for the next attempt's constraint loop.
Constraints inside one attempt are temporary planning bans merged onto an effective unsafe set. They are not a second long-term memory beyond the shared calendar.
Try it live
Run this algorithm on a built-in level, or paint your own grid and guards.