-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$

closed as unclear what you're asking by David Richerby, Evil, Juho, Tom van der Zanden, Kyle Jones Nov 15 '17 at 1:19

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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.