HN Explorer

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

135 points by eigenvalue ↗ HN
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.

47 comments

[ 3.5 ms ] story [ 114 ms ] thread
eigenvalue
Here's a direct link to the YouTube demo video: https://www.youtube.com/watch?v=iA6XJRE6CTM

Also, here's the Lisp implementation post that inspired me (and which I based my Python code on):

https://news.ycombinator.com/item?id=41145528

And here are a few other sample videos using different settings-- I'll add more during the day as they finish generating:

https://www.dropbox.com/scl/fo/q13cxuvgy8vxr3ksi06uw/APkL57-...

ryandrake
Ugh, it would be nice to be able to pause the final frame of animation to compare each generated path. Instead YouTube replaces it with their obnoxious "next video" suggestions. If you generate another video, I'd suggest artificially "freezing" the results frame for about 5 seconds so it can be seen and compared.
eigenvalue
Check out the other sample videos I linked to in my comment, those are easy to pause in VLC. I can look into extending the final frame for a few seconds, too.
noufalibrahim
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.
eigenvalue
Yes, doing it that way sort of goes beyond the standard A* and becomes more of a "build your own custom pathfinder toolbox" where you can insert any additional considerations you have in your specific problem domain. Sort of like how you can add different factors to a loss function in machine learning (like trying to minimize non-zero parameter count for LASSO in addition to minimizing mean squared error).
dietr1ch
The heuristic is the wrong place to adjust solutions, just change the costs on the original problem and adjust the heuristic if necessary.

I guess that for your intention, using an inconsistent heuristic that over-estimated costs and resulted in sub-optimal solutions was fine because you wanted sub-optimal solutions in your penalty-free problem, but this was better modeled by a modified problem that either penalized or forbid certain solutions in the original problem.

noufalibrahim
That's a good point. I didn't think of like that. I think the "don't allow" cases might be modelled in the heuristic but my initial graph was just all open.
dietr1ch
I'm not sure what you mean by the initial graph being just all open, but I'm still convinced that modelling things only in the heuristic is wrong. Here's why it fails eventually,

Hacking only the heuristic side will seem to work as intended on short paths, but as the f-value (g+h) naturally starts being dominated by g as the solutions become longer, you'll see that the hints at what not to do embedded in the heuristic will start to seemingly become neglected by A*

noufalibrahim
When I said "all open", I meant that none of the constraints were included in the graph I started with. All paths between the two endpoints are equally valid. I wanted then, to find paths that didn't overlap with other connectors, that didn't go too close to other objects and didn't turn too much. These, I modeled by adjusting the heuristics so that such paths are penalised.

I see your point. The penalties right now are "big" but only when compared to the values of g at the beginning. As it moves forward, even the big penalties will be swamped by the g and hence, the heuristics will be ignored.

I'm not sure about how else to model this though.

JBorrow
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.
crowdstriker
Pretty much the entire project.
[dead] wmichelin
[flagged]
[deleted]
(comment deleted)
karolist
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.

inhumantsar
I've done that when testing CI pipelines or pushing up minor tweaks to a personal project... but committing and pushing so often.. maybe OP was editing right in GitHub?
eigenvalue
I was developing on one remote machine and running/testing it another machine. This is just a fun little learning/diversion project... I don't really care about it having a meticulous git commit history.
[dead] preciousoo
[flagged]
[deleted]
(comment deleted)
Kiro
I use git like that. It's my backup solution. There's no logic to the commits. I just commit and push when I feel I've done enough that it would suck if my computer fails and I lose it.
[deleted]
(comment deleted)
[deleted]
(comment deleted)
samstave
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.)

szykbi
seems this was LLM generated? I dont mind people using LLMs to generate boilerplate, but at least apply some basic oop fundamentals to make it readable. the bar is on the floor
eigenvalue
I generally hate "OOP" style code. I like individual functions that stand on their own. Also, it makes it much harder to use numba to optimize the code if they are methods inside a huge class.

In any case, this project is about making cool looking and educational animations of a pathfinding algorithm and generating interesting and diverse mazes to test it on. Not about making some amazing and modular reusable system.

szykbi
I suggested OOP because its a baseline for readability. Also your code has at least 1 class already lol. Defending having everything in one file for a project like this is a bit unbelievable.
uncivilized
It is LLM generated code so I imagine it would be more work to create any semblance of a proper Python package structure.
dietr1ch
You wanted educational visualizations and you got them, but keeping the code organized to allow students to inspect it seems way more important than optimizing, especially if you are already using a slow language.
diggan
> but at least apply some basic oop fundamentals to make it readable

Heh, and here I sit, usually complaining about the opposite!

"Don't make it so OOP gratuitous so it gets a bit easier to read and understand" is probably something I've said more than twice.

Guess what's readable or not is subjective :)

eigenvalue
100% agree with you on this-- I find a functional approach, where there is no state to deal with, just input arguments and return values, to be much much easier because you can reason about each function separately.
YeGoblynQueenne
@eigenvalue, some comments suggest the project code and README was LLM-generated. Could you say to what extent that is the case?

Edit: I'm curious about other repositories under your account also. For example, this one:

https://github.com/Dicklesworthstone/introduction_to_tempora...

The content of this repo is an essay on temporal logic that seems at once unnecessarily verbose and lacking in concrete information (e.g. lists of "logical operators" -i.e. logical connectives and quantifiers- and their examples but nothing about logical interpretations, in an essay about proofs). If that's the case, then I'm curious what is the motivation of having that on github. If I were really paranoid I'd think you're trying to hasten self-training model collapse :)

