WIPpath-experiments

4 files changed, 52 insertions, 33 deletions

diff --git a/src/common.hpp b/src/common.hpp
index 6042e08..d4950e4 100644
--- a/src/common.hpp
+++ b/src/common.hpp
@@ -256,6 +256,7 @@ namespace game {
 		bool paused;
 		ntime_t t0;
 		size_t frames = 0, frames_since_t0, frames_behind = 0;
+		ntime_t pathfinder_time = 0;
 
 		void start(void);
 		void stop(void);
diff --git a/src/game/interface.cpp b/src/game/interface.cpp
index 262c3ae..bd70dbb 100644
--- a/src/game/interface.cpp
+++ b/src/game/interface.cpp
@@ -277,7 +277,11 @@ void state_t::render_to(render::state_t *render)
 	x[1] += em;
 	ss.str(std::string());
 	ss << std::fixed << std::setprecision(3);
-	ss << "Game t/F/B: " << game->time * 1.0e-9 << "/" << game->frames << "/" << game->frames_behind;
+	ss << "Game t/F/B/PFT: ";
+	ss << game->time * 1.0e-9 << "/";
+	ss << game->frames << "/";
+	ss << game->frames_behind << "/";
+	ss << game->pathfinder_time * 1.0e-9 << " (" << ((float)game->pathfinder_time / game->time * 100.0f) << "%)";
 	render->render_text(x, em, ss.str(), render::ALIGN_LEFT_TOP, sf::Color::White);
 }
 
diff --git a/src/game/units.cpp b/src/game/units.cpp
index edb41ec..5f722aa 100644
--- a/src/game/units.cpp
+++ b/src/game/units.cpp
@@ -163,6 +163,8 @@ bool unit_t::keep_moving(double speed)
 bool unit_t::start_moving(v2f_t dst)
 {
 	world::cmodel_t rep;
+	ntime_t t0;
+	bool rv;
 
 	if (!world) {
 		printf("unit_t::start_moving: entity is not linked\n");
@@ -175,7 +177,10 @@ bool unit_t::start_moving(v2f_t dst)
 	rep.cflags = move.cflags & ~(cmodel.cflags);
 	rep.bounds = cmodel.bounds;
 
-	if (!world->find_path(x, move.dst, &rep, this, &move.path)) {
+	t0 = nclock();
+	rv = world->find_path(x, move.dst, &rep, this, &move.path);
+	game->pathfinder_time += nclock() - t0;
+	if (!rv) {
 		move.moving = false;
 		return false;
 	}
@@ -531,8 +536,8 @@ void unit_soldier_t::render_late_to(render::state_t *render)
 
 unit_spider_t::unit_spider_t(game::state_t *game) : unit_t(game, UNIT_SPIDER)
 {
-	size[0] = v2f_t(-0.2f, +0.0f);
-	size[1] = v2f_t(+0.2f, +0.3f);
+	size[0] = v2f_t(-0.3f, +0.0f);
+	size[1] = v2f_t(+0.3f, +0.3f);
 	render_size[0] = v2f_t(-0.3f, -0.3f);
 	render_size[1] = v2f_t(+0.3f, +0.3f);
 	cmodel.cflags = CF_BODY_SMALL;
@@ -560,7 +565,7 @@ void unit_spider_t::target_and_attack(void)
 		return;
 
 	start_moving(target->x);
-	next_targetting = game->now + 0.2;
+	next_targetting = game->now + 500.0;
 
 	if (last_attack + 0.5 > game->now)
 		return;
@@ -588,7 +593,6 @@ void unit_spider_t::on_think(void)
 
 void unit_spider_t::on_wake(void)
 {
-	next_targetting = game->now;
 }
 
 void unit_spider_t::on_death(void)
diff --git a/src/path_finder.cpp b/src/path_finder.cpp
index 8a61cc6..04f4d57 100644
--- a/src/path_finder.cpp
+++ b/src/path_finder.cpp
@@ -136,10 +136,36 @@ bool path_finder_t::diagonal_test(tile_index_t index, size_t i)
 	return true;
 }
 
+static const int visit_orders[4][8] = {
+	{0, 7, 1, 2, 6, 5, 3, 4}, // prefer +x
+	{2, 3, 1, 0, 4, 7, 5, 6}, // prefer +y
+	{4, 5, 3, 2, 6, 1, 7, 0}, // prefer -x
+	{6, 5, 7, 0, 4, 3, 1, 2}  // prefer -y
+};
+
+static const int *visit_order(v2f_t delta)
+{
+	if (delta[1] > delta[0]) {
+		if (delta[1] > -delta[0])
+			return visit_orders[1];
+		else
+			return visit_orders[2];
+	} else {
+		if (delta[1] > -delta[0])
+			return visit_orders[0];
+		else
+			return visit_orders[3];
+	}
+
+	return visit_orders[0];
+}
+
 void path_finder_t::find_r(tile_index_t index, float dist, float limit)
 {
 	path_node_t *node;
+	v2f_t delta;
 	float dist_to_dst;
+	const int *order;
 
 	node = nodes + index[1] * width + index[0];
 
@@ -148,31 +174,37 @@ void path_finder_t::find_r(tile_index_t index, float dist, float limit)
 	if (node->dist <= dist)
 		return;
 
-	path.push_back(index);
 	node->dist = dist;
+	path.push_back(index);
 
-	dist_to_dst = (v2f_t(base + index) + tile_center - dst).len();
+	delta = dst - v2f_t(base + index) - tile_center;
+	dist_to_dst = delta.len();
 	if (dist_to_dst < 1.0f && dist + dist_to_dst < shortest_dist) {
 		shortest_path = path;
 		shortest_dist = dist + dist_to_dst;
+		return;
 	}
 
+	order = visit_order(delta);
+
 	for (size_t i = 0; i < 8; i++) {
 		tile_index_t offset, next;
 
-		offset = path_offsets[i];
+		offset = path_offsets[order[i]];
 		next = index + offset;
 
 		if (!is_accessible(next))
 			continue;
 
-		if (!diagonal_test(index, i))
+		if (!diagonal_test(index, order[i]))
 			continue;
 
 		if (dist + v2f_t(offset).len() > limit)
 			continue;
 
 		find_r(next, dist + v2f_t(offset).len(), limit);
+		if (shortest_path.size())
+			return;
 	}
 
 	path.pop_back();
@@ -181,31 +213,9 @@ void path_finder_t::find_r(tile_index_t index, float dist, float limit)
 bool path_finder_t::find(void)
 {
 	tile_index_t start;
-	float dist_simple;
-
-	dist_simple = (src - dst).len();
-
-	if (dist_simple < 0.5f)
-		return true;
 
 	start = tile_index_at(src) - base;
-	node_at(start)->accessible = false;
-
-	for (size_t i = 0; i < 8; i++) {
-		tile_index_t next;
-		v2f_t offset;
-
-		next = start + path_offsets[i];
-
-		if (!is_accessible(next))
-			continue;
-
-		if (!diagonal_test(start, i))
-			continue;
-
-		offset = (src - v2f_t(base)) - v2f_t(next) - tile_center;
-		find_r(next, v2f_t(offset).len(), dist_simple * 3);
-	}
+	find_r(start, 0.0f, 100.0f);
 
 	return shortest_path.size() > 0;
 }