arongranberg.com Open in urlscan Pro
213.239.212.56  Public Scan

Form analysis
0 forms found in the DOM

Text Content

Skip to content


ARONGRANBERG.COM

Game Development with Unity 3D
Menu
 * Home
 * A* Pathfinding Project
 * Unity
   * A* Pathfinding Project
     * A* Pathfinding Project
     * Download
     * Forums
     * Free vs Pro Comparison
     * Pro Version
     * Demos
   * ALINE

February 27, 2024


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!

Your browser does not support the video tag.


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.

Your browser does not support the video tag.


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 a new example scene: Recast graph with off-mesh links



Added a new example scene: Recast graph with tags



Added a new example scene: Recast graph on a terrain



Added a documentation page for the turn based example scene: Hexagonal Turn
Based

Improved the infinite world example scene with nicer meshes: Infinite
procedurally generated world



Improved documentation and look of the path types example scene: Path Types



Improved documentation and look of the moving example scene: Recast graph on a
moving surface




ADDED NEW TUTORIALS AND DOCUMENTATION PAGES

 * Off-mesh links
 * Pathfinding on tilemaps.
 * Circling a target.
 * Moving a graph at runtime.
 * Migrating from Unity Navigation.
 * Large worlds.
 * Agent-Specific Pathfinding.
 * Architecture overview.
 * Grid Graph Rules.
 * Writing Custom Grid Graph Rules.
 * Manual Player Movement.

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.

by Aron Granberg
 * Unity

April 29, 2017


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.

by Aron Granberg
 * Unity

February 11, 2017


FOOTSTEP PLANNING (PART 2)



Earlier I wrote a post about some research I have been doing into how to produce
realistic movement for characters. After a large amount of implementation work,
trying to understand papers and bug fixing I have some progress to share.

In the previous post I used relatively simple inverse kinematics (IK) to place
the feet at the correct positions. The approach that I used only looked a small
distance into the future and the past when determining the IK targets and
weights so the results were ok, but not that good. Based on the paper “Planning
Biped Locomotion using Motion Capture Data and Probabilistic Roadmaps” I have
now implemented a higher quality technique which adjusts both the position and
rotation of the character as well as the rotations of the character’s bones.
This is done by first simulating the movement of the character and at every
point in time and calculating the rotations of the bones if IK would have been
applied. Then b-splines are used to produce a fit to this data so that the
result is a collection of b-splines that determine how much the rotations of the
bones (or the position of the character) should be modified when playing the
animations. B-splines can have varying number of control points or “knots” and
the higher the number of knots, the more detail they can represent.
The approach that the paper and I use is to first fit the data to splines with a
very low number of knots, run the IK algorithm again when the adjustments from
that spline have been added and then add another b-spline with more knots. This
produces a hierarchical b-spline that can both generalize over stretches with
few data points as well as capturing the smaller details. In the image below you
can see 4 levels of a hierarchical b-spline. The first level in blue only
captures very rough information about the points, but subsequent levels add more
detail. Note that the black points are the input points for the curve fit, not
any kind of control points for the b-splines.

The benefit of using hierarchical b-splines over the earlier approach is that
they make it much easier to spread information further back and forwards in time
so that the character can anticipate where a foot needs to be placed and adjust
its pose accordingly.
The particular IK technique that is used also modifies the position of the
character. Most IK techniques keep the position of the character fixed and only
modify the rotations of the bones, but by allowing the position of the character
to be modified slightly a higher quality movement can be achieved. The downside
is that this makes the IK algorithm significantly slower (it takes around 200 ms
to process all the IK for the path in the video below). It will use a normal IK
technique that does not modify the position of the character and then it will
try to minimize the deviation of the bone rotations from the original animation
by using conjugate gradient descent where it can for example move the character
slightly if that makes it have to adjust the bone rotations less. In my current
implementation this step takes the majority of the time by a very large margin,
however I have some thoughts on how to optimize it. Firstly it uses numerical
gradients at the moment which works, but it is prone to floating point errors
and it requires an evaluation of the IK algorithm for each parameter that we are
optimizing over (in my current implementation I use x y and z coordinates of the
character as well as the rotation of the character around the y axis). A better
approach would be to use automatic differentiation to calculate the derivative
explicitly. Automatic differentiation is a bit tricky to implement correctly
however. Another thought I had was to adjust the relatively new IK algorithm
FABRIK so that it will move the position of the character instead of keeping it
fixed as is normally the case. I have yet to test if this is a viable approach.

