Navigation Mesh Technical Guide

Overview

This is a quick and dirty guide to hooking up your AI to use a navigation mesh (a.k.a. nav mesh). For an introduction to the Navigation Mesh system in the Unreal Engine, see the Navigation Mesh Reference.

Navigation Handle

(NavigationHandle.uc)

Previously all pathfinding functionality was contained in Pawn. All the new functionality for navigation mesh based pathfinding is encapsulated in an self-contained object called a navigation handle. The navigation handle itself is a component and can be attached to any actor with which you'd like to path. In addition the handle stores the output of the path search. That is it stores the generated path, and can be extended to store whatever else is relevant to the types of path traversals you are doing.

To make your AI pathfind it needs to:

• implement interface_navigationhandle. (More on the interface later).
• have a navigationhandle component accessible somewhere

Navigation handle functionality

Navigation handle functionality comes in roughly three categories:

1. Actual pathfinding (including constraint/goal evaluator control)
2. path following functions
3. functions for querying data from the navmesh

Actual Pathfinding functionality

Pathfinding is performed with the help of path constraints and goal evaluators. See the Constraints and Goal Evaluators page page for more information. To pathfind you need at least one constraint and one goal evaluator set up. To do this it's usually a good idea to add some sort of boiler plate function like this:

   event bool GeneratePathTo( Actor Goal, optional float WithinDistance, optional bool bAllowPartialPath )
   {
      if( NavigationHandle == None )
         return FALSE;
   
      AddBasePathConstraints(false);
   
      class'NavMeshPath_Toward'.static.TowardGoal( NavigationHandle, Goal );
      class'NavMeshGoal_At'.static.AtActor( NavigationHandle, Goal, WithinDistance, bAllowPartialPath );
   
      return NavigationHandle.FindPath();
   }
   

See example code here: TestAI_ExampleCode_v3.zip: Example use of navigationhandle path functions

• FindPath - will execute the A* loop and run until the goal evalautor stack determines a proper goal has been found, or the working set is empty (it ran out of nodes to try). It will then return TRUE if the search was a success, and the resulting path will be stored in the pathcache on the navigationhandle you called findpath on. In more customized path search situations (e.g. cover searches) the goal evaluator can store extra data depending on its own internal considerations.

Path Following Functions

• SetFinalDestination - this function sets the FinalDestination parameter on the navigationhandle. This is necessary for two reasons. First, the pathcache is a list of edges, so once the bot reaches the last edge we need more information to get the bot to the actual goal point of the path in the last poly of the path. Second, the reason this is not set automatically for every path search is that an AI currently walking on a path toward a goal may do a path search that is not related to actually pathing there (e.g. look for cover while running somewhere) and thus we don't want to clobber the currently stored finaldest in this case. Note: Certain goal evaluators (namely NavMeshGoal_At) set this automatically if it's not already set as they can only be used in traditional pathing situations

• GetNextMoveLocation - this is the heavy lifter of path following. It will determine where along the path you are currently, and calculate the point in space the entity should be moving toward (e.g. figure out what point to feed to MoveTo())

Navmesh Query Functions There are too many to list here. See this document FIXME for a complete list of navigation handle functions. A couple of note are

• PointReachable - this will do a linecheck against the obstacle mesh generated by the navmesh generation process. This is much faster than doing normal linechecks against collision geo, and faster still than doing normal reachability checks (which involve numerous linechecks)
• GetValidPositionsForBox - will return all valid (and non overlapping) positions for the passed box within the given bounds. Very useful for things like finding spawn locations

Navigation Interface

(Interface_NavigationHandle.uc) The Navigation Handle interface is what allows any actor to pathfind on the navigation mesh. During pathfinding certain basic attributes of the pathfinding entity are needed (width, supported edges, etc.) and this interface is what is queried by the path search functions in order to determine the pathfinding entity's capabilities.

