A* Algorithm
The cover image was generated by ChatGPT.
Introduction
A* Algorithm, also known as the A* Search Algorithm, is one of the most commonly used path planning algorithms in various games and artificial intelligence applications. It combines the global optimality of Dijkstra’s Algorithm with the heuristic strategy of the Greedy Algorithm, making A* both efficient and accurate, hence its widespread popularity. A* is also widely applied in fields such as robot navigation, map pathfinding, and many others.
How It Works
The evaluation function of the A* algorithm can be expressed as:
$$ f(n) = g(n) + h(n), $$
where $n$ represents the current location, $g(n)$ is the actual cost from the start point to $n$, and $h(n)$ is the estimated cost from $n$ to the goal.
From this evaluation function, we can observe the following:
- When $g(n) = 0$, the A* algorithm becomes $f(n) = h(n)$, which means only the distance to the goal is considered. This is equivalent to the Greedy Algorithm.
- When $h(n) = 0$, the A* algorithm becomes $f(n) = g(n)$, which means only the shortest path from the start is considered. This is equivalent to Dijkstra’s Algorithm.
- If $h(n)$ is less than the actual distance from $n$ to the goal, the algorithm is guaranteed to find the optimal solution, but it may need to explore more nodes, reducing efficiency.
- If $h(n)$ is equal to the actual distance from $n$ to the goal, the algorithm will find the best path and do so efficiently.
- If $h(n)$ is greater than the actual distance from $n$ to the goal, the algorithm may no longer guarantee the optimal solution, but it will compute very quickly.
Below is a simple example.
As shown in the image above, suppose we have six locations labeled $A$, $B$, $C$, $D$, $E$, and $F$. Let $A$ be the starting point and $F$ the goal, and we aim to find a path from $A$ to $F$.
First, we calculate the distances between each path using the Manhattan distance, as shown below.
To find the optimal path starting from point $A$, we will build a table to record the previous node and the evaluation function during the pathfinding process. All initial $f(n)$ values are assumed to be $\infty$ by default.
| Node | Marked | $g(n)$ | $h(n)$ | $f(n)$ | Previous Node |
|---|---|---|---|---|---|
| A | $\infty$ | ||||
| B | $\infty$ | ||||
| C | $\infty$ | ||||
| D | $\infty$ | ||||
| E | $\infty$ | ||||
| F | $\infty$ |
Since the starting point is $A$, we begin by marking point $A$ and calculating the corresponding evaluation function. Here, $g(n)$ represents the actual cost from the starting point to each node along the paths, and $h(n)$ represents the Manhattan distance from each node directly to the goal.
| Node | Marked | $g(n)$ | $h(n)$ | $f(n)$ | Previous Node |
|---|---|---|---|---|---|
| A | ✓ | 0 | 19 | 19 | |
| B | $\infty$ | ||||
| C | $\infty$ | ||||
| D | $\infty$ | ||||
| E | $\infty$ | ||||
| F | $\infty$ |
Next, examine the locations adjacent to $A$ that are unmarked, and calculate their evaluation functions.
| Node | Marked | $g(n)$ | $h(n)$ | $f(n)$ | Previous Node |
|---|---|---|---|---|---|
| A | ✓ | 0 | 19 | 19 | |
| B | 4 | 15 | 19 | A | |
| C | 5 | 14 | 19 | A | |
| D | $\infty$ | ||||
| E | $\infty$ | ||||
| F | $\infty$ |
Compare the values of $f(n)$ and identify the smallest one. Since $B$ and $C$ have the same $f(n)$, we arbitrarily choose one of them to mark next.
| Node | Marked | $g(n)$ | $h(n)$ | $f(n)$ | Previous Node |
|---|---|---|---|---|---|
| A | ✓ | 0 | 19 | 19 | |
| B | ✓ | 4 | 15 | 19 | A |
| C | 5 | 14 | 19 | A | |
| D | $\infty$ | ||||
| E | $\infty$ | ||||
| F | $\infty$ |
Next, search for the unmarked locations adjacent to the marked point $B$, and calculate their evaluation functions.
| Node | Marked | $g(n)$ | $h(n)$ | $f(n)$ | Previous Node |
|---|---|---|---|---|---|
| A | ✓ | 0 | 19 | 19 | |
| B | ✓ | 4 | 15 | 19 | A |
| C | 5 | 14 | 19 | A | |
| D | 11 | 8 | 19 | B | |
| E | 13 | 6 | 19 | B | |
| F | $\infty$ |
Now, compare the values of $f(n)$ and identify the smallest one. Since $f(n)$ for $C$, $D$, and $E$ are all 19, we choose $C$ to mark next.
| Node | Marked | $g(n)$ | $h(n)$ | $f(n)$ | Previous Node |
|---|---|---|---|---|---|
| A | ✓ | 0 | 19 | 19 | |
| B | ✓ | 4 | 15 | 19 | A |
| C | ✓ | 5 | 14 | 19 | A |
| D | 11 | 8 | 19 | B | |
| E | 13 | 6 | 19 | B | |
| F | 19 | 0 | 19 | C |
Repeat the process of marking the optimal unmarked location and updating its neighboring nodes until all locations have been marked. The final result can be summarized in the following table.
| Node | Marked | $g(n)$ | $h(n)$ | $f(n)$ | Previous Node |
|---|---|---|---|---|---|
| A | ✓ | 0 | 19 | 19 | |
| B | ✓ | 4 | 15 | 19 | A |
| C | ✓ | 5 | 14 | 19 | A |
| D | ✓ | 11 | 8 | 19 | B |
| E | ✓ | 13 | 6 | 19 | B |
| F | ✓ | 19 | 0 | 19 | C |
From the above table, we can not only determine that the shortest path distance is 19, but also trace back the optimal path from the endpoint $F$ to the starting point $A$. From the table above, the optimal path is
$$ A \Rightarrow C \Rightarrow F $$
Of course, the function $h(n)$, which estimates the cost from location $n$ to the goal, does not necessarily have to be calculated using the Manhattan distance as in the path calculation above; other methods can be used as well. Similarly, the path lengths between locations can be calculated using other measures, such as the Euclidean distance. Using different calculation methods can yield different values for the function $f(n)$, allowing the result to be computed more efficiently.
Algorithm
Based on the above example, the steps of the A* algorithm can be roughly summarized as follows:
- Initialize the value of $f(n)$ to $\infty$.
- Select the unmarked location with the smallest $f(n)$.
- Mark that location.
- Calculate $g(n)$, $h(n)$, and $f(n)$ through that location.
- Return to step 2 and repeat until all locations have been marked.
Conclusion
The A* algorithm is a classic algorithm that combines the shortest path efficiency of Dijkstra’s algorithm with the efficiency advantages of the greedy algorithm. It is not only effectively applied in map navigation and route planning but is also commonly seen in scenarios such as maze problems, game character movement, and robot path design. The A* algorithm can assign different weights and preferences to paths based on actual needs, making the results better suited to the application context. For example, avoiding dangerous areas or preferring to walk on designated roads instead of through grass.
References
A*搜尋演算法. (June 4, 2025). Wikipedia, The Free Encyclopedia. Retrieved July 8, 2025, from https://zh.wikipedia.org/zh-tw/A*搜尋演算法
廢物敗類窩囊廢. (May 14, 2018). 【筆記】遊戲中常用的A*最佳路徑演算法. 巴哈姆特. Retrieved July 8, 2025, from https://home.gamer.com.tw/creationDetail.php?sn=3988541
小哈片刻. (September 30, 2022). Trick 27: 承先啟後的路徑搜尋－A*演算法. iT 邦幫忙. Retrieved July 8, 2025, from https://ithelp.ithome.com.tw/articles/10292260
阿祥的開發日常. (July 8, 2016). A* Algorithm Introduction – 演算法簡介. WordPress. Retrieved July 8, 2025, from https://tedsieblog.wordpress.com/2016/07/08/a-star-algorithm-introduction/
林家慶. (August 4, 2023). [遊戲引擎研究] A* 演算法實作 (迷宮搜尋路徑) - 2023/8/4 [Video]. Youtube. Retrieved July 8, 2025, from https://youtu.be/A7xLS75gTzY
小哈片刻. (December 9, 2021). 勇者逛地城的必備技能: (科普)A*演算法 [Video]. Youtube. Retrieved July 8, 2025, from https://youtu.be/_B8XV1iIvq8
