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));
		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.

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

    Liked by 1 person

    Reply

  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

    Reply

    1. 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

      Like

      Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: