Pathfinding Algorithms: A*, Dijkstra, BFS Interactive Guide

Pathfinding algorithms are crucial for navigation systems, game AI, robotics, and many other applications. This guide explores the most important pathfinding algorithms, walking through how each one finds a path from start to goal on a grid.

Introduction to Pathfinding

Pathfinding is the process of finding a route between two points while avoiding obstacles. It's everywhere:

• GPS Navigation: Finding the fastest route to your destination
• Game AI: NPCs navigating game worlds
• Robotics: Autonomous vehicles avoiding obstacles
• Network Routing: Data packets finding paths through networks
• Logistics: Optimizing delivery routes

Grid-Based Pathfinding

Most pathfinding problems can be modeled on a grid where:

• Cells represent locations
• Obstacles are impassable cells
• Movement is typically to adjacent cells (4 or 8 directions)
• Cost may vary between different terrain types

Optimal Pathfinding Algorithms

A* (A-Star) Algorithm

A* is the gold standard for pathfinding, combining the best aspects of Dijkstra's algorithm with heuristic guidance.

Key Concepts:

f(n) = g(n) + h(n)

• g(n): Actual cost from start to node n
• h(n): Heuristic estimate from node n to goal
• f(n): Total estimated cost of path through n

Algorithm Steps:

1. Add start node to open set with f(start) = h(start)
2. While open set is not empty:
   • Select node with lowest f(n) value
   • If it's the goal, reconstruct path
   • Move node to closed set
   • For each neighbor:
     • Calculate tentative g(neighbor)
     • If better path found, update and add to open set

Heuristic Functions:

• Manhattan Distance: |x₁-x₂| + |y₁-y₂| (4-directional movement)
• Euclidean Distance: √[(x₁-x₂)² + (y₁-y₂)²] (any direction)
• Chebyshev Distance: max(|x₁-x₂|, |y₁-y₂|) (8-directional movement)

Properties:

• Optimal: Finds shortest path if heuristic is admissible
• Complete: Always finds a path if one exists
• Efficient: Uses heuristic to guide search toward goal

Applications:

• Game AI: Real-time strategy games, RPGs
• Robotics: Mobile robot navigation
• GPS Systems: Route planning with traffic data
• Puzzle Solving: 15-puzzle, sliding puzzles

Dijkstra's Algorithm (Grid Version)

Dijkstra's algorithm guarantees the shortest path by exploring nodes in order of distance from start.

Key Characteristics:

• Optimal: Always finds shortest path
• Uniform Exploration: Expands in all directions equally
• No Heuristic: Doesn't use goal information
• Guaranteed: Works with any non-negative edge weights

When to Use Dijkstra:

• Multiple Goals: Finding shortest path to any of several targets
• Unknown Goal: Goal location changes dynamically
• Weighted Terrain: Different movement costs for different terrain
• Preprocessing: Computing distances to all reachable cells

Comparison with A:*

• Dijkstra: Explores more nodes but guarantees optimality
• A*: More efficient but requires good heuristic

Uninformed Search Algorithms

Breadth-First Search (BFS)

BFS explores the grid level by level, guaranteeing the shortest path in unweighted grids.

Key Characteristics:

• Optimal: For unweighted grids (all moves cost 1)
• Complete: Always finds path if one exists
• Memory Intensive: Stores all nodes at current level
• Systematic: Explores all possibilities at each distance

Algorithm Steps:

1. Add start node to queue
2. While queue is not empty:
   • Dequeue front node
   • If it's the goal, reconstruct path
   • Add all unvisited neighbors to queue
   • Mark neighbors as visited

Applications:

• Maze Solving: Simple maze navigation
• Flood Fill: Image processing, paint bucket tool
• Connected Components: Finding all reachable areas
• Shortest Path: In unweighted scenarios

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking.

Key Characteristics:

• Not Optimal: May find longer paths
• Memory Efficient: Uses less memory than BFS
• Fast: Can find paths quickly if lucky
• Unpredictable: Path quality depends on exploration order

When to Use DFS:

• Any Path: When any path is acceptable
• Memory Constraints: Limited memory environments
• Maze Generation: Creating random mazes
• Puzzle Solving: When solution existence matters more than optimality

Heuristic Search Algorithms

Greedy Best-First Search

Uses only the heuristic to guide search, always moving toward the goal.

Key Characteristics:

• Fast: Often finds paths quickly
• Not Optimal: May find suboptimal paths
• Heuristic-Driven: Always moves toward goal
• Can Get Stuck: May fail in complex environments

Algorithm:

• Always expand the node closest to the goal (by heuristic)
• No consideration of actual distance traveled
• Can be trapped by local minima

Use Cases:

• Real-time Applications: When speed is more important than optimality
• Approximate Solutions: When "good enough" paths are acceptable
• Resource-Constrained: Limited computational resources

Algorithm Comparison

Algorithm	Optimal	Complete	Time Complexity	Space Complexity	Use Case
A*	Yes*	Yes	O(b^d)	O(b^d)	General pathfinding
Dijkstra	Yes	Yes	O(V²)	O(V)	Multiple goals, weighted
BFS	Yes**	Yes	O(b^d)	O(b^d)	Unweighted grids
DFS	No	Yes***	O(b^m)	O(bm)	Any path, memory limited
Greedy	No	No	O(b^m)	O(b^m)	Fast approximate paths

