Program produces unreachable locations in the maze

[deathslice]

So I'm trying to create a program that generates a maze using depth-first search. For the most part, this program is finished but what irks me is that the programs tends to produce locations that are simply unreachable and I can't seem to figure what extra logic I need to give in so that it does not produce unreachable locations

Maze.hpp

#pragma once

#include<vector>

class Maze
{
	public:
		Maze(int totalRows, int totalColumns);
		void displayMaze() const;
		void generateMaze();
		void generateMaze(int row, int column);
		int getNeighbourCell(int row, int column);
		int getCellIndex(int row, int column) const;
		void removeWalls(int currentCellIndex, int nextNeighbour);

	private:
		struct  Cell
		{
			Cell(int r, int col)
			{
				row = r;
				column = col;
				visited = false;
			}

			int getRowNumber() const
			{
				return row;
			}

			int getColumnNumber() const
			{
				return column;
			}

			bool Cell::isCellVisited() const
			{
				return visited;
			}

			void Cell::setVisitedCell(bool visit)
			{
				visited = visit;
			}

			int row;
			int column;
			bool visited;
			static const int MAX_WALLS = 4;

			bool walls[MAX_WALLS] = {true, true, true, true}; // Top, right, bottom, left.
		};

	private:
		std::vector<Cell> cells;

	public:
		const int ROWS;
		const int COLUMNS;
};

Maze.cpp

#include "Maze.hpp"
#include <iostream>
#include <random>
#include <stack>

constexpr int MAX_NEIGHBOURS = 4;

namespace RandomCellNumGenerator
{
	std::random_device rd;
	std::default_random_engine randEngine(rd());
}

Maze::Maze(int totalRows, int totalColmuns): ROWS(totalRows), COLUMNS(totalColmuns)
{
	cells.reserve(ROWS * COLUMNS);

	for (int i = 0; i < ROWS; i++)
	{
		for (int j = 0; j < COLUMNS; j++)
		{
			cells.push_back(Cell(i, j));
		}
	}
}

void Maze::displayMaze() const
{
	for (int i = 0; i < ROWS; i++)
	{
		for(int j = 0; j < COLUMNS; j++)
		{
			if (cells[i * COLUMNS + j].walls[0])
			{
				std::cout << "+---";
			}
			else
				std::cout << "+   ";
		}
			
		std::cout << "+" << std::endl;

		for (int j = 0; j < COLUMNS; j++)
		{
			if (cells[i * COLUMNS + j].walls[3])
			{
				std::cout << "|   ";
			}
			else
				std::cout << "    ";
		}

		std::cout << "|" << std::endl;
	}

	for (int i = 0; i < COLUMNS; i++)
	{
		std::cout << "+---";
	}
	
	std::cout << "+" << std::endl;
}

void Maze::generateMaze()
{
	std::uniform_int_distribution<int> distRow(0, ROWS - 1);
	std::uniform_int_distribution<int> distColumn(0, COLUMNS - 1);

	int startingRow = distRow(RandomCellNumGenerator::randEngine);
	int startingColumn = distColumn(RandomCellNumGenerator::randEngine);

	generateMaze(startingRow, startingColumn);
}

void Maze::generateMaze(int row, int column)
{
	int currentNeighbour = getCellIndex(row, column);

	std::stack<Cell> dfs;
	dfs.push(cells[currentNeighbour]);
	cells[currentNeighbour].setVisitedCell(true);

	while (!dfs.empty())
	{
		int nextNeighbour = getNeighbourCell(row, column);

		if (nextNeighbour != -1)
		{
			dfs.push(cells[nextNeighbour]);
			cells[nextNeighbour].setVisitedCell(true);
			removeWalls(currentNeighbour, nextNeighbour);
			row = cells[nextNeighbour].getRowNumber();
			column = cells[nextNeighbour].getColumnNumber();
			currentNeighbour = nextNeighbour;
		}
		else
		{
			dfs.pop();

			if (!dfs.empty())
			{
				row = dfs.top().getRowNumber();
				column = dfs.top().getColumnNumber();
			}
		}
	}
}

