From 886a97593c1da1351f978c3dc39d9c1ea2ab57d9 Mon Sep 17 00:00:00 2001 From: Paweł Redman Date: Sat, 21 Oct 2017 14:26:40 +0200 Subject: First working path finding. --- src/common.hpp | 9 +++++++-- src/game.cpp | 44 +++++++++++++++++++++++++++++++++++++++++++- src/path_finder.cpp | 30 +++++++++++++++++++++++++++++- src/render.cpp | 18 ++++++++++++++++++ src/world.cpp | 18 ++++++++++-------- 5 files changed, 107 insertions(+), 12 deletions(-) diff --git a/src/common.hpp b/src/common.hpp index bbf83cf..8f610a5 100644 --- a/src/common.hpp +++ b/src/common.hpp @@ -121,16 +121,19 @@ namespace world { class path_finder_t { public: - v2f_t src, dst; + v2f_t src, dst, tile_center; path_node_t *nodes; size_t width, height; tile_index_t base; - std::stack current_path, shortest_path; + + float shortest_dist; + std::deque path, shortest_path; ~path_finder_t(); void setup_nodes(v2f_t src_, v2f_t dst_); void find_r(tile_index_t index, float dist); void find(void); + bool export_path(std::list *list); }; } @@ -215,6 +218,8 @@ namespace render { void render(game::state_t *game); void render(animated_texture_t *anim, rectf_t bounds, bool mirror = false); void render(oriented_sprite_t *sprite, rectf_t bounds, float angle); + + void debug_path(std::list *path); }; } diff --git a/src/game.cpp b/src/game.cpp index ffee87d..2d9b67e 100644 --- a/src/game.cpp +++ b/src/game.cpp @@ -19,8 +19,9 @@ public: struct { bool moving; - std::list path; v2f_t dst; + + std::list path; } move; void place(world::world_t *world_, v2f_t x_) @@ -34,10 +35,47 @@ public: link(world); } + bool move_towards(v2f_t point, float *time) + { + bool partial; + v2f_t delta; + + delta = point - x; + + if (delta.len() >= *time) { + partial = true; + x += delta * *time / delta.len(); + *time = 0.0f; + } else { + partial = false; + x = point; + *time -= delta.len(); + } + + return partial; + } + void keep_moving(void) { + float time; + if (!move.moving) return; + + time = 0.15; + + while (time > 0.0f) { + if (!move.path.size()) { + move.moving = false; + break; + } + + if (!move_towards(*move.path.begin(), &time)) { + move.path.pop_front(); + } + } + + compute_bounds(); } bool start_moving(v2f_t dst_) @@ -68,6 +106,9 @@ public: &assets::human.legs_idle), render_bounds, angle); render->render(&assets::human.body_idle, render_bounds, angle); render->render(&assets::human.head_idle, render_bounds, angle); + + if (move.moving) + render->debug_path(&move.path); } }; @@ -89,6 +130,7 @@ void state_t::debug_click(v2f_t x) void state_t::tick(void) { + human.keep_moving(); } } //namespace game diff --git a/src/path_finder.cpp b/src/path_finder.cpp index 294f708..ab300dc 100644 --- a/src/path_finder.cpp +++ b/src/path_finder.cpp @@ -21,6 +21,9 @@ void path_finder_t::setup_nodes(v2f_t src_, v2f_t dst_) src = src_; dst = dst_; + tile_center = v2f_t(0.5, 0.5); + shortest_dist = INFINITY; + src_margin[0] = src - path_margin; src_margin[1] = src + path_margin; dst_margin[0] = dst - path_margin; @@ -41,6 +44,7 @@ void path_finder_t::setup_nodes(v2f_t src_, v2f_t dst_) void path_finder_t::find_r(tile_index_t index, float dist) { path_node_t *node; + float dist_to_dst; node = nodes + index[1] * width + index[0]; @@ -49,8 +53,15 @@ void path_finder_t::find_r(tile_index_t index, float dist) if (node->dist <= dist) return; + path.push_back(index); node->dist = dist; + dist_to_dst = (v2f_t(base + index) + tile_center - dst).len(); + if (dist_to_dst < 1.0f && dist + dist_to_dst < shortest_dist) { + shortest_path = path; + shortest_dist = dist + dist_to_dst; + } + for (size_t i = 0; i < 8; i++) { tile_index_t offset, next; @@ -63,6 +74,8 @@ void path_finder_t::find_r(tile_index_t index, float dist) find_r(next, dist + v2f_t(offset).len()); } + + path.pop_back(); } void path_finder_t::find(void) @@ -77,7 +90,7 @@ void path_finder_t::find(void) v2f_t offset; next = start + path_offsets[i]; - offset = src - v2f_t(base) - v2f_t(next); + offset = (src - v2f_t(base)) - v2f_t(next) - tile_center; if (next[0] < 0 || next[1] < 0 || next[0] >= (int64_t)width || next[1] >= (int64_t)height) @@ -87,4 +100,19 @@ void path_finder_t::find(void) } } +bool path_finder_t::export_path(std::list *list) +{ + if (!shortest_path.size()) + return false; + + list->clear(); + + for (tile_index_t &index : shortest_path) + list->push_back(v2f_t(index + base) + tile_center); + + list->push_back(dst); + + return true; +} + } // namespace world diff --git a/src/render.cpp b/src/render.cpp index 9e3adfa..87f4216 100644 --- a/src/render.cpp +++ b/src/render.cpp @@ -146,6 +146,24 @@ void state_t::render(oriented_sprite_t *sprite, rectf_t bounds, float angle) render(sprite->textures + index, bounds, mirror); } +void state_t::debug_path(std::list *path) +{ + bool first = true; + sf::Vertex line[2]; + + for (v2f_t &point : *path) { + line[1] = line[0]; + line[0] = sf::Vertex(point, sf::Color::Blue); + + if (first) { + first = false; + continue; + } + + window->draw(line, 2, sf::Lines); + } +} + animated_texture_t::~animated_texture_t(void) { delete[] frames; diff --git a/src/world.cpp b/src/world.cpp index 8d0b1fb..307374c 100644 --- a/src/world.cpp +++ b/src/world.cpp @@ -15,7 +15,7 @@ tile_index_t tile_index_at(v2f_t x) world_t::world_t(void) { - prng.seed(124); + prng.seed(125); perlin.generate(&prng, 32); } @@ -26,10 +26,9 @@ void world_t::generate_tile(tile_t *tile, tile_index_t x) waterlevel = perlin.get(x, 1000.0f) * 0.3f + perlin.get(x, 500.0f) * 0.1f; - height = perlin.get(x, 60.0f) * 0.6f + - perlin.get(x, 30.0f) * 0.25f + - perlin.get(x, 14.0f) * 0.1f + - perlin.get(x, 6.0f) * 0.05f; + height = perlin.get(x, 10.0f) * 0.6f + + perlin.get(x, 5.0f) * 0.25f + + perlin.get(x, 3.0f) * 0.2f; if (height < waterlevel - 0.2f) tile->type = -1; @@ -67,6 +66,7 @@ bool world_t::find_path(v2f_t src, v2f_t dst, rectf_t size, std::list *path) { path_finder_t finder; + bool rv; finder.setup_nodes(src, dst); @@ -80,6 +80,7 @@ bool world_t::find_path(v2f_t src, v2f_t dst, rectf_t size, } finder.find(); + rv = finder.export_path(path); debug.clear(); @@ -88,13 +89,14 @@ bool world_t::find_path(v2f_t src, v2f_t dst, rectf_t size, path_node_t *node = finder.nodes + y * finder.width + x; std::stringstream ss; - ss << finder.base + tile_index_t(x, y) << "\n"; - ss << node->dist; + ss << "LT " << tile_index_t(x, y) << "\n"; + ss << " T " << finder.base + tile_index_t(x, y) << "\n"; + ss << " d " << node->dist; debug.push_back((debug_t){finder.base + tile_index_t(x, y), ss.str()}); } - return false; + return rv; } sector_t *world_t::get_sector(sector_index_t index) -- cgit