C++

Forum

 
Explanation for a simple maze algorithm?

InsanelyNormal (26)
I want to know the steps involved in generating a 2d maze of a specific width and height, in detail.
g3n0m3 (29)
i just happen to have the source code of something you may be interested.
it's a backtracking based maze generator.

here is the pseudocode:

1.when entering the recursive function shuffle a vector of directions
2.for every direction possible (up down right left)
3.if its valid then call recursively the backtracking function
4.if its a dead end(no direction is valid) then backtrack to the instance of the function
where its possible to make another move

here is the source:

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

using namespace std;

int **l;
int n, m;
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { 1, 0, -1, 0 };
int dx1[4] = { 0, 2, 0, -2 }, dy1[4] = { 2, 0, -2, 0 };

int myrand(int i) { return rand() % i; };
void back(int x, int y)
{
	static int v[4] = { 0, 1, 2, 3 };
	random_shuffle(&v[0], &v[4], myrand);

	for (int i = 0; i < 4; i++)
	{
		int k = v[i];
		int x1 = x + dx[k], y1 = y + dy[k];
		x += dx1[k];
		y += dy1[k];
		if (y  < m - 1 && x  < n - 1 &&
			y  > 0 && x  > 0)
		{
			if (l[x1][y1] == 1 && l[x][y] == 1)
			{
				l[x1][y1] = l[x][y] = 0;
				back(x, y);
			}
		}
		x -= dx1[k];
		y -= dy1[k];
	}
}

int main()
{
	srand(time(NULL));	
	cout << "Height: "; cin >> n;
	cout << "Width: "; cin >> m;

	l = new int*[n];
	for (int i = 0; i < n; i++)
	{
		l[i] = new int[m];
		for (int j = 0; j < m; j++)
			l[i][j] = 1;
	}
	back(1, 1);
	l[1][1] = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (l[i][j] == 1)
				cout << char(219);
			else
				cout << ' ';
		}
		cout << endl;
	}
	return 0;
}
Last edited on
Topic archived. No new replies allowed.