One of the most fundamental problems facing agents in game worlds is how to move to a specific location. While a variety of solutions exist for characters moving on the ground, for agents navigating freely in three dimensions, such as drones, submarines, or characters with jetpacks, this is a much harder problem. This post looks at how Mercuna 3D Navigation solves this difficult issue and helps bring flying AIs to games.

The simplest approach to a systematic navigation solution for such agents is to put a 3D grid across the world and record in each cell in the grid whether there is anything in it that would impede the navigation of your agents. Building this grid produces a low resolution voxel representation of the game world, similar to what you see when playing Minecraft, except that each voxel can only be full (unnavigable) or empty (navigable), as shown in the image below. Once you have, what is in essence a simplified navigation map, you can search the grid to find a connected sequence of empty voxels that defines the traversable path between a start and end point. Most commonly the A* algorithm is used for the search, as it is guaranteed to find the shortest path, and performs well.

In order to produce the voxel representation of the game world the game’s physics system must be interrogated to discover whether there is an obstacle in each voxel. The simplest approach here is to query the physics system for each voxel to ask whether it is empty or not. A more sophisticated approach that’s more efficient when generating voxel data for large volumes is to gather all collision meshes overlapping the large volume and then rasterize the polygons into the 3D grid.

A 3D grid representation forms a great starting point for navigation, but in practice uses too much memory for reasonable sized levels, and searches for anything but trivial straight line paths need to explore millions of voxels to find routes around obstacles. Part of the problem is that the extra degree of freedom in 3D space compared to 2D pathfinding, mean there are more options to explore at each step of the path. However, we can make significant gains by combining adjacent empty voxels together into single large nodes in our search graph. One simple way of achieving this is with a sparse voxel octree – a data structure commonly used in 3D graphics processing. Mercuna uses enkiOT, a high performance, sparse octree licensed from Enkisoftware.

In an octree, the world is recursively divided into cubic nodes. Starting from a single large node that covers the entire world, each node is considered to be either completely empty, called a leaf node, or if it contains any geometry is subdivided into eight half sized cubic nodes. These smaller nodes are then themselves again either just leaf nodes, or further subdivided into eight even smaller nodes. Large empty regions can therefore be described by a few large leaf nodes, and only where in the game world there is lots of geometry will there be a need to subdivide into lots of nodes. Concentrating detail only where needed provides both substantial memory savings and massively improves search performance.

Using an octree for 3D pathfinding is an approach pioneered by Warframe, and Daniel Brewer gave an excellent talk on its advantages at GDC 2015 (Getting off the NavMesh: Navigating in Fully 3D Environments). It provides a big step towards making 3D pathfinding feasible in games. However, often just using an octree on its own is still not enough. Even in just moderately complex environments the huge number of voxels that need to be explored to find routes between far apart points quickly becomes unmanageable. Long, or even just medium range pathfinds end up taking too long to be useful.

The first step to making pathfind cost reasonable is to tweak the search to prefer to find paths that go through large cells. Depending on your environment this can make a really significant difference, and although it means the search might occasionally miss an optimal route that goes through a very narrow gap, the tradeoff for performance is considered worthwhile. Similarly, A* performance can be improved in most cases by making the search “greedy”, so that nodes closer to the goal are explored first.

However, while these techniques improve the average case and allow medium range pathfinds to be completed in a reasonable time, longer range pathfinding can still take unacceptably long. Mercuna 3D Navigation solves this problem, by using hierarchical pathfinding (HPF) to allow pathfinding to be performed over long distances. In HPF, in addition to the octree, a second lower resolution version of the navigation map is constructed. Long range pathfinding is performed by first searching the lower resolution graph for an approximate route, and then using this to guide a search through the octree that refines the route. It is like using a country level map to find a rough route across the country, but then using more detailed street maps to navigate individual cities.

3D navigation is a harder problem than most people first think, and for a long time proper 3D navigation was considered to be too expensive, both in terms of development time and CPU cost, to be used in games. This frequently led to design compromises for flying agents, with the most common being developers forced to drop them from their design. However, through a combination of using an octree for the navigation graph and HPF for longer range searches, along with various other optimizations, we have been able to make navigating through complicated 3D environments practical and available to anyone who wants flying agents in their game.