Trees maze generator

The rules

This article describes a maze generator I found in a french magazine - see the link at the end of this page.
The idea is to build the maze by growing trees from the border of the screen.

We start by defining some trunks.

Then we choose a random wall "inside" the maze and add it if it connects to another one.
But it must only touch one other wall. It should not connect 2 trees because that would mean some tiles would be
inaccessible.

These rules seem quite simple, but we will see that it takes a few stages before we get our complete maze.

Drawing the grid

First, we will try to see how to display the maze.
The size of our maze will be 30 * 20 tiles.

		#define MAZE_WIDTH      30
		#define MAZE_HEIGHT     20

Each tile will be a square of size of 20*20 pixels.

		#define TILE_SIZE       20

And the walls will have a width of 2.

		#define WALL_WIDTH      2

The screen size will be defined by these values.

		#define SCREEN_WIDTH    (MAZE_WIDTH  * TILE_SIZE + WALL_WIDTH)
		#define SCREEN_HEIGHT   (MAZE_HEIGHT * TILE_SIZE + WALL_WIDTH)

Now we will write a simple routine that draws a wall in the tile (x, y).
The wall will be either horizontal or vertical, and it will have a width of WALL_WIDTH and a length of TILE_SIZE.
We just need to add a few pixels to the length of the vertical wall to be sure to fill all the holes.

		void drawWall(int x, int y, bool isHorizontal, Color c)
		{
			int sx = x * TILE_SIZE;
			int sy = y * TILE_SIZE;

			if (isHorizontal == true)
			{
				int ex = sx + TILE_SIZE - 1;
				int ey = sy + WALL_WIDTH - 1;

				for (int yy = sy; yy <= ey; yy++)
					for (int xx = sx; xx <= ex; xx++)
						gfx.setPixel(xx, yy, c);
			}
			else
			{
				int ex = sx + WALL_WIDTH - 1;
				int ey = sy + TILE_SIZE + WALL_WIDTH - 1;

				for (int yy = sy; yy <= ey; yy++)
					for (int xx = sx; xx <= ex; xx++)
						gfx.setPixel(xx, yy, c);
			}
		}

To test this function we will draw all the walls of our maze.
So we begin with the left and top walls of each tile.

		// draw the maze
		for (int y = 0; y < MAZE_HEIGHT; y++)
			for (int x = 0; x < MAZE_WIDTH; x++)
			{
				drawWall(x, y, false, Color(255, 255, 255));
				drawWall(x, y, true,  Color(255, 255, 255));
			}

And as we said we have to draw the right and bottom borders of the whole
grid.

		for (int y = 0; y < MAZE_HEIGHT; y++)
			drawWall(MAZE_WIDTH, y, false, Color(255, 255, 255));

		for (int x = 0; x < MAZE_WIDTH; x++)
			drawWall(x, MAZE_HEIGHT, true, Color(255, 255, 255));

		Download source code
		Download executable for Windows

And we get the desired result

The maze datas

Now that we know how to draw our maze, let's see how it's datas will be stored in memory.
Following the representation we chose, each tile will have a top and a left walls.
A flag will tell us if they are drawn, and each of them will have a color.

		struct STile
		{
			bool    topIsActive;
			bool    leftIsActive;

			Color   topColor;
			Color   leftColor;
		};

The maze will be an array of these tiles.
As we must add the right and the bottom borders of the maze, the array will hold one more line and one more column.

		STile   maze[MAZE_WIDTH + 1][MAZE_HEIGHT + 1];

We will initialize this array by clearing all the walls' flags.

		// init the maze
		for (int y = 0; y <= MAZE_HEIGHT; y++)
			for (int x = 0; x <= MAZE_WIDTH; x++)
			{
				maze[x][y].topIsActive  = false;
				maze[x][y].leftIsActive = false;
			}

Now in this part we will try to draw only the borders of our maze.
So we will set their flags to true.

		// init left and right borders
		for (int y = 0; y < MAZE_HEIGHT; y++)
		{
			maze[0][y].leftIsActive = true;
			maze[0][y].leftColor = Color(255, 255, 255);

			maze[MAZE_WIDTH][y].leftIsActive = true;
			maze[MAZE_WIDTH][y].leftColor = Color(255, 255, 255);
		}

		// init top and bottom borders
		for (int x = 0; x < MAZE_WIDTH; x++)
		{
			maze[x][0].topIsActive = true;
			maze[x][0].topColor = Color(255, 255, 255);

			maze[x][MAZE_HEIGHT].topIsActive = true;
			maze[x][MAZE_HEIGHT].topColor = Color(255, 255, 255);
		}

