This plug-in brings 3D navigation to Unreal Engine.
It's based off of this GDC talk, and this associated chapter in Game AI Pro 3.
The original implementation of the algorithm comes from https://github.com/midgen/uesvon, and was heavily refactored, improved, and integrated into UE's navigation system.
You don't have to use specific MoveTo functions in your code, but only the regular nodes you're already used to use for your 2D pathfinding queries.
Pathfinding queries are automatically executed asynchronously.
Regeneration of the navigation data is automatically done whenever you move objects in the scene, and asynchronously.
- A-Star
- Theta-Star
- Lazy-Theta-Star
- Refs:
- Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D
- A算法改进——Any-Angle Path Planning的Theta算法与Lazy Theta*算法
- PATHFINDING IN 3D SPACE -A*, THETA*, LAZY THETA* IN OCTREE STRUCTURE
- Theta*: A Simple Any-Angle Algorithm based on A*
You'll find more informations about pathfinding below.
You can choose to smooth the paths returned by the pathfinding using a catmullrom algorithm.
Debug visualization options which allow you to draw the different layers of the octree, all the free and / or occluded voxels, the active paths of the flying actors in the world.
There is a Pathfinding helper actor which adds visualizations of the steps used by the pathfinding algorithm in the navigation data. That helps to understand all the paths the algorithm explores before reaching the destination. It also prints out informations about the path, such as the number of visited nodes, to help you choose the best options.
There are currently a few limitations to the plug-in which may be addressed in the future:
- Although the navigation data is generated asynchronously, it's done on one thread only. Given the nature of the data (in an octree), it is possible to split the workload in 8.
- No out of the box support for level streaming. See below for how to handle level streaming in your project.
- Detection of the occluded voxels is currently done using the physics engine overlap detection. It should be possible to do this asynchronously, or do like with the Recast implementation: store a representation of all the triangles in the scene in a buffer, and check overlap collisions on the CPU in one of the threads generating the data.
The first step is to add to the Navigation System settings configuration of your flying agents.
You need to open the project settings, then click on the Navigation System option under the Game section. Then, expand the Supported Agents array and add your agent properties.
You must select SVONavigationData both for the Nav Data Class and the Preferred Nav Data.
The Agent Radius property is very important, as this will control the size of the smallest voxels of the navigation data. The size of the voxels will be twice the agent radius.
You can create multiple flying agents with different radii. This will make the navigation system create multiple navigation data in the level.
After you created your agent in the navigation system settings, you need to place a SVO Bounds Volume actor in your level, to let the navigation system create the SVONavigationData actor in the same level. That actor will contain the sparse voxel octree data used by the pathfinding.
It's important to note that the size of the octree generated by the plug-in won't necessarily be the same size as that volume. Indeed, because the navigation data starts with voxels with a pre-determined size (twice the agent radius), and because that navigation data is an octree, the plug-in must compute a total size that will allow the root cube to be split as many times as necessary to end up with the smallest cubes with the correct size.
You can visualize the real navigation bounds using the Debug Infos . Debug Draw Bounds option, as explained later.
You can click on the actor to display some options:
Even though the navigation data is generated automatically by the engine when it is added to the level, and you move actors around, it may be convenient to manually rebuild the data. You can use the 2 buttons to clear the navigation data, and rebuild it again.
You can use the Collision Channel setting to change the channel used by the physics engine overlap detection.
The Clearance option allows you to add an extra offset to the boxes used to test overlap. For example, if the agent radius is 100 units, then the smallest voxel size will be 200. If the clearance is set to 10, the size of the smallest voxels will be 210.
Explanations of the Debug Infos section are further down this document, but you can Enable Drawing and check Debug Draw Layers to make sure the data has been generated. If you moved and resized the Nav Mesh Bounds Volume to encompass some geometry, you should see some big yellow cubes in the viewport.
The last step is to setup the flying actors.
The easiest is to have an actor which inherit from ACharacter. You then need to select the character movement component, head to the Nav Movement section, and select SVONavigationData as their Preferred Nav Data class.
The next step is to create a blueprint from the class SVONavigationQueryFilter.
That class defines the options to use by the pathfinder. You can find the explanations of the various options below.
You can set this asset as the Default Nav Filter Class of the AIController of your flying actor.
When it's done, you can for example use a behavior tree to move your actor, such as the following one:
To move the actor, you just need to use the Move To default node, and not forget to set the Filter Class option in the task properties.
You can visualize the paths used by your flying agents by checking Enable Drawing on the SVO navigation data actor, and checking Debug Draw Active Paths.
When the AI controller prepares a pathfinding request, it calls the function GetNavAgentLocation() on the pawn to get the starting position of the path, which for characters returns the feet location.
You would want to override that function to return another location.
If the actor is already flying, it makes little sense to return its feet position.
If your actor is grounded and you're using the pathfinding to find an aerial destination, returning the foot location would make the pathfinding fail because the feet would most likely be on a blocking surface, and would have generated a blocked voxel in the navigation data, which would make the pathfinding algorithm unable to find a path from an invalid start position.
Another function you may want to override is GetMoveGoalOffset.
Indeed, if you're asking a flying actor to move to a grounded actor, the destination location will be again the result of GetNavAgentLocation(), which would return the foot location, in an occluded voxel.
By overriding GetMoveGoalOffset, you can return a vertical offset to make sure the destination location sits above the occluded voxels.
An example implementation could use a USceneComponent in the actor, that you can visually place in the blueprint editor, and the function imnplementation could be:
FVector AMyGameCharacterPlayerBase::GetMoveGoalOffset( const AActor * moving_actor ) const
{
const auto * character = Cast< ACharacter >( moving_actor );
if ( character == nullptr )
{
if ( auto * controller = Cast< AController >( moving_actor ) )
{
character = controller->GetCharacter();
}
}
if ( character != nullptr )
{
if (const auto * movement_component = character->GetMovementComponent() )
{
if ( movement_component->IsFlying() )
{
return FlyingEnemyTargetAttachComponent->GetRelativeLocation();
}
}
}
return FVector::ZeroVector;
}
You can access the module settings by opening the Project Settings, heading to the Engine section on the left, and clicking on the SVONavigation System item.
The option Navigation Auto Update Enabled allows you to auto-rebuild the navigation data when you update the scene.
The option Default RayCaster Class allows you to define how you want the module to perform line of sight checks in the world.
Line of sight checks are performed in 2 occasions:
- Before computing a path, we check if there's a LoS between the start and end locations. If there is no obstacle, the resulting navigation path will be a straight line between the 2 points.
- Some algorithms used by the pathfinding require a LoS check to return a shorter path. See below for more explanations.
At the moment, you can choose between 3 raycast options:
-
Octree Traversal : this is a numeric algorithm based on the academic paper An Efficient Parametric Algorithm for Octree Traversal. This is the fastest of all 3 functions, and is the default.
-
Physics ray / sphere casts : this function uses the physics engine built-in RayCast / Sphere cast functions. It's less precise than the octree traversal function, but since it was implemented first, it was kept in case it's useful to anyone.
As explained before, the navigation query filter allows you to define the pathfinding algorithm and options to use for your flying actor.
The first option is the path finder class. You can choose between 3 options:
-
A* : this is a well known algorithm which is very fast to compute a path, but has the downside of producing very jaggy paths, as the path points will all be the centers of the voxels.
-
Theta*: this algorithm uses A* as a base, but adds line-of-sight checks to allow the path to take shortcuts between points. It produces the most accurate paths of the 3, but is also the more expensive to compute.
-
Lazy Theta*: this is the default algorithm of the plug-in. It's a variation of Theta* which produces slightly less optimal paths, but is much less expensive as it generates much less line-of-sight checks.
Theta* and Lazy Theta* both use Line of sight checks to shorten the path. As explained before, you can choose between 3 modes: Octree Traversal, physics ray cast, physics sphere cast.
The next option of the query filter is Traversal Cost Calculator.
This option allows you to define how the path finder will compute how much it costs to go from a position to another. There are 2 options:
- Distance: this will simply return the distance between the 2 positions.
- Fixed: this will always return the same cost. From the Game AI Pro 3 article linked in the introduction,
This means that no matter how big the node is, traveling through it has the same cost. This effectively biases the search even more toward exploring through large nodes.
The next options are for the heuristic cost.
Heuristic Calculator allows you to define how the path finder will compute how much it costs to go from a position to the target destination. You can choose between 2 options:
- Euclidean: this will simply return the distance between a position and the target destination.
- Manhattan: this will return the distance between the 2 positions using taxicab geometry.
Heuristic Scale can be used to force the algorithm to prefer exploring nodes that it thinks are closer to the goal.
The next option, Use Node Size Compensation, is another optimization suggested by the paper. If enabled, both the traversal cost and the heuristic cost will be adjusted so that it's cheaper to go through big nodes than through small ones.
You can easily see the impact of all those options on the pathfinding computation by using the path finder test actor. See below for informations.
The last option allows you to run a CatmullRom Algorithm on the points generated by the pathfinding to smooth it out. You can use the Smoothing Subdivisions to control the smoothness.
Depending on your level configuration, you may find useful to force all flying actors inside of a given volume to all use some pathfinding settings, and not the settings defined in the controller, or when using the MoveTo behavior tree task.
To do that, you can select the SVOBoundsVolume actor in the world. It has a property named Volume Navigation Query Filter, which you can assign the query filter to use.
After selecting a navigation query filter, all actors requesting a path inside that specific volume will use that filter.
It is possible to have different 3D navigation volumes in different sublevels that you can stream in and out. But having an actor navigate from a navigation volume to another is not currently supported.
To make it work, you need to follow those lines (those have been tested in shipped games):
- Setup your level and sublevels correctly as stated here : https://forums.unrealengine.com/t/nav-mesh-and-streaming-levels/451476/2
- You can not use the ResavePackages commandlet to build the 3d nav. You will have to write your own commandlet, that will first load the persistent level.
- Then for each sublevel that contains a SVO Navigation volume, you must load ONLY that level and ONLY the other sublevels that contain geometry that may create occluded voxels inside.
- You must then run the navigation build process, the same way it is done in
UNavigationSystemV1::Build - I recommend you create your own child class inheriting from
UNavigationSystemV1and assign it as the default navigation system.
Doing these steps will ensure that the navigation data is stored inside the navigation data chunk of the sublevel that contains each SVO Navigation volume (see ASVONavigationData::OnNavigationDataGenerationFinished).
When the game runs, and levels are streamed in and out, the code in ASVONavigationData::OnStreamingLevelAdded and ASVONavigationData::OnStreamingLevelRemoved will add / remove the navigation data from the levels.
The plug-in comes with lots of visualization options to help you understand how the data is structured, and how to best set up the pathfinding.
To see these visualizations, you first need to enable the Navigation visualization in the viewport.
Then you need to select the SVONavigationData actor in the world outliner and check the Enable Drawing flag.
Debug Draw Bounds: displays a white cube which represents the real size of the navigation data.
-
Debug Draw Occluded VoxelsandDebug Draw Free Voxelswill display yellow cubes for the occluded voxels and green cubes for the free voxels, if you choose to draw the layers or the sub nodes. -
Debug Draw Layers: displays the intermediate layers of the octree, down to layer 0, which is the leaf nodes layer.
Layer 3
Layer 2
Layer 1
Layer 0
SubNodes
Debug Draw Node Addresswill display the coordinates of each voxel in the layer you selected, or the subnodes.
Debug Draw Morton Codewill display the morton code of each voxel in the layer you selected, or the subnodes.
Debug Draw Active Pathscan be used while the game is running in the editor, and will display all the paths being used by your actors in the navigation data bounds.
To test the pathfinding options, you can drag'n drop 2 actors of type SVOPathFinderTest in your world.
Then select one of them, and set the other one as the Other Actor.
You can then set the Preferred Nav Data to SVONavigationData and the Navigation Query Filter to the blueprint class you created earlier.
From there, you can use the buttons from one of the actors to initiate a pathfinding computation.
Auto Complete Instantlywill generate the path as soon as you click the button, and will display the result in the viewport
Auto Complete Step by Stepwill show the algorithm working by processing each node one after each other after a small delay (which is configurable using the optionAuto Step Timer). You can pause the execution with the buttonPause Auto Completion.
Auto Complete Until Next Nodewill process one node at a time, with all its neighbors, until a new node is pushed on the stack of nodes to process.
To compare the performance of the different pathfinding algorithms, you can use the Path Finder Debug Infos section which is filled with interesting informations after a path has been found.
For example, here are 3 benchmarks with various settinsgs for the Lazy Theta*:
Traversal Cost: Distance
Heuristic Cost: Manhattan
Traversal Cost: Fixed
Heuristic Cost: Manhattan
Traversal Cost: Fixed
Heuristic Cost: Distance
You can use the console command CountNavMem to display in the OutputLog the memory used by the navigation data.
