1 files changed, 131 insertions, 0 deletions
diff --git a/src/maze.tpp b/src/maze.tpp
new file mode 100644
index 0000000..6c4fd71
--- /dev/null
+++ b/src/maze.tpp
@@ -0,0 +1,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);
+	}
+}