Path finding using A Star Algorithm: Java Example

With the A Star search algorithm it is possible to find the shortest path from one point to another on a map (while respecting fields that may not be walkable or that may slow down the movement). If your goal is not to find the path to one concrete point but to find the closed point that fulfills some condition, you should use Dijkstra’s algorithm instead.

I will not describe the A*-algorithm in depth on my page as it is already done quite well here:
Description of A Star
or you can go to the A Star Wikipedia for a short overview.

My Java implementation of the A Star Algorith works on a square map. It is reasonably fast, but it is more a proof of concept than an implementation that should be used anywhere where performance really matters. A simple example case is added as well.

And here you can find the Java source code for my example implementation of the a star algorithm:
a star java example code [6.74 kB]

To give you an idea what the code is like, here is the important method:

/**
* The main A Star Algorithm in Java.
*
* finds an allowed path from start to goal coordinates on this map.
* 
* This method uses the A Star algorithm. The hCosts value is calculated in
* the given Node implementation.
* 
* This method will return a LinkedList containing the start node at the
* beginning followed by the calculated shortest allowed path ending
* with the end node.
* 
* If no allowed path exists, an empty list will be returned.
* 
* 
* x/y must be bigger or equal to 0 and smaller or equal to width/hight.
*
* @param oldX x where the path starts
* @param oldY y where the path starts
* @param newX x where the path ends
* @param newY y where the path ends
* @return the path as calculated by the A Star algorithm
*/
public final List<T> findPath(int oldX, int oldY, int newX, int newY) {
openList = new LinkedList<T>();
closedList = new LinkedList<T>();
openList.add(nodes[oldX][oldY]); // add starting node to open list

done = false;
T current;
while (!done) {
current = lowestFInOpen(); // get node with lowest fCosts from openList
closedList.add(current); // add current node to closed list
openList.remove(current); // delete current node from open list

if ((current.getxPosition() == newX)
&& (current.getyPosition() == newY)) { // found goal
return calcPath(nodes[oldX][oldY], current);
}

// for all adjacent nodes:
List<T> adjacentNodes = getAdjacent(current);
for (int i = 0; i < adjacentNodes.size(); i++) {
T currentAdj = adjacentNodes.get(i);
if (!openList.contains(currentAdj)) { // node is not in openList
currentAdj.setPrevious(current); // set current node as previous for this node
currentAdj.sethCosts(nodes[newX][newY]); // set h costs of this node (estimated costs to goal)
currentAdj.setgCosts(current); // set g costs of this node (costs from start to this node)
openList.add(currentAdj); // add node to openList
} else { // node is in openList
if (currentAdj.getgCosts() > currentAdj.calculategCosts(current)) { // costs from current node are cheaper than previous costs
currentAdj.setPrevious(current); // set current node as previous for this node
currentAdj.setgCosts(current); // set g costs of this node (costs from start to this node)
}
}
}

if (openList.isEmpty()) { // no path exists
return new LinkedList<T>(); // return empty list
}
}
return null; // unreachable
}