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

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

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.

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.

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.

# 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

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.

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.

# New video

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

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

# 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

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.

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

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

# New Forum!

At last I have got a new forum software up and running!
It is powered by Vanilla Forums, an open source forum platform which seems to be very good. However I did not manage to migrate the old forum to the new forum, so I will leave the old forum open for viewing, but closed so that no new topics or posts can be created.

Check out the new forums here: http://arongranberg.com/vanillaforums

# Local Avoidance pt 3

So it’s time for local avoidance again.
The A* Pathfinding Project (pro version) has included a beta version of local avoidance for some time. I decided it was time to do something about that “beta” label.
There is a great library out there called the RVO2 library. It has been used in both UDK and in Unity. Unfortunately it has a rather limited license. Not for commercial use unless explicit permission is granted, which is a problem since they do not seem to answer any emails I send them.
So I decided to take inspiration from the rvo2 library and rewrite it in C#. Which I have now done. I have also added new features, for example agents and obstacles can now have different Y coordinates as well as XZ coordinates, so agents at different floors of a building can navigate properly without “colliding” with agents at other floors.
I have written a script to convert navmeshes to RVO obstacles, so agents will properly avoid navmesh edges. I will later write a similar one for Grid Graphs and I hope to get graph updates to work fine with it as well.
Time to stop talking and link to a demo:
http://www.arongranberg.com/unity/a-pathfinding/local-avoidance-demo/

It has really good performance. On my laptop I can run 500 agents when I just make sure they don’t all try to go through the same point, and on my stationary computer I can run more than 500 agents with a good framerate. Currently the rvo simulation is set to a desired fps of 20 and everything in between is interpolated.