Steve Exploring Stuff


CAINav v0.4: The Nuclear Option

CAINav v0.4.0 has been released.  There are a whole lot of enhancements and changes.  This post includes an overview, plus information on some of the enhancements. 

Download | Documentation (Improved getting started and advanced sections.)


First the bad news.  Well, 'bad' is not really the correct term.  For new users it's all happy happy joy joy.  For users upgrading from v0.3, will be pain pain suffering, then happy happy joy joy.

Remember all those warnings about CAINav being in alpha?

The pain centers around changes to the API and Unity extensions.  As I added features for v0.4 I quickly realized that there was no way to move forward and also make for a clean and easy upgrade.  So I chose the nuclear option. Kaboom went the API. Everyone will be affected.

Summary of Enhancements

The major enhancements for v0.4 include the following:

  • Conversion from float[3] arrays to Vector3 structures.
  • Easy tiled navigation meshes. (I.e. Large area meshes.)
  • Area and flag assignment during the build process.
  • Support for off-mesh connections in the build process.
  • Support for background/multi-threaded builds.
  • A standard end-to-end build process that is highly extendable.
  • For Unity users, almost all advanced build features are available to non-coders. (I.e. Scene designers.)
  • A new API for the PathCorridor class.  (Easier to use with better performance.)
  • An upgrade to Recast Navigation r338.

"But," you may ask, "aren't many of these feature already available in v0.3?" Yes they are.   But in v0.3 you had to fully understand the intricacies of the navigation mesh build process and write your own code to make use of the features.  The v0.4 build process makes things a whole lot easier.

Conversion from float[3] Arrays to Vector3 Structures

This is the API change that will impact every user.

Recast Navigation is based on float[3] vectors.  I originally chose to keep using float[3]'s throughout the core, switching to structures only in the Unity ease-of-use extensions; and then, only when it did not impact memory and performance too much. That was a design mistake that is rectified in v0.4.  float[3]'s are completely gone from the API.

For Unity users, everything uses UnityEngine.Vector3 structures. You'll also note that all the U3D* classes are gone. They are no longer needed.

.NET-only users get the simple org.critterai.Vector3 structure.  This structure is implemented in a way that will allow many users, with only an hour or so of work per version upgrade, to swap your own vector structure into CAINav, getting the same ease-of-use as Unity users. See Advanced Topics > .NET: Swapping in Native Vectors in the documentation for details.

This change is 99% good.  The API is much much cleaner and performance is significantly better.  One standard path following scenario showed a 30+% increase in performance.  Hard to believe, but I couldn't find any flaws in the test methodology. It is also really nice not to have to deal with vector array references all over the place.

There are two downsides.

Users who code for interoperability between both Unity and .NET applications can no longer use the same libraries for both targets.  (Not byte-code compatible.)  Also, source code that needs to run on both targets will need some extra code. Something like this:

using Vector3 = org.critterai.Vector3;
using Vector3 = UnityEngine.Vector3;

The other downside is serialization.  Multiple sets of libraries means that normal .NET serialization is of limited use.  In fact, I'll be removing the ISerializable interface from all classes starting in v0.5.  Byte[] serialization will be the standard format moving forward.

For those who are upgrading, most of it is just mind numbing grunt work. Converting variables from float[3]'s to Vector3's, dealing with the change from reference to value types, simplifying code structure, etc. The big gotcha is the stride of vector arrays. Be careful there, since you'll be changing from a stride of 3 to a stride of 1. That's the only bit that caused me any real pain.

A New Navigation Mesh Build Process

The IncrementalBuilder, which provides the standard navigation mesh build process, has been completely revamped. See Getting Started Topics > An Introduction to NMGen in the documentation for a full overview. The two main changes have to do with the input to the builder, and post-processing.

The incremental builder now accepts two main data objects, an InputGeometry object that specifies triangle and area assignment information, and a ProcessorSet object that contains all the post-processors that will be applied to the build. There is also a variation of the builder designed for creating meshes that will be part of a multi-tile navigation mesh.

The input geometry object allows you to assign areas (surface type) on a per-triangle basis.

The post-processors are what give the the incremental builder its flexibility. If you want to modify the standard build, just use one of the pre-defined processors, or implement a new custom processor.

For example, to stamp areas into the mesh, you can apply AreaBoxMarker, AreaConvexMarker, and AreaCylinderMarker processors. Any object that implements the INMGenProcessor interface can be used to modify the build.

Creating navigation mesh tile data from the NMGen data has always been a bit of a bother. Several new utility methods and classes make it easier. (See the getting started documentation.)

Big Changes to the Unity Build Process

In v0.3 and earlier, the navigation mesh build was broken up across multiple components residing in the scene. The new build process is centered on a single asset stored in the project, not the scene. The behavior of this asset is then modified by other assets as needed.

All standard build assets are editor-only. They don't have any impact on scene size and the code is no longer included in the Unity project build. There is little to no bloat caused by navigation mesh build and configuration.

