Improve path finding.

The path finder will avoid paths that would intersect obstacles.

1 files changed, 16 insertions, 4 deletions

diff --git a/src/world.cpp b/src/world.cpp
index ab3ef92..778e463 100644
--- a/src/world.cpp
+++ b/src/world.cpp
@@ -85,16 +85,27 @@ bool world_t::find_path(v2f_t src, v2f_t dst, cmodel_t *cmodel, entity_t *ignore
 {
 	path_finder_t finder;
 	rectf_t bounds;
+	v2f_t cmodel_dims;
+	bool found;
 
 	finder.setup_nodes(src, dst, cmodel->cflags);
 
+	cmodel_dims = cmodel->bounds.dims();
+
 	for (size_t y = 0; y < finder.height; y++)
 	for (size_t x = 0; x < finder.width; x++) {
-		path_node_t *node = finder.nodes + y * finder.width + x;
 		tile_index_t index;
+		rectf_t combined;
 
 		index = finder.base + tile_index_t(x, y);
-		node->accessible = get_tile(index)->type == TILE_DIRT;
+
+		if (get_tile(index)->type == TILE_DIRT)
+			continue;
+
+		combined[0] = v2f_t(index)  - cmodel_dims / 2;
+		combined[1] = v2f_t(index) + v2f_t(1.0f, 1.0f) + cmodel_dims / 2;
+
+		finder.eliminate_nodes(combined);
 	}
 
 	bounds = rectf_t(src, dst).norm();
@@ -103,8 +114,7 @@ bool world_t::find_path(v2f_t src, v2f_t dst, cmodel_t *cmodel, entity_t *ignore
 		if (ent != ignore)
 			finder.eliminate_nodes(ent->cmodel.bounds);
 
-	if (!finder.find())
-		return false;
+	found = finder.find();
 
 	debug.clear();
 
@@ -122,6 +132,8 @@ bool world_t::find_path(v2f_t src, v2f_t dst, cmodel_t *cmodel, entity_t *ignore
 		debug.push_back((debug_t){finder.base + tile_index_t(x, y), ss.str()});
 	}
 
+	if (!found)
+		return false;
 
 	finder.export_path(path);
 	return true;