Path Planner Application Manual

Path Planner Application Manual

User Manual

The Toolbar

Developer Manual

Introduction

Representing the Map

Standard Template Library

The CPathPlannerApp Class

The PathPlannerBase Interface

The PlannerNode Class

The Algorithms

Breadth-First

Best-First

Dijkstra

A*

A* Additions

A* On Node Mesh

User Manual

The Toolbar

The (Open CollisionMap) button allows the user to open a collision map. The collision map is the map on which the planning occurs. The application open Data\CollisionMap\CollisionMapBop.bmp as default relative to the application executable.

The (Application Settings) button brings up the application settings dialog. The dialog allows the user to select a planning algorithm, specify the start and goal coordinates, and specify/view other application settings.

The (Create Planner) button initializes an instance of the planner selected in the application settings dialog. If the selected planner has not been instantiated yet, it creates an instance of it.

The (Destroy Planner) button destructs the instance of the planner specified in the application settings dialog.

The (Start Planner) button signals the application that the planer should start the planning process. If an instance of the planner does not exist, one is created.

The (Pause Planner) button pauses the planning process.

The (Stop Planner) button stops the planner.

The (Planner settings) button allows the user to bring up planner specific settings. Note that some planners may not require additional settings. These settings are local to the planner and if the planner is destructed, the default settings will be restored.

The (Planner Information) button exposes the statistics and information about the selected planner.

The (Draw Progress) button toggles the drawings performed by the planner. When the button is not pressed, the planner will only be allowed to draw after it has completed the planning process. This feature is useful when timing the performance of a planner.

The (About Help) button brings up the about help dialog.

Developer Manual

Introduction

The path planner application is designed to allow for convenient creation, demonstration, and analysis of different path planning algorithms. In this manual the term path planner refers to the application component that performs the planning, and the term path planner application refers to the application itself. Developers can create a new planning algorithm and study its characteristics.

The application settings dialog allows the user to specify settings for the application. For example, it allows you to select a planning algorithm and specify some global settings such as the start and the goal coordinate. Once an algorithm is selected, the run controls can be used to run, pause, and stop the planner.

This tutorial covers planning algorithms that are derivatives of the Breadth-First algorithms. Even the A* algorithm is a modified version of the Breadth-First algorithm. The ultimate goal of this tutorial is to help you understand the A* algorithm. Instead of jumping right into A* we will first implement Breadth-First, Dijkstra, and Best-First. These algorithms are similar in many ways and by implementing them first, you will be able to better understand the A* algorithm. Implementing A* is not a hard task but it is more important to understand why it was developed and how it is different from other algorithms.

As you go through the tutorial be sure to compare your algorithms to the completed version to make sure you are on a right track. Keep in mind that writing code that performs many operations and loops many times can be harder to debug. Expect to run into bugs but use caution to avoid them.

Representing the Map

The collision map is a bitmap that represents the map the path planning occurs on. The black regions represent obstacles. The white and gray regions represent the passable regions. They represent regions with cost 1, 2, 3 and 4 respectively. The lighter the color the less it costs. These regions represent costs such as resources or the risk involved. Not all planning algorithms understand weighted regions and assume that all passable regions are weighted equally.

To represent the small-scale version of the world, many games use a graph/mesh of points (waypoints), polygons, or volumes. The nodes of such graph contain information such as the location of the node and a list of connections to other nodes. For example, two connected waypoints can represent a simple hallway. A simple hall way can also be represented as a convex polygon. Either way, you can use the data in these graphs to resolve paths between two points. The nodes of the graph can contain additional data to indicate that the entity should be climbing or crawl through a region. Tile based Games such as War Craft III and Age of Empires simply use a 2D grid. Here we assume that the world is represented as a 2D grid. Please note that a 2D grid is a specific case of a node graph where all the nodes are aligned and are connected to no more than eight immediate neighbors. A mesh of triangles (navigation mesh) is a specific case of a node graph that can have up to three connections. The algorithms covered here can be easily modified to work on an arbitrary graph of nodes.

Standard Template Library

If you are not familiar with the STL, I recommend that you go to read up on it. You can even look through Microsoft’s newer STL documentations (7.0 and up) for sample code. Here are the list of classes and functions you should be familiar with:

