Show HN: Visual A* pathfinding and maze generation in Python

135 points

2 years ago

I was fascinated reading through another recent HN submission about a highly efficient implementation of A* in Lisp, which got me thinking about how I could do something similar in Python. However, these kinds of pathfinding algorithms really need complex terrain/mazes with interesting obstructions to showcase what they can do and how they work. So, I started thinking about how I could generate cool and diverse random "mazes" (they aren't really mazes, but I'm not sure what the best term is). I got a bit carried away thinking of lots of different cool ways to generate these mazes, such as cellular automata, fractals, Fourier transforms, etc.

Then it turned out that many of the generated mazes weren't actually solvable, so I spent some time coming up with various strategies to test and validate the generated mazes and then modify them so they would work better for this purpose. I spent a fair amount of effort trying to optimize the performance as much as possible using tools like Numba where applicable, but I also got tired of the code bringing my very powerful machine to its knees. So, I tried to make it play nice with the rest of the system while also saturating a big computer with tons of CPU cores. This was done using concurrent futures with some tweaks, like using a Semaphore and lowering the CPU priority. People might find this project interesting just for these performance-tuning features.

I also spent a lot of time trying to make beautiful-looking animations that show multiple randomly generated mazes side by side, where you can see A* "races" as it tries to solve all the mazes at the same time, showing the current progress. When a solution is found, it is traced out on the screen. It's actually not that easy to get really slick/beautiful looking results straight out of Matplotlib, but if you use custom fonts and tweak a lot of parameters, it starts to look pretty polished.

Now you can just run this on a spare Linux machine and come back in a few hours to have a bunch of cool-looking animations to check out. By changing the grid sizes, you can get very different-looking effects, although larger grids can take a lot of compute power to render. Anyway, I hope you guys like it! I'm happy to answer any questions. I'm sure there are still some bugs, but it has been running pretty well for me and generating lots of cool-looking animations. Note: I know that the pulsating title at the top in the demo video is annoying— I already slowed this way down in the code but didn't want to wait for it to regenerate the video.

38 comments