Pathfinding with A* Algorithm in Java: Complete Implementation Guide

Table of Contents

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.