From c9a0aff5a9333cf5e0ee55ba5c8551457a3ae13c Mon Sep 17 00:00:00 2001
From: Paweł Redman <pawel.redman@gmail.com>
Date: Mon, 26 Mar 2018 19:27:17 +0200
Subject: WIP

---
 src/path_finder.cpp | 64 +++++++++++++++++++++++++++++++----------------------
 1 file changed, 37 insertions(+), 27 deletions(-)

(limited to 'src/path_finder.cpp')

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;
 }
-- 
cgit