Please enable JavaScript.
Coggle requires JavaScript to display documents.
Pathfinding Algorithms - Coggle Diagram
Pathfinding Algorithms
Search Concepts
State Space
Search Tree
Node = State
Branch = Action
Frontier (Open List)
Explored Set (Closed List)
Search Infrastructure
Node Information
Parent (Previous)
Action (Next)
State (Current)
Path Cost
Data Structures
Queue
Lookup Tables
Measuring Performance
Completeness
Optimality
Time Complexity
Space Complexity
Uninformed Search Algorithms
Depth-First Search (DFS)
Explores as deep as possible before backtracking
May not find optimal path
More memory efficient than BFS
Uniform Cost Search
Explores based on lowest total path cost
Works well with weighted graphs
Slower if path costs are similar
Breadth-First Search (BFS)
Explores nodes level by level
Guarantees shortest path in unweighted graphs
High memory usage
Informed Search Algorithms
A* (A-Star) Algorithm
Combines:
h(n) = heuristic estimate to goal
g(n) = cost from start to current node
f(n) = g(n) + h(n)
Finds optimal path efficiently
Greedy Best-First Search
Uses only the heuristic h(n)
Fast, but may not find optimal path
Can get stuck in loops
Dijkstra's Algorithm
Shortest Path in Weighted Graph
Edge Relaxation
Builds on BFS + Cost Evaluation
Heuristics (for Informed Search)
Helps estimate distance to goal
Common heuristics:
Manhattan Distance – for grid-based maps
Euclidean Distance – straight-line distance
Diagonal Distance – for 8-directional movement
Applications
Robot navigation
Maze solving
NPC pathing in games
Route planning (e.g., Google Maps)
Logistics and delivery optimization
References
https://www.redblobgames.com/pathfinding/a-star/introduction.html
https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/
https://www.graphable.ai/blog/pathfinding-algorithms/
https://medium.com/omarelgabrys-blog/path-finding-algorithms-f65a8902eb40