A* Pathfinding Visualizer

An interactive educational tool that visualizes the A* search algorithm in real-time using Python and Pygame.

Overview

This application provides an intuitive, visual way to understand how the A* (A-Star) algorithm explores a grid-based environment to find the optimal path between two points. Watch as the algorithm systematically evaluates nodes, navigates around obstacles, and discovers the shortest route using heuristics.

Features

Core Functionality

• Interactive Grid System: Click and drag to create custom maze layouts
• Visual Algorithm Execution: Real-time visualization of the pathfinding process
• Customizable Environment: Place start points, end points, and walls anywhere on the grid
• Path Highlighting: Clear visualization of the discovered shortest path

Visual Indicators

• 🟠 Orange: Start node
• 🔵 Turquoise: End/Target node
• ⬛ Black: Walls/Obstacles
• 🟢 Green: Open nodes (being considered)
• 🔴 Red: Closed nodes (already evaluated)
• 🟣 Purple: Final shortest path

User Controls

• Set Start: Define the starting position (First Left Click)
• Set End: Define the destination point (Second Left Click)
• Draw Walls: Create obstacles (Subsequent Left Clicks + Drag)
• Run A*: Execute the pathfinding algorithm (SPACEBAR)
• Reset: Clear the entire grid and start fresh (C)
• Right-Click: Remove any placed element

Installation

Prerequisites

• Python 3.7 or higher
• pip (Python package installer)

Setup Instructions

1. Clone or download this repository

   git clone https://github.com/harshil2424/A-star-pathfinding.git
   cd A-star-pathfinding

2. Install required dependencies

   pip install pygame

3. Run the application

   python main.py

Usage Guide

Basic Workflow

1. Launch the application - Run python main.py
2. Place the start node - Left click on any grid cell
3. Place the end node - Left click on another grid cell
4. Draw obstacles - Left click and drag to draw walls
5. Run the algorithm - Press SPACEBAR
6. Reset if needed - Press C

Controls

Mouse Controls

Action	Control
Place nodes/walls	Left Click
Remove items	Right Click
Drag to draw walls	Click + Drag

Keyboard Shortcuts

Key	Action
SPACEBAR	Run A* algorithm
C	Clear/Reset the grid

How It Works

A* Algorithm

A* is a smart graph search algorithm that finds the shortest path by combining actual cost from start ($g(n)$) and estimated cost to goal ($h(n)$).

Formula: $f(n) = g(n) + h(n)$

1. $g(n)$: Exact cost from start to node $n$.
2. $h(n)$: Heuristic estimated cost from $n$ to goal (Manhattan Distance).
3. $f(n)$: Total estimated cost of path through $n$.

Visualization Process

1. Green nodes: Nodes in the open set (candidates for exploration).
2. Red nodes: Nodes in the closed set (already evaluated).
3. Purple path: The reconstructed cheapest path.

Project Structure

A-star-pathfinding/
│
├── main.py              # Main entry point
├── settings.py          # Constants and configuration
├── node.py              # Node class definition
├── algorithm.py         # A* algorithm logic
├── README.md            # Project documentation
└── requirements.txt     # Dependencies

Future Enhancements

• Adjustable heuristics
• Diagonal movement
• Variable terrain weights