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