DonAI Navigation — 3D Pathfinding for Flying Enemies

The Problem

The Break of Day has flying enemies. Unreal Engine’s built-in navigation system (NavMesh) is designed for ground-based agents — it projects walkable surfaces onto a 2D mesh. That’s useless when your enemies need to fly through 3D space, dodge obstacles, and chase the player across vertical terrain.

I needed something that could handle true 3D pathfinding: volumetric, dynamic, and performant enough to run dozens of flying AI simultaneously without killing the frame rate.

Finding DonAI Navigation

After searching for ready-made solutions, I stumbled upon DonAI Navigation — a free, open-source plugin by Venugopalan Sreedharan (known as VSZue on GitHub). He originally built it for his own game Drunk on Nectar and released it to the community under the MIT license. The plugin is also available on the Epic Marketplace.

This man built a complete 3D voxel-based pathfinding system and gave it away for free. Absolute legend.

Porting to UE5

There was a catch — the plugin was last maintained for UE 4.19/4.27, and I needed it running on UE 5.5+. The original repository hadn’t been updated since early 2023.

I forked the plugin and made the necessary changes. Most were straightforward:

• Plugin manifest update — removed the old EngineVersion field and deprecated WhitelistPlatforms terminology
• Include path fixes — UE5 moved platform headers under subdirectories (AllowWindowsPlatformTypes.h → Windows/AllowWindowsPlatformTypes.h, same for Queue.h → Containers/Queue.h)
• Reflection macro migration — UProperty* was deprecated in UE 4.25 and replaced with FProperty*
• Build configuration cleanup — removed bEnableShadowVariableWarnings and Win32 platform entries that UE5 dropped
• Removed precompiled binaries — the old UE4 .dll/.lib files in Binaries/ had to go, everything compiles from source now

Nothing earth-shattering, but enough friction that you can’t just drop the original plugin into a UE5 project and hit compile.

If you need DonAI Navigation for UE5, feel free to use my fork — but remember the gigachad who created the original plugin and give him the credit he deserves.

How It Works

The Voxel Grid

DonAI Navigation divides the world into a uniform 3D grid of cubic voxels (default size: 100 units per side). Each voxel is a simple data structure tracking its grid coordinates, world position, and a NumResidents counter. If NumResidents == 0, the voxel is navigable. If anything occupies it — a wall, a platform, a dynamic obstacle — the counter increments and the voxel becomes blocked.

The grid dimensions are configurable (XGridSize, YGridSize, ZGridSize — default 30 each), defining the navigable volume around the grid origin.

For pawns larger than a single voxel, the system uses collision profiles — a set of voxel offsets representing the full volume the pawn occupies. When checking navigability for a large enemy, all occupied voxels must be clear.

A-Star Pathfinding in 3D

The core algorithm is A-star, adapted for a 3D voxel grid.

Each voxel connects to up to 18 neighbors:

• 6 direct neighbors — along each axis (forward, backward, left, right, up, down)
• 12 diagonal neighbors — combinations of two axes (e.g., forward+up, left+down). A diagonal neighbor is only reachable if both intermediate axis-aligned voxels are navigable, preventing corner-cutting through walls.

The heuristic is straightforward Euclidean distance from the neighbor to the destination. Combined with the uniform movement cost (voxel size per step), this gives the standard f = g + h priority calculation.

After finding the raw voxel path, the plugin runs a line-sweep optimization pass — starting from each waypoint, it attempts to skip ahead to the farthest directly reachable waypoint via a collision sweep. This smooths the staircase voxel path into a much more natural trajectory.

Async Execution and Task Budgeting

This is the part I find most elegant. The plugin doesn’t just run A-star and hope for the best — it has a proper task budgeting system that prevents pathfinding from ever blocking the game.

In multi-threaded mode (the default), a dedicated worker thread runs at below-normal priority, communicating with the game thread through lock-free queues. New path requests go in, completed paths come out — no locks, no stalls.

The budget system works like this:

• There’s a configurable maximum iteration count per cycle (default: 1000 for multi-threaded)
• This budget is divided equally among all active pathfinding tasks
• If there are more tasks than budget, each task gets at least 1 iteration, and only the budgeted number of tasks are processed per cycle
• Each task has a query timeout — if the timeout expires, the system returns whatever it has: the unoptimized path if the goal was found, or a timeout failure

In practice, this means a flying enemy will simply wait for its path if the system is under heavy load. It doesn’t block execution, doesn’t cause frame drops, and doesn’t affect other game systems. The worst case is a brief delay before the enemy starts moving — completely acceptable for gameplay.

The plugin also supports single-threaded mode for simpler setups, running pathfinding and collision tasks during Tick() with a lower default budget (500 iterations per tick).

Ready-Made Behavior Tree Integration

DonAI Navigation ships with BTTask_FlyTo — a Behavior Tree task node that wraps the entire pathfinding workflow. It handles path requests, waypoint traversal, dynamic collision re-pathing, and even observes Blackboard variables for target changes. For my flying enemies, this was essentially plug-and-play with the existing AI behavior trees.

The Result

The plugin handled my flying enemies exactly as I needed — smart pathfinding through complex 3D environments with zero performance impact. The voxel-based approach means obstacles are naturally handled, the A-star algorithm finds efficient paths, and the budget system keeps everything running smoothly even with multiple flying enemies active simultaneously.

Sometimes the best engineering decision is recognizing when someone else has already solved your problem better than you would have.