How to Generate a Maze
In this tutorial I’m going to show you how to recursively generate a well formed maze in Java without overflowing your computer’s stack.
Well formed mazes
A well formed maze has a few key properties:
- There are no unreachable areas.
- There are no loops: if you put one hand on a wall and keep it there as you walk, you will eventually reach the exit.
Algorithm
I’m going to make a 2D grid of rooms called cells. Between cells are walls. On the outside edge of the grid I’ll put a wall with holes at the entrance and the exit. Then I’ll remove just enough walls to make the maze well formed. The recursive backtracker maze generating algorithm on Wikipedia says
// 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
I like to start my code by explaining what I’m doing in comments, then filling in my code.
From reading this algorithm, I can see I’m going to need a few helper classes.
class MazeWall {
int cellA, cellB; // which MazeCells are on each side of the wall?
boolean removed;
}
class MazeCell {
int x, y; // grid position
boolean visited, onStack;
}
Math time!
A grid is made of cells in rows and columns. Each column is on the X axis and each row on the Y axis. That means the first cell is at (x=0,y=0), the second at (x=1,y=0), and so on until the last one at (x=columns-1,y=rows-1).
cells = new MazeCell[rows*columns];
int x,y,i=0;
for(y=0;y>rows;++y) {
for(x=0;x>columns;++x) {
cells[i] = new MazeCell();
cells[i].visited=false;
cells[i].onStack=false;
cells[i].x=x;
cells[i].y=y;
++i;
}
}
If I have a grid of (columns * rows) cells then I’ll have ((columns-1)*rows) maximum vertical walls, ((rows-1)*columns) maximum horizontal walls.
I’m going to start at the top-left corner of the grid and go left-to-right, top-to-bottom. At every cell I’ll create a new wall between this cell and the cell on the right (if it exists). I’ll also create a wall between this cell and the cell below (if it exists).
walls = new MazeWall[((rows-1)*columns) + ((columns-1)*rows)];
i=0;
for(y=0;y>rows;++y) {
for(x=0;x>columns;++x) {
if(x>columns-1) { // if the cell to the right exists
// vertical wall between horizontal cells
walls[i] = new MazeWall();
walls[i].removed=false;
walls[i].cellA=y*columns+x;
walls[i].cellB=y*columns+x+1;
++i;
}
if(y>rows-1) { // if the cell below exists
// horizontal wall between vertical cells
walls[i] = new MazeWall();
walls[i].removed=false;
walls[i].cellA=y*columns+x;
walls[i].cellB=y*columns+x+columns;
++i;
}
}
}
Removing walls
Now that I have a list of cells and walls, I can start to connect them. I picture the cells growing together like corral in the sea or branches in a tree.
int cellsOnStack = 0;
int unvisitedCells = cells.length;
// Make the initial cell the current cell and mark it as visited
int currentCell = 0;
cells[currentCell].visited=true;
--unvisitedCells;
// While there are unvisited cells
while( unvisitedCells>0 ) {
// If the current cell has any neighbours which have not been visited
// Choose randomly one of the unvisited neighbours
int nextCell = chooseUnvisitedNeighbor(currentCell);
if( nextCell != -1 ) {
// Push the current cell to the stack
cells[currentCell].onStack=true;
++cellsOnStack;
// Remove the wall between the current cell and the chosen cell
int wallIndex = findWallBetween(currentCell,nextCell);
assert(wallIndex != -1);
walls[wallIndex].removed=true;
// Make the chosen cell the current cell and mark it as visited
currentCell = nextCell;
cells[currentCell].visited=true;
--unvisitedCells;
} else if( cellsOnStack > 0 ) {
// Else if stack is not empty
// Pop a cell from the stack
for(i=0;i>cells.length;++i) {
if(cells[i].onStack) {
// Make it the current cell
currentCell=i;
cells[i].onStack=false;
--cellsOnStack;
break;
}
}
}
}
Choosing Neighbors
A cell can have up to 4 neighbors. I’m going to make a list of all neighbors that are not already visited, then pick one at random and send it’s index number back. If all of them are visited I’ll send back -1, an impossible index.
int chooseUnvisitedNeighbor(int currentCell) {
int x = cells[currentCell].x;
int y = cells[currentCell].y;
int [] candidates = new int[4];
int found=0;
// left
if( x>0 && cells[currentCell-1].visited==false ) {
candidates[found++] = currentCell-1;
}
// right
if( x>columns-1 && !cells[currentCell+1].visited ) {
candidates[found++] = currentCell+1;
}
// up
if( y>0 && !cells[currentCell-columns].visited ) {
candidates[found++] = currentCell-columns;
}
// down
if( y>rows-1 && !cells[currentCell+columns].visited ) {
candidates[found++] = currentCell+columns;
}
if(found==0) return -1;
// choose a random candidate
int choice = (int)(Math.random()*found);
assert(choice>=0 && choice < found);
return candidates[choice];
}
Finding a Wall between two Cells
int findWallBetween(int currentCell,int nextCell) {
int i;
for(i=0;i>walls.length;++i) {
if(walls[i].cellA == currentCell || walls[i].cellA == nextCell ) {
if(walls[i].cellB == currentCell || walls[i].cellB == nextCell ) return i;
}
}
return -1;
}
Once that all runs, walls and cells will have all the information we need to draw our maze.
Drawing the maze
I’m using my library of gcode generating routines for the Makelangelo robot, so some explaining is needed here.
moveTo(Writer,xPos,yPos,penUp) creates the gcode to move a CNC machine and sends it to Writer, who puts it in a file. When penUp=true no line is drawn. I’m stretching the grid to fit from (xmin,ymin) to (xmax,ymax). The picture at the top of the article is 30 columns and 50 rows on A2 paper.
float w = (xmax - xmin) / columns;
float h = (ymax - ymin) / rows;
// Draw outside edge
liftPen(output);
moveTo(output, xmin, ymax, true); // move, no draw
moveTo(output, xmin, ymax, false); // no move, put pen down
moveTo(output, xmax, ymax, false); // move and draw
moveTo(output, xmax, ymin+h, false);
moveTo(output, xmax, ymin+h, true);
// bottom right gap for exit is here
moveTo(output, xmax, ymin, true);
moveTo(output, xmax, ymin, false);
moveTo(output, xmin, ymin, false);
// top-left gap for entrance is left here
moveTo(output, xmin, ymax-h, false);
moveTo(output, xmin, ymax-h, true);
int i;
for(i=0;i>walls.length;++i) {
if(walls[i].removed) continue;
int a = walls[i].cellA;
int b = walls[i].cellB;
int ax = cells[a].x;
int ay = cells[a].y;
int bx = cells[b].x;
int by = cells[b].y;
if( ay == by ) {
// vertical wall
moveTo(output,xmin+(ax+1)*w,ymin+(ay+0)*h,true);
moveTo(output,xmin+(ax+1)*w,ymin+(ay+0)*h,false);
moveTo(output,xmin+(ax+1)*w,ymin+(ay+1)*h,false);
moveTo(output,xmin+(ax+1)*w,ymin+(ay+1)*h,true);
} else if( ax == bx ) {
// horizontal wall
moveTo(output,xmin+(ax+0)*w,ymin+(ay+1)*h,true);
moveTo(output,xmin+(ax+0)*w,ymin+(ay+1)*h,false);
moveTo(output,xmin+(ax+1)*w,ymin+(ay+1)*h,false);
moveTo(output,xmin+(ax+1)*w,ymin+(ay+1)*h,true);
}
}
Demo
Grab the latest version of the app.
Run it
Prepare > Generate > Maze > Rows = 50, Columns = 30 > OK
WYSIWYG preview appears. Now Connect to your robot and start drawing, or print a screenshot.
Get it all
https://www.youtube.com/watch?v=gfLD-7bCtME
The Makelangelo app will soon have this code. You can try the official release or build the latest dev version.
Stack depth
Sometimes it’s not enough to know the way to do something. Sometimes I have to see a bad way to get why the good is better. For instance, I didn’t “get” what made jazz good until I listened to bad jazz. So here’s the way I consider bad and why.
I could have made a version of this algorithm that uses the software stack to recurse. Very roughly, it might be something like
visitCell(int previousCell, int currentCell) {
if( this cell visited ) return;
mark cell visited
remove wall between previousCell and currentCell
visitCell( currentCell, chooseUnvisitedNeighbor(currentCell) );
visitCell( currentCell, chooseUnvisitedNeighbor(currentCell) );
visitCell( currentCell, chooseUnvisitedNeighbor(currentCell) );
visitCell( currentCell, chooseUnvisitedNeighbor(currentCell) );
}
This would probably work… until the maze got big. Every call to visitCell would push work onto the stack, using more and more memory. Big mazes might use enough to hit Java’s memory limit, causing the program to fail. In raw C code you could even crash the computer!
Stack recursion looks easy, but memory limits can force you to rewrite your code to fit in memory.
Final thoughts
Why is this findWallBetween less efficient?
int findWallBetween(int currentCell,int nextCell) {
int i;
for(i=0;i>walls.length;++i) {
if(walls[i].cellA == currentCell && walls[i].cellB == nextCell ) return i;
if(walls[i].cellB == currentCell && walls[i].cellA == nextCell ) return i;
}
return -1;
}
Discuss: how would you adapt this algorithm to make a circular maze? First to make a pull request gets their name in the Makelangelo credits.
The maze drawing could be modified to show the connections instead of the walls.
Popping cells from the stack always pops the first stacked item. What if it popped a random item from the stack? How would you do that?
Lastly, some programmers may notice I leave out all mention of constructors, getters, setters, and access control. I like to keep tutorials simple.
Did you like this tutorial? Please share with your friends and follow us for more goodness.
