A* Algorithm in Java: Learn with Practical Examples

A* (pronounced “A-star”) is one of the most influential and widely used pathfinding algorithms in computer science. Whenever a system needs to find the shortest route between two points — whether in a video game, a GPS navigation system, or a robot’s environment — it faces a fundamental challenge: how to find the best path without wasting time exploring countless unnecessary alternatives.

Developed in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael, A* solves this problem by combining two key pieces of information: the cost of the path traveled so far and a heuristic estimate of the remaining distance to the goal. By balancing these factors, the algorithm focuses its search on the most promising routes instead of examining every possible option. The result is a method that is both efficient and reliable, capable of finding optimal paths while significantly reducing the amount of work required.

This balance between accuracy and performance has made A* a cornerstone of pathfinding and graph traversal for more than five decades. It is used extensively in game AI, robotics, GPS navigation, autonomous systems, puzzle solving, and many other applications where intelligent route planning is essential. Its elegant combination of graph search and heuristics has also secured its place as one of the most widely taught algorithms in computer science.

In this article, we’ll break down how A* works, implement it step by step in Java, and explore practical examples that demonstrate why it remains one of the most important pathfinding algorithms ever created.

What Is the A* Algorithm? 🔍

A* is a shortest-path search algorithm that finds the optimal route between a starting node and a target node by combining: the actual known path cost, and an estimated remaining distance to the goal. The algorithm continuously selects the path that currently appears most promising according to its estimated total cost. Here is the core idea:

1. Choose a starting node
2. Assign a cost of 0 to the start node
3. Estimate the remaining distance to the target using a heuristic
4. Select the node with the smallest estimated total cost
5. Explore neighboring nodes
6. Update path costs if a shorter route is discovered
7. Repeat until the target node is reached

Animation of A algorithm. CountingPine, CC0, via Wikimedia Commons*

A useful way to visualize A is to imagine a traveler navigating toward a destination while constantly asking: “Which path currently looks cheapest overall?”*

Understanding the Heuristic Function 🧠

The heuristic function is the core component that gives A its intelligence and efficiency. It estimates the remaining cost from the current node to the target node, allowing the algorithm to identify and prioritize the most promising paths to explore next. A makes decisions using two important values:

• g(n) is the actual cost required to reach a node
• h(n) is a heuristic estimate of the remaining distance to the goal

These values are combined into a single score:

The node with the lowest f(n) value is explored first. This balance between the known path cost and the estimated remaining distance is what makes A* both efficient and effective.

The quality of the heuristic has a major impact on performance. A weak heuristic causes A* to explore many unnecessary nodes, behaving similarly to Dijkstra’s algorithm. A stronger heuristic focuses the search more directly toward the goal, often reducing the number of explored nodes dramatically. Common heuristic functions include:

• Manhattan distance
• Euclidean distance
• Chebyshev distance
• Straight-line distance

As example, the Manhattan distance heuristic measures the number of horizontal and vertical steps required to reach the target. It is commonly used in grid-based environments where movement is restricted to four directions: up, down, left, and right. The formula is:

For instance, moving from (1,1) to (4,5) gives |1 - 4| + |1 - 5| = 7, which results in a total Manhattan distance of 7.

A useful way to visualize Manhattan distance is to imagine navigating city blocks in Manhattan, where movement is limited to streets and intersections rather than diagonal shortcuts through buildings.

Heuristic Admissibility

An important concept in A is heuristic admissibility. A heuristic is considered admissible if it never overestimates the true remaining cost to the goal. When an admissible heuristic is used, A guarantees the shortest possible path.

A non-admissible heuristic may produce faster searches because it prioritizes aggressive estimates, but it can sacrifice optimality by missing the true shortest path. This creates a trade-off between accuracy and performance.

In practice, the ideal heuristic strikes a balance: it guides the search efficiently while remaining admissible, allowing A* to reach the destination with minimal unnecessary exploration while still guaranteeing an optimal solution.

Choosing the Correct Heuristics

The heuristic function is what gives A its intelligence. It is essentially an informed guess about the remaining distance to the goal. It doesn’t need to be exact — but the closer it is to reality, the more efficiently A performs. The choice of heuristic has a direct impact on:

• how many nodes are explored
• how fast the search completes
• whether the path remains optimal
• overall algorithm efficiency

Different movement systems require different heuristics, depending on how entities are allowed to move. Let’s explore the most common heuristics.

Manhattan Distance Heuristic measures how far two points are when movement is restricted to horizontal and vertical steps only. It is commonly used in grid-based games, tile maps, maze solvers, and pathfinding systems with 4-direction movement. The formula is:

This heuristic works well when diagonal movement is not allowed.

public static int manhattan(int x1, int y1, int x2, int y2) {
    return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}

// As example from (1, 1) to (4,5):
// = |1 - 4| + |1 - 5|
// = 3 + 4
// = 7

Euclidean Distance Heuristic measures the straight-line geometric distance between two points. It is used when movement is not restricted to grid directions, such as continuous movement systems, robotics, physics simulations, and open-world navigation. The formula is:

public static double euclidean(int x1, int y1, int x2, int y2) {
    int dx = x2 - x1;
    int dy = y2 - y1;
    return Math.sqrt(dx * dx + dy * dy);
}

// As example, from (1,1) to (4,5):
// = √((4 - 1)^2 + (5 - 1)^2)
// = √(9 + 16)
// = √25
// = 5

Chebyshev Distance Heuristic applies when movement is allowed in all eight directions and diagonal movement has the same cost as straight movement. It is commonly used in chess-like movement systems, 8-direction grid navigation, and strategy games. The formula is:

Instead of summing distances, Chebyshev distance takes the larger coordinate difference.

public static int chebyshev(int x1, int y1, int x2, int y2) {
    return Math.max(
        Math.abs(x1 - x2),
        Math.abs(y1 - y2)
    );
}

// As example, from (1,1) to (4,5):
// = max(|1 - 4|, |1 - 5|)
// = max(3, 4)
// = 4

Straight-Line Distance Heuristic is conceptually the same as Euclidean distance but is often used in geographic or navigation systems where the idea of “as-the-crow-flies” distance is more intuitive. Typical use cases are GPS navigation, airline routing, and geographical systems. The formula is identical to Euclidean distance:

The difference is primarily conceptual rather than mathematical.

public static double straightLineDistance(
        double lat1,
        double lon1,
        double lat2,
        double lon2) {

    double dx = lat2 - lat1;
    double dy = lon2 - lon1;
    return Math.sqrt(dx * dx + dy * dy);
}

