Wow. What an awesome explanation. I think my IQ went up 2 points after reading that. By the way, I do think you struck the right balance between intro and technical in the book. These were just some additional curiosity questions. The optimization tips are great. I can see how line-of-site would be better to check before pathfinding, especially on open-world maps.
For clarity on the benchmarking though, I’ll draw an ascii 2x4 ascii grid to properly differentiate the heuristics. S means start, M means Manhattan, D means Diagonal Distance, and G is Goal. Hopefully, it shows up nicely here.
+--+--+--+--+
| S|M1|M2|M3|
+--+--+--+--+
| |D1|D2| G|
+--+--+--+--+
Manhattan Distance = 4
Diagonal Distance = 3
Euclidean Distance = 2.23
Euclidean squared = 5
In 8-directional movement shown in the pictures, the only heuristic that predicts the distance is diagonal distance. Manhattan and euclidean squared overestimates the actual distance to goal. What I mean by overestimating is that the heuristic’s estimate is higher than the actual final path cost. What this means is that it will find a suboptimal path in the end, which is why you are getting the strange pathing on only those two. On the other hand, diagonal distance is spot on for 8-directional movement, as will be the pathing for euclidean distance which underestimates the actual distance. By underestimating, it will always be looking for the superoptimal path, which won’t lead you astray. So, the strange pathing, in my mind, is a misapplication of the heuristic. Redblob goes over those on his site. http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#manhattan-distance
He suggests manhattan for orthogonal; diagonal distance for 8-way; euclidean for any way (non-grid), and never to use the squared due to scaling issues.
The actual benchmark I’d be looking for would be a diagonal distance and euclidean and would be willing to bet that you wouldn’t give the strange pathing. Blob shows the formula for it on his page. I predict the diagonal distance should be faster than the euclidean because it is a cheaper calculation. But who knows in practice. lol I think you could then safely take out the closed list f-cost checks also…unless you want to keep it open to the possibility that someone might use inconsistent heuristics. The portals you mention is also an interesting concept.