list (doubly linked list)
push_front, push_back
pop_front, pop_back
front, back
begin, end
empty, clear
size
vector (dynamically growable array)
operator []
inser, erase
empty, clear
size
// This data structure is not as critical to know
map (internally represented as a binary search tree, it can be used for fast searches
for an object paired with or mapped to a unique key)
operator [] // for convenient insertion (and retrieval) of objects using a key
find // checking if a value has been mapped to a key

Once you implemented the algorithms you can go back and optimized your code by using your own data structures. This will payoff significantly for the list data structure, but not as much for the vectors. Since STL linked lists cannot require you to only put data in it that have a next and a previous pointer, every time you insert a node into an STL’s list, additional memory is allocated that contains the next and previous pointers in addition the data.

The CPathPlannerApp Class

This class is the application’s main class. It extends the CWinApp class, which store a pointer to the window. Once the application has been initialized, it acts as a state machine that provides the planner with some processing time. Here are some of the more important members of this class

static CPathPlannerApp *instance;

ApplicationStateapplicationState;

PathPlannerBase*planner;

int **collisionMapData;

This class is a singleton, which means that the member variable instance points to the only instance of the class. The member applicationState stores the current state of the application and is used to decide what actions are valid in different stages of the planning, as well as which function of the planner should be called. The member planner stores a pointer to an instance of the planner that is specified in the application settings dialog. collisionMapDatais a dynamically allocated 2D array that stores the data of the collision map. This array is populated by 1, 2, 3, 4 and –1 to indicate the weight (or cost) at different locations of the terrain. Regions that represent obstacles are set to –1. The line bellow demonstrated how to retrieve the terrain cost at the coordinate (x, y).

int mapData = CPathPlannerApp::instance->collisionMapData[y][x];

Please note that the first index of the array is y and the second index is x (as typically expected).

The PathPlannerBase Interface

The application communicates with a planner through the PathPlannerBase Interface. Every planner should extend PathPlannerBase. The Interface defines the following functions:

virtualvoid PlanPath(int ix, int iy, int gx, int gy);

virtual void Run();

virtualbool IsDone();

virtual void Draw(CDC *dc);

virtualvoid Settings();

virtualvoid ShowInfo();

virtualvoid CleanUp();

First thing you should notice is that all the functions are virtual and meant to be overridden. When the button is pressed the application initializes an instance of the currently selected planner as indicated in the applications settings dialog. If an instance of the planner does not exist, a new one is constructed. Otherwise, the existing instance is reused (CleanUp is called). Here is what happens when the application is in the run state:

void CPathPlannerApp::StateRun(){

runCount++;

//Allow the planner to run. The planner should try to spend //approximately as much time as indicated by the timeSlice

planner->Run();

if (drawProgress){

// cause a repaint

pFrame->GetChildView()->Invalidate(FALSE);

}

if (planner->IsDone()){

applicationState = STATE_RUN_END;

}

}

The sections bellow explain what the overwritten functions should do

PlanPath (…)

The PlanPath(…) function is used to tell the planner that the planning process is about to begin. It is called when the button is pressed. In this function, you can perform some initialization and store the start and goal points.

Run ()

Immediately after PlanPath(…) is called, the Run functions is called. The application repeatedly calls the Run function until the planer indicates that it no longer needs processing time. The Run function is where the planning occurs. It is extremely important to note that the Run cannot hold on to the thread for a long time. You are responsible for making sure that it returns after spending approximately CPathPlannerApp::instance->timeSlice. This is critical because if the run function takes too long, the application will not get the chance to respond to events such as resizing, moving, and most importantly painting. You can think of the application having a game loop. Any single function called by the application cannot take too long because the game will not be responsive. In other words, the planning process must be split across frames. It may sound like this will significantly complicate the planner code, but that is not the case. Algorithms such as Breadth-First, Dijkstra, Best-First, and A* can easily be split across frames. If you store the state of the planning when the Run function returns, you can continue the process the next time the function is invoked. Since this function is called repeatedly by the application, it is important not to perform any initialization in it. Initializations can be done in PlanPath or and some in the constructor.

IsDone ()

This function is called by the application to find out whether or not the planner has completed the process. This function should return false if you wish the run function to get called again, and true to indicate that the planer is done.

Draw (…)

When drawProgress is true and the run function returns, the application invalidates the content of the window, which in turn causes the Draw function of the planner to get called. The function can draw any debugging/visualization data on the map to allow the user to see what the planner is doing. Please note that you should never call Draw directly. Following this guideline allows the user to enable/disable the drawings of the planner in order to speed up or time the process. The draw function can, for example, you can call set pixel to set a pixel (or grid cell) to a specific color.

