# A Star (A*) Algorithm Implementation in Java

A* algorithm can be seen as an heuristic extension of Dijkstra’s. Whereas in the Dijkstra’s priority-queue ordering is based only on the distance from the start node to the current, A* algorithm additionally calculates the distance from the current node to the goal-node. Thus the ordering in the priority queue is different and the algorithm calculates more “straightforward” towards the end node in a graph and hence is significantly faster in finding the path than the Dijkstra. For detailed explanation how A* works check this link out. You can also find Dijkstra’s java implementation here.

‘Nuff said. Here’s the source…

```
/** Find the path from start to goal using A-Star search
*
* @param start The starting location
* @param goal The goal location
* @return The list of intersections that form the shortest path from
*   start to goal (including both start and goal).
*/
public List<GeographicPoint> aStarSearch(GeographicPoint start,
GeographicPoint goal)
{

MapNode startNode = pointNodeMap.get(start);
MapNode endNode = pointNodeMap.get(goal);

// setup for A*
HashMap<MapNode,MapNode> parentMap = new HashMap<MapNode,MapNode>();
HashSet<MapNode> visited = new HashSet<MapNode>();
Map<MapNode, Double> distances = initializeAllToInfinity();

Queue<MapNode> priorityQueue = initQueue();

//  enque StartNode, with distance 0
startNode.setDistanceToStart(new Double(0));
distances.put(startNode, new Double(0));
MapNode current = null;

while (!priorityQueue.isEmpty()) {
current = priorityQueue.remove();

if (!visited.contains(current) ){
// if last element in PQ reached
if (current.equals(endNode)) return reconstructPath(parentMap, startNode, endNode, 0);

Set<MapNode> neighbors = getNeighbors(current);
for (MapNode neighbor : neighbors) {
if (!visited.contains(neighbor) ){

// calculate predicted distance to the end node
double predictedDistance = neighbor.getLocation().distance(endNode.getLocation());

// 1. calculate distance to neighbor. 2. calculate dist from start node
double neighborDistance = current.calculateDistance(neighbor);
double totalDistance = current.getDistanceToStart() + neighborDistance + predictedDistance;

// check if distance smaller
if(totalDistance < distances.get(neighbor) ){
// update n's distance
distances.put(neighbor, totalDistance);
// used for PriorityQueue
neighbor.setDistanceToStart(totalDistance);
neighbor.setPredictedDistance(predictedDistance);
// set parent
parentMap.put(neighbor, current);
// enqueue
}
}
}
}
}
return null;
}

```

Basically, the only difference to Dijkstra’s algorithm are the following few lines, where distance to the end node is added to the total distance:

```// calculate predicted distance to the end node
double predictedDistance = neighbor.getLocation().distance(endNode.getLocation());

// 1. calculate distance to neighbor. 2. calculate total distance from start and to the end node
double neighborDistance = current.calculateDistance(neighbor);
double totalDistance = current.getDistanceToStart() + neighborDistance + predictedDistance;
```

Additional methods for path reconstruction and priority-queue initialization can be found here.

Enjoy the source and have fun.

1. […] the missing parts check my previous blog posts. A Star Algorithm Java Implementation Dijskstra’s Algorithm Java […]

Liked by 1 person

2. Hello respected, I have an implementation of Cellular Automata(CA) in GVG-LG. I want to implement this A* code inside my CA. Please help me out. How can i embed this inside my code. Thanks in anticipation.

Like

1. 