#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;
}