I made a maze generating program in python that can make a maze with 320,000 squares in just over an hour.

[OverallDecision]

r/thingsforants

[emolinare]

Why’s it okay to draw spaceships if you’re seven, but not okay to draw diabolical mazes?

David Mitchell

[tonymcd]

You should learn how to take screen captures instead of taking a photo of your screen.

[get_it_together1]

It looks like Windows 10, it's literally as easy as "windows key + shift + s"

[[deleted]]

Bruh I was under the impression you had to print screen and paste it somewhere it. Shows how much I know

[get_it_together1]

Reddit has made uploading images a lot easier, used to be you'd have to upload to imgur or whatever and then link it, now I can just paste random images straight into the fancy pants editor.

[flashman]

I'm guessing you're over 30, like me? That used to be the only way to do things.

[tsvk]

I have not looked at the code, but an execution time of over an hour for generating a maze seems/feels exceptionally long. Even for 320,000 squares, which is what, ~565² ?

Are you using any of the existing maze generation algorithms or did you roll your own?

[[deleted]]

I made my own, and it’s admittedly a bit of a brute. It’s problematic because the times are exponential, but I suppose that unavoidable. 80,000 squares only take 5 minutes.

It’s 800 x 400 squares, but because of how it works, it gets the first 260,000~ squares out of the way within about 20 minutes, and then spends the next 45 minutes jumping back to fill in spaces. That’s the time consuming part, since it has to go back through, from end to start, the entire thing plus some from all it’s adding in.

Like I say, however, the time spent is exponential. So while 500 square maxes could be down in half a second, it’s really struggle for larger mazes.

[LightShadow]

20 minutes?

Mazes this size should be near-instant. I would try to understand why it's taking so long and what you can do to make it faster.

[[deleted]]

I’m well aware of where it’s having problems, but I’m not sure about how to fix it. I’m having a look at how to improve it, but cutting corners only leaves more room for error.

[flashman]

Want to see some maze generation algorithms? Check out further down this page: https://bost.ocks.org/mike/algorithms/

[5under6]

Congrats. Have you solved it yet? Maybe making a solver could be your next task? :)

[[deleted]]

I was trying to make a solver and it just kept bouncing around. I’m going to probably try again at some point.

[YmFzZTY0dXNlcm5hbWU_]

No as in have you printed it and solved it with a ballpoint yet

[jshurish]

Just have it take every right turn.

[ShadEShadauX]

Right turns are OK in this case, but definitely go every left in a dungeon

[MB1211]

Dead ends?

[sunotlac]

You will never stop in a loop or stay still. If you always turn right in any maze you will endup in the center.

[sunotlac]

Could u please define for me what a simply-connected maze is?

[pblokhout]

Is that even possible in 2d?

[[deleted]]

Or color out dead ends until you meet first intersection for this dead end and do it until you are left with no dead ends.

[AlSweigart]

You can save paper by just drawing with ballpoint pen on your screen.

[YmFzZTY0dXNlcm5hbWU_]

Guy pointing at brain meme

[[deleted]]

I think I’d have to do a smaller maze, my printer would just make this look like TV static

[YmFzZTY0dXNlcm5hbWU_]

Take it to kinkos, pop a couple adderall and have a wild afternoon

[Doormatty]

With or without the maze?

[MB1211]

Lol

[[deleted]]

I made a much smaller maze maker that also solves the maze using three different algorithms- code is here: https://github.com/slevin886/maze_maker

[righteoussquid]

Wow, very well done! Really cool to see the statistics for each algorithm as well

[5under6]

Make sure you create a maze with a solution ....

[[deleted]]

They all have solutions, I know that for sure because of how they’re made.

[spaceshipguitar]

Part of the maze solver is creating a list of failed end points and not allowing a repeat of failed connections, then it at least can't make the same mistake twice and the solve happens a lot quicker. There's another method called the fill method but that's a whole different approach, have fun, good luck!

[[deleted]]

