By Aron Granberg

A* Pathfinding Project 4.0 Update

Version 4 of the A* Pathfinding Project has just been released! I have been working on this update for quite some time and now that it is finally released I thought I’d take this post to list the most notable improvements in this new version. This is not an exhaustive list, you can find more changes in the changelog.

Huge performance improvements for Recast graphs

New algorithms and optimization of the existing ones makes scanning and updating recast graphs significantly faster. The scan is now fully multi-threaded and it handles large worlds with lots of objects much better.
Speedups range from 2x to over 1000x with around 5x being the most common for small to medium sized worlds. The larger the world and the more cores your computer has, the greater the speedup. The 1000x+ speedup was observed when scanning a several square kilometer world (used in a real game). If your game has a procedural world and you use a recast graph to scan it when the game starts, this should improve your game’s startup times significantly.

If you use a large number of navmesh cuts you should also get a noticeable speed boost.

Object pooling is used in more places which reduces the number of allocations. This is particularly important when recalculating tiles or using navmesh cutting during runtime.

Improved graph rendering

Graph rendering has undergone a massive overhaul to both improve the style of them as well as improve the performance.
In 3.x graph rendering used Unity’s Gizmo system which, while nice, requires the rendered lines and surfaces to be recalculated every frame. To improve upon this a custom persistent line and surface drawing system has been developed which allows the meshes to be cached over several frames if the graph is not updated.
For grid graphs in particular this improves the frame rate in the scene view significantly. In 3.x large grid graphs were very slow to draw, for larger graphs sometimes so slow that it was hard to work with them. As an example, for a 1000×1000 graph each frame would take over 4 seconds to render. In 4.x this has been reduced to around 90 ms (or around 50 times faster) which is a perfectly interactable frame rate.
Take a look at the video below for a comparison when using a slightly smaller graph.

As a bonus, the new custom line rendering system will give you nice smooth anti-aliased lines on Windows even when anti-aliasing is disabled in the rendering settings (Unity Gizmos will become aliased).

The graph rendering style has been improved for grid graphs. Now you can render the surface of the nodes as well as the outline of them. In 3.x only the connections between the nodes are visible which is often confusing, particularly for new users. Hexagon graphs (which are grid graphs with certain settings) can with the new rendering code be visualized much better. In the inspector you can now choose between any combination of the surface, outline and connections for rendering.

2D for everything

This is a great update for all of you that are working on 2D games or have been thinking of making one.
Many of the internal systems have been reworked or rewritten to be able to handle 2D worlds or even better, worlds with any rotation.
Local avoidance now works for both for 2D games and 3D games, the only thing you need to do is to flip a switch on the RVOSimulator component. You can read more about the changes to the local avoidance system below.
The AIPath script has been rewritten to among other things support movement with any graph rotation. It can now also optionally use the Y-axis as the forward axis for the character instead of the Z-axis which is often desired in 2D games.

The funnel modifier now includes an optional pre-processing step where it flattens the path corridor before running the funnel algorithm. This makes it possible to use the funnel modifier for 2D games and even on curved worlds.

The layered grid graph now also supports arbitrary rotations. It had some partial support in 3.x, but not everything worked.

Recast graphs can now be rotated and navmesh cutting has been reworked to support this.

A new example scene for 2D games with local avoidance has been added and there is also a new documentation page and video tutorial about how to configure pathfinding for 2D games.

Async scanning

In 4.0 all graph types have been reworked to support asynchronous scanning which means that you can show a progress bar while the graphs are being scanned and the game will not freeze. In 3.x all graphs had to be scanned synchronously, i.e in a single frame. This was problematic if your graphs were large and took some time to scan as the game would freeze during the calculation time.

You can scan graph asynchronously using the new ScanAsync method. It is an IEnumerable which you can iterate through. At each iteration it will return a short message describing what it is doing as well as a percentage which you can use to for example update a progress bar.

Turn based games

New functionality for (primarily) turn based games has been introduced.
In turn based games one often want very detailed control over which units can walk on which nodes and how much it costs for a character to traverse each node. It has been possible to do this via some elaborate combination of graph updates and tags, but possible does not mean easy and neither does it mean performant or stable.
In 4.0 a ‘traversal provider‘ (which is an interface that your scripts can implement) can be added to paths which allows you to control exactly what nodes a character should consider blocked and how large the cost of traversing those nodes should be. The package comes with a built in implementation of a traversal provider called ‘BlockManager’ and an accompanying component called ‘SingleNodeBlocker’. The SingleNodeBlocker component can be attached to any object (for example the units in a turn based game) and has a very simple API with which you can block nodes that the e.g a unit occupies. With the BlockManager you can then easily do things like “allow this character to traverse all nodes except those occupied by this list of SingleNodeBlocker components” or “don’t allow this character to traverse any nodes occupied by SingleNodeBlocker components except the ones in this list”. This is useful if you for example want to search for a path where the character should not be blocked by itself, but other characters should not be able to move through it.

