Sunday, May 17, 2015

A* Algorithm (or A Star Algorithm) in JavaFX

In a previous blog we created a simple tower defense engine. It's all working nice, but we want the enemies to enter at a given start point and move to an end point. It would all be easy if the path is a given and hence can't be changed.

But as the enemy moves we want to create towers in their way and hence we could block their path. When that happens the enemies will have to find a new path.

One of the commonly used path finding algorithms is the A* Algorithm (aka A Star Algorithm). It's very good described on Wikipedia. The implementation in JavaFX is straightforward, you simply have to follow the pseudo code on Wikipedia using standard Java means.

I'll post the code here, including the pseudo code and how it got translated. Here's what we'll achieve:



What we need first are cells that we can access and in which we can store the variables

  • g = distance from start to current cell
  • h = distance from current cell to goal
  • f = g + h

We use a simple Euclidian distance calculation. You can choose whatever you prefer and whatever your game needs, e. g. distance calculations considering hills and slopes.

The algorithm is implemented as a common algorithm. So you have to map the cells of your grid to the grid algorithm and vice versa when the path is found. To facilitate the mapping, you can store your actual grid cell in the A* algorithm's cell.

And then there's the attribute which tells us if a cell is traversable (i. e. a path candidate) or not.

So the code for a cell could look like this.

 
package application.astar;

/**
 * A virtual cell which defines if it is traversable. The cell is used to store the f,g,h values of the A* algorithm.
 * 
 * @param <T> You can use {@link #obj} to store information about e. g. an external object.
 */
public class AStarCell<T> implements Cloneable {
 
 int col;
 int row;
 boolean isTraversable;
 
 /**
  * A pointer to an object of your choice. Unused in the A* algorithm.
  * Usually you convert your grid to the (virtual) A* grid, then find the path.
  * Afterwards you'd want to find out which of your cells are on the path.
  */
 T obj;
 
 double g;
 double f;
 double h;
 
 AStarCell<T> cameFrom;
 
 public AStarCell( int col, int row, boolean isPath, T obj) {
  this.col=col;
  this.row=row;
  this.isTraversable = isPath;
  this.obj = obj;
 }
 
 public T getObject() {
  return obj;
 }
 
 public double getF() {
  return f;
 }
 
 public double getG() {
  return g;
 }

 public double getH() {
  return h;
 }

 /**
  * Cloning only used in order to show the steps of the A* algorithm.
  */
 public AStarCell<T> clone() {
  
  AStarCell<T> clonedCell = new AStarCell<T>( col, row, isTraversable, obj);
  clonedCell.f =f;
  clonedCell.g = g;
  clonedCell.h = h;
  
  if( cameFrom != null) {
   clonedCell.cameFrom = cameFrom.clone();
  }
  
  return clonedCell;
  
 }
}

Then we need to put the cells into a grid. The grid also knows about the neighbors of the cells, so we implement the algorithm to find the neighbors in there. It's just a matter of checking 8 coordinates.

 
package application.astar;

/**
 * Virtual grid for the A* algorithm. Used to determine the neighbors of a cell.
 */
public class AStarGrid<T> {
 
 AStarCell<T>[][] gridCells;
 int cols;
 int rows;
 
 public AStarGrid( int cols, int rows) {
  this.cols = cols;
  this.rows = rows;
  gridCells = new AStarCell[rows][cols];
 }
 
 public void setCell( T cell, int col, int row, boolean path) {
  gridCells[row][col] =  new AStarCell<T>(col,row, path, cell);
 }
 
 public AStarCell<T> getCell( int col, int row) {
  return gridCells[row][col];
 }
 