Currently the interface looks like this:

   virtual UBOOL   CanCoverSlip(ACoverLink* Link, INT SlotIdx)   { return FALSE; }
   virtual FVector GetEdgeZAdjust(struct FNavMeshEdgeBase* Edge)=0;
   virtual UBOOL CheckMantleValidity(struct FNavMeshMantleEdge* Edge){ return TRUE; }
   virtual void SetupPathfindingParams( struct FNavMeshPathParams& out_ParamCache )=0;

these functions take input, and thus cannot be packed into SetupPathfindingParams and cached like the rest of the params

• CanCoverSlip - Given the passed coverlink determines if this entity can coverslip at this location
• GetEdgeZAdjust - Given the passed edge, determines the height above that edge's surfaces at which the point this AI should use to path through it should be. (e.g. hovering guys could override this to move near the top of the pathable space
• CheckMantleValidity - allows entities to do custom validation before using mantle edges

The bulk of the params for pathfinding are set using SetupPathfindingParams, and cached during the path search

• SetupPathfindingParams - here is a simple implementation:

void AController::SetupPathfindingParams( FNavMeshPathParams& out_ParamCache )
{
   VERIFY_NAVMESH_PARAMS(8);
   if(Pawn != NULL)
   {
      out_ParamCache.bAbleToSearch = TRUE;
      out_ParamCache.SearchExtent = Pawn->GetCylinderExtent()+NavMeshPath_SearchExtent_Modifier;
      out_ParamCache.SearchStart = Pawn->Location;
      out_ParamCache.bCanMantle = Pawn->bCanMantle;
      out_ParamCache.bNeedsMantleValidityTest = FALSE;
      out_ParamCache.MaxDropHeight = GetMaxDropHeight();
      out_ParamCache.MinWalkableZ = Pawn->WalkableFloorZ;
      out_ParamCache.MaxHoverDistance = (Pawn->bCanFly) ? -1.f : DEFAULT_BOX_PADDING;
   }
        else { ... }
}

Note the VERIFY_NAVMESH_PARAMS macro, which will throw a compile time 'assert' if the number of parameters specified here does not match NUM_PATHFINDING_PARAMS specified in the navigationhandle. This is to curb cases of parameters being added and not properly setup in client implementations.

Here is a description of all the params listed here and what they are used for:

• Interface - a pointer back to the interface ref of the entity pathfinding currently
• bCanMantle - stores whether this entity can use cover mantles
• bNeedsMantleValidityTest - stores whether CheckMantleValidity should get called for this entity (here so guys that don't need this don't get unnecessary vfunction calls)
• bAbleToSearch - is this entity valid to use for searches? (does it have a pawn, etc..)
• SearchExtent - size of the entity pathing. This is used to determine which edges the AI can fit through @NOTE: this will use the LARGEST of the X/Y dimensions. Pathfinding extents must be symmetrical, so if the extent is not, it will be made to be symmetric. (for long train-like objects path with the extent of the leader, and the rest will follow) @see FNavMeshEdgeBase::Supports()
• SearchStart - the position to start the search from
• MaxDropHeight - maximum height this AI is allowed to 'drop down' e.g. fall of a ledge
• MinWalkableZ - describes the steepest slope this AI is allowed to walk on (Z component of surface normal)
• MaxHoverDistance - max distance above polygons this AI is allowed to hover (used in determining which anchor poly.. e.g. if we are technically in two polys that overlap, which one am I actually close enough to the surface to to be considered inside it)

Nav Mesh Debugging

For information on debugging issues with navigationmesh pathfinding at runtime, see the Nav Mesh Path Debugging page.

Pawn pathfinding parameters

There are several parameters on the Pawn itself which will affect pathfollowing that aren't directly related to the navmesh.

Here is a quick overview:

• MaxStepHeight - Maximum vertical height this AI can 'stepup' (non jump step)
• MaxJumpHeight - Maximum vertical height this AI can jump (this will determine when the AI tries to jump over obstacles vs go around them)
• WalkableFloorZ - The maxmimum Z value of the normal of a slope considered walkable (Pawns will slode off of slopes with Z > this value)