From 56782dbb368117faaddda0a45ca2ecb753af90d7 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 13 Mar 2021 14:42:37 +0000 Subject: Initial commit of the route finder --- game/network/network.cpp | 18 ++++++ game/network/network.h | 4 ++ game/network/routeWalker.cpp | 37 +++++++++++ game/network/routeWalker.h | 24 +++++++ test/Jamfile.jam | 1 + test/test-network.cpp | 151 +++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 235 insertions(+) create mode 100644 game/network/routeWalker.cpp create mode 100644 game/network/routeWalker.h create mode 100644 test/test-network.cpp 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 #include #include #include #include +#include #include 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 +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 +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 #include #include +#include class Texture; class Shader; @@ -22,6 +23,9 @@ public: [[nodiscard]] NodePtr nodeAt(glm::vec3); [[nodiscard]] std::pair newNodeAt(glm::vec3); + [[nodiscard]] std::vector routeFromTo(const Link::End &, glm::vec3) const; + [[nodiscard]] std::vector 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 +#include +#include +#include +#include + +RouteWalker::RouteWalker() : solutionLength {std::numeric_limits::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(¤tEnd)) { // We've been here before + return; + } + visited.insert(¤tEnd); + 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(¤tEnd); +} 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 +#include + +class RouteWalker { +public: + using Solution = std::vector; + + RouteWalker(); + + Solution findRouteTo(const Link::End & currentEnd, const NodePtr & dest); + +private: + void findRouteTo(const Link::End & currentEnd, const NodePtr & dest, float length); + + std::set 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 +#include + +#include +#include +#include +#include +#include // IWYU pragma: keep +#include +#include +#include +#include +#include +#include +#include +#include + +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 { + TestNetwork() : NetworkOf {RESDIR "rails.jpg"} + { + // 0 1 2 + // p000 <-> p100 <-> p200 <-> p300 + addLink(p000, p100, 0.F, pi, 1.F); + addLink(p100, p200, 0.F, pi, 1.F); + addLink(p200, p300, 0.F, pi, 1.F); + } +}; + +const auto VALID_NODES = boost::unit_test::data::make({ + p000, + p100, + p200, + p300, +}); +const auto INVALID_NODES = boost::unit_test::data::make({ + {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() -- cgit v1.2.3