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 Nodepublic 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 Algorithmpublic 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.
Let's (path) find A Star
java;algorithm;game;pathfinding
PriorityQueueFor 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.HashSetSimilarly, 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. ExampleIf 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).