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

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.

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

I like this..I recently used A* to implement laying out connectors between nodes in a graph. I really like the abstraction of a heuristic function. I was able to add in all sorts of things to make the implementation work the way i want (penalise turns, crossing over lines etc.). This would automatically create "last resort" style solutions and minimise ugliness in the diagram.

I would be interested to hear what fraction of this script and README were generated by large language models. At first glance, the code contains a number of repetitive anti-patterns that 'feel like' they are Copilot-isms (e.g. large stacks of elif statements instead of using appropriate data structures), and the README is very verbose and includes a high fraction of filler words.

This would be neat to see applied to Vine Robots: https://youtu.be/eLVAMG_3fLg?t=153

---

They talk about the use of the pneumatic vine robots to nav rubble and caves etc - but if the vine robot could evaluate the terrain and use apropriate routing algo based on the nature of the terrain it was doing. they arent using vision necessarily in the vine robots - but if they could use terrain sensors that informed the best routing algo to use/accomplish goal that would be neat.

Another interesting thing about this would be to apply it to where vine-style micro-trenchers could know the patter of the lattice that will best be needed to accomplish whatever the stated newton bracing requirement were - then you could plop relative light foot pads onto a celestial body - then have these vine into the surface in such a way where you can begin to attach larger objects and very easily build foundations to large space structures - plus, as it maps out - you have an exact map of what your mycelium -like base foundation look like.

EDIT:

And you could grow the foundation as need - however, imagine a series of tubes mabe by these vinind robotw - that are later filled in (the robots) with structural hardening material -- you vine your robots into the mountian in sequences - first do a large outer lattice - and strucurally brace it with whatever material - then in the center space - vine into the core and fill those with explosives and tunnel. -- then you can snake through your exploded rubble - see whatst up - and deliver cables and hoses through the vine to a forward location...

A vine robot that tunnels - but its outer layer is a permiable filter and it has capillary features - but basically it unfulrs into being a well and the outer material is expanded do to corrugations in the design allowing debris filteres water to create a layer around the new pipe - and then capillaried up - or a pump in the core at the head of the water-wyrm.

(I need to figure out how to make some of these -- I love them.)

I think so too. Also, what's the point of using git with commit messages like that? https://github.com/Dicklesworthstone/visual_astar_python/com...

LoL.