Let's (path) find A Star

Question

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.

Answer 1

PriorityQueue

For openList, you could use a PriorityQueue instead of an ArrayList for better performance. With the ArrayList, every time you insert new elements, you need to sort the whole list, taking \$O(n\log n)\$ time. With the PriorityQueue, inserting a new element should only take \$O(\log n)\$ time. If you need to change an existing element, you should remove, modify, and reinsert the element to make sure that the element is correctly updated in the PriorityQueue.

HashSet

Similarly, for closedList, you could use a HashSet instead of an ArrayList. Your two operations on closedList are add() and contains(). With an ArrayList, contains() takes \$O(n)\$ time, but with a HashSet, contains() takes \$O(1)\$ time.

Example

If you want an example of how to use the PriorityQueue and HashSet, you could look at this other code review question. Be aware, that example did not update the PriorityQueue correctly, as it needed to remove and reinsert the node (see @mzivi's answer to that question).

Answer 2

Let's look at the data structures you're using and what you're using them for.

    List<AStarNode> closedList = new ArrayList<AStarNode>();
    closedList.add(currentNode)
    closedList.contains(adjNode)

closedList needs to be a collection that you can add items to and that you need to check for membership. Since you don't care about order or distinguishing between duplicates, the best abstract data set is a set, not a list. Looking at the list of Java's built-in set implementations, HashSet, LinkedHashSet, and TreeSet seem like good candidates. Since you don't care about order, HashSet is the best available set implementation.

List<AStarNode> openList = new ArrayList<AStarNode>();
openList.add(currentNode);
Collections.sort(openList, this.fComparator);
currentNode = openList.get(0);
openList.remove(currentNode);
(!openList.contains(adjNode))
openList.add(adjNode);

For openList, you need a data structure that can support adding items, checking membership, reading the 0th item, and removing the 0th item. You don't need to read or remove any item other than the 0th. The sort isn't necessary here. Using a list, you could get the minimum item (which would be at index 0 if you maintained a sorted list, costing O(1) read time but O(n) write time; or at a random index if you maintained an unsorted list, costing O(n) read time but O(1) write time). A priority queue is perfect for this--it's designed to access the minimum (or maximum, but not both) element in a set. You could implement a priority queue using an array or a linked list, but both have the problems described above. Instead, using a binary heap gives faster read and write time. Binary heaps are used in HeapSort, with log(n) insertion time and log(n) removal time.

I found Red Blob Games (written by @amitp) to be a good graph traversal resource. Includes pseudocode, interactive visualization (your plots show me that your algorithm found an optimal path, so you probably have an admissible heuristic, but you didn't show me plots of your search space, so you could accomplish the same thing with BFS). In particular, you should read this part where the author compares data structures for your queue (in particular, a priority queue).

The Wikipedia page on priority queues makes a very good distinction: a priority queue, stack, queue, list, and map are all abstract data types. This is distinct from the underlying data structure, that determines the cost of retrieval, insertion, and replacement.