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.

There are a lot of ways to update a graph and many different scenarios in which you could want to do it. So here is a table summarising the most common cases. Keep in mind that games are very different so some solution might work for your game that isn't in this list.

You want	How to do it
to recalculate the whole graph	See Recalculating the whole graph
to set exactly which nodes are walkable and which are not (e.g based on a tilemap)	See Using direct access to graph data, Utilities for turn-based games and Grid Graph Rules
to update the graph as some objects move around or are created/destroyed	See Recalculating parts of graphs in particular DynamicGridObstacle and Navmesh Cutting
to update the properties of a single node	See Using direct access to graph data, GraphUpdateScene and Grid Graph Rules
to dynamically load and unload graphs (e.g to a file)	See Saving and Loading Graphs
a smaller grid graph to follow the player around (e.g for a procedural world)	See ProceduralGridMover
to create new nodes and connect them using code	See PointGraph.AddNode and Writing Graph Generators
to make a part of the graph more costly to traverse	See Recalculating parts of graphs, Using direct access to graph data, GraphUpdateScene and Grid Graph Rules
to prevent some units from traversing some nodes but allow other units	See Working with tags, Recalculating parts of graphs, GraphUpdateScene, Using direct access to graph data and Grid Graph Rules
pathfinding on a moving object (e.g a ship)	See the example scene called 'Moving' (pro version only). This is not that well documented at the moment.
to add an obstacle, but first make sure that it doesn't block any units (useful in TD games)	See Check for blocking placements

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 on 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.

Recalculating the whole graph

A complete recalculation of all graphs or just a few can be done using

        // Recalculate all graphs
        AstarPath.active.Scan();
        // Recalculate only the first grid graph
        var graphToScan = AstarPath.active.data.gridGraph;
        AstarPath.active.Scan(graphToScan);
        // Recalculate only the first and third graphs
        var graphsToScan = new [] { AstarPath.active.data.graphs[0], AstarPath.active.data.graphs[2] };
        AstarPath.active.Scan(graphsToScan);

You can also recalculate graphs asynchronously (only available in the pro version). This does not guarantee a good frame rate, but you can at least show a loading screen.

    IEnumerator Start () {
        foreach (Progress progress in AstarPath.active.ScanAsync()) {
            Debug.Log("Scanning... " + progress.description + " - " + (progress.progress*100).ToString("0") + "%");
            yield return null;
        }
    }

See also: AstarPath.Scan; AstarPath.ScanAsync

Recalculating parts of graphs

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).

        // As an example, use the bounding box from the attached collider
        Bounds bounds = GetComponent<Collider>().bounds;
        AstarPath.active.UpdateGraphs(bounds);

        // using Pathfinding; //At top of script
        // As an example, use the bounding box from the attached collider
        Bounds bounds = GetComponent<Collider>().bounds;
        var guo = new GraphUpdateObject(bounds);
        // Set some settings
        guo.updatePhysics = true;
        AstarPath.active.UpdateGraphs(guo);

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.

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
        // As an example, use the bounding box from the attached collider
        Bounds bounds = GetComponent<Collider>().bounds;
        var guo = new GraphUpdateObject(bounds);
        // Set some settings
        guo.updatePhysics = true;
        AstarPath.active.UpdateGraphs(guo);

The bounds 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. In the example the bounding box is taken from the attached collider.

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.; Node properties and Pathfinding.GraphNode for information about what properties a node has.; Grid Graph Rules for how to create custom GridGraph rules. If you are using a grid graph, it is often more robust to write a custom grid graph rule.

Here is an example of changing all nodes in a grid graph and using perlin noise to determine if nodes should be walkable:

        AstarPath.active.AddWorkItem(new AstarWorkItem(ctx => {
            var gg = AstarPath.active.data.gridGraph;
            for (int z = 0; z < gg.depth; z++) {
                for (int x = 0; x < gg.width; x++) {
                    var node = gg.GetNode(x, z);
                    // This example uses perlin noise to generate the map
                    node.Walkable = Mathf.PerlinNoise(x * 0.087f, z * 0.087f) > 0.4f;
                }
            }
            // Recalculate all grid connections
            // This is required because we have updated the walkability of some nodes
            gg.GetNodes(node => gg.CalculateConnections((GridNodeBase)node));
            // If you are only updating one or a few nodes you may want to use
            // gg.CalculateConnectionsForCellAndNeighbours only on those nodes instead for performance.
        }));

The above code will generate this graph:

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.AddWorkItem:

        AstarPath.active.AddWorkItem(new AstarWorkItem(() => {
            // Safe to update graphs here
            var node = AstarPath.active.GetNearest(transform.position).node;
            node.Walkable = false;
        }));

        AstarPath.active.AddWorkItem(() => {
            // Safe to update graphs here
            var node = AstarPath.active.GetNearest(transform.position).node;
            node.position = (Int3)transform.position;
        });

When the connectivity of the nodes are changed, the system automatically recalculates the connected components of the graph. You can read more about this in the documentation for this class: Pathfinding.HierarchicalGraph. However in the middle of a sequence of work items, it may not be up to date. If you are using methods such as Pathfinding.PathUtilities.IsPathPossible or the Pathfinding.GraphNode.Area property you should call the ctx.EnsureValidFloodFill method first. Usually this is not something that work items require however.

Version: Prior to 4.2 you had to manually call methods like QueueFloodFill to keep this data up to date. However in 4.2 and above there is no need for that. The system will handle it automatically behind the scenes in a more performant way.

        AstarPath.active.AddWorkItem(new AstarWorkItem((IWorkItemContext ctx) => {
            ctx.EnsureValidFloodFill();
            // The above call guarantees that this method has up to date information about the graph
            if (PathUtilities.IsPathPossible(someNode, someOtherNode)) {
                // Do something
            }
        }));

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. If you are only updating a few nodes you could use the GridGraph.CalculateConnectionsForCellAndNeighbours method to avoid having to iterate through all nodes in the graph and recalculate their connections (which can be slow).

The AddWorkItem method can also be used in more advanced ways. For example it allows you to spread the calculation over multiple frames if necessary:

        AstarPath.active.AddWorkItem(new 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;
        }));

For a list of all different ways of creating a work item, take a look at the constructors for Pathfinding.AstarWorkItem.

Debugging

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 -> Graph Coloring. 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 UnityEngine;
using Pathfinding;
public class MyGUO : GraphUpdateObject {
    public Vector3 offset = Vector3.up;
    public override void Apply (GraphNode 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(goalPoint.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);
        }

Contents