1 files changed, 153 insertions, 0 deletions
diff --git a/src/app/maze.tpp b/src/app/maze.tpp
new file mode 100644
index 0000000..1ed69ac
--- /dev/null
+++ b/src/app/maze.tpp
@@ -0,0 +1,153 @@
+#pragma once
+
+#include "maze.hpp"
+
+#include "app/stack.hpp"
+
+#include <utility>
+#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,
+													 const 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({.x = 0U, .y = 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({.x = 0U, .y = 2U})).copy();
+
+		if (matrix->get(*pos_up) != space_element)
+		{
+			neighbours.push_back(pos_up);
+		}
+	}
+
+	if (pos->x() != 1U)
+	{
+		auto pos_left = (*pos - Vector2({.x = 2U, .y = 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({.x = 2U, .y = 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(const 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,
+					const std::shared_ptr<RandomNumberGenerator> &random_gen)
+{
+	Stack<std::shared_ptr<Vector2>> path_stack(get_maze_size(matrix));
+
+	path_stack.push(std::move(start_pos));
+
+	unsigned int visited_pos_cnt = 0U;
+	while (true)
+	{
+		auto pos = path_stack.peek();
+
+		matrix->set(*pos, space_element);
+
+		auto 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 next_pos = neighbours[random_gen->in_range(
+			0U, static_cast<unsigned int>(neighbours.size()) - 1U)];
+
+		auto between_pos = pos->copy();
+
+		if (next_pos->y() != pos->y())
+		{
+			pos_to_between(between_pos, pos->y(), next_pos->y(),
+						   Vector2({.x = 0U, .y = 1U}));
+		}
+
+		if (next_pos->x() != pos->x())
+		{
+			pos_to_between(between_pos, pos->x(), next_pos->x(),
+						   Vector2({.x = 1U, .y = 0U}));
+		}
+
+		matrix->set(*between_pos, space_element);
+
+		path_stack.push(next_pos);
+	}
+}