implement weird dijkstra

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 };
diff --git a/XY.cpp b/XY.cpp
index e2aa075..eaebe1f 100644
--- a/XY.cpp
+++ b/XY.cpp
@@ -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);
+}
+
diff --git a/XY.h b/XY.h
index 839e19f..8809104 100644
--- a/XY.h
+++ b/XY.h
@@ -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