implement breadth-first search pathfinding

1 files changed, 67 insertions, 0 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;
+}
+