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
80
81
82
83
84
85
86
87
88
89
90
|
#include "common.hpp"
namespace world {
static const v2f_t path_margin(5, 5);
static const tile_index_t path_offsets[8] = {
{+1, 0}, {+1, +1}, {0, +1}, {-1, +1},
{-1, 0}, {-1, -1}, {0, -1}, {+1, -1}
};
path_finder_t::~path_finder_t()
{
delete nodes;
}
void path_finder_t::setup_nodes(v2f_t src_, v2f_t dst_)
{
rectf_t src_margin, dst_margin, bounds;
tile_index_t end;
src = src_;
dst = dst_;
src_margin[0] = src - path_margin;
src_margin[1] = src + path_margin;
dst_margin[0] = dst - path_margin;
dst_margin[1] = dst + path_margin;
bounds = src_margin + dst_margin;
base = tile_index_at(bounds[0]);
end = tile_index_at(bounds[1]);
width = end[0] - base[0] + 1;
height = end[1] - base[1] + 1;
nodes = new path_node_t[width * height];
for (size_t i = 0; i < width * height; i++)
nodes[i].dist = INFINITY;
}
void path_finder_t::find_r(tile_index_t index, float dist)
{
path_node_t *node;
node = nodes + index[1] * width + index[0];
if (!node->accessible)
return;
if (node->dist <= dist)
return;
node->dist = dist;
for (size_t i = 0; i < 8; i++) {
tile_index_t offset, next;
offset = path_offsets[i];
next = index + offset;
if (next[0] < 0 || next[1] < 0 ||
next[0] >= (int64_t)width || next[1] >= (int64_t)height)
continue;
find_r(next, dist + v2f_t(offset).len());
}
}
void path_finder_t::find(void)
{
tile_index_t start;
start = tile_index_at(src) - base;
nodes[start[1] * width + start[0]].accessible = false;
for (size_t i = 0; i < 8; i++) {
tile_index_t next;
v2f_t offset;
next = start + path_offsets[i];
offset = src - v2f_t(base) - v2f_t(next);
if (next[0] < 0 || next[1] < 0 ||
next[0] >= (int64_t)width || next[1] >= (int64_t)height)
continue;
find_r(next, v2f_t(offset).len());
}
}
} // namespace world
|
