前言：
A*算法是路径搜索中的经典算法，也是公认的最优算法之一，网上找到一篇文章讲的很好，适合入门，所以翻译了一下，没有完全参照原文，主要还是意译，网上也有其他人翻译好的，个人觉得还是自己来一遍比较好，读者自斟：
原文
开始：搜索区域
这里假设有人要从A点去往B点，另外有一面墙将两者分开。如下图所示，绿色方块代表A点，红色方块代表B点，蓝色代表分开他们的墙。
图一
首先要注意的是我们这里先将整个搜索区域网格化，以方便路径搜索。这一方法将搜索区域简化为一个简单的2为数组。数组的每个元素代表网格上的一片区域，并且标记为可通过或不可通过两种状态。路径由从A点到达B点所经过的方块来表示。
这些点被称为节点。之所以不直接叫方块是因为区域可以被划分为矩形，六边形，等。而点也不一定是在中心，可以在边缘或其他地方。
开始搜索
一旦我们如上图将搜索区域网格化，将之转化为可操作数量的节点，然后下一步就是找到一个搜索算法找出最短路径。我们从A点出发，搜索递归周围领域，直到到达目标点
开始搜索的步骤如下：
1. 从A点出发并且将其放入到“候选列表”备用。候选列表就像就像是购物清单。现在上面只有一项在清单上，但我们会陆续添加。其中包含一些潜在的路径点。基本上，这个列表包含有待确认的方块。
2. 找到与起始点相邻的所有可到达方块，忽略那些墙，水等其他非法区域。将这些点加入到“候选列表”，存入方法与先前父方块A的存入方法相同。这些父方块会在我们进行路径跟踪回溯的时候派上用场。
3. 从“候选列表”中将A方块删除，并将其加入到“排除列表”，表明在此列表中的方块不需要再去关注。
关于这点，如下图所示，中间的方块是起始点，它周围的亮蓝色边框表明此方块一经被加入到“排除列表”。所有在“候选列表”上的方块都需要进一步检查，他们的边框呈现亮绿色。每一个里面都有一个箭头指向其父节点，这里是起始方框。
图2
接下来，我们在选择“候选列表”中的一个领域然后大致上重复刚才的步骤，如下所述。然后选择拥有最小F值的那个方块
路径评估
在路径选择是关键指标等式描述如下：
F = G + H
这里：
- G= 表示从A点到当前点的所经过的路径长度
- H=从当前点到目标点B的估计路径长度。这经常被描述为“启发式”，有时这样会引起歧义。之所以这么叫是因为这仅仅是一种猜测。事实上在找到路径之前我们并不知道实际路径长度，因为会有如墙，水等东西阻挡。这里给出一种计算H的方法，同时在网上有许多其他计算H值的方法。
我们的路径正式不断的遍历“候选列表”并选择最小F值的点。这个过程会在稍后详细说明。首先来了解我们是如何计算等式的。
如上所述，G是利用先前产生的路径到达当前点所得长度。此例中，出于简化目的，我们定义单元格之间的距离为10，对角单元格距离为14，同时这样做也会大大减少计算量。
有多中计算方法。这里所使用的方法是曼哈顿方法，该方法累计从当前点到目标点在水平方向和垂直方向（忽略对角线方向）所要经过的所有方块数，同时忽略可能遇到的障碍。然后将结果乘以10（单位距离），之所以成为曼哈顿方法，是因为这就像要数从一个地方到另一个地方要走过多少个街区，而同时你有不能斜穿街区。
看完这个描述，你或许会认为所谓的“启发式”不过是将剩余的路径长度粗略的估计为两点间的直线距离。事实上并非如此。我们正是在试图估计实际剩余距离（一般会比实际距离更长），与实际距离越接近，算法越快速，如果估计值过大，就会有可能出现找出的路径不是最短路径的情况。这种情况我们称之为“不可接受启发式”
第一步搜索的F，G，H可表示如下图
图三
继续搜索
继续搜索，我只是从“候选列表”选出最小F值的方块，然后执行如下操作
4) 将其从“候选列表”中删除加入到“排除列表”
5) 检查其领域内方块，排除不可通过方块，并且将没有在“候选列表”中的方块加入到“候选列表”。是当前选中方块成为父方块。
6) 如果领域内存在方块在“候选列表中”中，那么就检查是否从当前点经由那个候选方块是一条更好路径。换句话说，检查那个方块的G值是否会因为我们使用了当前点到达那里而变小，如果不是，什么都不做，另一方面，如果新的路径G值变小了，就将那个候选方块的父节点改为当前点。最后重新计算那个候选节点的F和G值
译者注：
这一步是A*算法较为难理解的一步，这一步的目的在于优化从起始点到候选列表中的点路径，因为在H函数既定的情况下，候选列表中H值就是一定的，此时优化G值可以帮助找到最小的F值。
现在来看一下，在候选列表中的8个方块中，拥有最小F值的是右边中间的方块，所以选择它为下一个方块，在图解中该方块边缘以蓝色高亮。
图4
首先将其从“候选列表”中删除，加入到“排除列表”。然后检查其领域，右边和左边中间的方块都被排除。
领域余下的4个方块都已经在“候选列表”中，所以我们需要检查是否从当前点经由那个候选方块是一条更好路径。计算可以经由当前点并不能改善原有候选列表中方块的G值。所以什么都不做
译者注：G是从起始点到所计算点所经过路径点的G值的和
接下来继续搜索候选列表，找到最小的F值的方块有两个，分别位于右上和右下，这里其实选择哪个没有固定标准，我们选择后加入“候选列表”的那个方块作为当前点，这样做的结果是我们总是优先计算新加入的F值较的候选点，在大部分情况下这有助于我们更快的到达目的地。同样这里采用不同的筛选方法会导致不同的最终路径但拥有相同的路径长度。
所以就选择右下那个方块
图5
这次，我们排除当前方块右边的三个方块，至于右下那个被排除，则是这里选择的穿透策略导致，你也可以选择其他的穿透策略。
重复刚才的步骤知道我们将目标嗲加入到“排除列表”，如下图所示：
图6
那么我们要如何来选择路径呢？答案很简单，我们只要从目标点开始不断的沿着其父方块就可以找回到起始方块。如图中红点方块所示。
图7
A*算法总结
现在将整个步骤总结如下：
1) 将起始点加入到“候选列表”
2) 重复如下步骤：
a) 搜索候选列表的最小F值，将其选为当前点
b) 放入“排除列表”
c) 对于与其相邻的8个方块
-
如果不可通过或其在“排除列表”中，就忽略掉，否则执行下面步骤。
-
如果其不在“候选列表”，将他加入到“候选列表”，将当前点作为其父节点，计算F，G，H
-
如果领域内存在方块在“候选列表中”中，那么就检查是否从当前点经由那个候选方块是一条更好路径。换句话说，检查那个方块的G值是否会因为我们使用了当前点到达那里而变小，如果不是，什么都不做，另一方面，如果新的路径G值变小了，就将那个候选方块的父节点改为当前点。最后重新计算那个候选节点的F和G值
d) 终止条件：
- 目标方块被加入到“排除类表”，这种情况下路径被找到
- 在“候选列表”中的点全部被放到了“排除列表中”，此时路径查找失败，没有通路。
3）保存路径，从目标点开始不断的沿着其父方块就可以找回到起始方块。
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.
上面这段红色话直译好理解，但是我还没有想到作者所谓两个节点中间的一条河这种情况是如何影响终止条件的，在我看来终止条件是只要将目标点加入“候选列表”中就可以了，知道的达人说一声，最好有图解。谢谢
唠叨几句
网上有许多号称是A*算法的，但其实不是，A*算法被认为是在大多数情况下最好的算法，有如下构成要件：
“候选列表”
“排除列表”
评估等式 F=G+H
实现算法的注意事项：
以下与算法本身关系不大暂时不翻译了，有兴趣自己看一下
Now that you understand the basic method, here are some additional things to think about when you are writing your own program. Some of the following materials reference the program I wrote in C++ and Blitz Basic, but the points are equally valid in other languages.
1. Other Units (collision avoidance): If you happen to look closely at my example code, you will notice that it completely ignores other units on the screen. The units pass right through each other. Depending on the game, this may be acceptable or it may not. If you want to consider other units in the pathfinding algorithm and have them move around one another, I suggest that you only consider units that are either stopped or adjacent to the pathfinding unit at the time the path is calculated, treating their current locations as unwalkable. For adjacent units that are moving, you can discourage collisions by penalizing nodes that lie along their respective paths, thereby encouraging the pathfinding unit to find an alternate route (described more under #2).
If you choose to consider other units that are moving and not adjacent to the pathfinding unit, you will need to develop a method for predicting where they will be at any given point in time so that they can be dodged properly. Otherwise you will probably end up with strange paths where units zig-zag to avoid other units that aren't there anymore.
You will also, of course, need to develop some collision detection code because no matter how good the path is at the time it is calculated, things can change over time. When a collision occurs a unit must either calculate a new path or, if the other unit is moving and it is not a head-on collision, wait for the other unit to step out of the way before proceeding with the current path.
These tips are probably enough to get you started. If you want to learn more, here are some links that you might find helpful:
译者注：看了以上这段我想起魔兽中那些小人在移动时遇到一起会停一下，然后排队继续运动，原因就在这里。
2. Variable Terrain Cost: In this tutorial and my accompanying program, terrain is just one of two things – walkable or unwalkable. But what if you have terrain that is walkable, but at a higher movement cost? Swamps, hills, stairs in a dungeon, etc. – these are all examples of terrain that is walkable, but at a higher cost than flat, open ground. Similarly, a road might have a lower movement cost than the surrounding terrain.
This problem is easily handled by adding the terrain cost in when you are calculating the G cost of any given node. Simply add a bonus cost to such nodes. The A* pathfinding algorithm is already written to find the lowest cost path and should handle this easily. In the simple example I described, when terrain is only walkable or unwalkable, A* will look for the shortest, most direct path. But in a variable-cost terrain environment, the least cost path might involve traveling a longer distance – like taking a road around a swamp rather than plowing straight through it.
An interesting additional consideration is something the professionals call “influence mapping.” Just as with the variable terrain costs described above, you could create an additional point system and apply it to paths for AI purposes. Imagine that you have a map with a bunch of units defending a pass through a mountain region. Every time the computer sends somebody on a path through that pass, it gets whacked. If you wanted, you could create an influence map that penalized nodes where lots of carnage is taking place. This would teach the computer to favor safer paths, and help it avoid dumb situations where it keeps sending troops through a particular path, just because it is shorter (but also more dangerous).
Yet another possible use is penalizing nodes that lie along the paths of nearby moving units. One of the downsides of A* is that when a group of units all try to find paths to a similar location, there is usually a significant amount of overlap, as one or more units try to take the same or similar routes to their destinations. Adding a penalty to nodes already 'claimed' by other units will help ensure a degree of separation, and reduce collisions. Don't treat such nodes as unwalkable, however, because you still want multiple units to be able to squeeze through tight passageways in single file, if necessary. Also, you should only penalize the paths of units that are near the pathfinding unit, not all paths, or you will get strange dodging behavior as units avoid paths of units that are nowhere near them at the time. Also, you should only penalize path nodes that lie along the current and future portion of a path, not previous path nodes that have already been visited and left behind.
3. Handling Unexplored Areas: Have you ever played a PC game where the computer always knows exactly what path to take, even though the map hasn't been explored yet? Depending upon the game, pathfinding that is too good can be unrealistic. Fortunately, this is a problem that is can be handled fairly easily.
The answer is to create a separate "knownWalkability" array for each of the various players and computer opponents (each player, not each unit -- that would require a lot more computer memory). Each array would contain information about the areas that the player has explored, with the rest of the map assumed to be walkable until proven otherwise. Using this approach, units will wander down dead ends and make similar wrong choices until they have learned their way around. Once the map is explored, however, pathfinding would work normally.
4. Smoother Paths: While A* will automatically give you the shortest, lowest cost path, it won't automatically give you the smoothest looking path. Take a look at the final path calculated in our example (in Figure 7). On that path, the very first step is below, and to the right of the starting square. Wouldn't our path be smoother if the first step was instead the square directly below the starting square?
There are several ways to address this problem. While you are calculating the path you could penalize nodes where there is a change of direction, adding a penalty to their G scores. Alternatively, you could run through your path after it is calculated, looking for places where choosing an adjacent node would give you a path that looks better. For more on the whole issue, check out Toward More Realistic Pathfinding, a (free, but registration required) article at Gamasutra.com by Marco Pinter.
5. Non-square Search Areas: In our example, we used a simple 2D square layout. You don't need to use this approach. You could use irregularly shaped areas. Think of the board game Risk, and the countries in that game. You could devise a pathfinding scenario for a game like that. To do this, you would need to create a table for storing which countries are adjacent to which, and a G cost associated with moving from one country to the next. You would also need to come up with a method for estimating H. Everything else would be handled the same as in the above example. Instead of using adjacent squares, you would simply look up the adjacent countries in the table when adding new items to your open list.
Similarly, you could create a waypoint system for paths on a fixed terrain map. Waypoints are commonly traversed points on a path, perhaps on a road or key tunnel in a dungeon. As the game designer, you could pre-assign these waypoints. Two waypoints would be considered "adjacent" to one another if there were no obstacles on the direct line path between them. As in the Risk example, you would save this adjacency information in a lookup table of some kind and use it when generating your new open list items. You would then record the associated G costs (perhaps by using the direct line distance between the nodes) and H costs (perhaps using a direct line distance from the node to the goal). Everything else would proceed as usual.
Amit Patel has written a brief article delving into some alternatives. For another example of searching on an isometric RPG map using a non-square search area, check out my article Two-Tiered A* Pathfinding.
6. Some Speed Tips: As you develop your own A* program, or adapt the one I wrote, you will eventually find that pathfinding is using a hefty chunk of your CPU time, particularly if you have a decent number of pathfinding units on the board and a reasonably large map. If you read the stuff on the net, you will find that this is true even for the professionals who design games like Starcraft or Age of Empires. If you see things start to slow down due to pathfinding, here are some ideas that may speed things up:
- Consider a smaller map or fewer units.
- Never do path finding for more than a few units at a time. Instead put them in a queue and spread them out over several game cycles. If your game is running at, say, 40 cycles per second, no one will ever notice. But they will notice if the game seems to slow down every once in a while when a bunch of units are all calculating paths at the same time.
- Consider using larger squares (or whatever shape you are using) for your map. This reduces the total number of nodes searched to find the path. If you are ambitious, 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. If you are interested in this concept, check out my article Two-Tiered A* Pathfinding.
- For longer paths, consider devising precalculated paths that are hardwired into the game.
- Consider pre-processing your map to figure out what areas are inaccessible from the rest of the map. I call these areas "islands." In reality, they can be islands or any other area that is otherwise walled off and inaccessible. One of the downsides of A* is that if you tell it to look for paths to such areas, it will search the whole map, stopping only when every accessible square/node has been processed through the open and closed lists. That can waste a lot of CPU time. It can be prevented by predetermining which areas are inaccessible (via a flood-fill or similar routine), recording that information in an array of some kind, and then checking it before beginning a path search.
- In a crowded, maze-like environment, consider tagging nodes that don't lead anywhere as dead ends. Such areas can be manually pre-designated in your map editor or, if you are ambitious, you could develop an algorithm to identify such areas automatically. Any collection of nodes in a given dead end area could be given a unique identifying number. Then you could safely ignore all dead ends when pathfinding, pausing only to consider nodes in a dead end area if the starting location or destination happen to be in the particular dead end area in question.
7. Maintaining the Open List: This is actually one of the most time consuming elements of the A* pathfinding algorithm. Every time you access the open list, you need to find the square that has the lowest F cost. There are several ways you could do this. You could save the path items as needed, and simply go through the whole list each time you need to find the lowest F cost square. This is simple, but really slow for long paths. This can be improved by maintaining a sorted list and simply grabbing the first item off the list every time you need the lowest F-cost square. When I wrote my program, this was the first method I used.
This will work reasonably well for small maps, but it isn’t the fastest solution. Serious A* programmers who want real speed use something called a binary heap, and this is what I use in my code. In my experience, this approach will be at least 2-3 times as fast in most situations, and geometrically faster (10+ times as fast) on longer paths. If you are motivated to find out more about binary heaps, check out my article, Using Binary Heaps in A* Pathfinding.
Another possible bottleneck is the way you clear and maintain your data structures between pathfinding calls. I personally prefer to store everything in arrays. While nodes can be generated, recorded and maintained in a dynamic, object-oriented manner, I find that the amount of time needed to create and delete such objects adds an extra, unnecessary level of overhead that slows things down. If you use arrays, however, you will need to clean things up between calls. The last thing you will want to do in such cases is spend time zero-ing everything out after a pathfinding call, especially if you have a large map.
I avoid this overhead by creating a 2d array called whichList(x,y) that designates each node on my map as either on the open list or closed list. After pathfinding attempts, I do not zero out this array. Instead I reset the values of onClosedList and onOpenList in every pathfinding call, incrementing both by +5 or something similar on each path finding attempt. This way, the algorithm can safely ignore as garbage any data left over from previous pathfinding attempts. I also store values like F, G and H costs in arrays. In this case, I simply write over any pre-existing values and don't bother clearing the arrays when I'm done.
Storing data in multiple arrays consumes more memory, though, so there is a trade off. Ultimately, you should use whatever method you are most comfortable with.
8. Dijkstra's Algorithm: While A* is generally considered to be the best pathfinding algorithm (see rant above), there is at least one other algorithm that has its uses - Dijkstra's algorithm. Dijkstra's is essentially the same as A*, except there is no heuristic (H is always 0). Because it has no heuristic, it searches by expanding out equally in every direction. As you might imagine, because of this Dijkstra's usually ends up exploring a much larger area before the target is found. This generally makes it slower than A*.
So why use it? Sometimes we don't know where our target destination is. Say you have a resource-gathering unit that needs to go get some resources of some kind. It may know where several resource areas are, but it wants to go to the closest one. Here, Dijkstra's is better than A* because we don't know which one is closest. Our only alternative is to repeatedly use A* to find the distance to each one, and then choose that path. There are probably countless similar situations where we know the kind of location we might be searching for, want to find the closest one, but not know where it is or which one might be closest.
Further Reading
If you do not have access to C++ or Blitz Basic, two small exe files can be found in the C++ version. The Blitz Basic version can be run by downloading the free demo version of Blitz Basic 3D (not Blitz Plus) at the Blitz Basic web site.
You should also consider reading through the following web pages. They should be much easier to understand now that you have read this tutorial.
- Amit’s A* Pages: This is a very widely referenced page by Amit Patel, but it can be a bit confusing if you haven’t read this article first. Well worth checking out. See especially Amit's own thoughts on the topic.
- Smart Moves: Intelligent Path Finding: This article by Bryan Stout at Gamasutra.com requires registration to read. The registration is free and well worth it just to reach this article, much less the other resources that are available there. The program written in Delphi by Bryan helped me learn A*, and it is the inspiration behind my A* program. It also describes some alternatives to A*.
- Terrain Analysis: This is an advanced, but interesting, article by Dave Pottinger, a professional at Ensemble Studios. This guy coordinated the development of Age of Empires and Age of Kings. Don’t expect to understand everything here, but it is an interesting article that might give you some ideas of your own. It includes some discussion of mip-mapping, influence mapping, and some other advanced AI/pathfinding concepts.
Some other sites worth checking out: