8 files changed, 374 insertions, 0 deletions
diff --git a/src/app/app.cpp b/src/app/app.cpp
new file mode 100644
index 0000000..0942c3e
--- /dev/null
+++ b/src/app/app.cpp
@@ -0,0 +1,26 @@
+#include "app.hpp"
+
+#include "app/maze.hpp"
+#include "engine/bounds.hpp"
+#include "engine/matrix.hpp"
+#include "engine/vector2.hpp"
+
+#include <memory>
+#include <string_view>
+
+void app_start(const AppOptions &app_options)
+{
+	Matrix<std::string_view> matrix(*app_options.maze_bounds() *
+										Bounds({.width = 2U, .height = 2U}) +
+									Bounds({.width = 1U, .height = 1U}));
+
+	matrix.fill(app_options.wall());
+
+	auto start_pos = *app_options.start_coords() * Vector2({.x = 2U, .y = 2U}) +
+					 Vector2({.x = 1U, .y = 1U});
+
+	matrix_to_maze<std::string_view>(&matrix, std::make_shared<Vector2>(start_pos), " ",
+									 app_options.random_gen());
+
+	matrix.print();
+}
diff --git a/src/app/app.hpp b/src/app/app.hpp
new file mode 100644
index 0000000..d02c405
--- /dev/null
+++ b/src/app/app.hpp
@@ -0,0 +1,5 @@
+#pragma once
+
+#include "app/options.hpp"
+
+void app_start(const AppOptions &app_options);
diff --git a/src/app/maze.hpp b/src/app/maze.hpp
new file mode 100644
index 0000000..2dd05a5
--- /dev/null
+++ b/src/app/maze.hpp
@@ -0,0 +1,23 @@
+#pragma once
+
+#include "engine/matrix.hpp"
+#include "engine/vector2.hpp"
+#include "random_generator.hpp"
+
+#include <memory>
+#include <string>
+
+/**
+ * Turns a matrix into a maze.
+ *
+ * @param matrix A matrix
+ * @param start_pos The start position in the matrix
+ * @param space_element A matrix element used to indicate a space in a maze
+ * @param random_gen A pseudo-random number generator
+ */
+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);
+
+#include "maze.tpp"
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);
+	}
+}
diff --git a/src/app/options.cpp b/src/app/options.cpp
new file mode 100644
index 0000000..cb6e20e
--- /dev/null
+++ b/src/app/options.cpp
@@ -0,0 +1,43 @@
+#include "options.hpp"
+
+#include <utility>
+
+std::shared_ptr<Bounds> AppOptions::maze_bounds() const
+{
+	return _maze_bounds;
+}
+
+void AppOptions::maze_bounds(std::shared_ptr<Bounds> maze_bounds)
+{
+	_maze_bounds = std::move(maze_bounds);
+}
+
+std::shared_ptr<Vector2> AppOptions::start_coords() const
+{
+	return _start_coords;
+}
+
+void AppOptions::start_coords(std::shared_ptr<Vector2> start_coords)
+{
+	_start_coords = std::move(start_coords);
+}
+
+std::string_view AppOptions::wall() const
+{
+	return _wall;
+}
+
+void AppOptions::wall(std::string_view wall)
+{
+	_wall = wall;
+}
+
+std::shared_ptr<RandomNumberGenerator> AppOptions::random_gen() const
+{
+	return _random_gen;
+}
+
+void AppOptions::random_gen(std::shared_ptr<RandomNumberGenerator> random_gen)
+{
+	_random_gen = std::move(random_gen);
+}
diff --git a/src/app/options.hpp b/src/app/options.hpp
new file mode 100644
index 0000000..0023283
--- /dev/null
+++ b/src/app/options.hpp
@@ -0,0 +1,38 @@
+#pragma once
+
+#include "engine/bounds.hpp"
+#include "engine/vector2.hpp"
+#include "random_generator.hpp"
+
+#include <memory>
+#include <string_view>
+
+/**
+ * Application options.
+ */
+class AppOptions
+{
+public:
+	AppOptions() = default;
+
+	[[nodiscard]] std::shared_ptr<Bounds> maze_bounds() const;
+	void maze_bounds(std::shared_ptr<Bounds> maze_bounds);
+
+	[[nodiscard]] std::shared_ptr<Vector2> start_coords() const;
+	void start_coords(std::shared_ptr<Vector2> start_coords);
+
+	[[nodiscard]] std::string_view wall() const;
+	void wall(std::string_view wall);
+
+	[[nodiscard]] std::shared_ptr<RandomNumberGenerator> random_gen() const;
+	void random_gen(std::shared_ptr<RandomNumberGenerator> random_gen);
+
+private:
+	std::shared_ptr<Bounds> _maze_bounds = nullptr;
+
+	std::shared_ptr<Vector2> _start_coords = nullptr;
+
+	std::string_view _wall;
+
+	std::shared_ptr<RandomNumberGenerator> _random_gen = nullptr;
+};
diff --git a/src/app/stack.hpp b/src/app/stack.hpp
new file mode 100644
index 0000000..11f7405
--- /dev/null
+++ b/src/app/stack.hpp
@@ -0,0 +1,41 @@
+#pragma once
+
+#include <cstdint>
+#include <vector>
+
+/**
+ * A stack data structure.
+ */
+template <typename Item>
+class Stack
+{
+public:
+	/**
+	 * Creates a stack.
+	 *
+	 * @param capacity The capacity of the stack
+	 */
+	explicit Stack(uint64_t capacity);
+
+	/**
+	 * Pushes a item onto the stack.
+	 */
+	void push(Item item);
+
+	/**
+	 * Pops the topmost item from the stack.
+	 */
+	void pop();
+
+	/**
+	 * Peeks into the stack.
+	 *
+	 * @returns The topmost stack item.
+	 */
+	Item peek();
+
+private:
+	std::vector<Item> _items;
+};
+
+#include "stack.tpp"
diff --git a/src/app/stack.tpp b/src/app/stack.tpp
new file mode 100644
index 0000000..bcdafc0
--- /dev/null
+++ b/src/app/stack.tpp
@@ -0,0 +1,45 @@
+#pragma once
+
+#include "stack.hpp"
+
+#include <iostream>
+#include <stdexcept>
+
+template <typename Item>
+Stack<Item>::Stack(uint64_t capacity)
+{
+	_items.reserve(capacity);
+}
+
+template <typename Item>
+void Stack<Item>::push(Item item)
+{
+	if (_items.size() == _items.capacity())
+	{
+		throw std::overflow_error("Tried to push when stack is full");
+	}
+
+	_items.push_back(item);
+}
+
+template <typename Item>
+void Stack<Item>::pop()
+{
+	if (_items.empty())
+	{
+		throw std::underflow_error("Tried to pop when stack size is 0");
+	}
+
+	_items.pop_back();
+}
+
+template <typename Item>
+Item Stack<Item>::peek()
+{
+	if (_items.empty())
+	{
+		throw std::underflow_error("Tried to peek when stack size is 0");
+	}
+
+	return _items.back();
+}