diff options
author | Dan Goodliffe <dan@randomdan.homeip.net> | 2021-03-13 14:42:37 +0000 |
---|---|---|
committer | Dan Goodliffe <dan@randomdan.homeip.net> | 2021-03-13 14:42:37 +0000 |
commit | 56782dbb368117faaddda0a45ca2ecb753af90d7 (patch) | |
tree | b80b09f507fe3932c0404474743c43a0126b88eb | |
parent | Only attempt to render renderable networks (diff) | |
download | ilt-56782dbb368117faaddda0a45ca2ecb753af90d7.tar.bz2 ilt-56782dbb368117faaddda0a45ca2ecb753af90d7.tar.xz ilt-56782dbb368117faaddda0a45ca2ecb753af90d7.zip |
Initial commit of the route finder
-rw-r--r-- | game/network/network.cpp | 18 | ||||
-rw-r--r-- | game/network/network.h | 4 | ||||
-rw-r--r-- | game/network/routeWalker.cpp | 37 | ||||
-rw-r--r-- | game/network/routeWalker.h | 24 | ||||
-rw-r--r-- | test/Jamfile.jam | 1 | ||||
-rw-r--r-- | test/test-network.cpp | 151 |
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(¤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 <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() |