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 "maze.h"
#include "grid.h"
#include "position.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int is_pos_empty(Grid grid, Position pos)
{
return strcmp(grid_get(grid, pos), " ") != 0;
}
void add_neighbour(Position neighbours[], uint8_t *neighbour_cnt, Position neighbour_pos)
{
neighbours[*neighbour_cnt] = neighbour_pos;
(*neighbour_cnt)++;
}
void get_neighbours(Grid grid, Position pos, Position neighbours[], uint8_t *neighbour_cnt)
{
if (pos.y != 1)
{
Position pos_down = position_create(pos.x, pos.y - 2);
if (is_pos_empty(grid, pos_down))
add_neighbour(neighbours, neighbour_cnt, pos_down);
}
if (pos.y != grid.dimens.height - 2)
{
Position pos_up = position_create(pos.x, pos.y + 2);
if (is_pos_empty(grid, pos_up))
add_neighbour(neighbours, neighbour_cnt, pos_up);
}
if (pos.x != 1)
{
Position pos_left = position_create(pos.x - 2, pos.y);
if (is_pos_empty(grid, pos_left))
add_neighbour(neighbours, neighbour_cnt, pos_left);
}
if (pos.x != grid.dimens.width - 2)
{
Position pos_right = position_create(pos.x + 2, pos.y);
if (is_pos_empty(grid, pos_right))
add_neighbour(neighbours, neighbour_cnt, pos_right);
}
}
unsigned int get_maze_size(Grid grid)
{
return ((grid.dimens.width - 1) / 2) * ((grid.dimens.height - 1) / 2);
}
int is_whole_maze_visited(Grid grid, unsigned int visited_pos_cnt)
{
return visited_pos_cnt == get_maze_size(grid) - 1;
}
void grid_to_maze(Grid grid, Position start_pos)
{
PositionStack *path = pos_stack_create(get_maze_size(grid));
pos_stack_push(path, start_pos);
unsigned int visited_pos_cnt = 0;
while (1)
{
Position pos = pos_stack_peek(path);
grid_set(grid, pos, " ");
Position neighbours[3];
uint8_t neighbour_cnt = 0;
get_neighbours(grid, pos, neighbours, &neighbour_cnt);
if (neighbour_cnt == 0)
{
if (is_whole_maze_visited(grid, visited_pos_cnt))
break;
// Go back a step
pos_stack_pop(path);
continue;
}
visited_pos_cnt++;
Position next_pos = neighbours[rand() % neighbour_cnt];
Position between_pos = position_create(pos.x, pos.y);
if (next_pos.y != pos.y)
between_pos.y += next_pos.y > pos.y ? 1 : -1;
if (next_pos.x != pos.x)
between_pos.x += next_pos.x > pos.x ? 1 : -1;
grid_set(grid, between_pos, " ");
pos_stack_push(path, next_pos);
}
pos_stack_destroy(path);
}
|
