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
5

For anyone updating documentation, I would like to also put in the following info;

If you delete a node, and then flush the system, if you then attempt to delete another node in the same work set, it will give an error indicating that the second node still contains connections. As a best practice for node deletion of multiple nodes in the same sequence, I have written the following;

public void DeleteNode(Vector3 vec3toDelete, bool _flushNow)
{
    GraphNode node1 = AstarPath.active.data.pointGraph.GetNearest(vec3toDelete, null, 0.4f).node;
    PointNode _pointNode = node1 as PointNode;
    var connections = new List<GraphNode>();
    if (node1 != null) node1.GetConnections(connections.Add);
    foreach (var connection in connections)
    {
        PointNode n1 = node1 as PointNode; PointNode n2 = connection as PointNode;
        GraphNode g1 = node1 as GraphNode; GraphNode g2 = connection as GraphNode;
        GraphNode.Disconnect(g1, g2);
    }
    if (node1 != null) { AstarPath.active.AddWorkItem(() => { _pointGraph.RemoveNode(_pointNode); }); }
    if (_flushNow) FlushIt();
}

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

Been slamming my head on the desk trying to figure out why I can delete one node just fine but as soon as a second one comes up, this happens. My best guess is that the nodes are stored as an array (I believe that is stated somewhere in the documentation) and it doesn’t update the entire array before getting to the second node. But that is a completely wild guess. It can also be that since both nodes connect to the same node, the remaining node is stuck in a pending status?
For any troubleshooting by the dev, the setup that works WITHOUT first disconnecting;
2
1 3
First it deletes 2, then it deletes 3, all good. But if I use setup;
1 2
3
It retains the connection from 1-3 and spits back an error and does NOT safely disconnect 1-3. It will still delete 2 and 3, and disconnect 1-2, but it will NOT disconnect 1-3 before deleting.

Hope this helps someone in the future. Or myself given that I solved it by googling my own answer in the end. What a day…

6

Hi

@Rawr_Andres

Thanks for the report.
Would it be possible for you to write the exact code you use and the error message you get?
There are many options in your code, and I can’t quite figure out which ones you use to trigger the error.

7

As they said in the original Jurassic Park; hold on to your butts!
Except with less smoking, because eww.

The world generates point nodes based on distance from the tilemap beneath or above it. It is non-ordered, just creating them all willy nilly and connecting and costing based on distance. If there is a way for me to get you the array ID of the specific node causing issue, let me know.
My setup from that ends up giving me this;

Gob1
Gob1710×341 43.7 KB

NOTE: The game is not running, it is scaled time 0, thats why Goblinna over there isnt moving around. Shouldn’t matter though, because frames still framing.
Now, I create the rope, which then creates, connects, and costs the connections between nodes. We have placement 1;

Gob3
Gob3729×340 55.5 KB

And placement 2;
Gob2
Gob2875×390 65 KB

You can see that the single rope is creating a node on itself and a node above it.
Now, if I delete the rope from placement 1, it disconnects and turns back to original picture, without needing the disconnection. The kicker code is as follows and is the same for both executions. Its not really important how we got here, just that it will possibly delete 1 node, possibly both nodes, possibly neither. In the scenario above, it qualifies as deleting BOTH the above node and below node. Without the disconnection checker, it has no problem with placement 1. It WILL fail on placement 2.

