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. But we are getting ahead of ourselves. Let's start at the beginning ... 介绍：搜索区域Introduction: The Search AreaLet'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. 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 SearchOnce 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:
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. 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. |