UDN

Search public documentation:

NavMeshConstraintsAndGoalEvaluators

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 > Nav Mesh Path constraints and Goal Evaluators

Nav Mesh Path constraints and Goal Evaluators

Overview

This document outlines the purpose and usage of path constraints and path goal evaluators as they pertain to path finding and generic path traversals.

Why?

The advent of these modular and customizable constraints allows the AI programmer to run path queries tailored to fit the needs of the game exactly, with very little code overhead. In the past if one wanted to do something like find a path from A -> B that stays away from enemies one would have to add a special case if block to the path cost function in native code, and continue doing so for each new situation. This quickly becomes unwieldy. For each different combination of custom considerations (constraints) one needs for a particular path search, new code must be added to take into account each new query.

Our approach instead packages concerns into self-contained objects called PathConstraints which gets added to a list of which all are considered during path finding. So if you're just trying to find the shortest path to your destination you could simply add the Path_TowardGoal constraint, which would get you the classical straight line A* heuristic favored by AI programmers. However, if you want to do something more complex say, find shortest path from A -> B that avoids fire you would simply add both the Path_TowardGoal constraint and a (hypothetical) Path_AvoidFire constraint. This is easily done, and is script accessible so it becomes trivial to cobble together custom, one-off path queries to fit your exact situation.

The constraints are only half the picture though. One also needs the ability to specify the completion conditions for a path search as well as have a chance to interrogate the data as it is traversed. This is what path goal evaluators are for. They both dictate when the search is finished (e.g. when we found a valid goal node) as well as handle interrogation and storage of computed data. For example in Gears of War, when searching for cover a cover goal evaluator is used. This custom goal evaluator will continue the search until a cover node of sufficient quality is found, and it will keep track of cover nodes found thus far, scoring them along the way. The most basic (and commonly used) path goal evaluator is Goal_AtActor, which simply stops the search when a navigation mesh polygon is found which contains the search goal point. This is the goal evaluator you would use to find the shortest path from A -> B.

Constraints and goal evaluators are stored in two lists within the Navigation Handle.

Path Constraints

As mentioned above path constraints can both modify the stored actual distance (g), as well as the heuristic distance (h). Lastly path constraints can also return false on a particular node which indicates this node is absolutely unfit and should not be added to the open list at all.

Things path constraints should be used for:

Shaping the traversal toward a goal (e.g. optimize the search by trying nodes toward the goal first)
Restricting traversal through conditionally untraversable areas (e.g. fire, lava, friendly-only doors)
Nudging traversals away from undesirable objects (e.g. enemy players)

Things path constraints should/can not be used for:

Gathering/storing data (your constraint may not get called if a previous constraint returns false)

Path Goal Evaluators

Path goal evaluators are a bit more complicated as they handle more of the basic path finding functionality such as determining the start and end nodes, and determining which node to call the 'goal' once a search stops for any reason. The goal evaluator sets up the search, and then determines when it's completed, as well as saves the found path back out to the navigation handle once one is found.

Note: the first path goal evaluator in the list has special meaning. It will be treated as the master evaluator, and thus it will have control over initialization of the search (e.g. seedworkingset, initializesearch).

Here is the life of a typical path goal evaluator:

InitializeSearch() - This is called at the very beginning of a path search. This allows the goal evaluator to set up whatever it needs to for the search to progress. The default functionality will find the polygon containing SearchStart and set that as the AnchorPoly.
SeedWorkingSet() - This is called next. This function is responsible populating the open list with one or more polygons to begin searching from. The default functionality simply adds the anchor polygon to the working set.

Now, we enter the main loop of the path search.

EvaluateGoal() - This will be called after the best node is popped off of the working set.. This function will go through the path goal evaluator list calling EvaluateGoal() on each one in turn. This allows each goal evaluator in the list a chance to interrogate the polygon, as well as call a halt to the search if a suitable node was found.
DetermineFinalGoal() - This will be called once the path has completed. (either because a goal was found or because the search ran out of nodes to test) This allows the goal evaluator to do final computation and determine what the actual best goal was (if any). The default here is just to check to see if a goal was found, but in more complicated evaluators such as Goal_AtCover a final stock is taken of polygons visited so far to determine what the most fit goal is.
SaveResultingPath() - This is the very last function to get called on the evaluator. On almost all goal evaluators this function simply walks the predecessor chain in reverse to save the path from start to goal. But this allows a custom evaluator to do something different here. For example, Goal_ClosestActorInList (which path finds from goal to start) saves the path in forward order since it's reversed to start (see more on this evaluator below).
NotifyExceededMaxPathVisits() - This is one more function called in exceptional cases. This will get called when the number of polygons visited exceeds the MaxPathVisits parameter on the navigation handle. In most cases this indicates a failure (e.g. no goal was found within the maximum sample size). But occasionally this just indicates the search is complete (e.g. Goal_Null which just searches until it runs out of nodes or hits the max visits cap.. useful for finding the best node in an area).

The only function required to be implemented by new path goal evaluators is EvaluateGoal(). This is the primary function of goal evaluators (that is, determining when a valid goal has been found).

