参考：

• A* Pathfinding for Beginners 及其 翻译

The Search Area

Let’s assume that we have someone who wants to get from point A(green) to point B(red). Let’s assume that a wall(blue) separates the two points.

To simplify the search area, we have divided our search area into a square grid. This particular method reduces our search area to a simple two dimensional array. Each item in the array represents one of the squares on the grid (nodes), and its status is recorded as walkable or unwalkable.

Starting the Search

We begin the search by doing the following:

1. Begin at the starting point A and add it to an “open list” of squares to be considered. It contains squares that might fall along the path you want to take, but maybe not. Basically, this is a list of squares that need to be checked out.
2. Look at all the reachable or walkable squares adjacent to the starting point. Add them to the open list, too. For each of these squares, save point A as its “parent square”. This parent square stuff is important when we want to trace our path.
3. Drop the starting square A from your open list, and add it to a “closed list” of squares that you don’t need to look at again for now.

---

Status after Step 3 is illustrated below:

• The dark green square in the center is your starting square. It is outlined in light blue to indicate that the square has been added to the closed list.
• All of the adjacent squares are now on the open list of squares to be checked, and they are outlined in light green. Each has a gray pointer that points back to its parent, which is the starting square.

Path Scoring

• After step 3, we choose one of the adjacent squares on the open list and more or less repeat the earlier process (step 1~3).
• But which square do we choose? The one with the lowest F cost.
• That means Our path is generated by repeatedly going through our open list and choosing the square with the lowest F score.

---

We use the following equation to determine which squares to use:
F = G + H F = G + H F=G+H

where

• G G G = the movement cost to move from the starting point A to a given square on the grid, following the path generated to get there. (也就是从起点到达该点的 actual cost)
• H H H = the estimated movement cost (just a guess) to move from that given square on the grid to the final destination, point B. (heuristic 启发式的)
  (We really don’t know the actual distance until we find the path. You are given one way to calculate H in this tutorial, but there are many others.)
• The closer our estimate is to the actual remaining distance, the faster the algorithm will be. If we overestimate this distance, however, it is not guaranteed to give us the shortest path. In such cases, we have what is called an “inadmissible(不可接受的) heuristic.”

---

First let’s look more closely at how we calculate the equation.

• In this example, we will assign a cost of 10 to each horizontal or vertical square moved, and a cost of 14 ( 10 2 10\sqrt2 102 ​) for a diagonal move.
  (Using whole numbers like these is a lot faster for the computer)
• The way to figure out the G cost of that square is to take the G cost of its parent, and then add 10 or 14 depending on whether it is diagonal or orthogonal (non-diagonal) from that parent square.
• H can be estimated in a variety of ways. The method we use here is called the Manhattan method, where you calculate the total number of squares moved horizontally and vertically to reach the target square from the current square, ignoring diagonal movement, and ignoring any obstacles that may be in the way. We then multiply the total by 10, our cost for moving one square horizontally or vertically.
  • Technically, in this example, the Manhattan method is inadmissible because it slightly overestimates the remaining distance.
  • But we will use it anyway because it is a lot easier to understand for our purposes, and because it is only a slight overestimation. On the rare occasion when the resulting path is not the shortest possible, it will be nearly as short.
• F is calculated by adding G and H.

Continuing the Search

4. To continue the search, we simply choose the lowest F score square from all those that are on the open list. (drop it from our open list and add it to our closed list)

If there is a tie in the lowest F score, we can choose them arbitrarily.

For simplicity，we refer to " u p d a t e update update s t a t u s status status" as “set parent node and update G, H, F scores”

5. Then we check the adjacent squares.

• We ignore the walls and the squares already in the closed list.
• If the adjacent squaresare are not on the open list, we need to add them to the open list and update their status.
• If the adjacent squares are already on the open list and the paths to those squares are better using this square to get there (by using G scores), we need to update their status.

---

• Let’s look at the square right above our selected square. Its current G score is 14. If we instead went through the current square to get there, the G score would be equal to 20. So this is not a better path.
• When we repeat this process for all 4 of the adjacent squares already on the open list, we find that none of the paths are improved by going through the current square, so we don’t change anything.
• So now that we looked at all of the adjacent squares, we are done with this square, and ready to move to the next square.
• Repeat step 4~5, as is shown in the following pricture.

规则中设定在有墙的地方不能斜着走

• We repeat this process until we add the target square to the closed list.

• So how do we determine the path? Simple, just start at the red target square, and work backwards moving from one square to its parent, following the arrows.

Summary of the A* Method

1. Add the starting square (or node) to the open list.

2. Repeat the following:

• Look for the lowest F cost square on the open list. We refer to this as the current square.
• Switch it to the closed list.
• For each of the 8 squares adjacent to this current square …
  • If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.
  • If it isn’t on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.
  • If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.

3. Add the target square to the closed list, in which case the path has been found, or Fail to find the target square, and the open list is empty. In this case, there is no path.

Note: In earlier versions of this article, it was suggested that you can stop when the target square (or node) has been added to the open list, rather than the closed list. Doing this will be faster and it will almost always give you the shortest path, but not always.
Situations where doing this could make a difference are when the movement cost to move from the second to the last node to the last (target) node can vary significantly – as in the case of a river crossing between two nodes, for example.

Notes on Implementation

• Use heaps to maintain the open list
• Store everything in arrays to avoid dynamic allocation, where the amount of time needed to create and delete objects adds an extra, unnecessary level of overhead that slows things down.
• You can devise two or more pathfinding systems that are used in different situations, depending upon the length of the path. This is what the professionals do, using large areas for long paths, and then switching to finer searches using smaller squares/areas when you get close to the target.

文中在这一部分还有更多有关 A* pathfinding 的注解，但是我现在好像用不着…

Further Reading

• Amit’s A* Pages. See especially Amit’s own thoughts on the topic. (翻译版在这里)