Pathfinding Algorithms: A* and Uniform Cost Search (UCS)

A complete, Java-based console application that visualizes and compares pathfinding algorithms on a randomized grid. The project generates a labyrinth with varying terrain heights and obstacles, then finds the optimal cost-effective path from a starting position to one of two potential goals using Uniform Cost Search (UCS) and A* (A-Star).

---

Table of Contents

1. Features
2. Algorithms Explained
3. Getting Started
4. Usage & Example
5. Project Structure & Source Code

---

Features

• Randomized Labyrinth Generation: Creates a grid of customizable size with random obstacles (blocked cells) and terrain heights (values 1-4).
• Dynamic Movement Costs: Moving between cells incurs a cost based on height differences and whether the movement is straight or diagonal.
• Multiple Goals: Supports calculating the optimal path to either Goal 1 (G1) or Goal 2 (G2), whichever is cheaper.
• Algorithm Comparison: Runs both UCS and A* sequentially to allow for comparison of node expansion and execution efficiency.

---

Algorithms Explained

• Uniform Cost Search (UCS): Explores paths iteratively by choosing the node with the lowest path cost from the start ($g(n)$). It guarantees the optimal (shortest) path but expands equally in all directions, making it slower.
• A Search Algorithm:* Combines the actual cost from the start ($g(n)$) with an estimated cost to the goal ($h(n)$). This evaluation function $f(n) = g(n) + h(n)$ directs the search towards the goals, resulting in a highly optimized execution that expands far fewer nodes while still guaranteeing an optimal path.

---

Getting Started

Prerequisites

• Java Development Kit (JDK) 8 or higher installed on your machine.

Compilation

Open your terminal, navigate to the project directory, and compile all Java files:

javac *.java

Project Structure & Source Code

This repository consists of 7 core Java classes along with detailed project documentation. Below is the complete file structure:

├── A_Star.java                 # A* Algorithm implementation
├── EnglishReport.pdf           # Project documentation and analysis (English)
├── GreekReport.pdf             # Project documentation and analysis (Greek)
├── Heuristic.java              # Heuristic function logic for A*
├── Labyrinth.java              # Grid environment generation
├── Movement.java               # Traversal cost calculations
├── Node.java                   # State representation for pathfinding
├── Project.java                # Main entry point and execution setup
├── README.md                   # Project overview and instructions
└── UniformCostSearch.java      # UCS Algorithm implementation

Usage & Example

...

Example Console Output

Give array size
5
arraysize is: 5
{2} ,{1} ,{---} ,{3} ,{4} ,
{1} ,{3} ,{2} ,{2} ,{1} ,
...
Enter Coordinates for S
0 0
Enter Position for G1
4 4
Enter Position for G2
0 4
...
algorithm is: UCS
The algorithm expanded on: (0,0) (1,0) (0,1) ...
Path = S:(0,0) , (1,1) , (2,2) , (3,3) , (4,4):G1
Cost of Path = 4.5

algorithm is: A*
The algorithm expanded on: (0,0) (1,1) (2,2) ...
Path = S:(0,0) , (1,1) , (2,2) , (3,3) , (4,4):G1
Cost of Path = 4.5