*With admissible heuristic
**For unweighted graphs
***For finite graphs

Advanced Pathfinding Concepts

Heuristic Design

Admissible Heuristics:

• Never overestimate the actual cost
• Guarantee optimal solutions with A*
• Examples: Manhattan, Euclidean distance

Consistent Heuristics:

• h(n) ≤ cost(n,n') + h(n') for all neighbors n'
• Stronger condition than admissible
• Ensures optimal behavior

Heuristic Quality:

• Too Low: More exploration, slower but optimal
• Too High: Faster but may miss optimal path
• Perfect: Exact remaining cost (rarely possible)

Optimization Techniques

Jump Point Search (JPS):

• Optimization of A* for uniform grids
• Skips unnecessary nodes
• Maintains optimality with significant speedup

Hierarchical Pathfinding:

• Multi-level approach for large maps
• High-level planning + local refinement
• Used in strategy games and large environments

Precomputed Paths:

• Store shortest paths between key points
• Fast lookup for common routes
• Memory vs. computation tradeoff

Dynamic Pathfinding

Moving Obstacles:

• Replan when environment changes
• Incremental replanning algorithms
• D* and D* Lite algorithms

Moving Goals:

• Target changes during pathfinding
• Adaptive algorithms
• Real-time strategy considerations

Real-World Applications

Game Development

Real-Time Strategy (RTS):

• Unit movement and formation
• Resource gathering optimization
• Combat positioning

Role-Playing Games (RPG):

• NPC navigation
• Quest routing
• World exploration

First-Person Shooters:

• AI bot movement
• Cover finding
• Flanking maneuvers

Robotics

Autonomous Vehicles:

• Route planning with traffic
• Obstacle avoidance
• Parking assistance

Warehouse Automation:

• Robot navigation in warehouses
• Collision avoidance
• Optimal picking routes

Drones:

• Flight path planning
• No-fly zone avoidance
• Energy-efficient routing

Navigation Systems

GPS Applications:

• Turn-by-turn directions
• Traffic-aware routing
• Multi-modal transportation

Indoor Navigation:

• Shopping mall guidance
• Hospital wayfinding
• Emergency evacuation

Network Routing

Internet Protocols:

• Packet routing
• Load balancing
• Fault tolerance

Telecommunications:

• Call routing
• Network optimization
• Bandwidth allocation

Implementation Considerations

Performance Optimization

Data Structures:

• Priority Queue: Binary heap for A* open set
• Hash Set: Fast closed set lookups
• Grid Representation: Efficient memory layout

Memory Management:

• Node Pooling: Reuse node objects
• Lazy Evaluation: Compute values when needed
• Compression: Compact grid representation

Algorithmic Improvements:

• Early Termination: Stop when goal is reached
• Bidirectional Search: Search from both ends
• Beam Search: Limit search width

Handling Special Cases

No Path Exists:

• Detect unreachable goals
• Provide alternative suggestions
• Graceful failure handling

Multiple Paths:

• Tie-breaking strategies
• Path diversity
• Alternative route suggestions

Dynamic Environments:

• Incremental replanning
• Path smoothing
• Obstacle prediction

Practical Considerations

Grid Resolution:

• Fine Grid: More accurate but slower
• Coarse Grid: Faster but less precise
• Adaptive: Variable resolution

Movement Models:

• 4-Directional: Cardinal directions only
• 8-Directional: Include diagonals
• Any-Angle: Smooth paths

Path Post-Processing:

• Smoothing: Remove unnecessary waypoints
• String Pulling: Direct line-of-sight optimization
• Spline Fitting: Smooth curves

Interactive Exercises

Try these experiments with the visualizations:

1. Algorithm Comparison: Run different algorithms on the same map
2. Obstacle Placement: See how obstacles affect path finding
3. Start/Goal Positions: Try different start and end points
4. Map Complexity: Compare performance on simple vs complex maps

Advanced Topics

Multi-Agent Pathfinding

Cooperative Pathfinding:

• Multiple agents avoiding each other
• Centralized vs. distributed approaches
• Conflict resolution strategies

Formation Movement:

• Groups moving together
• Maintaining formations
• Leader-follower dynamics

3D Pathfinding

Volumetric Navigation:

• 3D grids and octrees
• Flying vehicles and drones
• Underwater navigation

Multi-Level Environments:

• Buildings with multiple floors
• Elevators and stairs
• Vertical movement costs

Machine Learning Integration

Learned Heuristics:

• Neural networks for heuristic functions
• Reinforcement learning for pathfinding
• Adaptive algorithms

Pattern Recognition:

• Learning from successful paths
• Environment classification
• Predictive pathfinding

Conclusion

Pathfinding algorithms are fundamental tools for navigation and AI. Key insights:

• A is the gold standard* for most pathfinding applications
• Choose algorithms based on requirements: optimality vs. speed
• Heuristics are crucial for efficient pathfinding
• Consider the environment: static vs. dynamic, 2D vs. 3D
• Optimization matters for real-time applications

Following how these algorithms explore space and make decisions builds intuition for applying them to real problems.

Further Reading

• Amit's A* Pages
• Red Blob Games - Pathfinding
• AI Game Programming Wisdom
• Artificial Intelligence: A Modern Approach

---

Explore more algorithms: Graph Algorithms Visualization and Sorting Algorithms.