r/Python • • Nov 09 '19

My First Algorithm in Python! A Recursive Maze Solver

2.0k Upvotes

81 comments sorted by

94

u/LondonAppDev Nov 09 '19

Well done! What's the code look like?

87

u/DevJonPizza Nov 09 '19 edited Nov 09 '19

43

u/pjboro Nov 10 '19

I just checked it out. If you want to enable people to use your code, then always add a license: ISC/MIT/BSD is a good fit if you want to enable people to do everything they want with this code. And it's usually the case when considering really small projects :)

And... good job :)

22

u/DevJonPizza Nov 10 '19

Good point!

And... Thanks :p

5

u/imRobert7 Nov 10 '19

I do not know much about github, why should you add a license? You can just upload the code right? Isn't that the sign that you can just use the code?

7

u/WeirdFail Nov 10 '19

IANAL - but just because someone put something somewhere you can see it does not give you the right to use it, modify or redistribute it.

6

u/SgtBlackScorp Nov 10 '19

Not licensing your code gives others no permissions other than what is determined in Githubs TOS, which is just being allowed to view and fork it. That means nobody is allowed to use your code in other projects for example. https://opensource.guide/legal/

44

u/TheClassiestPenguin Nov 09 '19

Just how I like it

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.


InfoCustomYour RemindersFeedback

1

u/SilvrHorizon Nov 10 '19

Dont mind me just got to remember to check this out next Week

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

u/[deleted] 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

u/DevJonPizza Nov 10 '19

You should do it! That would be so cool!

2

u/GickRick Nov 10 '19

This is something i would contribute to in my free time cuz it's damn awesome!!!

1

u/DevJonPizza Nov 10 '19

Feel Free <3

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

u/flyvefugl Nov 10 '19

Nice thanks

2

u/[deleted] 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

u/DevJonPizza Nov 20 '19

Wow awesome! Def share the JS when your done!

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

u/[deleted] Nov 09 '19

You should code a laby generator to test the effectiveness of your laby solver on different maps

4

u/[deleted] 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

u/DevJonPizza Nov 10 '19

Feel Free to Contribute!

5

u/[deleted] 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

u/Zenith_N Nov 10 '19

Can you please explain what is a recursive solver?

2

u/DevJonPizza Nov 10 '19

Recursive means a function that calls itself

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

u/Bruguy1001 Nov 10 '19

Very well done. Code does not always have to be clean to work.

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

u/TheChuchNorris Nov 10 '19

I think it’s a depth-first search, right?

2

u/yaboytomsta Nov 10 '19

What window module did you use

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

u/YourBigBoySharky Nov 10 '19

My ass thought it was a QR code

1

u/[deleted] Nov 10 '19

I find this algorithm essential for making automatic reveal in mine sweepers.

1

u/razorfox Nov 10 '19

Very nice! What did you use for the graphics?

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

u/Grandpa_Nug Nov 11 '19

So what makes it choose one path over the other?

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

u/rtarafder Nov 09 '19

What did you use to make that

3

u/DevJonPizza Nov 10 '19 edited Nov 10 '19

Ansi escape codes and a lot of coffee

0

u/[deleted] 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

u/[deleted] 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

u/[deleted] Nov 10 '19

Anki!

1

u/[deleted] Nov 10 '19

Huh?

2

u/[deleted] Nov 10 '19

A spaced repetition program great for memorization. I highly recommend it!

1

u/[deleted] Nov 10 '19

Happen to have any examples?

1

u/[deleted] 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

u/[deleted] 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

u/[deleted] Nov 10 '19

[deleted]

1

u/DevJonPizza Nov 10 '19

Hmm that's odd... Python 3?

0

u/[deleted] Nov 12 '19

[deleted]

1

u/DevJonPizza Nov 12 '19

No idea ): sorry!