A* (pronounced "A-star") is a graph traversal and path search algorithm, which is often used in many fields of computer science due to its completeness, optimality, and optimal efficiency. One major practical drawback is its O(b^d) space complexity, as it stores all generated nodes in memory. Thus, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, as well as memory-bounded approaches; however, A* is still the best solution in many cases.
Topic
A* Search Algorithm
This topic includes the following resources and journeys:
Filters
Type
Experience
Scope
4 items
Autonomous Navigation, Part 4: Path Planning with A* and RRT
18 min
Beginner
Video
Theory
This video explores some of the ways that we can use a map like a binary occupancy grid for motion and path planning. We briefly cover what motion planning means and how we can use a graph...
See More
Pathfinding with A*
60 min
Beginner
Article / Blog
Application
An interactive visual explanation of the A* pathfinding algorithm. This resource uses motivating examples from computer games.
See More
A* Pathfinding (E01: algorithm explanation)
12 min
Beginner
Video
Theory
Welcome to the first part in a series teaching pathfinding for video games. In this episode we take a look at the A* algorithm and how it works.
See More
Introduction to the A* Algorithm
15 min
Beginner
Article / Blog
Application
An interactive visual explanation of the A* algorithm using motivating examples from computer games.
See More