I've been working on updating my pathfinding articles with interactive diagrams. While doing so, I realized that I don't like the way I've presented information in my pathfinding articles. Instead of just updating them in-place, I'm writing new tutorials and will eventually figure out how to stitch everything together.

A big one I've been working on is the introduction to A*. I started writing these notes in 1997 and have updated them over the years. The past few months I've been working on a replacement for this page. The page compares Breadth First Search, Dijsktra's Algorithm, Greedy Best First Search, and A*. Differences from the old page:

  • All the diagrams are interactive (of course)
  • I mention non-grids a little more (still not enough)
  • I use contour lines to compare the algorithms (not sure if this will make sense to people)
  • I show working Python code for each of the algorithms
  • I have supplemental material that includes the helper functions and classes needed for the search algorithms
  • I give some guidance on which algorithm to use

There are lots of little things (smoother animations, touch screen support, better code highlighting, better contour line visualization) that remain, but I decided to publish it 90% complete instead of delaying it to polish all those little details. Take a look at the new introduction and let me know what you think. Is it understandable? Do the contour lines help? Is it enough to help you implement A* yourself?



Todd Troxell wrote at July 16, 2014 8:11 PM

Best A* description I've ever seen!

Anonymous wrote at July 19, 2014 10:27 PM

Thank you for making everything so clear. I finally get it :)