summaryrefslogtreecommitdiff
path: root/game/network/routeWalker.cpp
diff options
context:
space:
mode:
authorDan Goodliffe <dan@randomdan.homeip.net>2021-03-13 14:42:37 +0000
committerDan Goodliffe <dan@randomdan.homeip.net>2021-03-13 14:42:37 +0000
commit56782dbb368117faaddda0a45ca2ecb753af90d7 (patch)
treeb80b09f507fe3932c0404474743c43a0126b88eb /game/network/routeWalker.cpp
parentOnly attempt to render renderable networks (diff)
downloadilt-56782dbb368117faaddda0a45ca2ecb753af90d7.tar.bz2
ilt-56782dbb368117faaddda0a45ca2ecb753af90d7.tar.xz
ilt-56782dbb368117faaddda0a45ca2ecb753af90d7.zip
Initial commit of the route finder
Diffstat (limited to 'game/network/routeWalker.cpp')
-rw-r--r--game/network/routeWalker.cpp37
1 files changed, 37 insertions, 0 deletions
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);
+}