// As example, from (1,1) to (4,5):
// = sqrt((4 - 1)^2 + (5 - 1)^2)
// = sqrt(3^2 + 4^2)
// = sqrt(9 + 16)
// = sqrt(25)
// = 5.0

Limitations of A* 📉

Although A* is one of the most efficient and widely used pathfinding algorithms, it still has several limitations, especially in large or complex search spaces.

Performance Depends on the Heuristic: The effectiveness of A* is heavily influenced by the quality of its heuristic function. A strong heuristic guides the search efficiently toward the goal, while a weak heuristic may cause the algorithm to explore many unnecessary nodes, reducing performance.

High Memory Usage: A* stores explored nodes, distance information, and priority queue states throughout the search process. On very large maps or dense graphs, memory consumption can become a significant limitation.

Optimality Is Not Always Guaranteed: A* guarantees the shortest path only when the heuristic is admissible, meaning it never overestimates the true remaining cost. Overestimating heuristics may improve speed but can produce suboptimal paths.

Performance Can Decrease on Large Graphs: In very large or complicated environments, A* may still need to explore a large number of nodes, increasing computation time. Optimizations such as hierarchical pathfinding or Jump Point Search are often used to improve scalability.

Designing a Good Heuristic Can Be Difficult: Different problem domains often require different heuristics. Choosing an ineffective heuristic can significantly reduce the efficiency of the algorithm.

Not Ideal for Exhaustive Searches: A* is designed for goal-directed pathfinding. If the objective is to compute shortest paths to many nodes or analyze an entire graph, algorithms such as Dijkstra’s algorithm may be more suitable.

Despite these limitations, A* remains one of the most important pathfinding algorithms in computer science because it provides an excellent balance between efficiency, flexibility, and optimal pathfinding performance.

From Theory to Practice 🛠️

In this section, we will first examine how A* makes decisions internally and then apply these concepts to pathfinding examples using a variety of heuristics.

1. Graph Implementation — Straight-Line (Euclidean) Distance

A* can be applied to general weighted graphs, where nodes represent locations or states and edges represent connections with associated costs. This approach is commonly used in systems such as road networks, GPS navigation, and route planning, where each connection may represent a distance, travel time, or other movement cost.

Unlike grid-based pathfinding, graph structures are not limited to fixed movement directions. Instead, the algorithm explores neighboring nodes through an adjacency list, making it well suited for irregular and real-world networks.

In this implementation, the heuristic uses straight-line (Euclidean) distance to estimate how far a node is from the goal based on their coordinates. Since the nodes represent spatial positions, the direct geometric distance provides a natural approximation of the remaining path cost and helps guide the search more efficiently toward the destination.

import java.util.*;

public class Main {

    // Represents a graph node with x and y coordinates
    static class Point {
        int x, y;

        // Constructor to initialize coordinates
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    // Represents a node used in the priority queue
    static class Node {
        String name;
        int g; // Actual cost from the start node
        double f; // Estimated total cost (g + h)

        // Constructor to initialize node values
        Node(String name, int g, double f) {
            this.name = name;
            this.g = g;
            this.f = f;
        }
    }

    // Represents a connection between two graph nodes
    static class Edge {
        String to; // Destination node
        int cost; // Cost to travel to destination

        // Constructor to initialize edge
        Edge(String to, int cost) {
            this.to = to;
            this.cost = cost;
        }
    }

    // Stores coordinates for each graph node
    static Map<String, Point> coordinates = new HashMap<>();

    // Heuristic function using Euclidean distance
    static double heuristic(String node, String goal) {

        // Get coordinates of current node and goal node
        Point a = coordinates.get(node);
        Point b = coordinates.get(goal);

        // Compute straight-line distance between nodes
        return Math.sqrt(
                Math.pow(a.x - b.x, 2) +
                Math.pow(a.y - b.y, 2)
        );
    }

    // A* search algorithm
    public static int aStar(
            Map<String, List<Edge>> graph,
            String start,
            String goal
    ) {

        // Stores shortest known distance from start to each node
        Map<String, Integer> dist = new HashMap<>();

        // Priority queue ordered by lowest estimated total cost
        PriorityQueue<Node> pq =
                new PriorityQueue<>(Comparator.comparingDouble(n -> n.f));

        // Initialize all node distances as infinity
        for (String node : graph.keySet()) {
            dist.put(node, Integer.MAX_VALUE);
        }

        // Distance to the start node is 0
        dist.put(start, 0);

        // Add start node to the priority queue
        pq.offer(
                new Node(
                        start,
                        0,
                        heuristic(start, goal) // Initial heuristic estimate
                )
        );

        // Continue searching while nodes remain
        while (!pq.isEmpty()) {

            // Get node with the smallest f value
            Node curr = pq.poll();

            // If goal is reached, return total cost
            if (curr.name.equals(goal)) {
                return curr.g;
            }

            // Explore all neighboring nodes
            for (Edge edge : graph.get(curr.name)) {

                // Compute new path cost to neighbor
                int newCost = curr.g + edge.cost;

                // If a shorter path is found
                if (newCost < dist.get(edge.to)) {

                    // Update shortest known distance
                    dist.put(edge.to, newCost);

                    // Compute heuristic estimate to goal
                    double h = heuristic(edge.to, goal);

                    // Add updated node to priority queue
                    pq.offer(
                            new Node(
                                    edge.to,
                                    newCost,
                                    newCost + h // f = g + h
                            )
                    );
                }
            }
        }

        // Return -1 if goal cannot be reached
        return -1;
    }

    public static void main(String[] args) {

        // Graph represented as an adjacency list
        Map<String, List<Edge>> graph = new HashMap<>();

        // Coordinates for each node
        coordinates.put("A", new Point(0, 0));
        coordinates.put("B", new Point(2, 1));
        coordinates.put("C", new Point(3, 3));
        coordinates.put("D", new Point(5, 4));

        // Add graph edges and costs
        graph.put("A", List.of(
                new Edge("B", 2),
                new Edge("C", 5)
        ));

        graph.put("B", List.of(
                new Edge("C", 1),
                new Edge("D", 4)
        ));

        graph.put("C", List.of(
                new Edge("D", 1)
        ));

        // Node D has no outgoing edges
        graph.put("D", List.of());

        // Run A* from node A to node D
        int result = aStar(graph, "A", "D");

        // Print the minimum path cost
        System.out.println("Minimum path cost: " + result);
    }
}

// Output:
// Minimum path cost: 4

This graph-based version of A* searches through connected nodes in a weighted network while prioritizing paths that appear closer to the goal. The Euclidean distance heuristic is particularly effective in this scenario because it provides a realistic estimate of the remaining travel distance without overestimating the actual shortest path.

2. Grid Implementation — Manhattan Distance (Cardinal Movement)

A* is widely used for pathfinding on 2D grids, where each cell represents a node and movement occurs between neighboring cells. This type of structure is common in tile-based games, robotics, maze solving, and navigation systems.

In this implementation, movement is restricted to four directions: up, down, left, and right. Because diagonal movement is not allowed, the Manhattan distance heuristic is the most appropriate choice. It estimates the remaining distance by calculating the total horizontal and vertical movement required to reach the goal.

Each value in the grid represents the movement cost of entering a cell, while the heuristic helps guide the search toward the destination more efficiently.

import java.util.*;

public class Main {

