Cette leçon contient 11 diapositives, avec diapositives de texte.
Éléments de cette leçon
Welcome Week 9
Path Finding Algorithms
Module Lecturer: Dr Raghav Kovvuri
Email: raghav.kovvuri@ieg.ac.uk
Slide 1 - Diapositive
Scope
Scope of Today’s Session:
Introduction to Path Finding: Purpose and relevance.
A* Search Algorithm: Core concepts and implementation.
Real-world Applications: Examples and case studies.
Real-world Analogies:
GPS Navigation: Finding the shortest route.
Robotic Navigation: Navigating a warehouse.
Video Games: NPC pathfinding and decision-making.
Slide 2 - Diapositive
Path Finding Fundamentals
What is Path Finding?
Definition: Path finding is the process of determining an optimal route between points.
Connection to Search Algorithms:Builds upon search techniques, considering weights and heuristics for improved accuracy.
Key Applications:
Navigation Systems: Real-time route optimization.
Robotics and Automation: Efficient movement in constrained environments.
Gaming: Smooth NPC and character movement.
Analogy: Similar to how a GPS system calculates the best route by evaluating distance, time, and obstacles.
Slide 3 - Diapositive
Discussions (1)
Dijkstra Algorithm.
Greedy Best-First Search.
Submit to Canvas
timer
15:00
Slide 4 - Diapositive
A* Algorithm Fundamentals*
Key Components:
Open Set: Collection of nodes to be evaluated.
Closed Set: Nodes already evaluated.
Heuristic Function: Guides the search process.
Path Reconstruction: Retraces steps from goal to start to build the optimal path.
The A* algorithm is an informed search algorithm, meaning it leverages a heuristic function to guide its search towards the goal. This heuristic function estimates the cost of reaching the goal from a given node, allowing the algorithm to prioritize promising paths and avoid exploring unnecessary ones.
The A* algorithm is a powerful and widely used graph traversal and path finding algorithm. It finds the shortest path between a starting node and a goal node in a weighted graph.
Slide 5 - Diapositive
Implementing A* algorithm
Python Code Implementation:
This implementation sets up an A* algorithm using a priority queue for efficient node evaluation.
Download A_star.py
timer
10:00
Slide 6 - Diapositive
Understanding Heuristics
Selecting Heuristics:
Heuristics are essential for A* efficiency, influencing search direction.
Manhattan Distance: Suitable for grid-based maps without diagonal movement.
def manhattan_distance(p1, p2):
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
Euclidean Distance: Better for maps where diagonal movement is possible.
Wij gebruiken cookies om jouw gebruikerservaring te verbeteren en persoonlijke content aan te bieden. Door gebruik te maken van LessonUp ga je akkoord met ons cookiebeleid.