Navigation graph is basic space representation used for navigation. The map is covered by nodes called navigation points , in short navpoints . Each navpoint is located in some safe location that can be reached by the bot. When there exists direct path from one navpoint to another then they are connected with an edge. With this representation finding a path from navpoint A to navpoint B can be easily solved with any graph search algorithm, particularly popular is heuristic A* algorithm (pronounced "A star"). Output of the path planning algorithm is sequence of nodes that should be followed in order to get to the target location.

Navigation in the level is divided into two stages:

Path planner is object responsible for the first stage of this process. Pogamut comes with several implementations of PathPlanner interface, the default is UT2004AStarPathPlanner. UT2004AStarPathPlanner is a proxy object that provides functionality of Unreal Tournament internal A*, this means that your bot can use exactly the same path planning algorithm as native UT bots. Another planner implementation is FloydWarshallPathPlanner, this class precomputes all paths between all navpoints at the startup which may take some time (the algorithm runs in O(n^3)). The planner is by default automatically instanciated in UT2004BotModuleController. You can create your own instance manually:

        
        // create new UT path planner
        UT2004AStarPathPlanner utPathPlanner  = new UT2004AStarPathPlanner(bot);
        // create new FloyadWarshall path planner
        FloydWarshallPathPlanner fwPathPlanner = new FloydWarshallPathPlanner(bot);
	  

UT2004AStarPathPlanner or FloydWarshallPathPlanner constructors require reference to the bot because it sends some commands to the game engine using the IAct and receives response through IWorldView events. If you want your bot to use different path planning strategy just code your own PathPlanner implementation.

Path executor handles navigating along the given path. It consists of the path navigator (interface IUT2004PathNavigator) that handles the actual navigation along the path and the code that handles for example waiting for the path be be complete (sometimes it takes time before the whole path is computed). Default path executor is UT2004PathExecutor. To implement your own path executor you have to implement PathExecutor class. However in most cases when you want to change the way how the bot navigates through the environment it will be enough to write your own path navigator (this is also recommended way). More about path navigator below. Path executor is instanciated automatically in UT2004BotModuleController class.

Path navigator is an interface responsible for moving the bot along precomputed path, avoid obstacles, open doors, wait for lifts, jump over pits etc. The default implementation of IUT2004PathNavigator interface is LoqueNavigator . Again as in the case of PathPlanner you can provide your own implementation of this interface, for example you can implement new path navigator that will enable the bot to avoid incoming rockets while moving to the target.

Now how it works in our example bot. The API that is most important for bot programmer are followPath(...) and addPathListener(PathExecutorListener) methods of PathExecutor . The followPath(...) method makes the bot follow path computed by some PathPlanner, goToRandomNavPoint() shows example usage of this method:

     /**
     * Picks random navpoint and goes to it.
     */
    protected void goToRandomNavPoint() {
        targetNavPoint = pickRandomNavPoint();
        // find path to the random navpoint, path is computed asynchronously
        // so the handle will hold the result onlt after some time
        IPathFuture<ILocated> pathHandle = pathPlanner.computePath(info.getLocation(), targetNavPoint);
        // make the path executor follow the path, executor listens for the
        // asynchronous result of path planning
        pathExecutor.followPath(pathHandle);
    }

Once the followPath(...) method is called the bot starts moving towards desired navpoint. To get notified about path execution status we have to register listener on path executor:

        // IMPORTANT
        // adds a listener to the path executor for its state changes, it will allow you to
        // react on stuff like "PATH TARGET REACHED" or "BOT STUCK"
        pathExecutor.getState().addStrongListener(new FlagListener<IPathExecutorState>() {

            @Override
            public void flagChanged(IPathExecutorState changedValue) {
                switch (changedValue.getState()) {
                    case PATH_COMPUTATION_FAILED:
                    // if path computation fails to whatever reason, just try another navpoint
                    case TARGET_REACHED:
                        // most of the time the execution will go this way
                        goToRandomNavPoint();
                        break;

                    case STUCK:
                        // the bot has stuck! ... target nav point is unavailable currently
                        tabooNavPoints.add(targetNavPoint, 10);
                        // sometimes the bot gets stucked then we have to return him
                        // to some safe location, try more complex maps to get into
                        // this branch

                        // so if we get stuck, we will try to return to some near navpoint
                        targetNavPoint = pickSecondNearestNavPoint();

                        if (targetNavPoint == null) { // no more navpoints, all are tabooized
                            targetNavPoint = pickRandomNavPoint(); // choose one randomly
                        }

                        // let's get to the chosen navpoint
                        pathExecutor.followPath(pathPlanner.computePath(info.getLocation(), targetNavPoint));
                        break;
                }
            }
        });

Also note stuck detectors - simple modules that can be registred in path executor. These modules signalize when the bot gets stuck. STUCK event will be generated that can be reacted to in FlagListener.

            pathExecutor.addStuckDetector(new UT2004TimeStuckDetector(bot, 3.0));       // if the bot does not move for 3 seconds, considered that it is stuck
        pathExecutor.addStuckDetector(new UT2004PositionHistoryStuckDetector(bot)); // watch over the position history of the bot, if the bot does not move sufficiently enough, consider that it is stuck
        

Each time target location is reached this FlagListener<IPathExecutorState> implementation will make the bot to again choose new random navpoint and go to it. The resulting behavior is that the bot is wandering around the level until stopped.

For debugging it is often useful to see the navigation graph the bot is following. You can visualize the graph in Unreal Tournament itself or in the Netbeans plugin. We will describe both possibilities.

If you are in UT you can easily show the graph by pressing Alt + G . This will add the navigation graph to the rendered image. After pressing this combination you will see graph with set of edges also rendered in the image. Notice that the edges have arrows indicating their orientation. Some edges are only one way, e.g. you can jump down through the window but you cannot get to the second floor by jumping from ground to the window. Another handy shortcut is Alt + R, this will draw a red line showing bots planned path.

Second option how to visualize the navigation graph is to show the whole level in map viewer build in the Netbeans plugin. To show this map double click UT server node.

As you can see the view shows only navigation graph and your connected bot.

Controlling the map:

The geometry of the level itself is not shown. The map is most useful when debugging team strategy.

To add a new bot: right-click on NavigationBot ("Projects" tab) and press "Run" (or "Debug").

Added bot will appear on your map as another dot. You can add as many bots as you want.

And to remove bot go to Local UT (server node), Pogamut bots and here right-click on some of those and press "Kill".