There are a couple of booleans which affect the way EvaluateGoal() operates. 99% of the traversals we do use the default settings (and actually most traversals only have one goal evaluator so these don't even come into play), but for composition of goal evalators these booleans have been added to make things easier:

bUseORforEvaluateGoal (on UNavigationHandle) - by default all goal evaluators must return true from EvaluateGoal() in order for the search to be considered finished. This can be modified via the bUseORforEvaluateGoal on the navigation handle. (when true, if any goal evaluator returns true from EvaluateGoal() the search will be stopped)
bAlwaysCallEvaluateGoal (on GoalEvaluator) - when this is true for a particular goal evaluator that goal evalator's EvaluateGoal() function will be called even if it has already been determined that the current node is or isn't the final goal. This is useful for goal evalators that need to store information or compute something for each path iteration.

Constraint/GoalEval Pooling

In order to keep from needlessly newing path constraints and goal evaluators all the time, they are newed on-demand and cached. This allows cached constraints and goal evalators to be re-used without newing and garbage collecting large numbers of constraints.

For this purpose you should never new PathConstraints or GoalEvaluators directly. Instead, you should call CreatePathConstraint() or CreatePathGoalEvaluator() on the NavigationHandle. This will either new a copy of that constraint if one has not been cached already or retrieve a cached copy.

As part of the caching process the Recycle() event is called when a constraint is cleared from a handle. Within this function all state is cleared and reset to defaults. When overriding PathConstraints and GoalEvaluators it's important to override this function and clear out any new state that might be a part of your derived class so that you don't get stale data coming with recycled constraints.

Example usage

It's convenient to implement a static function on constraints/evaluators such that you can call it to add the constraint or evaluator to the handle's lists. Here is an example of one such static function for the Path_TowardGoal constraint:

Path_TowardGoal.uc

static function bool TowardGoal(NavigationHandle NavHandle, Actor Goal)
{
  local NavMeshPath_Toward Con;

  if (NavHandle != None && Goal != None)
  {
    Con = NavMeshPath_Toward(NavHandle.CreatePathConstraint(default.class));
    if (Con != None)
    {
      Con.GoalActor = Goal;
      NavHandle.AddPathConstraint( Con );
      return TRUE;
    }
  }

  return FALSE;
}

As you can see it calls CreatePathConstraint() to retrieve a cached version of that class, and then calls AddPathConstraint() to place it in the list of constraints to be used during the search. AddPathConstraint(), AddGoalEvaluator() and ClearConstraints() are the interface for specifying constraints for your traversal.

Note: It is usually not necessary to call ClearConstraints() as constraints will automatically be cleared after you call FindPath().

More information about FindPath() and its usage can be found on the NavigationMeshTechnicalGuide. Also, be sure to check out the NavigationMeshPathDebugging page for more info on how to debug your path searches.

Quick summary of current path constraints and what they are for

NavMeshPath_AlongLine

This will add heuristic cost to nodes the further away from the direction specified.

NavMeshPath_EnforceTwoWayEdges

This will filter out edges which don't have a corresponding edge back. (keeps AIs from getting into situations they can't get out of).

NavMeshPath_MinDistBetweenSpecsOfType

This will walk back along the predecessor chain at each step to ensure there is a minimum distance between edges of a certain type. (For example ensuring a minimum distance between mantles)

NavMeshPath_SameCoverLink

This only allows polys that contain cover from the specified CoverLink.

NavMeshPath_Toward

This will add heuristic cost according to the distance to the passed goal point. Use this to bias normal path searches toward your a particular goal.

NavMeshPath_WithinDistanceEnvelope

Allows the user to specify an envelope within which paths are valid, and either throw out nodes outside this envelope or penalize them increasingly as they leave it. (e.g. I want to find a point within some max range to me)

NavMeshPath_WithinTraversalDist

Will throw out paths that exceed a specified value

Quick summary of current path goal evaluators and what they are for

NavMeshGoal_At

The simplest and most common goal evaluator. Will end the search when a polygon which contains the goal point is found.

NavMeshGoal_ClosestActorInList

One of the more interesting goal evaluators. This guy will efficiently find the closest actor (in path distance) to the requesting entity. This is accomplished via doing a search in reverse. The working set is seeded with all polygons which contain actors in the list to search for, and then the search continues until the polygon which contains the searchstart is found. At this point the path is saved in forward order since we're already going in reverse.

NavMeshGoal_Filter

This is a helper base class which is for filters that are meant to be used in conjunction with NavMeshGoal_GenericFilterContainer. These goals should only answer this question "is this a valid final goal or not?" and do nothing else.

NavMeshGoal_GenericFilterContainer

This goal evaluator will not stop until its out of paths, and will simply return the node with the least cost.

NavMeshGoal_Null

This goal evaluator will simply keep searching until the max number of iterations is hit, or the search runs out of nodes. Useful for finding the best node in an area. (e.g. could be used in conjunction with a NavMeshPath_WithinDistanceEnvelope constraint to find the furthest away polygon within some max range)

NavMeshGoal_PolyEncompassesAI

This goal evaluator will throw out polygons which can't fully fit the entity searching this is useful for open-ended path searches (e.g. find any polygon outside of a radius) because an edge may support the entity allowing the traversal to enter a polygon, but the entity might not necessarily fully fit inside the polygon, even though he could move through it.

NavMeshGoal_Random

This goal evaluator will not stop until its out of paths, and will return one of the nodes traversed at random.

NavMeshGoal_WithinDistanceEnvelope

This goal evaluator will throw out nodes (polygons) if they are outside the distance envelope specified.