Initial commit of walk/walkUtil terrain

3 files changed, 98 insertions, 1 deletions

diff --git a/game/terrain2.cpp b/game/terrain2.cpp
index cc0bf90..3e24778 100644
--- a/game/terrain2.cpp
+++ b/game/terrain2.cpp
@@ -54,6 +54,28 @@ TerrainMesh::findPoint(glm::vec2 p) const
 	return findPoint(p, *faces_begin());
 }
 
+namespace {
+	[[nodiscard]] constexpr inline bool
+	pointLeftOfLine(const glm::vec2 p, const glm::vec2 e1, const glm::vec2 e2)
+	{
+		return (e2.x - e1.x) * (p.y - e1.y) > (e2.y - e1.y) * (p.x - e1.x);
+	}
+
+	static_assert(pointLeftOfLine({1, 2}, {1, 1}, {2, 2}));
+	static_assert(pointLeftOfLine({2, 1}, {2, 2}, {1, 1}));
+	static_assert(pointLeftOfLine({2, 2}, {1, 2}, {2, 1}));
+	static_assert(pointLeftOfLine({1, 1}, {2, 1}, {1, 2}));
+
+	[[nodiscard]] constexpr inline bool
+	linesCross(const glm::vec2 a1, const glm::vec2 a2, const glm::vec2 b1, const glm::vec2 b2)
+	{
+		return pointLeftOfLine(a2, b1, b2) && pointLeftOfLine(a1, b2, b1) && pointLeftOfLine(b1, a1, a2)
+				&& pointLeftOfLine(b2, a2, a1);
+	}
+
+	static_assert(linesCross({1, 1}, {2, 2}, {1, 2}, {2, 1}));
+}
+
 OpenMesh::FaceHandle
 TerrainMesh::findPoint(glm::vec2 p, OpenMesh::FaceHandle f) const
 {
@@ -64,7 +86,7 @@ TerrainMesh::findPoint(glm::vec2 p, OpenMesh::FaceHandle f) const
 			if (f.is_valid()) {
 				const auto e1 = point(to_vertex_handle(*next));
 				const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(*next)));
-				if ((e2.x - e1.x) * (p.y - e1.y) > (e2.y - e1.y) * (p.x - e1.x)) {
+				if (pointLeftOfLine(p, e1, e2)) {
 					break;
 				}
 			}
@@ -74,6 +96,37 @@ TerrainMesh::findPoint(glm::vec2 p, OpenMesh::FaceHandle f) const
 	return f;
 }
 
+void
+TerrainMesh::walk(const glm::vec2 from, const glm::vec2 to, const std::function<void(FaceHandle)> & op) const
+{
+	walkUntil(from, to, [&op](const auto & fh) {
+		op(fh);
+		return false;
+	});
+}
+
+void
+TerrainMesh::walkUntil(const glm::vec2 from, const glm::vec2 to, const std::function<bool(FaceHandle)> & op) const
+{
+	auto f = findPoint(from);
+	assert(f.is_valid()); // TODO replace with a boundary search
+	FaceHandle previousFace;
+	while (f.is_valid() && !op(f)) {
+		for (auto next = cfh_iter(f); next.is_valid(); ++next) {
+			f = opposite_face_handle(*next);
+			if (f.is_valid() && f != previousFace) {
+				const auto e1 = point(to_vertex_handle(*next));
+				const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(*next)));
+				if (linesCross(from, to, e1, e2)) {
+					previousFace = f;
+					break;
+				}
+			}
+			f.reset();
+		}
+	}
+}
+
 bool
 TerrainMesh::triangleContainsPoint(const glm::vec2 p, const glm::vec2 a, const glm::vec2 b, const glm::vec2 c)
 {
diff --git a/game/terrain2.h b/game/terrain2.h
index 713fe23..848c36e 100644
--- a/game/terrain2.h
+++ b/game/terrain2.h
@@ -21,6 +21,9 @@ public:
 	[[nodiscard]] FaceHandle findPoint(glm::vec2) const;
 	[[nodiscard]] FaceHandle findPoint(glm::vec2, FaceHandle start) const;
 
+	void walk(const glm::vec2 from, const glm::vec2 to, const std::function<void(FaceHandle)> & op) const;
+	void walkUntil(const glm::vec2 from, const glm::vec2 to, const std::function<bool(FaceHandle)> & op) const;
+
 protected:
 	[[nodiscard]] static bool triangleContainsPoint(const glm::vec2, const glm::vec2, const glm::vec2, const glm::vec2);
 	[[nodiscard]] bool triangleContainsPoint(const glm::vec2, FaceHandle) const;
diff --git a/test/test-terrain.cpp b/test/test-terrain.cpp
index d062853..429207c 100644
--- a/test/test-terrain.cpp
+++ b/test/test-terrain.cpp
@@ -65,3 +65,44 @@ BOOST_DATA_TEST_CASE(findPointOnTerrain,
 {
 	BOOST_CHECK_EQUAL(fh, fixedTerrtain.findPoint(p, TerrainMesh::FaceHandle(start)).idx());
 }
+
+using WalkTerrainData = std::tuple<glm::vec2, glm::vec2, std::vector<int>>;
+
+BOOST_DATA_TEST_CASE(walkTerrain,
+		boost::unit_test::data::make<WalkTerrainData>({
+				{{310002, 490003}, {310002, 490003}, {0}},
+				{{310003, 490002}, {310003, 490002}, {1}},
+				{{310002, 490003}, {310003, 490002}, {0, 1}},
+				{{310003, 490002}, {310002, 490003}, {1, 0}},
+				{{310002, 490003}, {310202, 490003}, {0, 1, 2, 3, 4, 5, 6, 7, 8}},
+				{{310202, 490003}, {310002, 490003}, {8, 7, 6, 5, 4, 3, 2, 1, 0}},
+				{{310002, 490003}, {310002, 490203}, {0, 399, 398, 797, 796, 1195, 1194, 1593, 1592}},
+		}),
+		from, to, visits)
+{
+	std::vector<int> visited;
+	BOOST_CHECK_NO_THROW(fixedTerrtain.walk(from, to, [&visited](auto fh) {
+		visited.emplace_back(fh.idx());
+	}));
+	BOOST_CHECK_EQUAL_COLLECTIONS(visited.begin(), visited.end(), visits.begin(), visits.end());
+}
+
+BOOST_DATA_TEST_CASE(walkTerrainUntil,
+		boost::unit_test::data::make<WalkTerrainData>({
+				{{310002, 490003}, {310002, 490003}, {0}},
+				{{310003, 490002}, {310003, 490002}, {1}},
+				{{310002, 490003}, {310003, 490002}, {0, 1}},
+				{{310003, 490002}, {310002, 490003}, {1, 0}},
+				{{310002, 490003}, {310202, 490003}, {0, 1, 2, 3, 4}},
+				{{310202, 490003}, {310002, 490003}, {8, 7, 6, 5, 4}},
+				{{310002, 490003}, {310002, 490203}, {0, 399, 398, 797, 796}},
+		}),
+		from, to, visits)
+{
+	std::vector<int> visited;
+	BOOST_CHECK_NO_THROW(fixedTerrtain.walkUntil(from, to, [&visited](auto fh) {
+		visited.emplace_back(fh.idx());
+		return visited.size() >= 5;
+	}));
+	BOOST_CHECK_EQUAL_COLLECTIONS(visited.begin(), visited.end(), visits.begin(), visits.end());
+}