Waypoints Technical Guide

Document Summary: A quick guide to hooking up your AI to use a Path Node-based network.

Document Changelog: Created by Steve Polge; updated by Matt Tonks.

Overview

This is a quick and dirty guide to hooking up your AI to use a a series of pathnodes.

Way Points and Path Nodes

Navigation is based on a pre-generated path network. As this path network doesn't cover 100% of the areas a bot may traverse, they also have to be able to perform localised assessment and navigation of the environment, which they sample for these purposes using collision traces, as well as inspection of nearby objects in the collision data structure.

Key Points and other Navigation Points

JumpDests/JumpSpots

JumpDests/JumpSpots were removed. A reachspec will still be generated between two points even if it requires a jump to get between them. The AI is told it needs to jump between these points via setting a flag on the reachspec (see reach flags). It looks like they were removed from Engine, but we still have something similar in Gears of War, which we use for points which the AI couldn't normally jump to but we want to 'force things'. (For example a very long drop off which we want to force AI to use in special circumstances.)

Anchors

An anchor Is it simply a NavigationPoint that has only one other NavPoint attached to it. It is the bot's anchor point into the path network. More specifically an anchor is a navigation point that the bot can directly reach (without pathfinding). This is also where path searches are started from for this bot. The first step of pathfinding on any sort of path graph is to find the most appropriate start and end points on the graph in order to generate a path between them. The anchor represents the start point for the bot's path searches, such that after calling findpathtoward you will have a route from anchor to goal.

The only time raycasts are done (during runtime) is to determine if a point or object can be directly reached. That said, if path networks that are generated in the editor, then raycasts are performed between navigation points in order to determine reachability (This is what happens when you push the Build Paths button).

Controllers

Functions

ReachedDestination

This function is queried by an AI during a move in order to ascertain whether or not it should consider the object it is currently moving toward as 'reached'. In other words, the AI calls this to decide whether it should stop moving to the current destination, and either move on to the next object in its route or stop moving altogether because it has arrived at its overall goal. Note that this function calls 'reachedby' on the actor the AI is trying to move to which gives custom objects a chance to have a say in when an I should stop trying to move to it. A good example of how this is useful is on very large objects. Normally an AI would try and run to the location of the object until it is inside some radius of said object, but if it has collision which is larger than the radius its checking against obviously this would cause problems. For objects such as this you could just override reachedby to take into account its custom dimensions.

ActorReachable

The AI call this function to decide if an object is directly reachable or not. Meaning, can the AI run in a straight line to the object without running into something (that it can't jump over). This is used during moves to decide a few things, but a good example is when it uses this function to decide if it should run straight to its destination, or try and path there via the path network.

FindPathToward

This function will do execute a traversal of the path network generating a route from the bot's position to the passed goal, placing the generated route (An ordered list of waypoints from bot position to bot goal) in the routecache of the controller. This will tell the bot what waypoints to move to in order to each its goal.

FindPathToward determines how to travel towards an actor? by first ensure that the bot's anchor is valid (and try to find a new one if it's not), and then run a traversal across the path network to generate a route from the anchor to the goal. Once this route is generated the bot will run toward the first point in the route directly, until ReachedDestination determines it has arrived at the waypoint, which will then trigger the bot to run to the next waypoint in the generated route.

FindPathToward just generates the route for the bot to use, so if you're seeing bots clipping or rounding corners and getting stucka s a result, something else is awry. It's best to use show paths to see if lines (reachspecs) are going through the corner.

MoveTo

This is a latent function which moves the bot directly to the passed point, and finishes on arrival. This function does no pathfinding, it just directs the pawn straight toward the target.

MoveToward

This is very similar to MoveTo, except it takes an actor as a destination and has some special handling that makes use of this extra data. (will set anchor if the bot is moving toward a navigation point, etc.).

ActorReachable

It's best to view the source code for examples. Start with APawn::actorReachable in UnPawn.cpp. That said, at a high level what this function does is as follows:

1. try and early-out by determining if the actor we're checking against is on a reachspec we are standing on, or if the destination actor is within the radius of a navigation point we are also within. (Assumes reachspecs/nav points are always valid to walk along, as they are verified off-line).
2. does a quick raycast to see if the destination is visible at all and early outs if it's not
3. check to see if the destination actor is above solid ground
4. calls APawn::Reachable which will simulate the move to the destination (dependant on physics mode) and determine if it's possible to reach that point. For example if the bot is in PHYS_Walking it will call walkreachable and move simulate walking toward the destination and determine if it can be reached via walking/jumping. (see APawn::walkReachable in UnPawn.cpp)