Farthest walkable node

General
1

Hello, im trying to figure out how to get the farthest node for a given position. Being this position transform.position in the following code:

List availNodes = PathUtilities.GetReachableNodes(AstarPath.active.GetNearest(transform.position).node); int i = 0; foreach (Node node in availNodes) { int cost = (node.position - AstarPath.active.GetNearest(transform.position).node.position).costMagnitude; print(i + " -> " + node.position.ToString() + " " + cost); i++; }

So im printing the cost of each node, but the farthest node is not the one with the more cost.
Any clue? Is there a better way to do this?

Also in the documentation “GetReachableNodes” says that “The returned list is sorted by node distance from the seed node”
but it doesn’t seem the case for me.

Thanks in advance.

2

Point that in this sentence:


So im printing the cost of each node, but the farthest node is not the one with the more cost.
Any clue? Is there a better way to do this?

By farthest node i mean the one that i know it is the farthest one, the problem is that from the output of my code that doesnt seem to be case.

3

If you could explain how your wanting to use this info, it would help a lot~

Sadly finding the Farthest node is not quite as simple as comparing costMagnitude. This is because the costMagnitude returns the cost to move from one node to the next, not all the nodes between;

Edit: If I find an easy fix I will let you know

4

Id like to have an agent travel to the farthest walkable node from a given position, farthest in relation to the number of nodes the agent has to travel. Your are right, costs are relative to adjacent nodes, so this is a bit more complicated than i though, ill kepp thinking about it, thnx

5

*Removed Due to the much better answer below :slight_smile:

6

Int3.costMagnitude is basically the distance. It is named costMagnitude because that is the default cost if there is a direct connection between those two nodes. Usually there isn’t. So the script posted in the first part will list the euclidean distances to the different nodes, not the actual number of nodes it took to get there.

If you want the farthest node, as in the number of nodes it takes to get there:
// Replace GraphNode with Node if you are not using the beta List<GraphNode> availNodes = PathUtilities.GetReachableNodes(AstarPath.active.GetNearest(transform.position).node); GraphNode furthestAway = availNodes[availNodes.Count-1];

If you want it including stuff like node weights or taking into account different connection costs between different nodes (like if it is not a grid graph):

ConstantPath p = ConstantPath.Construct (transform.position, 99999999, null); AstarPath.active.StartPath (p); // If you use the beta, you can use AstarPath.active.StartPath (p, true) to bypass the path queue and calculate it directly AstarPath.WaitForPath(p); GraphNode furthestAway = p.nodes[p.nodes.Count-1];

Note that prior to the beta, the ConstantPath approach might actually return node arrays with slightly unsorted nodes, I do not think it should affect the furthest away node, but I am not totally sure.

However, thinking about it, I think the best approach is actually to use the RandomPath (as counterintuitive as it sounds). Because it only stops when it has reached a minimum G-score, if we set that G-score so high that it will never reach it, it will stop at the furthest away node it can find.

RandomPath p = RandomPath.Construct (transform.position, 99999999, null); AstarPath.active.StartPath (p); // If you use the beta, you can use AstarPath.active.StartPath (p, true) to bypass the path queue and calculate it directly AstarPath.WaitForPath(p); GraphNode furthestAway = p.nodes[p.nodes.Count-1];
Looks similar to the ConstantPath approach, but the constant path has to store ALL the nodes it visits, the RandomPath only has to store the path to the furthest away node. So this saves memory and is faster.