For my AI in a strategy game, I want to record the distance of the player starbase from every star in a procedural star system. I’ve been unable to find a means to get the number of nodes between two points - there’s a function to return if a path is possible, but it doesn’t return how many nodes are between them. From what I can see, I need to perform a path test for every star and record how many nodes the path is. This strikes me as wasteful. eg Given a star path S - S - S - S - B, performing a path search for each Star to Base will see the same paths covered repeatedly. It’d be better if I could radiate out from B to each star and record the steps, or something.
Is there a faster way than individual path tests for every star to evaluate each star’s distance in nodes from a specified base node? There’s 30+, probably 60 maximum, nodes, mostly linear routes with a few branches and loops, and this needs to run on mobile.
Hi
There is actually no such function at the moment. There is functionality to get the cost (usually the world space length of the path) between one node and every other node, but the cost may not be equal to the number of nodes between them.
The closest is the PathUtilities.BFS method, it actually does calculate this, but it does not return that result.
Here is a slightly modified and simplified version of PathUtilities.BFS which returns a map of the node-distance from one node to every other node (I haven’t tested this code, but I think it should work).
public static Dictionary<GraphNode, int> BFS (GraphNode seed) {
var que = new Queue<GraphNode>();
var map = new Dictionary<GraphNode, int>();
int currentDist = -1;
System.Action<GraphNode> callback = node => {
if (node.Walkable && !map.ContainsKey(node)) {
map.Add(node, currentDist+1);
que.Enqueue(node);
}
};
callback(seed);
while (que.Count > 0) {
GraphNode n = que.Dequeue();
currentDist = map[n];
n.GetConnections(callback);
}
return map;
}