r/Python • u/mutatedllama • Apr 01 '20
I Made This Maze Solver Visualizer - Dijkstra's algorithm (asynchronous neighbours)
10
2
u/Gekopoiss Apr 01 '20
Not sure if this is a limitation of the algorithm itself, but your implementation doesn't always seem to find the shortest path. For example, at 1:31, the path could be shorter if it cut some corners diagonally instead of moving horizontally and vertically around them - assuming the cost of moving diagonally is sqrt 2.
2
u/mutatedllama Apr 01 '20
You are correct - my implementation is the limitation here. I have not yet added diagonals as an option. Something to add to the list!
2
u/Gekopoiss Apr 01 '20
Yeah, I realised this myself just now. Considering that, it looks great! What did you use for the gui?
4
u/DenormalHuman Apr 01 '20
Good stuff! but I'd like to see it work on more complex mazes with many branching paths etc..
1
1
2
2
u/elburro908 Apr 01 '20
nice job! you should move it to the 3-D world. Gives a bit more challenge but it can be much fun.
2
2
2
2
u/jampk24 Apr 01 '20
Would be interesting to see in a maze that isnโt a one-way straight to the end.
2
u/ryanwithnob Apr 01 '20
The live updates of the calculated path got a verbal "woah" from me
1
u/ryanwithnob Apr 01 '20
If youre looking to extend functionality, there are algorithms that can generate random mazes. Might be worth looking into
2
2
2
2
2
Apr 01 '20
Nice
0
u/nice-scores Apr 01 '20
๐ท๐ฒ๐ฌ๐ฎ โ(๏พใฎ๏พโ)
Nice Leaderboard
1.
u/RepliesNiceat 4415 nices2.
u/cbis4144at 1890 nices3.
u/DOCTORDICK8at 1641 nices...
245628.
u/imbhuvneshat 1 niceI AM A BOT | REPLY !IGNORE AND I WILL STOP REPLYING TO YOUR COMMENTS
2
u/Fun-Visual-School Apr 01 '20
Awesome project! I could be a really useful tool for learners. Would you like to share the source code in a tutorial?
I'm working on a next-gen e-learning platform with tons of new features. One of them is the use of NLP to interconnect text passages with smart tooltips, I call them "nano lessons". Many other "easier" to implement features are centered around UX and graphics. Visualizations like these would be ideal nano lesson tooltips. Until the updated app is online I've created a community where we share top-notch visual tutorials such as yours. My intention is to connect with authors that understand what a visual tutorial means and you seem to master them. Hopefully, we can collaborate later on some cutting edge designs. I will reshare this post in r/VisualSchool since it's exactly the kind of content we are also envisioning for the platform.
Join us there if you want to connect and learn news about our progress. By mid-August, we should have a revamped prototype able to showcase many of the platform's features. In the meantime check out https://visual.school to see a short presentation of what we are preparing. I bet you will like this concept.
Keep up the good work!
1
u/TotesMessenger Apr 01 '20
1
1
Apr 01 '20
Is this used in video-game path-finding? I can see it being used not in real-time, but to generate a series of viable paths after a level is complete.
1
u/zrnest Apr 01 '20
Which library do you use to do the graphic user interface? (grid + ability to create walls with clicks, etc.)
1
u/blood_centrifuge Apr 01 '20
I am sorry I am a beginner. I am not able to visualise how dd you generate neighbors for each? What data structure did you use for this purpose as each node has node has at most 4 neighbors?
1
0
0
Apr 01 '20
[deleted]
1
u/mutatedllama Apr 01 '20
So when each node is checked, the functions to check each of the neighbours is meant to run asynchronously.
However I have since found out that it doesn't apply to this algorithm as it's CPU bound!
85
Apr 01 '20
[removed] โ view removed comment
64
u/mutatedllama Apr 01 '20
I think it is, and it's something I want to add so the user can switch between algorithms and see the different options. I went with Dijkstra because in all honestly it was the first one I heard of.
Before doing this I had no clue about pathfinding and when I heard about Dijkstra's algorithm I thought it sounded cool so I got to work on coding it. Firstly I put together an algorithm that worked without visuals (it was a codewars challenge) but it felt underwhelming. I saw some videos on YouTube, specifically one from Clement M where he had implemented the visuals beautifully in what I think is javascript. I took that as inspiration to adapt my code to a visualisation in pygame.
The satisfaction of seeing an algorithm being applied visually is huge for me. I struggle with mere concepts, and seeing it work in this way makes me feel like I really understand it.
21
u/jdk42 Apr 01 '20
Visualizing algorithms is one of the best ways of understanding, but also a very nice way of doing sanity checks - is the actually correct and does the algorithm actually work. Nice job!
11
u/livrem Apr 01 '20
The book Mazes for Programmers has great visualizations of paths through mazes and last time I checked the author still had a web site with some of them and javascript generators/solvers. Highly recommend.
2
u/KilroyWasHere189 Apr 01 '20
A* is hypothetically better but I don't think you'd see that much of a difference. Good job.
2
u/66bananasandagrape Apr 01 '20
Fun fact: if all of the distances in the graph are the same, then Dijkstra's algorithm is actually equivalent to breadth-first search.
0
Apr 02 '20
[deleted]
2
u/mutatedllama Apr 02 '20
Great suggestions - thanks! Love your one. I wish it was easier to get python in the browser.
14
3
u/livrem Apr 01 '20
Dijkstra's is one-to-many, not only one-to-one. It will beat A* for finding paths when they share a common source or goal.
10
u/AndreKuzwa Apr 01 '20
Great job man! I have recently finished the same project with option to chose between Dijskra and A* but I can clearly see that your Dijskra works much faster! Would you be so kind to share the source code, I think my implementation of the algorithm might not be optimal. Thanks and great job again!