Back to Code List
c++

Maze Generator

This is a simple maze generator for the console. It lets you input the height and width to generate and creates a maze. There are many maze algorithms out there, this one has a top-left to bottom-right format. This program also will print the solution to the maze that was just generated. There are good concepts of array/vector use in this program.

   Main.cpp

#include "Maze.h"
#include <iostream>
#include <vector>
#include <random>
#include <cstdlib>

void main()
{
	std::random_device rd;
	std::srand(rd());
	
	int w,h;
	std::cout << "Please input size of the maze.\nWidth (max 35): ";
	std::cin >> w;
	std::cout << "Height (max 50): ";
	std::cin >> h;

	if(w>35) w=35;
	if(h>50) h=50;

	Maze maze(w,h);
	maze.build();
	maze.display();

	maze.solve();
}
    

   Maze.h

#ifndef MAZE_H
#define MAZE_H

#include <vector>

class Maze
{
public:
	Maze(int);
	Maze(int,int);
	void display();
	Maze& build();
	void solve();
private:
	std::vector<char> maze;
	int width;
	int height;
	int maxCell;
	int startCell;
	int endCell;
	std::vector<int> directions;

	void buildGrid();
	void buildMaze();
	void removeWall(int,int);
	int getName(int,int);
	bool isOpen(int,char);
	void randNextCell(int, int);
	bool isValid(int,int,int);
	void setDirs();
	void moveUp(int&);
	void moveLeft(int&);
	int getCellCenter(int);
	void setupMaze();
};

#endif
    

   Maze.cpp

#include "Maze.h"
#include <algorithm>
#include <iostream>

Maze::Maze(int s)
	:width(2*s+1)
	,height(2*s+1)
	,maxCell(((width-1)/2)*((height-1)/2))
{
	setupMaze();
}

Maze::Maze(int w, int h)
	:width(2*w+1)
	,height(2*h+1)
	,maxCell(((width-1)/2)*((height-1)/2))
{
	setupMaze();
}

void Maze::setupMaze()
{
	maze.resize(width*height);
	std::generate(maze.begin(),maze.end(),[]{return 'X';});
	setDirs();
	startCell = 0;
	endCell = maxCell-1;
}

Maze& Maze::build()
{
	buildGrid();
	buildMaze();
	return *this;
}

void Maze::display()
{
	for(int i=0; i<height; ++i)
	{
		for (int j=0; j<width; ++j)
			std::cout << maze[i*width+j];
		std::cout << std::endl;
	}
}

void Maze::buildGrid()
{
	//punch holes every other row and column, set start and end
	for(int i=1; i<height; i+=2)
		for (int j=1; j<width; j+=2)
			maze[i*width+j] = ' ';
	maze[getCellCenter(startCell)] = 'S';
	maze[getCellCenter(endCell)] = 'E';
}

void Maze::buildMaze()
{
	// hit every cell at least once
	for(int i=0; i<((height-1)/2); ++i)
		for(int j=0; j<((width-1)/2); ++j)
		{
			auto row = i;
			auto col = j;
			randNextCell(row,col); // start burrowing from here
		}
}

bool Maze::isValid(int cellA, int cellB, int dir)
{
	return (
		cellB > -1 && cellB<maxCell
		&& (
			(dir == 3)
			|| !(dir == 2 && (cellA-cellB)==1 && cellB%((width-1)/2) == ((width-1)/2)-1)
		)
	);
}

void Maze::setDirs()
{
	// set directions
	//directions.push_back(0);
	//directions.push_back(1);
	directions.push_back(2);
	directions.push_back(3);
	// here, we'll always have a northwest bias
}

void Maze::randNextCell(int row, int col)
{
	int nrow, ncol;
	int dir = (std::rand() % 2)+2;
	int arr[2] = {dir,dir==2?3:2};

	for(int i=0; i<2; ++i)
	{
		switch (arr[i])
		{
			case 0: nrow=row;   ncol=col+1; break; //east
			case 1: nrow=row+1; ncol=col;   break; //south
			case 2: nrow=row;   ncol=col-1; break; //west
			case 3: nrow=row-1; ncol=col;   break; //north
		}
		int cellA = getName(row,col);
		int cellB = getName(nrow,ncol);

		if (isValid(cellA,cellB,arr[i]))
		{
			removeWall(cellA, cellB); // join the cells
			break;
		}
	}
}

int Maze::getName(int row, int col)
{
	return (row*(width-1)/2 + col);
}

void Maze::removeWall(int a, int b)
{
	auto colA = (a % ((width-1)/2))+1;
	auto rowA = (a / ((width-1)/2))+1;

	auto colB = (b % ((width-1)/2))+1;
	auto rowB = (b / ((width-1)/2))+1;

	auto startCol = colA < colB ? colA : colB;
	auto startRow = rowA < rowB ? rowA : rowB;

	int pos = -1;
	
	if (colA == colB)
		pos = (startRow*2) * width + (startCol*2)%width;
	else if (rowA == rowB)
		pos = 2*width*(startRow-1) + width + (colA+colB) % width;

	if (pos > -1
		&& pos > width // ignore first row
		&& pos < (maze.size()-width) // ignore last row
		&& pos % width > 0 // ignore first column
		&& pos % width < width //ignore last column
	) {
		maze[pos-1] = ' ';
	}
}



void Maze::solve()
{
	std::cout << std::endl << std::endl << "  Solution" << std::endl;
	int currCell = endCell;
	while (currCell != startCell)
	{
		if (isOpen(currCell,'l'))
			moveLeft(currCell);
		else if (isOpen(currCell,'t'))
			moveUp(currCell);
		else
			break;
	}
	display();
}

void Maze::moveUp(int &cell)
{
	auto pos = getCellCenter(cell);

	if (maze[pos] != 'S' && maze[pos] != 'E')
	{
		maze[pos] = '.';
	}
	maze[pos-width] = '.';

	cell = cell-((width-1)/2);
}

void Maze::moveLeft(int &cell)
{
	auto pos = getCellCenter(cell);

	if (maze[pos] != 'S' && maze[pos] != 'E')
	{
		maze[pos] = '.';
	}
	maze[pos-1] = '.';

	cell = cell - 1;
}

bool Maze::isOpen(int cell, char wall)
{
	auto pos = getCellCenter(cell);

	switch (wall)
	{
	case 'l': return maze[pos-1] != 'X'; break; // left
	case 'r': return maze[pos+1] != 'X'; break; // right
	case 't': return maze[pos-width] != 'X'; break; // top
	case 'b': return maze[pos+width] != 'X'; break; // bottom
	}
	return false;
}

int Maze::getCellCenter(int cell)
{
	auto col = (cell % ((width-1)/2))+1;
	auto row = (cell / ((width-1)/2))+1;
	return (((row-1)*2*width) + width + col*2)-1;
}