summaryrefslogtreecommitdiff
path: root/src/path_finder.cpp
diff options
context:
space:
mode:
authorPaweł Redman <pawel.redman@gmail.com>2017-11-07 11:01:20 +0100
committerPaweł Redman <pawel.redman@gmail.com>2017-11-07 11:01:20 +0100
commit68afd10851e01872c5c7774a2c1a09039d6e61d7 (patch)
tree382043bc62bad9751a3ef7778e799d78b4362bc3 /src/path_finder.cpp
parent6ab51bfb002af08da74a693f386c4154d2c4108a (diff)
Improve path finding.
The path finder will avoid paths that would intersect obstacles.
Diffstat (limited to 'src/path_finder.cpp')
-rw-r--r--src/path_finder.cpp29
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;