Please enable JavaScript.
Coggle requires JavaScript to display documents.
Pathfinding Algorithms - Coggle Diagram
Pathfinding Algorithms
Search Basics
State space
Search tree (Node = state, Branch = action)
Frontier = unexplored leaf nodes
Explored Set = avoid loops (closed list)
Measuring Performance
Completeness (finds solution)
Optimality (lowest cost path)
Time complexity (how fast)
Space complexity (memory used)
Uninformed (Blind) Search
Breadth-First Search (BFS): FIFO, guarantees shortest path
Depth-First Search (DFS): LIFO, memory efficient
Uniform Cost Search: Expand node with lowest path cost
Depth-Limited Search: DFS with depth limit
Iterative Deepening DFS: Increases limit gradually
Bidirectional Search: Search from start and goal simultaneously
Informed (Heuristic) Search
Best First Search: Use heuristic to expand promising node
Greedy Best First Search: Quick but not always optimal
A* Search: f(n) = g(n) + h(n)
Optimal and complete
g(n): path cost so far
h(n): estimated cost to goal
Special Algorithms
Dijkstra’s Algorithm:
Shortest path in weighted graphs
No heuristic
Builds like BFS but considers edge weights
Heuristics
Manhattan Distance
Misplaced Tiles (for puzzles)
Good heuristics = faster, optimal search
Applications and Examples
Game pathfinding (grids, tower defense)
Transportation networks
Vacuum cleaner world
Slime mould modeling efficient networks