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 pathfinding 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 get 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 navmeshpath_toward 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 toward constraint and the 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, when searching for cover a cover goal evaluator is used. This custom goal evaluator will continue the search until a covernode of sufficient quality is found, and it will keep track of covernodes found thus far, scoring them along the way. The most basic (and commonly used) path goal evaluator is navmeshgoal_at, which simply stops the search when a navmesh 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 goalevaluators are stored on two lists on the Navigation Handle. During each path step UNavigationHandle::ApplyConstraints will be called, which will give each path constraint in the list a chance to modify the heuristic, and actual costs for any given polygon. Likewise, when a new node (polygon) is popped off the open list UNavigationHandle::EvaluateGoal will give each path goal evaluator a chance to call the search done, and interrogate the polygon.

Path Constraints

(NavMeshPathConstraint.uc)

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)
• making coffee

Most path constraints need only implement the base interface function:

   /**
    * EvaluatePath - this function is called for every A* successor edge.  This gives constraints a chance
    * to both modify the heuristic cost (h), the computed actual cost (g), as well as deny use of this edge altogether
    * @param Edge - the successor candidate edge
    * @param SrcPoly - the poly we are expanding from (e.g. the poly from which we want to traverse the Edge)
    * @param DestPoly - The poly we're trying to traverse to (from SrcPoly)
    * @param PathParams - the cached pathing parameters of the pathing entity 
    * @param out_PathCost - the computed path cost of this edge (the current value is supplied as input, and can be modified in this function) 
    *                       (this constitutes G of the pathfinding heuristic function F=G+H)
    * @param out_HeuristicCost - the heuristic cost to be applied to this edge (the current heuristic is supplied as input, and can be modified in this function)
    *                          (this constitutes H of the pathfindign heuristic function F=G+H)
    * @return - TRUE if this edge is a valid successor candidate and should be added to the open list, FALSE if it should be thrown out
    */
   virtual UBOOL EvaluatePath( FNavMeshEdgeBase* Edge,
                        FNavMeshPolyBase* SrcPoly,
                        FNavMeshPolyBase* DestPoly,
                        const FNavMeshPathParams& PathParams,
                        INT& out_PathCost, INT& out_HeuristicCost );

Path Goal Evaluators

(NavMeshPathGoalEvaluator.uc)

Path goal evaluators are a bit more complicated as they handle more of the basic pathfinding 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 pathgoalevaluator 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 (this all happens within UNavigationHandle::GeneratePath()):

• InitializeSearch() 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() 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 poly to the working set.

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

• EvaluateGoal() 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() 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 navmeshgoal_atcover a final stock is taken of polys visited so far to determine what the most fit goal is.

• SaveResultingPath() 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 navmeshgoal_closestactorinlist (which pathfinds from goal to start) saves the path in forward order since it's reversed to start (see more on this evaluator below).

• NotifyExceededMaxPathVisits() 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. navmeshgoal_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 pathgoalevaluators 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 bools 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 evals these bools 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 goaleval'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 evals 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 evals 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/evals such that you can call it to add the constraint or eval to the handle's lists. Here is an example of one such static function for the navmeshpath_toward constraint:

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 retrive 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_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_AlongLine

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

NavMeshPath_EnforceTwoWayEdges

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

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_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

NavMeshPath_At

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

NavMeshPath_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.

NavMeshPath_Null

This goal eval 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_distanceenvelope constraint to find the furthest away polygon within some max range)