System Overview

A* pathfinding finds optimal paths by combining actual cost (g) with heuristic estimate (h). It explores promising nodes first, balancing between Dijkstra's completeness and greedy best-first's speed. The visualization shows open set (green), closed set (red), and the final path.

Step-by-step mode reveals the algorithm's decision-making: which nodes it considers, which it explores, and how it builds the path incrementally. This makes the search process transparent.

Why Games Use This

• AI Navigation: Enemies and NPCs find paths to targets
• Player Guidance: Show waypoints and routes
• Procedural Levels: Ensure all areas are reachable
• Dynamic Obstacles: Recalculate when environment changes
• Hierarchical Pathfinding: Use at multiple scales

Key Parameters

• Heuristic Weight: 1.0 = optimal, >1.0 = faster but suboptimal
• Obstacle Density: Affects path complexity and search time
• Step-by-Step: Control algorithm progression manually
• Cost Function: Uniform vs terrain-based costs

Failure Modes

• No path exists: Goal unreachable, algorithm exhausts search
• Poor heuristic: Overestimates cause suboptimal paths
• High obstacle density: Many dead ends slow search
• Dynamic obstacles: Path becomes invalid during execution
• Performance: Large grids with many obstacles are expensive

Scaling Behavior

A* is O(b^d) worst case where b is branching factor and d is depth. In practice, good heuristics dramatically reduce explored nodes. For large maps, use hierarchical pathfinding or jump point search.

Memory is O(n) for storing open/closed sets. Use efficient data structures (binary heap) for open set.

Related Algorithms

• Dijkstra: Explores uniformly, guaranteed optimal
• Greedy Best-First: Uses only heuristic, fast but suboptimal
• Jump Point Search: Optimized for uniform-cost grids
• Theta*: Allows diagonal movement through obstacles
• Flow Fields: Pre-computed vector fields for many agents

Free Tools & Libraries

• pathfinding.js: JavaScript pathfinding library
• NavMesh: Navigation mesh generation and pathfinding

System-Thinking Prompts

• What happens with no path? How does algorithm handle unreachable goals?
• Where does A* break? Poor heuristics, dynamic obstacles?
• How could players exploit pathfinding? Predictable routes?
• Which parameter dominates? Heuristic weight or obstacle density?
• What's the optimal heuristic weight? Speed vs optimality tradeoff?
• How do obstacles affect performance? Sparse vs dense grids?
• Can we guarantee optimal paths? Or is approximate acceptable?