Ben Lowing from the team of Mercuna talked about their AI navigation solution that provides efficient pathfinding, obstacle avoidance, and other features for characters and vehicles.
About the Team
My name is Ben Lowing and I’m the founder/CEO of Mercuna, a small team of specialist developers based in Edinburgh, Scotland, focusing on advanced AI navigation for games. My co-founder, Mike Bell, and I started the company with the aim to develop high-quality AI middleware that filled what we saw as a gap in the market.
We had previously worked together on general game AI and built AI for titles including Star Citizen, Lichdom: Battlemage, Wolcen: Lords of Mayhem, Descent: Underground, Aquanox Deep Descent and Miscreated. During this time we had noticed that there were a lot of solutions for character AI, but for other kinds of agents, particularly flying animals and vehicles, there was a lack of tools for navigation.
Mike and I have known each other for years, we met at university, where we bonded over our shared passion for space games and creating games together. Afterward, we went in different directions: Mike to develop telecommunications software and I went into academia as a computational astrophysicist. A decade later when Mike had the opportunity to get into game development, he invited me to join him. It was fantastic to work with Mike again as we both love finding elegant solutions to complex problems, so it’s no surprise that we ended up with a company designed to do exactly that.
Our team is rounded out by Grant Murray who oversees sales and marketing and Peter Creasey, leading our research efforts.
How Navigation Systems Work
In games, the decision making logic decides where an AI should go, and it is then the job of the navigation system to work out how to get there. Traditionally, work on game navigation has focused on humanoid characters, as these are the most common types of AIs in games. For the past two decades, navmeshes have been the most popular approach for character navigation.
However, for all types of AI navigation, navmesh-based or otherwise, the underlying method is generally the same. A simplified representation of the game world, i.e. a navigation graph, is generated that connects all the areas/surfaces an AI can move on. The navigation graph can then be searched to find connected routes between points. This is commonly done using the A* search algorithm, which is chosen as it is fast and is guaranteed to find the shortest route.
Steering uses the resulting paths as a guide of where to move. Some smoothing may be applied to make the movement look more natural, but if the agent strays from the straight-line path segments, it can no longer be sure it won’t stray into a wall. Finally, dynamic avoidance is applied to stop agents from hitting into each other. This is usually done by looking at the velocity of each agent and adjusting just enough to avoid collisions. Getting obstacle avoidance working robustly, while still looking natural is often surprisingly hard.
Most game engines, including UE4 and Unity, contain an implementation of a navmesh-based character navigation system, often based on the open source software Recast. However, navmeshes are confined to the ground, so don’t work for 3D navigation (i.e. flying or swimming), and they don’t work well for AI types that have additional movement constraints such as animals and vehicles. This is where our solutions come in.
Octree Pathfinding Method for Flying Agents
Navmeshes are ground-based maps, so they are not well suited for flying and underwater AI. Simple solutions can simulate 3D navigation by adding a height vector to navmesh-based navigation, but such solutions cannot recognize anything above the flat plane of the navmesh, which means the AI cannot navigate over or under obstacles. For dragons flying over bridges, or drones flying down tunnels, a proper 3D solution is needed.
Based on the pioneering work by Daniel Brewer, Mercuna uses a 3D octree, which maps the entire navigable space of the level and allows unconstrained navigation across in three dimensions. Similar to ground-based navigation, we construct a 3D navigation graph by voxelizing the world geometry (i.e. dividing it into small cubes) and working out which cubes are empty and therefore navigable, and which contain geometry (e.g. a bit of wall) so are unnavigable. The results are stored in a sparse voxel octree. We use a modified version of A* search to find paths through the octree.
Due to the extra dimension, pathfinding through 3D octrees is more computationally expensive than through 2D navigation graphs, so making the middleware run fast enough for use in large games has been a big challenge for us. This is something we have kept coming back to, making incremental improvements and have finally reached a performance level we are pleased with. The methods we have used to achieve this include a combination of doing all heavy computation asynchronously (i.e. in background jobs), using hierarchical pathfinding for long-range paths and low-level CPU specific optimizations. That said, we still have a few ideas left to try in the future.
In addition, we have extended the original octree pathfinding method to meet the needs of AAA games, by adding advanced features such as octree merging/demerging to allow level streaming and runtime generation. Beyond pathfinding, we have implemented a sophisticated steering system that we are very proud of. Most people concentrate on the pathfinding aspect when they think of navigation, but path following is just as important. Our approach takes the straight-line path and fits smooth cubic splines through the points to create much more natural curves. We then check these splines against the level geometry to ensure agents don’t accidentally clip walls.
Navigation Solution for Animals/Vehicles
Now that our 3D navigation software has reached a point we are happy with, we have more recently started to look at other kinds of neglected navigation, mainly that of animals and vehicles. The navigation used for characters doesn’t work well for these types of agents due to their additional movement constraints.
Unlike characters, vehicles are limited in how quickly they can change speed and direction. This is also true to a certain extent for quadruped animals which, when moving at speed, prefer to make gentle turns. The other big difference for vehicles and animals is their shape. Characters are usually modeled as circular for the purposes of navigation, whereas animals and vehicles are often long and thin in shape and therefore can fit through gaps that are wide enough for their width, but not their length. A circle is a bad approximation for this shape and prevents AI from moving through tight gaps.
To solve these problems we have taken a step back and instead of using the usual navmesh, started from an older approach based on a navgrid, stored in a multilayer quadtree. Using a grid rather than a mesh has the advantages that it allows both finer grain spatial searches and information about permitted orientations to be recorded - e.g. for a grid cell next to a wall a car might be fine if aligned with the wall, but couldn’t get that close if aligned perpendicular to the wall.
The grid, therefore, allows us to use a sophisticated ‘kinematic’ search that accounts for acceleration, turning limits and permitted orientations during the actual pathfinding, so that that AI finds a much more intelligent path that is realistic to the route a driver, or animal, would take. Rather than trying to slowly move through difficult and winding routes, a car might drive around a group of obstacles, which while further, would be quicker.
This is still a project under development, but we have had some very exciting results so far. We have recently received an Epic MegaGrant towards the development and aim to release the first version in Q3 2020.
Tech Behind Mercuna
The basics of AI navigation are well established and we don’t want to waste time reinventing the wheel. Therefore our approach is to take traditional navigation methods and build the next generation of AI technology upon them. This can take the form of adding more advanced features on top, such as we have done for 3D, or this may involve taking a step back and experimenting, as we have done for Off-Road navigation. Our goal is to offer developers new capabilities and ultimately new gameplay possibilities so that they can realize their visions and not be constrained by the underlying AI technology.
For 3D I think it is a combination of the ease of use and the advanced features that make our middleware stand out. Developers are often tempted to write their own 3D navigation solutions as the engines don’t offer one. What they don’t realize is that the time to create an octree based pathfinder might only be a few months of work, but adding all the extra features they will need (level streaming, runtime regeneration, etc.) and getting good enough performance takes a lot longer. We don’t want them to waste that time - instead, they can add Mercuna to their project and get on with writing their game. We plan to continue to add features and want to get it into a state where anyone with flying or underwater AI uses Mercuna 3D Navigation, no matter what their requirements are.
For our new Off-Road middleware, I believe we are doing something brand new. Navmesh-based solutions don't allow the kind of more advanced pathfinding searches needed for off-road AI. I think this is one of the roles of middlewares, to take a step back and invest in novel solutions that have much greater potential than anything currently available to studios. Middlewares should help studios avoid technical dead-ends, or having them spending more time and money trying to improve something with diminishing returns.
Ultimately, we’d love to see our tech being used to open up new areas for AI gameplay. Skies, lakes and off-road areas don’t need to just be beautiful backdrops. AIs and NPCs can go anywhere now!
Incorporating Mercuna into Workflow
Our Mercuna middlewares are designed to be very easy to get up and running, but also very adaptable so that developers can configure it to work how they need. The aim is to make the middlewares look as much as part of the engine as possible so that users don’t have to learn yet another new system. If they know how to use UE4, then they will know how to use Mercuna.
The usual workflow would be that the team’s programmer integrates Mercuna into their projects. This can be done in as little as 5 minutes and they can very quickly have agents flying or driving around the game world. Designers will then tune the agents' parameters in Mercuna to ensure their movement matches the style of the game so that birds fly like birds and not like spaceships.
Mercuna is then available as a tool within the engine that can be used when building AI. For each level with AI, a navigation graph will need to be set up and generated. Generation is usually done during level design time, as the levels are constructed the navigation graphs can be built through a menu option in the editor and then saved as part of the level. For games with procedural maps or dynamic worlds we also support runtime generation of the navigation graphs. This allows AIs to find new routes when doors open or walls are destroyed.
We also provide a set of debug tools as part of the middleware - they allow both programmers and designers to understand what is happening and why. If an agent can’t get somewhere, visualization of the navigation maps allow users to check for issues, and nav testing actors allow them to create test paths and see problems. Again, our goal is to make things as easy as possible for users.
We’ve always wanted to develop Mercuna into being a suite of AAA-quality navigation middlewares and our recent Epic MegaGrant has allowed us to move into off-road navigation. The immediate aim for Mercuna Off-Road Navigation is to get it to the same AAA standard as our 3D Navigation middleware: with all the features studios need, being easy to use, within performance limitations and, most importantly, ensuring it is stable and does exactly what we claim. Good middleware needs to just work.
The most exciting development is that we’re writing both products to be compatible so that we can give you one navigation system that handles all non-humanoid AI. When we’ve got that, it’ll be much easier for games to add different types of AI to their game and add gameplay to different parts of levels. It could really open up the game to new, unbounded experiences. Our eventual goal is to combine both products within one AI so that it can both move on the ground and fly.
Once we’ve got a feature-complete navigation middleware for all non-humanoid AI, we want to expand into other areas of game AI. Our vision is to make AI as easy and quick as possible for studios to do so that developers can stop spending their time on background tech and focus on making awesome games. As game worlds get larger, they need to be populated by interesting and convincing AI to be really brought to life. I really think AI is going to be the game-changer over the next few years.