Yesterday I found myself struggling with creating an A * algorithm in Java, but this morning I finally figured it out, so I would love to hear what Code Review has to say about it!
The goal here is not performance since it was a learning exercise. I tried to make the code and algorithm as readable and simple as possible. My understanding is that using BinaryHeap
in some fashion can improve the speed of the algorithm quite a bit. However, I don't know how to implement this, and my intended usage at this time is for map generation, so the speed is not especially critical.
For this implementation I do not need to consider diagonals. I haven't implemented it yet, but the next step will be to use the type of terrain of each tile on the map in order to affect the movement cost of the heuristic, so instead of a list of walls, the entire map data will be passed into the object.
Here is some proof that the algorithm is working:
The Node
public class AStarNode {
public final MapPoint point;
public AStarNode parent;
public int gValue; //points from start
public int hValue; //distance from target
public boolean isWall = false;
private final int MOVEMENT_COST = 10;
public AStarNode(MapPoint point) {
this.point = point;
}
/**
* Used for setting the starting node value to 0
*/
public void setGValue(int amount) {
this.gValue = amount;
}
public void calculateHValue(AStarNode destPoint) {
this.hValue = (Math.abs(point.x - destPoint.point.x) + Math.abs(point.y - destPoint.point.y)) * this.MOVEMENT_COST;
}
public void calculateGValue(AStarNode point) {
this.gValue = point.gValue + this.MOVEMENT_COST;
}
public int getFValue() {
return this.gValue + this.hValue;
}
}
The Algorithm
public class BZAstar {
private final int width;
private final int height;
private final Map<MapPoint, AStarNode> nodes = new HashMap<MapPoint, AStarNode>();
@SuppressWarnings("rawtypes")
private final Comparator fComparator = new Comparator<AStarNode>() {
public int compare(AStarNode a, AStarNode b) {
return Integer.compare(a.getFValue(), b.getFValue()); //ascending to get the lowest
}
};
public BZAstar(int width, int height, List<MapPoint> wallPositions) {
this.width = width;
this.height = height;
for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
MapPoint point = new MapPoint(x, y);
this.nodes.put(point, new AStarNode(point));
}
}
for (MapPoint point : wallPositions) {
AStarNode node = this.nodes.get(point);
node.isWall = true;
}
}
@SuppressWarnings("unchecked")
public ArrayList<MapPoint> calculateAStarNoTerrain(MapPoint p1, MapPoint p2) {
List<AStarNode> openList = new ArrayList<AStarNode>();
List<AStarNode> closedList = new ArrayList<AStarNode>();
AStarNode destNode = this.nodes.get(p2);
AStarNode currentNode = this.nodes.get(p1);
currentNode.parent = null;
currentNode.setGValue(0);
openList.add(currentNode);
while(!openList.isEmpty()) {
Collections.sort(openList, this.fComparator);
currentNode = openList.get(0);
if (currentNode.point.equals(destNode.point)) {
return this.calculatePath(destNode);
}
openList.remove(currentNode);
closedList.add(currentNode);
for (MapDirection direction : MapDirection.values()) {
MapPoint adjPoint = direction.getPointForDirection(currentNode.point);
if (!this.isInsideBounds(adjPoint)) {
continue;
}
AStarNode adjNode = this.nodes.get(adjPoint);
if (adjNode.isWall) {
continue;
}
if (!closedList.contains(adjNode)) {
if (!openList.contains(adjNode)) {
adjNode.parent = currentNode;
adjNode.calculateGValue(currentNode);
adjNode.calculateHValue(destNode);
openList.add(adjNode);
} else {
if (adjNode.gValue < currentNode.gValue) {
adjNode.calculateGValue(currentNode);
currentNode = adjNode;
}
}
}
}
}
return null;
}
private ArrayList<MapPoint> calculatePath(AStarNode destinationNode) {
ArrayList<MapPoint> path = new ArrayList<MapPoint>();
AStarNode node = destinationNode;
while (node.parent != null) {
path.add(node.point);
node = node.parent;
}
return path;
}
private boolean isInsideBounds(MapPoint point) {
return point.x >= 0 &&
point.x < this.width &&
point.y >= 0 &&
point.y < this.height;
}
}
MapPoint
is a simple point class with X and Y as integer values. I have overridden the equals
and hashCode()
methods so that two map points will be equal if they have the same X and Y values, even if they are not actually the same object.
MapDirection
is pretty simple as well. For each direction, getPointForDirection(point)
will return the delta of the input point and the direction X and Y values. Let me know if I need to post this class as well for you to review the code.