Fast method to connect multiple nodes

General Point graph
1

I have a point graph with 500 nodes, and I want to add 30 new nodes and connect them to each other and to existing graph.

Is there a fast method to do it?

I found that AstarPath.active.UpdateGraphs(bounds) is too slow for this. pointGraph.ConnectNodes() is also slow even with lookup tree. Because ConnectNodes iterates over all graph nodes. But I need to iterate over my newly added 30 nodes with all (limited by maxDistance).

it would be nice to have a method ConnectNodes(PointNode[ ] nodesForConnection)

2

How often are you adding these 30 new nodes? I also recommend taking a look at this page on optimization and see if anything here may be of use.

3

Oooooooh baby do I have some code for YOU! To be fair I only have 200 nodes and they only connect to things within 2.1 range of each other, but adding/deleting nodes takes zero noticable time.

List<GraphNode> nodesToRecheck = new List<GraphNode>();
Vector3Int _gridStartPosition = new Vector3Int(_vec3Int.x - 4, _vec3Int.z + 4, _vec3Int.z); Vector3Int _gridEndPosition = new Vector3Int(_vec3Int.x + 4, _vec3Int.y - 4, _vec3Int.z);
BoundsInt _nodeZone = new BoundsInt(
    Math.Min(_gridStartPosition.x, _gridEndPosition.x),
    Math.Min(_gridStartPosition.y, _gridEndPosition.y),
    Math.Min(_gridStartPosition.z, _gridEndPosition.z),
    Math.Abs(_gridEndPosition.x - _gridStartPosition.x) + 1,
    Math.Abs(_gridEndPosition.y - _gridStartPosition.y) + 1,
    Math.Abs(_gridEndPosition.z - _gridStartPosition.z) + 1
    );
foreach (var v in _nodeZone.allPositionsWithin)
{
    Vector3 _v3 = new Vector3(v.x + 0.55f, v.y + 0.55f, v.z);
    GraphNode nodev = AstarPath.active.data.pointGraph.GetNearest(_v3, null, 0.4f).node;
    PointNode _pointNodev = nodev as PointNode;
    if (_pointNodev != null) { if (!nodesToRecheck.Contains(_pointNodev)) nodesToRecheck.Add(_pointNodev); }
}
RedoCosts(nodesToRecheck);

public void RedoCosts(List<GraphNode> nodesToRecheck)
{
    //Debug.Log("Redoing " + nodesToRecheck.Count);
    foreach (GraphNode nodetoCheck in nodesToRecheck)
    {
        Vector3 _vec3 = (Vector3)nodetoCheck.position;
        Vector3Int _vec3Int = new Vector3Int(Mathf.FloorToInt(_vec3.x), Mathf.FloorToInt(_vec3.y), Mathf.FloorToInt(_vec3.z));
        Vector3Int _gridStartPosition = new Vector3Int(_vec3Int.x - 4, _vec3Int.z + 4, _vec3Int.z); Vector3Int _gridEndPosition = new Vector3Int(_vec3Int.x + 4, _vec3Int.y - 4, _vec3Int.z);
        BoundsInt _nodeZone = new BoundsInt(
        Math.Min(_gridStartPosition.x, _gridEndPosition.x),
        Math.Min(_gridStartPosition.y, _gridEndPosition.y),
        Math.Min(_gridStartPosition.z, _gridEndPosition.z),
        Math.Abs(_gridEndPosition.x - _gridStartPosition.x) + 1,
        Math.Abs(_gridEndPosition.y - _gridStartPosition.y) + 1,
        Math.Abs(_gridEndPosition.z - _gridStartPosition.z) + 1
        );
        var connections = new List<GraphNode>();
        foreach (var v in _nodeZone.allPositionsWithin)
        {
            Vector3 _v3 = new Vector3(v.x + 0.55f, v.y + 0.55f, v.z);
            GraphNode node1 = AstarPath.active.data.pointGraph.GetNearest(_v3, null, 0.4f).node;
            PointNode _pointNode = node1 as PointNode;
            if (node1 != null)
            {
                if (!connections.Contains(_pointNode)) { connections.Add(_pointNode); /*Debug.Log("Adding node at " + _pointNode.position);*/ }
            }
        }
        foreach (var connection in connections)
        {
            PointNode n1 = nodetoCheck as PointNode; PointNode n2 = connection as PointNode;
            GraphNode g1 = nodetoCheck as GraphNode; GraphNode g2 = connection as GraphNode;
            Vector3 nv1 = (Vector3)n1.position; Vector3 nv2 = (Vector3)n2.position;
            float d = Vector3.Distance(nv1, nv2);
            var cost = (uint)d;
            if (d <= 1.1f) cost = 1000;
            if (d > 1.1f && d < 2) cost = 2500;
            if (d >= 2) cost = 5500;
            //GraphNode.Disconnect(g1, g2);
            if (d <= 2) GraphNode.Connect(g1, g2, cost, OffMeshLinks.Directionality.TwoWay);
        }
    }
    FlushIt();

public void FlushIt()
{
    AstarPath.active.FlushWorkItems();
    AstarPath.active.FlushGraphUpdates();
}
4

thanks for examples. I also wrote my own solution based on pointGraph.ConnectNodes(). I need to add nodes not too often, but this operation shouldn’t make spikes on the main thread.
I wrote my post to make sure that the library doesn’t have a fast method out of the box.

5

Ahh, gotcha. Yeah I don’t think there’s anything particularly built-in for this use case. Sorry about that!

I great appreciate this contribution, btw, as well as the energy behind it :joy:

6

I want better games, don’t we all? Hording code is for Ubisoft :slight_smile:

1 Like
7

Contribution is absolutely king, agreed! :smiley: