I have several pages that are unfinished because I can’t find an explanation I’m happy with. Sometimes while trying to come up with an explanation, I realize I don’t actually understand the topic as well as I thought! One of these topics is heuristics for the A* algorithm.While trying to understand the topic better, I came up with this example:
That wasn’t the first attempt at an explanation. But I was still unhappy with it. I decided to remake the diagrams again. The problem I’m trying to demonstrate isn’t specific to grids, so I decided to use a non-grid example. Conveniently, I had a non-grid example at the top of the A* page, so I adapted it for this page. I wanted to display numbers on the map but they didn’t fit in some of the smaller cells so I removed all the small cells.
I rewrote not only the diagrams but also the introductory text. But I’m still not happy with it! I think the grid has some advantages for visualization. I’ll try rewriting this section again at some point.
There’s still a lot more to work on. The introductory section is just to set up the motivation. Section 2 is about basic insight for improving the heuristic. Section 3 is about the solution. Section 4 is the code. Then there are several more sections, including demos with maps from real games.
I’ve been working on the differential heuristics page since 2015 and I’m still not happy with it! Maybe I need to rethink my strategy, either by reducing the scope of the page or by planning to rewrite the page after I publish it. I love the idea — it’s very little code (<20 lines?), can produce a big speedup, and not limited to grid maps like some other A* optimizations. My general heuristics page is in even worse shape. The demos on that page are completely broken. I feel bad that after all this time I still haven’t finished these pages. I’ll keep working on them (slowly).