-3
$\begingroup$

I'm trying to build a maze solver using A* algorithm. The maze is a grid with movement allowed in 4 directions (up, down, left, right). If there's a starting cell (x1, y1) and a destination (x2, y2), which of these should I make my heuristic?

  1. Euclidean Distance
  2. abs(x2-x1)
  3. (x2-x1)^2 + (y2-y1)^2
  4. abs(x2-x1) + abs(y2-y1)

I'm leaning towards the euclidean distance because it seems intuitive but am unsure.

$\endgroup$
  • 1
    $\begingroup$ What have you tried and where did you get stuck? Have you implemented them all and let them compete? $\endgroup$ – Raphael Nov 8 '17 at 10:05
  • $\begingroup$ There probably is no general correct answer; which heuristic is better depends on what you mean by "better" and your inputs. $\endgroup$ – Raphael Nov 8 '17 at 10:05
  • $\begingroup$ It makes sense that some are inherently worse, though (such as OP's options 2 (ignoring y coordinates) and 3 (not admissible)). $\endgroup$ – Klaus Draeger Nov 8 '17 at 14:42
2
$\begingroup$

The best possible heuristic for A* is the actual length of the shortest path to the target that way A* can always select the next node in the optimal path. This is usually not possible to get so a approximation is needed.

The simplest heuristic is constant 0. This makes A* revert into dijkstra.

The closer the heuristic gets to the shortest path the better it is.

But if a heuristic overestimates then the node with the optimal path may get pushed down the queue and a less optimal path will get selected.

For a grid with only the 4 cardinal directions (and no obstacles) the optimal heuristic is the manhattan distance (option 4).

Option 3 is not a good heuristic because it will overestimate the distance which can lead to a non-optimal path being chosen.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.