A new example scene and a documentation page have been added which show how to use these components. The example scene also shows how to visualize all nodes within a certain distance from the character which is useful in turn based games to limit the distance a character can move in a single turn. It also showcases a hexagon graph which is a particularly popular graph type for turn based games.

Turn based example scene. The yellow hexagons show the movement range of one of the units (orange cone).

These utilities can of course be used for games that are not turn based as well, and I expect that they will be, but turn based games are the main target.

Improved movement scripts

The RichAI script has been improved and the AIPath script has been almost completely rewritten.
Among the most notable improvements are that the AIPath script now slows down and accelerates much more realistically and precisely. By using trajectory optimization the path of the agent is optimized to reach the end point of the path with a zero velocity to reduce any overshoot. This makes it able to stop much more precisely at the end points of paths without spinning around or overshooting.

The AIPath script can now use gravity and there is an option to use either the gravity set in the Unity project settings or a custom gravity which is useful for many games. This option has also been added to the RichAI script. Furthermore the way the AIPath and RichAI components integrate with rigidbodies has been improved and matches the behavior when not using rigidbodies a lot closer than before. The AIPath script has a new custom inspector that should make it easier to configure. It also draws gizmos in the scene view which visualize the various distance settings on the component.

When calculating many or long paths at the same time, especially on slow computers, it can take a small amount of time before the movement script gets back the result of the path calculation. During that time it may have moved a distance away from where it was when it requested the path and therefore the AIPath script has had code for detecting where it should start to follow the calculated path. If the latency for calculaing paths grew too large this algorithm could sometimes not keep up and the agent may for example turn around for a short amount of time and move in the wrong direction on the path. In 4.0 this algorithm has been improved to be both more performant and better handle cases when the latency grows large. This means it should tolerate slower computers (or more units/larger worlds) better.

Code quality

The code quality has been significantly improved in version 4.0. I have worked hard to clean up messy areas of code, to add more documentation comments and to refactor existing classes to improve encapsulation. This should make Intellisense suggestions less noisy. For those of you that like to read the source code of packages that you use, this should hopefully make it more enjoyable for you and make it easier to understand the code.

Local avoidance

The local avoidance algorithm has been rewritten completely. You will not notice many changes in behavior other than that they are now better at not being pushed through walls in high density crowds, however the configuration has been greatly simplified and some new features have been added. Each agent now has priority setting. Lower priority agents will avoid higher priority agents more. As mentioned in previously the local avoidance system now supports the XY plane as well so you can now use local avoidance in your 2D games.
In 3.x the local avoidance algorithm had various parameters that were not always easy to know the best values for, with the new algorithm it should be much easier to configure.

The new algorithm also allows for much better control over where exactly the character should stop. The previous algorithm was based only on velocities which works great when agents are moving, but it did not know at which point an agent intends to stop and this could sometimes lead to agents jiggling a bit when they reached their target point instead of stopping completely.

These are just the most notable changes. There are various other improvements that you can read about in the full changelog.

4.0 is a paid upgrade. However everyone who bought the package up to 8 months before the update was revealed (i.e after 2016-07-24) get the upgrade for free. Just make sure that you are logged in with the correct Asset Store account. If you bought the package earlier you can upgrade for 50% off in the Asset Store. If you didn’t buy the package via the Asset Store, please send me a PM via the forum.

Since not everyone can or want to upgrade, the 3.x branch will continue to get updates for a while with bug fixes and some features. I am not able to update the Asset Store package anymore due to how the Unity Asset Store works, but you can always download the latest version on the package homepage.

Footstep planning (part 2)




See the video below for the results.

Footstep planning (part 1)





Step midpoints. Image from the paper.
Path displacement from reference points. Image from the paper.






Cooperative Pathfinding Experiments

It’s time I wrote another one of these posts. I have been experimenting a bit with cooperative pathfinding during the last few weeks and it is working pretty well now.

What is cooperative pathfinding

Cooperative pathfinding is when instead of an agent just planning a path to the target and hoping it doesn’t crash in to any other agents the pathfinding algorithm will actually look at where all other agents will be in the future and make sure that the planned path does not collide with them. This is easier said than done because agents might change paths or new agents might be created while following the original path. Also the first agent that searches for a path can obviously not know where the other agents are going to be (since their paths have not been planned yet) but what essentially happens is that the first agent will plan its path and then the other agents will try to avoid crossing that path so it works well in practice.

There are many good papers on this subject. For example “Cooperative Pathfinding” by David Silver.

Here is a video showing how my experiments have turned out.

Why not local avoidance

Local avoidance is another technique for avoiding collisions however there are some downsides to it. Local avoidance usually only considers obstacles just a few seconds into the future and the ones in close proximity. This leads to it sometimes becoming stuck in a local minima which it cannot get out of. For example if two agents meet in a very thin corridor it is unlikely to be able to resolve that situation which requires one of the agents to back out of the corridor to let the other one past. Local avoidance simply does not have that longer term planning. If cooperative pathfinding was used instead, one agent would not even enter the corridor but would wait at the end for the other agent to pass (see the video for an example).