And the function to draw the maze will simply call drawWall() for each active wall.

		// draw the maze
		for (int y = 0; y <= MAZE_HEIGHT; y++)
			for (int x = 0; x <= MAZE_WIDTH; x++)
			{
				if (maze[x][y].leftIsActive == true)
					drawWall(x, y, false, maze[x][y].leftColor);

				if (maze[x][y].topIsActive == true)
					drawWall(x, y, true, maze[x][y].topColor);
			}

		Download source code
		Download executable for Windows

The result may not be easy to see, but we really get a white rectangle that shows the boundaries of our grid.

The maze class

To keep the main loop simple, we will create a class to decribe the maze in another file.
Here is "maze.h"

		#ifndef MAZE_H
		#define MAZE_H

		#include "Graphics.h"

		#define MAZE_WIDTH      30
		#define MAZE_HEIGHT     20
		#define TILE_SIZE       20
		#define WALL_WIDTH      2

		struct STile
		{
			bool    topIsActive;
			bool    leftIsActive;

			Color   topColor;
			Color   leftColor;
		};

		class CMaze
		{
			public:
				CMaze();

				void    draw();

			private:
				void    drawWall(int x, int y, bool isHorizontal, Color c);

				STile   tiles[MAZE_WIDTH + 1][MAZE_HEIGHT + 1];
		};

		#endif // MAZE_H

And "maze.cpp"

		#include "maze.h"

		void CMaze::drawWall(int x, int y, bool isHorizontal, Color c)
		{
			[...]
		}

		CMaze::CMaze()
		{
			// init the maze
			for (int y = 0; y <= MAZE_HEIGHT; y++)
				for (int x = 0; x <= MAZE_WIDTH; x++)
				{
					tiles[x][y].topIsActive  = false;
					[...]
				}

			// init left and right borders
			for (int y = 0; y < MAZE_HEIGHT; y++)
			{
				tiles[0][y].leftIsActive = true;
				[...]
			}

			// init top and bottom borders
			for (int x = 0; x < MAZE_WIDTH; x++)
			{
				tiles[x][0].topIsActive = true;
				[...]
			}
		}

		void CMaze::draw()
		{
			// draw the maze
			for (int y = 0; y <= MAZE_HEIGHT; y++)
				for (int x = 0; x <= MAZE_WIDTH; x++)
				{
					if (tiles[x][y].leftIsActive == true)
						drawWall(x, y, false, tiles[x][y].leftColor);

					if (tiles[x][y].topIsActive == true)
						drawWall(x, y, true, tiles[x][y].topColor);
				}
		}

Now in "main.cpp" we just need to make an instance of this class and to call its draw method.

		CMaze maze;
		[...]
		maze.draw();

		Download source code

The inner walls

In the next program we will try to get the coordinates of the inner walls of the maze that will be connected to the
trunks.
We will first write a function to choose one of these walls randomly.

		// choose a random wall inside maze
		STile* chooseWall(bool& isHorizontal)
		{
			int x, y;
			isHorizontal = (rand() & 1 ? false : true);

			if (isHorizontal == true)
			{
				x = 1 + (rand() % (MAZE_WIDTH - 2));
				y = 1 + (rand() % (MAZE_HEIGHT - 1));
			}
			else
			{
				x = 1 + (rand() % (MAZE_WIDTH - 1));
				y = 1 + (rand() % (MAZE_HEIGHT - 2));
			}

			return maze.getTile(x, y);
		}

Then in the main loop, we will call this function and draw this wall.

		bool isHorizontal;
		STile*  tile = chooseWall(isHorizontal);

		if (isHorizontal == true)
		{
			tile->topIsActive = true;
			tile->topColor = Color(255, 0, 0);
		}
		else
		{
			tile->leftIsActive = true;
			tile->leftColor = Color(0, 255, 0);
		}

		maze.draw();

		Download source code
		Download executable for Windows

This draws all the walls we want.

Planting the trunks

Now we will select the trunks that will fill the maze.
In the Maze class we add a chooseTrunk() function that will select a tile around the border.

		// choose a random place to put a trunk
		STile* CMaze::chooseTrunk(bool& isHorizontal)
		{
			int x, y;
			int dir = rand() % 4;

			if (dir == 0)
			{
				isHorizontal = true;
				x = 0;
				y = 1 + (rand() % (MAZE_HEIGHT - 1));
			}
			else if (dir == 1)
			{
				isHorizontal = true;
				x = MAZE_WIDTH - 1;
				y = 1 + (rand() % (MAZE_HEIGHT - 1));
			}
			else if (dir == 2)
			{
				isHorizontal = false;
				x = 1 + (rand() % (MAZE_WIDTH - 1));
				y = 0;
			}
			else
			{
				isHorizontal = false;
				x = 1 + (rand() % (MAZE_WIDTH - 1));
				y = MAZE_HEIGHT - 1;
			}

			return getTile(x, y);
		}

