diff options
-rw-r--r-- | Artist.cpp | 23 | ||||
-rw-r--r-- | Artist.h | 3 | ||||
-rw-r--r-- | BreadthFirstPathfinder.cpp | 13 | ||||
-rw-r--r-- | BreadthFirstPathfinder.h | 6 | ||||
-rw-r--r-- | CMakeLists.txt | 9 | ||||
-rw-r--r-- | Canvas.h | 4 | ||||
-rw-r--r-- | CollisionContext.cpp | 1 | ||||
-rw-r--r-- | DijkstraPathfinder.cpp | 8 | ||||
-rw-r--r-- | DijkstraPathfinder.h | 2 | ||||
-rw-r--r-- | Museum.cpp | 2 | ||||
-rw-r--r-- | MuseumDeserializer.cpp | 2 | ||||
-rw-r--r-- | Pathfinder.cpp | 31 | ||||
-rw-r--r-- | Pathfinder.h | 16 | ||||
-rw-r--r-- | PathfindingContext.cpp | 42 | ||||
-rw-r--r-- | PathfindingContext.h | 13 | ||||
-rw-r--r-- | People.cpp | 4 | ||||
-rw-r--r-- | People.h | 2 | ||||
-rw-r--r-- | SetPathfindingEndPointCommand.cpp | 11 | ||||
-rw-r--r-- | SetPathfindingEndPointCommand.h | 19 | ||||
-rw-r--r-- | SetPathfindingStartPointCommand.cpp | 11 | ||||
-rw-r--r-- | SetPathfindingStartPointCommand.h | 19 | ||||
-rw-r--r-- | StepTileBehavior.cpp | 2 | ||||
-rw-r--r-- | TXTParser.cpp | 2 | ||||
-rw-r--r-- | Tile.cpp | 2 | ||||
-rw-r--r-- | TileColorFactory.cpp | 2 | ||||
-rw-r--r-- | TileColorFactory.h | 2 | ||||
-rw-r--r-- | ToggleArtistPathCollisionCommand.cpp | 5 | ||||
-rw-r--r-- | ToggleArtistPathCollisionCommand.h | 11 | ||||
-rw-r--r-- | ViewController.cpp | 40 | ||||
-rw-r--r-- | ViewController.h | 8 | ||||
-rw-r--r-- | readme.md | 5 |
31 files changed, 212 insertions, 108 deletions
@@ -3,15 +3,21 @@ #include "Artist.h" #include "Museum.h" +using namespace std; + Artist::Artist(Museum & museum, ArtistData data) : museum(museum) { this->data = data; this->data.vx /= 5; this->data.vy /= 5; } -void Artist::update() { - this->update_edge_collision(); - this->update_movement(); +void Artist::update(bool tick) { + if (tick) { + this->update_edge_collision(); + this->update_movement(); + } + // Artist<->Artist collisions are marked by CollisionChecker + this->update_path_collision(); this->update_color(); } @@ -38,6 +44,17 @@ void Artist::update_movement() { if (abs(int(last_y) - int(this->data.y)) > 0) this->step = true; } +void Artist::update_path_collision() { + PathfindingContext & ctx = this->museum.pathfinding; + if (!ctx.has_collision) return; + Pathfinder & solver = ctx.get_solver(); + bool is_solution = solver.is_solution({ + static_cast<int>(this->data.x), + static_cast<int>(this->data.y), + }); + if (is_solution) this->colliding = true; +} + void Artist::update_color() { if (this->colliding) { this->color = { @@ -10,11 +10,12 @@ public: Artist(Museum &, ArtistData data); public: - void update(); + void update(bool tick = true); private: void update_movement(); void update_edge_collision(); + void update_path_collision(); void update_color(); public: diff --git a/BreadthFirstPathfinder.cpp b/BreadthFirstPathfinder.cpp index e3a5430..17119e3 100644 --- a/BreadthFirstPathfinder.cpp +++ b/BreadthFirstPathfinder.cpp @@ -3,15 +3,6 @@ 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(); @@ -23,7 +14,7 @@ void BreadthFirstPathfinder::find_between(const XY & start, const XY & end) { steps++; trails = this->find_step(trails); } - printf("BFS: %s (%d steps)\n", this->solution.empty() ? "no solution found" : "solution found", steps); + printf("BFS: %s (%d steps)\n", this->is_solved() ? "no solution found" : "solution found", steps); } vector<BreadthFirstPathfinder::Path> BreadthFirstPathfinder::find_step(const vector<Path> & to_visit) { @@ -33,7 +24,7 @@ vector<BreadthFirstPathfinder::Path> BreadthFirstPathfinder::find_step(const vec for (Path trail : to_visit) { const XY & here = trail.front(); if (here == this->end) { - this->solution = trail; + this->set_solved(trail); return {}; } diff --git a/BreadthFirstPathfinder.h b/BreadthFirstPathfinder.h index 0c73c69..c8b9fe5 100644 --- a/BreadthFirstPathfinder.h +++ b/BreadthFirstPathfinder.h @@ -9,16 +9,10 @@ class BreadthFirstPathfinder : public Pathfinder { public: virtual void find_between(const XY &, const XY &); - virtual const Path & get_path(); private: - Path solution; XY end; std::vector<Path> find_step(const std::vector<Path> &); - -protected: - virtual void clear(); - }; diff --git a/CMakeLists.txt b/CMakeLists.txt index 6b221da..c4173c7 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -53,10 +53,13 @@ add_executable(main CycleCollisionMethodCommand.cpp PathfindingContext.cpp XY.cpp - Pathfinder.cpp - DijkstraPathfinder.cpp - BreadthFirstPathfinder.cpp + Pathfinder.cpp + DijkstraPathfinder.cpp + BreadthFirstPathfinder.cpp CyclePathfindingMethodCommand.cpp + SetPathfindingStartPointCommand.cpp + SetPathfindingEndPointCommand.cpp + ToggleArtistPathCollisionCommand.cpp ) target_link_libraries(main @@ -28,8 +28,8 @@ public: void set_data(CanvasData data); public: - TileColorFactory tile_color; - TileBehaviorFactory tile_behavior; + TileColorFactory tile_color; + TileBehaviorFactory tile_behavior; private: void update_steps(); diff --git a/CollisionContext.cpp b/CollisionContext.cpp index 743a452..db300f5 100644 --- a/CollisionContext.cpp +++ b/CollisionContext.cpp @@ -31,6 +31,7 @@ void CollisionContext::update() { artist->colliding = false; this->checker = this->create_checker(); this->checker->check(); + this->museum.people.update(false); } void CollisionContext::cycle_method() { diff --git a/DijkstraPathfinder.cpp b/DijkstraPathfinder.cpp index 8a8e8eb..d920fc9 100644 --- a/DijkstraPathfinder.cpp +++ b/DijkstraPathfinder.cpp @@ -1,4 +1,3 @@ -#include <algorithm> #include <queue> #include "DijkstraPathfinder.h" @@ -6,13 +5,8 @@ using namespace std; -const DijkstraPathfinder::Path & DijkstraPathfinder::get_path() { - return this->solution; -} - void DijkstraPathfinder::clear() { Pathfinder::clear(); - this->solution.clear(); this->map.clear(); } @@ -30,11 +24,13 @@ void DijkstraPathfinder::find_between(const XY & start, const XY & end) { XY pos = end; int steps = 0; + Path solution; while (pos != start) { solution.push_front(pos); pos = this->map_get(pos).parent; steps++; } + this->set_solved(solution); printf("Dijkstra: solution found (%d steps, %u time)\n", steps, this->map_get(end).distance); } diff --git a/DijkstraPathfinder.h b/DijkstraPathfinder.h index 5fb1e21..93e6943 100644 --- a/DijkstraPathfinder.h +++ b/DijkstraPathfinder.h @@ -9,13 +9,11 @@ class DijkstraPathfinder : public Pathfinder { public: virtual void find_between(const XY &, const XY &); - virtual const Path & get_path(); protected: virtual void clear(); private: - Path solution; XY end; struct Node { @@ -34,7 +34,7 @@ void Museum::work() { while (this->working) { // immediately process forward jumps, even if paused if (this->jump > 0) { - while (--this->jump > 0) + for (; this->jump != 0; this->jump--) this->update(); } diff --git a/MuseumDeserializer.cpp b/MuseumDeserializer.cpp index 4f53887..8518872 100644 --- a/MuseumDeserializer.cpp +++ b/MuseumDeserializer.cpp @@ -17,7 +17,7 @@ void MuseumDeserializer::set_tile(TileData data) { void MuseumDeserializer::add_type(std::string type, Color color, unsigned int weight) { if (type.length() == 0) return; - this->museum.canvas.tile_color.register_color(type, color); + this->museum.canvas.tile_color.register_color(type, color); this->museum.pathfinding.register_weight(type, weight); } diff --git a/Pathfinder.cpp b/Pathfinder.cpp index deb6040..4cf5e76 100644 --- a/Pathfinder.cpp +++ b/Pathfinder.cpp @@ -8,19 +8,46 @@ using namespace std; Pathfinder::Pathfinder(Museum & m) : museum(m) { } +size_t Pathfinder::pos_to_idx(const XY & point) { + return point.y * this->museum.canvas.data.columns + point.x; +} + void Pathfinder::set_visited(const XY & point) { - this->visisted[point.y * this->museum.canvas.data.columns + point.x] = true; + this->visisted[this->pos_to_idx(point)] = true; } bool Pathfinder::is_visited(const XY & point) { - size_t idx = point.y * this->museum.canvas.data.columns + point.x; + size_t idx = this->pos_to_idx(point); if (idx >= this->visisted.size()) return false; return this->visisted[idx]; } +bool Pathfinder::is_solution(const XY & point) { + size_t idx = this->pos_to_idx(point); + if (idx >= this->solution.size()) return false; + return this->solution[idx]; +} + void Pathfinder::clear() { + this->solution.clear(); + this->solved = false; + CanvasData & canvas = this->museum.canvas.data; this->visisted.resize(canvas.columns * canvas.rows); fill(this->visisted.begin(), this->visisted.end(), false); } +void Pathfinder::set_solved(const Path & solution) { + this->path = solution; + this->solved = true; + + CanvasData & canvas = this->museum.canvas.data; + this->solution.resize(canvas.columns * canvas.rows); + fill(this->solution.begin(), this->solution.end(), false); + for (const XY & point : solution) { + this->solution[this->pos_to_idx(point)] = true; + } + + this->museum.people.update(false); +} + diff --git a/Pathfinder.h b/Pathfinder.h index 9c362dc..503423e 100644 --- a/Pathfinder.h +++ b/Pathfinder.h @@ -16,16 +16,24 @@ public: Pathfinder(Museum &); virtual void find_between(const XY &, const XY &) = 0; - virtual const Path & get_path() = 0; - virtual bool is_visited(const XY &); + virtual bool is_visited(const XY &); + virtual bool is_solution(const XY &); + + virtual bool is_solved() { return this->solved; } + virtual const Path & get_solution() { return this->path; } protected: - virtual void clear(); - virtual void set_visited(const XY &); + virtual void clear(); + virtual void set_visited(const XY &); + virtual void set_solved(const Path &); private: + size_t pos_to_idx(const XY &); std::vector<bool> visisted; + std::vector<bool> solution; + Path path; + bool solved = false; protected: Museum & museum; diff --git a/PathfindingContext.cpp b/PathfindingContext.cpp index 95ac3b1..49d1dc8 100644 --- a/PathfindingContext.cpp +++ b/PathfindingContext.cpp @@ -10,29 +10,29 @@ using namespace std; 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))); + 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(); + this->solver_index = (this->solver_index + 1) % this->solvers.size(); this->update(); } Pathfinder & PathfindingContext::get_solver() { - return *this->solvers[this->solver_index]; + return *this->solvers[this->solver_index]; } void PathfindingContext::set_start(const XY & point) { - if (this->empty_point(point)) return; + if (this->empty_point(point)) return; this->start_point = point; - this->update(); + this->update(); } void PathfindingContext::set_end(const XY & point) { - if (this->empty_point(point)) return; + if (this->empty_point(point)) return; this->end_point = point; - this->update(); + this->update(); } bool PathfindingContext::empty_point(const XY & point) { @@ -50,20 +50,20 @@ bool PathfindingContext::empty_point(const XY & point) { } void PathfindingContext::update() { - bool valid = true; - if (this->empty_point(this->start_point)) { - this->start_point = { -1, -1 }; - valid = false; - } - if (this->empty_point(this->end_point)) { - this->end_point = { -1, -1 }; - valid = false; - } - if (!valid) return; + bool valid = true; + if (this->empty_point(this->start_point)) { + this->start_point = { -1, -1 }; + valid = false; + } + if (this->empty_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); + ToggleMuseumPauseCommand(this->museum, true).execute(); + Pathfinder & solver = this->get_solver(); + solver.find_between(this->start_point, this->end_point); } void PathfindingContext::register_weight(const string & type, unsigned int weight) { diff --git a/PathfindingContext.h b/PathfindingContext.h index bb6fc23..c2c591c 100644 --- a/PathfindingContext.h +++ b/PathfindingContext.h @@ -12,16 +12,16 @@ class Museum; class PathfindingContext { public: PathfindingContext(Museum &); + void update(); public: void set_start(const XY & point); const XY & get_start() { return this->start_point; } void set_end(const XY & point); const XY & get_end() { return this->end_point; } +public: bool empty_point(const XY & point); - void update(); - public: void register_weight(const std::string & type, unsigned int weight); unsigned int get_weight(const std::string & type); @@ -33,11 +33,14 @@ private: XY end_point = { -1, -1 }; public: - Pathfinder & get_solver(); + Pathfinder & get_solver(); void cycle_solver(); private: - std::vector<std::unique_ptr<Pathfinder>> solvers; - size_t solver_index = 0; + std::vector<std::unique_ptr<Pathfinder>> solvers; + size_t solver_index = 0; + +public: + bool has_collision = false; private: Museum & museum; @@ -44,9 +44,9 @@ string People::to_string() { return out; } -void People::update() { +void People::update(bool tick) { for (Artist * artist : this->artists) { - artist->update(); + artist->update(tick); } } @@ -20,7 +20,7 @@ public: std::forward_list<Artist *> get_artists(); - void update(); + void update(bool tick = true); private: std::forward_list<Artist *> artists; diff --git a/SetPathfindingEndPointCommand.cpp b/SetPathfindingEndPointCommand.cpp new file mode 100644 index 0000000..c910a26 --- /dev/null +++ b/SetPathfindingEndPointCommand.cpp @@ -0,0 +1,11 @@ +#include "SetPathfindingEndPointCommand.h" +#include "Museum.h" + +SetPathfindingEndPointCommand::SetPathfindingEndPointCommand(Museum & m, const XY & point) : museum(m) { + this->point = point; +} + +void SetPathfindingEndPointCommand::execute() { + this->museum.pathfinding.set_end(this->point); +} + diff --git a/SetPathfindingEndPointCommand.h b/SetPathfindingEndPointCommand.h new file mode 100644 index 0000000..4bdc181 --- /dev/null +++ b/SetPathfindingEndPointCommand.h @@ -0,0 +1,19 @@ +#pragma once + +#include "Command.h" +#include "XY.h" + +class Museum; + +class SetPathfindingEndPointCommand : public Command { +public: + SetPathfindingEndPointCommand(Museum & m, const XY & point); + +public: + virtual void execute(); + +private: + Museum & museum; + XY point; +}; + diff --git a/SetPathfindingStartPointCommand.cpp b/SetPathfindingStartPointCommand.cpp new file mode 100644 index 0000000..9bee4ea --- /dev/null +++ b/SetPathfindingStartPointCommand.cpp @@ -0,0 +1,11 @@ +#include "SetPathfindingStartPointCommand.h" +#include "Museum.h" + +SetPathfindingStartPointCommand::SetPathfindingStartPointCommand(Museum & m, const XY & point) : museum(m) { + this->point = point; +} + +void SetPathfindingStartPointCommand::execute() { + this->museum.pathfinding.set_start(this->point); +} + diff --git a/SetPathfindingStartPointCommand.h b/SetPathfindingStartPointCommand.h new file mode 100644 index 0000000..f3ce6bf --- /dev/null +++ b/SetPathfindingStartPointCommand.h @@ -0,0 +1,19 @@ +#pragma once + +#include "Command.h" +#include "XY.h" + +class Museum; + +class SetPathfindingStartPointCommand : public Command { +public: + SetPathfindingStartPointCommand(Museum & m, const XY & point); + +public: + virtual void execute(); + +private: + Museum & museum; + XY point; +}; + diff --git a/StepTileBehavior.cpp b/StepTileBehavior.cpp index ff1217e..859845d 100644 --- a/StepTileBehavior.cpp +++ b/StepTileBehavior.cpp @@ -5,7 +5,7 @@ using namespace std; void StepTileBehavior::update(Tile & tile) { - if (this->interactions < 3) return; + if (this->interactions < 3) return; tile.set_type(DeleteArtistTileBehavior::type); } diff --git a/TXTParser.cpp b/TXTParser.cpp index 07ae62b..08c122c 100644 --- a/TXTParser.cpp +++ b/TXTParser.cpp @@ -121,7 +121,7 @@ static void parse_header_table(MuseumDeserializer & d, const std::string & heade col.push_back(c); } if (col.size() > 0) cols.push_back(col); - + if (cols.size() != 3) throw Exception("invalid header table row"); @@ -19,7 +19,7 @@ void Tile::set_type(const string & type) { void Tile::set_data(TileData & data) { this->data = data; - Canvas & canvas = this->museum.canvas; + Canvas & canvas = this->museum.canvas; this->color = canvas.tile_color.get_color(this->data.type); this->behavior = canvas.tile_behavior.create(this->data.type); } diff --git a/TileColorFactory.cpp b/TileColorFactory.cpp index 22738f6..124397a 100644 --- a/TileColorFactory.cpp +++ b/TileColorFactory.cpp @@ -5,7 +5,7 @@ using namespace std; const Color & TileColorFactory::get_color(const string & type) { if (this->collection.contains(type)) return this->collection.at(type); - + return TileColorFactory::default_color; } diff --git a/TileColorFactory.h b/TileColorFactory.h index 4394c9e..5608a01 100644 --- a/TileColorFactory.h +++ b/TileColorFactory.h @@ -13,7 +13,7 @@ public: void register_color(const std::string &, const Color &); private: - TileAppearanceCollection collection; + TileAppearanceCollection collection; static constexpr Color default_color = { .red = 0xff, .green = 0xff, diff --git a/ToggleArtistPathCollisionCommand.cpp b/ToggleArtistPathCollisionCommand.cpp new file mode 100644 index 0000000..81cfbf9 --- /dev/null +++ b/ToggleArtistPathCollisionCommand.cpp @@ -0,0 +1,5 @@ +#include "ToggleArtistPathCollisionCommand.h" +#include "Museum.h" + +ToggleArtistPathCollisionCommand::ToggleArtistPathCollisionCommand(Museum & m) : ControlBooleanCommand(m.pathfinding.has_collision) { } + diff --git a/ToggleArtistPathCollisionCommand.h b/ToggleArtistPathCollisionCommand.h new file mode 100644 index 0000000..6d3317e --- /dev/null +++ b/ToggleArtistPathCollisionCommand.h @@ -0,0 +1,11 @@ +#pragma once + +#include "ControlBooleanCommand.h" + +class Museum; + +class ToggleArtistPathCollisionCommand : public ControlBooleanCommand { +public: + ToggleArtistPathCollisionCommand(Museum & m); +}; + diff --git a/ViewController.cpp b/ViewController.cpp index 3238f0f..d1e519a 100644 --- a/ViewController.cpp +++ b/ViewController.cpp @@ -9,6 +9,9 @@ #include "Exception.h" #include "KeyboardCode.h" #include "MouseCode.h" +#include "SetPathfindingEndPointCommand.h" +#include "SetPathfindingStartPointCommand.h" +#include "ToggleArtistPathCollisionCommand.h" #include "ToggleMuseumPauseCommand.h" #include "OpenFileGUICommand.h" #include "StepTileCommand.h" @@ -80,31 +83,25 @@ void ViewController::draw_pathfinding_dot(const XY & point, const Color & color) } void ViewController::update_pathfinding() { - PathfindingContext & ctx = this->museum.pathfinding; + PathfindingContext & ctx = this->museum.pathfinding; Pathfinder & solver = ctx.get_solver(); - if (this->draw_visited) { - 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 = { + for (int y = 0; y < this->museum.canvas.data.rows; y++) { + for (int x = 0; x < this->museum.canvas.data.columns; x++) { + if (this->draw_visited && solver.is_visited({ x, y })) + this->view.draw_rect({ .x = x * scale, .y = y * scale, .width = scale, .height = scale, - }; - this->view.draw_rect(rect, { 0, 0, 0 }, 2); - } + }, { 0, 0, 0 }, 2); + if (this->draw_path && solver.is_solution({ x, y })) + this->draw_pathfinding_dot({ x, y }, { 0, 0, 0 }); } } - if (this->draw_path) { - const Pathfinder::Path & solution = solver.get_path(); - for (const XY & point : solution) { - this->draw_pathfinding_dot(point, { 0, 0, 0 }); - } + if (this->draw_path) this->draw_pathfinding_dot(ctx.get_start(), { 0xff, 0xff, 0xff }); - } } void ViewController::update_quadtree_recursive(QuadTreeCollisionChecker * tree) { @@ -181,7 +178,7 @@ void ViewController::ev_keydown(KeyboardCode key) { break; } case KEY_W: { - // TODO: toggle collision calculation between artist and path + ToggleArtistPathCollisionCommand(this->museum).execute(); break; } default: break; @@ -195,12 +192,11 @@ void ViewController::ev_mousedown(MouseCode button) { try { switch (button) { case MOUSE_LEFT: { - // TODO: call through command - this->museum.pathfinding.set_start(this->mouse_pos); + SetPathfindingStartPointCommand(this->museum, this->mouse_pos).execute(); break; } case MOUSE_RIGHT: { - this->museum.pathfinding.set_end(this->mouse_pos); + SetPathfindingEndPointCommand(this->museum, this->mouse_pos).execute(); break; } default: break; @@ -218,8 +214,8 @@ void ViewController::ev_mousemove(unsigned x, unsigned y) { } Rectangle ViewController::center(Rectangle rect) { - rect.x += (scale - rect.width) / 2; - rect.y += (scale - rect.height) / 2; - return rect; + rect.x += (scale - rect.width) / 2; + rect.y += (scale - rect.height) / 2; + return rect; } diff --git a/ViewController.h b/ViewController.h index c74c72a..13257dc 100644 --- a/ViewController.h +++ b/ViewController.h @@ -1,7 +1,5 @@ #pragma once -#include <utility> - #include "Color.h" #include "Command.h" #include "KeyboardCode.h" @@ -33,8 +31,8 @@ private: void update_quadtree_recursive(QuadTreeCollisionChecker * tree); private: - void draw_pathfinding_dot(const XY &, const Color &); - Rectangle center(Rectangle); + void draw_pathfinding_dot(const XY &, const Color &); + Rectangle center(Rectangle); private: Museum & museum; @@ -46,7 +44,7 @@ private: bool draw_quadtree = true; bool draw_path = true; bool draw_visited = true; - + private: float scale = 16; float artist_size = scale / 2; @@ -4,8 +4,3 @@ DPA: - state snapshots (memento) -ALGA: - -- artist-path collision behavior (toggleable) -- multiple fastest routes with dijkstra??? - |