summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/common.hpp10
-rw-r--r--src/game.cpp18
-rw-r--r--src/math.hpp38
-rw-r--r--src/path_finder.cpp35
-rw-r--r--src/world.cpp32
5 files changed, 103 insertions, 30 deletions
diff --git a/src/common.hpp b/src/common.hpp
index 79c160a..bf2a300 100644
--- a/src/common.hpp
+++ b/src/common.hpp
@@ -45,8 +45,9 @@ namespace world {
char type;
};
- typedef vec_t<int64_t, 2> sector_index_t;
- typedef vec_t<int64_t, 2> tile_index_t;
+ typedef int64_t coord_t;
+ typedef vec_t<coord_t, 2> sector_index_t;
+ typedef vec_t<coord_t, 2> tile_index_t;
sector_index_t sector_index_at(v2f_t x);
tile_index_t tile_index_at(v2f_t x);
@@ -85,7 +86,7 @@ namespace world {
sector_t *get_sector(sector_index_t index);
tile_t *get_tile(tile_index_t index);
- bool find_path(v2f_t src, v2f_t dst, rectf_t size, std::list<v2f_t> *path);
+ bool find_path(v2f_t src, v2f_t dst, rectf_t size, entity_t *ignore, std::list<v2f_t> *path);
// FIXME: iterators instead of returning std::lists
std::list<sector_t*> get_sectors(rectf_t rect);
@@ -131,7 +132,8 @@ namespace world {
~path_finder_t();
void setup_nodes(v2f_t src_, v2f_t dst_);
- void find_r(tile_index_t index, float dist);
+ void eliminate_nodes(rectf_t bounds);
+ void find_r(tile_index_t index, float dist, float limit);
bool find(void);
void export_path(std::list<v2f_t> *list);
};
diff --git a/src/game.cpp b/src/game.cpp
index 2dab5c6..f4b5057 100644
--- a/src/game.cpp
+++ b/src/game.cpp
@@ -36,13 +36,6 @@ public:
link(world);
}
- bool move_towards(v2f_t point, float *time)
- {
- bool partial;
-
- return partial;
- }
-
void keep_moving(void)
{
float time;
@@ -89,7 +82,7 @@ public:
move.dst = dst_;
move.path.clear();
- if (world->find_path(x, move.dst, size, &move.path))
+ if (world->find_path(x, move.dst, size, this, &move.path))
move.moving = true;
else
move.moving = false;
@@ -112,7 +105,7 @@ public:
}
};
-static human_t human;
+static human_t human, human2;
void state_t::start(void)
{
@@ -121,6 +114,13 @@ void state_t::start(void)
human.render_size[0] = v2f_t(-0.5f, -1.0f);
human.render_size[1] = v2f_t(+0.5f, +0.5f);
human.place(&world, v2f_t(0.5f, 0.5f));
+
+ human2.size[0] = v2f_t(-0.4f, -0.4f);
+ human2.size[1] = v2f_t(+0.4f, +0.4f);
+ human2.render_size[0] = v2f_t(-0.5f, -1.0f);
+ human2.render_size[1] = v2f_t(+0.5f, +0.5f);
+ human2.place(&world, v2f_t(3.5f, 0.5f));
+
}
void state_t::debug_click(v2f_t x)
diff --git a/src/math.hpp b/src/math.hpp
index 55bf438..938241f 100644
--- a/src/math.hpp
+++ b/src/math.hpp
@@ -188,6 +188,16 @@ public:
return r;
}
+ vec_t<T, N> ceil(void)
+ {
+ vec_t<T, N> r;
+
+ for (size_t i = 0; i < N; i++)
+ r[i] = std::ceil(v[i]);
+
+ return r;
+ }
+
T len(void)
{
return std::sqrt(*this * *this);
@@ -255,21 +265,33 @@ public:
return v[i];
}
- bool intersects(const rect_t<T, N> &b) const
+ T dim(size_t i) const
{
- for (size_t i = 0; i < N; i++)
- if (v[1][i] < b[0][i] || v[0][i] > b[1][i])
- return false;
+ return v[1][i] - v[0][i];
+ }
- return true;
+ rect_t<T, N> norm(void) const
+ {
+ rect_t<T, N> r;
+
+ for (size_t i = 0; i < N; i++) {
+ r[0][i] = std::min(v[0][i], v[1][i]);
+ r[1][i] = std::max(v[0][i], v[1][i]);
+ }
+
+ return r;
}
- T dim(size_t i) const
+ friend bool operator&&(const rect_t<T, N> &a, const rect_t<T, N> &b)
{
- return v[1][i] - v[0][i];
+ for (size_t i = 0; i < N; i++)
+ if (a[1][i] < b[0][i] || a[0][i] > b[1][i])
+ return false;
+
+ return true;
}
- friend rect_t<T, N> operator+(const rect_t<T, N> &a, const rect_t<T, N> &b)
+ friend rect_t<T, N> operator|(const rect_t<T, N> &a, const rect_t<T, N> &b)
{
rect_t r;
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;
diff --git a/src/world.cpp b/src/world.cpp
index ad055c0..07d5638 100644
--- a/src/world.cpp
+++ b/src/world.cpp
@@ -68,10 +68,11 @@ void world_t::generate(sector_t *sector, sector_index_t index)
sector->empty = false;
}
-bool world_t::find_path(v2f_t src, v2f_t dst, rectf_t size,
+bool world_t::find_path(v2f_t src, v2f_t dst, rectf_t size, entity_t *ignore,
std::list<v2f_t> *path)
{
path_finder_t finder;
+ rectf_t bounds;
finder.setup_nodes(src, dst);
@@ -85,9 +86,32 @@ bool world_t::find_path(v2f_t src, v2f_t dst, rectf_t size,
get_tile(index)->type <= 3);
}
+ bounds = rectf_t(src, dst).norm();
+
+ for (entity_t *ent : get_entities(bounds))
+ if (ent != ignore)
+ finder.eliminate_nodes(ent->bounds);
+
if (!finder.find())
return false;
+ debug.clear();
+
+ 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;
+ std::stringstream ss;
+
+ ss << finder.base + tile_index_t(x, y) << "\n";
+ if (node->accessible)
+ ss << node->dist;
+ else
+ ss << "inaccessible";
+
+ debug.push_back((debug_t){finder.base + tile_index_t(x, y), ss.str()});
+ }
+
+
finder.export_path(path);
return true;
}
@@ -146,7 +170,7 @@ std::list<entity_t*> world_t::get_entities(rectf_t rect)
if (ent->cookie == cookie)
continue;
- if (!rect.intersects(ent->bounds))
+ if (!(rect && ent->bounds))
continue;
ent->cookie = cookie;
@@ -169,7 +193,7 @@ std::list<entity_t*> world_t::get_render_entities(rectf_t rect)
if (ent->cookie == cookie)
continue;
- if (!rect.intersects(ent->render_bounds))
+ if (!(rect && ent->render_bounds))
continue;
ent->cookie = cookie;
@@ -200,7 +224,7 @@ void entity_t::link(world_t *world)
float xlip, ylip;
size_t xsecs, ysecs;
- total_bounds = bounds + render_bounds;
+ total_bounds = bounds | render_bounds;
fx = floor(total_bounds[0][0]);
fy = floor(total_bounds[0][1]);
generated by cgit (git 2.34.1) at 2024-11-01 05:22:10 +0000