Almost all advanced build features such as tiling, area assignment, and off-mesh connections are available to non-coders through GUI editors. You can even do partial rebuilds of multi-tile meshes and background builds of large area meshes.

The Getting Started Topics > Getting Started with Unity in the documentation covers the new features.

This build process is highly flexible because of the input build. As with the IncrementalBuilder, the input build can be altered by all sorts of pre-defined and custom processors.

Now for the bad news for those who need to upgrade. As you can see, this is an entirely new build process. There will be a lot of work to upgrade existing projects to the new structure. One bit of good news: The navigation mesh save/load buttons can be used to save your old navigation meshes to disk, then load them into the new data assets as part of your upgrade process.

Bye Bye to the Unity Navigation Extensions

Creating navigation extensions is problematic. There are so many ways to implement navigation. Do you need light weight pathfinding for a large number of agents? Or do you need complex pathfinding with steering and collision avoidance? Do you need navigation planning only at the scene level? Or do you need a navigation system that persists information between scenes? The core navigation functionality supports these different models, but the v0.3 extensions are kind of clunky and limited. So I've removed them from v0.4. If need something to help you get started, check out the Sample Pack. It includes an example implementation in the Crowd Demo.

At some point in the future I may add navigation extensions back into the mix, but probably only as optional packages.


There are various other enhancements and changes included in v0.4, but that's it for now. Good luck, and sorry about all the moth carcasses.



Gotchas: Unity Plugins for Multiple Platforms

As mentioned in my last post, I was surprised by some of the platform compatibility issues I experienced with the CAINav code. In this post I'll cover some of the issues and how they can be resolved.

A quick side note before getting into the main topic: The first sample pack that includes source code has been released. It includes various demos and feature explorers that will help you get started using CAINav.

The Basics

I'm not going to cover the basics of Unity plugin development. That is covered well by the Unity documentation. There is nothing surprising on the C++ side. Just make sure you include the necessary conditional compile macros for platform specific code (e.g. "__declspec(dllexport)" for Windows) and don't use platform specific syntax (e.g. nullptr).

Special Cases for the iOS Platform

While you may be aware that Unity provides wide, but still limited support for the standard .NET libraries, you may not be aware that there are differences in the support provided for the different platforms. This is especially true for iOS.

Lets start with a simple plugin method that will work for the desktop and Android platforms.

[DllImport("cai-nav-rcn", EntryPoint = "dtnqFree")] 
public static extern void FreeEx(ref IntPtr query);

The DLLImport attribute indicates the name of the plugin (cai-nav-rcn) and remaps its name to a C# friendly version (dtnqFree to FreeEx). In this case the method frees a query object's unmanaged resources.

Issue #1: iOS does not support remapping the name of the extern method. All method names must match the C function name. So the the signature must be simplified to:

public static extern void dtnqFree(ref IntPtr query);

Issue #2: iOS requires the custom plugin name __Internal. This makes the iOS signature incompatible with the other platforms.

One easy way to handle this is using conditional compilation as follows:

internal struct InteropUtil 
    public const string PLATFORM_DLL = "__Internal";
    public const string PLATFORM_DLL = "cai-nav-rcn";

This allows standardized method signatures throughout the rest of the code. Our example is altered as follows:

public static extern void dtnqFree(ref IntPtr query);

Issue #3: With compile time differences between platforms, how do you deploy the C# code?

Due to the incompatible code, just as with the plugins, you an no longer use a single pre-compiled .NET DLL for all platforms. There may be other options, but the easiest is to drop the use of pre-compiled .NET DLL's and distribute the C# code directly to the Unity project. Unity will then decide which type of build to perform.

Since CAINav targets the Windows platform, I chose a different method. The main Unity package contains pre-compiled DLL's, but the source code is organized so the C# code can be easily dropped directly into a Unity project.

Oh No, What About Serialization

If you are using Unity serialization for everything, then there is no problem. But that may not be possible. Often a plugin object contains references to unmanaged memory. Also, Unity doesn't support serialization of custom structures or unsigned primitives such as uint, ushort, etc.

You may be tempted to implement custom serialization based on the ISerializable interface. But that isn't cross-platform compatible since your iOS platform uses a different run-time DLL than the rest of the platforms. So you can't for example, serialize a Navmesh object in a Windows project and share it with an iOS project.

Since CAINav supports standalone use in .NET applications, it supports two serialization methods. The standard ISerializable interface, plus byte array serialization. Byte arrays can be serialized using the standard .NET serialization process and shared between all platforms.

An example of this is the Navmesh class. The Navmesh.GetSerializedMesh() method returns byte[]. This byte array can be serialized using either Unity or .NET serialization. One of the overloads of Navmesh.Build() can be used to re-create the navigation mesh from a byte array. This is how the BakedNavmesh component handles the serialization issue.

