3

I'm writing a system for a 3D game that allows the camera to travel between a network of nodes.

In my project, I've written a class which represents a node. Unlike a binary node class, each node can only have one parent node, but is allowed to have any number of children. Using my truly amazing paint skills, I've developed an image which represents a network of these nodes:

In this example, the "root node" is red, the yellow path is the shortest, and the blue path is the longest.
The important thing to note here is that the actual number of child nodes don't matter, but rather, the added length of the paths between them. Because of this, heuristics shouldn't be necessary in calculating the shortest path, because the shortest path will have the smallest combined length.

So how would you write a recursive function to traverse this tree, and return the shortest path?

Update

As amazing as my paint skills were, I feel that it doesn't fully illustrate my problem, and perhaps requires a more detailed explanation...

First of all, this is for a camera system in 3D world space. The world will be filled with a bunch of these nodes, and the camera will be placed on one of them. The player is allowed to look in any direction, but cannot move without clicking the mouse in a given direction. Once a click event occurs, a raycast is shot out in the direction he is facing, retrieving a list of nodes between him and X distance away from him. The objective here is to find the furthest node connected to his, and then the shortest path to get there...

So the first problem is actually checking if the furthest "hit" node is actually reachable faster than, say, the next closest "hit" node. It's possible that the furthest node might contain a path that is actually longer than the node directly in front of it, so I would also need some way of checking this. So there is a goal in mind, but the goal could change to a slightly closer node, making things all the more complicated.

And yes, while nodes may only have one parent (as stated above), this "tree" should actually be traversable in any direction, from any node in the network, treating the node the player is currently at as the "root" node.

