1 Comment

A* Path Finding Algorithm Visualization

Here's a fun little project I've been working on recently. Try it out below and then I'll blab a bit. Just click two nodes and the algorithm will attempt to find the shortest path between the two points. (fullscreen version)

I'd been researching path finding algorithms, particularly A* which seemed to be standard shortest path algorithm when you know where your target is (otherwise, check out Dijkstra's algorithm), and I found myself trying to form a mental picture of how the algorithm worked. This is pretty standard for me - I can read a bunch of pseudo code over and over, but complex algorithms don't usually click until I can build a visual model of how they work in my head. 

So, I started throwing this thing together. The code is basically a just divs, some CSS animations, and jQuery - no D3, though if I do any more of these I'll probably look in that direction. There are plenty of other path finding visualizations on the web, but they tend to be super fast and/or just show the final result of the algorithm on a grid-based map. I wanted to slow things down so I could really watch the algorithm in action and see how it works, which paths it attempts to traverse, how often it reaches dead-ends, etc.  

Now, I can say without a shadow of a doubt, I really understand this algorithm!

This was a super fun and educational exercise so I'd like to do more of them in the future. Here's a link to the github repo for anyone who's interested. Thanks for reading!

1 Comment