diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/common.hpp | 20 | ||||
| -rw-r--r-- | src/path_finder.cpp | 90 | ||||
| -rw-r--r-- | src/world.cpp | 100 |
3 files changed, 110 insertions, 100 deletions
diff --git a/src/common.hpp b/src/common.hpp index ced0b25..bbf83cf 100644 --- a/src/common.hpp +++ b/src/common.hpp @@ -5,6 +5,7 @@ #include <map> #include <list> #include <unordered_set> +#include <stack> #include <SFML/Graphics.hpp> #include "math.hpp" @@ -112,6 +113,25 @@ namespace world { virtual void render_to(render::state_t *render) = 0; }; + + typedef struct { + bool accessible; + float dist; + } path_node_t; + + class path_finder_t { + public: + v2f_t src, dst; + path_node_t *nodes; + size_t width, height; + tile_index_t base; + std::stack<v2f_t> current_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); + }; } namespace game { diff --git a/src/path_finder.cpp b/src/path_finder.cpp new file mode 100644 index 0000000..294f708 --- /dev/null +++ b/src/path_finder.cpp @@ -0,0 +1,90 @@ +#include "common.hpp" + +namespace world { + +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} +}; + +path_finder_t::~path_finder_t() +{ + delete nodes; +} + +void path_finder_t::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 path_finder_t::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 path_finder_t::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()); + } +} + +} // namespace world diff --git a/src/world.cpp b/src/world.cpp index 818c024..8d0b1fb 100644 --- a/src/world.cpp +++ b/src/world.cpp @@ -1,5 +1,4 @@ #include "common.hpp" -#include <stack> #include <sstream> namespace world { @@ -64,105 +63,6 @@ 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<v2f_t> 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<v2f_t> *path) { |