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)); priorityQueue.add(startNode); MapNode current = null; while (!priorityQueue.isEmpty()) { current = priorityQueue.remove(); if (!visited.contains(current) ){ visited.add(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 priorityQueue.add(neighbor); } } } } } 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.

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

LikeLiked by 1 person

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.

LikeLike

Dear Muhammad,

you can simply pass coordinates of your “cells” or “agents” as method parameters of the aStarSearch method.

GeographicPoint class is a simple wrapper for the latitude and longitude of the nodes. In your case this could be grid positions.

I hope this is helpful to you.

Regards,

Dzenan

LikeLike