Synzza Star - Learning 3D Navmesh in Unity
Given Synzza Star's requirements of AI agents capable of autonomous navigation without player input, and given the previously discussed benefits of moving the project to 3D, I decided to finally try Unity's Navmesh system. This was my first time using this technology myself - I've been on projects before where other designers have created and configured a Navmesh, but before now I had never interfaced with it directly.
Creating the Navmesh
In my previous post, I actually gave a preview to this subject by showing a simple level I whiteboxed in Unity. Here it is again:
I'm no level designer, but my goal was to make a simple level which had a few features that can stress-test a navigation AI. This is both to learn how Unity's Navmesh works and to give me confidence that whatever geometry I'd later like to design for levels shouldn't present too much of an issue from a navigation standpoint.
Here is the level again with the Navmesh baked and applied to the level:
The next step is to create a Navmesh agent to move around the level. To create a test case which is slightly more pertinent to my needs, I'll also create a basic player controller that can exist in the level purely as a target for the AI to move to. That, together with these static destination points, should give me a robust enough test to see how the AI operates:
All that remains now is to write the actual code that provides the AI's Navmesh Agent with targets. Some of it is standard boilerplate I won't waste your time with, but I did want to touch on a few interesting notes and lessons I picked up while coding this.
Programming the Navmesh Agents
The first note relates to the inner workings of Unity's Navmesh navigation, namely that it uses the A* algorithm to calculate a path whenever a new target is assigned. This is relevant because Navmesh agents consider "targets" to simply be points in 3D space, not references to Unity Transforms.
In other words, if I want an Agent to target a moving object, say a player, then I will need to update the target more than once while the Agent is still moving. This isn't great because that will mean Unity will have to throw away at least part of the Agent's current path and recalculate it again. So, I'd like to minimize the number of times these updates have to occur.
Nothing too fancy here. We simply check if the player has moved more than a single game unit away from where we last recorded them being, and only then do we update the destination. It's a simple workaround, but it's an important performance that can be easily overlooked, and sometimes it's nice to pick the low-hanging fruit.
Brief aside into Magnitude Land
By the way, in case you're wondering why I used "magnitude squared" of the difference vector rather than just the magnitude, this is also a slight optimization, though in this case I accept that it may not be saving me a ton. Basically, calculating the magnitude of a vector requires a square root, which is comparatively much more expensive arithmetic operation than everything else. If you're not familiar with the formula, here it is:
Now if you omit the square root operation, you're just left with multiplications and additions, which are much less expensive. We know from the above formula that whatever the sum of all the components squared evaluates to happens to be the square of the magnitude. It also just so happens that sometimes, the square of a vector's magnitude can be just as good of an approximation for what we need as the magnitude itself - such as in my case, where all I want to know is if the magnitude exceeds 1. It's a neat little optimization that can save some time.
Back to Navmesh Agents
Next, I'd like to talk about a design choice. I wanted the Navmesh Agents to select random targets to move to, but I didn't want them to be purely random. Specifically, I wanted to disallow the AI to select any of the last X targets its previously used, where X is a configurable number.
Seems simple enough, but it can actually be quite tricky to find an elegant design that achieves this. To restate the problem: Given a list of 3D points and an integer X, create an algorithm which ensures a random 3D point can be selected from the list without repeating any of the previous X return values. What would you come up with? If you'd like, try this problem for yourself, then you can come back here and compare notes with my solution.
Now I'll discuss my solution. Let's look at the code, and then I'll talk through it.
First, let's put things in terms of the prompt I gave above. `_positionalTargets` is the list of 3D points, specifically a 1D array of `UnityEngine.Vector3` structs, and X is indirectly defined as `_positionalTargets.Length - _validPositionalTargetCount`. Finally, I just have one more additional integer, `_positionalTargetSwapIndex`.
So what's the idea? Rather than needing to explicitly create a separate list or dictionary of used points, which would take up a lot of extra space in memory, we're going to "split" our array into two sections: elements before `_validPositionalTargetCount`, and elements after. The elements after are still physically in the array, but they are excluded from the random selection.
When a new target needs to be selected, it's selected with `Random.Range` and stored in `target`, then that element is swapped in the array with one of the elements after `_validPositionalTargetCount`. The exact element it's swapped with is determined by `_positionalTargetSwapIndex`. This is an integer whose values range from 0 to X - 1 and is sequentially progressed through this range every time a new target is selected. This is important because it ensures that each element behind the "valid positional target" wall always spends exactly X iterations there before being put back into the random selection range.
I like this system for its efficiency and simplicity, but there is a slight drawback. Given the current implementation, there are a few targets, namely the last X targets in the array, which can never be selected first, giving the AI a bias towards elements near the beginning of the array at the start of the game. It's something I can easily fix if I find it necessary later on, but I think it's a small price to pay for the elegance of this solution.
That's all I have for today. As a parting gift, enjoy this animation of the AI pathfinding exploring the level and chasing me around. If you enjoyed this technical discussion, stay tuned for future updates. Until next time, take care.
Comments
Post a Comment