See the video below for the results.


by Aron Granberg
 * Unity

December 11, 2016


FOOTSTEP PLANNING (PART 1)



I have recently started to experiment with ways of achieving very high quality
movement for characters.
Usually in video games or simulations one would request a path from the
pathfinding system and follow that path by for example rotating the character
around its pivot point and moving towards a point slightly further ahead on the
path. This produces smooth, but not very high quality movement. For humanoid
characters you really want it to look like the character is moving itself, not
being dragged along a path and playing some animations that sort of correspond
to how the character is moving. The Unity engine has an animation system called
‘Mecanim’ which has a feature called ‘root motion’. When root motion is enabled
the animations will drive the movement of the character which results in very
high quality movement. Unfortunately it is very hard to control that movement as
you would have to figure out exactly which animation to play and for how long to
get the character to move to a specific point, in many cases it might be
impossible to move it to the position that you want without a very complicated
and unnatural sequence of animations.

There should be a middle ground between easy to control movement and high
quality movement that gives us the best of the two approaches. I have been
inspired by a paper called “Planning Biped Locomotion using Motion Capture Data
and Probabilistic Roadmaps” which approaches the problem by instead of planning
a polygonal or spline path that the character should follow, it plans a sequence
of footsteps that the character should take. I think this is a very promising
approach with several potential improvements as well.

Image from the paper “Planning Biped Locomotion using Motion Capture Data and
Probabilistic Roadmaps”

The main parts of the algorithm described in the paper can be summarized as
follows (for more details, see the paper). For a visualization of some of the
steps, see the video below.

Step midpoints. Image from the paper.
 1. Plan a sequence of footprints and animation clip pairs using some kind of
    planner (in the paper they construct a graph of possible footprints with
    edges between them representing animation clips).
 2. Smooth the footprints while ensuring that the animations are not distorted
    too much and that they do not cause the character to intersect obstacles.
 3. Adjust the footprints to make them more similar to the original animation
    clips
 4. Optionally go to step 2 for another smoothing iteration (the paper uses
    between 2 and 4 iterations).
 5. Pick new animations after the footprints have been smoothed (or possibly
    after every smoothing iteration).
 6. Trace the root path (pivot of the character) of the animations if they would
    be played as is. This corresponds to using Mecanim’s root motion feature.
    The resulting path will unfortunately not match the desired path perfectly.
 7. Use the midpoints between the steps as a reference for the root path (see
    image).
 8. Transform the root path from step 6 to match the reference points of the
    desired path. This will give us a path that the character could follow.
 9. Use a retargeting step to optimize the resulting animation to make it more
    aesthetically pleasing and ensure that constraints such as the character’s
    feet actually being placed at the desired footprints are fulfilled.

Path displacement from reference points. Image from the paper.

Currently I have implemented step 2, 4, 5, 6, 7 and 8. Instead of step 9 a
comparatively simple IK solver is used instead (see video) to place the feet
where they should be. Instead of step 1 the sequence of footprints is determined
manually and the animation clips are selected greedily (picking the best
animation clip when looking at a pair of footprints at a time). The greedy
selection algorithm often produces a sequence of animations that are very far
from the desired path, however it is good enough to be used as input to the
later stages. In the future it will be replaced completely.

Below you can watch a video of a prototype of my current implementation.






I am not very happy with the movement quality so far. Initially I had thought
that the retargeting step that the paper uses (based on another paper called “A
Hierarchical Approach to Interactive Motion Editing for Human-like Figures”)
might be unnecessary and could be skipped if the transformation step was just
improved a bit. However it turns out that it is not enough. I did make
improvements to the transformation step as the paper only uses a series of rigid
transformations (think of a metal chain that can be deformed, but the individual
links cannot bend) while my implementation has incorporated blending weights
into it and works in a very similar way to how skinned meshes are deformed in
game engines and animation software. This results in a smoother path.

