Point Graph: finding all nodes x nodes away?

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.

Is this possible? Help is greatly appreciated!

Anybody know about this? I’ll be needing to figure out a solution one way or another today sometime

Hi

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>();

    int currentDist = 0;
    GraphNodeDelegate callback;
    if (tagMask == -1) {
    callback = delegate (GraphNode node) {
    if (node.Walkable && !map.ContainsKey (node)) {
    map.Add (node, currentDist+1);
    list.Add (node);
    que.Add (node);
    }
    };
    } else {
    callback = delegate (GraphNode node) {
    if (node.Walkable && ((tagMask >> (int)node.Tag) & 0x1) != 0 && !map.ContainsKey (node)) {
    map.Add (node, currentDist+1);
    list.Add (node);
    que.Add (node);
    }
    };
    }

    map[seed] = currentDist;
    callback (seed);

    while (que.Count > 0 && currentDist < depth ) {
    GraphNode n = que[que.Count-1];
    currentDist = map[n];
    que.RemoveAt ( que.Count-1 );
    n.GetConnections (callback);
    }

    Pathfinding.Util.ListPool.Release (que);

    #if ASTAR_PROFILE
    watch.Stop ();
    Debug.Log ((1000*watch.Elapsed.TotalSeconds).ToString(“0.0 ms”));
    #endif
    return list;
    }`

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();

}

Has this now been integrated into the release version and are there any quirks around it?

Hi

It is in my development version, but not in the release version yet I am afraid.