Notifications
Article
Custom Pathfinding In Unity
Updated 4 months ago
34
0
For Advanced AI And Spherical Worlds
Due to its ease of use and breadth of features, Unity is all but required for Indie developers. It's also become attractive for triple-A studios such as Blizzard and Bethesda, who chose Unity for the development of Hearthstone and Fallout Shelter, respectively. Unity has made many careers possible and streamlined production for some of the biggest names in the industry - and yet, its appeal continues to suffer as a result of bugs, oversights, and poor design choices. Despite being valued at over a billion dollars, Unity inexplicably struggles with essential systems like networking. Other systems arrive functional but with no clear roadmap, forcing users to wait years for missing features to trickle into the engine.
Pathfinding is perhaps the best example of a system introduced with severe limitations. One I contended with on a personal project was the inability to specify different radii for each agent type. This was crippling because radius determines how close agents can come to each other and obstacles, and ultimately, what areas of the level are accessible. Let's say you wanted tanks and infantry in your game. If tanks had the same radius as infantry, infantry would clip into tanks and tanks would clip into buildings. Since infantry are small enough to enter buildings, and tanks would be considered the same size as infantry, tanks would also be able to enter buildings! Probably not what you want.
Another issue I encountered, this time on a client's 2D beat 'em up, is that pathfinding was locked to the XZ plane…while 2D mode is locked to the XY plane. That’s right - two major systems were incompatible simply because they required different coordinate planes. It doesn’t get much dumber than that, folks.
Users often struggle against Unity’s limitations until they are forced to scale back their vision, hack together something liable to break at every turn, spend untold hours replacing entire systems, or turn away entirely. On my own project I chose the first option, accepting that all enemies had to be the same size and telling myself it was smarter to save bosses for the sequel anyway. My client was forced to turn back not because of technical difficulties, but because his art budget ran out prematurely. While I couldn't have gotten him the artwork he needed, nowadays there are fewer challenges and compromises when it comes to programming.
It's actually a great time to be working with navigation in Unity, considering how many features have finally manifested. Navmeshes now accommodate both varying agent sizes and arbitrary rotations, although you'll have to import the necessary code from GitHub. For some reason they don't consider it a priority to integrate these advancements directly into the engine, but the scripts are written and maintained by Unity Technologies. They also produced a series of video tutorials demonstrating basic setup.
For the majority of users, existing functionality is all that's needed. Still, there are scenarios where native pathfinding is insufficient or impractical. I intend to illustrate why, despite how far Unity's pathfinding has come in recent years, you might want to take option three I mentioned earlier and replace the whole dang thing. This post assumes readers have a passing familiarity with core concepts such as A* and navmeshes, but we'll explore these topics in detail later in the series. For the sake of simplicity, let's start with a look at grid-based A*.

Scenario 1

One of the major weaknesses of native pathfinding is a lack of support for flanking behaviors. Any sort of "behavior" is the domain of AI, and AI doesn't normally have a direct connection to navigation. What path is shortest between two points is more of an absolute truth about the environment; picking a destination and deciding whether or not to move there is a separate matter. Basic flanking doesn't require special considerations from navigation, since level designers can define intermediary waypoints and specify which agents will follow those routes. However, this case-by-case approach is limited, predictable, and time-consuming. What we're interested in is the general case, and this is where native pathfinding falls short.
The following screenshots are mockups of an agent flanking a stationary machine gun. (I like to picture this as a Troika encounter from Gears of War.) The friendly agent is green, the machine gun is red, and cover is blue. The machine gun has a limited firing arc, allowing it to fire only on orange tiles.
We want our friendly AI to pick off the machine gunner from relative safety, moving to the nearest white tile where it has line of sight while avoiding as many orange tiles as possible. It's common to mark an area as undesirable by increasing its weight, artificially inflating the total distance of paths through that area. The problem is that in Unity, it's only practical to adjust the weights of pre-defined volumes, not individual nodes (tiles or polygons) based on arbitrary criteria like line of sight. Since we have no effective way to indicate that orange tiles are dangerous, the naive path takes our soldier straight through the kill zone.
Whereas with proper weighting, the safest path looks like this:
Even if Unity allowed us to set the weights of individual nodes, we'd have another problem: The change would be universal for all agents, including those friendly to the machine gunner. Assuming there is no friendly fire, there’s no reason other enemies should avoid tiles the gunner can fire on. What we need in this scenario is a separate copy of weights for each team, and even this may not be ideal because it assumes knowledge of enemy positions is perfectly (and instantly) communicated between teammates.