Some of you reading this may wonder if/when this will show up in the A*
Pathfinding Project. Currently I have no plans for this, though it may of course
happen if this experiment turns out well. Right now this is just research.

The next step would be to either try to get a path planner working (step 1) or
implement the retargeting step (step 9). It turns out that in the retargeting
algorithm there are a lot of complicated things going on and it seems I finally
have to learn conjugate gradient descent, but hopefully that should be doable.

by Aron Granberg
 * Unity

June 21, 2015


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

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

by Aron Granberg
 * Unity

 * Unity

January 31, 2015


NEW VIDEO



Here is a new video showing of some of the features of the A* Pathfinding
Project.





by Aron Granberg
 * Unity

August 26, 2013


NAVMESH CUTTING



Navmeshes in the A* Pathfinding Project have been awesome when you have static
worlds, but often very low-performing when any kind of dynamic updates are
required.
The experimental version which has been released for a while (but now superseded
by the beta version) improves that by enabling tiled recast graphs so that
individual tiles can be recalculated.
This is however quite slow as well. It works, but it’s not something you want to
do without player interaction, and definitely not several times per second.

So what I have been working on is to enable navmesh cutting. What navmesh
cutting does is to take a valid navmesh (for example the one generated at start
by a recast graph), punches holes in it to make room for dynamic obstacles
(boolean operations), fixes it up a bit (fixing triangles not fulfilling the
delaunay criteria) and then puts it back to be used for pathfinding. And it’s a
lot quicker than recalculating a tile using recast.
The downside is of course that it only works for obstacles, not for something
like moving bridges (or whatever) which must add new ground for the player to
pathfind on. Luckily, you most often have these kinds of subtractive obstacles
that are dynamic.

Enough words, here is a video:






This feature will be available in the next release.

by Aron Granberg
 * Unity

August 25, 2013


BETA VERSION OF 3.3.5 RELEASED



Hi

You’ve got a new beta version to test!
It is at version 3.3.5 now, the last released version is 3.2.5.1 but the
experimental release has been at 3.3 for a while now.
LOTS of things have been improved in this version. Here are the highlights from
the changelog:

 * Rewritten graph nodes. Nodes can now be created more easily (less overhead
   when creating nodes).
 * Graphs may use their custom optimized memory structure for storing nodes.
   This is not that significant now. But it paves the way for other graph types
   like QuadtreeGraph (an efficient one, as opposed to the one used in the 2.x
   versions if you remember that).
 * Performance improvements for scanning recast graphs.
 * Added a whole new AI script. RichAI (and the class RichPath for some things):
   This script is intended for navmesh based graphs and has features such as:
   
   
   
   * Guarantees that the character stays on the navmesh
   * Minor deviations from the path can be fixed without a path recalculation.
   * Very exact stop at endpoint (seriously, I can get precision with something
     like 7 decimals (usually not that good though)).
     No more circling around the target point as with AIPath.
   * Does not use path modifiers at all (for good reasons). It has an internal
     funnel modifier however.
   * Simple wall avoidance to avoid too much wall hugging.
   * Basic support for off-mesh links (see example scene).
 * Improved randomness for RandomPath and FleePath, all nodes considered now
   have an equal chance of being selected.
 * Recast now has support for tiles. This enabled much larger worlds to be
   rasterized (without OutOfMemory errors) and allows for dynamic graph updates.
   Still slow, but much faster than
   a complete recalculation of the graph. Also, navmesh cutting is beta. Navmesh
   cutting can enable fast dynamic obstacles on recast graphs (note that navmesh
   cutting cannot be used in the beta version at the moment, so don’t spend time
   looking for it).
 * Added RecastMeshObj which can be attached to any GameObject to include that
   object in recast rasterization. It exposes more options and is also
   faster for graph updates with logarithmic lookup complexity instead of linear
   (good for larger worlds when doing graph updating).
 * Reintroducing special connection costs for start and end nodes.
   Before multithreading was introduced, pathfinding on navmesh graphs could
   recalculate
   the connection costs for the start and end nodes to take into account that
   the start point is not actually exactly at the start node’s position
   (triangles are usually quite a larger than the player/npc/whatever).
   This didn’t work with multithreading however and could screw up pathfinding,
   so it was removed.
   Now it has been reintroduced, working with multithreading! This means more
   accurate paths
   on navmeshes.
 * Added several methods to pick random points (e.g for group movement) to
   Pathfinding.PathUtlitilies.
 * Added RadiusModifier. A new modifier which can offset the path based on the
   character radius. Intended for navmesh graphs
   which are not shrinked by the character radius at start but can be used for
   other purposes as well.
 * …and probably some more things which I have forgotten for the moment.