[deleted]
(comment deleted)
eigenvalue
I do use LLMs to assist in writing and debugging code, but if you think there is any LLM model in the world that could easily conceive of and generate the code for this pathfinding project in a couple shots, I welcome you to try it and see what you get. I conceived of the idea of the project and how it would work, the various different maze generation techniques, how to optimize it, what the animation should look like, etc., with massive amounts of testing and evaluation along the way to figure out the best approach and how to make the output plots look nice.

Same with the README. It's the result of tons of manual intervention, many many steps of iteratively revising and changing, adding sections, improving sections, etc., and it's ultimately driven by the code itself which it is describing. The people who think it's so easy should try themselves and see if they can make anything that anyone thinks is cool or interesting with one or two LLM prompts.

YeGoblynQueenne
Thank you for the reply and sorry if it was indiscrete. To be honest I was doubtful myself that your mazes project was all LLM generated. To be more honest if it had been, I'd be very disappointed because I found it interesting and novel (so I'd be disappointed to myself, you see, for not spotting the LLM-ness).

Also because I've done some recent work on generating and solving mazes, and other grid-based maps, with a form of symbolic learning and I wanted to link to it, in case you (or someone else) are interested:

https://github.com/stassa/ijclr_2024_experiments/tree/master

When I was writing that paper I was looking for a quick way to generate grid-based maps of different kinds, not just mazes, so I would have been interested in your project. I might be able to use it in the future, if I do more work on mazes.

Edit: um, sorry for the harsh criticism of the temporal logic essay. I do think it needs more concise language, and more formality too.

eigenvalue
No problem. I also don't think you should be worried or disappointed about finding something interesting no matter what its provenance. As long as it's correct/fascinating (and in the case of this project, the animated output itself shows that it's doing something useful/interesting), none of that should really matter ultimately. I'll take a look at your project, sounds cool.

As for the temporal logic essay, you're very welcome to fork it and submit a PR to make something more formal/correct, but keep in mind that my goal with that was more explaining things in an intuitive way-- there are plenty of rigorous but impenetrable tomes already about mathematical logic!

YeGoblynQueenne
Returning to this conversation I think I misread your previous comment: you are saying you did use an LLM to generate some parts of the code and text in your repository, just not all, or not all in one go, or with only a couple of prompts. Is that correct?

>> I also don't think you should be worried or disappointed about finding something interesting no matter what its provenance.

I disagree. There are two issues here: accuracy, and novelty of the contribution.

Regarding accuracy, by now everyone understands that LLMs are champion bullshitters and you can't rely on anything they generate to be factually correct. My most recent experience with that is helping a student with their MSc dissertation. The dissertation included references to four papers whose descriptions had nothing to do with the actual, published papers. I happen to know those papers well since they come from my PhD advisor and one of his students and I had studied them during my own PhD. It was clear that whatever entity had come up with the description of those papers had imagined their content based on some words in the title, e.g. one paper about learning robot strategies through higher-order abstraction and predicate invention was described as contributing a novel way to control a robot hand- completely absent from the real paper. I know the student used ChatGPT enthusiastically and it was obvious that the imaginary description of the real paper came from it. As others have argued, if we keep polluting knowledge environments (the internet, publication records) with automatically generated bullshit there will come a time when we can't tell it apart from the real content.

As to the value of such LLM-generated bullshit for learning, for the person using the LLM or those reading the generated content, it is obviously very near zero, or worse, negative. For example, it was clear to me that the student learned nothing from the four papers they cited; they probably didn't even read them. And if you were to ask them now about the content of those papers they would just repeat the LLM-generated bullshit in their dissertation. In other words: negative learning value.

Regarding novelty, if some material can be generated by an LLM, maybe with a bit of elbow grease to come up with the right prompts, then there is no real point in sharing it as an interesting piece of work- just like I wouldn't copy some code or text found on the internet in my own web page or repo, and then point to my copy as something interesting, I would also not do that for whatever comes out of an LLM. Anyone who is interested in the subject can just generate it themselves with an LLM. Maybe they can even do a better job than me with the prompts, or have access to a better LLM.

That's also one reason that I don't think it's a good use of my time to suggest improvements for the temporal logic essay on your repo, if it's basically LLM-generated (with many of your prompts as input). What's the point of doing that? The LLM won't learn anything from my suggestions. It will happily generate the same kind of essay the next time someone else calls it. With text written by a human you can at least hope that you will help them improve their future work, if you make suggestions. But an LLM?

Anyway sorry that this comment is rather more critical than my last one. I'm not accusing you of doing anything wrong, to be clear. I really advise exercising great caution when sharing work generated by an LLM, even if you feel you have contributed a substantial amount of work and are very excited about the results. At the very least you can expect skepticism of the kind expressed by other comments in this post, which I'm guessing is not the reaction you are aiming for.

Finally, if people can easily tell your code or text is generated using an LLM maybe that's an indication that it needs more work.

Kiro
I wouldn't be surprised if the majority of things shared contains some LLM generated code. Everyone I know is using Copilot or some other code assistant and a few even use things like Cursor where the LLM takes the driver's seat. This is not the novel anomaly you make it sound like.
YeGoblynQueenne
Where do I say anything about an "anomaly", let alone a "novel" one?
globalise83
Interesting how it looks just like rainwater trickling down a dusty windshield.
yarg
I'm wondering if there's someway of abusing the heuristic to produce an absolute monster of a maze;

Somehow make it so that the top ~70% of next steps in the queue are never the next step in the solution (I'm too tired right now to come up with any sort of answer, but my guess is that it wouldn't be possible to generate a planar maze that way).

eigenvalue
You could make a very winding maze that has a lot of false corridors that don't lead anywhere, so the algorithm would be forced to waste a lot of time following them to the end. Especially if many of these are "near solutions" that get close to the goal but can't get all the way.
[dead] volkerp
[flagged]
[deleted]
(comment deleted)