    static class Node {
        int row, col;
        int g; // Cost from start to this node (actual path cost)
        int f; // Total estimated cost (g + h)

        Node(int row, int col, int g, int f) {
            this.row = row;
            this.col = col;
            this.g = g;
            this.f = f;
        }
    }

    // Heuristic function: Manhattan distance
    static int heuristic(int r, int c, int targetRow, int targetCol) {
        return Math.abs(r - targetRow) + Math.abs(c - targetCol);
    }

    public static int aStar(int[][] grid) {

        int rows = grid.length;
        int cols = grid[0].length;

        // Tracks the best known cost to reach each cell
        int[][] dist = new int[rows][cols];

        for (int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        // Possible movement directions (up, down, left, right)
        int[][] dirs = {
                {1, 0},
                {-1, 0},
                {0, 1},
                {0, -1}
        };

        // Priority queue orders nodes by lowest estimated total cost (f)
        PriorityQueue<Node> pq =
                new PriorityQueue<>(Comparator.comparingInt(n -> n.f));

        // Initialize start node (0,0)
        dist[0][0] = grid[0][0];

        int startHeuristic =
                heuristic(0, 0, rows - 1, cols - 1);

        pq.offer(
                new Node(
                        0,
                        0,
                        grid[0][0],                 // g cost
                        grid[0][0] + startHeuristic // f = g + h
                )
        );

        while (!pq.isEmpty()) {

            // Node with lowest estimated total cost
            Node curr = pq.poll();

            int r = curr.row;
            int c = curr.col;

            // If we reached the goal, return the cost
            if (r == rows - 1 && c == cols - 1) {
                return curr.g;
            }

            // Explore all 4 neighboring cells
            for (int[] d : dirs) {

                int nr = r + d[0];
                int nc = c + d[1];

                // Skip out-of-bounds neighbors
                if (nr >= 0 && nc >= 0 && nr < rows && nc < cols) {

                    // Compute new cost to reach neighbor
                    int newCost = curr.g + grid[nr][nc];

                    // Only proceed if this path is better
                    if (newCost < dist[nr][nc]) {

                        dist[nr][nc] = newCost;

                        int h = heuristic(nr, nc, rows - 1, cols - 1);

                        // Push neighbor with updated priority
                        pq.offer(
                                new Node(
                                        nr,
                                        nc,
                                        newCost,
                                        newCost + h
                                )
                        );
                    }
                }
            }
        }

        // If goal is unreachable
        return -1;
    }

    public static void main(String[] args) {

        int[][] grid = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };

        int result = aStar(grid);

        System.out.println("Minimum path cost: " + result);
    }
}

// Output:
// Minimum path cost: 7

This grid-based version of A combines the actual movement cost with a heuristic estimate to prioritize paths that are more likely to reach the goal quickly. Compared to Dijkstra’s algorithm, which explores nodes more uniformly, A uses the Manhattan distance heuristic to focus the search in the direction of the target, significantly reducing the number of explored states in many pathfinding scenarios.

3. Grid Implementation — Chebyshev Distance (Diagonal Movement)

A* is commonly used on 2D grids that support both orthogonal and diagonal movement. This type of pathfinding is widely used in tile-based games, robotics, and navigation systems that allow movement in eight directions.

Unlike the previous grid example, which restricted movement to up, down, left, and right, this implementation also allows diagonal movement between cells. Because diagonal moves can reduce both the row and column distance at the same time, the Manhattan distance heuristic is no longer the most appropriate choice.

Instead, this implementation uses the Chebyshev distance heuristic. This heuristic works well for diagonal movement because a single diagonal step can reduce both the row and column distance simultaneously, providing a more accurate estimate of the remaining path cost in eight-direction movement systems.

import java.util.*;

public class Main {

    // Represents a grid node
    static class Node {
        int row, col;
        int g; // Actual cost from start
        int f; // Estimated total cost (g + h)

        // Constructor to initialize node values
        Node(int row, int col, int g, int f) {
            this.row = row;
            this.col = col;
            this.g = g;
            this.f = f;
        }
    }

    // Chebyshev distance heuristic
    static int heuristic(int r, int c, int targetRow, int targetCol) {

        return Math.max(
                Math.abs(r - targetRow),
                Math.abs(c - targetCol)
        );
    }

