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
68
69
70
71
72
73
74
75
76
77
78
79
|
#include <algorithm>
#include "DijkstraPathfinder.h"
#include "Museum.h"
using namespace std;
const DijkstraPathfinder::Path & DijkstraPathfinder::get_path() {
return this->solution;
}
void DijkstraPathfinder::clear() {
Pathfinder::clear();
this->solution.clear();
this->map.clear();
}
void DijkstraPathfinder::find_between(const XY & start, const XY & end) {
this->clear();
this->end = end;
this->map_get(start).distance = 0;
this->dijkstra(start);
// no solution
if (!this->is_visited(end)) return;
XY pos = end;
while (pos != start) {
solution.push_front(pos);
pos = this->map[pos].parent;
}
}
DijkstraPathfinder::Node & DijkstraPathfinder::map_get(const XY & pos) {
if (!this->map.contains(pos))
this->map[pos] = Node();
return this->map[pos];
}
void DijkstraPathfinder::dijkstra(const XY & here) {
this->set_visited(here);
PathfindingContext & ctx = this->museum.pathfinding;
unsigned int dist_end = this->map_get(this->end).distance;
vector<pair<unsigned int, XY>> neighbors;
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;
Tile & neighbor_tile = this->museum.canvas.get_tile(neighbor);
unsigned int neighbor_cost = ctx.get_weight(neighbor_tile.data.type);
unsigned int dist_neighbor = this->map_get(here).distance + neighbor_cost;
if (dist_neighbor >= dist_end) continue;
Node & neighbor_node = this->map_get(neighbor);
if (dist_neighbor >= neighbor_node.distance) continue;
neighbor_node.parent = here;
neighbor_node.distance = dist_neighbor;
neighbors.push_back({ dist_neighbor, neighbor });
}
// sort by cost ascending
sort(neighbors.begin(), neighbors.end(), [] (auto & left, auto & right) {
return left.first < right.first;
});
for (pair<unsigned int, XY> & neighbor : neighbors) {
this->dijkstra(neighbor.second);
}
}
|