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
|
#include <stack>
#include <cstdio>
#include <ctime>
#define OUTPUT(x) printf("%s: %i\n",#x,x)
char oobchr=0;
struct maze{
char* data;
int w,h;
maze():data(NULL),w(0),h(0){}
maze(int width,int height){
data=new char[width*height];
w=width;
h=height;}
~maze(){
delete[] data;}
char& operator()(int x,int y){
if(x>=w || y>=h){
return oobchr;}
return data[y*w+x];}};
void printmaze(maze&);
void makemaze(maze& dfs,int startx,int starty,int endx,int endy){
int x,y;
for(x=0;x<dfs.w;++x){
for(y=0;y<dfs.h;++y){
dfs(x,y)=(x%2 && y%2)+1;}}//1 for wall, 2 for unvisited
bool dir[4];
bool start=true;
char num,lastdir,randdir,i,c,nextdir;
std::stack<char> path;
x=startx;
y=starty;
while((x!=startx || y!=starty) || start){
//get available directions
dir[0]=dfs(x+2,y);
dir[1]=dfs(x,y-2);
dir[2]=dfs(x-2,y);
dir[3]=dfs(x,y+2);
//get the number of available directions
num=(dir[0]+dir[1]+dir[2]+dir[3])>>1;
//special case (dead end)
if(num==0){
lastdir=path.top();
path.pop();
dfs(x,y)=0;
switch(lastdir){
case 0:
x-=2;
break;
case 1:
y+=2;
break;
case 2:
x+=2;
break;
case 3:
y-=2;
break;}
continue;}
//choose a random direction
randdir=rand()%num;
for(i=0,c=0;i<4;++i){
if(dir[i]){
if(c==num){
nextdir=i;}
++c;}}
//move and destroy wall in between cells
path.push(nextdir);
dfs(x,y)=0;
switch(nextdir){
case 0:
dfs(x+1,y)=0;
x+=2;
break;
case 1:
dfs(x,y-1)=0;
y-=2;
break;
case 2:
dfs(x-1,y)=0;
x-=2;
break;
case 3:
dfs(x,y+1)=0;
y+=2;
break;}
if(x==endx && y==endy){
path.pop();
dfs(x,y)=0;
switch(nextdir){
case 0:
x-=2;
break;
case 1:
y+=2;
break;
case 2:
x+=2;
break;
case 3:
y-=2;
break;}}
start=false;}}
void printmaze(maze& m){
int x,y;
for(y=0;y<m.h;++y){
for(x=0;x<m.w;++x){
if(m(x,y)==1){
printf("#");}
else if(m(x,y)==2){
printf("*");}
else{
printf(" ");}}
printf("\n");}}
int main(){
srand(time(0));
maze dfs(33,33);
makemaze(dfs,15,15,31,31);
printmaze(dfs);
getchar();
return 0;}
|
#################################
#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#
#*#*#*#*#*#*#*#*#
#################################
#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#
#################################
#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#
#################################
#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#
#################################
#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#
#################################
#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#
#################################
#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#
#################################
#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#
#################################
#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#*#
################################# | |
