A* Algorithm
A* is an informed search algorithm that finds the shortest path using both the actual distance from the start and an estimated distance to the goal (heuristic). It's optimal and efficient for pathfinding in games and robotics.
A* Algorithm Visualization
How to use the A* Visualizer1️⃣ Click Origin and select the start cell.
2️⃣ Click Destiny and select the goal cell.
3️⃣ Select Obstacle to draw walls.
4️⃣ Press Init to initialize the algorithm.
5️⃣ Use Step to run step-by-step or Run for automatic execution.
6️⃣ Adjust the speed slider to control animation speed.
2️⃣ Click Destiny and select the goal cell.
3️⃣ Select Obstacle to draw walls.
4️⃣ Press Init to initialize the algorithm.
5️⃣ Use Step to run step-by-step or Run for automatic execution.
6️⃣ Adjust the speed slider to control animation speed.
OPEN
CLOSED
Complexity
Time Complexity:
O(b^d)Space Complexity:
O(b^d)Pseudocode
function AStar(start, goal):
openSet = {start}
gScore = {start: 0}
fScore = {start: heuristic(start, goal)}
while openSet is not empty:
current = node with lowest fScore
if current == goal:
return reconstruct_path(cameFrom, current)
for each neighbor:
tentative_g = gScore[current] + distance(current, neighbor)
if tentative_g < gScore[neighbor]:
cameFrom[neighbor] = current
gScore[neighbor] = tentative_g
fScore[neighbor] = gScore[neighbor] + heuristic(neighbor, goal)Related Algorithms
Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a priority queue and is widely used in routing and network protocols.
Time: O((V + E) log V) | Space: O(V)
Breadth-First Search
Breadth-First Search (BFS) is a graph traversal algorithm that explores all vertices at the current depth level before moving to vertices at the next depth level. It uses a queue data structure and is useful for finding shortest paths in unweighted graphs.
Time: O(V + E) | Space: O(V)