    public static int aStar(int[][] grid) {

        int rows = grid.length;
        int cols = grid[0].length;

        // Stores shortest known distance to each cell
        int[][] dist = new int[rows][cols];

        for (int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        // 8 possible movement directions
        int[][] dirs = {
                {1, 0},   // down
                {-1, 0},  // up
                {0, 1},   // right
                {0, -1},  // left
                {1, 1},   // down-right
                {1, -1},  // down-left
                {-1, 1},  // up-right
                {-1, -1}  // up-left
        };

        // Priority queue ordered by lowest f value
        PriorityQueue<Node> pq =
                new PriorityQueue<>(Comparator.comparingInt(n -> n.f));

        // Initialize start position
        dist[0][0] = grid[0][0];

        int startHeuristic =
                heuristic(0, 0, rows - 1, cols - 1);

        pq.offer(
                new Node(
                        0,
                        0,
                        grid[0][0],
                        grid[0][0] + startHeuristic
                )
        );

        while (!pq.isEmpty()) {

            // Get node with smallest estimated cost
            Node curr = pq.poll();

            int r = curr.row;
            int c = curr.col;

            // Goal reached
            if (r == rows - 1 && c == cols - 1) {
                return curr.g;
            }

            // Explore all 8 neighboring cells
            for (int[] d : dirs) {

                int nr = r + d[0];
                int nc = c + d[1];

                // Skip invalid positions
                if (nr >= 0 && nc >= 0 &&
                    nr < rows && nc < cols) {

                    // Compute new path cost
                    int newCost = curr.g + grid[nr][nc];

                    // Update if shorter path found
                    if (newCost < dist[nr][nc]) {

                        dist[nr][nc] = newCost;

                        int h =
                                heuristic(
                                        nr,
                                        nc,
                                        rows - 1,
                                        cols - 1
                                );

                        // Add updated node to queue
                        pq.offer(
                                new Node(
                                        nr,
                                        nc,
                                        newCost,
                                        newCost + h
                                )
                        );
                    }
                }
            }
        }

        // Goal unreachable
        return -1;
    }

    public static void main(String[] args) {

        int[][] grid = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };

        int result = aStar(grid);

        System.out.println("Minimum path cost: " + result);
    }
}

// Output:
// Minimum path cost: 5

This implementation extends the traditional grid-based version of A* by allowing diagonal movement between cells. The Chebyshev distance heuristic is particularly effective in this scenario because it accurately reflects the minimum number of moves required when diagonal movement is available.

4. Tree Implementation — Depth-Based Heuristic

A* can also be applied to tree structures, where each node represents a state and each edge represents a decision or transition. Unlike general graphs, trees do not contain cycles, meaning each node has a single unique path from the root. This simplifies the search process because the algorithm does not need to handle repeated states or revisit previously explored nodes.

In this implementation, the heuristic is based on the estimated remaining depth to the goal. Since tree structures are naturally hierarchical, nodes that are closer in depth are often closer to the target as well. This provides a simple and effective way to guide the search without requiring more complex distance calculations.

import java.util.*;

public class Main {

    // Represents a node stored in the priority queue
    static class Node {
        TreeNode treeNode; // Reference to the tree node
        int g; // Actual cost from the root node
        int f; // Estimated total cost (g + h)

        // Constructor to initialize node values
        Node(TreeNode treeNode, int g, int f) {
            this.treeNode = treeNode;
            this.g = g;
            this.f = f;
        }
    }

    // Represents a node in the tree
    static class TreeNode {
        String name; // Node identifier

        // Estimated remaining depth to the goal
        int estimatedDepthToGoal;

        // List of child connections
        List<TreeEdge> children = new ArrayList<>();

        // Constructor to initialize tree node
        TreeNode(String name, int estimatedDepthToGoal) {
            this.name = name;
            this.estimatedDepthToGoal = estimatedDepthToGoal;
        }
    }

    // Represents a connection between tree nodes
    static class TreeEdge {
        TreeNode to; // Child node
        int cost; // Cost to move to child node

        // Constructor to initialize edge
        TreeEdge(TreeNode to, int cost) {
            this.to = to;
            this.cost = cost;
        }
    }

    // Depth-based heuristic function
    // Estimates how far the node is from the goal
    static int heuristic(TreeNode node) {
        return node.estimatedDepthToGoal;
    }

    // A* search algorithm for a tree structure
    public static int aStar(TreeNode root, String goal) {

        // Priority queue ordered by lowest estimated total cost
        PriorityQueue<Node> pq =
                new PriorityQueue<>(Comparator.comparingInt(n -> n.f));

        // Add root node to the priority queue
        pq.offer(
                new Node(
                        root,
                        0, // Initial path cost
                        heuristic(root) // Initial estimated total cost
                )
        );

        // Continue searching while nodes remain
        while (!pq.isEmpty()) {

            // Get node with the smallest f value
            Node curr = pq.poll();

            // If goal node is reached, return total path cost
            if (curr.treeNode.name.equals(goal)) {
                return curr.g;
            }

            // Explore all child nodes
            for (TreeEdge edge : curr.treeNode.children) {

                // Compute new path cost to child node
                int newCost = curr.g + edge.cost;

                // Compute heuristic estimate for child node
                int h = heuristic(edge.to);

                // Add child node to priority queue
                pq.offer(
                        new Node(
                                edge.to,
                                newCost,
                                newCost + h // f = g + h
                        )
                );
            }
        }

        // Return -1 if goal cannot be reached
        return -1;
    }

    public static void main(String[] args) {

        // Create tree nodes with estimated depth values
        TreeNode root = new TreeNode("A", 2);
        TreeNode b = new TreeNode("B", 1);
        TreeNode c = new TreeNode("C", 1);
        TreeNode d = new TreeNode("D", 0);

        // Add child connections from root
        root.children.add(new TreeEdge(b, 2));
        root.children.add(new TreeEdge(c, 3));

        // Add child connection from B to D
        b.children.add(new TreeEdge(d, 2));

        // Run A* search from root node to goal node D
        int result = aStar(root, "D");

        // Print minimum path cost
        System.out.println("Minimum path cost: " + result);
    }
}

// Output:
// Minimum path cost: 4

This tree-based version demonstrates how A can be adapted to hierarchical search problems by combining the actual path cost with an estimate of the remaining depth to the goal. While tree-based A is less common than grid or graph pathfinding, it is useful in areas such as AI decision trees, game behavior planning, and other structured search problems where states are organized hierarchically.

5. Continuous Space / Navigation Meshes — Euclidean Distance

A* can be applied to continuous spaces, where movement is not restricted to fixed grid cells or discrete graph steps. Instead, objects can move freely in any direction through an environment. This type of pathfinding is commonly used in robotics, 3D games, autonomous vehicles, and drone navigation.

Rather than using a regular grid, these systems often represent the environment using navigation meshes (NavMesh), waypoint systems, or polygon-based movement areas. In these representations, nodes typically correspond to positions or regions in continuous space, allowing more natural and realistic movement.

Because movement is unrestricted and can occur in any direction, the Euclidean distance heuristic is usually the most appropriate choice. It estimates the direct straight-line distance between the current position and the goal. This heuristic works well in continuous environments because it closely approximates the true shortest path when movement is free in all directions. Unlike Manhattan or Chebyshev distance, Euclidean distance naturally reflects real geometric movement in open spaces.

import java.util.*;

public class Main {

    // Represents a position in continuous 2D space
    static class Point {
        double x, y;

        // Constructor to initialize coordinates
        Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }

    // Represents a node used in the priority queue
    static class Node {
        String name;
        double g; // Actual cost from start
        double f; // Estimated total cost (g + h)

        // Constructor to initialize node values
        Node(String name, double g, double f) {
            this.name = name;
            this.g = g;
            this.f = f;
        }
    }

    // Represents a connection between nodes
    static class Edge {
        String to;
        double cost;

        // Constructor to initialize edge
        Edge(String to, double cost) {
            this.to = to;
            this.cost = cost;
        }
    }