public void NodeFlareRopeUnBuild(Vector3 _vec3, bool _ropeAbove, bool _ropeAboveAbove, bool _ropedownbuilt, bool _tiledown1, bool _tiledown2)
{
    _vec3.x = _vec3.x + 0.05f; _vec3.y = _vec3.y + 0.05f; GraphNode nodeMe = AstarPath.active.data.pointGraph.GetNearest(_vec3, null, 0.4f).node;
    Vector3 _vUp = new Vector3(_vec3.x, _vec3.y + 1.0f, _vec3.z); GraphNode nodeUp = AstarPath.active.data.pointGraph.GetNearest(_vUp, null, 0.4f).node;
    Vector3 _vUpUp = new Vector3(_vec3.x, _vec3.y + 2.0f, _vec3.z); GraphNode nopeUpUp = AstarPath.active.data.pointGraph.GetNearest(_vUpUp, null, 0.4f).node;
    if (!_ropeAboveAbove && !_ropeAbove) { if (_vUpUp != null) DeleteNode(_vUpUp, false, true); }
    if (!_ropeAbove && !_tiledown1) { if (_vUp != null) DeleteNode(_vUp, false, true); } bool _deleted = false;
    if (_tiledown1 && !_ropedownbuilt) { if (nodeMe != null) DeleteNode(_vec3, false, true); _deleted = true; }
    if (!_tiledown2 && !_ropedownbuilt && !_deleted) { if (nodeMe != null) DeleteNode(_vec3, false, true); }
    FlushIt();

Then it proceeds to move on to grabbing nodes in the area and costing them - after flushing the deleted nodes (and therefore severing connections). The error occurs before it gets to the flush.
What you can see from my code is that the deletions happen sequentially - add deletion work, either flush or dont, add deletion work, either flush or dont, then after all deletions, guaranteed flush.
The code with checker - shifting is just to check if the node being found is on the tilemap axis or the rope axis, so shifting to the 0.5 instead of int 0.

public void DeleteNode(Vector3 vec3toDelete, bool _flushNow, bool _alreadyShifted)
{
    if (!_alreadyShifted) vec3toDelete = new Vector3(vec3toDelete.x + 0.55f, vec3toDelete.y + 0.55f);
    GraphNode node1 = AstarPath.active.data.pointGraph.GetNearest(vec3toDelete, null, 0.4f).node;
    PointNode _pointNode = node1 as PointNode;
    var connections = new List<GraphNode>();
    if (node1 != null) node1.GetConnections(connections.Add);
    foreach (var connection in connections)
    {
        PointNode n1 = node1 as PointNode; PointNode n2 = connection as PointNode;
        GraphNode g1 = node1 as GraphNode; GraphNode g2 = connection as GraphNode;
        GraphNode.Disconnect(g1, g2);
    }
    if (node1 != null) { AstarPath.active.AddWorkItem(() => { _pointGraph.RemoveNode(_pointNode); }); }
    if (_flushNow) FlushIt();
}

Still with me? Ok cool! If you DO NOT HAVE THE DISCONNECTION, placement 1 disconnects perfectly, both nodes are deleted, everyone is happy. Regardless of if I flush after each, or flush only on finale.
If you dont have it and placement 2 occurs;
Gob4
Gob5

nvalidOperationException: A node in a PointGraph contained a connection to a destroyed PointNode.
Pathfinding.HierarchicalGraph+JobRecalculateComponents+<>c.<FindHierarchicalNodeChildren>b__12_0 (Pathfinding.GraphNode neighbour, Pathfinding.HierarchicalGraph+JobRecalculateComponents+Context& context) (at ./Packages/com.arongranberg.astar/Core/Pathfinding/HierarchicalGraph.cs:413)
Pathfinding.PointNode.GetConnections[T] (Pathfinding.GraphNode+GetConnectionsWithData`1[T] action, T& data, System.Int32 connectionFilter) (at ./Packages/com.arongranberg.astar/Graphs/Nodes/PointNode.cs:83)
Pathfinding.HierarchicalGraph+JobRecalculateComponents.FindHierarchicalNodeChildren (Pathfinding.HierarchicalGraph hGraph, System.Int32 hierarchicalNode, Pathfinding.GraphNode startNode) (at ./Packages/com.arongranberg.astar/Core/Pathfinding/HierarchicalGraph.cs:415)
Pathfinding.HierarchicalGraph+JobRecalculateComponents.Execute () (at ./Packages/com.arongranberg.astar/Core/Pathfinding/HierarchicalGraph.cs:510)
Unity.Jobs.IJobExtensions+JobStruct`1[T].Execute (T& data, System.IntPtr additionalPtr, System.IntPtr bufferRangePatchData, Unity.Jobs.LowLevel.Unsafe.JobRanges& ranges, System.Int32 jobIndex) (at <e509afeff7384f24a8f0ac30527ff01c>:0)

This is the part of the delete node that allows it to delete without the cute little arm of failure for placement 2, but is bafflingly unnecessary for placement 1.

 var connections = new List<GraphNode>();
    if (node1 != null) node1.GetConnections(connections.Add);
    foreach (var connection in connections)
    {
        PointNode n1 = node1 as PointNode; PointNode n2 = connection as PointNode;
        GraphNode g1 = node1 as GraphNode; GraphNode g2 = connection as GraphNode;
        GraphNode.Disconnect(g1, g2);
    }