implement breadth-first search pathfinding

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