A*寻径入门
原文链接：
原文更新于：2005年7月18日
译文日期：2005年7月24日
A*算法（中文读做A星）对于菜鸟来说可能很复杂。鉴于网络上已经有很多关于A*算法的进阶文章，本篇文章是为真正的菜鸟准备的。
本文并不打算对A*算法进行全面的阐述，只是介绍了它的基本原理，更多进阶的文章请参考文章末尾给出的链接。
最后，本文并不针对某种特定的语言。你可以将这其中的内容应用到任务语言中去。然后，在本文的结尾我还是如您所愿的提供了一个例子程序的链接，这个包里面包含了C++和Blitz Basic两个版本的实现以及最终生成的可执行程序。
让我们开始提升自己吧...
导言：搜索区域
我们假设有某人要饶过中间的墙从A点走到B点。如下图所示，A点是绿色，B点是红色，中间的方块墙是蓝色。
首先你会注意到我们把我们的搜索区域划分成方块。寻径算法的第一步便是简化搜索区域，划分方块将我们的搜索区域简化成一个2维矩阵，矩阵中的每一项表示搜索区域中的一个方块，其记录的状态信息代表了该方块是否能经过。通过计算出我们从A到B所需要经过的方块来求出路径。当路径被确定下来以后，我们的小人就可以从一个方块的中心点移动到下一个方块的中心点，直到它到达目标地点。
这些中心点被称为“结点”。如果你之前有读过寻径算法的文章，你会经常看到人们在讨论结点。为什么不叫他们方块呢？因为搜索区域可能被划分成其他形状而不仅仅是方块，这其中包括矩形、六边形、三角形或者其他任意的形状。而且结点可以被放置在图形中的任意位置，如中心点、边缘或者其他什么地方。无论如何，结点是最简洁的表达方式了。
开始搜索
当我们将我们的搜索区域简化成一组结点以后，下一步就是搜索最短的路径。我们从目标点开始，检查它临近的方块，并向外扩展出去直到我们找到目标。
下面是我们搜索的步骤：
1. 从A点开始，将A点存入一个待操作的"open list"中（open list有点类似于你的购物列表）。刚开始列表中只有一个项，但表着急，接下来我们会有更多的项。它所保存的方块，你可能经过，也可能不经过。基本上，它是一个需要被检查的方块的列表。
2. 忽略那些是墙壁、水池或其他不能通过的地形的方块，找到起始点附近所有可到达并可通过的方块，把他们也加入到open list中去。将A点保存为这些方块的“父方块”。父方块对我们找到路径来说很重要，稍后将会有所解释。
3. 从open list中删除掉A，将其加如一个叫做"closed list"的列表中，该列表用于保存以后不会再次被检查到的结点。
现在，你得到的是如下图所示的东西。在该图释中，中间的暗绿色方块是你的起始方块。它被亮蓝色的框框起来，代表该方块已经被加入到closed list中去。所有邻近的方块都被亮绿框框起，每个方块里有一条指向父方块的灰线。这些邻近的方块被放置在open list中等待下一步的检查。
接着，我们将取出open list保存的邻近方块们中的一块，大致重复前面所做的处理。但我们应该选择哪一块呢？答案是：F值最小的那一个。
给路径评分
下面的公式是决定寻径时该使用哪个方块的关键：
F = G + H
G = 沿着计算出的路径，从A移动到到网格中的指定方块的花费
H = 从指定方块运动到重点B的预估花费。由于在路上可能有各种各样的东西（如墙壁、水池等等）挡着，在我们找到最后的路径之前我们实际并不知道真正的距离，它只是个估测。因此这个计算的过程通常被称为启发式的。本文只提供了一种计算H值的方法，但你可以在网上找到其他的方法。
遍历我们的open list，选出其中F值最低的方块，不断的重复这个过程就能找到最终的路径。梢后将会有该过程的更详细的描述。首先我们来看看如何计算这个公式。
如上面所描述的，G是沿着计算出的路径，从起始点移动到指定方块的移动花费。在该例子中，我们假设垂直或水平移动的花费为10，对角线移动的花费为14。我们做出这样的假设，是因为对角线移动是水平移动或垂直移动花费的根号2，或者是1.414倍。简单起见，我们取了10和14，这样的比例基本上正确，并使我们避免计算根号或小数。对计算机来说，整数运算更快。很快你就会发现，不做这些简化措施的话，你的寻径过程将变得很慢。
因为我们是在计算沿指定路径到指定方块的G值，所以求出G值的方法，就是取父方块的G值，根据它对父结点的方位是对角线或非对角线，加上前面假设的值10或14。由于父方块的邻近结点不只一块，我们需要计算很多次。
计算H的方法有很多种，我们将使用一种叫做曼哈顿的算法，他计算从当前方块到目标方块间水平方块和垂直方块的总数量，忽略对角线移动和路上的任何障碍物。然后将总数量乘以10。我猜测之所以叫曼哈顿算法，可能是因为它和城市中移动有点像，你只能沿着路走，而不能以对角线穿过房子。
读到这，你可能猜想所谓的启发式只不过是对当前方块到目标方块的直线距离的粗略估计。事实上，我们试图估算的是沿着最终路径的距离，一般这个距离比上面的结果要长。我们的估算越接近实际剩下的距离（沿这最终路径），我们算法就会越快。如果我们过高的估计了这个距离，无论如何，我们都没法保证我们能得到最短路径。
在该例子中，曼哈顿算法有点高估了这个距离。由于它很简单，便于我们理解，而且只是有点小小的偏差，我们仍然使用他来描述我们的算法。在某些场合，可能找到的路径不是最短路径，但是会尽可能的短。关于启发式搜索，有更详细的介绍。
G加上H就得到了F。我们第一步的得到的结果如下图所示。每个方块中标明了他的F、G、H值。左上方是F，左下方是G，右下方是H。
让我们来看看其中的一些方块。在有字母标注的方块中，G = 10。因为他是和起始方块水平相连的方块。和起始方块相连的上、下、左、右的方块的G值都是10。对角线上的方块的值是14。
只计算水平和垂直方向的方块，忽略路上的障碍物，使用曼哈顿公式求出到红色目标方块的值就是H。该例中，和起始方块水平相连的方块和目标点距离3块方块，所以H值是30。位于起始方块的上面的方块和目标方块距离4个方块（记住，只能水平和垂直移动），所以H是40。你可以试着计算一下其他方块的H值。
每个方块的F值，就是各自G和H值的和。
继续搜索
接着，我们从open list中选出F值最小的那个方块，对它（以下我们称之为当前方块）进行以下的操作：
4. 把当前方块从open list中删除，并加入到closed list。
5. 检查当前方块的所有邻接方块，忽略那些那些不可通过的（如墙，水等）或者已经在closed list中的方块，如果它们还不在open list中，就将其加入到open list，并将当前方块记为这些方块的父方块。
6. 如果邻接方块已经在open list中，检查一下通过当前路径走到该邻接方块是不是一条更好的路径。换句话说，就是检查一下通过当前方块到达该邻接方块的话，G值是不是会更小一些。如果不是，则什么都不做。
另一方面，如果这条新路径的G值要来的小的话，就把该邻接方块的父方块改为当前方块（在上面的图中，将方块中箭头的方向改为指向当前方块）。然后，重新计算该邻接方块的F和G值。如果你还有些疑惑，请看下面的图。
让我们来瞧瞧它是如何运作的。当起始方块被放到closed list中以后，在open list中的就是剩下的8个邻接方块。在这个例子中，和起始方块紧挨在一起的右边的方块的F值是最小的：40。所以我们选择这个方块作为我们的下一步方块。在下图中，它用亮蓝色标示出来。
首先，我们把它从我们的open list中移到closed list中（这就是为什么它现在用亮蓝色标示）。然后我们检查它周围的邻接方块。它右边的几个方块是墙，跳过。左边的方块是起始方块（已经在closed list中），同样跳过。
其他的四个邻接方块已经在open list中了，所以我们需要以G值做为参考，检查一下如果通过当前方块到达它们那，会不会更好。来看看我们当前方块的正上方的那个方块，它的G值是14。如果我们通过当前方块，到达这个方块所花费的G是20（从起始点移动到当前方块需要花费10，从当前方块再走到这个方块又要花费10）。20的花费自然比14要多，所以这并不是一条更好的路径。直接从起始点斜向移动一个方块，比起先水平移动后再垂直移动来说要短，从图中你也能清楚地感觉到这点。
当我们对open list中已存在的所有4个邻接矩形重复这一处理过程以后，我们发现所有通过当前方块的路径并没有改善原先的路径，所以我们不做任何改变。现在，所有的邻接方块都已经被处理过了，我们可以处理下一个方块了。
我们遍历open list里剩下的7个方块，选出起中F值最小的那个。有趣的是，本例中有两个方块的F值都是54。那么，我们该选哪一个？出于速度的考虑，选择最后一个加到open list中的方块会来得快一些。在寻径过程中，当你靠近目标点的时候，选择最近找到的方块是个无关紧要的小偏好。（对待两个候选结点的不同方式导致了A*算法可能找到一样长的不同路径。
所以我们选择在正下方的那个方块（在起始方块的右边），如下图所示：
这一次，当我们检查邻接方块的时候我们发现正右边的那一块是墙，于是我们跳过它。它上面的那方块我们也一样跳过。对于在墙正下方的那个方块也被我们跳过。这是因为你在拐过那堵墙的时候不能直接从当前方块直接走到那个方块。你需要先走下来一格再平移到它上面去。（这个通过拐角的规则是可选的。它取决于你的结点们是如何放置的）
现在还剩下5个方块。当前方块下面的那两个方块还不在open list中，于是我们把它们添加到open list中，并把当前方块记为它们的父方块。其他的3个方块，有两个已经在closed list中了（起始方块，和当前方块正上方的那一块，在图中用亮蓝色标出），直接略过。在当前方块正左方的方块，我们检查如果我们经过当前方块走到那所产生的G值是不是会更低。看起来不行。现在我们可以检查open list中的下一个方块了。
我们一直重复上面的过程，直到我们把目标方块加入到closed list中去，如下图所示：
需要注意的是在起始方块下方的那两个方块的父方块已经被改动过了。之前它的G值是28，并且指向的是其右上方的方块。现在它的G值是20，并且指向正上方的方块。在我们的寻径过程中，我们发现如果用一条新的路径，G值将会更低，所以该方块的父方块被改变，并重新计算其G和F值。尽管在本例子中这样的改变并不明显，但在实际的寻径过程中它可能对结果产生很大的影响。
我们如何选择路径？简单，只需要从红色的目标方块开始，按箭头的方向向父方块移动，最终我们将回到起始方块，这就是你要的路径。就像下面的例图所展示的那样。从A点移动到B点只是简单地沿着路从一个方块（结点）的中心移动到下一个方块，直到你到达目的地。
A*算法概要
现在你已经看过了前面的说明，下面我们把步骤一步一步列出来：
1.把起始方块（或者叫结点）添加到open list中。
2.重复下列步骤：
a.从open list里选出F值最低的方块作为当前方块。
b.把当前方块移到closed list。
c.对当前方块8个邻接方块中的每一个方块...
·如果它不可通过或者已经在closed list中，忽略它。反之，进行下面的操作.
·如果它不在open list里面，把它加入到open list里并把当前方块记为它的父方块。计算出它的F，G，H值
·如它已经在open list里面，以G值为参考检查新的路径是不是更好。如果G值比较低说明是条更好的路径。如果是这样的话，就把它的父方块改成当前方块，并重新计算G和F值。如果你的open list采用F值来排序，你需要重新排序你的open list。
d.当...时停止
·目标方块被加入到closed list中（这意味着路径已经被找到（详见下面注释）），或者
·open list空了的时候还没找到目标方块，说明路径不存在。
注释：在本文的早期版本中，建议的做法是在目标方块（结点）被添加到open list中的时候就停止寻径，而不是closed list。这样做的话速度会更快，而且几乎总能找到最短的路径，但不是绝对的。如果刚好有一条河横在最后第二个结点和最后一个结点（目标结点）中，那么从最后第二个结点到最后一个结点的移动花费就会很大，这样这两种方法找出的结果就很不一样。
题外话
说点题外话，当你在浏览网上的关于A*算法的形形色色的文章时，你可能会看到一些被标为A*算法的代码，但实际上它们不是。要使用A*算法，你就会用到上面所讨论的那些算法的基本元素，比如：open list，closed list，用F，G，H值做路径评分。实际上存在很多的路径搜索算法，但使用其他元素的算不上A*算法，A*算法被认为是它们之中最好的寻径算法。在本文末尾给出的参考文献中，Bryan Stout讨论它们的优缺点。在某些情形下使用其他的算法可能会更好，你必须知道自己需要的是什么。恩，话说够了，回到正题中去吧。
关于实现
现在你已经知道了基本的原理，当你写实际代码的时候，这里还有些其他的要考虑到的细节。下面的部分内容引用了我用C++和Blitz Basic写的例子程序，但其中的观点对于其他语言同样有效。
1.其他单元（避免碰撞）：如果你已经仔细看过了我提供的例子代码，你应该会发现我完全忽略掉了屏幕上的其他单元。这些单元可以互相穿越。是否采用这样的规则其实取决于不同的游戏需求。如果你打算在寻径中考虑其他的单元，并让它们能够互相绕过，我建议你只考虑静止的单元，或者临近当前搜索单元的那些单元，把它们当成是不可通过的地形。对于那些临近区域移动的单元，你可以在它们各自的路径中的结点上放置一些惩罚措施，以鼓励它们寻找不同的路径（更详细的描述请看#2）
如果你打算把那些在非临近结点移动的单元也考虑进去的话，你需要找到一中方法来预测当前时刻它们可能的位置来避免它们之间的碰撞。否则你可能得到一条怪异的之字形路径，看起来就像是为了避免碰撞你试图绕过一个不存在的单元。
你也需要写一些碰撞检测的代码，因为时间的关系，在某一时刻看起来很棒的一条路线也可能随时被改变。当碰撞发生时，要嘛就找一条新的路径，或者，另外的那个单元也正在移动而且不是正面的碰撞，那么就停下来等那个单元走开。
以上的窍门或许足够你应付了。如果你想了解更多这方面的信息，下面的这些连接对你可能会有些帮助：
: Craig Reynold 在导向上的研究可能和寻径有点区别，但是把它和寻径结合起来能够的饿到一个更完整的移动和避免碰状的系统。
：一个关于导向和寻径的有趣调查。这是一个PDF文件。
：《帝国时代》的设计师Dave Pottinger写的关于编队和基于编队移动的文章。
：Dave Pottinger文章的第二部分。
2.不同地形的移动消耗：在本文和本文附带的例子中，地形只有两种——可通过和不可通过。但如果有一种地形是可以通过，但需要更多的移动消耗的呢？沼泽，山丘，地牢中的楼梯等等，这些地形是可通过的，但比平坦开阔的地形的移动消耗要多。类似的，地面上的一条路的移动消耗可能要比路周围的地形的移动消耗要小的多。
解决这个问题的方法很简单，只要在计算G值的时候加入地形消耗的影响就行了。由于A*算法通过计算最小的移动消耗来寻找路径，所以很容易处理这种情况。在我的例子中，地形只有可通过和不可通过两种情况，A*将找出最短最直接的那条路。但是在一个存在复杂地形的环境中，最少消耗的路径可能会绕过很长的距离，比如沿路绕过沼泽而不是直接穿过沼泽。
还有一种有趣的被称做“influence mapping”的情况。类似于上面不同地形引起的移动消耗，你可以创造一个分数系统并把它应用到AI中。想象你又一大队人马要穿过山区地带的某个路口。每次当计算机沿同样的路径把单元送过路口的话，路口就会变得拥挤不堪。如果你愿意，你可以创建一个influence map来在结点上放置惩罚措施（比如这些结点上正在发生大屠杀）。这样会让计算机倾向于选择更安全的路径，并且帮助让它避免仅仅因为距离短（因为这条路可能更危险）而不断的把人送到同一条路上去。
另一个可能的做法是在附近移动单元的路上放置惩罚结点。A*算法的一个缺点就是，如果有一堆的单元都要走到相似的目标点去，那可能最后寻找出的路径都几乎都相似，造成路径的交叠。在其他单元“要求”的结点上放些惩罚有助于分离开路径，避免碰撞。不要将那些结点标记为不可通过的，因为你还是希望让多数的单元能够列队挤过那个狭小的路口。而且，你应该只在寻径中单元附近的结点放置惩罚，而非所有的路径，要不你就会看到你的移动单元在躲避远处单元的奇怪行为。你也应该只在当前结点或下一个到达的而不是已经走过的结点上放置惩罚。
3.处理未知区域：你遇到过那种连地图都还没打开而电脑却总是知道该往哪走的电脑游戏吗？对于游戏来说，这样的寻径真是太假了。幸运的是，这样的问题很容易解决。
答案是为每个电脑对手和每个玩家（每个玩家，而不是每个单元——那样需要占用太多的内存）创建一个“已知可通过区域”（knownwalkability）的数组。每个数组记录了玩家已探索过的区域，还有地图上的其他区域（在证实它们可通过之前我们先假设它们可通过）。使用这种方法，单元会不停的碰壁直到它探索完周围的区域。一旦地图被探索完，寻径就会想往常一样发挥作用了。
4.平滑路径：A*算法给你的总是最短的，移动消耗最少的路径，而非给你看起来最平滑的路径。回顾一下在我们例子最后找到的那条路径（在图7中）。最初的一步是在起始方块的右边，如果这一步是直接往下面走，路径看起来会不会更平滑一点呢？
有几个方式可以解决这个问题。当你在计算路径的时候，你可以在需要改变前进方向的方块上放置惩罚，增加它们的G值消耗。或者你可以沿计算出的路径走一遍，找到相邻的可以让路径看起来更平滑的结点。想要了解更多的话，请参考Macro Pinter在Gamasutra.com上的 。（免费的，但需要注册）
5.非方形的搜索区域：在我们的例子中，我们使用简单的2D方块布局。你不一定非得用这种方式，你也可以使用不规则的区域。回想一下棋盘类游戏《Risk》中的国家。你可以在游戏中设计类似于它的寻径关卡。为此，你需要创建一个表格来存储哪个国家与哪个国家相邻还有从一个国家移动到另外一个国家的G消耗。还要有个估算H的算法。接着做的事情就和我们的例子中的一样了。在你向open list中添加项的时候，与以前寻找邻接方块不同的是，你只需要在表中寻找临界国家就行了。
同样的，你可以为一张地形图建立路径点（waypoint）系统。路径点一般是路径（比如一条道路或地牢中的隧道）上的一个断点。作为游戏设计师，你可以事先分配好这些路径点。如果两个路径点之间的直线通路上没有障碍物，它们就被认为是相邻的。就想在《Risk》中做的那样，你可以把这些邻接信息存放到一个查找表（lookup table）中并用它们来向open list中添加项。并且记录下相关的G值（可能用结点之间的直线距离来表示）和H值（可能用结点到目标点的直线距离来表示）。接下来的事按部就班。
Amit Patel写了一篇介绍了其他方法。我在文章中，介绍了一个在斜视角RPG地图中使用非方形搜索区域来寻径的例子。
6.提高搜索速度的窍门：如果你开发自己的A*程序，或者在我给的基础上改写，你会发现寻径占用了大量的CPU时间，尤其是在有大量寻径单元在一个大地图上移动的时候。如果你读过网上的相关文章，你会发现，即使是编写《星际争霸》和《帝国时代》的专家也会面临这样的问题。如果你发现寻径正在使游戏变慢，下面是一些提高搜索速度的建议：
·采用小一点的地图或着更少的单元。
·不要同时对多个单元寻径。相反，把它们放进队列中并分散到游戏的不同周期里处理。如果你的游戏每秒刷新40个周期，没人会发现速度会有差异。但是如果同一时刻如果有大量的单元在寻径，人们就会感觉到游戏的运行速度下降了。
·考虑在地图中使用更大的方块（或者任何你所使用的图形）。这个会减少寻径用的结点数。如果你够猛，也可以开发两套或者更多的寻径系统来应付不同的情况，这取决于路径的长度。专家们就是这么做的，对很长的路径采用大的搜索区域，并在接近目标点时切换到小搜索区域寻径。如果你对这个有兴趣的话，请参看我的。
·对于更长的路径，可以考虑预先计算出几条固定的路径并直接集成到游戏中。
·预先处理你的地图，找出哪一些区域是不可到达的。我把这些区域称为“孤岛”。实际上它们可以是岛或者被墙壁包围住的不可到达的区域。A*有一个缺点，如果你要求电脑要寻找通向那些区域的道路时，它会搜索整个地图，直到所有可通过的方块/结点被处理一边为止。这样会浪费大量的CPU时间。要避免这种情况的发生，只要提前检测哪些区域是可到达的（类似洪水的区域），将这些信息记录在某各个数组中，在寻径的开始检查这些区域。
·在类似迷宫的环境中，把不能连同的区域标记为死角。这些区域可以预置在你的地图编辑器中，或者你够猛的话可以自己开发算法来自动检测这样的区域。给死角上的所有结点一个唯一的数字标志。然后，除起始点或目标点恰好在死角某个结点内时需要额外考虑以外，其他时候你就可以很安全的避开所有的死角点。
7.维护open list：这是A*算法中最重要的部分。每次访问open list的时候，你需要找出F值最低的方块。有几种方法可以实现这一点。你可以在需要的时候保存结点，而在需要找到最低F值方块的时候遍历整个列表。这样做很容易，但是对与长路径搜索来说非常慢。可能的改进方法是，维护一个排好序的列表，每次需要取最低F结点的时候只要取出列表中的第一个项。这是我写代码时最开始使用的方法。
对小地图来说，这样做会有效果，但是不是最快的方法。苛求速度的程序员使用一种叫做二叉堆（binary heap）的方法，这也是我现在在代码中使用的方法。依我的经验来看，这种方法在大多数情况下能够快上2-3倍，而且在搜索长路径的时候速度以几何级数增长（10倍以上）。我的文章相信介绍了这方面的知识。
另一个瓶颈是在寻径时操作你的数据结构的方式。我个人倾向与把所有东西都存储到数组中。虽然结点可以以面向对象的风格动态地产生，记录与保存，但是我发现如此生成和删除物件会带来额外的不必要的开销，使运行的速度边慢。然后，如果你使用数组，你需要在调用之间清除数据。你所需要做的就是在一次寻径调用的最后花点时间清零，特别是当你的地图很大的时候。
我通过创建一个叫做whichlist(x,y)的2维数组来避免这样的开销，数组里面的元素指明了该结点是在open list里或是在closed list里。尝试寻径之后，我并没有清零这个数组。取而代之的是，我在每次寻径调用中重置它的值为onClosedList或onOpenList，每次尝试寻径都给它加上5或其他什么值。这样，算法可以安全的跳过前一次尝试寻径留下来的垃圾数据。我也把类似F，G，H这样的花费存储在数组中。这样，我只要简单地覆盖前面写过的数值，而不用在最后清除数组。
用多维数组来存储出可能会都占用一些内存，但是，以空间换时间。你可以使用你熟悉的方法来处理。
8.Dijkstra的算法：虽然A*通常被认为是最好的寻径算法（看前面的题外话），然后还有一种算法是很有用的。Dijksta的算法本质上和A*差不多，但是它没有启发值（H值一直是0），它通过在每个方向上均匀的扩展来搜索。正如你所想，Dijkstra的算法在找到目标点时需要搜索更大片的区域，所以一般比A*来的慢。
那么，为什么我们要用它？有些时候，我们不知道目标点所在的位置。比如你有一个资源采集单元，它需要采集某种形式的资源。它可能知道哪几个地方有这样的资源，但是它希望采集离它最近的那一块。在这种情况下，Dijkstra的算法要比A*来的更好一些，因为我们不知道哪一个目标点更近。用A*的话我们只能找出每一条的路径做比较才能选择出我们要的路径。我们可能有很多的目的地，我们要寻找它们之中最近的一个目标点，但是我们不知道哪一个更近。
更进一步的阅读
现在你已经对那些进阶概念有了一些基础的了解。我建议你可以开始研究我提供的代码。包中包含了C++和Blitz Basic两个版本的实现。每个版本里面都有大量的注释，因为是很容易能看得懂的。代码在。
如果你不熟悉C++或Blitz Basic，在C++版本中提供两个exe文件。Blitz Basic版本要在的网站上下载并安装了Blitz Basic 3D的演示程序才能运行。一个Ben O'Neill写的联机帮助在。
你也应该阅读一下以下的网页。看完本文后，它们应该显得比较容易理解一些了。
：这篇Amit Patel写的文章被广泛的引用，如果你没读过本文，它对你来说可能会有点小难。尤其值得一看的是Amit本人对A*的观点。
: 该文章由Bryan Stout编写，发表在Gamasutra.com，需要注册才能阅读。注册是免费的，而且该站上有其他很精彩的文章。Bryan用Delphi写的程序帮助我学会了A*算法，也为我的代码提供了不少灵感。其中也讨论了几个A*算法的变种。
： 由Ensemble工作室的专家写的进阶文章，有点难，但相当有趣。这个家伙曾经参与《帝国时代》和《帝王时代》的开发。别指望看完它你就能弄懂一切，但它确实是篇有趣的文章并能给你提供一些好的建议。它讨论了mip-mapping，influence mapping等一些高级的AI寻径话题。
其他一些好的网站：
* * *
我强烈推荐下面的几本书，里面有许多关于寻径和AI的文章。他们也都附送光盘。我已经买了他们，另外，如果你通过下面的连接在亚马逊购买它们，我也能小赚几美分：）[译者注：不是我赚的:(]
如果你恰好写了这方面的例子，我也很有兴趣看一看，可以给我发EMAIL：
祝您好胃口~~
posted on 2005-08-15 19:43 一个人的江湖 阅读(5560)