summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/common.hpp20
-rw-r--r--src/path_finder.cpp90
-rw-r--r--src/world.cpp100
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)
{