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.

Improve this question
10
  • Can we have this a duplicate of How to find the shortest simple path in a Tree in a linear time? or is there more to your problem? Commented Apr 26, 2016 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 Commented Apr 26, 2016 at 11:57
  • Maybe you want to look at the Wikipedia page for 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. Commented Apr 26, 2016 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 :) Commented Apr 26, 2016 at 12:01
  • @freeNick there are weights on every connection. So every path has a different value: Sum of connections' weights Commented Apr 26, 2016 at 12:03

2 Answers 2

Reset to default
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

Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

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.
@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
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.
I revert that statement, there actually is a goal (read my updated question)
@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
|
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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.