dc->SetPixel(x, y, RGB(0, 0, 255));

Settings ()

When the planner settings button is pressed on the toolbar, the application calls the settings function of the planner. This allows the planner to popup a dialog box in order to collect planner specific settings. Note that these settings are local to the planner and not saved when the planner is destroyed.

ShowInfo ()

When the planner Information button is pressed on the toolbar, the application calls the showInfo function of the planner. This allows the planner to display statistics/summery of the planning process.

CleanUp ()

This function is called when the application decides to reuse the instance of the planner. A planner is reused when is pressed and an instance of the planner has already been created (or is grayed out). You should also call this function from the destructor of your planner as well. It is your responsibility to ensure that the cleanup function does not fail if it is called when the planner has not done any planning.

The PlannerNode Class

A path can be described as an ordered list of sub-destinations. Instances of the PlannerNode class are used to represent a path between the start point and an arbitrary point on the map, which may be the goal. The node class needs to store a position as well as a parent pointer. By chaining nodes together using the parent (or previous) pointer, we can represent a path (or a candidate solution). Note that this node class is not exactly a waypoint node. A waypoint node is used to represent the connectivity of a map, whereas the PlannerNode represents a specific path through a map and is used strictly by a planning algorithm. A clear distinction between them is that a waypoint node only needs sibling pointers, but a PlannerNode only needs a parent pointer. The PlannerNodes are used to keep track of how we got to a spot on the map as opposed to where we can possibly go from a spot on the map.

A linked list of nodes that represent a path from goal to start

The Algorithms

During the planning process we will come across many different paths that may lead us to the goal, and therefore need to keep track of them. By keeping track of them, we will be able to come back to them in order to create additional paths that extend them. By creating additional paths that extend existing paths, we will be able to work our way through the map in search of the goal. The open list (green) will keep track of paths that are open for consideration (or being extended), and another list, the closed list (blue), will keep track of paths that we have already considered.

Figure 1

Figure 1 is a snapshot of a planner in process. Nodes in the open list are green and nodes in the closed list are blue. The open list contains paths that are yet to be extended. The closed list contains paths that used to be in the open list. They have already been extended and check to see if they had ran into the goal. It is important to note that each node in the open list indicates the head of a path that ends at the start point (upper left corner in the image above).

Figure 2

Figure 2 shows two different paths (red and pink) that partially overlap. Each path is a linked list of nodes that start at a green spot (a node in open) and end in the start point. The paths in the image are only two of the many different paths.

The different algorithms such as Breadth-First, Dijkstra, Best-First, and A* have a lot in common. They all share the pseudo code below, which is absolutely fundamental to understand.

1. Create a node for the start point and push it into the open list
2. While the open list is not empty
3. Pop a node from the open list and call it currentNode
4. Check to see if it is at the goal. If so, we can exit the loop
5. Create the successors of currentNode and push them into the open list.
6. Put the currentNode in to the closed list

Pseudo-code 1

The idea is simple. We want to examine the map in order to find a path between the start and the goal. We start traversing the map and for every spot we reach we will create a node that points to its parent. We will repeat this until we reach the goal. Once we find the goal, we will follow the parent pointer of the node that reached the goal in order to find out how we got to the goal. The root node will be the only node without a parent.

The algorithms first create a root node and push it into the open list. They then loop until they have examined every node in the open list. Note that the first iteration of the loop the only node in the open list, the root node, is popped from the list. This means that if we fail to push additional nodes into the list, the loop condition will evaluate to false. In the body of the loop, the algorithms attempt to create the successors of the currentNode. These successors are in essence extensions to the path that currentNode indicate. Once the successors are generated and pushed into the open list, the currentNode is pushed into the closed list.

Before creating a successor node, the algorithms make sure that there is no more than one node for any given spot of the map. This is to prevent unnecessary re-exploration of different parts of the map. For example, there is no need to store more than one path between the start and a specific point on the map. To prevent re-exploration of the map, before creating a successor node, we have to see if we have already made a node for that spot of the map. In order to do so, they have to check the open and the close list. This step can be very expensive (unless you use a data structure that offers fast lookups such as hashTable or hashMap), but is still a sound thing to do. Not catching redundant nodes can result in substantial consumption of memory as well as substantially longer time to find the goal.