Greedy Best-First Search

Greedy Best-First Search is Informed by a single idea: expand whichever open state is closest, in Manhattan distance, to the exit. It throws away accumulated cost. That is why it is fast to plan and why it can commit to a bad corridor early.

The heuristic is the information. Without it, Greedy Best-First Search would have no reason to prefer one frontier state over another.

Priority queue keyed only by distance to the exit. Pop the closest-looking state. If it is the exit, reconstruct. Expand neighbours at tick + 1, skipping walls, visited keys, and learned "x,y,phase" deaths. Never add the soft patrol risk into the priority. Risk only matters if it was learned as a hard ban from a previous catch.

In the animation, watch how little of the grid gets explored when the heuristic points a clear way around the red zone. That thrift is the point, and also the trap when the heuristic points through danger that has not been learned yet.

Catch, cone cells stored as "x,y,phase", full replan. Greedy Best-First Search still aims at the exit. The blacklist only removes illegal arrivals. If the beeline is blocked at the phase it wanted, it will take another approach that still looks close to the door, which is why later attempts can still feel aggressive around patrols until more phases are learned.

No positive safe-at-tick-t list is kept. Empty memory means the whole walkable grid looks fine.