See the whole changelog here:
http://arongranberg.com/astar/docs_FeatureFreeze/changelog.php
The beta version can be downloaded by users who own the pro version. Simply go
to the download page.

Thing to look out for: Lots of node variables and properties have changed casing
(.position is now .Position etc.). I plan to go back to the previous casing
before release to ease upgrading. But for now, you might have to fix some
compiler errors when upgrading your project (please keep a backup as always). If
you find something that is not working or buggy, it would be awesome if you
could notify me. If you are sure that it is a bug, send me a private message in
the forum, otherwise post a question in the forum.
Also, you will need to regenerate all saved files with node data (and cached
startup caches) since the binary format has changed. Settings are preserved but
node data is lost, you might get exceptions if you try to load old data.

by Aron Granberg
 * Unity

August 9, 2013


ROADMAP AND CURRENT DEVELOPMENT – A* PATHFINDING PROJECT



Hello everyone!

It has been quite a long time since I wrote here on this blog. Not that
development and activity was reduced during this period, quite the contrary, I
just haven’t gotten around to do it.
So now got a question in the forums asking about the plans for the future
development of the A* Pathfinding Project, and I thought that I really should
write this as a blog post instead. So here it is, enjoy!

The A* Pathfinding Project is currently at 3.2.5.1. It has not been updated
since sometime this spring. However, there are a huge load of new features
waiting to be released. I guess the plan for the short term future is to finish
them and actually release something. Most of the new features requires more work
to be production ready even if most of them are quite stable.

 * Faster to add and remove nodes during runtime without a huge performance
   cost. This can for example be used to add and remove nodes from a point graph
   during runtime very quickly.
   – Better AI for navmeshes (works on grid graphs as well, but not as big
   improvement). This AI uses a Funnel Corridor to follow instead of just
   points. Unfortunately this means it cannot use path modifiers, but on navmesh
   graphs it works very well without them, especially since the modifier you
   usually use is the funnel modifier and that is built in now (of course I have
   not removed all modifiers, other movement scripts can still use them, and I
   have no plans to deprecate modifiers). This AI also has much better steering
   and will not circle around the target as AIPath can do sometimes, it can
   position itself at the target with something like 5 decimal places of
   precision, and it even slows down really smoothly, not an instant stop.
   
 * The above builds upon a new class named RichPath, it holds a funnel corridor.
   The great thing about holding a funnel corridor is that the agent can wander
   off slightly without causing much trouble, previously this could have caused
   the AI to crash into a wall if it didn’t follow the path precisely. The
   RichPath also keeps the agent strictly on the navmesh, this removes the need
   for colliders in many cases, especially it reduces the need for a Character
   Controller which is really slow to use.
 * Tiled Recast Graphs. Tiling recast graphs enables runtime recalculation of a
   piece of a recast generated graph. It is not very fast, but it works and is
   miles faster than recalculating the whole graph. As a side note, recast graph
   scanning has been improved substantially in terms of performance but
   especially memory-wise.
 * Navmesh cutting. Tiled Recast graphs can be cut (subtractively) during
   runtime to make place for e.g dynamic obstacles. Navmesh cutting is much
   faster than recalculation of a tile, albeit not as powerful. The cuts you see
   in the image below are calculated in 3-18 ms per tile on my laptop (depending
   on tile complexity), from start to replaced navmesh tile. Tiled recast graph
   cut using navmesh cut objects (light blue outlines are the cutting polygons)
 * Threaded graph updates. The above recast tile recalculations are relatively
   slow, therefore I have added the ability to use threaded graph updates. So
   the game will continue to run ok and the graph recalculation will take place
   in a separate thread.
 * More stable core graph updates. The AstarPath.cs script has been a mess of
   callbacks, ManualResetEvents and lots of locks to try to keep pathfinding
   from interfering with graph updates and etc. Now this has been cleaned up and
   hopefully it will be more stable. There is even theoretical support although
   not yet actual support (not much work left) to do scanning over multiple
   frames (maybe to avoid pauses in loading animation or something).
 * Funnel modifier is more stable now, it could previously sometimes generate
   weird paths.
 * RecastMeshObj is a new component which enables you to specify unwalkable
   regions even for recast graphs. Previously you have had no control over if a
   region was walkable or not, the recast graph would do what it thought was
   best. See this youtube video
 * I have done more work on off mesh links on navmesh graphs. Now it is possible
   to create off mesh links, for example between two platforms and with an
   example script specify an animation to be used for that link, for example a
   jumping animation.
 * Radius Modifier. A new modifier which offsets the path into smooth curves. A
   path offset using the radius modifier
 * Graphs can use their own specialized data structure for storing nodes. This
   does not impact much right now, but might enable easier development of future
   additions, e.g quadtree graphs.
 * Funnel simplification. Especially on tiled recast graphs, the paths are not
   always the shortest one, therefore I have added to the RichPath class
   (mentioned above) a way to simplify funnels using graph raycasting before
   using. This works really well and will get you better paths.

