C++

Forum

 
Generating a maze

Satan (369)
So I need to generate a maze dynamically, meaning the user gives the dimensions and I must construct the maze using a function.

And I need to make multiple paths. Preferably no path should merge back into the right path because then there would be multiple solutions.

I can only use <ctime> and <iostream>. Pointers and rand() basically.
I want to do the program on my own, but what should the logic look like?

I'm lost ;p
closed account (1vRz3TCk)
https://en.wikipedia.org/wiki/Maze_generation_algorithm
Satan (369)
Umgh one question. While I was trying this thing out I noticed that the compiler doesn't quite care that the pointer is overflowing out of its allocation..

1) Could that be dangerous?
2) How do I know if the pointer is overflowing out of its allocation? How do I make sure that it's not overflowing?

In the below code, 
1
2
 
	for (int i = 0; i <= height+10; i++) {
		for (int j = 0; j <= width+10; j++)
this should access a value of the array which is not allocated. 

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
 
#include <ctime>
#include <iostream>

using namespace std;

void generate_maze(int height, int width) {
	char **p_p_maze = NULL;
	p_p_maze = new char*[height];
	for (int i = 0; i < height; i++) {
		p_p_maze[i] = new char[width];
	}

	for (int i = 0; i <= height+10; i++) {
		for (int j = 0; j <= width+10; j++) {
			p_p_maze[i][j] = 'x';
			cout << p_p_maze[i][j];
		}
		cout << '\n';
	}

}


int main() {
	generate_maze(20, 40);
	system("pause");
}

Last edited on
salem c (3700)
> 1) Could that be dangerous?
Very.

> 2) How do I know if the pointer is overflowing out of its allocation?
With any luck, you'll get a segmentation fault at the moment you step out of bounds.
If you're unlucky, it could be years before you notice.

Memory profiling tools like http://www.valgrind.org/ certainly help flush out problem code which fails to crash by itself.

> How do I make sure that it's not overflowing?
Maths, and accurate record keeping.

Or in C++, you use one of the standard containers like std::vector, which generally do away with the need for all this roll your own allocation (and the errors which come with it).


> Also notice that I have initialized the pointer to pointer to NULL.. so this shouldn't be happening
Also notice that on the very next line, you assign your pointer a proper value.



Satan (369)
Thanks salem. I edited my reply right before you wrote that reply,
so if anybody was wondering about..
Also notice that I have initialized the pointer to pointer to NULL.. so this shouldn't be happening
Also notice that on the very next line, you assign your pointer a proper value.
Last edited on
closed account (1vRz3TCk)
...pointer is overflowing out of its allocation..

I'm not sure I understand you. A pointer can point to some allocated memory and/or be used to traverse memory locations. It is quite easy to get a pointer to go 'out of bounds' of allocated memory.

1) Could that be dangerous?

yes.

2) How do I know if the pointer is overflowing out of its allocation? How do I make sure that it's not overflowing?

Generally, with raw pointers, you learn to be very careful with your pointer arithmetic.
Last edited on
Satan (369)
Okay so I want to do something similar to depth-first algorithm.

In that from a starting block, the computer keeps generating a path such that the path doesn't intersect an existing path.

Here's what I have in mind:
Use an array to store covered path blocks. Check if the path can go left, right, up or down by checking if that block which will be covered after moving the respective command would be touching a ' ' (a covered path). If the path hits a dead end, the program goes back to the last path in the array and tries to build a path from there (if it fails then it deletes that from the array) and keeps searching until if finds a path from which a new path can be built.

Eventually the array of valid paths will become empty, then no more paths are possible. And from there we can think about finding an end.


Any suggestions? Is there a better way to do this?

For the array holding path coordinates, should I initialize it by 1 and extend it by 1 every time there is a new coordinate or is that too greedy and I should do something like 10 instead?




Btw this is the code I have gotten till now just there can be improvement here itself:
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
 
#include <ctime>
#include <iostream>

using namespace std;

struct coordinates {
	int height;
	int width;
};

enum movement{
	RIGHT, LEFT, UP, DOWN
};

int random(int lower_limit, int upper_limit) {
	return rand() % (upper_limit - lower_limit + 1) + lower_limit;
}

void add_coordinates(int height, int width, coordinates *&path_array, int &current_size) {
	coordinates current_path;
	current_path.height = height;
	current_path.width =  width;

	coordinates *new_path_array = new coordinates[current_size+1];

	for (int i = 0; i < current_size; i++) {
		new_path_array[i] = path_array[i];
	}
	new_path_array[current_size] = current_path;

	current_size++;
	delete[] path_array;
	path_array = new_path_array;
}

