summaryrefslogtreecommitdiff
path: root/src/path_finder.cpp
diff options
context:
space:
mode:
authorPaweł Redman <pawel.redman@gmail.com>2018-03-26 19:27:17 +0200
committerPaweł Redman <pawel.redman@gmail.com>2018-03-26 19:27:17 +0200
commitc9a0aff5a9333cf5e0ee55ba5c8551457a3ae13c (patch)
treeaf5175e56edcb50062555933eb9779a9e7c231a6 /src/path_finder.cpp
parent2f978ea5085678e98e391317cc50ac991cd726a8 (diff)
Diffstat (limited to 'src/path_finder.cpp')
-rw-r--r--src/path_finder.cpp64
1 files changed, 37 insertions, 27 deletions
diff --git a/src/path_finder.cpp b/src/path_finder.cpp
index 8a61cc6..04f4d57 100644
--- a/src/path_finder.cpp
+++ b/src/path_finder.cpp
@@ -136,10 +136,36 @@ bool path_finder_t::diagonal_test(tile_index_t index, size_t i)
return true;
}
+static const int visit_orders[4][8] = {
+ {0, 7, 1, 2, 6, 5, 3, 4}, // prefer +x
+ {2, 3, 1, 0, 4, 7, 5, 6}, // prefer +y
+ {4, 5, 3, 2, 6, 1, 7, 0}, // prefer -x
+ {6, 5, 7, 0, 4, 3, 1, 2} // prefer -y
+};
+
+static const int *visit_order(v2f_t delta)
+{
+ if (delta[1] > delta[0]) {
+ if (delta[1] > -delta[0])
+ return visit_orders[1];
+ else
+ return visit_orders[2];
+ } else {
+ if (delta[1] > -delta[0])
+ return visit_orders[0];
+ else
+ return visit_orders[3];
+ }
+
+ return visit_orders[0];
+}
+
void path_finder_t::find_r(tile_index_t index, float dist, float limit)
{
path_node_t *node;
+ v2f_t delta;
float dist_to_dst;
+ const int *order;
node = nodes + index[1] * width + index[0];
@@ -148,31 +174,37 @@ void path_finder_t::find_r(tile_index_t index, float dist, float limit)
if (node->dist <= dist)
return;
- path.push_back(index);
node->dist = dist;
+ path.push_back(index);
- dist_to_dst = (v2f_t(base + index) + tile_center - dst).len();
+ delta = dst - v2f_t(base + index) - tile_center;
+ dist_to_dst = delta.len();
if (dist_to_dst < 1.0f && dist + dist_to_dst < shortest_dist) {
shortest_path = path;
shortest_dist = dist + dist_to_dst;
+ return;
}
+ order = visit_order(delta);
+
for (size_t i = 0; i < 8; i++) {
tile_index_t offset, next;
- offset = path_offsets[i];
+ offset = path_offsets[order[i]];
next = index + offset;
if (!is_accessible(next))
continue;
- if (!diagonal_test(index, i))
+ if (!diagonal_test(index, order[i]))
continue;
if (dist + v2f_t(offset).len() > limit)
continue;
find_r(next, dist + v2f_t(offset).len(), limit);
+ if (shortest_path.size())
+ return;
}
path.pop_back();
@@ -181,31 +213,9 @@ void path_finder_t::find_r(tile_index_t index, float dist, float limit)
bool path_finder_t::find(void)
{
tile_index_t start;
- float dist_simple;
-
- dist_simple = (src - dst).len();
-
- if (dist_simple < 0.5f)
- return true;
start = tile_index_at(src) - base;
- node_at(start)->accessible = false;
-
- for (size_t i = 0; i < 8; i++) {
- tile_index_t next;
- v2f_t offset;
-
- next = start + path_offsets[i];
-
- 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);
- }
+ find_r(start, 0.0f, 100.0f);
return shortest_path.size() > 0;
}