diff options
| -rw-r--r-- | src/common.hpp | 10 | ||||
| -rw-r--r-- | src/game.cpp | 18 | ||||
| -rw-r--r-- | src/math.hpp | 38 | ||||
| -rw-r--r-- | src/path_finder.cpp | 35 | ||||
| -rw-r--r-- | src/world.cpp | 32 |
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]); |