    // Stores coordinates for each node
    static Map<String, Point> positions = new HashMap<>();

    // Euclidean distance heuristic
    static double heuristic(String node, String goal) {

        Point a = positions.get(node);
        Point b = positions.get(goal);

        return Math.sqrt(
                Math.pow(a.x - b.x, 2) +
                Math.pow(a.y - b.y, 2)
        );
    }

    // A* search algorithm
    public static double aStar(
            Map<String, List<Edge>> graph,
            String start,
            String goal
    ) {

        // Stores shortest known distance to each node
        Map<String, Double> dist = new HashMap<>();

        // Priority queue ordered by lowest estimated cost
        PriorityQueue<Node> pq =
                new PriorityQueue<>(Comparator.comparingDouble(n -> n.f));

        // Initialize all distances as infinity
        for (String node : graph.keySet()) {
            dist.put(node, Double.MAX_VALUE);
        }

        // Distance to start node is 0
        dist.put(start, 0.0);

        // Add start node to priority queue
        pq.offer(
                new Node(
                        start,
                        0.0,
                        heuristic(start, goal)
                )
        );

        // Continue searching while nodes remain
        while (!pq.isEmpty()) {

            // Get node with smallest estimated total cost
            Node curr = pq.poll();

            // Goal reached
            if (curr.name.equals(goal)) {
                return curr.g;
            }

            // Explore neighboring nodes
            for (Edge edge : graph.get(curr.name)) {

                // Compute new path cost
                double newCost = curr.g + edge.cost;

                // Update if shorter path found
                if (newCost < dist.get(edge.to)) {

                    dist.put(edge.to, newCost);

                    double h = heuristic(edge.to, goal);

                    // Add updated node to queue
                    pq.offer(
                            new Node(
                                    edge.to,
                                    newCost,
                                    newCost + h
                            )
                    );
                }
            }
        }

        // Goal unreachable
        return -1;
    }

    public static void main(String[] args) {

        // Graph representing movement in continuous space
        Map<String, List<Edge>> graph = new HashMap<>();

        // Positions of nodes in 2D space
        positions.put("A", new Point(0.0, 0.0));
        positions.put("B", new Point(2.5, 1.0));
        positions.put("C", new Point(4.0, 3.0));
        positions.put("D", new Point(6.0, 4.5));

        // Connections between nodes
        graph.put("A", List.of(
                new Edge("B", 2.7),
                new Edge("C", 5.0)
        ));

        graph.put("B", List.of(
                new Edge("C", 2.0),
                new Edge("D", 4.2)
        ));

        graph.put("C", List.of(
                new Edge("D", 1.8)
        ));

        graph.put("D", List.of());

        // Run A* search
        double result = aStar(graph, "A", "D");

        // Print minimum path cost
        System.out.println("Minimum path cost: " + result);
    }
}

// Output:
// Minimum path cost: 6.8

This continuous-space version of A* demonstrates how the algorithm can operate in environments where movement is not limited to fixed grid directions. By using Euclidean distance as the heuristic, the search is guided toward the goal using the direct geometric distance between positions, making it especially effective for realistic navigation and free-form movement systems.

6. A* Path Reconstruction

In many real-world systems, finding the minimum cost alone is not enough — we also need the actual sequence of steps that forms the shortest path.

To support this, A* stores a reference to each node’s parent whenever a better path is discovered. After reaching the destination, these parent pointers allow the algorithm to reconstruct the path by walking backward from the goal to the start.

import java.util.*;

public class Main {

    static class Node {

        int row, col;
        int g, f; // g = actual cost so far, f = estimated total cost

        Node(int row, int col, int g, int f) {
            this.row = row;
            this.col = col;
            this.g = g;
            this.f = f;
        }
    }

    // Manhattan distance heuristic
    static int heuristic(int r, int c, int targetRow, int targetCol) {
        return Math.abs(r - targetRow) + Math.abs(c - targetCol);
    }

    public static List<int[]> shortestPath(int[][] grid) {

        int rows = grid.length;
        int cols = grid[0].length;

        // Stores the best known cost to reach each cell
        int[][] dist = new int[rows][cols];

        for (int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        // Parent pointers used to reconstruct the final path
        int[][] parentRow = new int[rows][cols];
        int[][] parentCol = new int[rows][cols];

        // Initialize parents as "unknown"
        for (int[] row : parentRow) {
            Arrays.fill(row, -1);
        }
        for (int[] row : parentCol) {
            Arrays.fill(row, -1);
        }

        // Movement directions (4-directional grid)
        int[][] dirs = {
                {1, 0},
                {-1, 0},
                {0, 1},
                {0, -1}
        };

        // Priority queue ensures we always expand the most promising node first
        PriorityQueue<Node> pq =
                new PriorityQueue<>(Comparator.comparingInt(n -> n.f));

        // Initialize start node (top-left corner)
        dist[0][0] = grid[0][0];

        pq.offer(
                new Node(
                        0,
                        0,
                        grid[0][0], // g cost
                        grid[0][0] + heuristic(0, 0, rows - 1, cols - 1) // f = g + h
                )
        );

        while (!pq.isEmpty()) {

            Node curr = pq.poll();

            int r = curr.row;
            int c = curr.col;

            // Stop early if we reach the goal node
            if (r == rows - 1 && c == cols - 1) {
                break;
            }

            // Explore all neighboring cells
            for (int[] d : dirs) {

                int nr = r + d[0];
                int nc = c + d[1];

                // Skip invalid positions
                if (nr >= 0 && nc >= 0 && nr < rows && nc < cols) {

                    // Compute cost of reaching this neighbor through current node
                    int newCost = curr.g + grid[nr][nc];

                    // Only update if this path is better than any previous one
                    if (newCost < dist[nr][nc]) {

                        dist[nr][nc] = newCost;

                        // Record where we came from (for path reconstruction)
                        parentRow[nr][nc] = r;
                        parentCol[nr][nc] = c;

                        int h = heuristic(nr, nc, rows - 1, cols - 1);

                        // Push updated node into priority queue
                        pq.offer(
                                new Node(
                                        nr,
                                        nc,
                                        newCost,
                                        newCost + h
                                )
                        );
                    }
                }
            }
        }

        // Reconstruct path by walking backwards from destination
        List<int[]> path = new ArrayList<>();

        int r = rows - 1;
        int c = cols - 1;

        // Follow parent pointers until reaching the start (-1, -1)
        while (r != -1 && c != -1) {

            path.add(new int[]{r, c});

            int pr = parentRow[r][c];
            int pc = parentCol[r][c];

            r = pr;
            c = pc;
        }

        // Reverse because we built the path from goal → start
        Collections.reverse(path);

        return path;
    }

    public static void main(String[] args) {

        int[][] grid = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };

        List<int[]> path = shortestPath(grid);

        System.out.println("Shortest Path:");

        for (int[] cell : path) {
            System.out.println("(" + cell[0] + ", " + cell[1] + ")");
        }
    }
}

// Output:
// Shortest Path:
// (0, 0)
// (0, 1)
// (0, 2)
// (1, 2)
// (2, 2)

This extension turns A from a cost calculator into a full path reconstruction algorithm. Instead of only telling you how expensive the optimal route is, it now reveals exactly which steps to take to follow that route* — which is what most real-world systems actually need.

Practical Examples 💡

A* is widely used in real-world systems because it provides an excellent balance between optimality and efficiency. Rather than exploring every possible path, it uses a heuristic to focus the search toward the most promising routes, significantly reducing the amount of work required to reach a solution.

Although the underlying algorithm remains the same, the meaning of nodes, edges, and movement costs varies depending on the problem being solved. The following sections demonstrate some of the most common applications of A*.

1. Video Game AI

A* is one of the most widely used pathfinding algorithms in game development. It enables players, enemies, and non-player characters (NPCs) to navigate around obstacles, avoid dangerous terrain, and efficiently move toward objectives.

A typical game world is represented as a grid where walkable tiles become nodes and blocked tiles become obstacles. A* searches this grid and returns the optimal route from the starting position to the destination.

import java.util.*;

record Node(int x, int y) {}

class AStar {

