UDN
Search public documentation:

NavigationMeshTechnicalGuide
日本語訳
中国翻译
한국어

Interested in the Unreal Engine?
Visit the Unreal Technology site.

Looking for jobs and company info?
Check out the Epic games site.

Questions about support via UDN?
Contact the UDN Staff

UE3 Home > AI & Navigation > Navigation Mesh Technical Guide

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


All PathNode path finding functionality was contained in Controller. All the new functionality for navigation mesh based path finding is encapsulated in a 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 path find using navigation meshes it needs to:

  • Implement Interface_NavigationHandle.
  • Have a NavigationHandle component accessible somewhere.

Navigation handle functionality

Navigation handle functionality comes in roughly three categories.

Actual path finding functionality

Path finding is performed with the help of path constraints and goal evaluators. See the Constraints and Goal Evaluators page for more information. To path find 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:

function 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();
}

  • FindPath() - This function will execute the A* loop and run until the goal evaluator 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 Actor reaches the last edge we need more information to get the Actor 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 Actor currently moving 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 FinalDestination in this case.
    ALERT! 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 Navigation Mesh Reference for a complete list of navigation handle functions. A couple of note are:
  • PointReachable() - This will do a line check against the obstacle mesh generated by the NavMesh generation process. This is much faster than doing normal line checks against collision geometry, and faster still than doing normal reachability checks (which involve numerous line checks).
  • GetValidPositionsForBox() - This will return all valid (and non overlapping) positions for the passed box within the given bounds. Very useful for things like finding spawn locations.

Nav Mesh Debugging


For information on debugging issues with Navigation Mesh path finding at run time, see the Nav Mesh Path Debugging page.

Pawn path finding parameters


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

Here is a quick overview:

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

Downloads


  • Download an example which demonstrates how to use NavigationHandle path functions.