Tutorial 12: Path Finding – A-Star algoritm by Osama Hosam

Introduction

In strategy games, the avatar is moving from a place to another, without hitting the wall or walk through a mountain. How this is done? In computer science there is some kind of branch called “Obstacle avoidance” this branch studies how the character can move on the map and avoid obstacle while he is walking. In this tutorial we will show how to do the best obstacle avoidance practice by examining one of the most important path finding algorithms, namely A Star algorithm. Its importance came from that it not only find the path but it finds the best path. It is extensively used in strategy games.

A Star Algorithm

Suppose we have a map and we have an object, we want to move this object from its current position to the target position. The intuitive way is to find a straight line connects the object to the needed target. But what happen if the line passes through an obstacle. In real world this is not permitted, since the object can’t walk through walls for example. See the next figure

A-star solves this problem by examining the neighbor nodes, and finds the best one suitable to be the next step to the target. A start uses two types of lists; the first list is called the Open List which contains all the neighboring nodes to the current node, we call this current node the Parent node of all nodes in its neighborhood. The second list is the Closed list which contains the current node. The node structure can be defined as

 struct NODE { int StartCost; int TotalCost; int X,Y; int ParentX,ParentY; //parent x,y };

Where start cost is the cost from the current node to get back to the first node, it calculates how hard the object needs to walk to get to the original position. The total cost can be calculated as the following

Total cost=Base cost + Start Cost + Goal Cost

The base cost is the terrain cost for each node, for example if the node is a wall it will take cost higher than the grass. The grass can take higher base cost than road nodes. In our program we will used two types of base cost 0 for grass nodes and 1 for any other node. So the object can only walk on the grass nodes.

The Goal cost calculates how much distance is needed to reach the target or the goal. If the object is at x1, y1 and the goal is at xg, yg the goal cost will be calculated as

Goal cost = |xg – x1| + |yg – y1|

The next figure shows the costs and the total cost for every open node in the Open List

The AStar algorithm contains the following steps
Step 1: Add the start node to the Closed List.
Step 2: Find all the neighboring nodes to the node in step 1. Add them all to the Open List
Step 3: Find the minimum node with the lowest total cost and add it to the closed list.
Step 4: Remove the node with the lowest total cost from the Open List.

After building the Open List and the Closed List (reach the goal) we back track them to find the path. The path can be examined by examining the goal node’s parent and then examining the parent of the goal node’s parent and so on until we reach the start node. This way we will get the right path.

The program Structure

The program contains a map, the map is reconstructed by 2D tiles the main tiles of the map are

• Grass tiles, this tile can be easy for the object to walk on.
• Tree tile, an obstacle
• Stones tile, an obstacle
• Bush tile, also an obstacle.
• In addition to the start tile (rabbit image), goal tile (red pin) and the track tile (feet track)

The map is built by using the above tiles, no more. We constructed a 20 by 20 tiles map as shown in the following figure

We have reconstructed the tile map as 2D array; we have shown in previous lessons how to reconstruct the map with 1D array. We have changed little bit to the 2D array to show the flexibility of having more than one solution for the same problem. We defined a Node structure as shown previously. Also we defined a CPath class in which we create the path needed for the rabbit to move from its current position to the goal. In our article we will concentrate only on making the path, we will leave the construction of the map as a practice.

The CPath class

The CPath class member functions are shown in the following code

 
class CPath 
{ 
 private: 
  vector &lt NODE > 
  OpenList,ClosedList; 
  int obstruction[20][20]; 
  int start_x,start_y; 
  int goal_x,goal_y; 
 public: 
  CPath(); 
  virtual ~CPath(); 
  SetObstructionMatrix(unsigned int map[20][20],unsigned int ground,unsigned int start,unsigned int goal);
  InsertIntoClosedList(int total_cost,int start_cost,int x, int y);
  InsertIntoOpenList(int x,int y); 
  vector &lt NODE > 
  DeleteElement(vector &lt NODE > nodesList,int x,int y); 
  bool IsElementExits(int x,int y); 
  NODE MinNode(vector &lt NODE > ); 
  Create(); 
  ClearAll(); 
  vector &lt NODE > 
  BackTrack(); 
  NODE GetNodeAt(int x,int y); 
 };

We have defined two lists, the OpenList and the ClosedList, we defined them as c++ vectors. You need to understand what vectors are so you can continue with this article. The obstruction matrix is needed to define the places in which the rabbit can’t walk. It is reconstructed inside the following function

 
CPath::SetObstructionMatrix(unsigned int map[20][20],unsigned int grnd,unsigned int strt,unsigned int gol) 
{ 
 //we set the ground tiles to be zero 
 //we also set the tree,bushes, stones tiles to be 1 
 //the start is set to 8 and goal is set to 9 
 for(int i=0;i < 20;i++) 
 { 
   for(int j=0;j < 20;j++) 
   { 
    if(map[i][j]==grnd) obstruction[i][j]=0; 
    else if(map[i][j]==strt) 
    { 
     obstruction[i][j]=8; 
     start_x=i; 
     start_y=j; 
    } 
    else if(map[i][j]==gol) 
    { 
     obstruction[i][j]=9; 
     goal_x=i; 
     goal_y=j; 
  } 
  else obstruction[i][j]=1; 
 } 
} 
}

The function takes the map_tiles and search for the start and goal, it sets a specified number corresponding to each type of tiles. It sets 0 to the grass or ground tiles, 8 to the start tile, 9 to the goal tile, and 1 to any else tile. The InsertIntoOpenList function inserts a node into the Open List the implementation of this function is shown in the following code

 
CPath::InsertIntoOpenList(int x, int y) 
{ 
 //node must be inside the boundary of the map 
 if(x < 20 && y < 20 && ClosedList.size() > 0 && !IsElementExits(x,y)) 
 { 
  NODE tempNode; 
  //the tile must be ground tile, so it will be passable 
  if(obstruction[x][y]==0) 
  { 
   int base_cost,cost_to_start,cost_to_goal; 
   base_cost=obstruction[x][y]; 
   cost_to_goal=abs(x - goal_x)+abs(y-goal_y); 
   cost_to_start= ClosedList.back().StartCost + base_cost; 
   tempNode.StartCost=cost_to_start; 
   tempNode.TotalCost=base_cost+cost_to_goal+cost_to_start; 
   tempNode.X=x; 
   tempNode.Y=y; 
   tempNode.ParentX=ClosedList.back().X; 
   tempNode.ParentY=ClosedList.back().Y; 
   OpenList.push_back(tempNode); 
  } 
  else if(obstruction[x][y]==9) 
  { 
    tempNode.StartCost=0; 
    tempNode.TotalCost=0; 
    tempNode.X=x; 
    tempNode.Y=y; 
    tempNode.ParentX=ClosedList.back().X; 
    tempNode.ParentY=ClosedList.back().Y; 
    OpenList.push_back(tempNode); 
   } 
  } 
}

It calculates the node’s info and adds the node to the Open List, First it calculates the base cost which is taken from the obstruction map, the cost to goal and cost to start will be added to the base cost to construct the total cost. The parent node of the nodes in the Open List will be the last node in the closed list, which is presented as ClosedList.back();. The DeleteElement function deletes a node at position x, y from the given list. The MinNode function iterate through the list to get the node with the lowest total cost. Here is the implementation of the MinNode function

 
NODE CPath::MinNode(vector &lt NODE > nodesList) 
{ 
 NODE minNode; 
 if(nodesList.size() > 0) 
 { 
  minNode=nodesList[0]; 
  for(int i=1;i < nodesList.size();i++) 
  { 
   if(nodesList[i].TotalCost < minNode.TotalCost) minNode=nodesList[i]; 
  } 
  return minNode; 
 } 
 else 
 { 
  //return an error 
  minNode.StartCost=-1; 
  minNode.TotalCost=-1; 
  minNode.X=0; 
  minNode.Y=0; 
  return minNode; 
 } 
}

If the list is empty it will return an empty node to show that there is an error. The Create() function is to create a path by using the A-Star algorithm here is the implementation of it

 
CPath::Create() 
{ 
 //Clear previous lists 
 ClearAll(); 
 //add the start node to the closed list 
 InsertIntoClosedList(0,0,start_x,start_y); 
 int next_x=start_x; 
 int next_y=start_y; 
 while(obstruction[next_x][next_y] != 9 && next_x < 20 && next_x > =0 && next_y < 20 && next_y > =0) 
 { 
  //take all the neighboring passable nodes and add them to the OpenList 
  InsertIntoOpenList(next_x+1,next_y); 
  InsertIntoOpenList(next_x+1,next_y+1); 
  InsertIntoOpenList(next_x,next_y+1); 
  InsertIntoOpenList(next_x-1,next_y+1); 
  InsertIntoOpenList(next_x-1,next_y); 
  InsertIntoOpenList(next_x-1,next_y-1); 
  InsertIntoOpenList(next_x,next_y-1); 
  InsertIntoOpenList(next_x+1,next_y-1); 
  //find the min node 
  if(MinNode(OpenList).StartCost != -1) 
  { 
   NODE minNode=MinNode(OpenList); 
   ClosedList.push_back(minNode); 
   next_x=minNode.X; 
   next_y=minNode.Y; 
   //delete the minimum node from the open list 
   OpenList=DeleteElement(OpenList,next_x,next_y); 
   } 
 } 
}

The two lists are cleared, next
1- The first node is added to the Closed List, the first node is the place which the rabbit stands on.
2- The while loop iterate until it finds the goal node which is known by 9. Then it goes through all the passable neighboring nodes and adds them to the Open List.
3- The min node in the Open List is added to the Closed List, and then the next node will be the min node so we set the next_x to be min node’s x and next_y to be min node’s y.
4- Last step, the min node is deleted from the Open List.
Now the Closed list contains the path elements, In order to get the right path we need to back track the path. This is done by using the function BackTrack it has the following code

 
vector &lt NODE > 
CPath::BackTrack() 
{ 
 vector &lt 
 NODE > pathL; 
 int k; k=0; 
 for(int i=ClosedList.size()-1;i > -1;i--) 
 { 
  NODE tempNode; 
  tempNode=GetNodeAt(ClosedList[i].ParentX,ClosedList[i].ParentY); 
  if(tempNode.TotalCost != -1) 
   pathL.push_back(tempNode); 
  } 
  return pathL; 
}

The function iterates through the closed list nodes from its end back to its beginning. It gets the parent node of the current node.

Using CPath classM

The CPath class will be used in our program with mouse clicks. So the left mouse click will set the start position or the position of the rabbit and the right click will set the goal and create the path.

 
vector &lt 
NODE > pathL; 
CPath pathCreator; 
void Mouse(int button, int state,int x,int y) 
{ 
 int mouse_tile_XPos=x/tile_size+g_XPos; 
 int mouse_tile_YPos=y/tile_size+g_YPos; 
 switch (button) 
 { 
   case GLUT_LEFT_BUTTON: 
    if (state == GLUT_DOWN) 
    { 
     //left clicked 
     ClearTrack(true); 
     map_tiles[mouse_tile_XPos][mouse_tile_YPos]=start; 
     } 
    break; 
   case GLUT_RIGHT_BUTTON: 
    if (state == GLUT_DOWN ) 
    { 
      //right clicked 
      ClearTrack(false); 
      //set the goal position 
      map_tiles[mouse_tile_XPos][mouse_tile_YPos]=goal; 
      //create the path 
      pathCreator.SetObstructionMatrix(map_tiles,ground,start,goal); 
      pathCreator.Create(); 
      pathL=pathCreator.BackTrack(); 
      //set the path to the map 
      for(int i=0;i < pathL.size()-1;i++) 
      { 
        map_tiles[pathL[i].X][pathL[i].Y]=track; 
      } 
      map_tiles[pathL[i].X][pathL[i].Y]=start; 
      //clean the path list 
      pathL.erase(pathL.begin(),pathL.begin()+pathL.size()); 
      } 
      break; 
      default: 
       break; 
    } 
 }

Two variables have been defined, pathL, and pathCreator. pathL holds the path nodes. And pathCreator is an instance of the CPath list, which will create the path by AStar algorithm.

In the left click GLUT_LEFT_BUTTON event the start node will be set to the click location of the mouse on the map. In the right click GLUT_RIGHT_BUTTON event, goal node is set to the goal position which is the current mouse click location on the map. The obstruction matrix is created and then the path is created and back tracked. The path is “printed” on the map by looping through all nodes in the path and set them on the map.

The source code

Click here to download the source code of this tutorial.