    private static class PathNode {
        Node node;
        PathNode parent;
        int g; // Cost from start
        int h; // Heuristic cost to goal

        PathNode(Node node, PathNode parent, int g, int h) {
            this.node = node;
            this.parent = parent;
            this.g = g;
            this.h = h;
        }

        int f() {
            return g + h;
        }
    }

    public static List<Node> findPath(
            int[][] map,
            Node start,
            Node goal) {

        PriorityQueue<PathNode> openSet =
                new PriorityQueue<>(Comparator.comparingInt(PathNode::f));

        Map<Node, Integer> gScores = new HashMap<>();
        Set<Node> closedSet = new HashSet<>();

        openSet.add(
                new PathNode(
                        start,
                        null,
                        0,
                        heuristic(start, goal)
                )
        );

        gScores.put(start, 0);

        while (!openSet.isEmpty()) {

            PathNode current = openSet.poll();

            if (current.node.equals(goal)) {
                return reconstructPath(current);
            }

            closedSet.add(current.node);

            for (Node neighbor : getNeighbors(map, current.node)) {

                if (closedSet.contains(neighbor)) {
                    continue;
                }

                int tentativeG = current.g + 1;

                if (tentativeG < gScores.getOrDefault(neighbor, Integer.MAX_VALUE)) {

                    gScores.put(neighbor, tentativeG);

                    openSet.add(
                            new PathNode(
                                    neighbor,
                                    current,
                                    tentativeG,
                                    heuristic(neighbor, goal)
                            )
                    );
                }
            }
        }

        return Collections.emptyList();
    }

    private static int heuristic(Node a, Node b) {
        return Math.abs(a.x() - b.x())
                + Math.abs(a.y() - b.y());
    }

    private static List<Node> getNeighbors(
            int[][] map,
            Node node) {

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

        int[][] directions = {
                {0, 1},
                {1, 0},
                {0, -1},
                {-1, 0}
        };

        for (int[] dir : directions) {

            int newX = node.x() + dir[0];
            int newY = node.y() + dir[1];

            if (newX >= 0
                    && newX < map.length
                    && newY >= 0
                    && newY < map[0].length
                    && map[newX][newY] == 0) {

                neighbors.add(new Node(newX, newY));
            }
        }

        return neighbors;
    }

    private static List<Node> reconstructPath(
            PathNode goalNode) {

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

        PathNode current = goalNode;

        while (current != null) {
            path.add(current.node);
            current = current.parent;
        }

        Collections.reverse(path);

        return path;
    }
}

public class Main {

    public static void main(String[] args) {

        int[][] map = {
                {0, 0, 0, 0},
                {1, 1, 0, 1},
                {0, 0, 0, 0},
                {0, 1, 1, 0}
        };

        Node start = new Node(0, 0);
        Node goal = new Node(3, 3);

        List<Node> path = AStar.findPath(map, start, goal);

        System.out.println("NPC path:");

        for (Node node : path) {
            System.out.printf(
                    "(%d, %d)%n",
                    node.x(),
                    node.y()
            );
        }
    }
}

// NPC path:
// (0, 0)
// (1, 0)
// (2, 0)
// (2, 1)
// (2, 2)
// (2, 3)
// (3, 3)

The NPC can then follow the generated path one step at a time. In modern games, A* is frequently combined with path smoothing, navigation meshes, and path caching to improve performance.

2. Robotics

In robotics, A* is used to plan safe and efficient movement through physical environments. Unlike many game maps, movement costs are often weighted to reflect real-world constraints such as energy consumption, terrain difficulty, or risk.

For example, a warehouse robot may choose a slightly longer route if it requires less energy or avoids congested areas.

import java.util.*;

record Node(int x, int y) {}

class AStar {

    private static class PathNode {
        Node node;
        PathNode parent;
        int g; // Total terrain cost so far
        int h; // Heuristic estimate

        PathNode(Node node, PathNode parent, int g, int h) {
            this.node = node;
            this.parent = parent;
            this.g = g;
            this.h = h;
        }

        int f() {
            return g + h;
        }
    }

    public static List<Node> findLowestCostPath(
            int[][] terrain,
            Node start,
            Node goal) {

        PriorityQueue<PathNode> openSet =
                new PriorityQueue<>(Comparator.comparingInt(PathNode::f));

        Map<Node, Integer> costs = new HashMap<>();
        Set<Node> closedSet = new HashSet<>();

        openSet.add(
                new PathNode(
                        start,
                        null,
                        0,
                        heuristic(start, goal)
                )
        );

        costs.put(start, 0);

        while (!openSet.isEmpty()) {

            PathNode current = openSet.poll();

            if (current.node.equals(goal)) {
                return reconstructPath(current);
            }

            if (!closedSet.add(current.node)) {
                continue;
            }

            for (Node neighbor :
                    getNeighbors(terrain, current.node)) {

                int movementCost =
                        terrain[neighbor.x()][neighbor.y()];

                int tentativeCost =
                        current.g + movementCost;

                if (tentativeCost <
                        costs.getOrDefault(
                                neighbor,
                                Integer.MAX_VALUE)) {

                    costs.put(neighbor, tentativeCost);

                    openSet.add(
                            new PathNode(
                                    neighbor,
                                    current,
                                    tentativeCost,
                                    heuristic(
                                            neighbor,
                                            goal
                                    )
                            )
                    );
                }
            }
        }

        return Collections.emptyList();
    }