void remove_coordinates(int index, coordinates *&path_array, int &current_size) { 
	coordinates *new_path_array = new coordinates[current_size - 1];

	for (int i = 0; i < current_size; i++) {
		if (i == index-1) 
			continue;
		else if (i > index-1) 
			new_path_array[i-1] = path_array[i];
		else
			new_path_array[i] = path_array[i];
	}

	current_size--;
	delete[] path_array;
	path_array = new_path_array;
}

bool check_up(int height, int width, char **&maze) {
	if (height - 1 < 0)
		return false;
	else if (!(height - 2 < 0 || width -1 < 0)) {
		if (maze[height - 1][width - 1] == ' ' || maze[height - 1][width + 1] == ' ' || maze[height - 2][width] == ' ')
			return false;
	}
	else
		return true;
}

bool check_down(int height, int width, char **&maze, int max_height) {
	if (height + 1 > max_height)
		return false;
	else if (!(height + 2 < max_height)) {
		if (maze[height + 1][width - 1] == ' ' || maze[height + 1][width + 1] == ' ' || maze[height + 2][width] == ' ')
			return false;
	}
	else
		return true;
}

bool check_right(int height, int width, char **&maze) {
	return false;
}

bool check_left(int height, int width, char **&maze) {
	return false;
}

void generate_maze(int height, int width) {
	int covered_path_size = 0;
	coordinates *covered_path = new coordinates[0];

	char **p_p_maze = new char*[height];
	for (int i = 0; i < height; i++) {
		p_p_maze[i] = new char[width];
	}

	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			p_p_maze[i][j] = 'x';
		}
	}
	p_p_maze[0][0] = ' ';
	p_p_maze[height - 1][width - 1] = ' ';

	if (check_up(0, 0, p_p_maze)) {
		cout << "true";
	}
	else
		cout << "false";

}

int main() {
	srand((unsigned)time(0));
	generate_maze(20, 40);
	system("pause");
}



I don't know why I used a dynamic 2D array, should I have just used a regular 2D array because I take it they are allocated in memory differently (regular 2D arrays are allocated linearly while dynamic 2D arrays are just all over the place.. apparently)..

Last edited on
Satan (369)
I've sort of figured out the logic but for some reason the program is not obeying like it's supposed to. It's giving me a maze whose path is meeting. Which is NOT supposed to happen. And the function check_movement() is supposed to make sure of this. I went through the function thrice I'm not able to figure out why the maze is failing..

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
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
 
#include <ctime>
#include <iostream>

using namespace std;

struct coordinates {
	int height;
	int width;
};

enum movement {
	RIGHT, LEFT, UP, DOWN
};

int random(int lower_limit, int upper_limit) {
	return rand() % (upper_limit - lower_limit + 1) + lower_limit;
}

void add_coordinates(coordinates current_path, coordinates *&path_array, int &current_size) {

	coordinates *new_path_array = new coordinates[current_size + 1];

	for (int i = 0; i < current_size; i++) {
		new_path_array[i] = path_array[i];
	}
	new_path_array[current_size] = current_path;

	current_size++;
	delete[] path_array;
	path_array = new_path_array;
}

void remove_coordinates(int index, coordinates *&path_array, int &current_size) {
	coordinates *new_path_array = new coordinates[current_size - 1];

	for (int i = 0; i < current_size; i++) {
		if (i == index - 1)
			continue;
		else if (i > index - 1)
			new_path_array[i - 1] = path_array[i];
		else
			new_path_array[i] = path_array[i];
	}

	current_size--;
	delete[] path_array;
	path_array = new_path_array;
}

bool check_movement(movement move, coordinates current_position, char **&maze, int max_height, int max_width) {
	if (move == UP) {
		if (current_position.height - 1 < 0)
			return false;
		else {
			if (!(current_position.height - 1 < 0 || current_position.width - 1 < 0))
				if (maze[current_position.height - 1][current_position.width - 1] == ' ')
					return false;
			if (!(current_position.height - 1 < 0 || current_position.width + 1 <= max_width))
				if (maze[current_position.height - 1][current_position.width + 1] == ' ')
					return false;
			if (!(current_position.height - 2 < 0))
				if (maze[current_position.height - 2][current_position.width] == ' ')
					return false;
		}
		return true;
	}
	else if (move == DOWN) {
		if (current_position.height + 1 >= max_height)
			return false;
		else {
			if (!(current_position.height + 1 >= max_height || current_position.width - 1 < 0))
				if (maze[current_position.height + 1][current_position.width - 1] == ' ')
					return false;

			if (!(current_position.height + 1 >= max_height || current_position.width + 1 >= max_width))
				if (maze[current_position.height + 1][current_position.width + 1] == ' ')
					return false;

			if (!(current_position.height + 2 >= max_height))
				if (maze[current_position.height + 2][current_position.width] == ' ')
					return false;
		}
		return true;
	}
	else if (move == RIGHT) {
		if (current_position.width + 1 >= max_width)
			return false;
		else {
			if (!(current_position.width + 2 >= max_width))
				if (maze[current_position.height][current_position.width + 2] == ' ')
					return false;
			if (!(current_position.height + 1 >= max_height || current_position.width + 1 >= max_width))
				if (maze[current_position.height + 1][current_position.width + 1] == ' ')
					return false;
			if (!(current_position.height - 1 < 0 || current_position.width + 1 >= max_width))
				if (maze[current_position.height - 1][current_position.width + 1] == ' ')
					return false;
		}
		return true;
	}

	else if (move == LEFT) {
		if (current_position.width - 1 < 0)
			return false;
		else {
			if (!(current_position.width - 2 < 0))
				if (maze[current_position.height][current_position.width - 2] == ' ')
					return false;
			if (!(current_position.height + 1 >= max_height || current_position.width - 1 < 0))
				if (maze[current_position.height + 1][current_position.width - 1] == ' ')
					return false;
			if (!(current_position.height - 1 < 0 || current_position.width - 1 < 0))
				if (maze[current_position.height - 1][current_position.width - 1] == ' ')
					return false;
		}
		return true;
	}
	else
		return false;
}

