一个人的江湖

传奇般的WII

一个人的江湖 — Fri, 06 Apr 2007 12:54:00 GMT

之前就很关注这部特别的游戏主机，因为宣传视频里展示的新颖的游戏方式实在很让人动心，但是心里还是有点担心现在的技术能不能完美地实现视频里所宣传的功能。

前几天有机会摸一下WII，很多人凑在一起玩，拿到手的就那么几分钟，所以一直也没有太热的感觉，只是觉得满有意思的。今天终于有机会和它单独相处，谁知道一上手就放不下了，玩了3个多小时，汗都出了不少。因为里面很多的小游戏都是模拟真实的动作，比如打棒球就可以把控制器当棒球棒来挥打，真的很燃烧脂肪啊。关于游戏的控制方式网上有很多视频，可以给大家更主观的感觉。
http://www.maikr.com/kan.aspx?id=0cdea172-7d2d-41bc-a5b3-3c95562385df

其实非手柄控制的游戏一直都有，像PS2的EYETOYS可以根据摄像头前玩家的动作来实现一些诸如搽窗子之类的游戏，这类游戏相对比较简单。而国外有出现过用特殊设备穿戴在身上实现的格斗类游戏，但是这些设备都很昂贵。而WII可以实现全方位的运动，而且价格在3个主机当中是最便宜的。

感觉老任这次真是找对了方向，不去和MS、SONY在图形性能上交锋，要知道SONY，MS每卖一台PS3，XBOX360，都是在亏本，而任天堂每卖一台WII都是在赚钱，而且这种新颖游戏方式更能吸引全年龄段的LU加入到电子游戏的行列中来，事实上有很多报道都正式不少的中老年非玩家都喜欢WII。大批的LU的进入拓展了电子游戏的受众群体，总体销量将得益于此。

另外想了一下可大捞钱的是周边，控制器本身就自带一个扳机形的按钮，如果出个枪托外设能将控制器置入其中，这样就真的有开枪的感觉了，想想这样玩FPS游戏该多让人兴奋哪。再设想一下拿个筒子将控制器包上，只露出A键，哇靠，活脱脱一把光剑哪，用来玩星战类动作游戏爽呆了。再者。。。。不敢想了都，这块做好的话，想不赚翻都难啊。其实原来的名字Revelution比WII更适合它~~

      推荐几款值得一玩的游戏：
      《初次的WII》里面几个小游戏都很搞笑，射击的那个小游戏让我找回FC时代打野鸭的感觉。
      《monkey ball》里面有很多体育游戏和射击类游戏，很耐玩
      《瓦里奥制造》一向BT的游戏系列，这次在WII上实现了更疯狂的游戏方式了。
      《塞尔达传说》传说中的神作，很仰慕，还没接触过。。
      《纸片马里奥》据说4月份会上市，很有意思的游戏，动画
      http://game.163.com/game2002/editor/edit_jianzhi/060510/060510_622996.html

BTW:各位，买台WII吧，保证你的爷奶父母叔伯兄弟妻子儿女都喜欢，御宅族慎买，因为你有可能完全失去到户外活动的理由。。。

最后一次在主页上非技术留念

一个人的江湖 — Fri, 02 Sep 2005 08:22:00 GMT

《七月七日晴》
歌手：许慧欣

说了再见是否就能不再想念
说了抱歉是否就能理解一切
眼泪代替你亲吻我的脸
我的世界忽然漫天白雪
拇指之间还残留你的昨天
一片一片怎么听见完全
七月七日晴
忽然下起了大雪
不敢睁开眼希望是我的幻觉
我站在地球边眼睁睁看着雪
覆盖你来的那条街
七月七日晴
黑夜忽然变白天
我失去知觉看着相爱的极限
我望着地平线天空无际无边
听不见你道别
拇指之间还残留你的昨天
一片一片怎么听见完全
七月七日晴
忽然下起了大雪
不敢睁开眼希望是我的幻觉
我站在地球边眼睁睁看着雪
覆盖你来的那条街
七月七日晴
黑夜忽然变白天
我失去知觉看着相爱的极限
我望着地平线天空无际无边
听不见你道别
七月七日晴
忽然下起了大雪
不敢睁开眼希望是我的幻觉
我站在地球边眼睁睁看着雪
覆盖你来的那条街
七月七日晴
我失去知觉
天空无际无边

[翻译]A*寻径入门

一个人的江湖 — Mon, 15 Aug 2005 11:43:00 GMT

A*寻径入门

原文链接：http://www.policyalmanac.org/games/aStarTutorial.htm

原文更新于：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上的Toward More Realistic Pathfinding 。（免费的，但需要注册）

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倍以上）。我的文章在A*寻径中使用二叉堆相信介绍了这方面的知识。

