This page demonstrates a couple tips on using A*. I actually thought I had a good handle on how A* worked, but did not realize it could degenerate so badly in certain cases. Specifically, things get pretty bad with large distances, relatively few obstacles, and using certain heuristics. The demo above should clearly indicate the problem (the path is in purple, but grey denotes tiles visited)...
I used rot.js to develop a roguelike for 7drl 2016 (this is my 4th time entering).
I found the behavior of rot's A* implementation really surprising. I figured that A* would basically zoom straight to the goal. And I thought that, with very few obstacles (an open world map), the number of tiles visited should be at a few multiples of the path length. Wrong!
I tried pathfinding a distance of 1,000 tiles and noticed rot was visiting over 4 million tiles to do it. Uh oh. Why was rot visiting a giant rectangle and why the hell was it moving away from the goal?
In hindsight, it makes perfect sense. Rot defaults to using an 8 direction topology and correspondingly a Diagonal heuristic (meaning diagonal moves are as cheap as orthogonal moves). That matches the cost of movement in my game, but doesn't work well for pathfinding. The algorithm moves diagonally "away" from the goal because it seems that it can return just as quickly as if it had gone in a straight line. In fact, you can see that every tile in that giant rectangle is part of an optimal path to the goal. So it visits all of them.
That's why I was seeing 4 million tiles visited! It roughly corresponds to the distance (1000) squared and then repeated visits for each neighbor.
There are two ways to solve this problem. One is to use another heuristic such as Euclidean distance or Octile distance. This way, it's no longer cheap for the algorithm to wander off the straight path. The second approach is to use tie breaking. To avoid visiting the giant rectangle, we can favor first searching tiles that are closest to the goal. Either approaches seems to work fine and you can play around with them in the demo above.
I found these pages very useful in understanding this stuff.
During 7drl, I actually wrote my own pathfinding algorithm and the original purpose of this page was to show it off (before I realized a couple lines of code could fix rot's implementation). Mine was pure garbage code that I wrote at 3am and not at all optimal. And actually, the solution I ended up with during 7drl was neither writing my own algorithm nor improving the one in rot. Instead, I just broke up my long distance pathfinding into chunks. If you have to pathfind large distances, that's a great solution as well!