int Maze::getNeighbourCell(int row, int column)
{
	int neighbours[MAX_NEIGHBOURS];
	int validNeighbours = 0;

	int top = getCellIndex(row - 1, column);
	int right = getCellIndex(row, column + 1);
	int bottom = getCellIndex(row + 1, column);
	int left = getCellIndex(row, column - 1);

	if (top != -1 && !cells[top].isCellVisited())
	{
		neighbours[validNeighbours] = top;
		validNeighbours++;
	}

	if (right != -1 && !cells[right].isCellVisited())
	{
		neighbours[validNeighbours] = right;
		validNeighbours++;
	}

	if (bottom != -1 && !cells[bottom].isCellVisited())
	{
		neighbours[validNeighbours] = bottom;
		validNeighbours++;
	}

	if (left != -1 && !cells[left].isCellVisited())
	{
		neighbours[validNeighbours] = left;
		validNeighbours++;
	}

	if (validNeighbours > 0)
	{
		std::uniform_int_distribution<int> distNeighbours(0, validNeighbours - 1);
		int randomNeighbourCellIndex = distNeighbours(RandomCellNumGenerator::randEngine);
		int nextNeighbourIndex = neighbours[randomNeighbourCellIndex];
		return nextNeighbourIndex;
	}

	return -1;
}

int Maze::getCellIndex(int row, int column) const
{
	if (row < 0 || column < 0 || row > ROWS - 1 || column > COLUMNS - 1)
		return -1;
	return (row * COLUMNS) + column;
}

void Maze::removeWalls(int currentNeighbour, int nextNeighbour)
{
	int result = cells[currentNeighbour].getRowNumber() - cells[nextNeighbour].getRowNumber();
	
	if (result != 0)
	{
		if (result == 1)
		{
			cells[currentNeighbour].walls[0] = false;
			cells[nextNeighbour].walls[2] = false;
		}
		else if (result == -1)
		{
			cells[currentNeighbour].walls[2] = false;
			cells[nextNeighbour].walls[0] = false;
		}
	}
	else
	{
		result = cells[currentNeighbour].getColumnNumber() - cells[nextNeighbour].getColumnNumber();

		if (result == 1)
		{
			cells[currentNeighbour].walls[3] = false;
			cells[nextNeighbour].walls[1] = false;
		}
		else if (result == -1)
		{
			cells[currentNeighbour].walls[1] = false;
			cells[nextNeighbour].walls[3] = false;
		}
	}
}

MazeGenerator.cpp

// MazeGenerator.cpp : Defines the entry point for the console application.
#include "Maze.hpp"

int main()
{
	Maze maze(5, 5);
	maze.generateMaze();
	maze.displayMaze();
	system("pause");
    return 0;
}

[dhayden]

One problem that's bound to mess you up: displayMaze() is wrong. Look at line 35. When i=3 and j=2, this will refer to the same cell as when i=2 and j=3. Or when i=4 and j=1.... It should be Cell[i*COLUMNS + j]

Line 47 has the same problem.

[deathslice]

That would be true if I was doing i++ but I'm doing i+=Columns. So in the first iteration, the second for loop will go from 0 to 4 and display the northern edges of the wall. Then the third for loop will go from 0 to 4 and print the western edge of the wall. Then i will move by 5 so that it starts in a new row. Plus i * COLUMNS + j would give me an out of bounds error.

[Ericool]

You have row*col so why don't you have 2 for loop one for row and the other one for col?simply using ++

[deathslice]

Because, I need to have one for loop that goes through the entire maze, and two more for loops that prints "+---" or "+ " , "+", and "| " or " " in one go. After I have printed each of those in all the columns in one row, I do i+=COLUMNS so that I can start in a new row. I can't do simply i++ because I'm going to run into the problem that dhayden described.

Edit: I made some modifications to the display maze so that it uses both ROWS and COLUMNS as well as i * columns + j to the traverse through the 1-D but the maze still has cells that are unreachable so it is not really a good maze. Maybe the question is, is it normal for depth first search to do this or is there wrong with the way I'm displaying the maze or performing my depth first search?

[lastchance]

In Maze::generateMaze

                        if (!dfs.empty())
                        {
                                row = dfs.top().getRowNumber();
                                column = dfs.top().getColumnNumber();
                                currentNeighbour = row * COLUMNS + column;     // <==== add this line
                        }

You construct your maze OK, it's just that sometimes you won't demolish a wall.

[deathslice]

Yep that was the problem lastchance thanks.