A* Search

* This algorithm is widely used in pathfinding and graph traversal.
* It can also be used to solve pathfinding problems in games.
* However, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance ( Dijkstra or BFS ).
* It is like Dijkstra: A* achieves better time performance by using heuristics.
* It uses a knowledge-plus-heuristic cost function of node x (usually denoted f(x) ) to determine the order in which the search visits nodes in the tree.
* The cost function is a sum of two functions:.
1. g(x) the known distance from the starting node to the current node x.
2. h(x) "heuristic estimate" of the distance from x to the goal.

* Note: if h(x)=0 -> that is the common shortest path problem.
* It is like the classic Dijkstra method, but here we make decisions according to the f(x)=g(x)+h(x) function.
* Why is it good?.
* If there are obstacles in the way between us and the final destination, A* helps to find the best path possible.
* If we decide to use Greedy Best First Search, it may lead us to dead-ends instead!.

* We use the Manhattan distance to track the distance between current position and the goal and NOT the Euclidean distance.

Codes of the Java files included in the program are given below:

Node.java

package astarsearch;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author ANIRUDDHA
 */

// Class Node for the A* Search
public class Node implements Comparable<Node>{ //Comparable : To compare the fScores between two nodes so as to make a decision

    private String value;
    private double gScore; // Calculates the actual distance from the start node to the current node
    private double hScore; // Calculates the heuristic distance from the goal node to the current node
    private double fScore;
    private double x;
    private double y;
    private List<Edge> adjacenciesList; //List of all adjacent neighbours
    private Node parentNode; //Predecessor Node
    
	//Constructor
    public Node(String value){
        this.value = value;
        this.adjacenciesList = new ArrayList<Edge>();
    }
    
    public void addNeighbour(Edge edge){
        this.adjacenciesList.add(edge);
    }
    
	//Getters and Setters
    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    public double getgScore() {
        return gScore;
    }

    public void setgScore(double gScore) {
        this.gScore = gScore;
    }

    public double gethScore() {
        return hScore;
    }

    public void sethScore(double hScore) {
        this.hScore = hScore;
    }

    public double getfScore() {
        return fScore;
    }

    public void setfScore(double fScore) {
        this.fScore = fScore;
    }

    public double getX() {
        return x;
    }

    public void setX(double x) {
        this.x = x;
    }

    public double getY() {
        return y;
    }

    public void setY(double y) {
        this.y = y;
    }

    public List<Edge> getAdjacenciesList() {
        return adjacenciesList;
    }

    public Node getParentNode() {
        return parentNode;
    }

    public void setParentNode(Node parentNode) {
        this.parentNode = parentNode;
    }
 
        
    public String toString(){
        return this.value;
    }

    // Comparing the fscores of two nodes to make a decision for the path
    @Override
    public int compareTo(Node otherNode) {
        return Double.compare(this.fScore, otherNode.getfScore());
    }


}

Edge.java

package astarsearch;

import java.util.ArrayList;

/**
 *
 * @author ANIRUDDHA
 */

public class Edge {

    private double cost;
    private Node targetNode;
    
	//Constructor
    public Edge(Node targetNode, double cost){
        this.cost = cost;
        this.targetNode = targetNode;
    }

	//Getters and Setters
    public double getCost() {
        return cost;
    }

    public void setCost(double cost) {
        this.cost = cost;
    }

    public Node getTargetNode() {
        return targetNode;
    }

    public void setTargetNode(Node targetNode) {
        this.targetNode = targetNode;
    }
    
}

AStarSearch.java

package astarsearch;

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

/**
 *
 * @author ANIRUDDHA
 */
public class AStarSearch {
    
        // We store the explored nodes in a Set Data Structure
        Set<Node> exploredNodes = new HashSet<>();
        
    public void aStarSearchAlgo(Node sourceNode, Node goalNode){
        
        // We use a PriorityQueue to implement A* Search
        // We keep adding nodes and its neighbours to the unexploredNodesQueue
        // We use the PriorityQueue along with the heap to find the minimum element in a time complexity of O(1) + O(log(N)) = O(log(N)) 
        PriorityQueue<Node> unexploredNodesQueue = new PriorityQueue<>();
        sourceNode.setgScore(0); //gScore is same as the min distance
        unexploredNodesQueue.add(sourceNode);
        boolean isFound = false;
        
        // Loop until goalNode is Found or the PriorityQueue is empty
        while(!unexploredNodesQueue.isEmpty() && !isFound){
            
            Node currentNode = unexploredNodesQueue.poll();
            exploredNodes.add(currentNode);
            
            //If goalNode is found
            if(currentNode.getValue().equals(goalNode.getValue())){
                isFound = true;
            }
            
            //Iterate through the edges
            //Visit all neighbours and add them to visited.
            for(Edge e: currentNode.getAdjacenciesList()){
                Node childNode = e.getTargetNode();
                double cost = e.getCost(); // cost of the edge
                double tempGScore = currentNode.getfScore() + cost;
                //A*Search f(x) = g(x) + h(x)
                double tempFScore = tempGScore + heuristic(childNode,goalNode); // Here the manhattan distance is used to calculate the tempFScore
                
                //Check is there is any better node
                if (exploredNodes.contains(childNode) && tempFScore >= childNode.getfScore()){
                    continue;
                }
                else if(!exploredNodes.contains(childNode) || tempFScore <= childNode.getfScore()){
                    childNode.setParentNode(currentNode);
                    childNode.setgScore(tempGScore);
                    childNode.setfScore(tempFScore);
                    
                    if(unexploredNodesQueue.contains(childNode)){
                        unexploredNodesQueue.remove(childNode);
                    }
                    
                    unexploredNodesQueue.add(childNode);
                }
            }
        }
    }
    
    public List<Node> printPath(Node targetNode){
        
        List<Node> pathList = new ArrayList<>();
        // Backtrack to the starting node
        for(Node node = targetNode; node!=null; node = node.getParentNode()){
            pathList.add(node);
        }
        
        Collections.reverse(pathList);
        
        return pathList;
       
    }

    // Manhattan heuristic function to calculated the estimated distance from goal node to current node
    private double heuristic(Node node1, Node node2) {
        return Math.abs(node1.getX() - node2.getX()) + Math.abs(node1.getY()- node2.getY());
    }
}

Main.java

package astarsearch;

import java.util.List;

/**
 *
 * @author ANIRUDDHA
 */
public class Main {

    public static void main(String[] args) {
     
        // Create nodes
        Node node1 = new Node("A");
        Node node2 = new Node("B");
        Node node3 = new Node("C");
        Node node4 = new Node("D");
        
        //Add neighbours to nodes
        node1.addNeighbour(new Edge(node2, 10)); 
        //node1.addNeighbour(new Edge(node4, 10)); // This gives path [A,D] as the route is very cheap. 
        node1.addNeighbour(new Edge(node4, 100)); // Whereas this gives [A,B,C,D] due to the added cost.
        node2.addNeighbour(new Edge(node3, 10));
        node3.addNeighbour(new Edge(node4, 10));
        
        AStarSearch as = new AStarSearch();
        as.aStarSearchAlgo(node1, node4);
        
        // Print out the path
        List<Node> path = as.printPath(node4);
        System.out.println(path);
        
    }
}

Output of the program is :

[A, B, C, D]

You can download the complete source code here : Source Code

---