Program produces unreachable locations in the maze

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#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

1
2
3
4
5
6
7
8
9
10
11
// 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;
}
Last edited on
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.
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.
You have row*col so why don't you have 2 for loop one for row and the other one for col?simply using ++
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?
Last edited on
In Maze::generateMaze

1
2
3
4
5
6
                        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.
Last edited on
Yep that was the problem lastchance thanks.
Topic archived. No new replies allowed.