summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--game/network/network.cpp18
-rw-r--r--game/network/network.h4
-rw-r--r--game/network/routeWalker.cpp37
-rw-r--r--game/network/routeWalker.h24
-rw-r--r--test/Jamfile.jam1
-rw-r--r--test/test-network.cpp151
6 files changed, 235 insertions, 0 deletions
diff --git a/game/network/network.cpp b/game/network/network.cpp
index fd61764..7349ff0 100644
--- a/game/network/network.cpp
+++ b/game/network/network.cpp
@@ -1,9 +1,11 @@
#include "network.h"
+#include "routeWalker.h"
#include <array>
#include <cache.h>
#include <game/network/link.h>
#include <gfx/models/texture.h>
#include <initializer_list>
+#include <stdexcept>
#include <utility>
Network::Network(const std::string & tn) : texture {Texture::cachedTexture.get(tn)} { }
@@ -44,3 +46,19 @@ Network::joinLinks(const LinkPtr & l, const LinkPtr & ol)
}
}
}
+
+std::vector<LinkWPtr>
+Network::routeFromTo(const Link::End & start, glm::vec3 dest) const
+{
+ auto destNode {findNodeAt(dest)};
+ if (!destNode) {
+ throw std::out_of_range("Node does not exist in network");
+ }
+ return routeFromTo(start, destNode);
+}
+
+std::vector<LinkWPtr>
+Network::routeFromTo(const Link::End & end, const NodePtr & dest) const
+{
+ return RouteWalker().findRouteTo(end, dest);
+}
diff --git a/game/network/network.h b/game/network/network.h
index c6d4dfa..f84c90c 100644
--- a/game/network/network.h
+++ b/game/network/network.h
@@ -10,6 +10,7 @@
#include <sorting.hpp>
#include <string>
#include <utility>
+#include <vector>
class Texture;
class Shader;
@@ -22,6 +23,9 @@ public:
[[nodiscard]] NodePtr nodeAt(glm::vec3);
[[nodiscard]] std::pair<NodePtr, bool> newNodeAt(glm::vec3);
+ [[nodiscard]] std::vector<LinkWPtr> routeFromTo(const Link::End &, glm::vec3) const;
+ [[nodiscard]] std::vector<LinkWPtr> routeFromTo(const Link::End &, const NodePtr &) const;
+
protected:
static void joinLinks(const LinkPtr & l, const LinkPtr & ol);
diff --git a/game/network/routeWalker.cpp b/game/network/routeWalker.cpp
new file mode 100644
index 0000000..496f9f3
--- /dev/null
+++ b/game/network/routeWalker.cpp
@@ -0,0 +1,37 @@
+#include "routeWalker.h"
+#include <array>
+#include <game/network/link.h>
+#include <limits>
+#include <memory>
+#include <utility>
+
+RouteWalker::RouteWalker() : solutionLength {std::numeric_limits<float>::max()} { }
+
+RouteWalker::Solution
+RouteWalker::findRouteTo(const Link::End & currentEnd, const NodePtr & dest)
+{
+ findRouteTo(currentEnd, dest, 0);
+ return bestSolution;
+}
+
+void
+// NOLINTNEXTLINE(misc-no-recursion)
+RouteWalker::findRouteTo(const Link::End & currentEnd, const NodePtr & dest, float length)
+{
+ if (currentEnd.node == dest && length < solutionLength) {
+ bestSolution = currentSolution;
+ solutionLength = length;
+ return;
+ }
+ if (visited.contains(&currentEnd)) { // We've been here before
+ return;
+ }
+ visited.insert(&currentEnd);
+ for (const auto & nexts : currentEnd.nexts) {
+ const auto link = nexts.first.lock();
+ currentSolution.push_back(link);
+ findRouteTo(link->ends[!nexts.second], dest, length + link->length);
+ currentSolution.pop_back();
+ }
+ visited.erase(&currentEnd);
+}
diff --git a/game/network/routeWalker.h b/game/network/routeWalker.h
new file mode 100644
index 0000000..7b1e1c8
--- /dev/null
+++ b/game/network/routeWalker.h
@@ -0,0 +1,24 @@
+#ifndef ROUTEWALKER_H
+#define ROUTEWALKER_H
+
+#include "link.h"
+#include <set>
+#include <vector>
+
+class RouteWalker {
+public:
+ using Solution = std::vector<LinkWPtr>;
+
+ RouteWalker();
+
+ Solution findRouteTo(const Link::End & currentEnd, const NodePtr & dest);
+
+private:
+ void findRouteTo(const Link::End & currentEnd, const NodePtr & dest, float length);
+
+ std::set<const Link::End *> visited;
+ Solution bestSolution, currentSolution;
+ float solutionLength;
+};
+
+#endif
diff --git a/test/Jamfile.jam b/test/Jamfile.jam
index ffc1a19..f1fda72 100644
--- a/test/Jamfile.jam
+++ b/test/Jamfile.jam
@@ -17,3 +17,4 @@ project : requirements
run test-collection.cpp ;
run test-obj.cpp ;
run test-maths.cpp ;
+run test-network.cpp ;
diff --git a/test/test-network.cpp b/test/test-network.cpp
new file mode 100644
index 0000000..80ff1ef
--- /dev/null
+++ b/test/test-network.cpp
@@ -0,0 +1,151 @@
+#define BOOST_TEST_MODULE network
+
+#include <boost/test/data/test_case.hpp>
+#include <boost/test/unit_test.hpp>
+
+#include <array>
+#include <collection.hpp>
+#include <game/network/link.h>
+#include <game/network/network.h>
+#include <game/network/network.impl.h> // IWYU pragma: keep
+#include <glm/glm.hpp>
+#include <location.hpp>
+#include <maths.h>
+#include <memory>
+#include <stdexcept>
+#include <stream_support.hpp>
+#include <utility>
+#include <vector>
+
+struct TestLink : public Link {
+ TestLink(NodePtr a, NodePtr b, float ad, float bd, float l) : Link {{std::move(a), ad}, {std::move(b), bd}, l} { }
+ [[nodiscard]] Location
+ positionAt(float, unsigned char) const override
+ {
+ throw std::runtime_error("not implemented");
+ }
+};
+
+constexpr glm::vec3 p000 {0, 0, 0}, p100 {1, 0, 0}, p200 {2, 0, 0}, p300 {3, 0, 0};
+
+struct TestNetwork : public NetworkOf<TestLink> {
+ TestNetwork() : NetworkOf<TestLink> {RESDIR "rails.jpg"}
+ {
+ // 0 1 2
+ // p000 <-> p100 <-> p200 <-> p300
+ addLink<TestLink>(p000, p100, 0.F, pi, 1.F);
+ addLink<TestLink>(p100, p200, 0.F, pi, 1.F);
+ addLink<TestLink>(p200, p300, 0.F, pi, 1.F);
+ }
+};
+
+const auto VALID_NODES = boost::unit_test::data::make<glm::vec3>({
+ p000,
+ p100,
+ p200,
+ p300,
+});
+const auto INVALID_NODES = boost::unit_test::data::make<glm::vec3>({
+ {1000, 0, 0},
+ {0, 1000, 0},
+ {0, 0, 1000},
+});
+
+BOOST_FIXTURE_TEST_SUITE(tn, TestNetwork)
+
+BOOST_DATA_TEST_CASE(findNodeAt_valid, VALID_NODES, p)
+{
+ auto n = findNodeAt(p);
+ BOOST_REQUIRE(n);
+ BOOST_CHECK_EQUAL(n->pos, p);
+}
+
+BOOST_DATA_TEST_CASE(findNodeAt_invalid, INVALID_NODES, p)
+{
+ BOOST_REQUIRE(!findNodeAt(p));
+}
+
+BOOST_DATA_TEST_CASE(nodeAt, VALID_NODES + INVALID_NODES, p)
+{
+ auto n = nodeAt(p);
+ BOOST_REQUIRE(n);
+ BOOST_CHECK_EQUAL(n->pos, p);
+}
+
+BOOST_DATA_TEST_CASE(newNodeAt_existing, VALID_NODES, p)
+{
+ auto n = newNodeAt(p);
+ BOOST_CHECK(!n.second);
+ BOOST_REQUIRE(n.first);
+ BOOST_CHECK_EQUAL(n.first->pos, p);
+}
+
+BOOST_DATA_TEST_CASE(newNodeAt_new, INVALID_NODES, p)
+{
+ auto n = newNodeAt(p);
+ BOOST_CHECK(n.second);
+ BOOST_REQUIRE(n.first);
+ BOOST_CHECK_EQUAL(n.first->pos, p);
+}
+
+BOOST_AUTO_TEST_CASE(network_joins)
+{
+ // Ends
+ BOOST_CHECK(links.objects[0]->ends[0].nexts.empty());
+ BOOST_CHECK(links.objects[2]->ends[1].nexts.empty());
+ // Join 0 <-> 1
+ BOOST_REQUIRE_EQUAL(links.objects[0]->ends[1].nexts.size(), 1);
+ BOOST_CHECK_EQUAL(links.objects[0]->ends[1].nexts.front().first.lock().get(), links.objects[1].get());
+ BOOST_CHECK_EQUAL(links.objects[0]->ends[1].nexts.front().second, 0);
+ BOOST_REQUIRE_EQUAL(links.objects[1]->ends[0].nexts.size(), 1);
+ BOOST_CHECK_EQUAL(links.objects[1]->ends[0].nexts.front().first.lock().get(), links.objects[0].get());
+ BOOST_CHECK_EQUAL(links.objects[1]->ends[0].nexts.front().second, 1);
+ // Join 1 <-> 2
+ BOOST_REQUIRE_EQUAL(links.objects[1]->ends[1].nexts.size(), 1);
+ BOOST_CHECK_EQUAL(links.objects[1]->ends[1].nexts.front().first.lock().get(), links.objects[2].get());
+ BOOST_CHECK_EQUAL(links.objects[1]->ends[1].nexts.front().second, 0);
+ BOOST_REQUIRE_EQUAL(links.objects[2]->ends[0].nexts.size(), 1);
+ BOOST_CHECK_EQUAL(links.objects[2]->ends[0].nexts.front().first.lock().get(), links.objects[1].get());
+ BOOST_CHECK_EQUAL(links.objects[2]->ends[0].nexts.front().second, 1);
+}
+
+BOOST_DATA_TEST_CASE(routeTo_nodeNotInNetwork, INVALID_NODES, dest)
+{
+ const auto & start = links.objects.front()->ends[1];
+ BOOST_CHECK_THROW((void)routeFromTo(start, dest), std::out_of_range);
+}
+
+BOOST_AUTO_TEST_CASE(routeTo_noSteps)
+{
+ const auto & start = links.objects.front()->ends[1];
+ auto r = this->routeFromTo(start, p100);
+ BOOST_CHECK(r.empty());
+}
+
+BOOST_AUTO_TEST_CASE(routeTo_upStream_to2)
+{
+ const auto & start = links.objects.front()->ends[1];
+ auto r = this->routeFromTo(start, p200);
+ BOOST_REQUIRE_EQUAL(r.size(), 1);
+ BOOST_CHECK_EQUAL(r[0].lock().get(), links.objects[1].get());
+}
+
+BOOST_AUTO_TEST_CASE(routeTo_upStream_to3)
+{
+ const auto & start = links.objects.front()->ends[1];
+ auto r = this->routeFromTo(start, p300);
+ BOOST_REQUIRE_EQUAL(r.size(), 2);
+ BOOST_CHECK_EQUAL(r[0].lock().get(), links.objects[1].get());
+ BOOST_CHECK_EQUAL(r[1].lock().get(), links.objects[2].get());
+}
+
+BOOST_AUTO_TEST_CASE(routeTo_downStream_to0)
+{
+ const auto & start = links.objects.back()->ends[0];
+ auto r = this->routeFromTo(start, p000);
+ BOOST_REQUIRE_EQUAL(r.size(), 2);
+ BOOST_CHECK_EQUAL(r[0].lock().get(), links.objects[1].get());
+ BOOST_CHECK_EQUAL(r[1].lock().get(), links.objects[0].get());
+}
+
+BOOST_AUTO_TEST_SUITE_END()
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-20 07:01:53 +0000