Please enable JavaScript.
Coggle requires JavaScript to display documents.
Pathfinding Algorithms - Coggle Diagram
Pathfinding Algorithms
Recap
State Space
Search Tree
Node = State
Expand state if not a goal
Branch = Action
Infrastructure of Search Algorithm
Data Structures
Lookup Table
Queue
Node Components
State
Parent
Action
Path Cost
The Frontier
Node Types
Child Node
Leaf Node
Parent Node
Sets
Leaf nodes = Frontier (open list)
Warnings
Avoid loopy paths
Maintain an explored set
Measuring Performance
Metrics
Completeness
Optimality
Time Complexity
Space Complexity
Uninformed Search (Blind)
Types
Uniform Cost
Depth-First
Depth-Limited
Iterative Deepening Depth-First
Bidirectional
Breadth-First
Informed Search (Uses Heuristic)
Heuristics
g(n): Path cost from start to n
h(n): Estimated cost from n to goal
f(n) = g(n) + h(n)
Dijkstra’s Algorithm
Edge relaxation
Shortest path in weighted graphs
Types
Greedy Best First Search
A*
Best First Search
Heuristics
Number of misplaced tiles
Manhattan distance
8-puzzle
Genetic Algorithms
Process
Measure fitness
Select parents
Crossover and mutation
Evaluate offspring
Pathfinding in Games
Applications
Efficient and optimal networks
Examples and tutorials
Implementation links
Slime Mould
Properties
Simple organism
Forms spore cases
Applications
Optimal networks
Links to research and tutorials