There are a thousand implementations of A* in Java. This one is mine.EDIT: If you're drawing your maps left to right, top to bottom, you're best off storing your maps as [y][x] to avoid cache misses and to improve data locality. The code below assumes [x][y] because I wrote it for someone else.`import java.awt.Point; import java.util.ArrayList;
public class AStar {
public static Point[] findPath(double[][] map, Point start, Point finish) {
// These are for running A*.
Point current = null;
ArrayList
// This may have problems when reversing, but we can safely do so because we have the start point as an argument.
parent[start.x][start.y] = start;
cost[start.x][start.y] = 0;
costToGoal[start.x][start.y] = heuristic(map, start.x, start.y, finish.x, finish.y);
candidates.add(start);
while(!candidates.isEmpty()) {
// Do an O(n) search for the smallest candidate. In a densely connected graph, a minheap may drive the cost to O(n^2 log n).
// Since this isn't really densely connected, we could switch for a performance boost.
Point minCostCandidate = null;
double minCost = Float.POSITIVE_INFINITY;
for(Point p : candidates) {
if(cost[p.x][p.y] + costToGoal[p.x][p.y] < minCost) {
minCostCandidate = p;
minCost = cost[p.x][p.y] + costToGoal[p.x][p.y];
}
}
candidates.remove(minCostCandidate);
current = minCostCandidate;
if(current.equals(finish)) {
break;
}
// We've got the shortest path so far. Now let's figure out the cost of the eight items around this candidate.
// If a neighbor has a _higher cost, make this node the parent and decrease the cost.
for(int dy=-1; dy<2; dy++) {
for(int dx=-1; dx<2; dx++) {
// Short-hand for our neighbor's location.
int nbrx = current.x+dx;
int nbry = current.y+dy;
// Make sure it's a valid spot on the map.
if(dx==0 && dy==0) { continue; } // Skip the current point. Can't be your own parent.
if(!isInsideMap(map, nbrx, nbry)) { continue; } // Don't plot outside the map.
// Distance from the start to here plus the distance from here to the neighbor.
double distToNeighbor = cost[current.x][current.y] + distanceSquared(map, current.x, current.y, nbrx, nbry);
// If we have a faster way to get here, update it!
if(distToNeighbor < cost[nbrx][nbry]) {
cost[nbrx][nbry] = distToNeighbor;
costToGoal[nbrx][nbry] = heuristic(map, nbrx, nbry, finish.x, finish.y);
parent[nbrx][nbry] = current;
candidates.add(new Point(nbrx, nbry));
}
}
}
}
if(!current.equals(finish)) {
return null; // No path to goal.
}
ArrayList
And some helpful main to produce pretty outputs: public static void main(String[] args) {
final int XSIZE = 40;
final int YSIZE = 40;
// Run this to test.
double[][] map = new double[XSIZE][YSIZE];
Random rand = new Random();
for(int i=0; i < XSIZE; i++) {
for(int j=0; j < YSIZE; j++) {
map[i][j] = rand.nextInt(2);
}
}
Point start = new Point(rand.nextInt(XSIZE), rand.nextInt(YSIZE));
Point end = new Point(rand.nextInt(XSIZE), rand.nextInt(YSIZE));
Point[] path = findPath(map, start, end);
// Draw the map
char[][] output = new char[XSIZE][YSIZE];
for(int i=0; i < XSIZE; i++) {
for(int j=0; j < YSIZE; j++) {
if(map[i][j] != 0) {
output[i][j] = '#';
} else {
output[i][j] = ' ';
}
}
}
// Draw the path on the map.
if(path != null) {
for(Point p : path) {
output[p.x][p.y] = '.';
}
}
// Draw the start and end.
output[start.x][start.y] = 'S';
output[end.x][end.y] = 'E';
// Print everything.
for(int j=0; j < YSIZE; j++) {
for(int i=0; i < XSIZE; i++) {
System.out.print(output[i][j]);
}
System.out.println();
}
}
`And some selected sample output.
# # #### # ### # # ## # #
### #E.### ## ## ## # #######
# # # # #.... ## # # ## ## # # #
##### # # ###.## # ## ## ### # ## #
## ## #### ## #.# # ## ## # # ###### #
## ### # ## ##.# # ## ### # # #
#### # ### # #.# ###### ## # ###### #
# ## ## ### .########## # ## #
## # # ## . # ##### # # # #####
### # ### ## . # ## ####
# ## # #### # .## ### ## #####
## ## # # # ####S # # # # ### #
# # # # # # ## # ## # ####### ##
# ##### # # # # #. ## ###..# #
## ## ## ##........... .......... #E# #
###### #. ## # ## # ## ## # ##
# ## ##.## ## # # # ### #### ##
## # #. # # ## # # ### #
#### ##.### ##### ### # #### # ###
# # ##. # #### # ### # # ##
#### S# # #### # ### # ## ###
## # ## # # # ## # ##### ## ###
# ## ## # # # # ## ## ### # ##