Node elimination basics.

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;