summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorPaweł Redman <pawel.redman@gmail.com>2017-10-21 14:26:40 +0200
committerPaweł Redman <pawel.redman@gmail.com>2017-10-21 14:26:40 +0200
commit886a97593c1da1351f978c3dc39d9c1ea2ab57d9 (patch)
tree4d8c5d456c8c78a7d7639b4cd608435a5f103f01 /src
parent1c637e1ca5c0b1cf8a91f37c999aa7379fa08a8f (diff)
First working path finding.
Diffstat (limited to 'src')
-rw-r--r--src/common.hpp9
-rw-r--r--src/game.cpp44
-rw-r--r--src/path_finder.cpp30
-rw-r--r--src/render.cpp18
-rw-r--r--src/world.cpp18
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<v2f_t> current_path, shortest_path;
+
+ float shortest_dist;
+ std::deque<tile_index_t> 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<v2f_t> *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<v2f_t> *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<v2f_t> path;
v2f_t dst;
+
+ std::list<v2f_t> 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<v2f_t> *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<v2f_t> *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<v2f_t> *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)