Navigation Network

The NavigationPoint Network

NavigationPoint Networks refers to the method of path finding that Unreal / Unreal Tournament bots utilize. Though a class attempting to cover all aspects of navigation AI would far exceed the bounds of a simple tutorial, I will explain the basics of the NavigationPoint Network, as well as what Unreal / UT does with the bots.

Knowing the Path

The NavigationPoint Network uses a 'network' of 'nodes' (usually pathnodes) to find its' way around a level. The names are a resultant of the similarities in nature of the method - like a telephone or computer network, each node is a connection point, and connections between nodes are the available paths of travel on the network.

Using the Path

In order to use the network, there are several requirements : a Pawn subclass with proper variables set and a map with a network properly built. Let's break it down a bit further.

Pawn subclass. A Pawn subclass would be a Bot, Player (via PlayerPawn), or a ScriptedPawn (there are more, these are just examples). Pawns access the network via two native functions - FindPathTo() and FindPathToward(), the difference being FindPathTo() tries to find a path to a particular location while FindPathToward() tries to find a path to a particular Actor. The functions are declared as such :

 native(518) final function Actor FindPathTo(vector aPoint, optional bool bSinglePath, optional bool bClearPaths);

• aPoint is the location in world coordinates you want to find a path to
• bSinglePath will tell the function to try to find a no hop (straight shot) path
• bClearPaths will tell the function to wipe clear the RouteCache array, where the paths are stored. If this is False or omitted, the found path will be added to the end of whatever path is in RouteCache already.

 native(517) final function Actor FindPathToward(actor anActor, optional bool bSinglePath, optional bool bClearPaths);

• anActor is the Actor the function will try to find a path to
• bSinglePath will tell the function to try to find a no hop (straight shot) path
• bClearPaths will tell the function to wipe clear the RouteCache array, where the paths are stored. If this is False or omitted, the found path will be added to the end of whatever path is in RouteCache already.

In order for these two functions to do you any good, the Pawn subclass must first have it's collision set to (bCollideWorld, bCollideActors, bBlockActors, and bBlockPlayers), the DefaultProperty values of those four bools need to also be set to True, the CollisionHeight and CollisionRadius must be non-zero, and the Pawn subclass must be standing on the ground. If these conditions are met, a call to FindPathTo/ward will result in the array RouteCache to be modified/filled according to whether or not a route was found and if bClearPaths was True, False, or omitted. Keep in mind that simply calling FindPathTo/ward() will not result in movement. Custom AI will have to handle the actual movement based upon the RouteCache array, while Bots and other Pawn subclasses are complex, with states doing many different things. This tutorial couldn't hope to cover the Bot AI without turning into a dissertation.

In-map network. The network layed out in the map has to follow some basic, but simple rules :

• all pathnodes must be close to the ground (within 32 Unreal units). This is not only key and vital, but the cause of more problems when dealing with the pathing network than anything else - literally, despite whatever size CollisionHeight is set to in the Pawn subclass, the pathnodes MUST be within 32 Unreal units of the level geometry below them
• pathnodes must be within 1000 Unreal units in order for a path to be built
• a path is built between any pathnode within LOS (Line Of Sight) of each other.

Paths, when displayed in Ued (right click on a view window's menu area, select View->paths), will be one of two colors :

Blue : the path between the two pathnodes is considered a good path, free of obstruction with enough width clearance
Red : the path between the two pathnodes is considered a poor path, though it may have LOS, there may be level geometry that would interfere with a pawn moving on the straight line between the two pathnodes

In UED2.1 it is:

Blue - Air path, only flying NPC's can use it.
White - Wide path, largest NPC's can use.
Green - Slightly narrowed path, normal NPC's can use it.
Red - Narrow path, only human sized or smaller NPC's can use it (like DM bots).
Purple - Special path, such as elevator or teleporter paths.

What that means blue paths will be taken over red ones, unless there is no other option other than to take a red path. You can prevent red evaluated paths be ensuring enough clearance around the pathnodes as well as the area between them.

Walking the Path

Now you should have all the basic information necessary to understanding how to create and use the NavigationPoint Networks utilized by the Unreal engine. Sadly, there are few to no references written by Epic programmer Steve Polge (originator of the AI used in Unreal / UT) which adequately cover the basics from a programmer's standpoint. Hopefully, you will have found this quick tutorial useful enough to get started on learning the intricate details of the Unreal / UT AI.