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
|
#include "matrix.hpp"
#include "maze.hpp"
#include "stack.hpp"
#include <vector>
/**
* Returns the neighbours of a position in a maze.
*
* @param matrix A matrix
* @param pos A matrix position
* @param space_element A matrix element used to indicate a space in a maze
*/
template <typename Element>
std::vector<std::shared_ptr<Vector2>> get_neighbours(Matrix<Element> *matrix,
std::shared_ptr<Vector2> pos,
Element space_element)
{
std::vector<std::shared_ptr<Vector2>> neighbours;
neighbours.reserve(3);
if (pos->y() != 1U)
{
auto pos_down = (*pos - Vector2(0U, 2U)).copy();
if (matrix->get(*pos_down) != space_element)
neighbours.push_back(pos_down);
}
if (pos->y() != matrix->rows() - 2U)
{
auto pos_up = (*pos + Vector2(0U, 2U)).copy();
if (matrix->get(*pos_up) != space_element)
neighbours.push_back(pos_up);
}
if (pos->x() != 1U)
{
auto pos_left = (*pos - Vector2(2U, 0U)).copy();
if (matrix->get(*pos_left) != space_element)
neighbours.push_back(pos_left);
}
if (pos->x() != matrix->columns() - 2U)
{
auto pos_right = (*pos + Vector2(2U, 0U)).copy();
if (matrix->get(*pos_right) != space_element)
neighbours.push_back(pos_right);
}
return neighbours;
}
/**
* Returns the logical size of a maze for a matrix.
*
* @param matrix A matrix
*/
template <typename Element>
unsigned int get_maze_size(Matrix<Element> *matrix)
{
return ((matrix->columns() - 1U) / 2U) * ((matrix->rows() - 1U) / 2U);
}
/**
* Makes a position be between two coordinates with a differential vector.
*
* @param between_pos Target position
* @param coord A coordinate
* @param coord A second coordinate that must not be equal too the first
* @param diff A differential vector to apply to the target position
*/
void pos_to_between(std::shared_ptr<Vector2> between_pos, unsigned int coord,
unsigned int away_coord, Vector2 diff)
{
if (away_coord > coord)
*between_pos += diff;
else
*between_pos -= diff;
}
template <typename Element>
void matrix_to_maze(Matrix<Element> *matrix, std::shared_ptr<Vector2> start_pos,
Element space_element, std::mt19937 random_gen)
{
Stack<std::shared_ptr<Vector2>> path_stack(get_maze_size(matrix));
path_stack.push(start_pos);
unsigned int visited_pos_cnt = 0U;
while (1)
{
auto pos = path_stack.peek();
matrix->set(*pos, space_element);
std::vector<std::shared_ptr<Vector2>> neighbours =
get_neighbours(matrix, pos, space_element);
if (neighbours.empty())
{
if (visited_pos_cnt == get_maze_size(matrix) - 1U)
break;
// Go back a step
path_stack.pop();
continue;
}
visited_pos_cnt++;
auto random_dist =
std::uniform_int_distribution<unsigned int>(0U, neighbours.size() - 1UL);
auto next_pos = neighbours[random_dist(random_gen)];
auto between_pos = pos->copy();
if (next_pos->y() != pos->y())
pos_to_between(between_pos, pos->y(), next_pos->y(), Vector2(0U, 1U));
if (next_pos->x() != pos->x())
pos_to_between(between_pos, pos->x(), next_pos->x(), Vector2(1U, 0U));
matrix->set(*between_pos, space_element);
path_stack.push(next_pos);
}
}
|
