Reference

The three searches

Every path an NPC walks is one of these searches running under the hood. They differ in what they optimise and how hard they work to do it. Back to the lab anytime: Open the search lab →

• Breadth-first search (BFS)

  Explores outward in rings, one step at a time, treating every move as equal. It finds the path with the FEWEST steps — but because it ignores terrain cost, it will happily walk straight through expensive ground. It also expands a lot of cells, since it fans out in every direction.

• Dijkstra’s algorithm

  Always expands the cheapest-total-cost cell next, so it guarantees the lowest-COST path even when some ground costs more to cross. With no sense of WHERE the goal is, though, it still explores in every direction — thorough but not aimed.

• A* (A-star)

  Dijkstra plus a heuristic — an estimate of the distance still to go. As long as that estimate never overshoots (it is "admissible"), A* is guaranteed to find the same lowest-cost path as Dijkstra, but it aims toward the goal and so finalizes far fewer cells. Same answer, much less work.

• The heuristic

  The heuristic here is Manhattan distance: how many grid steps away the goal is, ignoring walls. It never overestimates, which is exactly the condition that keeps A* correct. A better (but still admissible) estimate means even less searching.

The takeaway: all three are correct, but the right one depends on what you are optimising and how much compute you can spend. Try a world →