From 20b189455545db5688ed4f14d2966380137ee2db Mon Sep 17 00:00:00 2001 From: Paweł Redman Date: Sat, 21 Oct 2017 11:20:34 +0200 Subject: Start working on path finding. --- assets/LiberationMono-Regular.ttf | Bin 0 -> 313408 bytes src/common.hpp | 18 ++++- src/game.cpp | 41 ++++++++--- src/interface.cpp | 7 +- src/math.hpp | 22 +++++- src/render.cpp | 11 +++ src/world.cpp | 145 +++++++++++++++++++++++++++++++++++++- 7 files changed, 225 insertions(+), 19 deletions(-) create mode 100644 assets/LiberationMono-Regular.ttf diff --git a/assets/LiberationMono-Regular.ttf b/assets/LiberationMono-Regular.ttf new file mode 100644 index 0000000..1a39bc7 Binary files /dev/null and b/assets/LiberationMono-Regular.ttf differ diff --git a/src/common.hpp b/src/common.hpp index e135d56..ced0b25 100644 --- a/src/common.hpp +++ b/src/common.hpp @@ -47,8 +47,10 @@ namespace world { typedef vec_t sector_index_t; typedef vec_t tile_index_t; + sector_index_t sector_index_at(v2f_t x); + tile_index_t tile_index_at(v2f_t x); + class entity_t; - class sector_iterator_t; class sector_t { public: @@ -69,18 +71,26 @@ namespace world { void generate_tile(tile_t *tile, tile_index_t index); void generate(sector_t *sector, sector_index_t index); + protected: + friend render::state_t; + typedef struct { + v2f_t x; + std::string text; + } debug_t; + std::list debug; + public: world_t(void); 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 *path); + // FIXME: iterators instead of returning std::lists std::list get_sectors(rectf_t rect); std::list get_entities(rectf_t rect); std::list get_render_entities(rectf_t rect); - void render(sf::RenderWindow *window); - void debug_point(sf::Vector2f point); }; @@ -113,6 +123,8 @@ namespace game { void start(void); void tick(void); + + void debug_click(v2f_t x); }; } diff --git a/src/game.cpp b/src/game.cpp index d805c83..ffee87d 100644 --- a/src/game.cpp +++ b/src/game.cpp @@ -4,8 +4,9 @@ namespace game { class unit_t : public world::entity_t { world::world_t *world; + v2f_t x; - void compute_bounds(v2f_t x) + void compute_bounds() { bounds[0] = x + size[0]; bounds[1] = x + size[1]; @@ -17,19 +18,19 @@ public: rectf_t size, render_size; struct { - world::tile_index_t pos; - bool moving; - std::list path; - world::tile_index_t dest; + std::list path; + v2f_t dst; } move; - void place(world::world_t *world, world::tile_index_t pos) + void place(world::world_t *world_, v2f_t x_) { - move.pos = pos; + world = world_; + x = x_; move.moving = false; + unlink(); - compute_bounds((v2f_t)pos + v2f_t(0.5f, 0.5f)); + compute_bounds(); link(world); } @@ -39,9 +40,22 @@ public: return; } - bool start_moving(world::tile_index_t dest) + bool start_moving(v2f_t dst_) { - return false; + if (!world) { + printf("unit_t::start_moving: entity is not linked\n"); + return false; + } + + move.dst = dst_; + move.path.clear(); + + if (world->find_path(x, move.dst, size, &move.path)) + move.moving = true; + else + move.moving = false; + + return move.moving; } }; @@ -65,7 +79,12 @@ void state_t::start(void) human.size[1] = v2f_t(+0.4f, +0.4f); human.render_size[0] = v2f_t(-0.5f, -1.0f); human.render_size[1] = v2f_t(+0.5f, +0.5f); - human.place(&world, world::tile_index_t(0, 0)); + human.place(&world, v2f_t(0.5f, 0.5f)); +} + +void state_t::debug_click(v2f_t x) +{ + human.start_moving(x); } void state_t::tick(void) diff --git a/src/interface.cpp b/src/interface.cpp index 17c1727..0650889 100644 --- a/src/interface.cpp +++ b/src/interface.cpp @@ -48,7 +48,12 @@ void state_t::tick(void) return; case sf::Event::MouseButtonPressed: - if (event.mouseButton.button == 1) { + if (event.mouseButton.button == 0) { + v2f_t point = window->mapPixelToCoords( + sf::Vector2i(event.mouseButton.x, + event.mouseButton.y)); + game->debug_click(point); + } else if (event.mouseButton.button == 1) { camera.dragging = true; camera.drag_ref = window->mapPixelToCoords( sf::Vector2i(event.mouseButton.x, diff --git a/src/math.hpp b/src/math.hpp index c07b7d0..f3b049b 100644 --- a/src/math.hpp +++ b/src/math.hpp @@ -178,6 +178,21 @@ public: return v; } + vec_t floor(void) + { + vec_t r; + + for (size_t i = 0; i < N; i++) + r[i] = std::floor(v[i]); + + return r; + } + + T len(void) + { + return std::sqrt(*this * *this); + } + // Compatibility with SFML template @@ -243,6 +258,11 @@ public: return true; } + T dim(size_t i) const + { + return v[1][i] - v[0][i]; + } + friend rect_t operator+(const rect_t &a, const rect_t &b) { rect_t r; @@ -257,7 +277,7 @@ public: friend std::ostream& operator<<(std::ostream& stream, rect_t r) { - stream << "(" << r[0] << ", " << r[1] << ")"; + stream << "(" << r[0] << " x " << r[1] << ")"; return stream; } }; diff --git a/src/render.cpp b/src/render.cpp index 66eeba8..9e3adfa 100644 --- a/src/render.cpp +++ b/src/render.cpp @@ -2,6 +2,7 @@ #include static sf::RectangleShape wot_rect; +static sf::Font font; static void draw_tile(sf::RenderWindow *window, v2f_t x, world::tile_t *tile) { @@ -53,6 +54,8 @@ namespace render { state_t::state_t(sf::RenderWindow *window_) { window = window_; + + font.loadFromFile("assets/LiberationMono-Regular.ttf"); } void state_t::begin_frame(double time_) @@ -95,6 +98,14 @@ void state_t::render(game::state_t *game) for (world::entity_t *ent : ents) ent->render_to(this); + + for (world::world_t::debug_t &debug : game->world.debug) { + sf::Text text(debug.text, font, 20); + text.setPosition(debug.x); + text.setScale(0.006, 0.006); + text.setColor(sf::Color::Red); + window->draw(text); + } } void state_t::render(animated_texture_t *anim, rectf_t bounds, bool mirror){ diff --git a/src/world.cpp b/src/world.cpp index d2fc2bb..818c024 100644 --- a/src/world.cpp +++ b/src/world.cpp @@ -1,11 +1,17 @@ #include "common.hpp" +#include +#include namespace world { sector_index_t sector_index_at(v2f_t x) { - return sector_index_t(floor(x[0] / SECTOR_SIZE), - floor(x[1] / SECTOR_SIZE)); + return sector_index_t((x / SECTOR_SIZE).floor()); +} + +tile_index_t tile_index_at(v2f_t x) +{ + return sector_index_t(x.floor()); } world_t::world_t(void) @@ -45,7 +51,7 @@ void world_t::generate(sector_t *sector, sector_index_t index) sector->index = index; sector->bounds.v[0] = (v2f_t)index * SECTOR_SIZE; - sector->bounds.v[1].broadcast(SECTOR_SIZE); + sector->bounds.v[1] = sector->bounds.v[0] + v2f_t(SECTOR_SIZE, SECTOR_SIZE); std::cout << "generating " << index << "\n"; @@ -58,6 +64,139 @@ void world_t::generate(sector_t *sector, sector_index_t index) sector->empty = false; } +typedef struct { + bool accessible; + float dist; +} path_node_t; + +static const v2f_t path_margin(5, 5); +static const tile_index_t path_offsets[8] = { + {+1, 0}, {+1, +1}, {0, +1}, {-1, +1}, + {-1, 0}, {-1, -1}, {0, -1}, {+1, -1} +}; + +class path_finder_t { +public: + v2f_t src, dst; + path_node_t *nodes; + size_t width, height; + tile_index_t base; + std::stack current_path, shortest_path; + + ~path_finder_t() + { + delete nodes; + } + + void setup_nodes(v2f_t src_, v2f_t dst_) + { + rectf_t src_margin, dst_margin, bounds; + tile_index_t end; + + src = src_; + dst = dst_; + + src_margin[0] = src - path_margin; + src_margin[1] = src + path_margin; + dst_margin[0] = dst - path_margin; + dst_margin[1] = dst + path_margin; + bounds = src_margin + dst_margin; + + base = tile_index_at(bounds[0]); + end = tile_index_at(bounds[1]); + + width = end[0] - base[0] + 1; + height = end[1] - base[1] + 1; + + nodes = new path_node_t[width * height]; + for (size_t i = 0; i < width * height; i++) + nodes[i].dist = INFINITY; + } + + void find_r(tile_index_t index, float dist) + { + path_node_t *node; + + node = nodes + index[1] * width + index[0]; + + if (!node->accessible) + return; + if (node->dist <= dist) + return; + + node->dist = dist; + + for (size_t i = 0; i < 8; i++) { + tile_index_t offset, next; + + offset = path_offsets[i]; + next = index + offset; + + if (next[0] < 0 || next[1] < 0 || + next[0] >= (int64_t)width || next[1] >= (int64_t)height) + continue; + + find_r(next, dist + v2f_t(offset).len()); + } + } + + void find(void) + { + tile_index_t start; + + start = tile_index_at(src) - base; + nodes[start[1] * width + start[0]].accessible = false; + + for (size_t i = 0; i < 8; i++) { + tile_index_t next; + v2f_t offset; + + next = start + path_offsets[i]; + offset = src - v2f_t(base) - v2f_t(next); + + if (next[0] < 0 || next[1] < 0 || + next[0] >= (int64_t)width || next[1] >= (int64_t)height) + continue; + + find_r(next, v2f_t(offset).len()); + } + } +}; + +bool world_t::find_path(v2f_t src, v2f_t dst, rectf_t size, + std::list *path) +{ + path_finder_t finder; + + finder.setup_nodes(src, dst); + + 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; + tile_index_t index; + + index = finder.base + tile_index_t(x, y); + node->accessible = (get_tile(index)->type >= 1); + } + + finder.find(); + + 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"; + ss << node->dist; + + debug.push_back((debug_t){finder.base + tile_index_t(x, y), ss.str()}); + } + + return false; +} + sector_t *world_t::get_sector(sector_index_t index) { sector_t *sector; -- cgit