Gridgraph, GUO UpdateGraphs, Recalculate existing paths

#1

I am trying to write a Tower Defence game. One issue I am having is that when a new tower is placed, only newly created creeps respect it. The creeps are using an Alternate-path Script to avoid them all taking exactly the same path.

Making creeps recalculate path every half second results in erratic behavior, including indecisive turning around repeatedly, and choppy movement, or surging forward a small but visible amount. Not doing it at all results in them phasing through walls.

Not really sure how to resolve this. I was going to make a tower placement/sale result in all paths being recalculated, but that would probably do something similar.

I would like them to only recalculate if a new path would be significantly faster, or else the old path isn’t physically possible. That is, if a shortcut opened up that cuts the total path distance by x, or the old path goes through areas of the graph that have been disabled.

Not really sure how to do this however.

#2

Hi

You can regularly check if the creep will soon pass through a wall. Eg by checking for a few points ahead in the path if

if (!AstarPath.active.GetNearest(point, NNConstraint.None).node.Walkable) {
    // Would pass unwalkable node, might be a good idea to request a new path
}
#3

Could you explain that to me? Looking at it, it only looks like it would check the closest node to the entity, rather than looking at the next node.

#4

That depends on what point is. You can even use multiple of them.

I am not sure which movement script you are using or which version you are using, but if you are using 3.8.x and the AIPath movement script you could try something like this:

for (int i = currentWaypoint; i < Mathf.Min(path.vectorPath.Count - 1, currentWaypoint + 4); i++) {
     if (!AstarPath.active.GetNearest(path.vectorPath[i], NNConstraint.None).node.Walkable) {
        // Would pass unwalkable node, might be a good idea to request a new path
    }
}

If I remember correctly the AIPath script has a variable called ‘currentWaypoint’ which indicates the waypoint it is currently moving towards. I haven’t tested the code myself, but that’s the gist of it.

#5

Using AILerp currently. Not sure how to get the path, but ABPath.vectorPath is an array (or Array-like object) that returns all the grid-graph points it will visit on the current path, right? So I loop all the points on that path, and if any are now invalid, I can tell it to update the path.

Does the path remove points it visits? I don’t want it to recalculate if you cover a point it already passed with a new tower.

protected int currentWaypointIndex = 0;

Presumably this is the point that it most recently visited, so start at this point, don’t calculate it, but do the next one until the last one. I think.

#6

Basically.

No, that’s why you should start at currentWaypointIndex. That’s the index of the point it is currently moving towards (it hasn’t reached it yet).

#7

I think I have another problem, but its hard to say

I think what is happening is that the graph isn’t updated yet, which means the new tower gets ignored. I am not really sure however, since I don’t actually know how UpdateGraphs and FlushGraphUpdates works. I though flush forced it to happen immediately, but if it is a soon-as-possible instead, I need to somehow wait for that to finish, I think.

Also getting this warning
“Penalty for some nodes has been reset while this modifier was active. Penalties might not be correctly set.”

In Tower (Called after tower is created, or when it is destroyed, and collider is disabled)

private void UpdatePathing()
{

    GraphUpdateObject guo = new GraphUpdateObject(GetComponent<Collider>().bounds);
    
    AstarPath.active.UpdateGraphs(guo, 0.0f);
    //Pathfinding.Console.Write ("// Flushing\n");
    AstarPath.active.FlushGraphUpdates();
    
    Creep.RefreshPathing();
}

in Creep

public static void RefreshPathing()
{
    foreach (Creep creep in EntityManager.GetCreeps())
    {
        //if (!creep.lerp.isPathValid())
        {
            creep.lerp.SearchPath();
        }
    }
}
#8

the “Surge” of speed is caused by Path Switch Interpolation. Setting the speed to match the normal speed mostly fixes it, even if the path it takes can be a bit wierd.

Adding a delay of 0.1f seconds before relcalculating the path appears to work. It shows the old path for a split second, then choses a new path, which hasn’t passed over a tower yet.

Hopefully more issues won’t show up.