 /**
  * Get neighboring cells relative to the given cell. By default they are top/right/bottom/left. 
  * If allowDiagonals is enabled, then also top-left, top-right, bottom-left, bottom-right cells are in the results.
  * @param cell
  * @param allowDiagonals
  * @return
  */
 public AStarCell<T>[] getNeighbors(AStarCell<T> cell, boolean allowDiagonals) {
  
  AStarCell<T>[] neighbors = new AStarCell[ allowDiagonals ? 8 : 4];

  int currentColumn = cell.col;
  int currentRow = cell.row;

  int neighborColumn;
  int neighborRow;
  
  // top
  neighborColumn = currentColumn;
  neighborRow = currentRow - 1;
  
  if (neighborRow >= 0) {
   if( gridCells[neighborRow][neighborColumn].isTraversable) {
    neighbors[0] = gridCells[neighborRow][neighborColumn];
   }
  }

  // bottom
  neighborColumn = currentColumn;
  neighborRow = currentRow + 1;
  
  if (neighborRow < rows) {
   if( gridCells[neighborRow][neighborColumn].isTraversable) {
    neighbors[1] = gridCells[neighborRow][neighborColumn];
   }
  }

  // left
  neighborColumn = currentColumn - 1;
  neighborRow = currentRow;
  
  if ( neighborColumn >= 0) {
   if( gridCells[neighborRow][neighborColumn].isTraversable) {
    neighbors[2] = gridCells[neighborRow][neighborColumn];
   }
  }

  // right
  neighborColumn = currentColumn + 1;
  neighborRow = currentRow;
  
  if ( neighborColumn < cols) {
   if( gridCells[neighborRow][neighborColumn].isTraversable) {
    neighbors[3] = gridCells[neighborRow][neighborColumn];
   }
  }

  if (allowDiagonals) {
   
   // top/left
   neighborColumn = currentColumn - 1;
   neighborRow = currentRow - 1;
   
   if (neighborRow >= 0 && neighborColumn >= 0) {
    if( gridCells[neighborRow][neighborColumn].isTraversable) {
     neighbors[4] = gridCells[neighborRow][neighborColumn];
    }
   }

   // bottom/right
   neighborColumn = currentColumn + 1;
   neighborRow = currentRow + 1;
   
   if (neighborRow < rows && neighborColumn < cols) {
    if( gridCells[neighborRow][neighborColumn].isTraversable) {
     neighbors[5] = gridCells[neighborRow][neighborColumn];
    }
   }

   // top/right
   neighborColumn = currentColumn + 1;
   neighborRow = currentRow - 1;
   
   if (neighborRow >= 0 && neighborColumn < cols) {
    if( gridCells[neighborRow][neighborColumn].isTraversable) {
     neighbors[6] = gridCells[neighborRow][neighborColumn];
    }
   }

   // bottom/left
   neighborColumn = currentColumn - 1;
   neighborRow = currentRow + 1;
   
   if (neighborRow < rows && neighborColumn >= 0) {
    if( gridCells[neighborRow][neighborColumn].isTraversable) {
     neighbors[7] = gridCells[neighborRow][neighborColumn];
    }
   }

  }

  
  return neighbors;
 }

}

Now we got the elements to implement the algorithm. It's really easy to do. Here's the code:
 
package application.astar;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * This is a 1:1 translation of the algorithm on wikipedia: http://en.wikipedia.org/wiki/A*_search_algorithm
 * 
  
   function A*(start,goal)
      closedset := the empty set    // The set of nodes already evaluated.
      openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
      came_from := the empty map    // The map of navigated nodes.
   
      g_score[start] := 0    // Cost from start along best known path.
      // Estimated total cost from start to goal through y.
      f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)
   
      while openset is not empty
          current := the node in openset having the lowest f_score[] value
          if current = goal
              return reconstruct_path(came_from, goal)
   
          remove current from openset
          add current to closedset
          for each neighbor in neighbor_nodes(current)
              if neighbor in closedset
                  continue
              tentative_g_score := g_score[current] + dist_between(current,neighbor)
   
              if neighbor not in openset or tentative_g_score < g_score[neighbor] 
                  came_from[neighbor] := current
                  g_score[neighbor] := tentative_g_score
                  f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
                  if neighbor not in openset
                      add neighbor to openset
   
      return failure
   
   function reconstruct_path(came_from,current)
       total_path := [current]
       while current in came_from:
           current := came_from[current]
           total_path.append(current)
       return total_path
       
 */

@SuppressWarnings("rawtypes")
public class AStarAlgorithm {
 
 /**
  * Get the cell with the minimum f value.
  */
 public class CellComparator implements Comparator<AStarCell>
 {
     @Override
     public int compare(AStarCell a, AStarCell b)
     {
      return Double.compare(a.f, b.f);
     }
 }

