# Maze Generator in C++ using iterative approach

This is a simple maze generator program. I didn't want to include header files and separate compilation because it was meant to be simple and straightforward. I also think the code is both readable and understandable, which is why I do not have many comments. I implemented an iterative version due to the function call overload of a recursive approach, though I felt a recursive approach might be cleaner.

The code works based on what I have tested so far.

MAJOR CONCERNS

2. Potential pitfalls
4. Poor use of Data structures

# maze_gen.cc

#include <iostream>
#include <array>
#include <string>
#include <vector>
#include <tuple>
#include <map>
#include <stack>
#define N 16

struct Cell
{
Cell() = default;
Cell( int i, int j );
const Cell &operator=( const Cell & );
std::string direction( const Cell & );

std::map< std::string, bool> walls;
std::map<std::string, std::string> mypairs;
int x;
int y;
bool visited;
std::stack<Cell> neighbors;
};

Cell::Cell( int i, int j )
:  x( i ), y( j ), visited( false )
{
walls.insert( { "N", true } );
walls.insert( { "S", true } );
walls.insert( { "W", true } );
walls.insert( { "E", true } );

mypairs.insert( { "N", "S" } );
mypairs.insert( { "S", "N" } );
mypairs.insert( { "E", "W" } );
mypairs.insert( { "W", "E" } );

}

const Cell &Cell::operator=( const Cell &c )
{
x = c.x;
y = c.y;
visited = c.visited;
walls = c.walls;
mypairs = c.mypairs;

return *this;
}

std::string Cell::direction( const Cell &other )
{
if( x == other.x && y + 1 == other.y )
return "E";
if( x == other.x && y - 1 == other.y )
return "W";
if( x - 1 == other.x && y == other.y )
return "N";
if( x + 1 == other.x && y == other.y  )
return "S";
return "";
}

struct Grid
{
Grid();
void print_grid();
std::vector<std::tuple< int, int> > get_all_neighbors( int i, int j );
std::string direction( Cell current, Cell other );
void generate_maze();

std::array<std::array< Cell, N >, N > grids;
};

Grid::Grid() {
for( int i = 0; i != N; ++i ) {
for( int j = 0; j != N; ++j ) {
grids[ i ][ j ] = Cell( i, j );
}
}
}

std::vector<std::tuple< int, int> > Grid::get_all_neighbors( int i, int j ) {
std::tuple< int, int> co_ordinates;
std::vector<std::tuple< int, int> > valid_neighbors;

if( ( i >= 0 && i < N ) && ( j + 1  >= 0 && j + 1 < N ) && ( grids[ i ][ j + 1 ].visited == false ) ) {
co_ordinates = std::make_tuple( i, j + 1 );
valid_neighbors.push_back( co_ordinates );
}
if( ( i >= 0 && i < N ) && ( j - 1 >= 0 && j - 1 < N ) && ( grids[ i ][ j - 1 ].visited == false ) ) {
co_ordinates = std::make_tuple( i, j - 1 );
valid_neighbors.push_back( co_ordinates );
}
if( ( i - 1 >= 0 && i - 1 < N ) && ( j >= 0 && j < N ) && ( grids[ i - 1 ][ j ].visited == false ) ) {
co_ordinates = std::make_tuple( i - 1 , j );
valid_neighbors.push_back( co_ordinates );
}
if( ( i + 1 >= 0 && i + 1 < N ) && ( j >= 0 && j < N ) && ( grids[ i + 1 ][ j ].visited == false ) ) {
co_ordinates = std::make_tuple( i + 1 , j );
valid_neighbors.push_back( co_ordinates );
}

return valid_neighbors;
}

void Grid::print_grid() {
std::cout << "+";
for( int i = 0; i != N; ++i )
std::cout << "----+";
std::cout << std::endl;
for( int i = 0; i != N; ++i ) {
std::string body = "    ";
std::cout << "|";
for( int j = 0; j != N; ++j ) {
if( grids[i][j].walls.at( "E" ) )
std::cout << body << "|";
else
std::cout << body << " ";
}
std::cout << std::endl;
for( int j = 0; j != N; ++j ) {
std::cout << "+";
if( grids[i][j].walls.at( "S" ) ) {
std::cout << "----";
}
else {
std::cout << body;
}
}
std::cout << "+";
std::cout << std::endl;
}
}

