r/Python • • Apr 01 '20

I Made This Maze Solver Visualizer - Dijkstra's algorithm (asynchronous neighbours)

1.9k Upvotes

72 comments sorted by

View all comments

Show parent comments

23

u/mutatedllama Apr 01 '20

Awesome! and thanks for your comment!

My code isn't the best, but here is the repo: https://github.com/ChrisKneller/pygame-pathfinder

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.

0

u/[deleted] Apr 01 '20

[deleted]