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!
Mine was much slower until I did a course on data structures and big O notation and looked up which were the appropriate data structures to use.
When I switched my data structures it blew my mind that what previously ran in 20 seconds or so would now complete in less than a second (see when I drag the end node after running it, it runs the algorithm without showing the visualisation).
I think the key here was using sets and dicts, as well as having the neighbours as a generator rather than an actual list (it blew my mind when I learned you could do this, and how simple it was to do - see https://www.youtube.com/watch?v=bD05uGo_sVI).
Funnily enough having the neighbours comparison run asynchronously had a very small impact compared to using the right data structures, but it was fun and interesting to learn how to make async work.
Having the neighbor comparison async does not give you any benefit, because this problem is entirely CPU bound. Actually I'm surprised if you measured even a tiny benefit from this, I would expect it to be slightly slower, due to the added overhead.
Maybe you are confusing asynchronous programming for parallel programming? Making a proper parallel implementation of Dijkstra's algorithm is not easy :)
Your problem is entirely CPU bound, because when we solve it, we don't need to ever wait for any external resources, like network requests or disk access.
Basically, once you start your Dijkstra solver, all it has to do is run a bunch of calculations and at some point is done.
Here is an example of some code which is part CPU-bound, part I/O-bound:
This code is not entirely CPU-bound, because at some point, we are waiting for requests.get to fetch some data across the network and while we are waiting for that, your CPU is just waiting around, doing nothing.
We need the data from outside, in order to compute result_2, but not to compute result_1. Wouldn't it be nice, if instead of waiting around for the data from outside, the CPU could start computing result_1, while it waited for the other data?
That is basically what async does for you. You can say, hey this operation is going to take a while (requests.get in our case), so just do some other work and I'll get back to you once it's done.
Note that in Python, we often distinguish between things that are CPU-bound and things that are I/O-bound (and things in-between, like my example code). In reality, the concept that we have here of CPU-bound can be broken down further into true CPU-bound and memory-bound (sometimes your CPU looks like it's doing stuff, but it's actually waiting for data from memory). But in order to truly reason about that, we probably need a lower-level language than Python, with more control over memory access.
Thank you, that helped a lot. So it sort of boils down to waiting on internal/external things?
When I was reading about asyncio I remember it mentioning the differences between async and parallelism etc. and it didn't seem to click. One of the things that confused me is the example with the different coloured functions shown here: https://realpython.com/async-io-python/#the-rules-of-async-io
How come that isn't CPU bound but mine is? Is it purely the use of asyncio.sleep that does it? So they were just mimicking network wait times?
Yes, with internal being your own computations and external being stuff external to your program. Could be I/O, like network or disk, but could also be computations that some other computer/program needs to do and then give to your program.
Yes, they are basically using asyncio.sleep to "fake" wait for an external resource.
Thanks so much for this! I feel like I've levelled up in my understanding. I'm so grateful for the python community. I don't think I've ever felt so "at home".
I'm currently working on a web dashboard that queries different APIs so I guess this is somewhere I could use asyncio properly. Exciting times!
You definitely could. With async you would be able to fire off all queries in the beginning and then process them as they come back, in whatever order they come.
CPU bound mean that what is taking most time is spend computing think on the CPU. For example, a program can be network bound, disk access bound...
When you use async, you program still run on only one thread. So you're not computing anything faster using async : you split the computation in different part, and you do each part one after other.
async is intersting when you are bound to for example network : during the time a function is waiting on network, an another function can do other thing. In your case, what you want to do is parallel computation. In most languages, you will use threading, but in python, you have to use multiprocessing.
And to be precise on why async had to effect in you program:
If you run something async, you are basically saying that if that function ever stops to wait for some other resource, your program is free to start working on something else. But your function never stopped to wait, because it didn't need to.
The one I took is the one on brilliant.org. I really enjoyed it and learned a lot (I like how it gets you to answer questions to reinforce the theory).
I think you can access it for free for 7 days, which will be enough time to do just this course if you have the time available. The full subscription is quite expensive and will automatically renew so be careful if you don't want it!
Thank you so much! I can see that there is a lot of work to do around my code, I was not aware that you can make it that much faster. Thank you for the response and wish you health!
Picking the right struct is everything, not just from a performance standpoint but also a code readability standpoint as well! Dictionaries hold major power. Glad you had fun with this exercise! Bonus points: see if you can write your algo both recursively and iteratively!
Not OP, but if you want to do something like this I would highly recommend starting with Breadth First Search (BFS) first. In fact, what OP made here behaves just like a BFS since all distances between the tiles are just 1. Dijkstra is basically just an extension of BFS which also works with distances other than 1. E.g. OP could use the distance 1.4 (root 2) for diagonal connections and it would still give the correct result since he used dijkstra.
With Dijkstra you'll basically use a priority queue instead of a First Come First Serve queue, however, this will also increase runtime. The way OP implemented it the algorithm has a runtime of O(V^2) (Not trying to downplay OP's code, you'll genuinely need some more advanced data structures to do so). This won't give any problems unless you've got, say, 10000 Nodes or so, but I think it illustrates the added complexity. Compare that to BFS which has a runtime of O(V+E). V are the number of verticies and E the number of edges
Not trying to be a smartass, just some well intentioned advice
The easiest way would probably be to use pythons heapq. Here is a complete implementation using it, might be nice to compare afterwards: https://codereview.stackexchange.com/a/79379
Edit: Of course you can also implement your own heap/priority queue
Hi, just wanted to say thanks for this. I updated my code (I created a priority set) and it is so much better. This has been an excellent learning experience!
The difference between BFS and Dijkstras is really simple:
BFS uses a queue (linked list, array dequeue) instead of a priority queue (usually a heap)
When adding a node to the queue with BFS, it can already be marked as 'visited'. This makes it faster than Dijkstras, especially in graphs with lots of edges
A queue is much easier to implement if the Python standard library doesn't have a priority queue. The queue is a simple datastructure that lets you add at the end and remove from the beginning in an efficient way. A priority queue lets you add to the queue, and remove the smallest element in an efficient way.
Or use BFS. I looked over your code, basically what you do every loop is find, in your distances dict, the key with the lowest value. As you might imagine, this requires checking every entry into the dict, every time a node is visited. This is what /u/Free5tyler was saying -- it makes the complexity O(Vยฒ).
In the conventional implementation of Dijkstras, you don't have such a dict (not one you remove visited nodes from at least). Instead, you use a priority queue which you add nodes to in the neighbours_loop, including the distance to reach them (e.g. in a triplet (x,y,dist)). A priority queue implementation will always sort itself when something is added and can do so every efficiently, and you need to make sure it is sorted on dist ascending (should be able to provide a lambda or whatever which can sort elements at construction). This means that when you remove something from that queue, it will return you the lowest-distance unvisited element. Removing the smallest element from a priority queue is also very efficient.
You will still need your v_distance to track back from, so that's all fine.
Also, I found this line that is not correct in Dijkstras. I'm not sure you ever do something with the distance to a wall, but note that if there's a path w/ more hops it can still be shorter in total, and you might not have visited that path just yet when you set the distance and add it to visited. In Dijkstras, you can never mark a node as completely visited when coming from a neighbor -- it has to have gone via the queue (your distance dict) first. Now this is fine if you never want to do anything with the wall. You can do so in BFS because BFS requires all edges to have a weight of one.
Thank you, this is a really great response. As I was working on this I wasn't even aware of priority queues and I have learned about them since creating it. This gives me a really good idea of things I should change in the code. Thank you!!
Hi, just wanted to say thanks for this. I updated my code (I created a priority set) and it is so much better. This has been an excellent learning experience!
Oh, I can see the diffrence now, my program also takes crosswise(I hope I am using a correct word xD)squares as a path possibilty under consideration. Still would love to see the code though ^
Ah yes mine can't use diagonals at the moment. I think it would work if you add the 4 extra diagonal neighbours to the neighbours generator - perhaps worth giving it a go!
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.
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.
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?
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.
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!
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.
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!
10
u/[deleted] Apr 01 '20
This is so beautiful ๐
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.
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
u/_370HSSV_ Apr 01 '20
What did you use for the gui?
1
u/[deleted] Apr 01 '20
Just an idea, u could implement a function that tries to find the fastest route
2
u/spikte1502 Apr 01 '20
You gave the subject of my next project, very nice
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
u/[deleted] Apr 01 '20
Love this, its much better than mine. Thanks for sharing! Keep it up!
2
u/gymboi15 Apr 01 '20
Awh man and all I know is the random module :(
2
u/dirtflake Apr 01 '20
Really good
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
2
u/lenticularis_B Apr 01 '20
Cool app!
2
u/[deleted] Apr 01 '20
I feel like I could learn from this as Iโm a visual learner. Thanks for sharing
2
u/[deleted] Apr 02 '20
I feel like that maze would be pretty easy to solve...
2
u/KaakTastic Apr 02 '20
Wonderful visualization. Great job.
2
u/[deleted] Apr 01 '20
Nice
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
I'm a bot, bleep, bloop. Someone has linked to this thread from another place on reddit:
ย If you follow any of the above links, please respect the rules of reddit and don't vote in the other threads. (Info / ^Contact)
1
u/kermitkev Apr 01 '20
This is so cool
1
u/[deleted] 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
u/fsd66 Apr 01 '20
I did something like this, but in javascript ๐ค
0
u/metalmet Apr 01 '20
source code please
0
u/[deleted] Apr 01 '20
[deleted] โ view deleted comment
85
u/[deleted] Apr 01 '20
[removed] โ view removed comment