Pathfinding Benchmarks is an advanced algorithmic engineering laboratory designed to audit, stress-test, and optimize graph search strategies. Unlike standard visualizers that only show the shortest path, this system focuses on the computational economics of pathfinding: specifically, the trade-off between Time Complexity (CPU cycles) and Space Complexity (RAM usage).

Modern pathfinding faces two critical challenges which this project addresses:

Standard A (A-Star)* is optimally efficient in terms of nodes visited, but it is memory-hungry. On massive grids (game maps, logistics networks), it creates millions of object references, often leading to OutOfMemoryError. SMA (Simplified Memory-Bounded A)** solves this by fixing a hard memory limit and "pruning" the worst nodes when full. However, if the algorithm later needs those pruned nodes, it must regenerate them. This cycle of forgetting and relearning is called Thrashing. This suite provides the tooling to visualize exactly when and how Thrashing destroys performance.

Mathematical heuristics (Manhattan, Euclidean) are "blind" to terrain costs like mud, traffic, or walls until they touch them. This project implements a Hybrid AI Pipeline that:

1. Generates thousands of procedural maps with complex topologies.
2. Trains Python-based ML models (Linear Regression, Neural Networks) to predict path costs based on features like % Wall Density, % Traffic, and Grid Distance.
3. Injects these learned weights back into the Java engine, allowing the AI to "see" obstacles before exploring them, significantly reducing search space.

This project employs a polyglot architecture to leverage the best tools for each domain:

Component	Technology	Purpose
Core Engine		High-performance A* / SMA* implementation and benchmark runner.
ML Training		Scikit-Learn pipeline for training heuristic weights (ML.py).
Analytics		Responsive dashboard structure (index.html).
Visualization		Interactive charts for efficiency, memory usage, and thrashing.
Scripting		Automation of the build-run-analyze loop.

We treat algorithm performance data like financial analytics. The project includes a dedicated HTML5/JS dashboard that parses the raw CSV logs from the Java engine and visualizes Memory Thrashing, Heuristic Efficiency, and Time-Space Tradeoffs.

The following diagram illustrates the Hybrid AI Pipeline—how Java generation feeds Python training, which loops back into the Java runtime.

graph LR

    subgraph P1["Phase 1: Data Generation (Java)"]
        A[Map Generator] -->|1000+ Maps| B(Solved Maps)
        B -->|Extract Features| C[training_data.jsonl]
    end

    subgraph P2["Phase 2: Model Training (Python)"]
        C --> D[ML.py]
        D -->|Train Model| E{Best Model?}
        E -->|Export Weights| F[ml_weights.properties]
    end

    subgraph P3["Phase 3: Runtime Injection (Java)"]
        F -->|Load at Startup| G[MachineLearnedHeuristic.java]
        G -->|Predict Cost| H[A* / SMA* Engine]
        H -->|Output Logs| I[benchmark_results.csv]
    end

    I --> J[HTML5 Dashboard]

Follow these steps to set up the environment for both the Java Benchmark Engine and the Python ML Pipeline.

• Java JDK 11+: Required to compile and run the core engine.
  • Verify: java -version
• Python 3.8+: Required only if you intend to retrain the ML models.
  • Libraries: scikit-learn, numpy, pandas
• Git: To clone the repository.

1. Clone the Repository

   git clone https://github.com/amir-hossein-khodaei/ai-pathfinding-benchmarks.git
   cd ai-pathfinding-benchmarks

2. Compile the Java Engine The project uses a standard directory structure. You can compile it using javac:

   # Create build directory
   mkdir -p bin
   
   # Compile all sources
   javac -d bin -sourcepath src src/Main.java

3. Setup Python Environment (Optional for ML) If you plan to run the ML.py script:

   pip install scikit-learn numpy pandas

The application is driven by an interactive Command Line Interface (CLI).

To launch the main menu, run the compiled Java class:

java -cp bin Main

You will be presented with the Pathfinding Benchmark System v3.0 menu:

==========================================
    PATHFINDING BENCHMARK SYSTEM v3.0     
==========================================
Select Mode:
  [1] Standard Benchmark (A* vs SMA*)
  [2] Visualize Trace (Single Map Audit)
  [3] Generate Training Data (For Python)
  [4] Test Machine Learned Heuristic (Bonus)
  [0] Exit

If you want the AI to "learn" a new type of map topology:

1. Run Option [3] in the Java CLI to generate final_output/training_data.jsonl.

2. Run the Python training script:

   python ML.py

3. The script will output performance metrics (R² Score, RMSE) and save the new weights to:

   • ml_weights.properties (Linear Regression)
   • ml_weights_mlp.properties (Neural Network)
   • ml_weights_lasso.properties (Feature Selection)

4. Restart the Java application and choose Option [4] to test your new model!

After running a benchmark (Option 1 or 4), the results are saved to final_output/benchmark_results.csv.

1. Navigate to final_output/ in your file explorer.
2. Open index.html or ml_report.html in a modern web browser.
3. Note: If the charts do not load due to local CORS policy (browser security), use the "📂 Select Data.csv" button in the dashboard UI to manually load your generated CSV file.

This repository implements a wide range of heuristic strategies to test the limits of A* and SMA*.

• Core Engine: Robust A* and SMA* implementations.
• Visualizer: Interactive HTML5/JS Dashboard with Plotly.
• ML Integration: Python pipeline for Linear Regression & Neural Networks.
• Advanced Algorithms:
  • Bidirectional A*
  • IDA* (Iterative Deepening A*)
  • JPS (Jump Point Search)
• 3D Support: Moving from 2D grids to 3D voxel maps.
• Docker Support: Containerizing the Java/Python workflow.

See the open issues for a full list of proposed features.

Contributions are what make the open-source community such an amazing place to learn, inspire, and create. Any contributions you make are greatly appreciated.

1. Fork the Project
2. Create your Feature Branch (git checkout -b feature/AmazingFeature)
3. Commit your Changes (git commit -m 'Add some AmazingFeature')
4. Push to the Branch (git push origin feature/AmazingFeature)
5. Open a Pull Request

Distributed under the MIT License. See LICENSE for more information.

Amir Hossein Khodaei - GitHub Profile

Project Link: https://github.com/amir-hossein-khodaei/ai-pathfinding-benchmarks