    private static int heuristic(
            Node current,
            Node goal) {

        return Math.abs(current.x() - goal.x())
                + Math.abs(current.y() - goal.y());
    }

    private static List<Node> getNeighbors(
            int[][] terrain,
            Node node) {

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

        int[][] directions = {
                {0, 1},
                {1, 0},
                {0, -1},
                {-1, 0}
        };

        for (int[] direction : directions) {

            int x = node.x() + direction[0];
            int y = node.y() + direction[1];

            if (x >= 0
                    && x < terrain.length
                    && y >= 0
                    && y < terrain[0].length) {

                neighbors.add(new Node(x, y));
            }
        }

        return neighbors;
    }

    private static List<Node> reconstructPath(
            PathNode goalNode) {

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

        PathNode current = goalNode;

        while (current != null) {
            path.add(current.node);
            current = current.parent;
        }

        Collections.reverse(path);

        return path;
    }
}

public class Main {

    public static void main(String[] args) {

        int[][] terrain = {
                {1, 1, 2, 5},
                {1, 3, 2, 1},
                {4, 2, 1, 1},
                {5, 5, 1, 1}
        };

        Node start = new Node(0, 0);
        Node goal = new Node(3, 3);

        List<Node> path =
                AStar.findLowestCostPath(
                        terrain,
                        start,
                        goal
                );

        System.out.println(
                "Energy-efficient route:"
        );

        path.forEach(System.out::println);
    }
}

// Energy-efficient route:
// Node[x=0, y=0]
// Node[x=0, y=1]
// Node[x=0, y=2]
// Node[x=1, y=2]
// Node[x=1, y=3]
// Node[x=2, y=3]
// Node[x=3, y=3]

In this example, each value represents the energy cost required to enter a location. Rather than minimizing distance alone, A* minimizes the total traversal cost.

Common applications include warehouse automation, autonomous vehicles, drones, and industrial robotics.

3. GPS Navigation Systems

GPS navigation systems use the same core principles as grid-based pathfinding, but the graph represents a road network rather than a game map. In this context:

• Nodes represent intersections.
• Edges represent roads.
• Edge costs may represent distance, travel time, fuel consumption, or traffic conditions.

A* uses the known cost of roads together with a heuristic estimate of the remaining distance to the destination. This allows navigation systems to compute routes efficiently across extremely large networks.

Conceptually, the process is identical to the game example:

import java.util.*;

record Location(
        String name,
        int x,
        int y) {
}

record Road(
        String destination,
        int distance) {
}

class RoadGraph {

    private final Map<String, Location> locations =
            new HashMap<>();

    private final Map<String, List<Road>> roads =
            new HashMap<>();

    public void addLocation(Location location) {

        locations.put(
                location.name(),
                location
        );

        roads.putIfAbsent(
                location.name(),
                new ArrayList<>()
        );
    }

    public void addRoad(
            String from,
            String to,
            int distance) {

        roads.get(from)
                .add(new Road(to, distance));

        roads.get(to)
                .add(new Road(from, distance));
    }

    public List<Road> getNeighbors(
            String location) {

        return roads.getOrDefault(
                location,
                Collections.emptyList()
        );
    }

    public Location getLocation(
            String name) {

        return locations.get(name);
    }
}

class AStar {

    private static class PathNode {

        String location;
        PathNode parent;
        int g;
        int h;

        PathNode(
                String location,
                PathNode parent,
                int g,
                int h) {

            this.location = location;
            this.parent = parent;
            this.g = g;
            this.h = h;
        }

        int f() {
            return g + h;
        }
    }

    public static List<String> findRoute(
            RoadGraph graph,
            String start,
            String goal) {

        PriorityQueue<PathNode> openSet =
                new PriorityQueue<>(
                        Comparator.comparingInt(
                                PathNode::f
                        )
                );

        Map<String, Integer> gScores =
                new HashMap<>();

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

        openSet.add(
                new PathNode(
                        start,
                        null,
                        0,
                        heuristic(
                                graph,
                                start,
                                goal
                        )
                )
        );

        gScores.put(start, 0);

        while (!openSet.isEmpty()) {

            PathNode current =
                    openSet.poll();

            if (current.location.equals(goal)) {
                return reconstructPath(
                        current
                );
            }

            if (!closedSet.add(
                    current.location)) {
                continue;
            }

            for (Road road :
                    graph.getNeighbors(
                            current.location)) {

                String neighbor =
                        road.destination();

                int tentativeG =
                        current.g
                                + road.distance();

                if (tentativeG <
                        gScores.getOrDefault(
                                neighbor,
                                Integer.MAX_VALUE)) {

                    gScores.put(
                            neighbor,
                            tentativeG
                    );

                    openSet.add(
                            new PathNode(
                                    neighbor,
                                    current,
                                    tentativeG,
                                    heuristic(
                                            graph,
                                            neighbor,
                                            goal
                                    )
                            )
                    );
                }
            }
        }

        return Collections.emptyList();
    }

    private static int heuristic(
            RoadGraph graph,
            String current,
            String goal) {

        Location currentLocation =
                graph.getLocation(current);

        Location goalLocation =
                graph.getLocation(goal);

        double dx =
                currentLocation.x()
                        - goalLocation.x();

        double dy =
                currentLocation.y()
                        - goalLocation.y();

        return (int) Math.sqrt(
                dx * dx + dy * dy
        );
    }

    private static List<String> reconstructPath(
            PathNode goalNode) {

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

        PathNode current =
                goalNode;

        while (current != null) {

            path.add(
                    current.location
            );

            current =
                    current.parent;
        }

        Collections.reverse(path);

        return path;
    }
}

public class Main {

