Saturday, October 10, 2015

Taming Unity's Navigation System - Assumption Testing Part 1

So you need some pathfinding in your game huh?  Well, you have some options and of course some tradeoffs associated whatever you choose.  So real quick-like, what are the options?

1. Unity's native system
2. Aron Granberg's A* system
3. Apex Path
4. Quick Path
5. Simple Path
6. Simply A* (free)
7. Easy Path
8. Etc..... (several others available on the asset store)

That's a lot and unfortunately I don't have the time and money to evaluate each one and so I haven't explored all of these in much depth... with the exception of Unity's own native system.  However, I don't think I really needed to as I picked Unity's solution for a very specific reason.

PERFORMANCE #perfmatters


Performance really does matter, especially in more CPU intensive games where you have a very tight budget and can't afford to take a big chunk out for pathfinding.  Or, maybe you want to have hundreds of independently simulated units.  In any case, Unity's system has the advantage of being built with native code (C++) and optimized by the people who make the engine so we can expect it to perform well for most use cases. Check out the improvements made in Unity 5 here.

Any 3rd parties that provides this feature will suffer from the overhead involved in running .net scripts (C#/Unityscript/Boo).  At best, I've heard performance can be about 1.5x as fast. However,  once IL2CPP is fully deployed across all platforms this may be less of an issue (due to cross compilation to native code) for final builds but it will still hurt workflow in the editor which relies on .net/mono, not IL2CPP.

So that sounds great, it performs well.  How easy is it to use and how flexible is it to do whatever crazy things we wanna do?

Well, a core value of Unity is simplicity so it's no surprise that their system is relatively simple (and that's generally a good thing) but how flexible is it?

This is a deeper question and why the title of this post is called "taming".   Over the next few posts we'll be putting this to the test but for now let's just get our feet wet.

How do we use this thing?

1. Mark your scene objects to support navmesh creation (navmesh static)
2. Bake your navmesh (create it)
3. Add the NavMeshAgent component to any object you want to be able to navigate
4. Set up the agent's properties such as speed, acceleration, radius, etc...
5. (Optional) Give any objects that are obstacles the NavMeshObstacle component
5. Give the agent a destination and watch em go

If you're clear on all these steps read on but if not, check out Unity's tutorials of the whole process here: http://unity3d.com/learn/tutorials/modules/beginner/navigation

Also take a quick look at the main APIs we have to work with here:
NavMeshAgent
NavMesh

With that the API verbage is fresh in your mind, let's start exploring what's there and test any assumptions we might have.

Assumption #1


Setting the destination will immediately calculate a path on the same frame.

Test




Nope, generally not but Unity is pretty clear about this behavior.



In any case you should know what to expect or rather, you should expect to not exactly know what to expect.  Let me explain.  In a game I was working on during Summer 2015, I had implemented a squad based pathfinding system.  It was based around a "leader" unit that knew the full path from their current location to the destination and "follower" units who created micro-paths (small distance away) based on the leader.  Most of the time, things worked as expected but occasionally the "followers" would stand around for a while doing nothing until Unity finally calculated a path and they went on their merry way.  In some cases this took over 1 second resulting the in "leader" dashing off toward his destination while the "followers" well... did nothing.

The solution is to use a method the completes immediately when we request the path - NavMeshAgent.CalculationPath and NavMeshAgent.SetPath.  Here's an example:

NavMeshPath path = new NavMeshPath();
agent.CalculatePath(hit.position, path);
agent.SetPath(path);

This may be less performant since the calculation cannot be amortized across multiple frames (I assume Unity does something like this but would have to do more investigation to know for sure) but you are guaranteed to have a path immediately available.  Also, generally having deterministic logic in your game is generally a very good thing for design and debugging.

Assumption #2


NavMeshAgent.remainingDistance will always tell us how far we have to go.

Test




Hmmm.... remaining distance appears to be Mathf.Infinity until the agent becomes relatively close to the destination.  I guess that's not a value we can rely on.  If we really need that info we can calculate it ourselves by measuring the distance between each waypoint (NavMeshAgent.path.corners) and adding them all up.

What does Unity say about all this:


Ok, I suppose by unknown they mean that they haven't yet calculated it for us since we can obviously do the calculations ourselves.  Here's an example:

float distance = 0.0f;
Vector3[] corners = myAgent.path.corners;
for (int c = 0; c < corners.Length - 1; ++c) {
    distance += Mathf.Abs((corners[c] - corners[c + 1]).magnitude);
}


Assumption #3


hasPath will be false when the agent has finished pathing.

Test



Ok, so this one is tricky.  After a quick test you might conclude this to be true only to discover a case later when it is not.  If you leave the NavMeshAgent's settings to their defaults you'll notice that autoBraking is true (checked box in the inspector).  And, if you don't change that then you will be able to rely on the hasPath variable actually telling you when the path is complete.  Otherwise, you'll have to have some your own logic for determining when an agent should stop "pathing".

Now there is plenty more testing to be done but I thought I'd chop this up into separate parts in the hopes that I could actually release this to you rather than letting it collect dust in my personal collection.  Until then: