Monday, April 9, 2012

AI Navigation in UnrealScript

Moving in a level is a fundamental aspect of Artificial Intelligence in games. The most common form of AI navigation is based on waypoints that are placed on the level to create a network of paths. The UDK also supports a more efficient navigation system based on "Navigation Mesh" which results in a more natural movement.

Waypoints are represented by the class PathNode:


In the AIController class we have a code example that uses the waypoints system:
//Extract from AIController class (Engine package)

state ScriptedMove
{
    // state functions...
    
    Begin:
    // while we have a valid pawn and move target, and
    // we haven't reached the target yet
    while (Pawn != None &&
           ScriptedMoveTarget != None &&
           !Pawn.ReachedDestination(ScriptedMoveTarget))
    {
        // check to see if it is directly reachable
        if (ActorReachable(ScriptedMoveTarget))
        {
            // then move directly to the actor
            MoveToward(ScriptedMoveTarget, ScriptedFocus);
        }
        else
        {
           // attempt to find a path to the target
           MoveTarget = FindPathToward(ScriptedMoveTarget);
           if (MoveTarget != None)
           {
               // move to the first node on the path
               MoveToward(MoveTarget, ScriptedFocus);
           }
           else
           {
               // abort the move                
               ScriptedMoveTarget = None;
           }
        }
    }
}

In the system based on "Navigation Mesh", the path is represented by a set of convex polygons that are generated automatically in the level from an actor known as Pylon:


The functions related to pathfinding using "Navigation Mesh" are contained in a class called NavigationHandle. This class works with the concept of Path Constraints and Goal Evaluators. The use of Path Constraints allows to set criteria to be taken into account during the pathfinding. The simplest Path Constraint is the NavMeshPath_Toward. The Goal Evaluator is used to define the end of pathfinding. The most common Goal Evaluator is the NavMeshGoal_At.

Looking in the source code that came with the UDK, I found a simple example of pathfinding using "Navigation Mesh". The code below is from the function GeneratePathToActor() of the GameCrowdAgent class:
//Extract from GameCrowdAgent class (GameFramework package)

/**
  * Generate a path to Goal on behalf of the QueryingAgent
  */
event vector GeneratePathToActor( Actor Goal, optional float WithinDistance, optional bool bAllowPartialPath )
{
    local vector NextDest;

    LastPathingAttempt = WorldInfo.TimeSeconds;
    NextDest = Goal.Location;

    // make sure we have a valid navigation handle
    if ( NavigationHandle == None )
    {
        InitNavigationHandle();
    }
    if( (NavigationHandle != None) && !NavigationHandle.ActorReachable(Goal) )
    {
        class'NavMeshPath_Toward'.static.TowardGoal( NavigationHandle, Goal );
        class'NavMeshGoal_At'.static.AtActor( NavigationHandle, Goal, WithinDistance, bAllowPartialPath );

        if ( NavigationHandle.FindPath() )
        {
            NavigationHandle.GetNextMoveLocation(NextDest, SearchExtent.X);
        }
        NavigationHandle.ClearConstraints();
    }

    return NextDest;
}

For more information about AI Navigation: