A* Algorithm Implementation in Java

 import java.util.*;

class Node {

    int x;

    int y;

    int gCost; // cost from start node

    int hCost; // heuristic cost to target node

    int fCost; // total cost (gCost + hCost)

    Node parent;

    public Node(int x, int y) {

        this.x = x;

        this.y = y;

    }

}

class AStarAlgorithm {

    private int[][] grid;

    private int numRows;

    private int numCols;

    private Node startNode;

    private Node targetNode;

    public AStarAlgorithm(int[][] grid) {

        this.grid = grid;

        this.numRows = grid.length;

        this.numCols = grid[0].length;

    }

    public List<Node> findPath(Node start, Node target) {

        this.startNode = start;

        this.targetNode = target;

        PriorityQueue<Node> openSet = new PriorityQueue<>(Comparator.comparingInt(node -> node.fCost));

        Set<Node> closedSet = new HashSet<>();

        openSet.add(startNode);

        while (!openSet.isEmpty()) {

            Node currentNode = openSet.poll();

            if (currentNode == targetNode) {

                return reconstructPath(currentNode);

            }

            closedSet.add(currentNode);

            List<Node> neighbors = getNeighbors(currentNode);

            for (Node neighbor : neighbors) {

                if (closedSet.contains(neighbor))

                    continue;

                int newGCost = currentNode.gCost + calculateDistance(currentNode, neighbor);

                if (newGCost < neighbor.gCost || !openSet.contains(neighbor)) {

                    neighbor.gCost = newGCost;

                    neighbor.hCost = calculateDistance(neighbor, targetNode);

                    neighbor.fCost = neighbor.gCost + neighbor.hCost;

                    neighbor.parent = currentNode;

                    if (!openSet.contains(neighbor)) {

                        openSet.add(neighbor);

                    }

                }

            }

        }

        return new ArrayList<>(); // no path found

    }

    private List<Node> getNeighbors(Node node) {

        List<Node> neighbors = new ArrayList<>();

        int[] dx = { -1, 1, 0, 0 }; // x-axis directions (up, down, left, right)

        int[] dy = { 0, 0, -1, 1 }; // y-axis directions (up, down, left, right)

        for (int i = 0; i < 4; i++) {

            int newX = node.x + dx[i];

            int newY = node.y + dy[i];

            if (newX >= 0 && newX < numRows && newY >= 0 && newY < numCols && grid[newX][newY] == 0) {

                Node neighbor = new Node(newX, newY);

                neighbors.add(neighbor);

            }

        }

        return neighbors;

    }

    private int calculateDistance(Node node1, Node node2) {

        int dx = Math.abs(node1.x - node2.x);

        int dy = Math.abs(node1.y - node2.y);

        return dx + dy;

    }

    private List<Node> reconstructPath(Node currentNode) {

        List<Node> path = new ArrayList<>();

        Node node = currentNode;

        while (node != null) {

            path.add(node);

            node = node.parent;

        }

        Collections.reverse(path);

        return path;

    }

}

public class Main {