Pathfinding with A* Algorithm in Java: Complete Implementation Guide

Introduction

A* (A-star) is one of the most popular and efficient pathfinding algorithms used in games, robotics, and AI applications. It combines the strengths of Dijkstra's algorithm (guaranteed shortest path) with greedy best-first search (fast computation) using heuristics to guide the search.

Project Setup

Maven Dependencies

<!-- pom.xml --> <properties> <javafx.version>21</javafx.version> </properties> <dependencies> <!-- JavaFX for Visualization (Optional) --> <dependency> <groupId>org.openjfx</groupId> <artifactId>javafx-controls</artifactId> <version>${javafx.version}</version> </dependency> <!-- Logging --> <dependency> <groupId>ch.qos.logback</groupId> <artifactId>logback-classic</artifactId> <version>1.4.11</version> </dependency> </dependencies>

Core A* Algorithm Implementation

Node Class

package com.pathfinding.core; import java.util.Objects; public class Node implements Comparable<Node> { private final int x; private final int y; private boolean walkable; private Node parent; // Cost values private double gCost; // Cost from start to this node private double hCost; // Heuristic cost to target private double fCost; // Total cost (g + h) // Additional properties for different terrain types private double movementCost = 1.0; private NodeType type = NodeType.NORMAL; public Node(int x, int y) { this(x, y, true); } public Node(int x, int y, boolean walkable) { this.x = x; this.y = y; this.walkable = walkable; this.gCost = Double.MAX_VALUE; this.hCost = 0; this.fCost = Double.MAX_VALUE; } public void calculateFCost() { this.fCost = gCost + hCost; } public void reset() { this.parent = null; this.gCost = Double.MAX_VALUE; this.hCost = 0; this.fCost = Double.MAX_VALUE; } // Getters and setters public int getX() { return x; } public int getY() { return y; } public boolean isWalkable() { return walkable; } public void setWalkable(boolean walkable) { this.walkable = walkable; } public Node getParent() { return parent; } public void setParent(Node parent) { this.parent = parent; } public double getGCost() { return gCost; } public void setGCost(double gCost) { this.gCost = gCost; } public double getHCost() { return hCost; } public void setHCost(double hCost) { this.hCost = hCost; } public double getFCost() { return fCost; } public double getMovementCost() { return movementCost; } public void setMovementCost(double movementCost) { this.movementCost = movementCost; } public NodeType getType() { return type; } public void setType(NodeType type) { this.type = type; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Node node = (Node) o; return x == node.x && y == node.y; } @Override public int hashCode() { return Objects.hash(x, y); } @Override public int compareTo(Node other) { if (this.fCost < other.fCost) return -1; if (this.fCost > other.fCost) return 1; // If F costs are equal, compare H costs (tie-breaker) return Double.compare(this.hCost, other.hCost); } @Override public String toString() { return String.format("Node(%d, %d) [F:%.1f G:%.1f H:%.1f]", x, y, fCost, gCost, hCost); } public enum NodeType { NORMAL(1.0), WATER(3.0), // Higher cost to cross water FOREST(2.0), // Moderate cost for forests MOUNTAIN(5.0), // Very high cost for mountains ROAD(0.8), // Lower cost for roads SWAMP(4.0); // High cost for swamps private final double costMultiplier; NodeType(double costMultiplier) { this.costMultiplier = costMultiplier; } public double getCostMultiplier() { return costMultiplier; } } }

Heuristic Calculators

package com.pathfinding.heuristics; import com.pathfinding.core.Node; public interface Heuristic { double calculate(Node start, Node end); // Common heuristic implementations class Manhattan implements Heuristic { @Override public double calculate(Node start, Node end) { int dx = Math.abs(start.getX() - end.getX()); int dy = Math.abs(start.getY() - end.getY()); return dx + dy; } } class Euclidean implements Heuristic { @Override public double calculate(Node start, Node end) { int dx = start.getX() - end.getX(); int dy = start.getY() - end.getY(); return Math.sqrt(dx * dx + dy * dy); } } class Chebyshev implements Heuristic { @Override public double calculate(Node start, Node end) { int dx = Math.abs(start.getX() - end.getX()); int dy = Math.abs(start.getY() - end.getY()); return Math.max(dx, dy); } } class Diagonal implements Heuristic { private static final double D = 1.0; // Cost for horizontal/vertical movement private static final double D2 = Math.sqrt(2); // Cost for diagonal movement @Override public double calculate(Node start, Node end) { int dx = Math.abs(start.getX() - end.getX()); int dy = Math.abs(start.getY() - end.getY()); return D * (dx + dy) + (D2 - 2 * D) * Math.min(dx, dy); } } }

Grid Representation

package com.pathfinding.core; import java.util.ArrayList; import java.util.List; public class Grid { private final int width; private final int height; private final Node[][] nodes; private boolean allowDiagonal = true; public Grid(int width, int height) { this.width = width; this.height = height; this.nodes = new Node[width][height]; initializeGrid(); } public Grid(int width, int height, boolean[][] walkableMap) { this.width = width; this.height = height; this.nodes = new Node[width][height]; initializeGrid(walkableMap); } private void initializeGrid() { for (int x = 0; x < width; x++) { for (int y = 0; y < height; y++) { nodes[x][y] = new Node(x, y); } } } private void initializeGrid(boolean[][] walkableMap) { for (int x = 0; x < width; x++) { for (int y = 0; y < height; y++) { boolean walkable = walkableMap[x][y]; nodes[x][y] = new Node(x, y, walkable); } } } public Node getNode(int x, int y) { if (x >= 0 && x < width && y >= 0 && y < height) { return nodes[x][y]; } return null; } public void setWalkable(int x, int y, boolean walkable) { Node node = getNode(x, y); if (node != null) { node.setWalkable(walkable); } } public void setNodeType(int x, int y, Node.NodeType type) { Node node = getNode(x, y); if (node != null) { node.setType(type); node.setMovementCost(type.getCostMultiplier()); } } public List<Node> getNeighbors(Node node) { List<Node> neighbors = new ArrayList<>(); int x = node.getX(); int y = node.getY(); // Cardinal directions (up, right, down, left) addIfValid(neighbors, x, y - 1); // Up addIfValid(neighbors, x + 1, y); // Right addIfValid(neighbors, x, y + 1); // Down addIfValid(neighbors, x - 1, y); // Left // Diagonal directions (if allowed) if (allowDiagonal) { addIfValid(neighbors, x - 1, y - 1); // Up-Left addIfValid(neighbors, x + 1, y - 1); // Up-Right addIfValid(neighbors, x - 1, y + 1); // Down-Left addIfValid(neighbors, x + 1, y + 1); // Down-Right } return neighbors; } private void addIfValid(List<Node> neighbors, int x, int y) { Node node = getNode(x, y); if (node != null && node.isWalkable()) { neighbors.add(node); } } public double getMovementCost(Node from, Node to) { // Check if movement is diagonal boolean isDiagonal = (from.getX() != to.getX() && from.getY() != to.getY()); double baseCost = isDiagonal ? Math.sqrt(2) : 1.0; // Apply terrain cost multiplier return baseCost * to.getMovementCost(); } public void resetAllNodes() { for (int x = 0; x < width; x++) { for (int y = 0; y < height; y++) { nodes[x][y].reset(); } } } // Getters public int getWidth() { return width; } public int getHeight() { return height; } public boolean isAllowDiagonal() { return allowDiagonal; } public void setAllowDiagonal(boolean allowDiagonal) { this.allowDiagonal = allowDiagonal; } public void printGrid() { for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { Node node = nodes[x][y]; char symbol = node.isWalkable() ? '.' : '#'; System.out.print(symbol + " "); } System.out.println(); } } public void printGridWithPath(List<Node> path) { for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { Node node = nodes[x][y]; char symbol; if (path.contains(node)) { symbol = '*'; } else if (!node.isWalkable()) { symbol = '#'; } else { symbol = '.'; } System.out.print(symbol + " "); } System.out.println(); } } }

A* Pathfinder Implementation

package com.pathfinding.core; import com.pathfinding.heuristics.Heuristic; import java.util.*; public class AStarPathfinder { private final Grid grid; private Heuristic heuristic; private boolean useTieBreaking; // Statistics private int nodesExplored; private long executionTime; private int pathLength; public AStarPathfinder(Grid grid) { this(grid, new Heuristic.Euclidean()); } public AStarPathfinder(Grid grid, Heuristic heuristic) { this.grid = grid; this.heuristic = heuristic; this.useTieBreaking = true; } public PathfindingResult findPath(Node start, Node end) { return findPath(start.getX(), start.getY(), end.getX(), end.getY()); } public PathfindingResult findPath(int startX, int startY, int endX, int endY) { long startTime = System.nanoTime(); nodesExplored = 0; Node startNode = grid.getNode(startX, startY); Node endNode = grid.getNode(endX, endY); if (startNode == null || endNode == null) { return new PathfindingResult(false, "Invalid start or end position"); } if (!startNode.isWalkable() || !endNode.isWalkable()) { return new PathfindingResult(false, "Start or end node is not walkable"); } // Reset all nodes grid.resetAllNodes(); // Initialize open and closed sets PriorityQueue<Node> openSet = new PriorityQueue<>(); Set<Node> closedSet = new HashSet<>(); // Initialize start node startNode.setGCost(0); startNode.setHCost(heuristic.calculate(startNode, endNode)); startNode.calculateFCost(); openSet.add(startNode); while (!openSet.isEmpty()) { Node currentNode = openSet.poll(); nodesExplored++; // Check if we reached the destination if (currentNode.equals(endNode)) { executionTime = (System.nanoTime() - startTime) / 1_000_000; // Convert to ms List<Node> path = reconstructPath(currentNode); pathLength = path.size(); return new PathfindingResult(true, path, "Path found successfully"); } closedSet.add(currentNode); // Explore neighbors for (Node neighbor : grid.getNeighbors(currentNode)) { if (closedSet.contains(neighbor)) { continue; } double tentativeGCost = currentNode.getGCost() + grid.getMovementCost(currentNode, neighbor); if (tentativeGCost < neighbor.getGCost()) { neighbor.setParent(currentNode); neighbor.setGCost(tentativeGCost); neighbor.setHCost(heuristic.calculate(neighbor, endNode)); // Apply tie-breaking if enabled if (useTieBreaking) { neighbor.setHCost(neighbor.getHCost() * (1.0 + 1.0 / (grid.getWidth() * grid.getHeight()))); } neighbor.calculateFCost(); if (!openSet.contains(neighbor)) { openSet.add(neighbor); } } } } executionTime = (System.nanoTime() - startTime) / 1_000_000; return new PathfindingResult(false, "No path found"); } private List<Node> reconstructPath(Node endNode) { List<Node> path = new ArrayList<>(); Node currentNode = endNode; while (currentNode != null) { path.add(0, currentNode); // Add to beginning to reverse the path currentNode = currentNode.getParent(); } return path; } // Getters and setters public Heuristic getHeuristic() { return heuristic; } public void setHeuristic(Heuristic heuristic) { this.heuristic = heuristic; } public boolean isUseTieBreaking() { return useTieBreaking; } public void setUseTieBreaking(boolean useTieBreaking) { this.useTieBreaking = useTieBreaking; } // Statistics getters public int getNodesExplored() { return nodesExplored; } public long getExecutionTime() { return executionTime; } public int getPathLength() { return pathLength; } public static class PathfindingResult { private final boolean success; private final String message; private final List<Node> path; private final int pathLength; private final int nodesExplored; private final long executionTime; public PathfindingResult(boolean success, String message) { this(success, message, Collections.emptyList(), 0, 0, 0); } public PathfindingResult(boolean success, List<Node> path, String message) { this(success, message, path, path.size(), 0, 0); } public PathfindingResult(boolean success, String message, List<Node> path, int pathLength, int nodesExplored, long executionTime) { this.success = success; this.message = message; this.path = path; this.pathLength = pathLength; this.nodesExplored = nodesExplored; this.executionTime = executionTime; } // Getters public boolean isSuccess() { return success; } public String getMessage() { return message; } public List<Node> getPath() { return path; } public int getPathLength() { return pathLength; } public int getNodesExplored() { return nodesExplored; } public long getExecutionTime() { return executionTime; } public double getPathCost() { if (path.isEmpty()) return 0.0; return path.get(path.size() - 1).getGCost(); } } }

Advanced Features

Jump Point Search (JPS) for Grids

package com.pathfinding.advanced; import com.pathfinding.core.Grid; import com.pathfinding.core.Node; import com.pathfinding.heuristics.Heuristic; import java.util.*; public class JumpPointSearch { private final Grid grid; private final Heuristic heuristic; public JumpPointSearch(Grid grid) { this.grid = grid; this.heuristic = new Heuristic.Euclidean(); } public List<Node> findPath(Node start, Node end) { PriorityQueue<Node> openSet = new PriorityQueue<>(); Set<Node> closedSet = new HashSet<>(); start.setGCost(0); start.setHCost(heuristic.calculate(start, end)); start.calculateFCost(); openSet.add(start); while (!openSet.isEmpty()) { Node current = openSet.poll(); if (current.equals(end)) { return reconstructPath(current); } closedSet.add(current); for (Node neighbor : getPrunedNeighbors(current)) { if (closedSet.contains(neighbor)) continue; Node jumpPoint = jump(neighbor, current, end); if (jumpPoint != null && !closedSet.contains(jumpPoint)) { double tentativeGCost = current.getGCost() + distance(current, jumpPoint); if (tentativeGCost < jumpPoint.getGCost()) { jumpPoint.setParent(current); jumpPoint.setGCost(tentativeGCost); jumpPoint.setHCost(heuristic.calculate(jumpPoint, end)); jumpPoint.calculateFCost(); if (!openSet.contains(jumpPoint)) { openSet.add(jumpPoint); } } } } } return Collections.emptyList(); } private Node jump(Node current, Node parent, Node goal) { if (current == null || !current.isWalkable()) return null; if (current.equals(goal)) return current; int dx = current.getX() - parent.getX(); int dy = current.getY() - parent.getY(); // Check for forced neighbors (diagonal movement) if (dx != 0 && dy != 0) { if ((grid.getNode(current.getX() - dx, current.getY()) == null || !grid.getNode(current.getX() - dx, current.getY()).isWalkable()) && grid.getNode(current.getX() - dx, current.getY() + dy) != null && grid.getNode(current.getX() - dx, current.getY() + dy).isWalkable()) { return current; } if ((grid.getNode(current.getX(), current.getY() - dy) == null || !grid.getNode(current.getX(), current.getY() - dy).isWalkable()) && grid.getNode(current.getX() + dx, current.getY() - dy) != null && grid.getNode(current.getX() + dx, current.getY() - dy).isWalkable()) { return current; } // Recursive diagonal jumps if (jump(grid.getNode(current.getX() + dx, current.getY()), current, goal) != null || jump(grid.getNode(current.getX(), current.getY() + dy), current, goal) != null) { return current; } } else { // Horizontal/vertical movement if (dx != 0) { if ((grid.getNode(current.getX() + dx, current.getY() + 1) == null || !grid.getNode(current.getX() + dx, current.getY() + 1).isWalkable()) && grid.getNode(current.getX() + dx, current.getY() + 1) != null && grid.getNode(current.getX() + dx, current.getY() + 1).isWalkable()) { return current; } if ((grid.getNode(current.getX() + dx, current.getY() - 1) == null || !grid.getNode(current.getX() + dx, current.getY() - 1).isWalkable()) && grid.getNode(current.getX() + dx, current.getY() - 1) != null && grid.getNode(current.getX() + dx, current.getY() - 1).isWalkable()) { return current; } } else { if ((grid.getNode(current.getX() + 1, current.getY() + dy) == null || !grid.getNode(current.getX() + 1, current.getY() + dy).isWalkable()) && grid.getNode(current.getX() + 1, current.getY() + dy) != null && grid.getNode(current.getX() + 1, current.getY() + dy).isWalkable()) { return current; } if ((grid.getNode(current.getX() - 1, current.getY() + dy) == null || !grid.getNode(current.getX() - 1, current.getY() + dy).isWalkable()) && grid.getNode(current.getX() - 1, current.getY() + dy) != null && grid.getNode(current.getX() - 1, current.getY() + dy).isWalkable()) { return current; } } } return jump(grid.getNode(current.getX() + dx, current.getY() + dy), current, goal); } private List<Node> getPrunedNeighbors(Node node) { List<Node> neighbors = new ArrayList<>(); Node parent = node.getParent(); if (parent == null) { // Return all neighbors for start node return grid.getNeighbors(node); } int dx = Integer.signum(node.getX() - parent.getX()); int dy = Integer.signum(node.getY() - parent.getY()); // Add natural neighbors if (dx != 0 && dy != 0) { // Diagonal movement addIfValid(neighbors, node.getX(), node.getY() + dy); addIfValid(neighbors, node.getX() + dx, node.getY()); addIfValid(neighbors, node.getX() + dx, node.getY() + dy); // Forced neighbors if (!grid.getNode(node.getX() - dx, node.getY()).isWalkable()) { addIfValid(neighbors, node.getX() - dx, node.getY() + dy); } if (!grid.getNode(node.getX(), node.getY() - dy).isWalkable()) { addIfValid(neighbors, node.getX() + dx, node.getY() - dy); } } else { // Horizontal/vertical movement if (dx != 0) { addIfValid(neighbors, node.getX() + dx, node.getY()); // Forced neighbors if (!grid.getNode(node.getX(), node.getY() + 1).isWalkable()) { addIfValid(neighbors, node.getX() + dx, node.getY() + 1); } if (!grid.getNode(node.getX(), node.getY() - 1).isWalkable()) { addIfValid(neighbors, node.getX() + dx, node.getY() - 1); } } else { addIfValid(neighbors, node.getX(), node.getY() + dy); // Forced neighbors if (!grid.getNode(node.getX() + 1, node.getY()).isWalkable()) { addIfValid(neighbors, node.getX() + 1, node.getY() + dy); } if (!grid.getNode(node.getX() - 1, node.getY()).isWalkable()) { addIfValid(neighbors, node.getX() - 1, node.getY() + dy); } } } return neighbors; } private void addIfValid(List<Node> list, int x, int y) { Node node = grid.getNode(x, y); if (node != null && node.isWalkable()) { list.add(node); } } private double distance(Node a, Node b) { int dx = Math.abs(a.getX() - b.getX()); int dy = Math.abs(a.getY() - b.getY()); if (dx == dy) { return dx * Math.sqrt(2); } else { return Math.abs(dx - dy) + Math.min(dx, dy) * Math.sqrt(2); } } private List<Node> reconstructPath(Node endNode) { List<Node> path = new ArrayList<>(); Node current = endNode; while (current != null) { path.add(0, current); current = current.getParent(); } return path; } }

Path Smoothing

package com.pathfinding.advanced; import com.pathfinding.core.Grid; import com.pathfinding.core.Node; import java.util.ArrayList; import java.util.List; public class PathSmoother { public static List<Node> smoothPath(List<Node> path, Grid grid) { if (path.size() <= 2) { return path; } List<Node> smoothedPath = new ArrayList<>(); smoothedPath.add(path.get(0)); int currentIndex = 0; while (currentIndex < path.size() - 1) { int furthestVisible = currentIndex + 1; for (int i = currentIndex + 2; i < path.size(); i++) { if (isLineOfSight(grid, path.get(currentIndex), path.get(i))) { furthestVisible = i; } } smoothedPath.add(path.get(furthestVisible)); currentIndex = furthestVisible; } return smoothedPath; } private static boolean isLineOfSight(Grid grid, Node start, Node end) { int x0 = start.getX(); int y0 = start.getY(); int x1 = end.getX(); int y1 = end.getY(); int dx = Math.abs(x1 - x0); int dy = Math.abs(y1 - y0); int x = x0; int y = y0; int n = 1 + dx + dy; int xInc = (x1 > x0) ? 1 : -1; int yInc = (y1 > y0) ? 1 : -1; int error = dx - dy; dx *= 2; dy *= 2; for (; n > 0; --n) { Node node = grid.getNode(x, y); if (node == null || !node.isWalkable()) { return false; } if (x == x1 && y == y1) { break; } if (error > 0) { x += xInc; error -= dy; } else { y += yInc; error += dx; } } return true; } public static List<Node> bezierSmoothPath(List<Node> path, int segments) { if (path.size() < 3) { return path; } List<Node> smoothedPath = new ArrayList<>(); for (int i = 0; i < path.size() - 2; i++) { Node p0 = path.get(i); Node p1 = path.get(i + 1); Node p2 = path.get(i + 2); for (int j = 0; j <= segments; j++) { double t = (double) j / segments; double x = bezierPoint(p0.getX(), p1.getX(), p2.getX(), t); double y = bezierPoint(p0.getY(), p1.getY(), p2.getY(), t); // Create a new node for the smoothed point // Note: In practice, you might want to snap to grid or handle differently smoothedPath.add(new Node((int) Math.round(x), (int) Math.round(y))); } } return smoothedPath; } private static double bezierPoint(double p0, double p1, double p2, double t) { double oneMinusT = 1 - t; return oneMinusT * oneMinusT * p0 + 2 * oneMinusT * t * p1 + t * t * p2; } }

Visualization with JavaFX

Pathfinding Visualizer

package com.pathfinding.visualization; import com.pathfinding.core.*; import com.pathfinding.heuristics.Heuristic; import javafx.application.Application; import javafx.application.Platform; import javafx.geometry.Insets; import javafx.scene.Scene; import javafx.scene.canvas.Canvas; import javafx.scene.canvas.GraphicsContext; import javafx.scene.control.*; import javafx.scene.layout.BorderPane; import javafx.scene.layout.HBox; import javafx.scene.layout.VBox; import javafx.scene.paint.Color; import javafx.stage.Stage; import java.util.List; import java.util.concurrent.Executors; import java.util.concurrent.ScheduledExecutorService; import java.util.concurrent.TimeUnit; public class PathfindingVisualizer extends Application { private static final int GRID_SIZE = 20; private static final int CELL_SIZE = 25; private Grid grid; private AStarPathfinder pathfinder; private Canvas canvas; private GraphicsContext gc; private Node startNode; private Node endNode; private List<Node> currentPath; private ComboBox<String> heuristicCombo; private CheckBox diagonalCheckbox; private CheckBox tieBreakingCheckbox; private Button findPathButton; private Button clearButton; private Label statsLabel; @Override public void start(Stage primaryStage) { initializeGrid(); setupUI(primaryStage); drawGrid(); } private void initializeGrid() { grid = new Grid(GRID_SIZE, GRID_SIZE); pathfinder = new AStarPathfinder(grid); // Set default start and end positions startNode = grid.getNode(2, 2); endNode = grid.getNode(GRID_SIZE - 3, GRID_SIZE - 3); // Add some obstacles createTestObstacles(); } private void createTestObstacles() { // Create a maze-like pattern for (int x = 5; x < GRID_SIZE - 5; x++) { for (int y = 5; y < GRID_SIZE - 5; y++) { if ((x + y) % 4 == 0) { grid.setWalkable(x, y, false); } } } // Add some terrain variations for (int x = 0; x < GRID_SIZE; x++) { for (int y = 0; y < GRID_SIZE; y++) { if ((x + y) % 7 == 0) { grid.setNodeType(x, y, Node.NodeType.FOREST); } else if ((x + y) % 9 == 0) { grid.setNodeType(x, y, Node.NodeType.WATER); } } } } private void setupUI(Stage primaryStage) { BorderPane root = new BorderPane(); root.setPadding(new Insets(10)); // Create canvas canvas = new Canvas(GRID_SIZE * CELL_SIZE, GRID_SIZE * CELL_SIZE); gc = canvas.getGraphicsContext2D(); // Setup mouse interaction setupMouseHandlers(); // Create control panel VBox controlPanel = createControlPanel(); root.setCenter(canvas); root.setBottom(controlPanel); Scene scene = new Scene(root); primaryStage.setTitle("A* Pathfinding Visualizer"); primaryStage.setScene(scene); primaryStage.show(); } private VBox createControlPanel() { VBox panel = new VBox(10); panel.setPadding(new Insets(10)); // Heuristic selection HBox heuristicBox = new HBox(10); heuristicBox.getChildren().add(new Label("Heuristic:")); heuristicCombo = new ComboBox<>(); heuristicCombo.getItems().addAll("Manhattan", "Euclidean", "Chebyshev", "Diagonal"); heuristicCombo.setValue("Euclidean"); heuristicBox.getChildren().add(heuristicCombo); // Checkboxes diagonalCheckbox = new CheckBox("Allow Diagonal"); diagonalCheckbox.setSelected(true); tieBreakingCheckbox = new CheckBox("Tie Breaking"); tieBreakingCheckbox.setSelected(true); // Buttons HBox buttonBox = new HBox(10); findPathButton = new Button("Find Path"); clearButton = new Button("Clear Path"); buttonBox.getChildren().addAll(findPathButton, clearButton); // Stats label statsLabel = new Label("Ready"); // Event handlers findPathButton.setOnAction(e -> findPath()); clearButton.setOnAction(e -> clearPath()); diagonalCheckbox.setOnAction(e -> grid.setAllowDiagonal(diagonalCheckbox.isSelected())); tieBreakingCheckbox.setOnAction(e -> pathfinder.setUseTieBreaking(tieBreakingCheckbox.isSelected())); panel.getChildren().addAll(heuristicBox, diagonalCheckbox, tieBreakingCheckbox, buttonBox, statsLabel); return panel; } private void setupMouseHandlers() { canvas.setOnMouseClicked(e -> { int x = (int) (e.getX() / CELL_SIZE); int y = (int) (e.getY() / CELL_SIZE); if (x >= 0 && x < GRID_SIZE && y >= 0 && y < GRID_SIZE) { Node clickedNode = grid.getNode(x, y); if (e.isShiftDown()) { // Set start node startNode = clickedNode; } else if (e.isControlDown()) { // Set end node endNode = clickedNode; } else { // Toggle obstacle clickedNode.setWalkable(!clickedNode.isWalkable()); } drawGrid(); } }); canvas.setOnMouseDragged(e -> { int x = (int) (e.getX() / CELL_SIZE); int y = (int) (e.getY() / CELL_SIZE); if (x >= 0 && x < GRID_SIZE && y >= 0 && y < GRID_SIZE) { Node draggedNode = grid.getNode(x, y); if (!draggedNode.equals(startNode) && !draggedNode.equals(endNode)) { draggedNode.setWalkable(false); drawGrid(); } } }); } private void findPath() { // Update heuristic String selectedHeuristic = heuristicCombo.getValue(); switch (selectedHeuristic) { case "Manhattan": pathfinder.setHeuristic(new Heuristic.Manhattan()); break; case "Euclidean": pathfinder.setHeuristic(new Heuristic.Euclidean()); break; case "Chebyshev": pathfinder.setHeuristic(new Heuristic.Chebyshev()); break; case "Diagonal": pathfinder.setHeuristic(new Heuristic.Diagonal()); break; } // Find path AStarPathfinder.PathfindingResult result = pathfinder.findPath(startNode, endNode); if (result.isSuccess()) { currentPath = result.getPath(); statsLabel.setText(String.format( "Path found! Length: %d, Cost: %.2f, Nodes explored: %d, Time: %dms", result.getPathLength(), result.getPathCost(), result.getNodesExplored(), result.getExecutionTime() )); } else { currentPath = null; statsLabel.setText("No path found: " + result.getMessage()); } drawGrid(); } private void clearPath() { currentPath = null; grid.resetAllNodes(); drawGrid(); statsLabel.setText("Ready"); } private void drawGrid() { gc.clearRect(0, 0, canvas.getWidth(), canvas.getHeight()); // Draw grid cells for (int x = 0; x < GRID_SIZE; x++) { for (int y = 0; y < GRID_SIZE; y++) { Node node = grid.getNode(x, y); drawNode(node, x, y); } } // Draw path if exists if (currentPath != null) { drawPath(currentPath); } } private void drawNode(Node node, int x, int y) { double screenX = x * CELL_SIZE; double screenY = y * CELL_SIZE; // Determine color based on node type and state Color color = getNodeColor(node); gc.setFill(color); gc.fillRect(screenX, screenY, CELL_SIZE, CELL_SIZE); // Draw border gc.setStroke(Color.LIGHTGRAY); gc.strokeRect(screenX, screenY, CELL_SIZE, CELL_SIZE); // Draw start/end markers if (node.equals(startNode)) { gc.setFill(Color.GREEN); gc.fillText("S", screenX + CELL_SIZE / 3, screenY + CELL_SIZE * 2 / 3); } else if (node.equals(endNode)) { gc.setFill(Color.RED); gc.fillText("E", screenX + CELL_SIZE / 3, screenY + CELL_SIZE * 2 / 3); } } private Color getNodeColor(Node node) { if (!node.isWalkable()) { return Color.DARKGRAY; // Obstacle } if (node.equals(startNode)) { return Color.LIGHTGREEN; } if (node.equals(endNode)) { return Color.LIGHTCORAL; } // Color based on terrain type switch (node.getType()) { case WATER: return Color.LIGHTBLUE; case FOREST: return Color.DARKGREEN; case MOUNTAIN: return Color.GRAY; case ROAD: return Color.LIGHTYELLOW; case SWAMP: return Color.DARKOLIVEGREEN; default: return Color.WHITE; } } private void drawPath(List<Node> path) { gc.setStroke(Color.PURPLE); gc.setLineWidth(3); for (int i = 0; i < path.size() - 1; i++) { Node current = path.get(i); Node next = path.get(i + 1); double startX = current.getX() * CELL_SIZE + CELL_SIZE / 2; double startY = current.getY() * CELL_SIZE + CELL_SIZE / 2; double endX = next.getX() * CELL_SIZE + CELL_SIZE / 2; double endY = next.getY() * CELL_SIZE + CELL_SIZE / 2; gc.strokeLine(startX, startY, endX, endY); } // Draw path nodes gc.setFill(Color.PURPLE); for (Node node : path) { if (!node.equals(startNode) && !node.equals(endNode)) { double x = node.getX() * CELL_SIZE + CELL_SIZE / 2; double y = node.getY() * CELL_SIZE + CELL_SIZE / 2; gc.fillOval(x - 3, y - 3, 6, 6); } } } public static void main(String[] args) { launch(args); } }

Usage Examples

Basic Pathfinding Demo

package com.pathfinding.demo; import com.pathfinding.core.*; import com.pathfinding.heuristics.Heuristic; public class BasicPathfindingDemo { public static void main(String[] args) { // Create a 10x10 grid Grid grid = new Grid(10, 10); // Add some obstacles grid.setWalkable(3, 3, false); grid.setWalkable(3, 4, false); grid.setWalkable(3, 5, false); grid.setWalkable(4, 5, false); grid.setWalkable(5, 5, false); grid.setWalkable(6, 5, false); grid.setWalkable(7, 5, false); // Create pathfinder with Euclidean heuristic AStarPathfinder pathfinder = new AStarPathfinder(grid, new Heuristic.Euclidean()); // Define start and end points Node start = grid.getNode(1, 1); Node end = grid.getNode(8, 8); // Find path AStarPathfinder.PathfindingResult result = pathfinder.findPath(start, end); // Display results if (result.isSuccess()) { System.out.println("Path found successfully!"); System.out.println("Path length: " + result.getPathLength()); System.out.println("Path cost: " + result.getPathCost()); System.out.println("Nodes explored: " + result.getNodesExplored()); System.out.println("Execution time: " + result.getExecutionTime() + "ms"); // Print grid with path grid.printGridWithPath(result.getPath()); // Print path coordinates System.out.println("\nPath coordinates:"); for (Node node : result.getPath()) { System.out.println(" (" + node.getX() + ", " + node.getY() + ")"); } } else { System.out.println("No path found: " + result.getMessage()); grid.printGrid(); } } }

Performance Comparison

package com.pathfinding.demo; import com.pathfinding.core.*; import com.pathfinding.heuristics.Heuristic; import java.util.ArrayList; import java.util.List; public class PerformanceComparison { public static void main(String[] args) { int gridSize = 50; int numTests = 10; List<Heuristic> heuristics = List.of( new Heuristic.Manhattan(), new Heuristic.Euclidean(), new Heuristic.Chebyshev(), new Heuristic.Diagonal() ); List<String> heuristicNames = List.of("Manhattan", "Euclidean", "Chebyshev", "Diagonal"); System.out.println("Performance Comparison (" + gridSize + "x" + gridSize + " grid)"); System.out.println("============================================="); for (int i = 0; i < heuristics.size(); i++) { Heuristic heuristic = heuristics.get(i); String name = heuristicNames.get(i); long totalTime = 0; int totalNodesExplored = 0; int successfulPaths = 0; for (int test = 0; test < numTests; test++) { Grid grid = createRandomGrid(gridSize, gridSize, 0.3); // 30% obstacles AStarPathfinder pathfinder = new AStarPathfinder(grid, heuristic); Node start = grid.getNode(0, 0); Node end = grid.getNode(gridSize - 1, gridSize - 1); AStarPathfinder.PathfindingResult result = pathfinder.findPath(start, end); if (result.isSuccess()) { totalTime += result.getExecutionTime(); totalNodesExplored += result.getNodesExplored(); successfulPaths++; } } if (successfulPaths > 0) { double avgTime = (double) totalTime / successfulPaths; double avgNodes = (double) totalNodesExplored / successfulPaths; System.out.printf("%-10s: Avg Time: %6.2fms, Avg Nodes: %6.1f, Success Rate: %d/%d%n", name, avgTime, avgNodes, successfulPaths, numTests); } else { System.out.printf("%-10s: No successful paths found%n", name); } } } private static Grid createRandomGrid(int width, int height, double obstacleProbability) { boolean[][] walkableMap = new boolean[width][height]; for (int x = 0; x < width; x++) { for (int y = 0; y < height; y++) { walkableMap[x][y] = Math.random() > obstacleProbability; } } // Ensure start and end are walkable walkableMap[0][0] = true; walkableMap[width - 1][height - 1] = true; return new Grid(width, height, walkableMap); } }

Summary

This comprehensive A* pathfinding implementation provides:

Core Algorithm: Complete A* implementation with open/closed sets
Multiple Heuristics: Manhattan, Euclidean, Chebyshev, and Diagonal distances
Advanced Features: Jump Point Search for optimization, path smoothing
Terrain Support: Different movement costs for various terrain types
Visualization: JavaFX-based visualizer with interactive grid
Performance Metrics: Execution time, nodes explored, path cost tracking
Flexible Grid: Support for obstacles, diagonal movement, and custom costs

The implementation is production-ready and can be easily integrated into games, robotics applications, or any project requiring efficient pathfinding capabilities.