Skip to content

README.md

Latest commit

 

History

History
157 lines (119 loc) · 5.15 KB

README.md

File metadata and controls

157 lines (119 loc) · 5.15 KB

Dijkstra Pathfinding Visualizer

An interactive educational tool that visualizes Dijkstra's shortest path algorithm in real-time using Python and Pygame.

Python Version Pygame License

Overview

This application provides an intuitive, visual way to understand how Dijkstra's 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 ultimately discovers the shortest route.

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 explored)
  • 🔴 Red: Closed nodes (already evaluated)
  • 🟣 Purple: Final shortest path

User Controls

  • Set Start: Define the starting position for pathfinding
  • Set End: Define the destination point
  • Draw Walls: Create obstacles to navigate around
  • Run Dijkstra: Execute the pathfinding algorithm with visualization
  • Reset: Clear the entire grid and start fresh
  • Right-Click: Remove any placed element (walls, start, or end nodes)

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/Dijkstra-pathfinding-algo.git
cd Dijkstra-pathfinding-algo

  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 - Click "Set Start" button, then click on any grid cell
  3. Place the end node - Click "Set End" button, then click on another grid cell
  4. Draw obstacles - Click "Draw Walls" button, then click and drag across cells to create barriers
  5. Run the algorithm - Click "Run Dijkstra" or press SPACEBAR to start visualization
  6. Reset if needed - Click "Reset" or press C to clear the grid

Controls

Mouse Controls

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

Keyboard Shortcuts

Key Action
SPACEBAR Run Dijkstra's algorithm
C Clear/Reset the grid

How It Works

Dijkstra's Algorithm

Dijkstra's algorithm is a graph search algorithm that finds the shortest path between nodes in a graph. This implementation uses:

  1. Priority Queue: Explores nodes in order of their distance from the start
  2. Distance Tracking: Maintains the shortest known distance to each node
  3. Backtracking: Reconstructs the path once the target is reached

Visualization Process

  1. Green nodes: Represent the "frontier" - nodes currently being considered
  2. Red nodes: Show explored territory - nodes already evaluated
  3. Purple path: The final shortest path from start to finish

Project Structure

Dijkstra-pathfinding-algo/
│
├── main.py              # Main application file
├── README.md            # Project documentation
└── requirements.txt     # Python dependencies

Technical Details

Grid System

  • Grid-based pathfinding on a 2D plane
  • Configurable grid size and cell dimensions
  • Supports obstacle placement for complex pathfinding scenarios

Algorithm Implementation

  • Efficient priority queue implementation for node selection
  • Distance calculation using grid-based coordinates
  • Path reconstruction using parent node tracking

Educational Value

This visualizer is perfect for:

  • Computer Science Students: Understanding graph algorithms visually
  • Algorithm Enthusiasts: Exploring pathfinding behavior with different obstacle configurations
  • Teachers: Demonstrating shortest path algorithms in an engaging way
  • Developers: Learning algorithm implementation and visualization techniques

Requirements

pygame>=2.0.0

Future Enhancements

Potential improvements for future versions:

  • Additional pathfinding algorithms (A*, BFS, DFS)
  • Diagonal movement options
  • Variable terrain costs/weights
  • Save/Load maze configurations
  • Speed control for visualization
  • Step-by-step mode
  • Performance metrics display

Screenshots

Add screenshots of your application here to showcase: alt text alt text alt text alt text

Note: This is an educational tool designed to help visualize and understand pathfinding algorithms. It is not optimized for production pathfinding systems.