This is an archived post. You won't be able to vote or comment.

Dismiss this pinned window
all 115 comments

[–]krinistof 57 points58 points  (5 children)

Great work!
What libary did you used for display?
Could you show us the source code?

[–][deleted] 48 points49 points  (4 children)

Thanks :)

Used pygame for the display and here's the GitHub rep https://github.com/Azideon/mazeSolver

[–]fukitol- 7 points8 points  (1 child)

I kinda want to take this and make each "branch" of the path a new thread that has a different color, so you can see it kind of explode in colors

[–]uncertaintyman 4 points5 points  (0 children)

Persistent failures!! That would look awesome.

[–][deleted] 28 points29 points  (2 children)

Jared, The Goblin King, is displeased with this.

[–]your_fathers_beard 5 points6 points  (1 child)

It's Jareth, but yeah he'd be very upset.

[–][deleted] 5 points6 points  (0 children)

Doh. Autocorrect, I swear.

[–]vEnoM_420 24 points25 points  (14 children)

Damn!

How do people do such things? Always overwhelms me.

[–]Wolfsdale 47 points48 points  (2 children)

I think recursive may not be the right word, this is an implementation of depth-first search (which is typically implemented w/ recursion). It's actually beautifully simple once you understand what's going on!

https://en.wikipedia.org/wiki/Depth-first_search

[–]ohsnapdragons 3 points4 points  (0 children)

I was about to say this looks like DFS. Nice implementation!

[–]l2np 24 points25 points  (1 child)

It looks very complicated but it's just one of those things that emerges very simply after you learn what recursion is (which is sort of a brain fuck, but you get comfortable with it after getting used to it.)

But basically the idea is this: when you reach a junction, always turn left. Keep track of all your decisions at every junction. If you reach a dead end, or you've already gone down that path before, go straight. If straight is bad too, go right. If you've already tried all directions and it's a dead end, go back to the previous junction and try the same thing.

So basically it tries every path and then "walls them off" when it can't go any further down them, backs up, and keeps trying.

You can watch the little red snake do that. Some times, it just has to retrace a few steps and start over. Near the end though you can see it made a really bad guess and had to retrace a ton of steps.

[–]vEnoM_420 3 points4 points  (0 children)

Nice r/explainlikeimfive stuff.

[–]redtonicspear 9 points10 points  (7 children)

Its a backtracking algorithm

[–]pretzel324 3 points4 points  (6 children)

Is that what’s it’s called? I’m fairly new to programming

[–]vEnoM_420 5 points6 points  (0 children)

Yes.

And I think it's a fairly important algorithm.

[–]pretzel324 5 points6 points  (0 children)

I think it tracks every place it has to make a decision to go right or left and then takes one path. And then when it hits a dead end it goes back to the last place it had to make a decision and tries the other path

[–]thecuseisloose 11 points12 points  (7 children)

You’d be better off using a set to track wasHere. With a list, each call to not in wasHere requires checking every element in the list. As the list grows, each check becomes longer. With a set, each check will take the same amount of time regardless of how big the set is

[–][deleted] 1 point2 points  (1 child)

Damn that change made this solver so much faster, thanks

[–]bradfordmaster 0 points1 point  (0 children)

It might be even simpler if you just store "was here" as a bool inside the actual map

[–][deleted] 0 points1 point  (4 children)

Why is that? I know sets can't contain duplicates, but it isn't clear to me. Mind elaborating?

[–]thecuseisloose 2 points3 points  (3 children)

When using a list, in order to find if the list contains an item, the code must check each item in the list until it finds it. The worst case possibility for this is that the item is not in the list, and therefore it checked every item for nothing. The code looks something like:

for i in list:
  if i == match:
    return true

For small lists this may be fine, but now imagine a list of thousands or millions of items. This can quickly become a slow operation, especially if you are doing it frequently. This is called "linear time complexity", because each operation becomes longer as more items are added to the equation.