void Grid::generate_maze()
{
Cell current_cell = grids[ 6 ][ 6 ];
std::stack<Cell> visited_cells;
grids[ current_cell.x ][ current_cell.y ].visited = true;
visited_cells.push( grids[ current_cell.x ][ current_cell.y ] );

while( visited_cells.empty() == false )
{
current_cell = visited_cells.top();
visited_cells.pop();

auto neighbors = get_all_neighbors( current_cell.x, current_cell.y );
int random_int = 0;
if ( neighbors.size() != 0 ) {
random_int = 0 + rand() % neighbors.size();
}

if( neighbors.empty() == false )
{
visited_cells.push( grids[ current_cell.x ][ current_cell.y ] );
int i = std::get<0>( neighbors[ random_int ] );
int j = std::get<1>( neighbors[ random_int ] );
Cell neighbor = grids[ i ][ j ];

std::string direction = grids[ current_cell.x ][ current_cell.y ].direction( neighbor );
grids[ current_cell.x ][ current_cell.y ].walls[ direction ] = false;
grids[ neighbor.x ][ neighbor.y ].walls[ grids[ current_cell.x ][ current_cell.y ].mypairs[ direction ] ] = false;

grids[ i ][ j ].visited = true;
visited_cells.push( grids[ i ][ j ]  );
}
}
}

int main()
{
srand( static_cast<unsigned int> (time(0)) );
Grid grid;
grid.print_grid();
grid.generate_maze();
std::cout << "\nMaze generated\n";
grid.print_grid();
}



Avoid macros. Replace #define N 6 with constexpr int N = 6;. N is not a very descriptive name; you should give it a better one (MAZE_SIZE). You're also using this for both dimensions of the maze, which limits you to square mazes.

operator= should not return a const reference.

Since Cell::walls is a map that stores a bool, you could replace it with a set, and use the presence of the key in the set as the value.

Rather than using short strings for things like direction, you could use an enum type. This would save space and improve performance.

Cell::direction can be a const function (std::string Cell::direction( const Cell &other ) const).

You could add an init or setxy function to Cell, and use that in the Grid constructor (grids[ i ][ j ].init(x, y);).

Grid::get_all_neighbors can also be a const member function. You can get rid of co_ordinates  by using valid_neighbors.emplace_back(std::make_tuple(/*...*/)).

When checking a bool value, you don't need to use ==, you can check it directly. To check for false, you can use the ! operator: !grids[ i ][ j - 1 ].visited.

There are a couple of duplicated conditions in get_all_neighbors. This function can be rewritten with nested if statements to remove them. This would also improve the readability just a bit.

In a lot of your for loops, your comparison uses !=. While that works here, more common is to use <. The < comparison is essential when using something like OpenMP to add multithreading.

In print_grid, the body variable can be moved outside of the for loop. This will avoid repeatedly creating and destroying it.

generate_maze uses a hardcoded 6 as a starting cell. This should be a constant somewhere (defined next to N), or should be some fraction of N. You seem to be using current_cell just to hold x and y values. You can use either a smaller coordinate class, or a pair, to manipulate these. By using the full Cell object you're copying around a lot of (empty) maps and stacks.

rand is not a very good source of random numbers. Look into the facilities provided by the <random> header.

• I found out that whenever i declare operator= without const, it resulted to weird things happening when I make a copy – theProgrammer Oct 31 '20 at 4:49
• @theProgrammer While in practice it usually doesn't matter, the compiler generated assignment operator returns a non-const reference, and there are some cases where the value returned by the assignment is immediately used or modified that would not compile if the returned reference was const. – 1201ProgramAlarm Oct 31 '20 at 17:32