Scenario 2

Advanced flanking isn't just for evading enemies; it could force a group of agents to spread out as they approach their target. This is where it becomes apparent that what we may really want is a copy of weights for each agent. An excellent case study is the castle water room in Resident Evil 4. At the start of this classic set-piece fight, two cultists flank around the pools on either side.
In the mockups below, blue tiles are pools of water rather than cover. The player is at the bottom and enemies are at the top, each one a different color.
Agent avoidance wouldn't help us much because it doesn't fundamentally alter paths; it only nudges agents so they gather or pass each other without clipping. All enemies would still approach down the middle.
Instead, let's modify weights on a per-agent basis. For each agent, all weights in paths belonging to other agents will be increased. The ideal solution is for magenta and orange to calculate paths first, which increases the cost of traveling down the middle for yellow and cyan, causing them to prefer farther but lower-cost nodes along the outer edges. The resulting paths look like this:
One issue is that if yellow and cyan select paths first, magenta and orange will be forced to pass them to take their paths. However, this is the least of our worries. A much bigger concern is that if one agent's path is influenced by other agents' paths, then you have to wait for each one to finish calculating before you can start the next. Considering how expensive and time-consuming pathfinding typically is (enough to have its own thread), this is a delay we'll need to address.
Perhaps the greatest problem of all is that, in reality, there would likely be too many tiles or too few polygons to coax the exact number of agents you want down a corridor. Fortunately, we have plenty of options for tackling this. One thing we can do is group agents together so they don't weight nodes in each other's paths, effectively allowing them to share nodes. A variation is to not apply weights by default, only doing so for agents that flag themselves as flankers and grouping them for shared routes. An alternative to grouping is incrementing the weight of a node for each agent passing through it, allowing multiple agents to use a node before it becomes too expensive. Agent-specific weighting also makes it possible to recalculate paths that are too short and throw out paths that are too long, although repeated calculations are another compelling reason to address performance.
Admittedly, our case study is trivial to script in Unity with waypoints, and it was likely done this way in Resident Evil 4. If predictable is what you want for set-piece battles, then scripted behavior is the easiest and safest choice. However, generalizing this scenario allows us to extend the behavior to more obscure encounters, like fighting through a series of hallways or back alleys where it's not clear which route the player will take and which routes should be used by flankers. We can produce even more nuanced behavior such as forcing agents to spread out between trees or pillars, flowing around them like water through a river delta.

Scenario 3

If you’re interested like I am in developing a specific type of game, another shortcoming of native pathfinding becomes obvious: It isn't designed for navigation around tiny planets in the vein of Super Mario Galaxy or Poly Universe. My goal is creating a pathfinding solution flexible enough that it can be adapted to this unique scenario. There's so much else to cover first, but sphere navigation is in the pipeline!

Conclusion

Pathfinding is one of the most ubiquitous challenges in game development, and also one of the most formidable. This is why it was such a relief when the system was added to the engine back in version 3.5. Although rife with limitations at first (in typical Unity fashion), enough features have been added over the years to meet the needs of most developers. Despite this, there are situations where the benefits of a custom solution would be tremendous. Unity's greatest strength, above all else, is a rock solid foundation on top of which you can build virtually anything you want, replacing entire systems if you have the need and the time. This is exactly what we'll be doing with custom pathfinding.
Next up, we'll dive headfirst into code with a fully functional demo of A* on a grid!
Brian Crandell
Programmer - Programmer
3
Comments