[HN Gopher] Show HN: Visual A* pathfinding and maze generation i...
___________________________________________________________________
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.
Author : eigenvalue
Score : 75 points
Date : 2024-08-05 15:56 UTC (7 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| eigenvalue wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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).
| JBorrow wrote:
| 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 wrote:
| Pretty much the entire project.
| karolist wrote:
| I think so too. Also, what's the point of using git with
| commit messages like that? https://github.com/Dicklesworthsto
| ne/visual_astar_python/com...
|
| LoL.
| inhumantsar wrote:
| 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 wrote:
| 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.
| samstave wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| It is LLM generated code so I imagine it would be more work
| to create any semblance of a proper Python package
| structure.
| diggan wrote:
| > 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 wrote:
| 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 wrote:
| @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 :)
| eigenvalue wrote:
| 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 wrote:
| 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 wrote:
| 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!
| globalise83 wrote:
| Interesting how it looks just like rainwater trickling down a
| dusty windshield.
| yarg wrote:
| 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 wrote:
| 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.
| dheera wrote:
| ooh it would be super interesting to 3d print the maze and then
| watch ants solve it
___________________________________________________________________
(page generated 2024-08-05 23:00 UTC)