Then we will call it in the Maze constructor where we initialize the flags of the walls:

		// init the trunks
		for (int i = 0; i < NB_TRUNKS; ++i)
		{
			bool isHorizontal;
			Color   color(32 + rand() % 224,
			              32 + rand() % 224,
			              32 + rand() % 224);

			while (true)
			{
				STile*  tile = chooseTrunk(isHorizontal);

				if (isHorizontal == true)
				{
					if (tile->topIsActive == false)
					{
						tile->topIsActive = true;
						tile->topColor = color;
						break;
					}
				}
				else
				{
					if (tile->leftIsActive == false)
					{
						tile->leftIsActive = true;
						tile->leftColor = color;
						break;
					}
				}
			}
		}

		Download source code
		Download executable for Windows

This give us the same kind of image that we saw at the beginning.

Checking collisions

Unfortunately, the program we just wrote is not perfect and as the trunks are placed randomly, this kind of things
may happen:

As we said we dont want that trees connect together. Here we can see that the corner tile is isolated from the rest
of the maze. And we want to be able to reach each tile of the maze from another tile.
So we will need a function to check if a wall will touch another before we draw it.
The function we will write will check all the walls that are touching the top-left corner of a tile.

To simplify the code, this function uses 4 sub-functions to check if there is a wall in one of the 4 directions
- up, down, left or right.

		bool CMaze::hasWallUp(int x, int y)
		{
			return getTile(x, y - 1)->leftIsActive;
		}

		bool CMaze::hasWallDown(int x, int y)
		{
			return getTile(x, y)->leftIsActive;
		}

		bool CMaze::hasWallLeft(int x, int y)
		{
			return getTile(x - 1, y)->topIsActive;
		}

		bool CMaze::hasWallRight(int x, int y)
		{
			return getTile(x, y)->topIsActive;
		}

		bool CMaze::checkIntersection(int x, int y)
		{
			if (hasWallUp(x, y) == true)
				return true;

			if (hasWallDown(x, y) == true)
				return true;

			if (hasWallLeft(x, y) == true)
				return true;

			if (hasWallRight(x, y) == true)
				return true;

			return false;
		}

Then we can use this function when we choose a trunk to test if its end touches another wall:

		// choose a random place to put a trunk
		STile* CMaze::chooseTrunk(bool& isHorizontal)
		{
			int x, y;
			STile*  tile;

			while (true)
			{
				int dir = rand() % 4;

				if (dir == 0)
				{
					isHorizontal = true;
					x = 0;
					y = 1 + (rand() % (MAZE_HEIGHT - 1));

					if (checkIntersection(x + 1, y) == false)
						break;
				}
				else if (dir == 1)
				{
					isHorizontal = true;
					x = MAZE_WIDTH - 1;
					y = 1 + (rand() % (MAZE_HEIGHT - 1));

					if (checkIntersection(x, y) == false)
						break;
				}
				else if (dir == 2)
				{
					isHorizontal = false;
					x = 1 + (rand() % (MAZE_WIDTH - 1));
					y = 0;

					if (checkIntersection(x, y + 1) == false)
						break;
				}
				else
				{
					isHorizontal = false;
					x = 1 + (rand() % (MAZE_WIDTH - 1));
					y = MAZE_HEIGHT - 1;

					if (checkIntersection(x, y) == false)
						break;
				}
			}

			return getTile(x, y);
		}

		Download source code

Drawing the maze

Now we have all the functions we need to draw the maze.
But when we choose the inner wall we will add, we have to check if it does not connect 2 trees.
This will be done in a function called checkWall()

		// choose a random wall inside maze
		void chooseWall()
		{
			int     x, y;
			Color   c;
			bool    isHorizontal;

			while(true)
			{
				isHorizontal = (rand() & 1 ? false : true);

				if (isHorizontal == true)
				{
					x = 1 + (rand() % (MAZE_WIDTH - 2));
					y = 1 + (rand() % (MAZE_HEIGHT - 1));

					if (checkWall(x, y, isHorizontal, c) == false)
					{
						maze.getTile(x, y)->topIsActive = true;
						maze.getTile(x, y)->topColor = c;
						break;
					}
				}
				else
				{
					x = 1 + (rand() % (MAZE_WIDTH - 1));
					y = 1 + (rand() % (MAZE_HEIGHT - 2));

					if (checkWall(x, y, isHorizontal, c) == false)
					{
						maze.getTile(x, y)->leftIsActive = true;
						maze.getTile(x, y)->leftColor = c;
						break;
					}
				}
			}
		}

