Completed

A* Pathfinding Visualization

Interactive visualization of the A* pathfinding algorithm with obstacle avoidance using visibility graphs

ReactTypeScriptCanvasAlgorithmsA*Pathfinding
Try It Live

Overview

An interactive web-based visualization of the A* pathfinding algorithm demonstrating how autonomous agents can navigate around obstacles to reach their goals. This tool combines visibility graphs with A* search to find optimal paths in 2D environments.

Features

Interactive Canvas

  • Wall Drawing: Click and drag to create rectangular obstacles
  • Node Placement: Set start (green) and goal (blue) nodes with a single click
  • Real-time Visualization: Watch the algorithm build the visibility graph and compute the path
  • Debug Log: Live updates showing algorithm progress and metrics

Algorithm Implementation

  • Visibility Graph Construction: Automatically generates nodes at obstacle corners and connects all mutually visible nodes
  • Line-of-Sight Checking: Precise collision detection ensures edges don't intersect obstacles
  • A* Search: Efficient pathfinding using Euclidean distance heuristic
  • Optimal Path: Always finds the shortest collision-free path if one exists

User Experience

  • Keyboard Controls: Intuitive shortcuts for quick mode switching (W, S, G, Enter, C)
  • Visual Feedback: Color-coded nodes and edges make the algorithm's behavior clear
  • Responsive Design: Works seamlessly on desktop and tablet devices
  • Dark Mode Support: Fully styled for both light and dark themes

Technical Details

Algorithm Phases

  1. Visibility Graph Construction

    • Creates nodes at each corner of every obstacle
    • Includes start and goal nodes
    • Connects all node pairs that have direct line-of-sight
    • Stores as adjacency list with edge weights (Euclidean distance)

  2. A* Pathfinding

    • Uses priority queue (frontier) to explore nodes
    • Heuristic function: h(n) = Euclidean distance to goal
    • Cost function: g(n) = actual distance from start
    • Evaluation function: f(n) = g(n) + h(n)
    • Reconstructs path by backtracking through parent pointers

Performance

  • Graph Construction: O(n²) where n = number of nodes
  • Pathfinding: O(e log n) where e = number of edges
  • Collision Detection: Efficient rectangle-line and line-line intersection tests

Technologies Used

  • React 19: Modern component architecture with hooks
  • TypeScript: Full type safety for algorithm logic
  • HTML5 Canvas: High-performance 2D rendering
  • Next.js 15: Server-side rendering and routing

Use Cases

This visualization is useful for:

  • Education: Teaching pathfinding and graph algorithms
  • Game Development: Prototyping AI navigation systems
  • Robotics: Planning collision-free paths for autonomous robots
  • Algorithm Visualization: Understanding A* vs Dijkstra vs BFS

Future Enhancements

Potential additions to explore:

  • Additional algorithms (Dijkstra, BFS, DFS, Jump Point Search)
  • Weighted terrain with variable movement costs
  • Dynamic obstacle movement
  • Path smoothing and optimization
  • Multiple agents with collision avoidance
  • Save/load functionality for complex maps

Project Origin

Originally implemented as a vanilla JavaScript demo, this project was migrated to React and TypeScript as part of a portfolio modernization effort. The core algorithm logic remains faithful to the original while taking advantage of modern React patterns and TypeScript's type safety.

Back to Projects