When two frontier cells share a priority, which comes out first decides which of several equal paths you get. Today you make that choice deterministic by breaking ties on insertion order, so equal-cost searches always return the same path.
Break equal-priority ties by insertion order so the heap is fully deterministic.
A min-heap ordered by priority alone leaves one thing to chance: when two items share a priority, which surfaces first is an artifact of swap order. In a search that is fatal to reproducibility, because two cells often reach the frontier with the same cost, and whichever pops first steers the path. To pin down a single answer we need a tie-breaker.
The simplest deterministic one is insertion order. Give every pushed item a
sequence number from a counter that ticks up on each push, and when priorities
are equal, prefer the smaller sequence, the one pushed earlier. Route every
comparison in push and pop through one less function so the rule applies
everywhere at once. Now the heap is a total order with no ties left to chance,
and combined with the fixed neighbor order from chapter one, every search built on it
returns exactly one path. This is the second half of the determinism promise the
whole project rests on.
type Item struct { Priority, Seq int; Cell Coord }// compare by priority, then by seq to break tiesfunc less(a, b Item) bool {if a.Priority != b.Priority { return a.Priority < b.Priority }return a.Seq < b.Seq}// use less(...) everywhere Push and Pop compared .Priority directly.// assign Seq from a counter that increments on every Push.