Please enable JavaScript.
Coggle requires JavaScript to display documents.
Pathfinding Algorithms - Coggle Diagram
Pathfinding Algorithms
Basics
State Space
Search Tree
Node = State
Branch = Action
The Frontier
Parent Node
Child Node
Leaf Node
Open List (Frontier)
Key Concepts
Warnings
Maintain Explored Set (Closed List)
Avoid Loopy Paths
Infrastructure
Node Attributes
State (Current Position)
Parent (Origin)
Action (Possible Moves)
Path Cost (Cumulative Cost)
Queue / Lookup Table
Performance Metrics
Completeness (Solution Guaranteed)
Optimality (Efficient Path)
Time Complexity (Execution Duration)
Space Complexity (Memory Usage)
Search Strategies
Uninformed Search (Blind)
Breadth-First Search (BFS)
FIFO Queue
Challenges with Memory
Uniform Cost Search
Lowest Path Cost Priority
Depth-First Search (DFS)
LIFO Stack
Backtracking
Depth Limited Search
Fixed Depth Limit
Iterative Deepening DFS
Incremental Depth Expansion
Bidirectional Search
Simultaneous Two-Way Search
Informed Search (Heuristic)
Best First Search
Evaluation Function ( f(n) )
Greedy Best First Search
Heuristic Only ( f(n) = h(n) )
A* Search
Combined Cost Function ( f(n) = g(n) + h(n) )
Advanced Algorithms
Dijkstra’s Algorithm
Shortest Path in Weighted Graphs
Edge Relaxation for Optimal Path
Heuristics
8 Puzzle Example
Misplaced Tiles ( h1 )
Manhattan Distance ( h2 )
Genetic Algorithms
Fitness Measurement
Probability-Based Selection
DNA Swapping for Offspring
Random Mutation
Applications
Organic Computing
Slime Mould as Computing Model
Network Efficiency
Pathfinding in Games
Grid-Based Strategies
Tower Defense Pathfinding
Resources
A Tutorial Links*
Introduction to A*
Game Programming Patterns
Path Finding Tutorials
Code Examples
Vacuum Cleaner World (C++)
A* Algorithm Implementation (C++)
Comparative Analysis
Algorithm Comparisons
A* vs. Dijkstra
BFS vs. DFS
Concurrent Algorithms