Graph Updates during Runtime

Contents

• Overview
• What to update
• Using Scripting
  • Using direct access to graph data
• Viewing the results of updates
• Technical Details
  • GridGraph specific details
  • Navmesh based graphs
  • PointGraphs
• The Graph Update Object
• Check for blocking placements

Overview

Sometimes it can be necessary to update a graph during runtime. Maybe a player has constructed a new building or maybe a door has been opened. Graphs can either be completely recalculated or partially updated. A complete recalculation is good if you have changed your whole map but smaller updates can be done much faster if you have only need to change a small part of the graph.

A complete recalculation of all graphs can be done using

AstarPath.active.Scan();

Smaller graph updates can either be done using the GraphUpdateScene component which can be edited in the Unity inspector or using scripting which is done by calling a method in the AstarPath class with either a Bounds object or a Pathfinding.GraphUpdateObject (which is what the GraphUpdateScene component actually does in the background).

AstarPath.active.UpdateGraphs (myBounds);
AstarPath.active.UpdateGraphs (myGraphUpdateObject);

The method will then put the task in a queue to be carried out before the next path calculation. It has to be put in a queue because if it carried out directly, it might interfere with pathfinding, especially if multithreading is on, and cause all kinds of errors. This means that you might not see an update of the graph directly, but it will always be updated before the next pathfinding calculation starts (almost always, see AstarPath.limitGraphUpdates ).

Recast graphs can also be pseudo-updated using navmesh cutting. Navmesh cutting can cut out holes for obstacles in the navmesh, but cannot add more navmesh surface. See Pathfinding.NavmeshCut. This is much faster, but more limited than recalculating a whole recast tile.

Using the GraphUpdateScene component is usually easiest if you are working in the Unity Editor on a known graph. For example you can easily change the tag of a specific region without any code. However updating the graph using code is usually easier if you are doing it dynamically during runtime. For example if you are updating the graph to account for a newly placed building in a tower defence game.

What to update

When updating graphs, one usually wants to accomplish one of two things.

You might want to recalculate the graph with the same settings as it was calculated with when it was initially generated, but if you have only updated the graph in a small region, it seems wasteful to recalculate the whole graph (using AstarPath.Scan). For example the player might just have placed a new tower in a tower defence game.

Or you might want to change some settings on the existing graph. For example you might want to change the tag or penalty or some nodes.

To just recalculate a small part of the graph in the same way as it was calculated at the start can be done for all graphs except the NavMeshGraph since it usually only make sense to completely recalculate it. The way you do this using both scripting and the GraphUpdateScene component is that you set the field called "updatePhysics" to true. It might not be the most descriptive name, sorry about that.

Grid graphs will work as you expect, you can just specify the bounds and it will do everything for you. It may however recalculate a region which is slightly larger than the one you specified in order to make sure things like erosion are correctly taken into account.

Recast graphs can only be recalculated a whole tile at a time. So when a request is made to update it, all tiles which the bounds touches will be completely recalculated. Therefore it can be good to use a smaller tile size to avoid very large recalculation times. However not too small since then it essentially degenerates into a grid graph. If you use multithreading a large part of the tile recalculation will however be offloaded to a separate thread to avoid impacting the FPS too much.

Point graphs will recalculate all connections that passes through the bounds. It will however not look for new nodes that are added as GameObjects. For that you need to use AstarPath.Scan.

If you want to change properties on the exiting graph there are a bunch of things you can change.

You can change the tags on the nodes. This can be used to enable some units to traverse a region while preventing other units from doing that. You can read more about tagging here: Working with tags.

You can change the penalty on the nodes. This is used to make some nodes harder/slower to traverse compared the other nodes so that an agent will prefer some paths before others. There are some limitations though. You cannot specify negative penalties since the algorithms used cannot handle that (and if they could, the system would be a lot slower). However a common trick is to set a very large initial penalty (which can be done in the graph settings) and then decrease the penalty from that high value. Note however that this will make pathfinding slower overall since it has to search more nodes. The penalty values that are required are quite high. There is no real "penalty unit" however a penalty of 1000 corresponds roughly to one world unit of travel.

