Please enable JavaScript.
Coggle requires JavaScript to display documents.
Pathfinding Algorithms, Pathfinding is the process of identifying the most…
Pathfinding Algorithms
What is Pathfinding?
Involves nodes, edges, states, cost
Used in navigation, robotics, games, logistics
Search Strategies
-
-
Optimal Search
- Always finds the shortest or least costly path
-
-
-
-
A (A-Star) Search*
→ f(n) = g(n) + h(n)
-
- h(n): estimated cost to goal
→ Uses heuristics like:
- Manhattan Distance: grid movement
- Euclidean Distance: straight line
- Diagonal Distance: 8-directional games
→ Example:
- A* is like a smart taxi driver who not only checks current traffic (g) but also knows a shortcut (h) to the destination.
“ 
”
-
Greedy Best-First Search
-
-
Very fast, but can miss better paths
→ Example:
- Like chasing a target based only on direction, even if a wall is in the way.
Real-World Applications
-
→ Video Game AI (NPCs, tower defense)
-
-
-
-
Performance Metrics
-
-
-
-
→ Example:
- BFS is complete and optimal, but uses lots of memory.
- DFS is fast but not guaranteed to be optimal.
-
- Pathfinding is the process of identifying the most efficient route from a start point to a goal within a mapped environment, using algorithms that avoid obstacles and reduce time or cost.
-
- Follows one path deeply until it hits a dead-end, then backtracks and tries another. Not guaranteed to find the shortest path.
- UCS always expands the node with the lowest total cost from the start, ignoring the goal’s position.
- Expands the node that appears closest to the goal based on heuristic alone.
- Every pathfinding algorithm is measured by its efficiency and effectiveness.