summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorPaweł Redman <pawel.redman@gmail.com>2017-10-21 11:20:34 +0200
committerPaweł Redman <pawel.redman@gmail.com>2017-10-21 13:12:42 +0200
commit20b189455545db5688ed4f14d2966380137ee2db (patch)
tree7504e059147cfae54fa466b8a4c0073ecbbc582c /src
parent29d124b93125d7c9de762c45876f69df3acd549d (diff)
Start working on path finding.
Diffstat (limited to 'src')
-rw-r--r--src/common.hpp18
-rw-r--r--src/game.cpp41
-rw-r--r--src/interface.cpp7
-rw-r--r--src/math.hpp22
-rw-r--r--src/render.cpp11
-rw-r--r--src/world.cpp145
6 files changed, 225 insertions, 19 deletions
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<int64_t, 2> sector_index_t;
typedef vec_t<int64_t, 2> 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_t> 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<v2f_t> *path);
+
// FIXME: iterators instead of returning std::lists
std::list<sector_t*> get_sectors(rectf_t rect);
std::list<entity_t*> get_entities(rectf_t rect);
std::list<entity_t*> 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<world::tile_index_t*> path;
- world::tile_index_t dest;
+ std::list<v2f_t> 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<T, N> floor(void)
+ {
+ vec_t<T, N> 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 <typename U>
@@ -243,6 +258,11 @@ public:
return true;
}
+ T dim(size_t i) const
+ {
+ return v[1][i] - v[0][i];
+ }
+
friend rect_t<T, N> operator+(const rect_t<T, N> &a, const rect_t<T, N> &b)
{
rect_t r;
@@ -257,7 +277,7 @@ public:
friend std::ostream& operator<<(std::ostream& stream, rect_t<T, N> 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 <list>
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 <stack>
+#include <sstream>
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<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)
+{
+ 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;