Recursive Division Maze Generator

Maze.cpp

#include <iostream>
#include <vector>
#include <random>
#include <chrono>

enum class TileStatus
{
	Visited,
	Wall,
	NotVisited
};

struct Tile
{
	int x;
	int y;
	TileStatus status = TileStatus::NotVisited;
};

class Maze
{
public:
	Maze(int x, int y) : width(x), height(y), tiles(std::vector<Tile>(x*y))
	{
		setWallsAtPoint(0, 0, 0, width - 1, 0, height - 1);
		setWallsAtPoint(width - 1, height - 1, 0, width - 1, 0, height - 1);
		
		generateMaze();
	}

	int Width() const
	{
		return width;
	}

	int Height() const
	{
		return height;
	}

	void setWall(int x, int y)
	{
		tiles[getInternalLocation(x, y)].status = TileStatus::Wall;
	}

	void setVisited(int x, int y)
	{
		tiles[getInternalLocation(x, y)].status = TileStatus::Visited;
	}

	void setNotVisited(int x, int y)
	{
		tiles[getInternalLocation(x, y)].status = TileStatus::NotVisited;
	}

	Tile getTile(int x, int y) const
	{
		if (x < width && x >= 0 && y < height && y >= 0)
		{
			return tiles[getInternalLocation(x, y)];
		}
		else
		{
			throw std::invalid_argument("coordinate out of bound");
		}
	}

private:
	int getInternalLocation(int x, int y) const
	{
		auto val = width*y + x;
		return val;
	}
	
	void setWallsAtPoint(int x, int y, int startX, int endX, int startY, int endY)
	{
		for (auto col = startX; col <= endX; ++col)
		{
			setWall(col, y);
		}

		for (auto row = startY; row <= endY; ++row)
		{
			setWall(x, row);
		}
	}

	void recursiveDivision(int startX, int endX, int startY, int endY)
	{
		if (endX - startX > 3 && endY - startY > 3)
		{
			std::uniform_int_distribution<int> xWallDist(startX+2, endX-2);
			auto xDivide = xWallDist(engine);
			std::uniform_int_distribution<int> yWallDist(startY+2, endY-2);
			auto yDivide = yWallDist(engine);

			// Build walls
			setWallsAtPoint(xDivide, yDivide, startX, endX, startY, endY);

			// Poke holes in walls
			std::uniform_int_distribution<int> xHoleDist1(startX + 1, xDivide - 1);
			auto xHole = xHoleDist1(engine);
			setNotVisited(xHole, yDivide);

			std::uniform_int_distribution<int> xHoleDist2(xDivide + 1, endX - 1);
			xHole = xHoleDist2(engine);
			setNotVisited(xHole, yDivide);

			std::uniform_int_distribution<int> yHoleDist1(startY + 1, yDivide- 1);
			auto yHole = yHoleDist1(engine);
			setNotVisited(xDivide, yHole);

			std::uniform_int_distribution<int> yHoleDist2(yDivide + 1, endY - 1);
			yHole = yHoleDist2(engine);
			setNotVisited(xDivide, yHole);

			// Divide sub rooms
			recursiveDivision(startX, xDivide, startY, yDivide);
			recursiveDivision(xDivide, endX, startY, yDivide);
			recursiveDivision(startX, xDivide, yDivide, endY);
			recursiveDivision(xDivide, endX, yDivide, endY);
		}
	}

	void generateMaze()
	{
		auto startX = 0;
		auto startY = 0;
		auto endX = width-1;
		auto endY = height-1;

		recursiveDivision(startX, endX, startY, endY);
	}

	std::vector<Tile> tiles;
	std::mt19937 engine = std::mt19937(static_cast<unsigned int>(std::chrono::system_clock::now().time_since_epoch().count()));
	int width;
	int height;
};

// operator << for printing
std::ostream& operator<<(std::ostream& os, const Maze& maze)
{
	for (auto col = 0; col < maze.Width(); ++col)
	{
		for (auto row = 0; row < maze.Height(); ++row)
		{
			switch (maze.getTile(col, row).status)
			{
				case TileStatus::Visited:
				{
					os << '*';
				} break;

				case TileStatus::Wall:
				{
					os << '#';
				} break;

				default:
				{
					os << ' ';

				} break;
			}
		}
		os << '\n';
	}
	return os;
}

// Traverse Maze starting at point x,y
void traverseMaze(Maze& maze, int x, int y)
{
	auto tile = maze.getTile(x, y);
	if (tile.status != TileStatus::Visited && tile.status != TileStatus::Wall)
	{
		maze.setVisited(x, y);
		traverseMaze(maze, x + 1, y);
		traverseMaze(maze, x - 1, y);
		traverseMaze(maze, x, y + 1);
		traverseMaze(maze, x, y - 1);
	}
}

int main()
{
	char input;
	do
	{
		Maze maze(50, 40);
		traverseMaze(maze, 1, 1);
		std::cout << maze;
		std::cin >> input;
	} while (input != 'x');
	return 0;
}