    public static void main(String[] args) {

        RoadGraph graph =
               new RoadGraph();

        graph.addLocation(
                new Location(
                        "Home",
                        0,
                        0
                )
        );

        graph.addLocation(
                new Location(
                        "Highway",
                        4,
                        3
                )
        );

        graph.addLocation(
                new Location(
                        "Office",
                        10,
                        0
                )
        );

        graph.addRoad(
                "Home",
                "Highway",
                5
        );

        graph.addRoad(
                "Highway",
                "Office",
                10
        );

        graph.addRoad(
                "Home",
                "Office",
                20
        );

        List<String> route =
                AStar.findRoute(
                        graph,
                        "Home",
                        "Office"
                );

        System.out.println(
                "Best route: "
                        + route
        );
    }
}

// Best route: [Home, Highway, Office]

The difference lies in how the graph is constructed and how movement costs are calculated. Real navigation systems further incorporate live traffic updates, speed limits, road closures, and historical congestion data.

4. Puzzle Solving

A* is also widely used to solve state-space search problems such as the 8-puzzle, 15-puzzle, maze solving, and Sokoban.

In these problems, each node represents an entire puzzle configuration rather than a physical location. A move transforms one state into another, creating a graph of possible solutions.

The heuristic estimates how close the current state is to the goal state, allowing A* to prioritize promising configurations.

import java.util.*;

record PuzzleState(
        int[][] board,
        int moves) {
}

class AStar {

    private static class Node {

        int[][] board;
        int moves;
        int heuristic;
        Node parent;

        Node(
                int[][] board,
                int moves,
                int heuristic,
                Node parent) {

            this.board = board;
            this.moves = moves;
            this.heuristic = heuristic;
            this.parent = parent;
        }

        int f() {
            return moves + heuristic;
        }
    }

    public static PuzzleState solve(
            int[][] start,
            int[][] goal) {

        PriorityQueue<Node> openSet =
                new PriorityQueue<>(
                        Comparator.comparingInt(
                                Node::f
                        )
                );

        Set<String> visited =
                new HashSet<>();

        openSet.add(
                new Node(
                        copyBoard(start),
                        0,
                        heuristic(start, goal),
                        null
                )
        );

        while (!openSet.isEmpty()) {

            Node current =
                    openSet.poll();

            String key =
                    serialize(current.board);

            if (!visited.add(key)) {
                continue;
            }

            if (Arrays.deepEquals(
                    current.board,
                    goal)) {

                return new PuzzleState(
                        current.board,
                        current.moves
                );
            }

            for (int[][] neighbor :
                    generateNeighbors(
                            current.board)) {

                if (!visited.contains(
                        serialize(neighbor))) {

                    openSet.add(
                            new Node(
                                    neighbor,
                                    current.moves + 1,
                                    heuristic(
                                            neighbor,
                                            goal
                                    ),
                                    current
                            )
                    );
                }
            }
        }

        return null;
    }

    private static int heuristic(
            int[][] board,
            int[][] goal) {

        int distance = 0;

        for (int row = 0;
             row < board.length;
             row++) {

            for (int col = 0;
                 col < board[row].length;
                 col++) {

                int value =
                        board[row][col];

                if (value == 0) {
                    continue;
                }

                for (int goalRow = 0;
                     goalRow < goal.length;
                     goalRow++) {

                    for (int goalCol = 0;
                         goalCol < goal[goalRow].length;
                         goalCol++) {

                        if (goal[goalRow][goalCol]
                                == value) {

                            distance += Math.abs(
                                    row - goalRow
                            );

                            distance += Math.abs(
                                    col - goalCol
                            );
                        }
                    }
                }
            }
        }

        return distance;
    }

    private static List<int[][]>
    generateNeighbors(
            int[][] board) {

        List<int[][]> neighbors =
                new ArrayList<>();

        int emptyRow = -1;
        int emptyCol = -1;

        for (int row = 0;
             row < board.length;
             row++) {

            for (int col = 0;
                 col < board[row].length;
                 col++) {

                if (board[row][col] == 0) {
                    emptyRow = row;
                    emptyCol = col;
                }
            }
        }

        int[][] directions = {
                {-1, 0},
                {1, 0},
                {0, -1},
                {0, 1}
        };

        for (int[] direction :
                directions) {

            int newRow =
                    emptyRow + direction[0];

            int newCol =
                    emptyCol + direction[1];

            if (newRow >= 0
                    && newRow < 3
                    && newCol >= 0
                    && newCol < 3) {

                int[][] copy =
                        copyBoard(board);

                copy[emptyRow][emptyCol] =
                        copy[newRow][newCol];

                copy[newRow][newCol] = 0;

                neighbors.add(copy);
            }
        }

        return neighbors;
    }

    private static String serialize(
            int[][] board) {

        StringBuilder builder =
                new StringBuilder();

        for (int[] row : board) {

            for (int value : row) {
                builder.append(value);
            }
        }

        return builder.toString();
    }

    private static int[][] copyBoard(
            int[][] board) {

        int[][] copy =
                new int[board.length]
                        [board[0].length];

        for (int i = 0;
             i < board.length;
             i++) {

            copy[i] =
                    board[i].clone();
        }

        return copy;
    }
}

public class Main {

    public static void main(String[] args) {

        int[][] start = {
                {1, 2, 3},
                {4, 0, 6},
                {7, 5, 8}
        };

        int[][] goal = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 0}
        };

        PuzzleState solution =
                AStar.solve(
                        start,
                        goal
                );

        System.out.println(
                "Moves required: "
                        + solution.moves()
        );
    }
}

// Moves required: 2

By using an informed heuristic, A* can dramatically reduce the number of states explored compared to uninformed search algorithms, making many otherwise intractable puzzles practical to solve.

Conclusion 📣

A* has earned its reputation as one of the most important pathfinding algorithms in computer science. By combining the actual cost of a path with a heuristic estimate of the remaining distance, it intelligently focuses its search on the most promising routes while still guaranteeing optimal solutions when an admissible heuristic is used.

Throughout this article, we’ve explored the core concepts behind A, examined how its cost function works, implemented the algorithm in Java, and applied it to a variety of real-world scenarios. From guiding NPCs through game worlds and helping robots navigate complex environments to planning GPS routes and solving puzzles, A demonstrates a remarkable balance between efficiency, flexibility, and accuracy.

While the algorithm has limitations — particularly in terms of memory consumption and heuristic design — it remains a foundational technique for pathfinding and graph traversal. Many modern navigation systems and AI applications still rely on A* directly or use algorithms derived from its principles.

Understanding A provides more than just another algorithm for your toolkit. It introduces fundamental concepts such as informed search, heuristics, cost optimization, and graph exploration that appear throughout computer science and artificial intelligence. Whether you’re developing games, building autonomous systems, or simply studying algorithms, mastering A offers valuable insight into how intelligent systems make decisions and find efficient solutions to complex problems.

Thanks for reading! Please give this article a like and follow me if you enjoyed it 😃