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
230
231
232
233
234
235
236
237
238
|
#include "stack.h"
#include <ctype.h>
#include <getopt.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
// Error handling
void err(int id)
{
switch (id)
{
case 0:
printf("Error: Stack overflow\nBe kind and report this problem.");
break;
case 1:
printf("Error: Stack underflow\nBe kind and report this problem.");
break;
}
exit(1);
}
// Get a position in the maze from coordinates y and x
//
// This is achieved by concatenating the binary values of the two variables.
//
// For example:
// Y: 8 00001000
// X: 15 00001111
// Will become:
// 0000100000001111
int get_maze_pos(int posY, int posX) { return ((posY) << 8) | posX; }
// Get y and x coordinates from a position in the maze
//
// This is achived by using bitwise operations
//
// >> is the bitwise right shift operator and will shift bits to the right
// & is the bitwise and operator and is used to get only specific bits
int get_maze_coords(int pos, int *y, int *x)
{
*y = pos >> 8;
*x = pos & 255;
return 1;
}
// Find out if a string is a number by running it through
// isdigit() char-by-char
int is_number(char *str)
{
size_t len = strlen(str);
for (int c = 0; c < len; c++)
{
if (!isdigit(str[c]))
return 0;
}
return 1;
}
int main(int argc, char *argv[])
{
int maze_width = 40;
int maze_heigth = 20;
char *wall = "█";
int seed = 0;
static struct option options[] = {
/* NAME ARGUMENT FLAG SHORTNAME */
{"width", required_argument, NULL, 'w'},
{"heigth", required_argument, NULL, 'h'},
{"wall", required_argument, NULL, 'W'},
{"seed", required_argument, NULL, 's'},
{"help", no_argument, NULL, 0},
{NULL, 0, NULL, 0}};
int c;
while ((c = getopt_long(argc, argv, "w:h:W:s:", options, NULL)) != -1)
{
switch (c)
{
case 'w':
case 'h':
// Set heigth or width
if (is_number(optarg) && atoi(optarg) >= 1 && atoi(optarg) <= 255)
switch (c)
{
case 'h':
maze_heigth = atoi(optarg);
case 'w':
maze_width = atoi(optarg);
}
else
{
printf("Invalid option argument for -%c!\n", c);
exit(1);
}
break;
case 'W':
// Set the wall
wall = optarg;
break;
case 's':
// Set the seed
if (is_number(optarg))
{
seed = atoi(optarg);
break;
}
else
{
printf("Invalid option argument for -s/--seed!\n");
exit(1);
}
case 0:
// Help
printf(
"Usage: mazerator [--help] [-W wall] [-s seed] [-w width] [-h heigth]\n\n\
OPTIONS\n\
--width -w The width of the maze. (1-255). Default: 40\n\
--heigth -h The heigth of the maze. (1-255). Default: 20\n\
--wall -W Single character used as maze walls. Default: '█'\n\
--seed -s The randomization seed used for maze generation. (Any number). Default is to read /dev/urandom\n\
--help Displays usage information\n\
");
exit(0);
case '?':
printf("\nTry 'mazerator --help' for more information\n");
exit(1);
}
}
int maze[maze_heigth][maze_width];
char *maze_visual[maze_heigth * 2 + 1][maze_width * 2 + 1];
struct stack *path = new_stack(maze_width * maze_heigth);
// Prepares seed value for randr()
// Get's a seed from /dev/urandom if not already set
if (seed == 0)
{
printf("What");
FILE *f = fopen("/dev/urandom", "r");
fread(&seed, sizeof(seed), 1, f);
fclose(f);
}
srand(seed);
// Prepares the maze grids
// Fills the maze with zeroes indicating that none of the grid squares have
// been visited
//
// Fills the visual maze with walls
for (int y = 0; y < sizeof(maze) / sizeof(maze[0]); y++)
{
for (int x = 0; x < sizeof(maze[0]) / sizeof(maze[0][0]); x++)
{
maze[y][x] = 0;
}
}
for (int y = 0; y < sizeof(maze_visual) / sizeof(maze_visual[0]); y++)
{
for (int x = 0; x < sizeof(maze_visual[0]) / sizeof(maze_visual[0][0]);
x++)
{
maze_visual[y][x] = wall;
}
}
// Set the start value (0, 0) and begin the algoritm loop
stack_push(path, 0);
int cnt = 0;
while (1)
{
int pos = stack_peek(path);
int posY, posX;
get_maze_coords(pos, &posY, &posX);
// Set the currently visited grid square to 1 indicating that it has been
// visited and excavate the visual maze
maze[posY][posX] = 1;
maze_visual[posY * 2 + 1][posX * 2 + 1] = " ";
// Find out available next positions to go to
int neighbours[3];
int i = 0;
if (posY != 0 && maze[posY - 1][posX] == 0)
{
neighbours[i] = get_maze_pos(posY - 1, posX);
i++;
}
if (posY != maze_heigth - 1 && maze[posY + 1][posX] == 0)
{
neighbours[i] = get_maze_pos(posY + 1, posX);
i++;
}
if (posX != 0 && maze[posY][posX - 1] == 0)
{
neighbours[i] = get_maze_pos(posY, posX - 1);
i++;
}
if (posX != maze_width - 1 && maze[posY][posX + 1] == 0)
{
neighbours[i] = get_maze_pos(posY, posX + 1);
i++;
}
switch (i)
{
case 0:
// No available next positions
if (cnt == (maze_heigth * maze_width) - 1)
{
for (int y = 0; y < sizeof(maze_visual) / sizeof(maze_visual[0]); y++)
{
for (int x = 0;
x < sizeof(maze_visual[0]) / sizeof(maze_visual[0][0]); x++)
{
printf("%s", maze_visual[y][x]);
}
printf("\n");
}
exit(0);
}
stack_pop(path);
break;
default:
// Available next positions
// Choose a random one and go there
cnt++;
int next = neighbours[rand() % i];
int next_y, next_x;
get_maze_coords(next, &next_y, &next_x);
maze_visual[posY * 2 - (posY - next_y) + 1]
[posX * 2 - (posX - next_x) + 1] = " ";
stack_push(path, next);
}
}
}
|
