Bring diagonal walking back.

2 files changed, 63 insertions, 12 deletions

diff --git a/src/common.hpp b/src/common.hpp
index 6d4c7c2..10fafcf 100644
--- a/src/common.hpp
+++ b/src/common.hpp
@@ -144,6 +144,10 @@ namespace world {
 	} path_node_t;
 
 	class path_finder_t {
+		path_node_t *node_at(tile_index_t index);
+		bool is_accessible(tile_index_t index);
+		bool diagonal_test(tile_index_t index, size_t i);
+
 	public:
 		v2f_t src, dst, tile_center;
 		cflags_t cflags;
diff --git a/src/path_finder.cpp b/src/path_finder.cpp
index 6d9540c..748a72f 100644
--- a/src/path_finder.cpp
+++ b/src/path_finder.cpp
@@ -3,12 +3,11 @@
 namespace world {
 
 static const v2f_t path_margin(5, 5);
-/*static const tile_index_t path_offsets[8] = {
+
+// The path finder will try to walk in the eight directions listed below.
+static const tile_index_t path_offsets[8] = {
 	{+1, 0}, {+1, +1}, {0, +1}, {-1, +1},
 	{-1, 0}, {-1, -1}, {0, -1}, {+1, -1}
-};*/
-static const tile_index_t path_offsets[4] = {
-	{+1, 0}, {0, +1}, {-1, 0}, {0, -1}
 };
 
 path_finder_t::~path_finder_t()
@@ -76,6 +75,50 @@ void path_finder_t::eliminate_nodes(rectf_t bounds)
 	}
 }
 
+path_node_t *path_finder_t::node_at(tile_index_t index)
+{
+	return nodes + index[1] * width + index[0];
+}
+
+bool path_finder_t::is_accessible(tile_index_t index)
+{
+	if (index[0] < 0 || index[1] < 0 ||
+	    index[0] >= (coord_t)width || index[1] >= (coord_t)height)
+		return false;
+
+	return node_at(index)->accessible;
+}
+
+// Walking diagonally requires an additional accessibility test. The tables
+// below list when it's needed and which tile is to be tested. For example,
+// when walking north-west, the north and the west neighbors have to be tested
+// for accessibility.
+bool path_finder_t::diagonal_test(tile_index_t index, size_t i)
+{
+	static const bool do_test[8] = {
+		false, true, false, true, false, true, false, true
+	};
+	static const tile_index_t offsets[8][2] = {
+		{},
+		{{+1, 0}, {0, +1}},
+		{},
+		{{0, +1}, {-1, 0}},
+		{},
+		{{-1, 0}, {0, -1}},
+		{},
+		{{0, -1}, {+1, 0}}
+	};
+
+	if (!do_test[i])
+		return true;
+
+	for (size_t j = 0; j < 2; j++)
+		if (!is_accessible(index + offsets[i][j]))
+			return false;
+
+	return true;
+}
+
 void path_finder_t::find_r(tile_index_t index, float dist, float limit)
 {
 	path_node_t *node;
@@ -97,14 +140,16 @@ void path_finder_t::find_r(tile_index_t index, float dist, float limit)
 		shortest_dist = dist + dist_to_dst;
 	}
 
-	for (size_t i = 0; i < 4; i++) {
+	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)
+		if (!is_accessible(next))
+			continue;
+
+		if (!diagonal_test(index, i))
 			continue;
 
 		if (dist + v2f_t(offset).len() > limit)
@@ -127,19 +172,21 @@ bool path_finder_t::find(void)
 		return true;
 
 	start = tile_index_at(src) - base;
-	nodes[start[1] * width + start[0]].accessible = false;
+	node_at(start)->accessible = false;
 
-	for (size_t i = 0; i < 4; i++) {
+	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) - tile_center;
 
-		if (next[0] < 0 || next[1] < 0 ||
-		    next[0] >= (int64_t)width || next[1] >= (int64_t)height)
+		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);
 	}