News for hackers. Stuff that matters.
Re:Show HN: Algoviz, Interactive a* Pathfinding Visualization by forsythe on Sunday January 12, 2020 @03:59AM (#22025258)
I believe the push and pull is between optimal path and time to find the path. The heuristic dictates whether the algorithm will lean towards Dijkstra or Greedy or somewhere in between.

I got my knowledge about heuristics from here:

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics...

Re:Show HN: Algoviz, Interactive a* Pathfinding Visualization by nemetroid on Sunday January 12, 2020 @07:13AM (#22025932)
Whether a greedy heuristic is faster or not is dependent on the structure of the graph. For the example in the article about mountains and grassland, it makes sense that such a heuristic would speed up the search, since the algorithm can't get stuck in dead-ends.

But in a problem where the algorithm can get stuck in dead-ends, it's possible to construct examples where the greedy heuristic is (much) slower than plain Manhattan distance. Here's an example:

                xxx
                xEx
                x x
                x x
                x x
                x x
  Sxxxxxxxxxxxxxx x
                  x
   xxxxxxxxxxxxxxxx