另一个瓶颈是在寻径时操作你的数据结构的方式。我个人倾向与把所有东西都存储到数组中。虽然结点可以以面向对象的风格动态地产生，记录与保存，但是我发现如此生成和删除物件会带来额外的不必要的开销，使运行的速度边慢。然后，如果你使用数组，你需要在调用之间清除数据。你所需要做的就是在一次寻径调用的最后花点时间清零，特别是当你的地图很大的时候。

我通过创建一个叫做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 Baisc的网站上下载并安装了Blitz Basic 3D的演示程序才能运行。一个Ben O'Neill写的联机帮助在此。

你也应该阅读一下以下的网页。看完本文后，它们应该显得比较容易理解一些了。

Amit's A* Page：这篇Amit Patel写的文章被广泛的引用，如果你没读过本文，它对你来说可能会有点小难。尤其值得一看的是Amit本人对A*的观点。

Smart Moves: Intelligent Path Finding: 该文章由Bryan Stout编写，发表在Gamasutra.com，需要注册才能阅读。注册是免费的，而且该站上有其他很精彩的文章。Bryan用Delphi写的程序帮助我学会了A*算法，也为我的代码提供了不少灵感。其中也讨论了几个A*算法的变种。

Terrain Analysis：由Ensemble工作室的专家写的进阶文章，有点难，但相当有趣。这个家伙曾经参与《帝国时代》和《帝王时代》的开发。别指望看完它你就能弄懂一切，但它确实是篇有趣的文章并能给你提供一些好的建议。它讨论了mip-mapping，influence mapping等一些高级的AI寻径话题。

其他一些好的网站：

* aiGuru: Pathfinding
* Game AI Resource: Pathfinding
* GameDev.net: Pathfinding

我强烈推荐下面的几本书，里面有许多关于寻径和AI的文章。他们也都附送光盘。我已经买了他们，另外，如果你通过下面的连接在亚马逊购买它们，我也能小赚几美分：）[译者注：不是我赚的:(]

如果你恰好写了这方面的例子，我也很有兴趣看一看，可以给我发EMAIL：

祝您好胃口~~

[无聊]发几张图

一个人的江湖 — Sat, 09 Jul 2005 08:58:00 GMT

划时代的武侠巨作

一个人的江湖 — Sun, 22 May 2005 13:36:00 GMT

上个世纪的经典武侠片，还有人记得它的名字否

男一号

男二号

里面的轻功

爬云仙术

天外飞仙

经过两天一夜的拓展训练

一个人的江湖 — Sun, 24 Apr 2005 14:40:00 GMT

累！！！
爽！！！

完~

莎士比亚、猴子和程序员

一个人的江湖 — Wed, 13 Apr 2005 14:52:00 GMT

出个无聊的题*_%...

首先来看个概率论中的著名例子：一个猴子站在打字机旁，假定它随机地敲击各个键，每次击键时，任何符号或空格键被敲击的可能性是相等的，那么在特定的时间内那些猴子打出莎士比亚著作（或大英博物馆中的所有书籍）的可能性有多大。显然，如果一定数量的猴子中每只打出足够多的页数，那么整个这些片断包含莎士比亚著作中的一个连贯的段落的概率是非零的。然而，那个概率极小。即使全世界所有的猴子花一万年的时间，每天各打字8小时，打出的文章包含佛里奥版本的莎士比亚著作中一个连贯的部分的概率也是可以忽略不计的。

接着看看鲁塞尔·马洛尼（Russell Maloney）几年前发表于《纽约人》杂志上的题为《不变的逻辑》（Inflexible Logic）一文中，作者虚构了这样一个故事：6个黑猩猩开始系统地用打字机打大英博物馆中的书籍，一本接一本，毫不犹豫，也不出错。但这些黑猩猩的结局却很悲惨：一个科学家为了维护自己的概率定律而将它们杀掉了。最后一只猩猩在一阵临死挣扎时，“猛然摔在它的打字机跟前。它痛苦地用自己的左手从打字机上拿下刚打完的，佛罗里欧（Florio）写的《蒙田》一书中的最后一页。它摸索着找到一张白纸，将它放入打字机里，然后用一个手指打着，‘《汤姆叔叔的小屋》（Uncle Tom’s Cabin），哈里特·比切尔·斯陀著。第一章……’，然后它也死去了。”

于是，便有了下面的题：
[输入]
C++中的关键字、操作符、括号等语素
可能调用到的函数
包含上面那些函数的头文件列表

[输出]
一个有“点”意义的程序，行数可在100行左右，必须通过编译器的编译

[要点]
在程序中利用上面输入的元素随机的组合出一段代码来，可以在程序中设置相应的潜规则来使随机得到的程序更大概率的通过编译。但规则的应用必须保持一定的随机性，限定死了就不好玩了:b

[结果]
越快的输出一个通过编译的程序质量越好，输出来的程序越有意义越好，代码越符合编码规范越好。。。