diff options
| -rw-r--r-- | .gitmodules | 11 | ||||
| -rw-r--r-- | BreadthFirstPathfinder.cpp | 26 | ||||
| -rw-r--r-- | BreadthFirstPathfinder.h | 8 | ||||
| -rw-r--r-- | CMakeLists.txt | 3 | ||||
| -rw-r--r-- | DijkstraPathfinder.cpp | 80 | ||||
| -rw-r--r-- | DijkstraPathfinder.h | 21 | ||||
| -rw-r--r-- | MuseumDeserializer.cpp | 2 | ||||
| -rw-r--r-- | PathfindingContext.cpp | 29 | ||||
| -rw-r--r-- | PathfindingContext.h | 9 | ||||
| -rw-r--r-- | XY.cpp | 4 | ||||
| -rw-r--r-- | XY.h | 6 | ||||
| -rw-r--r-- | docs/class-diag.puml | 6 | ||||
| -rw-r--r-- | input/test.txt | 25 | ||||
| m--------- | lib/SDL | 0 | ||||
| m--------- | lib/cpr | 0 | ||||
| m--------- | lib/pugixml | 0 |
16 files changed, 183 insertions, 47 deletions
diff --git a/.gitmodules b/.gitmodules deleted file mode 100644 index de46813..0000000 --- a/.gitmodules +++ /dev/null @@ -1,11 +0,0 @@ -[submodule "lib/SDL"] - path = lib/SDL - url = https://github.com/libsdl-org/SDL - shallow = true -[submodule "lib/cpr"] - path = lib/cpr - url = https://github.com/libcpr/cpr - shallow = true -[submodule "lib/pugixml"] - path = lib/pugixml - url = https://github.com/zeux/pugixml diff --git a/BreadthFirstPathfinder.cpp b/BreadthFirstPathfinder.cpp index ef4492a..c204387 100644 --- a/BreadthFirstPathfinder.cpp +++ b/BreadthFirstPathfinder.cpp @@ -1,6 +1,5 @@ #include "BreadthFirstPathfinder.h" #include "Museum.h" -#include "NullTileBehavior.h" using namespace std; @@ -26,6 +25,7 @@ void BreadthFirstPathfinder::find_between(const XY & start, const XY & end) { vector<BreadthFirstPathfinder::Path> BreadthFirstPathfinder::find_step(const vector<Path> & to_visit) { vector<Path> next_step = {}; + PathfindingContext & ctx = this->museum.pathfinding; for (Path trail : to_visit) { const XY & here = trail.front(); @@ -34,30 +34,20 @@ vector<BreadthFirstPathfinder::Path> BreadthFirstPathfinder::find_step(const vec return {}; } - Tile & tile = this->museum.canvas.get_tile(here); - const XY offsets[] = { + vector<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); + for (const XY & offset : offsets) { + const XY neighbor = here + offset; + if (ctx.empty_point(neighbor)) continue; + if (this->is_visited(neighbor)) continue; + this->set_visited(neighbor); Path trail_copy = trail; - trail_copy.push_front(here + offset); + trail_copy.push_front(neighbor); next_step.push_back(trail_copy); } } diff --git a/BreadthFirstPathfinder.h b/BreadthFirstPathfinder.h index ba05f70..0c73c69 100644 --- a/BreadthFirstPathfinder.h +++ b/BreadthFirstPathfinder.h @@ -1,9 +1,9 @@ #pragma once -#include "Pathfinder.h" - #include <vector> +#include "Pathfinder.h" + class BreadthFirstPathfinder : public Pathfinder { using Pathfinder::Pathfinder; @@ -12,11 +12,11 @@ public: virtual const Path & get_path(); private: - std::vector<Path> find_step(const std::vector<Path> &); 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 e89069e..710b756 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -8,9 +8,6 @@ set(CMAKE_BUILD_TYPE Debug) find_package(SDL3 REQUIRED) find_package(cpr REQUIRED) find_package(pugixml REQUIRED) -# add_subdirectory(lib/SDL) -# add_subdirectory(lib/cpr) -# add_subdirectory(lib/pugixml) project(main C CXX) diff --git a/DijkstraPathfinder.cpp b/DijkstraPathfinder.cpp index 1603094..95291b3 100644 --- a/DijkstraPathfinder.cpp +++ b/DijkstraPathfinder.cpp @@ -1,3 +1,83 @@ +#include <algorithm> + #include "DijkstraPathfinder.h" +#include "Museum.h" + +using namespace std; + +const DijkstraPathfinder::Path & DijkstraPathfinder::get_path() { + return this->solution; +} + +void DijkstraPathfinder::clear() { + Pathfinder::clear(); + this->solution.clear(); + this->map.clear(); +} + +void DijkstraPathfinder::find_between(const XY & start, const XY & end) { + this->clear(); + this->end = end; + + this->explore(start); + + // no solution + if (!this->is_visited(end)) return; + + XY pos = end; + while (pos != start) { + solution.push_front(pos); + pos = this->map[pos].parent; + } +} + +DijkstraPathfinder::Node & DijkstraPathfinder::map_get(const XY & pos) { + if (!this->map.contains(pos)) + this->map[pos] = Node(); + return this->map[pos]; +} + +void DijkstraPathfinder::explore(const XY & here, unsigned int cost) { + if (this->is_visited(here)) return; + + PathfindingContext & ctx = this->museum.pathfinding; + unsigned int end_cost = this->map_get(this->end).cost; + + vector<pair<unsigned int, XY>> neighbors; + vector<XY> offsets = { + { 0, 1 }, + { 1, 0 }, + { 0, -1 }, + { -1, 0 }, + }; + for (const XY & offset : offsets) { + const XY neighbor = here + offset; + if (ctx.empty_point(neighbor)) continue; + + Tile & neighbor_tile = this->museum.canvas.get_tile(neighbor); + unsigned int neighbor_cost = ctx.get_weight(neighbor_tile.data.type); + unsigned int step_cost = cost + neighbor_cost; + + if (step_cost > end_cost) continue; + + neighbors.push_back({ step_cost, neighbor }); + + Node & neighbor_node = this->map_get(neighbor); + if (step_cost < neighbor_node.cost) { + neighbor_node.parent = here; + neighbor_node.cost = step_cost; + } + } + + this->set_visited(here); + + // sort by cost ascending + sort(neighbors.begin(), neighbors.end(), [] (auto & left, auto & right) { + return left.first < right.first; + }); + for (pair<unsigned int, XY> & neighbor : neighbors) { + this->explore(neighbor.second, neighbor.first); + } +} diff --git a/DijkstraPathfinder.h b/DijkstraPathfinder.h index af475dd..d02d9cb 100644 --- a/DijkstraPathfinder.h +++ b/DijkstraPathfinder.h @@ -1,9 +1,30 @@ #pragma once +#include <unordered_map> + #include "Pathfinder.h" class DijkstraPathfinder : public Pathfinder { using Pathfinder::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 { + XY parent; + unsigned int cost = -1; + }; + Node & map_get(const XY &); + std::unordered_map<XY, Node> map; + + void explore(const XY &, unsigned int cost = 0); }; diff --git a/MuseumDeserializer.cpp b/MuseumDeserializer.cpp index 19fc1a6..4f53887 100644 --- a/MuseumDeserializer.cpp +++ b/MuseumDeserializer.cpp @@ -18,6 +18,6 @@ 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.pathfinding.weights.register_weight(type, weight); + this->museum.pathfinding.register_weight(type, weight); } diff --git a/PathfindingContext.cpp b/PathfindingContext.cpp index bcc9f37..df2f65b 100644 --- a/PathfindingContext.cpp +++ b/PathfindingContext.cpp @@ -10,7 +10,7 @@ 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 DijkstraPathfinder(m))); this->solvers.push_back(unique_ptr<Pathfinder>(new BreadthFirstPathfinder(m))); } @@ -23,38 +23,38 @@ Pathfinder & PathfindingContext::get_solver() { } void PathfindingContext::set_start(const XY & point) { - if (!this->valid_point(point)) return; + if (this->empty_point(point)) return; this->start_point = point; this->update(); } void PathfindingContext::set_end(const XY & point) { - if (!this->valid_point(point)) return; + if (this->empty_point(point)) return; this->end_point = point; this->update(); } -bool PathfindingContext::valid_point(const XY & point) { +bool PathfindingContext::empty_point(const XY & point) { try { // check if square is empty (has null behavior) Tile & tile = this->museum.canvas.get_tile(point); TileBehavior * behavior = tile.behavior.get(); - if (dynamic_cast<NullTileBehavior *>(behavior) != nullptr) return false; + if (dynamic_cast<NullTileBehavior *>(behavior) != nullptr) return true; } catch (...) { // get_tile throws an exception if the point is outside the canvas bounds - return false; + return true; } - return true; + return false; } void PathfindingContext::update() { bool valid = true; - if (!this->valid_point(this->start_point)) { + if (this->empty_point(this->start_point)) { this->start_point = { -1, -1 }; valid = false; } - if (!this->valid_point(this->end_point)) { + if (this->empty_point(this->end_point)) { this->end_point = { -1, -1 }; valid = false; } @@ -65,3 +65,14 @@ void PathfindingContext::update() { solver.find_between(this->start_point, this->end_point); } +void PathfindingContext::register_weight(const string & type, unsigned int weight) { + this->weight_map[type] = weight; +} + +unsigned int PathfindingContext::get_weight(const string & type) { + if (this->weight_map.contains(type)) + return this->weight_map[type]; + + return 0; +} + diff --git a/PathfindingContext.h b/PathfindingContext.h index 7c7f173..bb6fc23 100644 --- a/PathfindingContext.h +++ b/PathfindingContext.h @@ -1,6 +1,7 @@ #pragma once #include <memory> +#include <unordered_map> #include <vector> #include "XY.h" @@ -17,10 +18,16 @@ public: const XY & get_start() { return this->start_point; } void set_end(const XY & point); const XY & get_end() { return this->end_point; } - bool valid_point(const XY & point); + 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); +private: + std::unordered_map<std::string, unsigned int> weight_map; + private: XY start_point = { -1, -1 }; XY end_point = { -1, -1 }; @@ -43,3 +43,7 @@ bool XY::operator != (const XY& rhs) const { return !(*this == rhs); } +size_t std::hash<XY>::operator () (const XY & instance) const { + return instance.x | (instance.y << 16); +} + @@ -1,5 +1,7 @@ #pragma once +#include <functional> + struct XY { int x = 0; int y = 0; @@ -13,3 +15,7 @@ struct XY { bool operator != (const XY& other) const; }; +template<> struct std::hash<XY> { + size_t operator () (const XY &) const; +}; + diff --git a/docs/class-diag.puml b/docs/class-diag.puml index 32b7018..bf19cf3 100644 --- a/docs/class-diag.puml +++ b/docs/class-diag.puml @@ -154,6 +154,10 @@ rectangle Group_Pathfinding as "Pathfinding" <<group>> { + valid_point(const XY &) : bool + update() -- + + register_weight(type : const string &, weight : unsigned int) + + get_weight(type : const string &) : unsigned int + - weight_map : map<string, unsigned int> + -- + get_solver() : Pathfinder & + cycle_solver() -- @@ -185,6 +189,8 @@ rectangle Group_Pathfinding as "Pathfinding" <<group>> { # clear() } class DijkstraPathfinder { + + find_between(const XY &, const XY &) + + get_path() : const forward_list<XY> & } Pathfinder <|-- BreadthFirstPathfinder diff --git a/input/test.txt b/input/test.txt new file mode 100644 index 0000000..744a62a --- /dev/null +++ b/input/test.txt @@ -0,0 +1,25 @@ +rows=18,cols=32 +letter,rgb,weight +Y,[255,255,0],1 +B,[0,0,255],4 +R,[255,0,0],10 +G,[195,195,195],2 + +________________________________ +__RRRRRR______________________R_ +__RRRRRBBBBBBBBBBBBBBBBBB_____R_ +__RRRRRBBBBBBBGGBBBBBBBBB_____R_ +__RRRRRR______GG______________R_ +__RRRRRR______GG______________R_ +______________GG______________R_ +_________Y____GG______________R_ +_________Y____GG______________R_ +_________Y____GG______________R_ +_________Y____GG______________R_ +_________Y____GG______________R_ +__BBBBBBBBBBBBBBBBBBBBBB______R_ +_________Y____GG______________R_ +_________Y____GG______________R_ +______________GG______________R_ +________________________________ +________________________________ diff --git a/lib/SDL b/lib/SDL deleted file mode 160000 -Subproject e9efcfb428c6cf4ee49b249fb099981445685e0 diff --git a/lib/cpr b/lib/cpr deleted file mode 160000 -Subproject 99f044e386115194485ce77e326c31e9bd80bb0 diff --git a/lib/pugixml b/lib/pugixml deleted file mode 160000 -Subproject 3b17184379fcaaeb7f1fbe08018b7fedf2640b3 |