This function will call checkIntersection() at both end of the wall we want ot add.

		bool checkWall(int x, int y, bool& isHorizontal, Color& color)
		{
			Color   c1, c2;
			bool    inter1, inter2;

			inter1 = maze.checkIntersection(x, y, c1);

			if (isHorizontal == true)
				inter2 = maze.checkIntersection(x + 1, y, c2);
			else
				inter2 = maze.checkIntersection(x, y + 1, c2);

We want to connect this wall to another one but to avoid connecting 2 trees together.
So there are 3 possible combinations of values for inter1 and inter2:

Either we do not touch any wall at all. In this case we don't want to draw the wall. Because we want it
to be connected to another one.
Or we are touching a wall on both side. In this case, we don't draw the wall either. Because we would
connect 2 trees together or isolate a tile.
The third case is when we touch a wall on one side but not on the other side. In this case we draw our
wall that will add a branch to a tree.

So for the 3rd case, we have to check if either inter1 is true and inter2 is false, or the opposite.

			if (inter1 == true && inter2 == false)
			{
				color = c1;
				return false;
			}
			else if (inter1 == false && inter2 == true)
			{
				color = c2;
				return false;
			}
			return true;
		}

		Download source code
		Download executable for Windows

Note that as the checkIntersection() checks all the directions, it will also check if there is already a wall at
the place we want to add one.
You may also have noticed that I modified all the checking functions to get the color of the wall we touch, because
I wanted to draw all the "branches" of a tree with the color of its trunk.

This is an example of what this program produces.

Detecting the end

The problem now is that when the program completes the maze, it tries to find another wall to draw and goes in a forever
loop.
So it will tell you that it doesn't repond when you try to close it.
To detect the end of the drawing we will add a flag to each wall in the Tile structure, telling if we visited this
wall or not.

		struct STile
		{
			bool    topIsActive;
			bool    leftIsActive;

			Color   topColor;
			Color   leftColor;

			bool    topVisited;
			bool    leftVisited;
		};

Of course these flags are initialized to false in the Maze class constructor.
Now we will set them to true in 2 cases:

Either if if we draw a wall at this place.
Or if we checked that there are 2 walls touching this one. That means we can't put a wall here, even in the
future.

The case when no wall touches this one is not interesting, because we may draw a wall in the future.
So we modify the checkWall() function to set these flags:

		bool checkWall(int x, int y, bool& isHorizontal, Color& color)
		{
			[...]

			if (inter1 == true && inter2 == false)
			{
				if (isHorizontal == true)
					maze.getTile(x, y)->topVisited = true;
				else
					maze.getTile(x, y)->leftVisited = true;

				color = c1;
				return false;
			}
			else if (inter1 == false && inter2 == true)
			{
				if (isHorizontal == true)
					maze.getTile(x, y)->topVisited = true;
				else
					maze.getTile(x, y)->leftVisited = true;

				color = c2;
				return false;
			}
			else if (inter1 == true && inter2 == true)
			{
				if (isHorizontal == true)
					maze.getTile(x, y)->topVisited = true;
				else
					maze.getTile(x, y)->leftVisited = true;
			}

			return true;
		}

Now at the end we should have marked all the positions of the inner walls where we actually drew a wall or where
we could not because of the rules.
So the function to check the end of the drawing needs simply to count all these flags and to check it against the
total number of inner walls.

		bool checkFinished()
		{
			int nbVisits = 0;

			for (int x = 0; x < MAZE_WIDTH; x++)
				for (int y = 0; y < MAZE_HEIGHT; y++)
				{
					if (maze.getTile(x, y)->topVisited == true)
						nbVisits++;

					if (maze.getTile(x, y)->leftVisited == true)
						nbVisits++;
				}

			return (nbVisits == (MAZE_WIDTH - 1) * (MAZE_HEIGHT - 2) + (MAZE_WIDTH - 2) * (MAZE_HEIGHT - 1));
		}

