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.
[HR][/HR]
My Objective:
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.
[HR][/HR]
My Problem:
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?
Hi Michael,
as far as I can tell, calling this function with from=nodeA and To=NodeC2, getting NodeB1 seems to be expected (and correct) behavior. What exactly do you want to have in appendix? Maybe you should test this with a more nested structure that also has several paths to your goal. Right now, there is only one path when you specifically look for a function that is supposed to return all valid paths.
Cheers,
Yes I see your point, but my problem is that I can’t even figure out a proper way to return even ONE valid path, which is why my code has been shrunk down to minimal code.
I do get NodeB1, which is correct, but it’s the only thing that this function is returning — one node away from the target. In other words, if there were another set of nodes “Node D1” through “D8”, and the target were “D3” coming from NodeA, then the array would only contain {NodeC2, (empty)} and NOT {NodeC2, NodeB1}. Also, I would prefer it if the array actually contained these paths in order (i.e., {NodeA, NodeB1, NodeC2, NodeD3} etc)… But at this point, I’ll take whatever I can get and I’ll work with that.
Another thing that’s throwing me for a loop (excuse the pun) is that, even though it looks like a tree, it’s actually a graph where some nodes can be connected to each other.
i.e., it’s valid to have NodeC1 connected to NodeC2… This seems to make recursion much more difficult, due to the dangers of infinite loops and stack overflows.
Not sure how to properly handle this.
In general this is basically a traversal algorithm that’s going through directed cyclical graph (if you don’t allow cycles then directed acyclical graph or DAG). We know we have:
These just differ by using a queue instead of a stack to store the current traversed nodes. You also need to keep a list of visited nodes to avoid infinite loop. You really don’t need recursion as it is expensive for this algorithm. Here’s a break down in pseudo-code
- Put root node into Stack/Queue
- While Stack/Queue is not empty, Do:
- Pop or Dequeue a node
- Do work and add this to the visited list
- for each of its connected node, push it or enqueue it
Since you are looking for path, depth first will give you a single path at a time while breath first will give you all path incrementally.
I have updated my original post with a much better explanation and example of what I require.