How does it work

Reserved nodes in a path
Reserved nodes in a path

The way this type of cooperative pathfinding works is that instead of treating say every square in a grid graph as a node, it will treat every pair of a square and a time as a node. In other words instead of just searching space, it searches space-time. This way the pathfinding algorithm will not search just node at a position and check if that is valid, but it will search a node at a specific position and a specific time and check if that is valid (which it would be if it was not inside an obstacle and no other agents are in that node at that time). The calculated path is then a sequence of squares with specified times of when the agent should arrive at those nodes. Immediately after calculating the path the agent can then reserve all the nodes in that path so that no other agents will calculate paths that will lead to a collision.

In the image to the right you can see an agent (red cylinder) following a path (green) and the reserved nodes in the path (red boxes). Reservations higher up indicate that they are reserved further into the future.

Agents in a cross formation. Each agent has the goal of moving to the opposite side.
Agents in a square formation. The goal is to move to the opposite side of the square. Reservations get complex pretty quickly.

Now we start to see some downsides to cooperative pathfinding as well. All those nodes need to represented and searched, that means if we want to search say 20 ticks into the future (where a tick is the time it takes for the agent to move one square) we need to search 20 times as many nodes as we would have to if we had not used cooperative pathfinding. We will also use a lot more memory but it isn’t 20 times as much since we don’t need to store a copy of the node 20 times, after all the position of the node and a lot of other data is the same. In my experiments I have usually limited the number of ticks in the future it can search search to either 20 or 40 and that seems to cover most cases. I have also used aggressive heuristic optimizations to make sure that only the most relevant nodes are searched. Another limitation in the current implementation is that all agents need to move at the exact same speed. This can be worked around by instead of reserving one node at time T when moving forwards one can reserve both the node at T and T+1. This would be used for slow units that move at exactly half the speed of the rest. But as noted, I have not yet implemented this.


The system described above would work pretty well, but it would fail completely in some cases. Consider for example one agent that does not have a goal at all but just want to stand on the same spot and another agent that needs to move past this first agent. The first agent would have reserved all the nodes on that spot in the future so the second agent will just have to wait. It will resolve itself after a while because agents recalculate their paths and if the first agent had calculated its path say 3 ticks ago, there would be 3 nodes that were not reserved yet (remember that agents only reserve up to a fixed number of ticks in the future) that the second agent could use to move forward. This leads to very long wait times for the agents and overall it just feels sluggish even though it usually manages to resolve all collisions. An improvement to this is to add a very small penalty for waiting and making sure that the penalty is higher for nodes in the near future compared to nodes the agent will reach in a long time. So the agents will prefer to wait as far into the future as possible. In this example the next time the agent that just stands still recalculates its path it will notice that the other agent will move over the node it is standing on in the future, so it will decide to move out of the way quickly and then wait and then move back to its original position rather than waiting until right before the other agent will take its spot and move away then. Later when the agent with the goal searches for a path again it will find that the other agent has moved out of the way and it can proceed to move to directly to the goal. It takes a few round trips of path recalculations but in my tests this has reduced the waiting times a lot.
Another thing that can be done is to make it so that when an agent is standing still it doesn’t completely reserve the node it is standing on, instead it will just apply large penalty for other agents to move over it. This further reduces waiting times a lot, especially in crowded scenarios, however it makes it possible for agents to overlap in some cases. If that is acceptable in the game or not depends. In the video I have this enabled because otherwise it takes ages for the agents to find collision free paths when ordered to order themselves in a dense grid.

When will this be in the A* Pathfinding Project

I am not sure. There are a bunch of tweaks I need to do to get it stable. Also keep in mind that this type of cooperative pathfinding has a long list of limitations. So if you are thinking “that would be great for my game” then read this list first.

  • All units need to move at the same speed.
  • No physics can be used to push agents around.
  • It is very grid based (well, it can be used with any graph, but it makes most sense on grid graphs).
  • It does not take unit sizes into account. All units are assumed to occupy a single node.
  • Only a single pathfinding thread can be used since paths need to be calculated sequentially (you can use more, but then you will have no guarantees that units will not collide).
  • It does in no way guarantee an optimal solution or even that a solution can be found.
  • No kinds of links can be used.
  • I think that was everything, but I might have forgot some constraint.

Navmesh Cutting



Enough words, here is a video:

This feature will be available in the next release.

Beta version of 3.3.5 released


You’ve got a new beta version to test!

  • Performance improvements for scanning recast graphs.

    • Guarantees that the character stays on the navmesh
      No more circling around the target point as with AIPath.
    • Simple wall avoidance to avoid too much wall hugging.
  • Reintroducing special connection costs for start and end nodes.
    Before multithreading was introduced, pathfinding on navmesh graphs could recalculate
    on navmeshes.

See the whole changelog here:


Roadmap and Current Development – A* Pathfinding Project

Hello everyone!



    A path offset using the radius modifier

So what do I want to do next?




– Aron Granberg

Local Avoidance in version 3.2



New Forum!


Check out the new forums here: