X9

What would be a game without path-finding in 2010 ? well not much. To make your game look a little more professional, we will add the dreaded path finding to your pawn. Ok, the success to this is to have proper path nodes (waypoints) at the right place in your maps.

See UDN : http://udn.epicgames.com/Three/UsingWaypoints.html for a starter guide.

If you fire up the map that comes with the tutorial and press P. you will see the paths like the following image :

 

In case you did not get the map yet, get it here

Now from my experimentation, for not making the pawn look like an idiot, be sure to have white or green paths, blue paths are too narrow and will be dismissed by default. There can be override to this but it is beyond this tutorial.

Waypoints VS Navigation Meshes

Waypoints differ in that they are less optimized than Nav meshes. As I did not have time to check on navmeshes yet, but it is on my todo list, I cannot say if for this type of game it really is a show stopper. You could actually only use waypoints in your game, the point is that the player never get stuck and can click beyond obstacles and let the player run by himself. Most of the time, I would guess the player will hold the mouse in the direction they want to go, Diablo style.

 

So what do we have to do to add path-finding ? First thing is to uncomment that function call in StopFire. I am sure you eagerly awaited this moment…

 

Add The following variable to prepare for pathing (all taken from AIController)

 

/*****************************************************************
 *
 *  PATH FINDING
 *
 * The following variables where taken as is from AiController.uc
 *
 */
var Actor       ScriptedMoveTarget;
/** Route from last scripted action; if valid, sets ScriptedMoveTarget with the points along the route */
var Route       ScriptedRoute;
/** if ScriptedRoute is valid, the index of the current point we're moving to */
var int         ScriptedRouteIndex;
/*****************************************************************/

Copy the ExecutePathFindMove and be sure you uncommented the call in StopFire !

/******************************************************************
 *
 *  TUTORIAL FUNCTION
 *
 *  ExecutePathFindMove makes the call to the FindPathTo so that a list
 *  of possible PathNodes will be cached in RouteCache.
 *
 ******************************************************************/
function ExecutePathFindMove()
{
	ScriptedMoveTarget = FindPathTo(GetDestinationPosition());
	`Log("Route length is"@RouteCache.Length);
	if( RouteCache.Length > 0 )
	{
		`Log("Launching PathFind");
		PushState('PathFind');
	}
}

This function will Launch a query to find a route to a destination vector. If the RouteCache holding the all the waypoints is not empty, we push the PathFind state. This state is a lightly modified version of the ScriptedRouteMove from the AIController.uc :

/******************************************************************
 *
 *  TUTORIAL STATE (PathFind)
 *
 *  This is almost the same if not identical to AiController
 *  ScriptedRouteMove. For each route in the RouteCache (initialized
 *  with a call to FindPathTo(destVector), push a state that will
 *  make the pawn goto a location determined by a PathNode location.
 *  You will need to have multiple PathNodes on your map for this to
 *  work properly. This does not use NavigationMeshes, only Linked
 *  PathNodes. PathNodes are manually placed. NavigationMeshes uses
 *  Pylons and other type of actors, so the two systems are different.
 *
 ******************************************************************/
state PathFind
{
Begin:
	if( RouteCache.Length > 0 )
	{
		//for each route in routecache push a ScriptedMove state.
		ScriptedRouteIndex = 0;
		while (Pawn != None && ScriptedRouteIndex < RouteCache.length && ScriptedRouteIndex >= 0)
		{
			//Get the next route (PathNode actor) as next MoveTarget.
			ScriptedMoveTarget = RouteCache[ScriptedRouteIndex];
			if (ScriptedMoveTarget != None)
			{
				`Log("ScriptedRoute is launching ScriptedMove index:"@ScriptedRouteIndex);
				PushState('ScriptedMove');
			}
			else
			{
				`Log("ScriptedMoveTarget is invalid for index:"@ScriptedRouteIndex);
			}
			ScriptedRouteIndex++;
		}
		PopState();
	}
}

What this state does is to check if there is paths calculated beforehand. If there is a path list, then an iteration cycle goes on to push a ScriptedMove for each destination. This will fill the state stack with multiple states that will try to reach the destination. Now remember that at the beginning of StartFire there is a PopState(true). This means that if we interrupt the pathfinding with a mouse click the parameter TRUE specify to eliminate all states from the stack. So you will not loose the control of the pawn while it tries to reach a destination.

The very last element to see in this long tutorial is the state that makes the magic of path finding work. This function, again is taken from AIController :

/******************************************************************
 *
 *  TUTORIAL STATE (ScriptedMove)
 *
 *  This is the state that is put on the state stack for each PathNode
 *  found when pathfinding. So if you click on a destination and it has
 *  3 PathNode on its route, this state will be stacked 3 times for
 *  moving to a destination. The destination actor represented
 *  by ScriptedMoveTarget is the PathNode.
 *
 ******************************************************************/
state ScriptedMove
{
Begin:
	while(ScriptedMoveTarget != none && Pawn != none && !Pawn.ReachedDestination(ScriptedMoveTarget))
	{
		// check to see if it is directly reachable
		if (ActorReachable(ScriptedMoveTarget))
		{
			// then move directly to the actor
			MoveToward(ScriptedMoveTarget, ScriptedMoveTarget);
			SetDestinationPosition(ScriptedMoveTarget.Location);
		}
		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, MoveTarget);
				SetDestinationPosition(MoveTarget.Location);
			}
			else
			{
				// abort the move
				`warn("Failed to find path to"@ScriptedMoveTarget);
				ScriptedMoveTarget = None;
			}
		}
	}
	PopState();
}

What we added is the SetDestinationPosition(…) so that when the PlayerMove function execute each frame, the rotation will be set to the destination. Remember you can use the ToggleIsometricDebug command so that the super.DrawRoute(…) in the MyHud class output line trace to each destination.

 

Conclusion

 

Now I hope you liked this tutorial, and look forward to inputs here in the UDK forum, thanks to everybody that has made this possible, here is a list of forum members I would like to thank for their great support :

 

Chris2009
Immortius
Red-Fathom
guineapig
TheSpaceMan
3dxero
JeremyStieglitz

 

 

Get the source code to chapter 5

 

Chapter 6 – Navigation meshes implementation