bool check_if_possible(coordinates current_position, char **&maze, int height, int width) {
	return check_movement(UP, current_position, maze, height, width) ||
		   check_movement(DOWN, current_position, maze, height, width) ||
		   check_movement(RIGHT, current_position, maze, height, width) ||
		   check_movement(LEFT, current_position, maze, height, width);
}

void generate_next_path(coordinates &current_position, char **&maze, int max_height, int max_width) {
	int possible_move = 0;
	movement possibilities[4];

	if (check_movement(UP, current_position, maze, max_height, max_width)) {
		possibilities[possible_move] = UP;
		possible_move++;
	}
	if (check_movement(DOWN, current_position, maze, max_height, max_width)) {
		possibilities[possible_move] = DOWN;
		possible_move++;
	}
	if (check_movement(RIGHT, current_position, maze, max_height, max_width)) {
		possibilities[possible_move] = RIGHT;
		possible_move++;
	}
	if (check_movement(LEFT, current_position, maze, max_height, max_width)) {
		possibilities[possible_move] = LEFT;
		possible_move++;
	}

	int chosen;
	do
		chosen = rand() % possible_move + 1; 
	    // 0 to possibilities, neglect 0 because it's unfairly unlikely
	while (chosen == 0);

	if (possibilities[chosen-1] == UP) {
		current_position.height--;
	}
	else if (possibilities[chosen-1] == DOWN) {
		current_position.height++;
	}
	else if (possibilities[chosen-1] == RIGHT) {
		current_position.width++;
	}
	else 
		current_position.width--;
}

void fill_maze(char **&maze, int height, int width) {
	for (int i = 0; i < height; i++) {
		maze[i] = new char[width];
	}

	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			maze[i][j] = 'x';
		}
	}
	maze[0][0] = ' ';
	maze[height - 1][width - 1] = ' ';
}

void display_maze(char **&maze, int height, int width) {
	for (int i = -1; i <= height; i++) {
		for (int j = -1; j <= width; j++) {
			if (i == -1 || j == -1 || i == height || j == width) {
				cout << '0';
			}
			else
				cout << maze[i][j];
		}
		cout << '\n';
	}
}

void generate_maze(int height, int width) {

	int covered_path_size = 0;
	coordinates *covered_path = new coordinates[0];

	char **p_p_maze = new char*[height];
	fill_maze(p_p_maze, height, width);

	coordinates current_position;
	current_position.height = 0;
	current_position.width = 0;
	add_coordinates(current_position, covered_path, covered_path_size);

	generate_next_path(current_position, p_p_maze, height, width);
	//cout << current_position.height << ' ' << current_position.width;


	//temporary while loop to test logic
		while (check_if_possible(current_position, p_p_maze, height, width)){
			p_p_maze[current_position.height][current_position.width] = ' ';
			generate_next_path(current_position, p_p_maze, height, width);
			p_p_maze[current_position.height][current_position.width] = ' ';
		}
	

	display_maze(p_p_maze, height, width);

}

int main() {
	srand((unsigned)time(NULL));
	generate_maze(20, 40);
	system("pause");
}


output I got:
000000000000000000000000000000000000000000
0   xxxxxxx   xxxxxxx     xx   xxxxxxxxxx0
0xx xxxxxxx x xxxxx   xxx    x xxxxxxxxxx0
0xx      x  x x     xxxxxxxxx  xxxxxxxxxx0
0xxxxxxx   xx   xxxx  x       xxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxx x xxxx  xxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxx  x xxxx  xxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxx x  xxxx  xxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxx   xxxxx xxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 0
000000000000000000000000000000000000000000
Press any key to continue . . .
Last edited on
salem c (3700)
Topic archived. No new replies allowed.