🗺️ Grid Pathfinder

Recursive algorithm for computing shortest paths in two-dimensional grids with obstacles.

Project for the Algorithms and Data Structures course (academic year 2024–25).

Description

The project is composed of 3 main components:

1. Grid Generator — Configurable with different types of obstacles: simple, clustered, diagonal, boundary, bar-shaped, etc.

2. CAMMINOMIN Algorithm — Given a grid and two traversable cells (source and destination), it computes a shortest path (if one exists), returning the sequence of landmarks and its length.

3. ExperimentationSystem — Given a grid, it evaluates correctness and time/space performance after multiple algorithm invocations.

How It Works

The algorithm uses:

• Free paths of type 1 and 2
• Construction of context, complement, and boundaries
• A recursive approach to efficiently explore the grid

Features

• Random or semi-random generation of customizable grids
• Computation of the shortest path and its representation as a sequence of moves
• Analysis of free distance (dlib) between cells
• Performance experimentation based on configurable parameters

Requirements

• Language: Java
• File-based input/output
• Focus on code reuse and maintainability

Project Structure

grid-pathfinder/
├── grid-pathfinder/    # Java implementation
│   ├── bin            # Compiled files
│   ├── src            # Source code
│   ├── Grids          # Pre-generated grids ready to use
├── Elaborato/         # Project specification
├── Relazione/         
│   ├── Relazione      # Final report
│   ├── use cases      # Generated grids with all executed test cases
└── README.md

License

MIT License — See LICENSE for details.