So that was all the features I have developed and are mostly complete. At least
I think so… though I have probably forgotten some :p
So what do I want to do next?

 * Any-angle path search. This is an algorithm similar to A* for navmesh based
   graphs which generates more optimal paths on navmesh graphs. You can
   sometimes see that many small triangles next to a few large ones can cause
   sub-optimal paths to be generated. With any-angle path search, more optimal
   paths will be generated.
 * Jump-point search. An algorithm for grid graphs similar to A* but A LOT
   faster unfortunately with a few constraints. It cannot handle penalties,
   neither any off-mesh links. Only simple straightforward grid pathfinding,
   walkable or unwalkable nodes. See this demo.
 * Navmesh graph reductions. Navmesh graphs can be optimized using a
   hierarchical structure which enables faster searches. This is described in
   the paper “Efficient Triangulation-Based Pathfinding” by Douglas Demyen and
   Michael Buro.
 * The above linked paper also has a brief note about a funnel algorithm which
   can generate a path with a minimum clearance from all edges. The result would
   be similar to what the Radius Modifier along with the Funnel Modifier
   generates right now, but it would be more stable, the radius modifier can
   fail in certain conditions (not that usual though, and if paths are
   recalculated relatively often, it will not be a problem).

I have no plan for when these additional developments will be done. Right now I
am focusing on pushing the first list of new features into the released package
and I hope to release an update within a month.

As always, if you have any feature requests, I am happy to know about them. See
the Feature Requests category in the forums.

– Aron Granberg

by Aron Granberg
 * Unity

October 30, 2012


LOCAL AVOIDANCE IN VERSION 3.2



RVO Local Avoidance is progressing. I recently managed to fix a bug which
boosted performance hugely. Apparently it is not a good idea to use generic
lists for holding simple structs since they will be copied every time they are
accessed, and when you do that 170000 times every frame, that small copy
operation adds up. Moving to a standard array fixed that. I can now get 5000
agents running around at 50 fps average and 10 fps during calculation steps, the
rvo simulation itself is only running at around 10 fps. And this is on my
laptop.
I uploaded a new video showing 1000 agents trying to reach their antipodal
points on a circle.



So how easy is it to integrate existing movement scripts with the local
avoidance then? Really easy actually. I have written an RVOController script
which is designed to be an almost drop-in replacement for the Unity
CharacterController so starting to use local avoidance will be easy as pie.

by Aron Granberg
 * Unity

Posts navigation
Older posts

INDIE GAME MUSIC!


Built with Make. Your friendly WordPress page builder theme.
 * Twitter
 * YouTube
 * RSS