Start working on path finding.

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;