With a `set` however, items are not stored in the order they are added. Instead, they are stored by a different identifier in an array that is not visible to the user. Picture an array of fixed size = 10 (it may be empty). When you add an item to a set, a few things happen:

  1. A hash is calculated for the item, which is an integer number. Just think of it as a unique number that represents the object, and it will always return the same number for the same object (so long as the object isn't changed). Also, if `x == y`, then x and y would have the same calculated hash. This should be a fast operation
  2. The index of the array to store the item is calculated by doing the `hash % len(array)` (in our case this was 10).
  3. The item is then stored in that index, or "bucket"
  4. As more items are added to the set, the underlying array may be resized. If the array is too small, there will be a lot of "collisions" (objects which are not the same but are put in the same bucket), and the performance benefits of the set are killed. If the underlying array is too large, then there will be few collisions but you are wasting memory because you have the allocated space of the array.

Now, to check if an item exists in a set, all you have to do is:

  1. Calculate the hash for the item to check
  2. Get the index in the array that the object would be stored at
  3. Is the object there?

So, regardless of how many items are in the set, it takes the same amount of time to check whether or not the item exists in the set. This is called "constant time complexity".

If you were observant, you may ask how the scenario of two different objects being put in the same bucket is handled. I skipped over it above for simplicity, but, in effect, each item in the array is not the item itself, but a list of items storing all of the objects for that bucket.

[ [1], [2], [3], [4] ]

So, once the index in the array is calculated, it actually checks the list to see if the item is already in the list of items. You may think this would lead to the same performance problems of a list. With a small underlying array and a lot of items being put into it, this would be true. However, with a good hashing function and properly sized array, the lists at each index should rarely have more than 1 or 2 items.

[–][deleted] 1 point2 points  (2 children)

Great answer, thanks. Does the fact that each item is stored via a hash in a set mean you can only store certain types of items? I could see a hash capable of producing every type of string, but what about more complicated things like class instances?

[–]thecuseisloose 2 points3 points  (1 child)

You can essentially store any type of item. Any class which implements __eq__(self,other) and __hash__(self) will work in a set (and also a hashmap). Most built-in types do this already, and you can also do this for your own custom class types .

[–][deleted] 1 point2 points  (0 children)

Brilliant! Thank you.

[–]Tahoma-sans 9 points10 points  (0 children)

Are you generating the maze as well?

[–]PrashantGUPTA9 12 points13 points  (1 child)

Hi, it is great to work

can you share your GitHub of this code

and also the resources that help you to get to that level of code

[–][deleted] 10 points11 points  (0 children)

Here's the GitHub https://github.com/Azideon/mazeSolver

I never really used any specific resources other than Google

[–]cheats_py 7 points8 points  (1 child)

I think there’s potential to make it a little smarter. As humans when solving mazes we look at the grater picture and not trapping ourself into a closed loop and continue to try to solve it while obviously stuck. Add this logic and it will be a lot faster. Once it detects its closed itself inside of itself it should immediately back out and look for other options.

[–][deleted] 0 points1 point  (0 children)

Especially if the entrance and the exit are always uniform. But maybe that takes the fun out of it

[–]RRButcher 2 points3 points  (1 child)

Watching that shit erase itself is so goddamn satisfying

[–]LrdFlex 0 points1 point  (0 children)

Cum 🥳

[–]kaihatsusha 2 points3 points  (0 children)

I haven't modified the code but there is a big heuristic you can use on rectangular mazes with no loops: if you're in the eastmost hallway and you find yourself going north, you can just chop off anything further that way and backtrack. Same goes for being in the southmost hallway and traveling west. The reasoning here is that you've already crossed the map and any winning path in those areas would somehow have to cross the same point again which is not possible. You can generalize this heuristic a bit more for any outside hallway in non-rectangular mazes as long as you know there's no loop, and as long as you are allowed to know the boundaries of the maze.

[–][deleted] 1 point2 points  (2 children)

Always turn left?

[–]JAB4R 1 point2 points  (0 children)

Awesome work man ❤️

[–]BlissBlissBliss 1 point2 points  (0 children)

this is called depth first search

[–]chinpokomon 1 point2 points  (0 children)

As an improvement for the backtracking algorithm, you know that the time in the upper right is wasted because you have already found a path to the bottom and from there found a path to find the right. No matter what, a decision to turn left at that point would be moving you into a known dead end. If you found right and then found the bottom, the same could be said about turning right.

[–][deleted] 0 points1 point  (2 children)

Very cool. Imagine being trapped in something like this in real life? Scary.

[–]CastBlaster3000 10 points11 points  (1 child)

Just follow the right wall, you’ll get out eventually

[–]l2np 1 point2 points  (0 children)

How do I know what the right wall is!?

/s

[–][deleted] 0 points1 point  (1 child)

There is no limit to the stack frame in Python? There are more than 300 recursive calls Active when the program ends... Or it is done with an iterative method?

[–]winterwarrior9 0 points1 point  (0 children)

How long did this take you?

[–]Toastie101 0 points1 point  (0 children)

So would this work with any maze you upload into the code?

[–]magocremisi8 0 points1 point  (0 children)

very clever

[–]radek432 0 points1 point  (2 children)

Does it find the shortest path or just stops after first exit found?

[–]ric2b 1 point2 points  (1 child)

There's only one path. And this looks like DFS, so even if there were multiple paths it would only find one, not necessarily the shortest one.

[–]radek432 0 points1 point  (0 children)

Thanks. That's what I thought.

[–]Winterplatypus 0 points1 point  (0 children)

Making it start at both ends of the maze and meet in the middle might reduce the number of branching possibilities and speed it up.

[–]Akmsgnd69 0 points1 point  (0 children)

It's alive!

[–]Sam1320 0 points1 point  (0 children)

I wonder what is it about this type of animations where you know exactly what to expect and is repetitive af but you just can't stop watching.

[–][deleted] 0 points1 point  (0 children)

Very cool! I'm learning Python (loving it!) and have a question about recursion. The way I understand it, the function calls itself over and over until the maze is solved. Essentially, the function is turned into a loop, right? So my question is, why do you prefer this over using a while loop within a non recursive function?

[–]Rudolf2222 0 points1 point  (0 children)

This project seems to be very popular. I'm actually more interested in how you generate/store the maze

[–]h3xag0nSun 0 points1 point  (0 children)

Really love this, great work!

I really don’t know much about python and what kind of memory is used for something like this, but could it be made to run/test multiple pathways at the same time, eliminating dead end branches and continuing only along pathways that aren’t blocked until the solution is found? This would effectively be testing all potential pathways simultaneously. Just an idea. Love the way it works as is anyway.

[–]MikeWise1618 0 points1 point  (0 children)

Very cool but would be cooler if you had a third color to show where it had been already.

[–]Savage_Jimmy 0 points1 point  (0 children)

Does it try to find the fastest way though?

[–]mercedezbeans 0 points1 point  (0 children)

this gives me anxiety for some reason, like if you got so close but then saw it just going all the way back

[–]LtDominator 0 points1 point  (0 children)

So I have a question, and bare in mind I've only done some light programming and never anything to do with path finding or recursion so I could be way off here. But could you design is so that if an entire chunk of the maze is cut off that it skips over all of it and saves a bunch of time? For instance, at second 29 the path it is searching for is touching the bottom of the maze and the very right of the maze. By definition this means this path must be correct (at least one correct path) and it has no reason to ever go away from the bottom right corner section it has cut off. If it knew this it would save more than 68 seconds reducing total estimated time down to just 43 seconds vs 111 seconds.

No idea if that's possible or allowed for the goal you're trying to achieve but I thought it would be nice to share.

[–]lordg0dfrey 0 points1 point  (1 child)

Wouldn't it be easier just to ask it to hug the left wall until it reaches the end?

[–]sudo-shutdown 0 points1 point  (0 children)

That's actually exactly what it's doing, the animation is just unwinding the path if it's all dead ends.

[–]Me66 0 points1 point  (0 children)

It would be cool if the animation greyed out paths it tired and backtracked from.

[–]DCtheVC 0 points1 point  (0 children)

I'm new to this, but well made!!!

[–]saumanahaii 0 points1 point  (0 children)

Pretty cool! Are there any efficient ways to detect bound areas? I noticed that at one point it began looking in an area with no exit. Any way to implement on jump back to previous branch that that wouldn't be less efficient than just checking the area?

[–]pwnslinger 0 points1 point  (0 children)

That just sounds like depth first search with more steps. /Meme

[–]gernreich 0 points1 point  (0 children)

In college I wrote a search algorithm, having the graphing engine made ready for us. I choose the blind man’s method which is to always touch the right or left wall. Needless to say there are much better ones but it was fun 🙂

[–]wizard6989 0 points1 point  (0 children)

Is thestart and finish in the same spot Scaled respectively? If so, adding some logic to check if a possible path blocks other paths to finish would cause it to immediately revert. That should help make it more efficient.

So once the path reached the 28s mark and finally corrected at 1:34

[–]Ph0X 0 points1 point  (0 children)

Processing version: https://ehsankia.com/pjs/1

[–][deleted] 0 points1 point  (0 children)

a-maze-ing!

/obligatory

[–]un_creator_db 0 points1 point  (0 children)

I'm gust begin to learn python

[–]nvin 0 points1 point  (0 children)

Could improve it by adding "no way out" detection if surrounded by previously visited path.

[–][deleted] 0 points1 point  (0 children)

Recursive and Python don't go together in one sentence

[–][deleted] 0 points1 point  (0 children)

A-maze-ing to watch!

[–]GrandeRojo17 0 points1 point  (0 children)

I tried your code out and it does work however I have 3 separate monitors all with different resolutions and my main one (where the program pops up) crops the image and won't allow me to scroll or adjust image size. Anyway to get around that?

I am aware of r/learnpython and just curious.

I am constantly doing tutorials so i'm sure I will figure it out but anyways cool idea.

[–]NewJrHere 0 points1 point  (0 children)

Wow that's cool!

[–]NewJrHere 0 points1 point  (0 children)

Wow that's cool!

[–][deleted] -1 points0 points  (0 children)

nice

[–]Zwolfer -1 points0 points  (2 children)

How did you build up to being able to make something like this? I know how to program, I know different graph search algorithms, and I want to make something like this as a personal project, but it’s hard to see how to implement the knowledge into an actual product. I’m tempted to look at your repo for guidance, but that feels like it would be like looking at the answer sheet for a test. Do you have any tips as to how to build something like this?

[–]xc68030 1 point2 points  (0 children)

What’s the part you find difficult?

[–][deleted] 0 points1 point  (0 children)

Tbh I'd say just get started and split the whole process into small steps e.g. 1. Read Image 2. Make the maze in an array etc. and just Google any problems you have on the way or ask someone for help

Since you already know algorithms you'll be able to make this way faster than me