Walkability of the nodes can also be modified directly. So you can make all nodes within some bounds be all walkable or all unwalkable.

For information about how to use the GraphUpdateScene component . See the docs for that class. The GraphUpdateScene component settings map almost 1 to 1 to the GraphUpdateObject which is used when updating graphs using scripting. So I recommend that you read that page even though you are only going to use scripting.

Using Scripting

To update a graph you create a GraphUpdateObject and set the parameters you want, then you call the AstarPath.UpdateGraphs method to queue the update.

// using Pathfinding; //At top of script

var guo = new GraphUpdateObject(myBounds);
// Set some settings
guo.updatePhysics = true;
AstarPath.active.UpdateGraphs (guo);

The myBounds variable referred to is a UnityEngine.Bounds object. It defines an axis aligned box in which to update the graphs in. Often you want to update the graph around some newly created object. If that object has a collider you can easily do

var guo = new GraphUpdateObject(GetComponent<Collider>().bounds); 

However make sure that this object will be recognised by the graph. For grid graphs you should make sure that the object's layer is included in either the collision testing mask or the height teting mask.

If you don't need to recalculate all parameters on the nodes when using a grid graph or connections when using a point graph, you can set updatePhysics (see GridGraph specific details) to false to avoid unnecessary calculations

guo.updatePhysics = false; 

For details about exactly what fields to set, take a look at the class documentation for the GraphUpdateObject .

Using direct access to graph data

In some cases it might be inconvenient to use a GraphUpdateObject to update the graph. In those cases you can update the graph data directly. However care needs to be taken. When using the GraphUpdateObject the system takes care of a lot of things for you.

See Also

Accessing graph data for information about how to access graph data

Graph data must only be modified when it is safe to do so. Pathfinding might be running at any time so it is necessary to first pause the pathfinding threads and then update the data. The easiest way to do this is to use AstarPath.RegisterSafeUpdate however using AstarPath.AddWorkItem instead gives you more flexibility and can be more performant (see details later).

AstarPath.RegisterSafeUpdate (() => {
    // Safe to modify graph data here
});

Some care needs to be taken to make sure that the pathfinding data is up to date after you have changed it. If you have changed the walkability or connections of any node, you need to call AstarPath.FloodFill in order to recalculate what nodes are reachable from what other nodes (this is used to quickly determine if a path is possible or not).

If you are modifying walkability you also need to make sure that connections are recalculated properly. This is important mostly for the grid graph. You can use the GridGraph.CalculateConnections method. Note that this needs to be called both on the node you changed walkability on and also the nodes adjacent to it since they might have to change their connections to add or remove that node as a connection.

To get a safe callback to modify graph data you can instead of the RegisterSafeUpdate method use the AddWorkItem method. It allows you to spread the calculation over multiple frames if necessary and it also allows you to batch the FloodFill calls so that multiple graph updates which are executed directly after each other do not have to run the FloodFill more than once. This is done by calling the AstarPath.QueueWorkItemFloodFill method. The flood fill will then be done after all work items have been completed.

AstarPath.AddWorkItem (new AstarPath.AstarWorkItem (
() => {
    // Called once, right before the
    // first call to the method below
},
force => {
    // Called every frame until complete
    // Signal that the work item is
    // complete by returning true.
    // The "force" parameter will
    // be true if the work item is
    // required to complete immediately.
    // In that case this method should
    // block and return true when done.
    return true;
}
));

Viewing the results of updates

While some things like walkability and position are immediately visible changes. Tags and penalties are not directly visible on the graph. However there are other viewing modes that can be enabled to visualize both tags and penalties.

The viewing mode can be edited at A* Inspector -> Settings -> Debug -> Path Debug Mode. If you set it to "Tags" all tags will be visible as different colors on the graph.

You can also set it to show penalties. By default it will automatically adjust itself so that the node(s) with the highest penalty will show up as pure red and the node(s) with the lowest penalty will show up as green.

Technical Details

When updating is carried out using a GraphUpdateObject, all graphs will be looped over and those which can be updated (all built in ones) will have their UpdateArea function called (i.e be updated).
Each node is updated by the graphs calling Pathfinding.GraphUpdateObject.Apply sending each affected node to it, the Apply function will then change penalty, walkability or other parameters specified. Graphs can also use custom updating logic, such as the GridGraph (see GridGraph specific details). You do not have to understand all different function calls to be able to use it, those are mostly for people who want to mess around with the source code.

