diff options
| -rw-r--r-- | BreadthFirstPathfinder.cpp | 67 | ||||
| -rw-r--r-- | BreadthFirstPathfinder.h | 24 | ||||
| -rw-r--r-- | CMakeLists.txt | 3 | ||||
| -rw-r--r-- | DijkstraPathfinder.cpp | 3 | ||||
| -rw-r--r-- | DijkstraPathfinder.h | 9 | ||||
| -rw-r--r-- | Pathfinder.cpp | 26 | ||||
| -rw-r--r-- | Pathfinder.h | 33 | ||||
| -rw-r--r-- | PathfindingContext.cpp | 40 | ||||
| -rw-r--r-- | PathfindingContext.h | 13 | ||||
| -rw-r--r-- | ViewController.cpp | 57 | ||||
| -rw-r--r-- | ViewController.h | 7 | ||||
| -rw-r--r-- | XY.cpp | 10 | ||||
| -rw-r--r-- | XY.h | 2 | ||||
| -rw-r--r-- | docs/class-diag.puml | 37 |
14 files changed, 296 insertions, 35 deletions
diff --git a/BreadthFirstPathfinder.cpp b/BreadthFirstPathfinder.cpp new file mode 100644 index 0000000..ef4492a --- /dev/null +++ b/BreadthFirstPathfinder.cpp @@ -0,0 +1,67 @@ +#include "BreadthFirstPathfinder.h" +#include "Museum.h" +#include "NullTileBehavior.h" + +using namespace std; + +void BreadthFirstPathfinder::clear() { + Pathfinder::clear(); + this->solution.clear(); +} + +const BreadthFirstPathfinder::Path & BreadthFirstPathfinder::get_path() { + return this->solution; +} + +void BreadthFirstPathfinder::find_between(const XY & start, const XY & end) { + this->clear(); + + vector<Path> trails = { { start } }; + this->end = end; + + while (trails.size() > 0) { + trails = this->find_step(trails); + } +} + +vector<BreadthFirstPathfinder::Path> BreadthFirstPathfinder::find_step(const vector<Path> & to_visit) { + vector<Path> next_step = {}; + + for (Path trail : to_visit) { + const XY & here = trail.front(); + if (here == this->end) { + this->solution = trail; + return {}; + } + + Tile & tile = this->museum.canvas.get_tile(here); + const XY offsets[] = { + { 0, 1 }, + { 1, 0 }, + { 0, -1 }, + { -1, 0 }, + }; + for (size_t i = 0; i < 4; i++) { + const XY offset = offsets[i]; + Tile * neighbor = tile.get_neighbor(offset); + + // if neighbor doesn't exist (out of bounds) + if (neighbor == nullptr) continue; + + // if neighbor is a blank tile + TileBehavior * behavior = neighbor->behavior.get(); + if (dynamic_cast<NullTileBehavior *>(behavior) != nullptr) continue;; + + // if neighbor is already visited + if (this->is_visited(here + offset)) continue; + this->set_visited(here + offset); + + Path trail_copy = trail; + trail_copy.push_front(here + offset); + next_step.push_back(trail_copy); + } + } + + return next_step; +} + diff --git a/BreadthFirstPathfinder.h b/BreadthFirstPathfinder.h new file mode 100644 index 0000000..ba05f70 --- /dev/null +++ b/BreadthFirstPathfinder.h @@ -0,0 +1,24 @@ +#pragma once + +#include "Pathfinder.h" + +#include <vector> + +class BreadthFirstPathfinder : public Pathfinder { + using Pathfinder::Pathfinder; + +public: + virtual void find_between(const XY &, const XY &); + virtual const Path & get_path(); + +private: + std::vector<Path> find_step(const std::vector<Path> &); + Path solution; + + XY end; + +protected: + virtual void clear(); + +}; + diff --git a/CMakeLists.txt b/CMakeLists.txt index 51a2557..e89069e 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -56,6 +56,9 @@ add_executable(main CycleCollisionMethodCommand.cpp PathfindingContext.cpp XY.cpp + Pathfinder.cpp + DijkstraPathfinder.cpp + BreadthFirstPathfinder.cpp ) target_link_libraries(main diff --git a/DijkstraPathfinder.cpp b/DijkstraPathfinder.cpp new file mode 100644 index 0000000..1603094 --- /dev/null +++ b/DijkstraPathfinder.cpp @@ -0,0 +1,3 @@ +#include "DijkstraPathfinder.h" + + diff --git a/DijkstraPathfinder.h b/DijkstraPathfinder.h new file mode 100644 index 0000000..af475dd --- /dev/null +++ b/DijkstraPathfinder.h @@ -0,0 +1,9 @@ +#pragma once + +#include "Pathfinder.h" + +class DijkstraPathfinder : public Pathfinder { + using Pathfinder::Pathfinder; + +}; + diff --git a/Pathfinder.cpp b/Pathfinder.cpp new file mode 100644 index 0000000..deb6040 --- /dev/null +++ b/Pathfinder.cpp @@ -0,0 +1,26 @@ +#include <algorithm> + +#include "Pathfinder.h" +#include "Museum.h" + +using namespace std; + +Pathfinder::Pathfinder(Museum & m) : museum(m) { +} + +void Pathfinder::set_visited(const XY & point) { + this->visisted[point.y * this->museum.canvas.data.columns + point.x] = true; +} + +bool Pathfinder::is_visited(const XY & point) { + size_t idx = point.y * this->museum.canvas.data.columns + point.x; + if (idx >= this->visisted.size()) return false; + return this->visisted[idx]; +} + +void Pathfinder::clear() { + CanvasData & canvas = this->museum.canvas.data; + this->visisted.resize(canvas.columns * canvas.rows); + fill(this->visisted.begin(), this->visisted.end(), false); +} + diff --git a/Pathfinder.h b/Pathfinder.h new file mode 100644 index 0000000..9c362dc --- /dev/null +++ b/Pathfinder.h @@ -0,0 +1,33 @@ +#pragma once + +#include <vector> +#include <forward_list> + +#include "XY.h" + +class Museum; +class Canvas; + +class Pathfinder { +public: + typedef std::forward_list<XY> Path; + +public: + Pathfinder(Museum &); + + virtual void find_between(const XY &, const XY &) = 0; + virtual const Path & get_path() = 0; + + virtual bool is_visited(const XY &); + +protected: + virtual void clear(); + virtual void set_visited(const XY &); + +private: + std::vector<bool> visisted; + +protected: + Museum & museum; +}; + diff --git a/PathfindingContext.cpp b/PathfindingContext.cpp index cfebb44..bcc9f37 100644 --- a/PathfindingContext.cpp +++ b/PathfindingContext.cpp @@ -2,19 +2,36 @@ #include "XY.h" #include "Museum.h" #include "NullTileBehavior.h" +#include "ToggleMuseumPauseCommand.h" + +#include "DijkstraPathfinder.h" +#include "BreadthFirstPathfinder.h" using namespace std; -PathfindingContext::PathfindingContext(Museum & m) : museum(m) {} +PathfindingContext::PathfindingContext(Museum & m) : museum(m) { + // this->solvers.push_back(unique_ptr<Pathfinder>(new DijkstraPathfinder(m))); + this->solvers.push_back(unique_ptr<Pathfinder>(new BreadthFirstPathfinder(m))); +} + +void PathfindingContext::cycle_solver() { + this->solver_index = (this->solver_index + 1) % this->solvers.size(); +} + +Pathfinder & PathfindingContext::get_solver() { + return *this->solvers[this->solver_index]; +} void PathfindingContext::set_start(const XY & point) { - if (!this->valid_point(point)) return; + if (!this->valid_point(point)) return; this->start_point = point; + this->update(); } void PathfindingContext::set_end(const XY & point) { - if (!this->valid_point(point)) return; + if (!this->valid_point(point)) return; this->end_point = point; + this->update(); } bool PathfindingContext::valid_point(const XY & point) { @@ -31,3 +48,20 @@ bool PathfindingContext::valid_point(const XY & point) { return true; } +void PathfindingContext::update() { + bool valid = true; + if (!this->valid_point(this->start_point)) { + this->start_point = { -1, -1 }; + valid = false; + } + if (!this->valid_point(this->end_point)) { + this->end_point = { -1, -1 }; + valid = false; + } + if (!valid) return; + + ToggleMuseumPauseCommand(this->museum, true).execute(); + Pathfinder & solver = this->get_solver(); + solver.find_between(this->start_point, this->end_point); +} + diff --git a/PathfindingContext.h b/PathfindingContext.h index 19fd93d..7c7f173 100644 --- a/PathfindingContext.h +++ b/PathfindingContext.h @@ -1,6 +1,10 @@ #pragma once +#include <memory> +#include <vector> + #include "XY.h" +#include "Pathfinder.h" class Museum; @@ -15,10 +19,19 @@ public: const XY & get_end() { return this->end_point; } bool valid_point(const XY & point); + void update(); + private: XY start_point = { -1, -1 }; XY end_point = { -1, -1 }; +public: + Pathfinder & get_solver(); + void cycle_solver(); +private: + std::vector<std::unique_ptr<Pathfinder>> solvers; + size_t solver_index = 0; + private: Museum & museum; }; diff --git a/ViewController.cpp b/ViewController.cpp index 40e624a..b1fd795 100644 --- a/ViewController.cpp +++ b/ViewController.cpp @@ -14,6 +14,7 @@ #include "TimeTravelCommand.h" #include "View.h" #include "Museum.h" +#include "Pathfinder.h" using namespace std; @@ -43,10 +44,10 @@ void ViewController::update_tiles() { for (int x = 0; x < this->museum.canvas.data.columns; x++) { Tile & tile = this->museum.canvas.get_tile({ x, y }); Rectangle rect = { - .x = static_cast<float>(x * scale), - .y = static_cast<float>(y * scale), - .width = static_cast<float>(scale - line_width), - .height = static_cast<float>(scale - line_width), + .x = x * scale, + .y = y * scale, + .width = scale, + .height = scale, }; this->view.fill_rect(rect, tile.color); } @@ -57,10 +58,10 @@ void ViewController::update_artists() { People & people = this->museum.people; for (Artist * artist : people.get_artists()) { Rectangle rect = { - .x = static_cast<float>(artist->data.x * scale), - .y = static_cast<float>(artist->data.y * scale), - .width = static_cast<float>(artist_size), - .height = static_cast<float>(artist_size), + .x = artist->data.x * scale, + .y = artist->data.y * scale, + .width = artist_size, + .height = artist_size, }; this->view.fill_rect(rect, artist->color); } @@ -68,26 +69,36 @@ void ViewController::update_artists() { void ViewController::draw_pathfinding_dot(const XY & point, const Color & color) { this->view.fill_rect(center({ - .x = static_cast<float>(point.x * scale), - .y = static_cast<float>(point.y * scale), - .width = static_cast<float>(pathfinding_size), - .height = static_cast<float>(pathfinding_size), + .x = point.x * scale, + .y = point.y * scale, + .width = pathfinding_size, + .height = pathfinding_size, }), color); } void ViewController::update_pathfinding() { - PathfindingContext & ctx = this->museum.pathfinding; - this->draw_pathfinding_dot(ctx.get_end(), { - .red = 0x00, - .green = 0x00, - .blue = 0xdd, - }); - this->draw_pathfinding_dot(ctx.get_start(), { - .red = 0xff, - .green = 0xff, - .blue = 0xff, - }); + + Pathfinder & solver = ctx.get_solver(); + for (int y = 0; y < this->museum.canvas.data.rows; y++) { + for (int x = 0; x < this->museum.canvas.data.columns; x++) { + if (!solver.is_visited({ x, y })) continue; + Rectangle rect = { + .x = x * scale, + .y = y * scale, + .width = scale, + .height = scale, + }; + this->view.draw_rect(rect, { 0, 0, 0 }, 2); + } + } + + const Pathfinder::Path & solution = solver.get_path(); + for (const XY & point : solution) { + this->draw_pathfinding_dot(point, { 0, 0, 0 }); + } + + this->draw_pathfinding_dot(ctx.get_start(), { 0xff, 0xff, 0xff }); } void ViewController::update_quadtree_recursive(QuadTreeCollisionChecker * tree) { diff --git a/ViewController.h b/ViewController.h index d50dfb1..ce069bd 100644 --- a/ViewController.h +++ b/ViewController.h @@ -47,10 +47,9 @@ private: bool draw_quadtree = true; private: - unsigned int scale = 16; - unsigned int line_width = 0; - unsigned int artist_size = (scale - line_width) / 2; - unsigned int pathfinding_size = scale - 4; + float scale = 16; + float artist_size = scale / 2; + float pathfinding_size = artist_size; private: XY mouse_pos; @@ -33,3 +33,13 @@ XY& XY::operator -= (const XY & rhs) { return *this; } +bool XY::operator == (const XY& rhs) const { + if (this->x != rhs.x) return false; + if (this->y != rhs.y) return false; + return true; +} + +bool XY::operator != (const XY& rhs) const { + return !(*this == rhs); +} + @@ -9,5 +9,7 @@ struct XY { XY operator - (const XY &) const; XY& operator += (const XY &); XY& operator -= (const XY &); + bool operator == (const XY& other) const; + bool operator != (const XY& other) const; }; diff --git a/docs/class-diag.puml b/docs/class-diag.puml index 2d890d5..32b7018 100644 --- a/docs/class-diag.puml +++ b/docs/class-diag.puml @@ -148,13 +148,41 @@ rectangle Group_Collisions as "Collisions" <<group>> { rectangle Group_Pathfinding as "Pathfinding" <<group>> { class PathfindingContext { + PathfindingContext(Museum &) + -- + - start_point : XY <<+get>> <<+set>> + - end_point : XY <<+get>> <<+set>> + + valid_point(const XY &) : bool + + update() + -- + + get_solver() : Pathfinder & + + cycle_solver() + -- + - solvers : vec<uniq<Pathfinder>> + - solver_index : size_t + - museum : Museum & } class Pathfinder <<abstract>> { + Pathfinder(Museum &) + + find_between(const XY &, const XY &) <<pure virtual> + + get_path() : const forward_list<XY> & <<pure virtual>> + -- + + is_visited(const XY &) : bool + # set_visited(const XY &) + -- + # clear() + - visited : vec<bool> -- # museum : Museum & } class BreadthFirstPathfinder { + + find_between(const XY &, const XY &) + + get_path() : const forward_list<XY> & + -- + - find_step(const vec<forward_list<XY>> &) : vec<forward_list<XY>> + - solution : forward_list<XY> + - end : XY + -- + # clear() } class DijkstraPathfinder { } @@ -185,7 +213,7 @@ rectangle Group_Model as "Model" <<group>> { class Canvas { + Canvas(Museum &) -- - + get_tile(x, y) : Tile & + + get_tile(XY) : Tile & + set_tile(TileData) -- + update() @@ -222,7 +250,7 @@ rectangle Group_Model as "Model" <<group>> { + set_data(TileData &) + set_type(type : const string &) + update() - + get_neighbor(dx, dy) : Tile * + + get_neighbor(XY) : Tile * -- - museum : Museum & } @@ -408,11 +436,10 @@ rectangle Group_Commands as "Commands" <<group>> { - files : vec<string> } class StepTileCommand { - + constructor(Canvas &, pair<x, y>) + + constructor(Canvas &, const XY &) -- - canvas : Canvas & - - x : unsigned int - - y : unsigned int + - tile_pos : XY } class TimeTravelCommand { + constructor(Museum &, forwards : bool) |