First working path finding.

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)