Hello World! Its been a long time since my last visit here and lots of thing have happened while I'm gone but enough of the talk and lets get to the real topic.
So for the last few days I've been watching many Coding Train videos on YouTube to know more things about programming especially in javascript, then I stumbled upon one video of creating a maze on processing framework using depth-first search algorithm and I enjoy watching it so I made one myself.
The GIF you see above is the depth-first search algorithm creating a maze. So what is depth-first search maze generation?
As stated on Wikipedia,
This algorithm is a randomized version of the depth-first search algorithm. Frequently implemented with a stack, this approach is one of the simplest ways to generate a maze using a computer. Consider the space for a maze being a large grid of cells (like a large chess board), each cell starting with four walls. Starting from a random cell, the computer then selects a random neighbouring cell that has not yet been visited. The computer removes the wall between the two cells and marks the new cell as visited, and adds it to the stack to facilitate backtracking. The computer continues this process, with a cell that has no unvisited neighbours being considered a dead-end. When at a dead-end it backtracks through the path until it reaches a cell with an unvisited neighbour, continuing the path generation by visiting this new, unvisited cell (creating a new junction). This process continues until every cell has been visited, causing the computer to backtrack all the way back to the beginning cell. We can be sure every cell is visited.
Most of you probably didn't read all of it so here is the general instruction of depth-first search algorithm:
- Make the initial cell the current cell and mark it as visited
- While there are unvisited cells
- If the current cell has any neighbours which have not been visited
- Choose randomly one of the unvisited neighbours
- Push the current cell to the stack
- Remove the wall between the current cell and the chosen cell
- Make the chosen cell the current cell and mark it as visited
- Else if stack is not empty
- Pop a cell from the stack
- Make it the current cell
- If the current cell has any neighbours which have not been visited
Visualization of the above instruction
- Brown cells are the visited cells
- Peach cells are all unvisited cells
- Maroon cell is the current cell
- Blue cell is the next cell to visit
- Green cells are other available neighbor cells
The noticeable problem with this algorithm is that you can't choose your own exit cell because it always look for possible cell to visit anywhere. Commonly the exit cell of this algorithm is the longest path, like for the example above the exit cell is on the 2nd column on the 5th row. What I want is to have the starting cell on the top left corner of the room and the exit cell is on the bottom right corner.
So what I did was simple, I've created two maze generator in one single room, one for the starting cell and one for the exit cell;
Problem has now been solved, I can set the starting and exit cell anywhere I want with two maze generator. But a new problem has been arised, the two random mazes in this room are not connnected to each other, so we need a way to make them a one single maze.
This is what I've come up:
- Loop through every cell in the first maze
- If this cell is adjacent to the cell of the second maze
- Add this cell to the stack
- If this cell is adjacent to the cell of the second maze
- Randomly pick a cell from the stack
- Remove the wall between this cell and its adjacent cell
So there you go! My customized depth-first search algorithm! But wait, we're not done yet! There is still one more thing that bothers me with this algorithm. Its the way that most of the time it creates a long corridor until it found a dead end, means there are chances that it will generate a less branches of paths with long corridors but what I want is more branches with a decent length of corridors per branches. A simple way to fix it is by creating a step counter that increments every time a current cell visited a new cell then once we reached a maximum step, we will go back to the previous visited cell nth times and resetting the step counter back to zero.
Maximum of 10 steps before going back by 5 steps
As you can see above, even if there is a cell to visit, once it reaches a maximum of 10 steps it will backtrack 5 times and will start looking for another path to go. Finding the right maximum steps is the key for making hard random mazes.
And thats all for my own customized Depth-first search maze generator! Nothing fancy and anyone can do even better than this too.
TL;DR
A custom variation of Depth-first search consisting of two mazes in one room merged into one single big maze. One maze is initialized as starting cell and the second maze is initialized as the exit cell, both of them can be set anywhere in a room, in my example the starting cell is at the top left corner of the room and the exit cell is at the bottom right corner. The depth-first search is known to have a lot of long corridors but in this variation you can set the maximum length of corridor before it backtracks and find another branch of paths.
The algorithm is the same as the original depth-first but with the addition of new a condition maximum steps before visiting a new cell, if its steps are greater than the maximum step then go backtrack nth times as specified by the user then reset the step counter to zero.
To merge two mazes as one, the program will loop into all of the cells within the first maze and if that cell is adjacent or next to a cell within the second maze then remove a wall from this cell and its adjacent cell from the second maze. This need to be run onced to prevent a looping maze.
91x41 cells with a 132 maximum steps, checking 60 cells per frame.
I am not really good on explaining things and stuffs so if you have any feedbacks feel free to comment it out below. Also the source code and the explanation of my codes in javascript language will be on my next blog so stay tuned and if you like this idea feel free to share and upvote!