---

🗺️ A* Pathfinding Algorithm Evaluator

Welcome to the A Pathfinding Algorithm Evaluator*! This project is a robust, Java-based simulation designed to execute, visualize, and benchmark the A* (A-Star) search algorithm across procedurally generated grid maps.

Whether you are studying pathfinding, optimizing game AI, or simply exploring heuristic behaviors, this tool provides everything you need to understand how different distance metrics impact search efficiency. It runs comprehensive tests, tracks performance, and exports detailed analytics directly to CSV files.

---

📂 Project Structure and Navigation

To help you navigate the codebase, here is a complete breakdown of the project's architecture and where to find specific functionality:

📁 Project Root
├── ⚙️ Configuration & Entry
│   ├── Config.java              # Centralized constants (map size, runs, obstacle rate)
│   └── Main.java                # Application entry point and core A* execution loop
│
├── 🧠 Core Pathfinding Logic
│   ├── Node.java                # Represents a grid cell with x/y coordinates and g/h/f costs
│   ├── OpenList.java            # Custom Min-Heap priority queue for fast f-cost retrieval
│   └── HeuristicCalculator.java # Modern implementations of distance metrics
│
├── 🗺️ Environment Management
│   ├── MapGenerator.java        # Handles procedural map creation and random obstacle placement
│   └── MapDisplay.java          # Handles terminal visualization, borders, and legends
│
├── 📊 Analytics & Reporting
│   ├── AlgorithmResult.java     # Data model storing the outcome of a single pathfinding run
│   └── SaveResults.java         # Handles metric aggregation and timestamped CSV file exports
│
└── 🗑️ Deprecated / Legacy
    └── Functions.java           # Old heuristic distance calculations (maintained for backward compatibility)

---

📊 Benchmark Results (Empirical Data)

Based on our recent benchmark of 100 randomized test runs on a 50x50 grid (with 20-30% obstacle density), here is how the algorithms actually performed.

Algorithm	Success Rate	Avg Path Length	Avg Path Cost	Avg Nodes Expanded	Efficiency Ranking
Manhattan Distance	97.0%	36.13	35.13	155.53	🏆 1st (Best)
Euclidean Distance	97.0%	36.13	35.13	301.22	🥈 2nd
Chebyshev Distance	97.0%	36.13	35.13	338.64	🥉 3rd
Zero Heuristic (Dijkstra)	97.0%	36.13	35.13	862.47	🐢 4th (Slowest)

💡 Key Takeaways from the Data:

• Optimality is Guaranteed: As seen in the data, the Average Path Length and Average Path Cost are completely identical (36.13 and 35.13) across all algorithms. This proves that A* is an optimal algorithm; regardless of the heuristic, it will always find the shortest possible path.
• The Power of the Right Heuristic: Manhattan Distance is the undisputed champion for this simulation. Because the agent can only move in 4 directions (Up, Down, Left, Right), Manhattan perfectly models the true movement cost. It explored ~5.5x fewer nodes than the Zero Heuristic (Dijkstra's) and roughly half as many nodes as Euclidean distance.
• Dijkstra's is Exhaustive: Because the "Zero Heuristic" offers zero directional guidance, it expands almost every accessible node in a circle (averaging 862 nodes) until it stumbles upon the goal.
• Success Rate: The 97% success rate indicates that in 3 out of the 100 random map generation attempts, the randomized obstacles created an impossible map where the goal was walled off and unreachable.

---

✨ Key Features

• Procedural Map Generation: Automatically generates randomized grid maps with configurable dimensions, start/end points, and obstacle densities.
• Multiple Heuristics: Compares four distinct heuristic approaches: Zero (Dijkstra's), Manhattan, Euclidean, and Chebyshev distances.
• Custom Data Structures: Includes a highly optimized Min-Heap priority queue (OpenList) specifically built for rapid A* node evaluation.
• Rich Console Visualization: Beautifully renders the grid, complete with borders, coordinate axes, and a dynamic legend.
• Automated CSV Reporting: Aggregates data over multiple runs (default is 100) and exports both detailed run-by-run logs and averaged statistical summaries.

---

🚀 Getting Started (How to Run)

To run this application successfully, you will need Java 16 or higher installed on your system. This requirement is necessary because the application utilizes the modern Java record feature for statistical data aggregation.

1. Compile the Code

Open your terminal or command prompt, navigate to the directory containing your .java files, and compile them all at once:

javac *.java

2. Execute the Application

Once compiled, run the Main class to start the evaluation:

java Main

Upon execution, the application will begin generating maps, printing visual grids to your console, evaluating paths, and finally outputting the CSV reports into your current directory.

---

🛠️ How to Customize

Because of the clean architecture, tweaking the simulation is incredibly easy. Open Config.java and modify these constants to see different behaviors:

• Make the map massive: Change MAP_SIZE_X = 50; and MAP_SIZE_Y = 50; to 200.
• Increase the difficulty: Adjust OBSTACLE_RATE_MIN = 20.0; and OBSTACLE_RATE_MAX = 30.0; to 40.0 and 45.0 to create dense, maze-like environments.
• Run a larger sample size: Change TOTAL_RUNS = 100; to 1000 to gather more statistically significant data in your CSV exports.