summaryrefslogtreecommitdiff
path: root/src/path_finder.cpp
diff options
context:
space:
mode:
authorPaweł Redman <pawel.redman@gmail.com>2017-10-24 10:29:10 +0200
committerPaweł Redman <pawel.redman@gmail.com>2017-10-24 13:13:45 +0200
commit28331efb18a9700e556879e51915cd0ecb51ae79 (patch)
tree89289301ad562d378cc1811854a39a835b53bbe5 /src/path_finder.cpp
parentee017fb5def1c4d372a664e5e64210ed0cd52174 (diff)
Node elimination basics.
Diffstat (limited to 'src/path_finder.cpp')
-rw-r--r--src/path_finder.cpp35
1 files changed, 30 insertions, 5 deletions
diff --git a/src/path_finder.cpp b/src/path_finder.cpp
index 8ca0ccc..ab8126a 100644
--- a/src/path_finder.cpp
+++ b/src/path_finder.cpp
@@ -28,7 +28,7 @@ void path_finder_t::setup_nodes(v2f_t src_, v2f_t dst_)
src_margin[1] = src + path_margin;
dst_margin[0] = dst - path_margin;
dst_margin[1] = dst + path_margin;
- bounds = src_margin + dst_margin;
+ bounds = src_margin | dst_margin;
base = tile_index_at(bounds[0]);
end = tile_index_at(bounds[1]);
@@ -41,7 +41,26 @@ void path_finder_t::setup_nodes(v2f_t src_, v2f_t dst_)
nodes[i].dist = INFINITY;
}
-void path_finder_t::find_r(tile_index_t index, float dist)
+void path_finder_t::eliminate_nodes(rectf_t bounds)
+{
+ rect_t<coord_t, 2> index_bounds;
+ tile_index_t index;
+
+ std::cout << "eliminate " << bounds << "\n";
+
+ index_bounds[0] = tile_index_t(bounds[0].floor()) - base;
+ index_bounds[1] = tile_index_t(bounds[1].ceil()) - base;
+
+ for (index[1] = index_bounds[0][1]; index[1] <= index_bounds[1][1]; index[1]++)
+ for (index[0] = index_bounds[0][0]; index[0] <= index_bounds[1][0]; index[0]++) {
+ path_node_t *node;
+
+ node = nodes + index[1] * width + index[0];
+ node->accessible = false;
+ }
+}
+
+void path_finder_t::find_r(tile_index_t index, float dist, float limit)
{
path_node_t *node;
float dist_to_dst;
@@ -72,7 +91,10 @@ void path_finder_t::find_r(tile_index_t index, float dist)
next[0] >= (int64_t)width || next[1] >= (int64_t)height)
continue;
- find_r(next, dist + v2f_t(offset).len());
+ if (dist + v2f_t(offset).len() > limit)
+ continue;
+
+ find_r(next, dist + v2f_t(offset).len(), limit);
}
path.pop_back();
@@ -81,8 +103,11 @@ void path_finder_t::find_r(tile_index_t index, float dist)
bool path_finder_t::find(void)
{
tile_index_t start;
+ float dist_simple;
+
+ dist_simple = (src - dst).len();
- if ((src - dst).len() < 1.0f)
+ if (dist_simple < 1.0f)
return true;
start = tile_index_at(src) - base;
@@ -99,7 +124,7 @@ bool path_finder_t::find(void)
next[0] >= (int64_t)width || next[1] >= (int64_t)height)
continue;
- find_r(next, v2f_t(offset).len());
+ find_r(next, v2f_t(offset).len(), dist_simple * 3);
}
return shortest_path.size() > 0;