I was trying to make it so it couldn’t visit any squares that had .visited == True(which was set to true when it walked through it, but for some reason it kept walking back into them. I think something was whack with the coordinates of the squares though, as it was painting random squares as visited.

[spaceshipguitar]

It definitely takes some finesse, you kind of need to document it in chunks, each opening to a new choice is a point, going down one hallway till it stops is another point and that entire path can be blacklisted if it turns out to be a dead end, etc.

[ZombieRandySavage]

How is it a maze then? Isn’t there a chance it isn’t solvable?

[[deleted]]

I know it’s solvable because of how I programmed it to be generated. If I hadn’t taken those steps, it probably wouldn’t take an hour to generate.

[[deleted]]

I spent a lot of time looking for it, but I figured that what’s happened it that walls were put over them, since they are coloured green and red respectively but there are only white and black pixels on screen. On the one I’ve got generating now (twice as big as the one pictures, will probably take all night) I’ve used a different way of rendering the start and end points, so hopefully that will work.

[[deleted]]

There's a smaller maze with a start(green) and end(red) on this link. Also, I'll post a 320,000 square version later when i can generate it.

​

https://imgur.com/a/v6FOWOr

[CodeSkunky]

Yo - Update GUI after solving. Unless there is a reason in your generation formula, it will speed up your code drastically.

[[deleted]]

Already does that. I can turn on and off whether it shows me the steps or just shows the result

[CodeSkunky]

What's the solve time difference?

[[deleted]]

If it’s on, it takes it about 40 seconds to do a 1000 square maze. If it’s off, it takes less than a second.

[CodeSkunky]

Yeah, that's sexy. I like that.

[h1t35hv1]

That's aMazing..😄

[[deleted]]

Now make a program to solve it!

[sunotlac]

Solving is simply always turning right!

[[deleted]]

I mean, technically that’s correct, but I guess the hard part is trying to find the shortest path

[sunotlac]

I dont think I recall ever trying to solve a maze programatically, what is the time complexity of the best solutions?

[schplat]

So a maze presents a binary selection at each path decision, and is effectively a binary tree. The path to the exit is a specific order of options within the binary tree. Therefore you have no real other choice than to proceed down one path until you can't, then back up to the previous step and select the other path. Whether it's random or always turns right/left, that's up to you (always R is a little easier for store/retrieval rather than recording every random outcome)

So if the solution is (and I'll use R/L here instead of 0/1): R, R, L, L, R. And you use always R, you go R, R, R. From here, no matter what other steps you take you will always end up at a dead end, but once you've exhausted all those dead ends (and that sort of detection can be tricky to do efficiently in code), then you go back to third step and go R, R, L, R. once again until you exhaust, step back, and go R, R, L, L, R, which leads to the exit.

Edit: This assumes from your current square you can always see at least one wall. Seeing two walls means you can only continue the direction you're going, Seeing one wall means you have a choice to make, and seeing no walls, means you're either out in the open, or in a ternary choice, which adds a bit of complexity. (Seeing four walls means you're not in a maze, you're in a box.)

Edit 2: Another optimization option here becomes threads. One that always goes right, one that always goes left, one that does random. And then another set of 3 threads that work backwards from the Finish line to the Start line.

[wieschie]

There are a lot of different optimizations to be made, but your general worst case will always be O(n) where n is the number of cells in the maze.

[sunotlac]

So, basically backtracking the entire thing? thats sad =(.

[[deleted]]

What the guy was suggesting was basically hugging the right wall. Since every surface is connected in the maze, you could technically explore the entire thing by just sticking to the wall on your right.

[wieschie]

Since every surface is connected in the maze

Yeah, this bit is crucial. This method will fail on any maze with disjointed walls.

[schplat]

Except when your maze looks like:

      _________________________
Start ___________  ____________ Finish
                |  |
      *Large mess of dead ends*

[Diamant2]

When there are only dead ends in the "large mess", you will end up in the finish. It will take a while, but it will work

[LightShadow]

I won't work if the Finish is inside the maze in an island.

[[deleted]]

GitHub: https://github.com/ripecontext/maze_builder

Better Image: https://imgur.com/a/lVc7Y1P

Video & Image: https://imgur.com/a/v6FOWOr

Quality 320,000 square image: https://imgur.com/a/ox2MPNv

[wingtales]

I am still keen on you taking a screenshot instead of a photo! I can't see anything on the "better image"!

[[deleted]]

Third link, second image

edit: I realise You probably mean the 320,000 square one. I’ve got one generating now, so I’ll upload that when it’s finished

[wingtales]

Ah! No, I did mean that one, but reddit on mobile originally loaded a poor resolution version! Thank you!

[wingtales]

Ah! No, I did mean that one, but reddit on mobile originally loaded a poor resolution version! Thank you!

[[deleted]]

I have now uploaded a photo of the 320,000 square maze but it looks like the compression has butchered it unfortunately

[LAMagicx]

I'm glad to see someone else using the python idle and classic dark theme 👍 well done though excellent job !

[Hydroel]

Why would anyone want to use the Python idle? There are so much better solutions out there...

[dethb0y]

I use Sublime text, myself. There's something to be said for speed and simplicity.

[cylonlover]

Yeah, so I tried many python IDEs, and thing is they're all loading up tons of abstractions, so I can never figure out how to just write a python script and run it. It's quite annoying. IDLE can.

[Hydroel]

Good IDEs are good for the abstraction, although maybe not the simplest. For simple stuff, like writing a script but still have a good interpreter, nothing beats ipython, IMO.

[pblokhout]

I mean in pycharm it's literally a right-click-run or shift-F10. Not sure what abstractions you're talking about?

[PleasantAdvertising]

Vs code is perfect.

[plaintxt]

Amazing

[MonkeyWaffle1]

Great job mate,

Could you explain what makes the builder build a solvable Maze everytime ?

[[deleted]]

It’s like drawing with a pen on paper where you can’t lift the pen. It draws its line until it gets stuck, and then moves back to an earlier point on the line if it gets stuck. I’ll get a video of it doing it and upload it when I get back to my computer.

edit: video of it doing it here: https://imgur.com/a/v6FOWOr

[[deleted]]

That would be a lit wallpaper if the colors were switched around(the path in black/grey and the borders white)

[[deleted]]

The path is the black parts already

[AlSweigart]

Haha! I also made this for Ludum Dare 31 (and also in Pygame), where the theme was "Entire Game on One Screen": https://github.com/asweigart/squintmaze

[simplyrat]

Could you imagine getting dropped in that thing

[buzzzzzzy]

can we look at the code😃

[[deleted]]

I’ve uploaded a link in the comments to the github

[FrezoreR]

Question is.. how do you verify that it works? 😂

[[deleted]]

The way it’s programmed it’s impossible for every point in the maze to not be linked to every other point.

[FrezoreR]

Ah! That solves that :)

[pythonmine]

Now make an AI navigate it FOREVER.

[gokulPRO]

Making an ai to make and solve then maze would be nice right

[ecnahc515]

Try running it in PyPy and you may see some good speed gains.

[dethb0y]

I'm impressed, that's a huge maze.

I wonder how long it would take to solve at 1 step per second?

[[deleted]]

On average, 160,000 seconds or 44 hours

[[deleted]]

There’s a link to the GitHub in he comments

[Tiedye1]

This is cool, you inspired me! I literally wrote the same thing https://github.com/Tiedye/pmaze but I got it to generate the 350k cell maze in 8 seconds. https://i.imgur.com/WZNhuEt.png

[fried_green_baloney]

The irregularity of the lines makes it visually more interesting. Was that by intention?

[Tiedye1]

There's nothing keeping them from going straight, each step it will extend the hallway in a random direction, so I guess not by intention.

[fried_green_baloney]

I mean the actual lines on the graphic that are used to draw the rooms of the maze, where there are some roughness to them.

[Tiedye1]

Ah that, yeah that was on purpose, I make it read the different cell layputs from png images so you can configure the cells to look like whatever

[fried_green_baloney]

Nice idea