GridGraph specific details

The updatePhysics variable matters a lot when updating grid graphs. If it is set to true, all nodes affected will have their height recalculated and then checked if they are still walkable. You usually want to leave this to true when updating a grid graph.

When updating a GridGraph, the GraphUpdateObject's Apply function (which changed walkability, tags and penalties) will be called for each node inside the bounds, it will check the updatePhysics variable, if it is true (which is the default value), the area will be expanded by the diameter of the specified in the Collision Testing settings and every node inside the area will be checked for collisions. If it is false, however, only the Apply function will be called for the nodes inside the area (not expanded) and nothing else will be done.

Navmesh based graphs

Navmesh based graphs (NavMeshGraph and RecastGraph) only have support for updating penalty, walkability and similar on already existing nodes or for recast graphs, to completely recalculate whole tiles. New nodes cannot be created using GraphUpdateObjects (unless recalculating whole tiles). The GraphUpdateObject will affect all nodes/triangles which intersect or are contained by the GUO's bounds.

For recast graphs you can also use navmesh cutting to update the graph in a fast way.

PointGraphs

Point graphs will call Apply on every node inside the bounds. If GraphUpdateObject.updatePhysics is set to true (default true) it will also recalculate all connections which passes through the bounds object.

Note

Updating Point graphs is only available in the pro version of the A* Pathfinding Project.

A* Pro Feature:

This is an A* Pathfinding Project Pro feature only. This function/class/variable might not exist in the Free version of the A* Pathfinding Project or the functionality might be limited
The Pro version can be bought here

The Graph Update Object

The GraphUpdateObject contains some basic variables on how to update each node. See documentation for the Pathfinding.GraphUpdateObject for more info.

Inheriting from the GraphUpdateObject

Classes can inherit from the GraphUpdateObject to override some functionality.
Here's an example of a GraphUpdateObject which moves nodes by some offset while still keeping the base functionality.

using Pathfinding;

public class MyGUO : GraphUpdateObject {
    public Vector3 offset = Vector3.up;
    public override Apply (Node node) {
        // Keep the base functionality
        base.Apply (node);
        // The position of a node is an Int3, so we need to cast the offset
        node.position += (Int3)offset;
    }
}

You could then use that GUO like this:

 public void Start () {
    MyGUO guo = new MyGUO ();
    guo.offset = Vector3.up*2;
    guo.bounds = new Bounds (Vector3.zero,Vector3.one*10);
    AstarPath.active.UpdateGraphs (guo);
}

Check for blocking placements

A common thing in tower defence games is to make sure that the towers the player places does not block the path between the spawn points and the goal. This might seem hard to do, but luckily there is an API for that.

The Pathfinding.GraphUpdateUtilities.UpdateGraphsNoBlock method can be used to first check if a given graph update object will cause the path between two or more points to become blocked. This is however slower than a normal graph update so you probably don't want to use it too often.

For example when a player in a tower defence game places a tower, you could instantiate it, then call the UpdateGraphsNoBlock method to check if the newly placed tower will block the path. If it did then remove the tower immediately and notify the player that the choosen position was not valid. You can pass a list of nodes to the UpdateGraphsNoBlock method so you could for example make sure that not only is the path from the start to the goal not blocked, but also that all units can still reach the goal (if it is possible to place towers when enemies are walking around).

var guo = new GraphUpdateObject (tower.GetComponent<Collider>.bounds);
var spawnPointNode = AstarPath.active.GetNearest (spawnPoint.position).node;
var goalNode = AstarPath.active.GetNearest (goalNode.position).node;
if (GraphUpdateUtilities.UpdateGraphsNoBlock (guo, spawnPointNode, goalNode, false)) {
    // Valid tower position
    // Since the last parameter (which is called "alwaysRevert") in the method call was false
    // The graph is now updated and the game can just continue
} else {
    // Invalid tower position. It blocks the path between the spawn point and the goal
    // The effect on the graph has been reverted
    Destroy (tower);
}