Please enable JavaScript.
Coggle requires JavaScript to display documents.
Pathfinding Algorithms - Coggle Diagram
Pathfinding Algorithms
Introduction
Definition
Pathfinding algorithms are techniques used to find the shortest or most efficient path between two points, often used in maps, games, and robotics.
Importance in AI
-
-
-
-
Game Development: Powers character movement, enemy chasing, and map exploration.
-
-
-
Search Tree Concepts
Branch = action, node = state
-
-
-
-
State Expansion
-
-
Key part of algorithms like BFS, DFS, A*.
-
-
-
-
-
Graph Search
Grid Representation
-
-
Edges connect adjacent cells (up, down, left, right — sometimes diagonals).
Useful for pathfinding, especially in games, robotics, and simulations.
-
-
-
Uninformed Search (Blind): Uninformed search strategies explore the search space without using any domain-specific knowledge.
-
-
Depth-First Search (DFS)
-
-
Memory efficient, but not guaranteed to find optimal solution.
-
-
Bidirectional Search
-
-
Highly efficient for large state spaces, reducing complexity from O(b^d) to O(b^(d/2)).
-
-
-
Informed Search (Uses Heuristic): These algorithms use heuristic functions to guide the search more efficiently toward the goal.
-
Greedy Best-First Search
-
-
Fast, but not always optimal or complete.
-
-
-
-
-
Genetic Algorithms: Based on the principles of natural selection and evolution to solve optimization problems.
-
-
-
-
Mutation
-
-
-
Usually applied with a low probability (e.g., 1-5%).
Applications
Pathfinding in Games
-
Common algorithms: A*, Dijkstra’s, Greedy Best-First.
-
-
-
