Path to always use nearest node

General Point graph
1

Howdy folks. I appear to be missing something simple.
My grid graph allows 8 directions, it hooks up nicely.
For pathfinding, I want it to generate based on closest node by vector distance, and prioritize always walking to closest.
So for example;
A->B directly beside, distance 1
A->C two apart, distance 2
A->D is diagonal, so distance 1.5

I would prefer for it to move A->D instead of A->C due to the way I am using my movement script.
Currently, it is trying to use the fewest points, instead of shortest distance between points.
Imagine 6 nodes in a row, all 1 apart, with a max link distance 2;
C - B - A - B - C

Current pathing outcome: a-c, a-c, a-c.
Looking for: a-b, a-b, a-b, a-b, a-b, a-b
If it cannot find an a-b, then find an a-d. Then if it cant find that, a-c.

I cannot use difficult modifiers because a node may have have another on its left (a-b) but a gap on the right (a-c). Essentially, I need to cost the connections when creating the path, not cost the node.

2

There’s actually a property you can use to set a cost to individual connections, Connection.cost- this might be of some help hopefully?

3

Ok folks, I did it. My map is 2D tile based, and you can add/delete the tiles. It generates the nodes and connects them. Making the pathfinding properly cost the node CONNECTIONS instead of the node ITSELF has been accomplished, code below.
During creation, it checks position, creates nodes. I add the nodes to a list (in this case, about 200). It automatically connects the nodes using the pointmap max distance - just supply a list of vector3/vector3 ints to it. This gets you an incosted list of connected nodes.

foreach (var v in _nodeVecs)
{
    Vector3 _v2 = v; _v2 = new Vector3(_v2.x + 0.55f, _v2.y + 0.55f, _v2.z);
    AstarPath.active.AddWorkItem(() =>
    {
        _pointGraph.maxDistance = 2.1f;
        PointNode node = _pointGraph.AddNode((Int3)_v2);
        _points.Add(node);
        _pointGraph.ConnectNodes();
    });
}

Then, because we need to cost them based on distance, we do below.

public void RedoCosts(List<GraphNode> nodesToRecheck)
{
    foreach (GraphNode nodetoCheck in nodesToRecheck)
    {
        var connections = new List<GraphNode>();
        nodetoCheck.GetConnections(connections.Add);
        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) cost = 1000;
            if (d > 1 && d < 2) cost = 1500;
            if (d >= 2) cost = 3500;
            GraphNode.Disconnect(g1, g2);
            GraphNode.Connect(g1, g2, cost);
        }
    }
}

And with that, we have a nodegraph of 200 nodes, with essentially zero time. When you add or delete nodes, you can use the redo costs for this as well - making for a fully dynamic Point Graph.

1 Like
4

Nicely done, and thanks for sharing your work! Very much appreciated.

1 Like