BreadthFirstPathfinder.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

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

	int steps = -1;
	while (trails.size() > 0) {
		steps++;
		trails = this->find_step(trails);
	}
	printf("BFS: %s (%d steps)\n", this->solution.empty() ? "no solution found" : "solution found", steps);
}

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