3D Pathfinding for Flying and Swimming in Games

Navigating three-dimensional environments presents a unique challenge in game development, as flying and swimming entities are not bound to a flat, two-dimensional ground plane. To handle this freedom of movement, pathfinding systems must transition from traditional 2D navigation meshes to volumetric spatial representation and dynamic flight calculations. This article explores how developers adapt pathfinding for 3D environments using spatial partitioning, modified search algorithms, and steering behaviors to create realistic movement for aerial and aquatic creatures.

Volumetric Spatial Partitioning

Traditional pathfinding relies on a 2D Navigation Mesh (NavMesh) walked on by ground characters. For 3D entities, developers must represent the entire volume of open space. The most common way to achieve this is through spatial partitioning techniques that divide 3D space into searchable nodes.

• 3D Grids (Voxels): The simplest approach is to divide the game world into a 3D grid of cubes (voxels). Each voxel is marked as walkable, blocked, or open. While easy to implement, uniform 3D grids require massive amounts of memory and CPU power to search.
• Octrees: To optimize performance, developers use Octrees. An octree hierarchically subdivides 3D space. Large volumes of empty air or water are represented by a single large node, while areas near obstacles and terrain are subdivided into smaller, highly detailed nodes. This drastically reduces the memory footprint and speeds up pathfinding calculations.

3D Pathfinding Algorithms

Once the 3D space is partitioned, pathfinding algorithms must navigate the node network. The standard A* (A-Star) algorithm is easily adapted to 3D by adding a Z-axis to its heuristic distance calculations (typically using 3D Euclidean distance).

However, basic 3D A* paths can look jagged and unnatural for flying or swimming creatures. To solve this, developers use Theta* (Theta-Star) or Lazy Theta*. These “any-angle” pathfinding algorithms perform line-of-sight checks between non-adjacent nodes. If a straight line of sight exists through open 3D space, the algorithm skips intermediate nodes, resulting in smooth, direct, and natural-looking flight paths.

Dynamic Local Avoidance and Steering

Global pathfinding calculates the rough route from point A to point B, but flying and swimming entities must also react dynamically to moving obstacles, other agents, and sudden changes in the environment.

• Steering Behaviors: Developed by Craig Reynolds, steering behaviors apply forces (such as seek, flee, and obstacle avoidance) to the entity. For 3D entities, these forces are calculated as 3D vectors. An entity might follow a global path but continuously apply a “separation” force to stay away from nearby flock members, or an “avoidance” force to steer clear of an oncoming projectile.
• Raycasting and Sensors: To detect immediate obstacles, 3D entities often cast virtual “rays” (raycasts) in front of them in a cone shape. If a ray intersects with an object, the entity calculates an evasive steering force in the opposite direction.
• 3D Avoidance Algorithms: More advanced systems use 3D Reciprocal Velocity Obstacles (RVO) or Optimal Reciprocal Collision Avoidance (ORCA). These algorithms allow multiple flying or swimming entities to navigate around each other without colliding by predicting future trajectories and sharing the responsibility of avoiding one another.

By combining volumetric Octrees for global path planning, any-angle 3D algorithms for smooth routing, and real-time steering forces for local avoidance, game developers can create highly convincing and performant navigation systems for any entity that flies through the air or swims through the deep.