A* Pathfinding Algorithms

Advanced pathfinding algorithms with limited visibility and comprehensive performance benchmarking

Java Swing Algorithms Data Structures Cross-Platform

Project Overview

Repeated A* is a pathfinding approach for environments with limited visibility. The algorithm plans a path with current knowledge, follows it until discovering new obstacles, then replans from the current position. This process repeats until reaching the goal, making it ideal for robot navigation and other real-world scenarios.

This project implements three variants with configurable tiebreaker strategies, sight radius settings (1-20 cells), and algorithm types (Forward, Backward, or Adaptive). The application provides comprehensive tools for comparing how these parameter choices affect performance across different maze configurations.

Interactive Maze Solver

The main interface features three integrated modes: Interactive Solver, Saved Results, and Performance Analysis. Users can create custom mazes, configure algorithm parameters, and watch real-time pathfinding visualization.

The left panel provides comprehensive algorithm configuration options, including tiebreaker strategies, sight radius settings, and algorithm type selection. All settings persist between sessions for consistent testing.

Real-Time Algorithm Visualization

Watch algorithms explore the maze in real-time, showing explored cells, the current frontier, and the final optimal path. The sight radius limitation creates realistic partial observability.

Different colors represent various cell states: unexplored (white), explored (light pink), current planned path (yellow), goal (red). The visualization updates dynamically as the algorithm progresses.

Algorithm Performance Comparison

Exploration Pattern Heat Maps

Individual Algorithm Analysis

Statistical Performance Metrics

Performance Analysis & Heat Maps

Comprehensive performance analysis with heat map visualizations showing exploration patterns, statistical comparisons between algorithms, and detailed performance metrics.

Run batch tests across multiple mazes to compare algorithm efficiency. Heat maps reveal how different parameter choices affect exploration patterns and overall performance characteristics.

Technical Implementation

Algorithm Variants

Repeated Forward A*: Plans from current position to goal, replanning when new information is discovered.

Repeated Backward A*: Plans from goal to current position. Less efficient because searches encounter unknown areas late in the process, requiring extensive computation to find new paths toward the agent's current location, whereas forward search operates in a smaller known area.

Adaptive A*: Learns improved heuristics from previous searches by updating distance estimates based on actual path costs discovered, becoming more efficient with repeated use.

Limited Knowledge Simulation

The algorithms operate with partial observability through a configurable sight radius (1-20 cell radius). This simulates real-world scenarios where complete environment information isn't available.

Agents must explore the environment while pathfinding, discovering walls and open spaces within their sight radius as they move through the maze.

Performance Analysis

Comprehensive benchmarking across 50 predetermined mazes reveals significant performance differences:

Algorithm	Avg Expanded Cells	Avg Time (ms)
Repeated Forward A* (g-tie)	9,847	12.3
Repeated Forward A* (h-tie)	254,891	45.7
Repeated Backward A* (g-tie)	125,432	28.9
Adaptive A* (g-tie)	9,623	13.1

Data Structures & Architecture

Custom Priority Queue: Optimized for A* search operations with efficient priority updates.

Modular Design: Clean separation between algorithm logic, UI components, and data management.

Cross-Platform Support: Smart build system with dual launchers for end users and developers.

Key Features

Interactive maze editor with multiple editing modes
Real-time algorithm visualization
Configurable parameters (tiebreaker strategy, sight radius)
Heat map generation showing exploration patterns
Persistent configuration management
Result export/import system
Comprehensive unit testing

Software Engineering

The project demonstrates professional development practices including:

Smart build detection (only rebuilds when necessary)
Cross-platform launcher system (Windows/Unix/macOS)
Clean project organization with proper separation of concerns
Comprehensive documentation and README
Professional error handling and user feedback

Core Algorithm Implementation

Here's a simplified version of the A* search implementation:

public class MazeSolver {
    private PriorityQueue openList;
    private Set<State> closedList;
    private int sightRadius;
    
    public SolveResult solveMaze(char[][] maze, Coordinates start, Coordinates goal) {
        openList = new PriorityQueue();
        closedList = new HashSet<>();
        
        State startState = new State(start, 0, calculateHeuristic(start, goal));
        openList.add(startState);
        
        while (!openList.isEmpty()) {
            State current = openList.poll();
            
            if (current.getPosition().equals(goal)) {
                return reconstructPath(current);
            }
            
            closedList.add(current);
            
            // Explore visible neighbors within sight radius
            for (Coordinates neighbor : getVisibleNeighbors(current.getPosition(), maze)) {
                if (closedList.contains(new State(neighbor, 0, 0))) continue;
                
                int tentativeG = current.getG() + 1;
                State neighborState = new State(neighbor, tentativeG, 
                                              calculateHeuristic(neighbor, goal));
                neighborState.setParent(current);
                
                if (!openList.contains(neighborState) || 
                    tentativeG < neighborState.getG()) {
                    openList.add(neighborState);
                }
            }
        }
        
        return new SolveResult(false, closedList.size(), 0);
    }
    
    private List<Coordinates> getVisibleNeighbors(Coordinates pos, char[][] maze) {
        // Return neighbors within sight radius that are not walls
        // Implementation handles partial observability
    }
}

Installation & Usage

Download from GitHub

Prerequisites: Java 17 or higher

Clone the repository:

git clone https://github.com/Electrolyzer/A-Star_Maze_Solvers.git

Navigate to directory:

cd A-Star_Maze_Solvers

Or download the ZIP file directly from the GitHub repository.

Quick Start

Launch the application with smart build detection:

Windows:

.\launcher.bat

Unix/Linux/macOS:

./launcher.sh

The launcher automatically builds the project if needed and starts the application.

Development Mode

For development with forced rebuilds: