From 68afd10851e01872c5c7774a2c1a09039d6e61d7 Mon Sep 17 00:00:00 2001 From: Paweł Redman Date: Tue, 7 Nov 2017 11:01:20 +0100 Subject: Improve path finding. The path finder will avoid paths that would intersect obstacles. --- src/path_finder.cpp | 29 +++++++++++++++++++++++------ 1 file changed, 23 insertions(+), 6 deletions(-) (limited to 'src/path_finder.cpp') 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 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; -- cgit