CODEWITHSUNDEEP
c++path-findingunreal-engine4
RectangleEquals
RectangleEquals

Reputation: 1825

Complicated pathfinding algorithm

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.

Upvotes: 3

Views: 504

Answers (2)

Sergei
Sergei

Reputation: 550

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.

Upvotes: 1

Khalil Khalaf
Khalil Khalaf

Reputation: 9407

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

Upvotes: 2

Related Questions