Share your repls and programming experiences

← Back to all posts
Maze Generator (Depth-First Search Algorithm)
HackingGo306 (36)

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

Comments
hotnewtop
Bunnytoes (111)

this is so satisfying

Elliot1120 (1)

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

HackingGo306 (36)

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

DonoldJTrump (9)

@HackingGo306 why does the square teleport?

HackingGo306 (36)

@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.

sojs (341)

1000

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

HackingGo306 (36)

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

sojs (341)

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

HackingGo306 (36)

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

sojs (341)

no. screen shot:


big blue square on right.

@HackingGo306

HackingGo306 (36)

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

WilliamXing (50)

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

Brendan23 (166)

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

HackingGo306 (36)

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

Brendan23 (166)

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

HackingGo306 (36)

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

DynamicSquid (4893)

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

HackingGo306 (36)

@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.

DynamicSquid (4893)

@HackingGo306 Oh do you generate invisible edges?

HackingGo306 (36)

@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.