I have a set of nodes with spline components connecting them together.
Connections made between each node allows for bi-directional travel… Meaning that any direction, both to and from the previous node, is considered a valid move.
The goal of this project is to:
- Figure out which path(s) are valid ones to take in order to reach the target node, returning a list of each valid path as an array of nodes (i.e.: [FONT=Courier New]std::vector<TArray<ANode*>> validPaths;).
- Figure out which of the valid paths is the shortest path to take, based upon overall spline length. This can easily be calculated for each [FONT=Courier New]validPath returned.
So in the image above, with [FONT=Courier New]NodeA as the root and [FONT=Courier New]NodeE1 as the target, these would be valid paths:
- Valid Path #1: [FONT=Courier New]NodeA > [FONT=Courier New]NodeB1 > [FONT=Courier New]NodeC2 > [FONT=Courier New]NodeD2 > [FONT=Courier New]NodeE1
- Valid Path #2: [FONT=Courier New]NodeA > [FONT=Courier New]NodeB2 > [FONT=Courier New]NodeC4 > [FONT=Courier New]NodeD2 > [FONT=Courier New]NodeE1
And in this example, Path #2 would be the shortest path, because it’s overall spline length ends up being shorter than Path #1’s spline lengths.
I have tried many different traversal algorithms in order to return a valid path, including Depth-First Search and Breadth-First Search.
Both of those algorithms seem to visit each node perfectly fine, and without recursion or infinite loop (with the aid of a “visited” array of nodes)…
But neither of them seem to be able to construct a valid path in the correct order… Or rather, I can’t seem to find a way to do it without recursion.
Dijkstra’s Algorithm could possibly work, but I’m having trouble implementing it when all valid moves are bi-directional.
So what can I do to get a list of all valid paths?