 /**
  * Find a path from start to goal using the A* algorithm
  */
 @SuppressWarnings("unchecked")
 public List<AStarCell> getPath( AStarGrid grid, AStarCell start, AStarCell goal, boolean allowDiagonals) {

  AStarCell current = null;
  boolean containsNeighbor;

  int cellCount = grid.rows * grid.cols;
  
  // closedset := the empty set    // The set of nodes already evaluated.
  Set<AStarCell> closedSet = new HashSet<>( cellCount);
  
  // openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
     PriorityQueue<AStarCell> openSet = new PriorityQueue<AStarCell>( cellCount, new CellComparator());
  openSet.add( start);
  
  // g_score[start] := 0    // Cost from start along best known path.
  start.g = 0d;
  
     // Estimated total cost from start to goal through y.
     // f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)
  start.f = start.g + heuristicCostEstimate(start, goal);
  
  
     // while openset is not empty
  while( !openSet.isEmpty()) {

   // current := the node in openset having the lowest f_score[] value
   // note: we have a priorityqueue => for performance reasons we also remove the item instead of removing it later (as suggested in the algorithm)
   // remove current from openset
   current = openSet.poll();
   
         // if current = goal
         //        return reconstruct_path(came_from, goal)
   if( current == goal) {
    return reconstructPath( goal);
   }
   
   // remove current from openset
   // already done in openSet.poll(), see above
    
   // add current to closedset
   closedSet.add( current);
   
   // for each neighbor in neighbor_nodes(current)
   for( AStarCell neighbor: grid.getNeighbors( current, allowDiagonals)) {
    
    if( neighbor == null) {
     continue;
    }
    
             // if neighbor in closedset
                //   continue
    if( closedSet.contains( neighbor)) {
     continue;
    }
    
    // tentative_g_score := g_score[current] + dist_between(current,neighbor)
    double tentativeScoreG = current.g + distBetween( current, neighbor);
    
    // if neighbor not in openset or tentative_g_score < g_score[neighbor]
    if( !(containsNeighbor=openSet.contains( neighbor)) || Double.compare(tentativeScoreG, neighbor.g) < 0) {
     
     // came_from[neighbor] := current
     neighbor.cameFrom = current;
    
     // g_score[neighbor] := tentative_g_score
     neighbor.g = tentativeScoreG;
     
     // f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
     neighbor.h = heuristicCostEstimate(neighbor, goal);
     neighbor.f = neighbor.g + neighbor.h;
     
                 // if neighbor not in openset
                    //   add neighbor to openset
     if( !containsNeighbor) {
      openSet.add( neighbor);
     }
    }
   }
   
  }
  
  // nothing found
  return new ArrayList<>();
 }
 
 /**
  * Create final path of the A* algorithm.
  * The path is from goal to start.
  */
 // function reconstruct_path(came_from,current)
 private List<AStarCell> reconstructPath( AStarCell current) {
  
  List<AStarCell> totalPath = new ArrayList<>(200); // arbitrary value, we'll most likely have more than 10 which is default for java
  
  // total_path := [current]
  totalPath.add( current);
    
     // while current in came_from:
        // current := came_from[current]
  while( (current = current.cameFrom) != null) {

      // total_path.append(current)
   totalPath.add( current);
         
  }
         
     // return total_path
  return totalPath;
 }
 
 /**
  * Distance between a given cell and its neighbor.
  * Used in the algorithm as distance calculation between the current cell and a neighbor. 
  * In our case we use the same distance which we use from the current cell to the goal.
  */
 private double distBetween(AStarCell current, AStarCell neighbor) {
  return heuristicCostEstimate( current, neighbor);
 }
 
 /**
  * Distance between two cells. We use the euclidian distance here. 
  * Used in the algorithm as distance calculation between a cell and the goal. 
  */
 private double heuristicCostEstimate(AStarCell from, AStarCell to) {
  
  return Math.sqrt((from.col-to.col)*(from.col-to.col) + (from.row - to.row)*(from.row-to.row));
  
 }
 
}

Since that was very easy, I got some spare time left to implement a GUI around it. Among other featuers the GUI allows you to

  • click/drag primary mouse button to create obstacles 
  • click/drag secondary mouse button to remove obstacles 

Path finding is started once you release the mouse button In order to help you understand the algorithm better I added the values which we store in the cells.

  • g = top/left value 
  • h = top/right value 
  • f = g + h = center value 

 The colorization of the cells is as follows:

  • path = blue 
  • obstacle = black 
  • cells of closed set = green 
  • cells of open set = red 

You can use the step slider in order to show the calculations step by step.

A screenshot:



And here's a video of how it looks like in action:



Interested ones can get the AStarFX code on github. If you'd like to have other grid dimensions, simply modify the file Settings.java.

It will be nice to see this algorithm work in our tower defense game.

Have fun and keep on coding :-)

4 comments:

  1. i would like to use this as a part in my project but i dont have idea how to correct which arise may i get the coding as source file where i could open as project and exectute it sir

    ReplyDelete
  2. Just click the "AStarFX code on github" link and on the github page click the "Download ZIP" button. Then create a new JavaFX project and copy the files from the ZIP into the src folder. Start the app by executing the Main.java class.

    ReplyDelete
  3. Hi RolandC,

    I have tried to add a transition animation to your application. The animation follows the path. The only problem is the ui/gui becomes unresponsive. I am clueless as to how to solve this?

    ReplyDelete
    Replies
    1. Without your code nobody can say where your problem is. I suggest you create a MCVE (Minimal Complete Verifiable Example) and post a question on StackOverflow.

      Delete