summaryrefslogtreecommitdiff
path: root/src/path_finder.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/path_finder.cpp')
-rw-r--r--src/path_finder.cpp71
1 files changed, 59 insertions, 12 deletions
diff --git a/src/path_finder.cpp b/src/path_finder.cpp
index 6d9540c..748a72f 100644
--- a/src/path_finder.cpp
+++ b/src/path_finder.cpp
@@ -3,12 +3,11 @@
namespace world {
static const v2f_t path_margin(5, 5);
-/*static const tile_index_t path_offsets[8] = {
+
+// The path finder will try to walk in the eight directions listed below.
+static const tile_index_t path_offsets[8] = {
{+1, 0}, {+1, +1}, {0, +1}, {-1, +1},
{-1, 0}, {-1, -1}, {0, -1}, {+1, -1}
-};*/
-static const tile_index_t path_offsets[4] = {
- {+1, 0}, {0, +1}, {-1, 0}, {0, -1}
};
path_finder_t::~path_finder_t()
@@ -76,6 +75,50 @@ void path_finder_t::eliminate_nodes(rectf_t bounds)
}
}
+path_node_t *path_finder_t::node_at(tile_index_t index)
+{
+ return nodes + index[1] * width + index[0];
+}
+
+bool path_finder_t::is_accessible(tile_index_t index)
+{
+ if (index[0] < 0 || index[1] < 0 ||
+ index[0] >= (coord_t)width || index[1] >= (coord_t)height)
+ return false;
+
+ return node_at(index)->accessible;
+}
+
+// Walking diagonally requires an additional accessibility test. The tables
+// below list when it's needed and which tile is to be tested. For example,
+// when walking north-west, the north and the west neighbors have to be tested
+// for accessibility.
+bool path_finder_t::diagonal_test(tile_index_t index, size_t i)
+{
+ static const bool do_test[8] = {
+ false, true, false, true, false, true, false, true
+ };
+ static const tile_index_t offsets[8][2] = {
+ {},
+ {{+1, 0}, {0, +1}},
+ {},
+ {{0, +1}, {-1, 0}},
+ {},
+ {{-1, 0}, {0, -1}},
+ {},
+ {{0, -1}, {+1, 0}}
+ };
+
+ if (!do_test[i])
+ return true;
+
+ for (size_t j = 0; j < 2; j++)
+ if (!is_accessible(index + offsets[i][j]))
+ return false;
+
+ return true;
+}
+
void path_finder_t::find_r(tile_index_t index, float dist, float limit)
{
path_node_t *node;
@@ -97,14 +140,16 @@ void path_finder_t::find_r(tile_index_t index, float dist, float limit)
shortest_dist = dist + dist_to_dst;
}
- for (size_t i = 0; i < 4; i++) {
+ 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)
+ if (!is_accessible(next))
+ continue;
+
+ if (!diagonal_test(index, i))
continue;
if (dist + v2f_t(offset).len() > limit)
@@ -127,19 +172,21 @@ bool path_finder_t::find(void)
return true;
start = tile_index_at(src) - base;
- nodes[start[1] * width + start[0]].accessible = false;
+ node_at(start)->accessible = false;
- for (size_t i = 0; i < 4; i++) {
+ 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) - tile_center;
- if (next[0] < 0 || next[1] < 0 ||
- next[0] >= (int64_t)width || next[1] >= (int64_t)height)
+ if (!is_accessible(next))
continue;
+ if (!diagonal_test(start, i))
+ continue;
+
+ offset = (src - v2f_t(base)) - v2f_t(next) - tile_center;
find_r(next, v2f_t(offset).len(), dist_simple * 3);
}