#include "BreadthFirstPathfinder.h"
#include "Museum.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 = {};
	PathfindingContext & ctx = this->museum.pathfinding;

	for (Path trail : to_visit) {
		const XY & here = trail.front();
		if (here == this->end) {
			this->solution = trail;
			return {};
		}

		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;
			if (this->is_visited(neighbor)) continue;
			this->set_visited(neighbor);

			Path trail_copy = trail;
			trail_copy.push_front(neighbor);
			next_step.push_back(trail_copy);
		}
	}

	return next_step;
}