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.

Posted in Unity | 7 Comments

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.

Posted in Unity | 7 Comments

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

Posted in Unity | 1 Comment

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.

Posted in Unity | 10 Comments

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

Posted in Unity | 20 Comments

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.

Posted in Unity | 2 Comments

3.1.2 Update

Version 3.1.2 of the A* Pathfinding Project has just been released.
This is a bugfix update which fixes some problems, mainly with iPhone compatibility.
Check out the changelog at the usual place: http://arongranberg.com/astar/docs/changelog.php

Posted in Unity | 7 Comments

Small bugfix release

Okay, people immediately found bugs with the 3.1 release (and obvious bugs as well I really should have tested it more).
So now 3.1.1 has been uploaded, the two bugs should be fixed now. With a bit of luck, I haven’t made any other serious mistakes.
For those wondering, the Asset Store submission is pending.

Changelog (updated version will be uploaded in a minute): http://arongranberg.com/astar/docs/changelog.php

[EDIT] Version 3.1.1 is now available in the Asset Store as well.

Posted in Unity | Leave a comment

A* Pathfinding Project 3.1 Released!

Yay! Now it is finally here! Version 3.1 of my pathfinding system.
The upgrade should be hassle free (hopefully). However ListGraphs will not have their settings preserved. This is because I have renamed the ListGraph to PointGraph (better name) so it will not find the graph type ListGraph anymore.
The whole serialization system has been rewritten as well. It is now a lot more stable (no custom written hackish stuff) and is aimed to be both forwards and backwards compatible (well, not with the old system, but when updates to the new serialization system are made). It is based on Json and now you can actually save graph data, unzip it (yes it is stored as a zip) and edit the graph settings by hand!
Anyway, too many new features to list here (seriously!). Check out the changelog: http://arongranberg.com/astar/docs/changelog.php

Version 3.1 has been submitted to the Asset Store, but it might take a few days for it to be approved.

Posted in Unity | 1 Comment

A* Pathfinding Project 3.1 beta released!

I just released the beta version of the A* Pathfinding Project 3.1.

The release has almost everything working, just a few details which need to be reworked, so it is stable enough to be used in a game. But please back up your projects before upgrading.

Pro users which have bought it at this website can use the download link in the confirmation email they got when first buying it, the zip file linked will now contain both the current version and the 3.1 beta.

Sorry, but I didn’t have time to upload the beta version to the Asset Store (and I won’t have time for about two weeks). Those who have bought it there will have to wait for the final 3.1 release.

I hope you will find it a great upgrade!

Posted in Unity | 6 Comments