Node elimination basics.

5 files changed, 103 insertions, 30 deletions

diff --git a/src/common.hpp b/src/common.hpp
index 79c160a..bf2a300 100644
--- a/src/common.hpp
+++ b/src/common.hpp
@@ -45,8 +45,9 @@ namespace world {
 		char type;
 	};
 
-	typedef vec_t<int64_t, 2> sector_index_t;
-	typedef vec_t<int64_t, 2> tile_index_t;
+	typedef int64_t coord_t;
+	typedef vec_t<coord_t, 2> sector_index_t;
+	typedef vec_t<coord_t, 2> tile_index_t;
 
 	sector_index_t sector_index_at(v2f_t x);
 	tile_index_t tile_index_at(v2f_t x);
@@ -85,7 +86,7 @@ namespace world {
 		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);
+		bool find_path(v2f_t src, v2f_t dst, rectf_t size, entity_t *ignore, std::list<v2f_t> *path);
 
 		// FIXME: iterators instead of returning std::lists
 		std::list<sector_t*> get_sectors(rectf_t rect);
@@ -131,7 +132,8 @@ namespace world {
 
 		~path_finder_t();
 		void setup_nodes(v2f_t src_, v2f_t dst_);
-		void find_r(tile_index_t index, float dist);
+		void eliminate_nodes(rectf_t bounds);
+		void find_r(tile_index_t index, float dist, float limit);
 		bool find(void);
 		void export_path(std::list<v2f_t> *list);
 	};
diff --git a/src/game.cpp b/src/game.cpp
index 2dab5c6..f4b5057 100644
--- a/src/game.cpp
+++ b/src/game.cpp
@@ -36,13 +36,6 @@ public:
 		link(world);
 	}
 
-	bool move_towards(v2f_t point, float *time)
-	{
-		bool partial;
-
-		return partial;
-	}
-
 	void keep_moving(void)
 	{
 		float time;
@@ -89,7 +82,7 @@ public:
 		move.dst = dst_;
 		move.path.clear();
 
-		if (world->find_path(x, move.dst, size, &move.path))
+		if (world->find_path(x, move.dst, size, this, &move.path))
 			move.moving = true;
 		else
 			move.moving = false;
@@ -112,7 +105,7 @@ public:
 	}
 };
 
-static human_t human;
+static human_t human, human2;
 
 void state_t::start(void)
 {
@@ -121,6 +114,13 @@ void state_t::start(void)
 	human.render_size[0] = v2f_t(-0.5f, -1.0f);
 	human.render_size[1] = v2f_t(+0.5f, +0.5f);
 	human.place(&world, v2f_t(0.5f, 0.5f));
+
+	human2.size[0] = v2f_t(-0.4f, -0.4f);
+	human2.size[1] = v2f_t(+0.4f, +0.4f);
+	human2.render_size[0] = v2f_t(-0.5f, -1.0f);
+	human2.render_size[1] = v2f_t(+0.5f, +0.5f);
+	human2.place(&world, v2f_t(3.5f, 0.5f));
+
 }
 
 void state_t::debug_click(v2f_t x)
diff --git a/src/math.hpp b/src/math.hpp
index 55bf438..938241f 100644
--- a/src/math.hpp
+++ b/src/math.hpp
@@ -188,6 +188,16 @@ public:
 		return r;
 	}
 
+	vec_t<T, N> ceil(void)
+	{
+		vec_t<T, N> r;
+
+		for (size_t i = 0; i < N; i++)
+			r[i] = std::ceil(v[i]);
+
+		return r;
+	}
+
 	T len(void)
 	{
 		return std::sqrt(*this * *this);
@@ -255,21 +265,33 @@ public:
 		return v[i];
 	}
 
-	bool intersects(const rect_t<T, N> &b) const
+	T dim(size_t i) const
 	{
-		for (size_t i = 0; i < N; i++)
-			if (v[1][i] < b[0][i] || v[0][i] > b[1][i])
-				return false;
+		return v[1][i] - v[0][i];
+	}
 
-		return true;
+	rect_t<T, N> norm(void) const
+	{
+		rect_t<T, N> r;
+
+		for (size_t i = 0; i < N; i++) {
+			r[0][i] = std::min(v[0][i], v[1][i]);
+			r[1][i] = std::max(v[0][i], v[1][i]);
+		}
+
+		return r;
 	}
 
-	T dim(size_t i) const
+	friend bool operator&&(const rect_t<T, N> &a, const rect_t<T, N> &b)
 	{
-		return v[1][i] - v[0][i];
+		for (size_t i = 0; i < N; i++)
+			if (a[1][i] < b[0][i] || a[0][i] > b[1][i])
+				return false;
+
+		return true;
 	}
 
