Posted On: 2022-03-21
While Autonomous Agent Movement (aka. AAM) can be a valuable design tool, it doesn't always fit neatly into every project. AAM can be performance-intensive on its own, and certain elements of a project's design can amplify (or reduce) the performance costs of using it. For today's post, I'll take a look at a few of these - some of which apply to my project and others of which are simply common generally.
The first challenge is a simple challenge of scale. Calculating autonomous movement in any project has a cost associated with it (time determining a path, turning that path into character movement, etc.) The more characters that are using AAM, the more significant that cost is. A project just starting out with AAM, for example, may have no problem with one character, but find everything slows to a crawl when trying to use AAM to move a whole city's worth of characters.
Fortunately, this is such a common problem that many pre-built pathfinding tools are optimized to lower the cost per agent. Generally these optimizations scale best when agents' capabilities are identical: the more two agents have in common, the easier it is for them to share paths. Designers trying to take advantage of these optimizations might smooth over small differences in characters - such as using the same collision shape and size for all agents (regardless of the visual shape/size of the individual characters.)
The most computationally expensive part of pathfinding is (usually) creating the node graph. This is a (metaphorical) map that agents use to plan paths, and, since it's so expensive, it's almost always cached. If the environment is static, this can be a great approach: the node graph can be generated way ahead of time, and it will always be correct. If the environment is dynamic, however, this can become a problem - since now the cache is "invalid", and all the agents stop planning and wait until a new/updated node map is created.
The naive way of updating the graph is simply to throw out the old one and create a brand new one. If the graph is simple and small (ie. a 20x20 grid), this can be a perfectly fine solution, as it will be done before anyone even notices. If the graph is particularly large or complex, it may take a while (ie. seconds) to generate, potentially causing highly visible problems (ie. application or agents completely freezing while the new graph is generated.) Fortunately, the impact can be reduced through good design, such as by carving the graph into pieces and only updating the pieces that contain a change.
A lot of pathfinding solutions arrange the nodes of the graph in a grid: the environment is broken up into equal-sized pieces (usually squares), with each node representing a single piece. Every node in the grid has the same set of connections (ie. the four cardinal directions), which makes walking the graph consistent and predictable. Grids' predictability makes it easy to predict the memory requirements of caching the graph, and can support many simpler pathfinding algorithms without becoming unsolvable. While convenient to use, some environment designs underperform when represented as a grid: large open areas containing small obstacles, for example, are a poor fit for grids, as they risk wasting a lot of space/time walking through the many nodes in the open area*.
When grids don't work, it's common to use a navigation mesh, which is basically a 3D representation of the navigable space*. Navigation meshes are more flexible, which makes them great at handling environments with obstacles of wildly varying sizes/shapes, but that flexibility often comes at a cost: creating a navigation mesh is often quite computationally expensive. When the environment is static, that cost can be hidden from the player (ie. the navigation mesh is created at the same time as the level, and it never changes), but when the environment is more dynamic, the costs of creating/updating the navigation mesh may outweigh the benefits of using it.
Many pathfinding tools and algorithms assume that the environment is stateless - that is, the range of possiblities for where a character can go from a particular point is always the same, no matter how they got to that point. When a project attempts to simulate gravity and jumping, however, that assumption cannot hold. A character that is landing from a jump will have a different set of possible directions they can go (ie. down, down-left, down-right) compared to a character that is rising during a jump (ie. up, up-left, up-right) - even if they are both passing through the exact same point. Depending on the tools/frameworks used, developers may find themselves fighting against systems - or reinventing them completely - as they try to support stateful pathfinding.
Beyond jumping, there's a whole host of common, stateful movement properties that might pose problems for pathfinding. If you need to account for the direction a character's facing or their turn radius or momentum, you may find the pathfinding becoming much more complex. Since stateful movement properties are great for adding depth to player-controlled movement/actions, there is something of a conflict between creating a character that is fun to control, and creating a character that AAM can control*.
Making a good decision often involves weighing different options and comparing relevant information. For information that's immediately available (ie. what's the agent's current HP value), the cost is usually pretty low. For information that's tricky to get (ie. how long would it take to heat a room given its size and insulation properties), the cost may be non-trivial. When a "good" decision involves comparing a lot of such information (ie. which room, from all buildings in walking distance, would warm up the fastest), the performance costs can pile up.
The cost of deciding is particularly nasty, as it often grows incrementally over the course of a project. Every new feature or capability can add dozens of new options to an already large pool - so a system that performs great at the start may gradually slow as features pile up, potentially reaching the point where the largest cost of any new feature is what to rework/cut to keep the AAM systems from freezing up. Fortunately, this risk can be mitigated through good system design. Using asynchronous/non-blocking decision-making can keep framerates smooth while agents plan, and some decision-making patterns (like Utility systems) are designed to reduce complexity and number of choices in a large-scale project.
Taken individually, these challenges are surmountable: between out-of-the-box solutions and writings from others who've tackled the same problem, there's always a way forward. When a project has multiple of these challenges at once, however, that may no longer hold true. I've been keenly aware of this in my own project, as many of its challenges encourage using conflicting approaches. A wide variation in size/shape of environment geometry encourages using navigation meshes, but the frequency with which the environment changes encourages using grids. The stateful elements of the game's mechanics (ie. jumping) push me to dig in and make changes myself, but the sheer size of the graphs means I really benefit from others' more complex designs (ie. heirarchical graphs and separately updating areas.)
Fortunately, with a bit of compromise and some handy tools, it's looking like I will be able to use AAM in my project, despite the many challenges it faces. The next (and final) part in the series will dive into specifics on this - though it won't be my next post*. So, tune in next time for a different topic altogether - along with (hopefully) some news about when that final part in the series will arrive.