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

General Grid graph
1

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?

2

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
3

@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.

4

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?

5

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

6

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.

7

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

1 Like
8

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