A* Pathfinding Project 5.0

Version 5.0 of the A* Pathfinding Project is now available. This is a major update which has been in the works for quite some time.

The A* Pathfinding Project is a blazing fast pathfinding package for the Unity game engine.

This update brings the package into the new world of burst, unity’s job system, and the entity component system.
There have been substantial performance improvements across the board, a ton of bugfixes, lots of new features, and a focus on improving robustness and stability.

This release has been battle tested in an open beta, so it should be pretty robust from the start. But if you find any bugs, please report them in the forum, and I’ll take a look at them.

Where to get it

I know, you are eager to get your hands on it. But not to worry, you can download the latest version directly from the Asset Store right now, or from the package website.

If you are upgrading from an earlier version, you may want to read the upgrade guide.

New Features

There are lots of new features and improvements in this release. I have grouped them by graph type and area, to make it easier to read.

Grid Graphs and Layered Grid Graphs

Grid graphs have received a major rewrite in how they scan and update the graph.

Better performance with Burst and improved algorithms

The grid graph is now powered by the Burst Compiler and the unity job system, which makes scanning graphs around 3x faster.

More intuitive slope handling

There’s a new option called Max Step Uses Slope, which makes the graph much better connected in most scenarios involving slopes. When upgrading, this field will be disabled for compatibility reasons, but it will be enabled for all new graphs.

New rule system

There’s also a whole new system for creating rules for grid graphs. These rules allow you to tweak the grid graph scanning process in a very flexible way, which also works with graph updates transparently.

See Grid Graph Rules.

Automatic tilemap alignment

For 2D enthusiasts, the grid graph can now align itself to a Tilemap directly from the inspector. Something which otherwise might have required complex trigonometry, especially for isometric games, or those using hexagonal tiles.

More accurate linecasts on grid graphs

Linecasts on grid graphs have received a major rewrite, with a big focus on robustness and correctness. Previously, edge cases like “the linecast runs precisely along the border to an unwalkable obstacle”, or “the linecast ends exactly at a corner of an obstacle”, were not well-defined. Now, the border between the walkable part of the navmesh and the obstacles is defined as walkable. Edge cases are handled a lot better now.

Recast Graphs

Improved pathfinding accuracy

Pathfinding accuracy on recast/navmesh graphs has been improved significantly. Previously, paths on recast/navmesh graphs have been searched by going from triangle center to triangle center. This was not very accurate and could lead to agents choosing suboptimal paths. Now, paths use a more accurate method which moves between different points on the sides of the triangles instead of the centers. This is much more accurate and should lead to agents choosing better paths in almost all cases. It also accounts for the exact start and end point of the path more accurately now.

This will lead to many fewer instances of the agents unnecessarily taking the long way around an obstacle.

However, this improved accuracy comes with a cost, and pathfinding performance on navmesh/recast graphs is a bit lower than before. Luckily, it is still very fast, and most games are not bottle necked by this.

Significantly improved performance

Recast graphs now use the Burst Compiler and the Unity Job System. Together with a lot of work on improving the underlying algorithms, this has resulted in much faster scans and updates of recast graphs. It’s now up to 3.5x faster. Graph updates and async scans also run almost entirely in separate threads now, to make the fps impact as minimal as possible.

2D Support

The recast graph now supports 2D colliders, and the inspector has a new enum that allows you to toggle between 2D and 3D mode. There’s a new field Background Traversability that controls if a navmesh should be generated for an unobstructed background in 2D mode. There’s also a new example scene demonstrating a recast graph in a 2D scene (read more below).

Terrain Holes

Terrain holes are now supported out of the box by recast graphs.

Solid Colliders

Recast graphs now treat convex colliders (box, sphere, capsule and convex mesh colliders) as solid, and will no longer generate a navmesh inside of them.

Tag surfaces directly

You can now mark surfaces with specific pathfinding tags. Just add the RecastMeshObj component to an object and set the mode to WalkableSurfaceWithTag.

This is much less error-prone (and faster) than having to use a GraphUpdateScene component.

Better tree support

  • Colliders on child objects will also be taken into account.
  • You can use the RecastMeshObj component on trees to customize how they are rasterized.
  • Significantly improved performance when you have many trees.
  • Tree rotation is now taken into account.

Navmesh Prefabs

The new component NavmeshPrefab allows you to easily store recast graph tiles in prefabs and load them at runtime. This is great for big procedurally generated levels, where scanning the graph at runtime is too slow to be an option.

Navmesh Graphs

Improved performance

Scanning navmesh graphs is also powered by burst and the job system, making them much faster to scan.

Pathfinding on spherical worlds

Added support for pathfinding, local avoidance and movement on spherical worlds, and other strange world shapes.