I'm sure there are other gotcha's. But this post should help you avoid some of the headaches involved in cross-platform plugin development.


CAINav 0.3.0: Path Corridors and More

CAINav v0.3.0 has been released. It is a 'big little' update.  There aren't a lot of new features, but the underlying structure has changed a lot.  

The full change log can be found in both the distribution package and the SVN repository.  But there are several changes worth mentioning here.

Two Boring Items

The NavManager Unity component has been retired and replaced with the NavSource component.  This is worth mentioning here because the functionality of the two components appears to be the same.  And they are pretty much 99% the same.  The difference is that NavSource only provides navigation resources.  It does not handle the CrowdManger.Update() method.  So if you use it you'll need to make sure you add code somewhere to manage the crowd manager. 

The documentation for the last release had some big holes, especially for the crowd manager and introduction to navigation.  That has been mostly addressed.  There is even some navigation related getting started code to hold you over until the new sample pack is released.

The New PathCorridor

The biggest new feature is the addition of the PathCorridor class.  (And U3DPathCorridor Unity extension.)

The NavmeshQuery class contains almost all the pathfinding features needed to hand roll your own navigation solution, whether you just need a list of waypoints or you want to implement complex local movement and steering.  

If you want to manage steering for crowds of agents, then you can use to the CrowdManger.  The crowd manager is great, but it requires that you give it a lot of control and can be overkill for certain situations.

The path corridor fills in the middle ground.  It takes an initial path of polygons (a corridor), then helps you manage it without worrying about locomotion inaccuracies, floating point errors, a moving goal, or any of the other common pathfinding gotchas that make moving along the path difficult.  

Definitely take a look at this new class.  It can help you get rid of a lot of your path management code.

Now, Multi-Platform Friendly

This is where the 'big' comes in, even though most of it is hidden.

CAINav is still supported only on Windows, and is likely to stay that way as long as I don't have a way to validate it on other platforms before release.  But my goal is to keep it friendly for use on the other Unity target platforms

That goal is now much closer to being  met due to a lot of work by Dan Treble down in Australia.  Dan, who is working on an game called Quick Quest, went through the pain and suffering of getting CAINav working with Unity on iPhone and Android.

I expected some minor adjustments to the C++ code.  The surprise was the C# code.  I'll cover that in detail in a separate post.  For now, suffice it to say that the C# syntax for Windows and iPhone plugins is not compatible.

You will have to build your own native libraries.  And for iPhone you will need to copy the C# code directly into your project.  But due to Dan's feedback the CAINav code base should now be useable on both Unity iPhone and Android. The documentation includes some tips.

In closing, here is a much nicer navigation mesh visualization than I can produce, courtesy of Dan:

Until next time, take care of the bobcats.


A Quick Death and Building a Sample Pack

I was just browsing the Unity roadmap for 2011.  Oh look!  Navigation mesh generation, pathfinding, and local steering is planned for version 3.5!  The fact they they are adding built-in pathfinding isn't a big surprise.  They've been advertising for AI programmers for a while now, and the first task for AI is almost always pathfinding.  What I'm surprised at is that we may get it by the end of the year.

So, CAINav may have a lifespan of only about 6 months.  At least in Unity.  Luckily, most of my reasons for creating CAINav still apply.  For example, it has been a great project for becoming comfortable with C++, .NET/C++ interop, and Unity plug-in development.

Don't worry, I'm not halting work on CAINav.  Even if it dies with Unity 3.5 I still need its functionality now.  And there is still a lot of good exploration and personal training benefit to continuing development.

On that front, I've been experimenting with CrowdManager. (Local steering.)  It is nice.  When I add animation and locomotion, the agents look quite natural.  Better locomotion handling, such as the ability to side-step and back away, rather than just turning, and it will look great.

The big thing to remember about CrowdManger is that it isn't a silver bullet.  It is one part of the navigation puzzle and has its limits.  Don't succumb to the temptation to just add agents, set targets, and expect it to do everything for you.

It won't do long distance planning.  You will need to implement that separately. In my prototype I plan the long distance path, perform a partial string-pull, then feed CrowdManager a target several waypoints out from the agent's current location.

You also have to build in some edge case handling, such as when slow moving agents meet head on at corners.  They can block each other.

And remember, CrowdManager isn't meant to be used with large crowds.  The goal is to support up to 20 agents in a moderately complex environment, and that seems to be working out.

If you want to see CrowdManger in action, it is available in the new SamplePack.  This is how I'll release most demo's, tutorials, and samples in the future; packaged together in one download.

The demo allows you to add up to 25 agents to the scene and watch their behavior as they wander around at different speeds.  Clicking on an agent will toggle it's debug visualizations.  So you can see the world as CrowdManger see's it.

Still no sample code I'm afraid.  Beside the fact that I am still learning the best ways of using CAINav, there are some licensing and format issues I need to figure out for the models, animations, and support code.

Enjoy the new demo, and stay away from Arizona.