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
|
#include <stdlib.h>
#include "maze_generator.h"
#include "utilities.h"
#include "maze.h"
static void remove_wall(int **graph, struct point a, struct point b)
{
int diff_x = a.x - b.x;
int diff_y = a.y - b.y;
if (diff_y == 0)
{
if (diff_x == 1)
graph[b.x][b.y] &= 3;
else if (diff_x == -1)
graph[a.x][a.y] &= 3;
}
else if (diff_x == 0)
{
if (diff_y == 1)
graph[b.x][b.y] &= 5;
else if (diff_y == -1)
graph[a.x][a.y] &= 5;
}
}
static void generate_maze_graph(int **graph, int width, int height, struct point point)
{
//I've been here.
graph[point.x][point.y] &= 6;
struct point points[4];
int index = 0;
//Possibilities:
if (point.x > 0)
points[index++] = relative_point(point, -1, 0);
if (point.x < width - 1)
points[index++] = relative_point(point, 1, 0);
if (point.y > 0)
points[index++] = relative_point(point, 0, -1);
if (point.y < height - 1)
points[index++] = relative_point(point, 0, 1);
//Shuffle:
shuffle(points, index, sizeof(struct point));
//Examine possibilities:
index--;
struct point new_point;
while (index >= 0)
{
new_point = points[index];
if ((graph[new_point.x][new_point.y] & 1) == 1)
{
//Remove wall:
remove_wall(graph, point, new_point);
//Go on:
generate_maze_graph(graph, width, height, new_point);
}
index--;
}
}
int generate_maze(struct maze *maze)
{
if (!is_valid_maze_size(maze->width) || !is_valid_maze_size(maze->height))
return -1;
//Init graph:
int graph_width = ((maze->width - 2) + 1) / 2;
int graph_height = ((maze->height - 2) + 1) / 2;
char mem[sizeof_2d(graph_width, graph_height, sizeof(int))];
init2d((void **)mem, graph_width, graph_height, sizeof(int));
int **graph = (int **)mem;
for (int x = 0; x < graph_width; x++)
for (int y = 0; y < graph_height; y++)
graph[x][y] = 7;
//Generate graph:
struct point starting_point;
starting_point.x = 0;
starting_point.y = 0;
generate_maze_graph(graph, graph_width, graph_height, starting_point);
//Convert:
for (int x = 0; x < graph_width; x++)
{
for (int y = 0; y < graph_height; y++)
{
int real_x = (2 * x) + 1;
int real_y = (2 * y) + 1;
int is_last_x = x == maze->width - 2;
int is_last_y = y == maze->height - 2;
maze->map[real_x][real_y] = 0;
if (!is_last_x)
maze->map[real_x + 1][real_y] = (graph[x][y] & 4) == 4;
if (!is_last_y)
maze->map[real_x][real_y + 1] = (graph[x][y] & 2) == 2;
if (!(is_last_x || is_last_y))
maze->map[real_x + 1][real_y + 1] = 1;
}
}
//Set sides:
for (int x = 0; x < maze->width; x++)
{
maze->map[x][0] = 1;
maze->map[x][maze->height - 1] = 1;
}
for (int y = 0; y < maze->height; y++)
{
maze->map[0][y] = 1;
maze->map[maze->width - 1][y] = 1;
}
//Set start and end:
maze->starting_point.x = 1;
maze->starting_point.y = 1;
maze->end_point.x = maze->width - 2;
maze->end_point.y = maze->height - 2;
return 0;
}
|
