Support Forum

[Solved] BFS adding additional points outside of maxDepth

Unity Version: 2020.01.2f1
AStar: 4.2.15
While using List<GraphNode> reachableNodes = PathUtilities.BFS(node, distance); It seems to add an extra node or two that it should not when scanning. Here is an example of what I am seeing: image

The extra tile is marked with a red circle.

A second example moving the unit down 1 tile and showing the extra tile extended off the end of the max range. image

This is the full code I am using.

public class ShowMoveableGrid : MonoBehaviour
    public GameObject thing; // Holds prefab
    public GameObject thingHolder; // Parent for prefabs for tracking

    public BlockManager blockManager;
    private BlockManager.TraversalProvider traversalProvider;

    public void UpdateUsingCurrentPos(int distance, Transform _transform, List<SingleNodeBlocker> obstacles)
        GraphNode node =;
        traversalProvider = new BlockManager.TraversalProvider(blockManager, BlockManager.BlockMode.OnlySelector, obstacles);
        List<GraphNode> reachableNodes = PathUtilities.BFS(node, distance);
        foreach (GraphNode nodeToSpawn in reachableNodes)
            Vector3 ourPos = (Vector3)node.position;
            Vector3 newPos = (Vector3)nodeToSpawn.position;
            Path path = ABPath.Construct(ourPos, newPos, null);

            // Make the path use a specific traversal provider
            path.traversalProvider = traversalProvider;

            // Calculate the path synchronously
            if (!traversalProvider.CanTraverse(path, nodeToSpawn))
            if (path.GetTotalLength() < distance)
                var v3 = (Vector3)nodeToSpawn.position;
                Instantiate(thing, v3, Quaternion.identity, thingHolder.transform);


Not quite sure what’s going on there, but you might want to log what distances you get from the path calculation. Keep in mind that the path calculation may include diagonals (if your grid graph is configured that way) and thus GetTotalLength may not be an integer. You might want to use path.path.Count instead.

Looks like moving to path.path.count resolved my issue. My graph is not configured for diagonals so its a bit strange that it produces a few extra tiles as an edge case.

Its funny because I had path.path.Count in there originally but to me it is a bit ugly and GetTotalLength seemed to have the same behavior…

Thanks for the help!

1 Like