Spent a bunch of time reading about Heuristics and A* applications. I also did a ton of testing between the Manhattan Distance and Euclidean Distance heuristics and came up with some surprising results.
Lock the random seed so we can generate the same dungeon each run.
Test between closed list re-evaluation and non-closed evaluations.
Use Manhattan and Euclidean heuristics as test variants.
Quantify by tracking overall algorithm time, path size, and total tile (node) evaluation count.
Since I am way too lazy to post a full-on results table (it's rather large), here are my final notes:
Euclidean heuristic did 10x node evaluations as the non-closed variant.
Manhattan heuristic did 3x what the non-closed Euclidean heuristic did, but it did not matter which closed list strategy was used, the result was always the same.
Manhattan had a much more optimal path by ~1-2% path size reduction.
Runtimes for both were very similar around ~1 millisecond per run (using a very large search space).
In short, the Manhattan heuristic (for my tests) is just as fast with the bonus of re-evaluating the closed list for possible late path optimizations and always returned the most optimal path.
The Manhattan approach looks something like this:
All those green tiles are sitting on the open list when the algorithm terminates. You can clearly see something else is still wrong with the tile evaluation method I am using and this does not even show what was on the closed list!
Which led me to some additional reading about scaling G and H costs. The key finding here is that A* computes f(n) = g(n) + h(n). To add two values, those two values need to be at the same scale. If g(n) is measured in hours and h(n) is measured in meters, then A* is going to consider g or h too much or too little, and you either won't get as good paths or you A* will run slower than it could. Horizontal and vertical movement were scaled down to 1 from 10 and diagonal movement was scaled down to 2 from 14.
After proper cost scaling, I added a new Diagonal Heuristic (sometimes called the Chebyshev Distance) to use in place of Manhattan and Euclidean variants I was experimenting with before. This is because for my application moving diagonally will cost a unit more than moving in straight lines. I know have paths which look the same, but evaluate much fewer tiles (in most cases):
A huge difference in total tile evaluations and much faster generation!
areudirty
yousharknotpass
amandla
gummygunk