RectangleEquals
  • 1,825
  • 2
  • 25
  • 44
  • Can we have this a duplicate of [How to find the shortest simple path in a Tree in a linear time?](http://stackoverflow.com/questions/4977112/how-to-find-the-shortest-simple-path-in-a-tree-in-a-linear-time) or is there more to your problem? – dhke Apr 26 '16 at 11:50
  • A Dijkstras Algorithm that builds the graph will fix it for you. Just look it up. I did this a while ago and it worked like a charm. It finds the shortest path between ANY two nodes and tells what are the nodes/path to follow. I missed the the paint skills however – Khalil Khalaf Apr 26 '16 at 11:57
  • Maybe you want to look at the Wikipedia page for [Dijkstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra's_algorithm). There's a nice animation of it as well. The only difference is that instead of terminating when you hit the goal node, you terminate on any leaf. – alcedine Apr 26 '16 at 11:58
  • I don't understand what you want. Do you want to calculate paths to all children? Then it doesn't matter what algorithm you use, pick any (depth-first, breadth-first). If you want to find the shortest way between the two given nodes, then the "shortest" part is irrelevant: since any node can have only one parent (it's a tree), there is only one path. One or zero. Am I misunderstanding something? P.S. Your paint skills are magnificent :) – FreeNickname Apr 26 '16 at 12:01
  • @freeNick there are weights on every connection. So every path has a different value: Sum of connections' weights – Khalil Khalaf Apr 26 '16 at 12:03
  • @FirstStep, yes, I get it, but why is it important, if there is only one path? One or zero. It's not an arbitary graph, it's a tree. – FreeNickname Apr 26 '16 at 12:07
  • @free well that is correct. There is only one path to every leaf in HIS paint. But based on what he explained, all leaves of his paint are actually one "thing" that he is trying to reach, but needs to find the shortest path to it – Khalil Khalaf Apr 26 '16 at 12:19
  • @FreeNickname In my head, it definitely looks like a tree, but I might be wrong since this "tree" needs to be traversable in any direction from any node (perhaps even including actual it's parent, treating it as a child node?)... The reason I say this now is because these nodes will be physically placed on a map in 3D space, and the player should be able to click in any direction to travel from the node he's at, along the shortest path to the farthest node in the direction he is facing. I'll try to update my question to reflect this – RectangleEquals Apr 26 '16 at 12:23
  • @rec, using Dijkstras to find the least cost/shortest path between two nodes, `source node` is player's current location and `destination node` is player's clicked node sounds doable to me – Khalil Khalaf Apr 26 '16 at 12:44
  • Is your intention to pre-process, find all shortest paths and use that? Or is this dynamic? Dijkstra will find the shortest path but it can be quite intensive (slow), not really suitable if your tree grows and you want the shortest path with a time constraint. A* and variants thereof are used a lot in games as a well performing compromise. https://en.wikipedia.org/wiki/A*_search_algorithm – Robinson Apr 26 '16 at 13:11

2 Answers2

2

A Dijkstras Algorithm will fix it for you. You would need to feed your system the graph: How many Nodes, Who are the Neighbors of every Node, Weights of every connection.. etc. Just look it up. I did this a while ago and it worked like a charm. It finds the shortest path between ANY two nodes and if you tune it a little bit (I had to tune what I found onlien back then), it tells what are the nodes/path to follow. I missed the the paint skills however

Some Implementation Versions HERE

Khalil Khalaf
  • 9,259
  • 11
  • 62
  • 104
  • Is this really just Dijkstra's algorithm? It seems rather similar... except that in the example I've posted, there is no predefined "goal" that you are trying to reach. The goal will simply be whichever ending path from the root is the shortest, regardless of how many child nodes have been traversed. – RectangleEquals Apr 26 '16 at 12:04
  • @reck It's an extra that it provides you the shortest between ANY two nodes. In your case If I understand right, source would be the root and destination would be all leafs (loop), then pick the minimum – Khalil Khalaf Apr 26 '16 at 12:06
  • 2
    If you allow Dijkstra's algorithm to parse the entire graph (i.e. its only termination condition is that the open set is empty) then it will assign every node a distance value from the root. You then simply iterate over every node to find the lowest and highest values. – Fibbs Apr 26 '16 at 12:12
  • I revert that statement, there actually is a goal (read my updated question) – RectangleEquals Apr 26 '16 at 12:35
  • @rec could you use your _truly amazing_ paint skills and draw an exact graph of what the player sees and how the nodes are connected and NOT how it is in your head for now? Because I didn't see anything different or anything that yet Dijkstra's can't solve – Khalil Khalaf Apr 26 '16 at 12:38
  • Perhaps instead of solving this with Dijkstra's, it would be better to do away with the concept of having a parent & child node(s), and simply have an array of `connectedNodes` sorted by their distances? – RectangleEquals Apr 26 '16 at 13:05
  • @rec You know your problem better. Give it a shot and see – Khalil Khalaf Apr 26 '16 at 13:06
  • @Fibbles Sounds like this is what I need to do. I'll throw the parent/child pattern out of the window, and simply treat it as a graph, then use Dijkstra's algorithm to sort each element by distance, then simply use that as a map to dynamically add up the costs – RectangleEquals Apr 26 '16 at 15:49
  • @rec Good luck. You will like it and it's efficient if the problem is simple (graph is small but it still work for crazy large graphs no problem). One thing to note, Dijkstra will check the WHOLE graph and provide you a cost from a source to EVERYTHING. Unlike A*. Look at the animations(right side of the page) in Wikipedia and choose wisely (I chose Dij and it took three days to work with full awesomeness) – Khalil Khalaf Apr 26 '16 at 15:54
  • So processing speed matters if you don't need EVERYTHING. Two resources that do comparisons between A* and Dij here http://stackoverflow.com/questions/1332466/how-does-dijkstras-algorithm-and-a-star-compare and here http://gis.stackexchange.com/questions/23908/what-is-the-difference-between-astar-and-dijkstra-algorithms-in-pgrouting – Khalil Khalaf Apr 26 '16 at 15:57
1

I guess you want to represent your 3d world is a graph of accessible points in space. Forget about trees, they are just special cases of graphs. Then look into Dijkstra's algorithm. If you need to make it more efficient look into A* which is an improvement over Dijkstra's.

Sergei
  • 508
  • 7
  • 13