Introduction : S&S Racing : Quake 3 Rally : Maya md3Export Plugin : AUV : OpenGl Terrain : Texture Blending : Physics Tests : Advanced Bot AI : Bot AI :

AUV A* Path Finding Demonstration

• The red dots represent nodes on the closed list.
• The closed list consists of nodes that have already had their children expanded.
• The magenta dots represent nodes on the open list.
• The open priority queue consists of nodes that have not been expanded yet and that are adjacent to closed nodes. They are ordered based on the heuristic distance from start to goal through the node (lower is better).
• The blue dot is the current node.
• The green dot is the goal node.
• The blue line is the path of linked nodes that was found.
• The black circle is the AUV.
• The grey areas are barriers and the AUV cannot pass through them.

Overview of how it works:

1. Terrain and Node setup:
   1. First the "terrain" image is loaded.
   2. Initialize the trace object.
   3. A two demensional array of nodes is created.
   4. Nodes that are in the solid region of the terrain are removed.
   5. Connections between adjacent nodes if terrain is not blocking the path between them.

2. Create AUV "Bot":
   1. Initialize bot variables
   2. Get closest node and set it to current node and goal node

3. AUV Think:
   1. If the goal has changed since the last think find a new path to the goal (see "Finding the Path" below)
   2. Run post-smoothing of the path.
   3. Reverse the parent list so the node list goes from current -> goal.
   4. If more than 4 pixels from the current node move towards it.
   5. If less than 4 pixels from the current node then change current node to the next node in the list.

4. Finding the Path:
   1. Setup the open (priority queue) and the closed (regular list) lists.
   2. Setup the current node and estimate the distance to the goal.
   3. Push the current node onto the open list.
   4. While the bestNode is not the goalNode do this:
      1. If open is empty then exit because we cant get to the goal.
      2. Pop a node from open (bestNode) and place it on closed.
      3. Approximate the distance from bestNode to its successors (adjacent nodes)
      4. For all four successors:
         1. If bestNode doesnt have a successor in this direction (bestNode is against a wall) then just continue with the next successor.
         2. If the successor is on the open list check if the distance to it from the start is less than the distance to it through bestNode.
            1. If it is then change the successors parent node to bestNode and set its g and h values and update its position in the priority queue.
            2. If not then just continue.
         3. If its not on the open list, is it on the closed list and is the distance to it from the start less than the distance to it through bestNode?
            1. If it is then change the successors parent node to bestNode and set its g value and update its position in the priority queue. (Should also be propagating the new distance value down the tree)
            2. If not then just continue.
         4. If its not on the open or closed lists then set its parent to bestNode and estimate its distance to the goal.
         5. Add the successor to the open list.

Last Updated: Sept 8th, 2002

Email me at: stonelance at quakerally dot com