-	friend rect_t<T, N> operator+(const rect_t<T, N> &a, const rect_t<T, N> &b)
+	friend rect_t<T, N> operator|(const rect_t<T, N> &a, const rect_t<T, N> &b)
 	{
 		rect_t r;
 
diff --git a/src/path_finder.cpp b/src/path_finder.cpp
index 8ca0ccc..ab8126a 100644
--- a/src/path_finder.cpp
+++ b/src/path_finder.cpp
@@ -28,7 +28,7 @@ void path_finder_t::setup_nodes(v2f_t src_, v2f_t dst_)
 	src_margin[1] = src + path_margin;
 	dst_margin[0] = dst - path_margin;
 	dst_margin[1] = dst + path_margin;
-	bounds = src_margin + dst_margin;
+	bounds = src_margin | dst_margin;
 
 	base = tile_index_at(bounds[0]);
 	end = tile_index_at(bounds[1]);
@@ -41,7 +41,26 @@ void path_finder_t::setup_nodes(v2f_t src_, v2f_t dst_)
 		nodes[i].dist = INFINITY;
 }
 
-void path_finder_t::find_r(tile_index_t index, float dist)
+void path_finder_t::eliminate_nodes(rectf_t bounds)
+{
+	rect_t<coord_t, 2> index_bounds;
+	tile_index_t index;
+
+	std::cout << "eliminate " << bounds << "\n";
+
+	index_bounds[0] = tile_index_t(bounds[0].floor()) - base;
+	index_bounds[1] = tile_index_t(bounds[1].ceil()) - base;
+
+	for (index[1] = index_bounds[0][1]; index[1] <= index_bounds[1][1]; index[1]++)
+	for (index[0] = index_bounds[0][0]; index[0] <= index_bounds[1][0]; index[0]++) {
+		path_node_t *node;
+
+		node = nodes + index[1] * width + index[0];
+		node->accessible = false;
+	}
+}
+
+void path_finder_t::find_r(tile_index_t index, float dist, float limit)
 {
 	path_node_t *node;
 	float dist_to_dst;
@@ -72,7 +91,10 @@ void path_finder_t::find_r(tile_index_t index, float dist)
 		    next[0] >= (int64_t)width || next[1] >= (int64_t)height)
 			continue;
 
-		find_r(next, dist + v2f_t(offset).len());
+		if (dist + v2f_t(offset).len() > limit)
+			continue;
+
+		find_r(next, dist + v2f_t(offset).len(), limit);
 	}
 
 	path.pop_back();
@@ -81,8 +103,11 @@ void path_finder_t::find_r(tile_index_t index, float dist)
 bool path_finder_t::find(void)
 {
 	tile_index_t start;
+	float dist_simple;
+
+	dist_simple = (src - dst).len();
 
-	if ((src - dst).len() < 1.0f)
+	if (dist_simple < 1.0f)
 		return true;
 
 	start = tile_index_at(src) - base;
@@ -99,7 +124,7 @@ bool path_finder_t::find(void)
 		    next[0] >= (int64_t)width || next[1] >= (int64_t)height)
 			continue;
 
-		find_r(next, v2f_t(offset).len());
+		find_r(next, v2f_t(offset).len(), dist_simple * 3);
 	}
 
 	return shortest_path.size() > 0;
diff --git a/src/world.cpp b/src/world.cpp
index ad055c0..07d5638 100644
--- a/src/world.cpp
+++ b/src/world.cpp
@@ -68,10 +68,11 @@ void world_t::generate(sector_t *sector, sector_index_t index)
 	sector->empty = false;
 }
 
-bool world_t::find_path(v2f_t src, v2f_t dst, rectf_t size,
+bool world_t::find_path(v2f_t src, v2f_t dst, rectf_t size, entity_t *ignore,
                         std::list<v2f_t> *path)
 {
 	path_finder_t finder;
+	rectf_t bounds;
 
 	finder.setup_nodes(src, dst);
 
@@ -85,9 +86,32 @@ bool world_t::find_path(v2f_t src, v2f_t dst, rectf_t size,
 		                    get_tile(index)->type <= 3);
 	}
 
+	bounds = rectf_t(src, dst).norm();
+
+	for (entity_t *ent : get_entities(bounds))
+		if (ent != ignore)
+			finder.eliminate_nodes(ent->bounds);
+
 	if (!finder.find())
 		return false;
 
+	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";
+		if (node->accessible)
+			ss << node->dist;
+		else
+			ss << "inaccessible";
+
+		debug.push_back((debug_t){finder.base + tile_index_t(x, y), ss.str()});
+	}
+
+
 	finder.export_path(path);
 	return true;
 }
@@ -146,7 +170,7 @@ std::list<entity_t*> world_t::get_entities(rectf_t rect)
 		if (ent->cookie == cookie)
 			continue;
 
-		if (!rect.intersects(ent->bounds))
+		if (!(rect && ent->bounds))
 			continue;
 
 		ent->cookie = cookie;
@@ -169,7 +193,7 @@ std::list<entity_t*> world_t::get_render_entities(rectf_t rect)
 		if (ent->cookie == cookie)
 			continue;
 
-		if (!rect.intersects(ent->render_bounds))
+		if (!(rect && ent->render_bounds))
 			continue;
 
 		ent->cookie = cookie;
@@ -200,7 +224,7 @@ void entity_t::link(world_t *world)
 	float xlip, ylip;
 	size_t xsecs, ysecs;
 
-	total_bounds = bounds + render_bounds;
+	total_bounds = bounds | render_bounds;
 
 	fx = floor(total_bounds[0][0]);
 	fy = floor(total_bounds[0][1]);