Support Forum

Is there a function like BFS that would collect all the nodes in a list with a hurdle?

Hello everyone.
I’ll start from afar. I made a dialogue system and I’m trying to simulate a situation when a character is standing behind a fence. Accordingly, you can not approach him, but you can talk.
I’m using the BFS feature to find path endpoints for squad members. Now I have learned to code a little and I want to make the moment with the dialogue a little easier.
I want to find all nodes at a certain distance from an object and put them in a list. Then, as needed, discard all nodes with obstacles from the list and discard all nodes with a tag. Then a simple search to find the nearest node.
I learned how to find the nearest point from the list, and I also know how to remove nodes with tags from the list.
How to do the rest?

if I’m understanding this right, these should be the steps:

  1. find the nearest node using AstarPath.active.GetNearest(character.transform.position) or a similar function
  2. add all of the nodes next to it to a queue
  3. repeatedly remove the next node from the queue and check if it has already been checked
    • if it has already been checked, skip them
      3a. if the node hasn’t already been checked, then check its’ distance
      • if it isn’t far enough away yet, add its connected nodes to the queue and add it to the checked set
      • if it is far enough away, add them to a list of the possible nodes if untagged and unobstructed
      • if it is too far away, skip them
  4. after repeating steps 3 and 3a enough, you now have a list of valid nodes

tentative (untested) solution code:

var charPos = character.transform.position;
GraphNode startNode = AstarPath.active.GetNearest(charPos)
var connections = new Queue<GraphNode>();
startNode.GetConnections(connections.Enqueue);
var nodes = new List<GraphNode>();
var checkedNodes =  new HashSet<GraphNode>();
while (connections.Count > 0) {
    //remove a node from the queue
    var node = connections.Dequeue();
    //if we already looked at this node, don't check it again
    if(checkedNodes.contains(node)) continue;
    //record that we have now checked this node
    else checkedNodes.Add(node);
    
    //get the distance between the character and the node's center
    var dist = Vector3.Distance(charPos, (Vector3)node.position);
    //if too far away, don't do anything with it
    if(dist > maxDistance) continue;
    //if it's within the acceptable distance it's a potential valid node
    else if(dist <= maxDistance && dist >= minDistance) {
        //if tagged or contains a obstacle, don't bother with it
        if(node.tag != 0 || !node.walkable) continue;
        //otherwise this is a valid node
        nodes.Add(node);
    }
    //if this node is too close,
    //add all of the connected nodes to connections to be checked later
    else node.GetConnections(connections.Enqueue);
}
//nodes is now your list of nodes within the proper distance

@ConfusedIntern The logic seems to be correct but doesn’t work. I compared your code and mine with the BFS function and recorded a video. Under these conditions, they should give approximately the same result. But they don’t give out.

var poziciyaTchk = AstarPath.active.GetNearest(navelsya.transform.position, NNConstraint.None).node;
List<GraphNode> areaaTchk = new List<GraphNode>();
areaaTchk = PathUtilities.BFS(poziciyaTchk, nygnoeRasstoyanie).Where(node => node.Tag != KeshPriStart.tagMaskZone3).ToList();

This is my code. And this is a video.
https://youtu.be/MNb3WkoFGlg

The lists store a different number of nodes.Why is that?

I still don’t know the library well and don’t know many keywords from the library. So I have no idea why this is so.

Am I correct in that you want to find all nodes within a certain distance, without taking into account obstacles at all in the distance calculation. And then you want to filter out obstacle nodes from that list?

Yes, that is right.
BFS works like water. And this method should form a slightly different list.

But in the script above, if it worked, it seems that there is a way to filter the gap between the character and the fence.

else if(dist <= maxDistance && dist >= minDistance)

It would be great if it could be. For example, the NPC is in a cage. In general, a huge scope for the imagination.

That is, I launch BFS from the character who is in the cage, and not the one who walks.

You may want to use GridGraph.GetNodesInRegion (or one of the other overloads of that function)

1 Like

Thank you, I was able to finish this function. Used the hint from this thread. BFS walkability constraint
That’s what I did.

  public void navedenieVersusIunitRS2()
    {
        var navelsya = OfAttack.cellVrag;
        var samPers = TextSceny.PersonagTextStatic.teloPersonaga;
        GridGraph GG = AstarPath.active.data.gridGraph;
        GridNode centerNode = GG.GetNearest(navelsya.transform.position, NNConstraint.None).node as GridNode;
        int width = nygnoeRasstoyanie;
        List<GraphNode> nodes = GG.GetNodesInRegion(new IntRect(centerNode.XCoordinateInGrid - width, centerNode.ZCoordinateInGrid - width,
            centerNode.XCoordinateInGrid + width, centerNode.ZCoordinateInGrid + width)).Where(node => node.Tag != KeshPriStart.tagMaskZone3).Where(node => node.Walkable == true).ToList();
        if (nodes.Count == 0)
        {
            print("red");
            width = nygnoeRasstoyanie * 2;
            nodes = GG.GetNodesInRegion(new IntRect(centerNode.XCoordinateInGrid - width, centerNode.ZCoordinateInGrid - width,
           centerNode.XCoordinateInGrid + width, centerNode.ZCoordinateInGrid + width)).Where(node => node.Tag != KeshPriStart.tagMaskZone3).Where(node => node.Walkable == true).ToList();
        }
        float DistanceToPlayer = 5000;
        int NearestObject = 0;
        for (int i = 0; i < nodes.Count; i++)
        {
            // float  DistanceToPlayer3 = Vector3.Distance((Vector3)areaaTchk[i].position, samPers.transform.position);
            Vector3 prom = (Vector3)nodes[i].position - samPers.transform.position;
            float DistanceToPlayer2 = prom.sqrMagnitude;
            //print(DistanceToPlayer3 + "  " + DistanceToPlayer2 + "   " + i);
            if (DistanceToPlayer2 < DistanceToPlayer)
            {
                DistanceToPlayer = DistanceToPlayer2;
                NearestObject = i;
            }

        }
        tochkaYdara = (Vector3)nodes[NearestObject].position;
       // print(nodes.Count);
    }

@aron_granberg Let’s make my game together. On kickstarter, it remains only to draw the interface and a few pictures of the characters, the demo version will be ready. Then more people could be recruited. There is very little programming left.

1 Like