diff options
Diffstat (limited to 'game/network/routeWalker.cpp')
-rw-r--r-- | game/network/routeWalker.cpp | 37 |
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(¤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); +} |