We will use this function at the beginning of chooseWall() to avoid entering in an endless loop.

		void chooseWall()
		{
			int     x, y;
			Color   c;
			bool    isHorizontal;

			while(true)
			{
				if (checkFinished() == true)
					break;

		Download source code
		Download executable for Windows

Now this program should end without any error.

The islands

The original program in the magazine also allowed to create islands instead of trees.
Islands are trees that grows from the inside of the maze instead of from the borders, like that:

To start them we simply have to put some trunks anywhere inside the maze at the beginning.
Of course as for every wall, we need to check if they touch other walls too.

		// choose a random place to put an island
		STile* CMaze::chooseIsland(bool& isHorizontal)
		{
			int x, y;
			Color   c;

			while (true)
			{
				isHorizontal = (rand() & 1 ? false : true);

				if (isHorizontal == true)
				{
					x = 1 + (rand() % (MAZE_WIDTH - 2));
					y = 1 + (rand() % (MAZE_HEIGHT - 1));

					if (checkIntersection(x, y, c) == false &&
					    checkIntersection(x + 1, y, c) == false)
						break;
				}
				else
				{
					x = 1 + (rand() % (MAZE_WIDTH - 1));
					y = 1 + (rand() % (MAZE_HEIGHT - 2));

					if (checkIntersection(x, y, c) == false &&
					    checkIntersection(x, y + 1, c) == false)
						break;
				}
			}

			return getTile(x, y);
		}

		CMaze::CMaze()
		{
			srand(time(NULL));

			// init the maze
			[...]

			// init left and right borders
			[...]

			// init top and bottom borders
			[...]

			// init the trunks
			[...]

			// init the islands
			for (int i = 0; i < NB_ISLANDS; ++i)
			{
				bool isHorizontal;
				Color   color(32 + rand() % 224,
				              32 + rand() % 224,
				              32 + rand() % 224);

				STile*  tile = chooseIsland(isHorizontal);

				if (isHorizontal == true)
				{
					tile->topIsActive = true;
					tile->topColor = color;
				}
				else
				{
					tile->leftIsActive = true;
					tile->leftColor = color;
				}
			}
		}

		Download source code
		Download executable for Windows

Here is an exemple of a maze with islands:

Improving the borders

One thing that I dislike in this generator is that it creates long corridors along the borders of the maze.
That's because there are only a limited number of trunks.
So I wanted to modify it to generate trunks dynamically.
We will start with no trunks, and we will modify the chooseWall() function to allow it to choose tiles along the
borders, that will become trunks.

		void chooseWall()
		{
			int     x, y;
			Color   c;
			bool    isHorizontal;

			while(true)
			{
				if (checkFinished() == true)
					break;

				isHorizontal = (rand() & 1 ? false : true);

				if (isHorizontal == true)
				{
					x = rand() % MAZE_WIDTH;
					y = 1 + (rand() % (MAZE_HEIGHT - 1));

					if (x == 0)
					{
						if (maze.checkIntersection(1, y, c) == false)
						{
							maze.getTile(x, y)->topIsActive = true;
							maze.getTile(x, y)->topColor = Color(32 + rand() % 224,
							                                        32 + rand() % 224,
							                                        32 + rand() % 224);
							break;
						}
					}
					else if (x == MAZE_WIDTH - 1)
					{
						if (maze.checkIntersection(x, y, c) == false)
						{
							maze.getTile(x, y)->topIsActive = true;
							maze.getTile(x, y)->topColor = Color(32 + rand() % 224,
							                                        32 + rand() % 224,
							                                        32 + rand() % 224);
							break;
						}
					}
					else if (checkWall(x, y, isHorizontal, c) == false)
					{
						maze.getTile(x, y)->topIsActive = true;
						maze.getTile(x, y)->topColor = c;
						break;
					}
				}
				else
				{
					x = 1 + (rand() % (MAZE_WIDTH - 1));
					y = rand() % MAZE_HEIGHT;

					if (y == 0)
					{
						if (maze.checkIntersection(x, 1, c) == false)
						{
							maze.getTile(x, y)->leftIsActive = true;
							maze.getTile(x, y)->leftColor = Color(32 + rand() % 224,
							                                         32 + rand() % 224,
							                                         32 + rand() % 224);
							break;
						}
					}
					else if (y == MAZE_HEIGHT - 1)
					{
						if (maze.checkIntersection(x, y, c) == false)
						{
							maze.getTile(x, y)->leftIsActive = true;
							maze.getTile(x, y)->leftColor = Color(32 + rand() % 224,
							                                         32 + rand() % 224,
							                                         32 + rand() % 224);
							break;
						}
					}
					else if (checkWall(x, y, isHorizontal, c) == false)
					{
						maze.getTile(x, y)->leftIsActive = true;
						maze.getTile(x, y)->leftColor = c;
						break;
					}
				}
			}
		}

		Download source code
		Download executable for Windows

And this is a maze produced by this code: