blob: ef4492a2c8198402fea6ed1ebde8a0cae7a5d11e (
plain)
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
61
62
63
64
65
66
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;
}
|