Skip to content
Sign upLog in
← Back to Community

Maze Generator (Depth-First Search Algorithm)

Profile icon
HackingGo306

Maze Generator

This is a maze generator that uses the depth-first search algorithm.

Note: Not recommended for making satisfying graphics, the red square will teleport sometimes

Source: http://www.migapro.com/depth-first-search/

EDIT: there is a improved (harder) version at: https://seashellrundownparameters-3.hackinggo306.repl.co/

__ It's harder because it generates cross roads at the very start so you have more choices to make __

Voters
Profile icon
HackingGo306
Profile icon
jihhyuu202
Profile icon
RolandJLevy
Profile icon
TurtleAndrew
Profile icon
LorenzoCampos
Profile icon
Bunnytoes
Profile icon
Nettakrim
Profile icon
JWZ6
Profile icon
DavanIrons
Profile icon
ChopSueyMaster
Comments
hotnewtop
Profile icon
Bunnytoes

this is so satisfying

Profile icon
Bunnytoes

nice job!

Profile icon
HackingGo306

@Bunnytoes

Thx

Profile icon
JWZ6

so cool

Profile icon
HackingGo306

@JWZ6
Thanks!

Profile icon
JWZ6

@HackingGo306
no prob

Profile icon
Elliot1120

I am ur 10th upvote and wanted to say I beat ur 149 by 149 maze after breaking my brain. BUT VERY WELL DONE!!!

Profile icon
HackingGo306

@Elliot1120

lol I don't even have the patience to watch the 149 by 149 finish...

Profile icon
Elliot1120

@HackingGo306
dwbi i dont either

Profile icon
DonoldJTrump

@HackingGo306
why does the square teleport?

Profile icon
HackingGo306

@DonoldJTrump

Every time the square moves to a new space, it adds it to an array called 'past'. When the square hits a dead end, then it goes to the latest place in 'past' and then deletes it from the array.
If the square hits a dead end but the previous move was already deleted from 'past', then it will teleport to another location from 'past'.
I know it sounds kinda confusing.

Profile icon
sojs

image

1000

And also why is there a blue square at the side?

Profile icon
HackingGo306

@sojs

I don't see a blue square.
And just FYI, the max is 149 by 149

Profile icon
sojs

ah so thats really a 149x149. I thought it looked a little small :)

@HackingGo306

Profile icon
HackingGo306

@sojs

Are you talking about the square on the top left? That's for you to control and try to beat the maze. :P

Profile icon
sojs

no. screen shot:

image


big blue square on right.

@HackingGo306

Profile icon
HackingGo306

@sojs

Ah. Do you mean the rest of the canvas? That's just the part that the maze doesn't take up.

Profile icon
sojs

wow!

Profile icon
CandySuperCool

Maybe make it so that you could play the maze after it's created?

Profile icon
HackingGo306

@WilliamXing

Made it.

Profile icon
Brendan23

@HackingGo306
cool! do you think it would be hard to do this in python?(the making the maze part not the print part.)

Profile icon
HackingGo306

@Brendan23
I'm probably not good enough at python to say so. :(

Profile icon
Brendan23

@HackingGo306
Oh, well, I'm gonna take a shot at it. I'll give you credit for the idea if you want.

Profile icon
HackingGo306

@Brendan23

k. Thx

Profile icon
HackingGo306

@Brendan23

But you don't have to give me credit because it's in python

Profile icon
Brendan23

@HackingGo306
True.

Profile icon
DynamicSquid

Nice! How are you using dfs? What are your "boundaries" that tells the algorithm to change direction?

Profile icon
HackingGo306

@DynamicSquid

The program knows if it is at a dead-end if all the moves (2 up, 2 down, 2 left, 2 right) hits an edge, passes the edge, or if the grid there is not a wall.

Profile icon
DynamicSquid

@HackingGo306
Oh do you generate invisible edges?

Profile icon
HackingGo306

@DynamicSquid

The red square moves 2 grids at a time, and since the dimensions are in a square, it is easy to check in advance if a certain move will pass the edge. The dimensions are always odd and so are the coordinates of the red square.
For moving right, you can check if the x-position of the square plus 2 is greater or equal to the edge size, if it is, then the move is illegal.

Profile icon
HackingGo306

@DynamicSquid

Here's I site I should've put in the credits:
http://www.migapro.com/depth-first-search/