From 5dae8f8d10d506abc3c75a1f66c1dfe620c84fc1 Mon Sep 17 00:00:00 2001 From: HampusM Date: Tue, 15 Feb 2022 20:27:51 +0100 Subject: refactor: improve project design --- src/app/app.cpp | 26 +++++++++ src/app/app.hpp | 5 ++ src/app/maze.hpp | 23 ++++++++ src/app/maze.tpp | 153 ++++++++++++++++++++++++++++++++++++++++++++++++++++ src/app/options.cpp | 43 +++++++++++++++ src/app/options.hpp | 38 +++++++++++++ src/app/stack.hpp | 41 ++++++++++++++ src/app/stack.tpp | 45 ++++++++++++++++ 8 files changed, 374 insertions(+) create mode 100644 src/app/app.cpp create mode 100644 src/app/app.hpp create mode 100644 src/app/maze.hpp create mode 100644 src/app/maze.tpp create mode 100644 src/app/options.cpp create mode 100644 src/app/options.hpp create mode 100644 src/app/stack.hpp create mode 100644 src/app/stack.tpp (limited to 'src/app') 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 +#include + +void app_start(const AppOptions &app_options) +{ + Matrix 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(&matrix, std::make_shared(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 +#include + +/** + * 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 +void matrix_to_maze(Matrix *matrix, std::shared_ptr start_pos, + Element space_element, + const std::shared_ptr& 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 +#include + +/** + * 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 +std::vector> get_neighbours(Matrix *matrix, + const std::shared_ptr &pos, + Element space_element) +{ + std::vector> 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 +unsigned int get_maze_size(Matrix *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 &between_pos, unsigned int coord, + unsigned int away_coord, Vector2 diff) +{ + if (away_coord > coord) + { + *between_pos += diff; + } + else + { + *between_pos -= diff; + } +} + +template +void matrix_to_maze(Matrix *matrix, std::shared_ptr start_pos, + Element space_element, + const std::shared_ptr &random_gen) +{ + Stack> 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(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 + +std::shared_ptr AppOptions::maze_bounds() const +{ + return _maze_bounds; +} + +void AppOptions::maze_bounds(std::shared_ptr maze_bounds) +{ + _maze_bounds = std::move(maze_bounds); +} + +std::shared_ptr AppOptions::start_coords() const +{ + return _start_coords; +} + +void AppOptions::start_coords(std::shared_ptr 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 AppOptions::random_gen() const +{ + return _random_gen; +} + +void AppOptions::random_gen(std::shared_ptr 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 +#include + +/** + * Application options. + */ +class AppOptions +{ +public: + AppOptions() = default; + + [[nodiscard]] std::shared_ptr maze_bounds() const; + void maze_bounds(std::shared_ptr maze_bounds); + + [[nodiscard]] std::shared_ptr start_coords() const; + void start_coords(std::shared_ptr start_coords); + + [[nodiscard]] std::string_view wall() const; + void wall(std::string_view wall); + + [[nodiscard]] std::shared_ptr random_gen() const; + void random_gen(std::shared_ptr random_gen); + +private: + std::shared_ptr _maze_bounds = nullptr; + + std::shared_ptr _start_coords = nullptr; + + std::string_view _wall; + + std::shared_ptr _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 +#include + +/** + * A stack data structure. + */ +template +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 _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 +#include + +template +Stack::Stack(uint64_t capacity) +{ + _items.reserve(capacity); +} + +template +void Stack::push(Item item) +{ + if (_items.size() == _items.capacity()) + { + throw std::overflow_error("Tried to push when stack is full"); + } + + _items.push_back(item); +} + +template +void Stack::pop() +{ + if (_items.empty()) + { + throw std::underflow_error("Tried to pop when stack size is 0"); + } + + _items.pop_back(); +} + +template +Item Stack::peek() +{ + if (_items.empty()) + { + throw std::underflow_error("Tried to peek when stack size is 0"); + } + + return _items.back(); +} -- cgit v1.2.3-18-g5258