I have a point graph set up in my scene, I’m wondering how I could go about finding all nodes that are x nodes away. For example, if I were to want to find all nodes 5 nodes away, it would return a list of nodes that are exactly 5 nodes away from the start node.
In my dev version I have added a method for that: PathUtilities.BFS, but until that is released, here’s the code for it
`/** Returns all nodes within a given node-distance from the seed node.
This function performs a BFS (breadth-first-search) or flood fill of the graph and returns all nodes which can be reached from
the seed node. In almost all cases this will be identical to returning all nodes which have the same area as the seed node.
In the editor areas are displayed as different colors of the nodes.
The only case where it will not be so is when there is a one way path from some part of the area to the seed node
but no path from the seed node to that part of the graph.
The returned list is sorted by node distance from the seed node
i.e distance is measured in the number of nodes the shortest path from \a seed to that node would pass through.
Note that the distance measurement does not take heuristics, penalties or tag penalties.
Depending on the number of nodes, this function can take quite some time to calculate
so don’t use it too often or it might affect the framerate of your game.
\param seed The node to start the search from.
\param depth The maximum node-distance from the seed node.
\param tagMask Optional mask for tags. This is a bitmask.
\returns A List containing all nodes reachable from the seed node.
For better memory management the returned list should be pooled, see Pathfinding.Util.ListPool
*/
public static List BFS (GraphNode seed, int depth, int tagMask = -1) { #if ASTAR_PROFILE
System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();
watch.Start (); #endif
List que = Pathfinding.Util.ListPool.Claim ();
List list = Pathfinding.Util.ListPool.Claim ();
/** \todo Pool */
Dictionary<GraphNode,int> map = new Dictionary<GraphNode,int>();
Awesome, thanks a ton! I ended up actually coming up with my algorithm for hex grids, here it is for anyone interested:
//Gets all hexes within a certain range.
public static Point[] GetNodesInRange(Point origin, int range)
{
List selection = new List();
//This algorithm assumes the grid is set up in odd-r offset. The grid I was given was.
//Convert odd-r offset to cube coordinates
Int3 conversion = new Int3(origin.X - (origin.Y - (origin.Y & 1)) / 2, -origin.X - origin.Y, origin.Y);
//Get all hexes within distance N
for (int testX = conversion.x - range; testX <= conversion.x + range; testX ++)
{
for (int testY = conversion.y - range; testY <= conversion.y + range; testY ++)
{
for (int testZ = conversion.z - range; testZ <= conversion.z + range; testZ ++)
{
//If the sum of the deltas is equal to 0 this is within range.
if ((conversion.x - testX) + (conversion.y - testY) + (conversion.z - testZ) == 0)
{
//Convert cube to odd-r offset
Point testPoint = new Point(testX + (testZ - (testZ & 1))/2, testZ);
if (new Vector2(testPoint.X, testPoint.Y) != new Vector2(origin.X, origin.Y))
selection.Add(testPoint);
}
}
}
}
return selection.ToArray();