r/Python • u/DevJonPizza • Nov 09 '19
My First Algorithm in Python! A Recursive Maze Solver
11
u/MecRandom Nov 09 '19
Weird thing happens with some green colored path while being a dead end. Do you know why? Excellent work BTW. How did you make the display of the maze?
9
u/DevJonPizza Nov 09 '19
idk why, it's very much not perfect code :/ ... I displayed the maze using ansi escape codes
3
u/Coolhilljr Nov 10 '19
While in Uni, we used the Zelle graphics package. Objects are displayed in a separate window, and isnt powerful, but pretty easy to use. https://mcsp.wartburg.edu/zelle/python/graphics.py Two other recommendations: http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap ^ this is a blog that gives an overview of several different maze generation techniques. Maybe try to implement a few of these to test you solver on. Second, I also recommend the Cracking the Coding interview book. It does a great job of going over the primary data structures and common algorithms used today in coding interviews.
1
u/SilvrHorizon Nov 10 '19
RemindMe! One Week
1
u/kzreminderbot Nov 10 '19
There is a 55 minutes delay to fetch comment reminders. Thanks for your patience! See KZReminderBot Stats for more statistics. PMs are unaffected by delay. If you have a reminder that is not confirmed, use this tool to manually load reminder using comment link.
Got it, SilvrHorizon 👌! Your reminder arrives in 1 week on 2019-11-17 19:57:17Z :
r/Python · My_first_algorithm_in_python_a_recursive_maze · 1
CLICK THIS LINK to also be reminded. Thread has 1 reminder and 1/4 confirmation comments.
Op can Delete Comment · Delete Reminder · Get Details · Update Time · Update Message · Add Timezone · Add Email
KZReminderTool · Create Reminder · Your Reminders · Give Feedback
1
u/RemindMeBot Nov 10 '19
I will be messaging you on 2019-11-17 19:57:17 UTC to remind you of this link
CLICK THIS LINK to send a PM to also be reminded and to reduce spam.
Parent commenter can delete this message to hide from others.
There is currently another bot called u/kzreminderbot that is duplicating the functionality of this bot. Since it replies to the same RemindMe! trigger phrase, you may receive a second message from it with the same reminder. If this is annoying to you, please click this link to send feedback to that bot author and ask him to use a different trigger.
Info Custom Your Reminders Feedback 1
4
u/DevJonPizza Nov 09 '19
BTW here is my blog post: https://jon.network/programming/62/Recursive-Maze-Solver/
3
u/numice Nov 10 '19
Is this your latest version? I don't notice where it makes the path green. I ran the code and it's all red. Do I miss something?
1
u/DevJonPizza Nov 10 '19
Your right, my friend made the recording and I think he hacked around with it for a while first.
1
u/ePierre Nov 10 '19
Haha thanks! I looked at the code and was like "wait, where is the instruction to color the maze green???"
2
Nov 10 '19
Awesome project. I'm a C# developer, but I also code a tad in python. Would be cool to recreate this in c#.
1
2
u/GickRick Nov 10 '19
This is something i would contribute to in my free time cuz it's damn awesome!!!
1
2
u/flyvefugl Nov 10 '19
Where did you learn that?
2
u/DevJonPizza Nov 10 '19
I'm self-taught, learned a lot at the recurse center: https://www.recurse.com
1
2
Nov 19 '19
I rewrote it in Nim: https://github.com/NostraDavid/MazeSolver-Nim
Why? Because I wanted to write something in Nim and your code seemed a good candidate :p
I've also rewritten it in Javascript, but that isn't finished yet.
1
1
u/DevJonPizza Nov 20 '19
One recommendation: use 2 spaces instead of one between the escape codes, makes each pixel look a bit more square.
64
u/Jugad Py3 ftw Nov 10 '19 edited Nov 11 '19
You might be using recursion, but the way it's going about the search is more generally known as backtracking.
Backtracking : Basically, if an algo hits a deadend, it goes back to the last point where a choice was made, and makes a different choice, never repeating an old choice. If it runs out of choices at a particular point, the algo backtracks further.
This works surprisingly well for a wide variety of problems. For example, Sudoku solvers, maze solvers, etc.
21
u/callmelucky Nov 10 '19
Formally known as Depth First Search. Right?
9
u/Fushium Nov 10 '19
Backtracking is a more general purpose algorithm. DFS just happens to be a specific form of backtracking. Backtracking can be used on any type of structure where portions of the domain can be eliminated - whether or not it is a logical tree.
4
u/Jugad Py3 ftw Nov 10 '19 edited Nov 10 '19
Yes, in a way.
Lets look at a backtracking sudoku solver...
For a sudoku solver, you might take a guess for a non-obvious empty square, and then try to fill in the remaining ones. If you hit a dead end, you change the last guess (if that square has no guesses left, you go back further).
Now, this is similar to a depth first search on the whole, but DFS has strong links to graphs. To solve the problem using DFS, we might map the problem to a graph, feed that graph to the DFS algo, which then spits out the answer.
Try to imagine the kind of graph that you would have to feed the DFS which would solve the problem (what are the nodes and links of the graphs and what would be the terminating conditions) - it seems like a fun little exercise to come up with that one.
38
Nov 09 '19
You should code a laby generator to test the effectiveness of your laby solver on different maps
4
Nov 10 '19
I was thinking that too. Maze makers tries to maximize the number of bad turns, maze runner tries to minify them. See how many generations until there is a clear winner.
16
u/karen_jd Nov 09 '19
You should check out this video from conputerphile on maze solving! Really interesting! https://youtu.be/rop0W4QDOUI
1
5
Nov 10 '19
step2: do it with explicit stack manipulation and loops.
3
u/Jugad Py3 ftw Nov 10 '19
Ah yes, the ol convert a recursive algo into a non-recursive one. Good exercise.
1
u/Dakadoodle Nov 10 '19
So wait? How is the maze opened? Is it pygame or whatever. And is that all the code for this?
2
u/DevJonPizza Nov 10 '19
It opens the image using Pillow, then runs some small logic to map that to a 2d array of the image. Then, it prints to the terminal using ansi escape codes. That is indeed all the code for it!
1
1
u/Prosodism Nov 10 '19
In the upper left quadrant there are three one-cell-deep dead ends, and two two-cell deep ones that didn’t turn red. Also, since your algorithm is “always take the right hand option”, I’m not sure why three of these got shaded in. You might wanna check your cases. But it’s a fun little program!
1
u/DevJonPizza Nov 10 '19
It first tries to go down, then right, so it's technically not "always the right hand option"
1
u/samuelcbird Nov 10 '19
This is awesome. Where did you get the maze png’s? Would love to try out coding this myself!
1
u/DevJonPizza Nov 10 '19
I made them myself using some online drawing thing. I just added some more mazes!
1
u/samuelcbird Nov 10 '19
Oh cool! Looks like a fun project anyhow.
Are you using colour to make the distinction between path and wall?
3
1
u/BarryScott2019 Nov 10 '19
Interesting, but how come it ignores some of the wrong routes by leaving them blank yet makes other wrong routes red? But nevertheless very pleasing to watch.
3
u/DoubleHooray Nov 10 '19
It’s marking squares it’s visited once with green, twice with red. Basically the algo says: choose any square not colored over a green square for the next step, ignore red squares, they’ve been eliminated.
1
u/DevJonPizza Nov 10 '19
It's sad you know my code better than me... It just kinda worked and I was like OK lol
1
u/BarryScott2019 Nov 10 '19
Massive thank for the response, and I hope to see more of your programming in the future!
2
2
1
u/allomanticpush Nov 09 '19
I like the maze’s name. It’s like a sequel to an earlier maze that was already solved.
1
u/deepturquoisesea Nov 10 '19
This looks great. Just a little suggestion, I also often can't be bothered with adding comments but, if you could add a comment line for each function at Github, it'd be infinitely helpful for the readers of your code. Regardless, thanks for sharing!
1
1
1
1
u/Vausinator Nov 10 '19
Would be cool to see this implementing (deep) Q-learning, so you can have an "intelligence" sorting this maze!
1
u/TheOuterLinux Nov 10 '19
Pretty cool, but I only get a red color and not green. I'm using xfce4-terminal and have tried it on both python2 and python3.
Just make sure to keep supporting Python 2.7 as long as you can because the inability to drag-and-drop a file when asked for input because of the single quotes is really annoying in Python 3. You can script it to replace the single quotes with nothing, but then if the file name has spaces, you have to then deal with that and so on and so forth. Whomever thought having Python 3 behave like that, which I'm guessing is because of stricter code practices regarding single quotes as being better than double-quotes, is an idiot. But, drag-and-drop works fine in Python 2.7.
1
1
1
u/harjotsingh0802 Nov 18 '19
Did a pretty good job on that, I feel this community is going to explode with ideas.
1
u/Nortages Nov 10 '19
Can you add some comments into the code? It would be very helpful for those who decided to look you code and maybe suggest the better algorithm. Thanks! :)
0
0
Nov 09 '19
[deleted]
32
u/DevJonPizza Nov 09 '19
I've been programming for about a year, you could definitely do something like this! I just kinda started hacking around, try it, you will be surprised how far you could get.
6
Nov 09 '19
Right, I have a question. How do you start writing algorithms? In a year, learning syntax, then writing simple loops and then algorithms? What tricks helped you remember things you can do and can’t do with your data?
7
u/DevJonPizza Nov 10 '19
Tbh, all I had written before was a bfs algorithm, I really just started hacking away towards a goal and it worked. I don't think there are any tricks, just use logic. I haven't really written one since because it takes a lot of mental power, so you need to do it right after you drink a bunch of coffee in the morning.
4
u/VStrideUltimate Nov 10 '19
Just by looking at how the graph is traversed, this is recursive depth first search.
3
u/florinandrei Nov 10 '19
I really just started hacking away towards a goal and it worked
That's true for most things that one could learn. Have a goal, work towards it.
1
Nov 10 '19
Anki!
1
Nov 10 '19
Huh?
2
Nov 10 '19
A spaced repetition program great for memorization. I highly recommend it!
1
Nov 10 '19
Happen to have any examples?
1
Nov 10 '19
Q: Two cases for every recursion? A: Base case and recursive case.
Q:sqlite3: object needed for connection? A: object.connect()
0
Nov 10 '19
[deleted]
1
u/DevJonPizza Nov 10 '19
pip install PIL Or it might be pip install Pillow I think it's pillow
0
94
u/LondonAppDev Nov 09 '19
Well done! What's the code look like?