Let's (path) find A Star

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 nodes = new HashMap();

@SuppressWarnings("rawtypes"

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).

StackExchange Code Review Q#100716, answer score: 11