Take a look at Spherical Worlds for more info.

Local Avoidance

New Algorithm

The new local avoidance algorithm is based on ORCA (Optimal Reciprocal Collision Avoidance), which leads to nicer movement in most cases.

Much better performance

It’s a lot faster! Not only due to the new algorithm, but also because now everything is powered by burst and the unity job system. Local avoidance is up to 10x faster than in 4.2.x.

Crowded Destination Detection

Agents can use the local avoidance system to detect if a destination that they want to reach is crowded. The agent can use this information to stop, instead of trying to move forward endlessly.

This is done by the new FollowerEntity movement script automatically, and can be enabled on the AIPath/RichAI movement scripts.

Avoid the navmesh border

The local avoidance system now takes the navmesh into account automatically, and with good performance. Previously, the RVONavmesh component has been used for a similar result, but it had much worse performance, and it was not as robust.

New ECS-powered movement script

A new movement script called FollowerEntity is now included. The focus for this new movement script is that it should “just work”, and that it should be very robust and handle all those pesky edge cases.

In terms of performance, it’s also slightly better than both the AIPath and RichAI movement scripts.

Out of the box, it supports local avoidance, smooth and very responsive movement, off-mesh links, staying away from walls, facing a given direction when it reaches its destination, and a lot more.

You do not need to know anything about ECS to use it, everything is abstracted away, and you can use it much like the other movement scripts.

Infinite procedural worlds with recast graphs

The ProceduralGraphMover (previously ProceduralGridMover) now supports recast graphs too. Now your infinite worlds can have recast graphs too!

Improved off-mesh links

Off-mesh links have been almost completely rewritten to be more robust and easier to use. You can now specify a tag for them, and choose which graphs they are allowed to link. They are also much more robust when combined with graph updates, whereas previously they could sometimes lose their connection to the navmesh. And during those graph updates, they require much less CPU power to refresh themselves, so now you can have a lot more of them in your scene without any performance issues. Take a look at the new tutorial on off-mesh links: Recast graph with off-mesh links.

Improved navmesh cutting

NavmeshCuts now support expanding the cut by the agent radius. Making them more useful if you have multiple graphs for different agent sizes.

Enter Play Mode Options Support

Added support for all Enter Play Mode Options. This means you can cut down on your iteration times significantly. See https://docs.unity3d.com/Manual/ConfigurableEnterPlayMode.html

Improved Documentation

The documentation has received an overhaul in this update. There are new example scenes, new tutorials, and of-course more in-code documentation.

Added all new example scenes

6 new example scenes are now included in the package, each with their own dedicated page in the documentation. These are much better looking than the old ones, and show more advanced usage of the package.

Added a new example scene: Recast graph in a 3D game

Added a new example scene: Recast graph with doors

Added a new example scene: Recast graph in a 2D game

Added new tutorials and documentation pages

There’s also a new flowchart to help new users find the right graph type for their game. See TL;DR Which graph should I use?.

Access the documentation easily from Unity

You can now right-click on almost any property in a component, and get a link directly to the online-documentation for it. This existed in some old versions too, but it had to be removed due to Unity limitations. But now it’s back again!

Better tooltips in the Unity inspector

When hovering over properties in the Unity inspector, you now get much better tooltips on most components.

Improved robustness

A lot of work has gone into making the package more robust.

The improvements are too numerous to list here, but one such improvement is improved consistency guarantees when doing an async graph scan or graph update. Previously, the graphs could be in partially scanned states during the scan/update, which could cause e.g. GetNearest calls to return incorrect results, or throw exceptions. Now, the graphs will be in a consistent state at all times during the update (from the main thread’s perspective).

Colorful icons for components

To help you more easily find the right component in the inspector, most components now have a custom-designed icon.

More improvements and fixes

Check out the full changelog for another 200 or so improvements, changes and fixes.

Other changes

Price Update

The A* Pathfinding Project has had the same price since it was first released, over 10 years ago. To keep up with inflation, and also the massive number of improvements that have been added since then, the price of the package has been increased to $140. Existing users of the 4.x version will be able to upgrade to 5.0 for free.

Minimum Unity version and dependencies

Due to the reliance on the burst compiler, I’ve had to increase the minimum supported Unity version to 2021.3.35f1. However, I strongly recommend going further and using Unity 2022.3 LTS or later.
Most features work in Unity 2021.3, but about half of the example scenes are not compatible due to Unity serialization issues, and anything that uses the entities package is only available on 2022.3+.

The new version also depends on the mathematics, collections and burst packages.
The entities package is an optional dependency. Any components that require it have a button in their inspector to allow you to easily install the package.