Path Scoring
  Summary of the A* Method

  Printable version
  Discuss this article

This article has been translated into Spanish and French. Other translations are welcome.

While it is easy once you get the hang of it, the A* (pronounced A-star) algorithm can be complicated for beginners. There are plenty of articles on the web that explain A*, but most are written for people who understand the basics already. This one is for the true beginner.

This article does not try to be the definitive work on the subject. Instead it describes the fundamentals and prepares you to go out and read all of those other materials and understand what they are talking about. Links to some of the best are provided at the end of this article, under Further Reading.

Finally, this article is not program-specific. You should be able to adapt what's here to any computer language. As you might expect, however, I have included a link to a sample program at the end of this article. The package contains two versions: one in C++ and one in Blitz Basic. It also contains executables if you just want to see A* in action.
最后,本文不是编程规范的。你应该能够改写这里的东西到任何计算机语言上。如你所期望的,同时,我包含了一个示例程序的链接,在本文后面结束的地方。这个程序包有两个版本:一个是C++,另一个用Blitz Basic语言编写。如果你只是想看看A*的行为,里面也含有可执行exe文件。

But we are getting ahead of ourselves. Let's start at the beginning ...
但我们要超越自己。让我们从头开始 ...

介绍:搜索区域Introduction: The Search Area

Let's assume we have someone who wants to get from point A to point B and that a wall separates the two points. This is illustrated in the graphic found below, with green being the starting point A, red being the ending point B, and the blue filled squares being the wall in between.

[图 1][Figure 1]

The first thing you should notice is that we have divided our search area into a square grid. Simplifying the search area, as we have done here, is the first step in pathfinding. 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, and its status is recorded as walkable or unwalkable. The path is found by figuring out which squares we should take to get from A to B. Once the path is found, our person moves from the center of one square to the center of the next until the target is reached.

These center points are called "nodes". When you read about pathfinding elsewhere, you will often see people discussing nodes. Why not just refer to them as squares? Because it is possible to divide up your pathfinding area into something other than squares. They could be rectangular, hexagons, or any shape, really. And the nodes could be placed anywhere within the shapes ? in the center or along the edges, or anywhere else. We are using this system, however, because it is the simplest.

开始搜索Starting the Search

Once we have simplified our search area into a manageable number of nodes, as we have done with the grid layout above, the next step is to conduct a search to find the shortest path. In A* pathfinding, we do this by starting at point A, checking the adjacent squares, and generally searching outward until we find our target.

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. The open list is kind of like a shopping list. Right now there is just one item on the list, but we will have more later. 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. 从开始点A起,添加它到待考虑的方块的“开放列表”。开放列表有点象购物列表。此时只有一个项目在里面,但很快我们会得到更多。它包含了你可能取用的沿途的方块,也可能不用它。基本上,这是需要检查的方块的列表。
  3. Look at all the reachable or walkable squares adjacent to the starting point, ignoring squares with walls, water, or other illegal terrain. 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. It will be explained more later.
  4. 观察开始点邻近的所有可到达或可行走的方块,忽略有墙,水或其他非法地形的方块。也把它们添加到开放列表。对每一个方块,保存A 点作为它们的“父亲”。这个父亲方块在跟踪路径时非常重要。后面会更多的解释。
  5. 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.
  6. 把开始方块A从开放列表中取出,并放到“封闭列表”内,它是所有现在不需要再关注的方块的列表。

At this point, you should have something like the following illustration. In this diagram, 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.

[图 2][Figure 2]

Next, we choose one of the adjacent squares on the open list and more or less repeat the earlier process, as described below. But which square do we choose? The one with the lowest F cost.

路径排序Path Scoring