Improve path finding.

The path finder will avoid paths that would intersect obstacles.

1 files changed, 23 insertions, 6 deletions

diff --git a/src/path_finder.cpp b/src/path_finder.cpp
index aeded09..6d9540c 100644
--- a/src/path_finder.cpp
+++ b/src/path_finder.cpp
@@ -3,9 +3,12 @@
 namespace world {
 
 static const v2f_t path_margin(5, 5);
-static const tile_index_t path_offsets[8] = {
+/*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()
@@ -38,8 +41,10 @@ void path_finder_t::setup_nodes(v2f_t src_, v2f_t dst_, cflags_t cflags_)
 	height = end[1] - base[1] + 1;
 
 	nodes = new path_node_t[width * height];
-	for (size_t i = 0; i < width * height; i++)
+	for (size_t i = 0; i < width * height; i++) {
+		nodes[i].accessible = true;
 		nodes[i].dist = INFINITY;
+	}
 }
 
 void path_finder_t::eliminate_nodes(rectf_t bounds)
@@ -47,8 +52,20 @@ void path_finder_t::eliminate_nodes(rectf_t bounds)
 	rect_t<coord_t, 2> index_bounds;
 	tile_index_t index;
 
-	index_bounds[0] = tile_index_t(bounds[0].floor()) - base;
-	index_bounds[1] = tile_index_t(bounds[1].ceil()) - base;
+	bounds[0] -= tile_center;
+	bounds[1] -= tile_center;
+
+	index_bounds[0] = tile_index_t(bounds[0].ceil()) - base;
+	index_bounds[1] = tile_index_t(bounds[1].floor()) - base;
+
+	if (index_bounds[0][0] < 0)
+		index_bounds[0][0] = 0;
+	if (index_bounds[0][1] < 0)
+		index_bounds[0][1] = 0;
+	if (index_bounds[1][0] >= (coord_t)width)
+		index_bounds[1][0] = width - 1;
+	if (index_bounds[1][1] >= (coord_t)height)
+		index_bounds[1][1] = height - 1;
 
 	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]++) {
@@ -80,7 +97,7 @@ 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 < 8; i++) {
+	for (size_t i = 0; i < 4; i++) {
 		tile_index_t offset, next;
 
 		offset = path_offsets[i];
@@ -112,7 +129,7 @@ bool path_finder_t::find(void)
 	start = tile_index_at(src) - base;
 	nodes[start[1] * width + start[0]].accessible = false;
 
-	for (size_t i = 0; i < 8; i++) {
+	for (size_t i = 0; i < 4; i++) {
 		tile_index_t next;
 		v2f_t offset;