主题：初到贵宝地,灌一点游戏开发的东东 -- foundera
家园 初到贵宝地,灌一点游戏开发的东东 游戏设计中的合作
本文阐述了在游戏开发过程中，在合作方面应该注意到的或者说应该做到的事情。也是我持之以恒寻找伙伴的原因。
1. 尤其是在从事某些文学，艺术或者科学性的事业
2. 和敌人合作
回顾电脑游戏工业的初期，一个开发队伍只有少数几个人的现象一点儿也不奇怪。随着游戏的规模和复杂度的发展，游戏开发任务现在往往由30－40个人分担。几个设计者共同为一个游戏工作已成常事。如何使这种合作奏效？尤其在游戏设计者们往往具有强烈个性的情况下。新的技巧是必需的。
我们做过的最好的项目是和其他人合作完成的。最差的，往往也是。当合作达到效果时，它们可以产生一种效果使得每个人都能创造出比个人独自工作时好得多的东西。当合作不奏效时，你会觉得自己处于恶梦之中。。。我们接下来会研究一些会使得合作失败的做法，以及建议一些增加合作成功的可能的方法，我们还会指出什么样的情况下你就该说不或者干脆离开这个项目吧！
从以往的经验中我们已经懂得合作设计时需要注意的五个基本因素。它们是明确分工，互相尊重，达成共识，相辅相成和好的流程。下文我们将会仔细的讨论这些因素，也作为我们在1997年CGDC的讨论的一份材料。
明确分工
为使合作者在一起工作的很好，每个人都必须对自己在项目中的角色有一个明确的认识。很不幸，管理者经常对这一点不够清楚。特别的，设计者的角色在一个互动游戏项目中往往是很有诱惑力的，因而某些管理者发现让团队中的很多人来共同扮演这一角色是颇为有效的办法，这样可以避免他们失望，从而失去兴趣。大家开始可能会很高兴，但是随着没有人知道究竟谁对某部分设计工作具体负责时，问题就产生了。在合作设计中，从一开始就要明确每个参与者的责任和权力，以免产生混淆。
有时这种混淆会在项目经理（制作人）和总设计师（总企划）之间产生。在实现设计思想的程序员和项目经理或者设计师之间往往会产生争吵。后两者可能会拥有有名无实的做出改变的权力，但这其实取决于实现功能的程序员。这种情况可以通过在项目开始时就确定每个人的角色来避免。有很多人参与设计过程往往是很好的事情，前提是要明白这些往往决然不同的看法该怎样有效的汇集在一起，否则肯定一团糟。
因而，确定谁拥有对设计的最终决定权是件好事。这项重任往往落在了项目经理的肩上。如果一个设计师就某个设计上的变化报告项目经理，后者缺乏足够的专业知识，但还是希望对项目有全面的控制，设计师可能会预估这一变化对项目的影响。项目经理可能同意在不影响预算和进度的情况下采取这一方案，他同时也拥有最终否决权。有时项目经理也是总设计师，从而简化了决策流程。在这些情况下，项目经理往往也有要对之负责的人：一个高级经理、另一个主管人员或者，唉，市场部门的头头儿。因此同样的设计决定控制权也必须明确。
设计决定权拥有者的确认使得项目里的其他人员在发生争吵时知道该找谁拍板。如果没有明确谁拥有这项权力，往往会导致美术人员和程序员会从都认为自己拥有决定权的不同的人那里收到截然不同的指示。 这会降低士气，也会影响进度。
另外一个处理方法是确定一个"监护人"。通常这个人是总设计师，但也可能是项目经理、程序员、编剧或者美术人员来最终做出决定。无论怎样，让项目中所有工作人员和相关管理人员全体认同某个人拥有这项决定权是确保良好合作的最重要的步骤。
相互尊重
即使决定了由谁来最终决定设计上的事宜，一个项目仍然需要设计者间的相互尊重才能进行良好。当团队成员可能在某些方面无法彼此尊重，他们也必须在合作相关的方面相互尊重。举个例子，如果一个编剧和一位著名游戏设计师合作，编剧应该尊重设计师游戏方面的知识，而设计师应该尊重编剧的写作能力。如果他们能找到共通点，当然很好，但这不是必要的。有可能出现这样的情况，例如编剧觉得游戏设计师是一个毫无希望的讨厌鬼，而设计师认为编剧粗俗下流，但是他们仍然可能合作得很好，仅仅因为他们尊重对方的专业能力。然而，如果他们中的一位对和另外一位协同工作毫无兴趣，这合作恐怕就得完蛋。当然了，除非这个人确实有我们需要的能力，否则为什么要跟他合作呢？
互相尊重的合作是很好的沟通。如果两个合作者不能彼此尊重，沟通就会被阻碍，他们也无法很好的告诉对方自己的想法。有规律的沟通是非常重要的，无论是通过面对面讨论，例行电话会议或者电子邮件。
达成共识
相互尊重是关键，但是要有效率的合作，他们必须对这个项目的方向达成共识。这个认识可能仅仅是种感觉，也可能是用50页的文件来详细描述，但是核心人员必须对它究竟是什么有个共同的认识。游戏的主题风格是一个重要的，并且需要达成共识的方面。如果一个人倾向于做一个喜剧味道很浓的游戏，然而另外一个人却古板的要命，那恐怕他们就很难同意对方的意见了。而且即使双方都同意要做一个喜剧，你还需要决定要做哪一种喜剧。。。Monty Pythonesque? Marx Brothers? Noel Coward? Oscar Wilde? Saturday Night Live? 猴岛小英雄1代和2代里面的对话和笑话是由三个设计师和一个很有名气的外部作者完成的。因为花费了大量时间在开会讨论游戏风格上面，他们可以达到统一的幽默风格。结果是一个天衣无缝的游戏。就最终产品所要达到的情感方面的影响达成共识是一个不错的开始。
另外一个极其需要达成共识的方面是决定这个游戏到底是怎么玩的。我们看过不少编剧和设计师就游戏故事和角色可以达成共识的例子，但是这离最终带给玩家什么样的游戏还差很远。举例来说，一个人可能彻底坠入了做一个指挥大军在地图上行进的游戏的想法，而另外一个人则需要一个实时战场第一视角的表现方式从而让玩家能更好的融入其中。先尽早地决定基本游戏结构，让所有的合作参与者都认同它，这一点是非常重要的。
但是在你开始实际设计之前，怎么能认同这些事情呢？可以采取一些方法。如果设计是基于已有的角色或者形势，比如一个特许授权开发的产品或者一个系列的续作，这些角色和形势会有助于提供一个共识的基础。在我们以前合作开发的Indiana Jones and the Last Crusade的项目中，已经有三部电影很好的刻画了主角的形象。我们都知道他会说什么，做什么以及不会做什么。如果是一个新角色，就多花些时间去构思他/她吧。创造一个架构宏大的故事，即使其中的大部分内容根本没有在游戏中出现。如果你想尝试一些新东西，参考现在的资料以便可以总结出一个可以用来达成共识的范围。例如，如果所有的合作者都喜欢电影，那么"它看起来会象Blade Runner，但是象Roger Rabbit一样敏感"这样的描述可能比较容易让大家达成共识。
相辅相成
回顾我们做过的众多合作性项目，我们已经注意到拥有可以相辅相成的合作者往往可以做出最成功的结果。有很多次两个具有相似专业技能的人在一起合作得很好，但是如果他们还同时能有各自擅长的领域，就会增强之间的互相尊重，从而促进更好的合作。另一方面，一次个人观念驱动的竞争性冲突可以被调和。当几种同一方面的具有很强创新性的理念碰在一起时往往是很危险的。越来越多的，编剧和设计师达成共识后，编剧主要负责故事架构和角色刻画，同时设计师集中精力于互动非线性的结构和游戏的玩法。
如果两个合作者具有相似的优点，因为他们可以更好的把握项目，从而可以高效地工作。这里可能存在的问题就是一定要确定他们不会有相同的缺点，否则由于缺乏监督，设计中很有可能会出错。具有类似的创造力的合作者可能会因为他们有相互补充的风格而彼此尊重，例如一个循规蹈矩，另外一个是个不停的冒出创新的主意的家伙。
好的流程
前面的四个关键因素讨论完毕，是时候看一下合作的流程了。这里有些事情可以使得工作变得高效而且充满乐趣。
公开的交流是非常重要的。很多项目失败的原因仅仅是参与人员各行其事，没有告诉其他人自己在做什么。定时召开例会是非常有用的，哪怕只是花上几分钟时间凑在一起聊聊，确认一切都进行顺利。
进行信息交互的测试过程是有效的。无论是范例，设计文档，美术作品或者代码，使用最新而且有效的工具来进行共享可以减少不少麻烦。不要以为每个人都能看得懂别人的文档。
明确分工带来的好处之一就是有一条清晰的具有互相理解的影响和责任的指挥链。在某一美术工作整合到项目里面之前由谁来验收？谁来检查对话和显示是否搭配正常？这不仅仅是项目管理的范畴，而是如果合作者们希望做到高效，就必须知道谁负责项目的哪一部分。
让一个人负责对外事务，一个人负责对内事务有助于好的合作关系。特别的，负责对外事务的人，往往是项目经理或者产品经理，将负责预算会议，市场，包装，和公司其他部门的日程安排冲突等等事宜。对内事务负责人，往往是总设计师（陈忾说：我好渴望这种情况在中国适时的运作起来），他的工作集中在项目本身，为实现某些功能而要做出权衡，游戏的玩法等等。在游戏设计合作中有时由不同的人担任这些角色，有时负责对外事务的人本身并不参与设计，但是在对内负责的人群里面将会有一个合作关系。怎样做都可以。
一定要确定合作关系得到了"管理的祝福"。我们讨论过的这些因素大部分都假定人们是真心愿意合作设计的。如果设计师多过一个的话就让大老板觉得不舒服，而且总是拉一个合作者过来讨论问题，只能造成紧张关系。
对争论的解决方法一定要达成共识。可以采用投票，或者设法使得整个团队都毫无疑义的认同，但是一定要在项目偏离正规太多之前让每个人都认同。有时由大家都尊重的第三方来仲裁也不失为一个好办法。
听从你内心的声音
现在还有一个最后的因素来确保你加入的所有项目都能合作良好。听从你"发自内心的声音"。在一个项目刚刚开始，还很容易脱身出去的时候，这一点尤其重要。如果你觉得合作者之间的气氛不大对劲儿，比如大家对项目的期望不尽相同，没有明确的监督人，成功的可能性微乎其微，或者仅仅是你自己觉得"这根本就行不通！"，这样的话你还是早早离开吧（陈忾说：很多人问过我：“为什么去了很多公司，然后又快速的离开？”我想，上面的就是答案了。你要想了解一个公司的开发目标，是无法从公司外的角度去看清楚的，需要具体地到项目中去，才有可能发现项目的问题。而一旦发现问题，你所能做的就很少了。因为国内还没有确定设计师引领项目开发的模式。所以，作为设计者，与其在一个注定不怎么样的项目里挣扎，不如去一个新的地方冒险。我相信，总会有实现梦想的地方。）。
另外一方面，如果直到项目已经开始你才注意到上述的危险，你就不得不做出判断，如果设法去修正这些问题，对于项目是好还是坏。在产品到了Beta版的时候你跑过去跟主程序面对面大吵一番可能会延缓而不是加速项目的完成。
如果，经历这所有的一切，你开始了和其他人合作设计，我们希望你会发现那句老话"人多力量大"在这里能派得上用场，而不是"每人都来添勺羹，结果乱成一锅粥"。
本帖一共被 1 帖 引用 (帖内工具实现)家园 解拆《傲世三国》的图形文件 解拆《傲世三国》的图形文件 出 处：程序人生
《傲世三国》的图片资源都按555与565格式分别存放在555与565两个目录下，图片都是以资源的形式存放在DLL中的，因此我们可以很方便的导出这些资源。粗略的观察了一下这些文件，发现许多都是以xbm开头的，可以肯定这些是图片文件无疑。从观察的结果看，所有这些图片都有一个64byte的文件头。下面我选用了555\res02.dll中的30450资源来进一步观察。文件头如下：
78 62 6D 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 5A 00 00 00 50 00 00 00 10 0F 01 00
1F 7C 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
根据我的经验推测，文件头的数据结构大体是这样的：
struct FILE_HEAD {
BYTE ID[20]; // 图片文件标识="xbm..."
DWORD Width,Height; // 定义图片的宽和高
DWORD ColorMode; // 这个值在555时为10f10，在565时为11010，推测应该是定义颜色模式的
DWORD MaskColor; // 定义透明色的值
DWORD AlphaChannel; // 当图片带Alpha通道时，该值为1。
DWORD ImageOffset; // 当图片带Alpha通道时，该值为图片数据在文件中的偏移量。
BYTE Reserved[20]; // 暂时还没有发现这些值被使用
}
接下来的数据：
40 01 00 00 42 01 00 00 44 01 00 00 46 01 00 00
48 01 00 00 4A 01 00 00 4C 01 00 00 4E 01 00 00
50 01 00 00 52 01 00 00 54 01 00 00 56 01 00 00
58 01 00 00 5A 01 00 00 5C 01 00 00 5E 01 00 00
…… ……
这些数据排列很有规律，一共80个，应该不是图像数据，明眼人一看便知，这些是每一行图像数据在文件中的偏移量，当读入内存的时候这些值就会被加上图像数据的首地址，从而成为指向每一行图像数据的指针。这些对我们解图片用处不大，解的时候可以跳过这些数据。接下来是真正的图像数据：
B4 00 B4 00 B4 00 B4 00 B4 00 B4 00 B4 00 B4 00
B4 00 B4 00 B4 00 B4 00 B4 00 B4 00 B4 00 B4 00
B4 00 B4 00 B4 00 B4 00 B4 00 B4 00 B4 00 B4 00
B4 00 B4 00 B4 00 B4 00 B4 00 B4 00 B4 00 B4 00
B4 00 B4 00 B4 00 22 00 06 00 6A 35 8A 35 49 31
2C 00 0A 00 25 31 E9 51 C9 4D 67 3D C3 20 56 00
…… ……
从刚才的偏移量数据看出，每行的数据量都不相同，可以肯定是压缩的数据。根据我的经验判断，这些图片使用了最简单的只压缩透明色的RLE压缩算法。这个算法对于我们来说是很熟悉的，早在很多年以前（写闪电战机的时候）我就开始使用了，下面简单介绍一下。
第一个WORD数据0xB4，表示连续透明点的长度是180（怎么是180？哦，应该再除2才对），所以应该画90个透明像素点（注意：图片宽度也是90，因此第一行就已经画完了），接着转下一行，又是0xB4，接着转下一行……。下面看这行数据：
2200 0600 6A35 8A35 4931 2C00 0A00 2531 E951 C94D 673D C320 5600
0x22表示画17个透明像素点，0x6表示画3个像素点，像素数据跟在后面0x356A、0x358A、0x3149，接着再是透明点、像素点……直到一行画满为止。至此，这类图片格式就全部解拆完了，。
下面，我们再来看看带Alpha通道的图片格式，这类格式和前面一种差不多，只不过在文件头后面插入了一个Alpha通道，Alpha通道的数据是不压缩的，每个点为一个Byte宽度，因此，只要跳过Width*Height的数据就和上面的处理方法一样了。
由于时间有限，暂时我就只发现了这两种图片格式，可能还有其他没有被发现的图片格式，就靠大家去发现了。所有的数据结构也只是本人主观臆测，未必正确。另外程序我也写出来了，但是我不打算拿出来了，一来考虑到版权保护的问题，二来是想锻炼一下各位的动手能力，如果你有兴趣的话，看了上面的介绍，应该很容易写出解图片的程序。
家园 2D飞行射击中简单的跟踪算法 2D飞行射击中简单的跟踪算法
首先，本文讨论的是很简单的算法。高手莫入。
在飞行射击游戏中，恐怕没有一个游戏不用到跟踪算法的。比如在玩街机的时候，是不是经常挂于BOSS的“跟踪弹”？
这是怎样实现的呢？很简单，只要有高中的一点数学知识就行了。
首先回忆几个三角函数：sin、cos、tan(tg)、arctan(arctg)。
sin(x) ― 对边/斜边。在1，2项限为正，3，4项限为负。
cos(x) ― 邻边/斜边。在1，4项限为正，2，3项限为负。
tan(x) ― 对边/邻边。在1，3项限为正，2，4项限为负。
考虑到游戏里面的坐标系如下所示：
图1
假设敌人子弹的坐标为slug.x，slug.y，子弹的速度为slug.speed（全部是double型）。上面的三角形的斜边就代表子弹的速度，则子弹每次移动的时候座标的改变为：
slug.x+=slug.speed*cos(theta); slug.y+=slug.speed*sin(theta);
在敌人子弹向你发射过来的时候，首先要计算子弹位置与你所在的位置所夹的角度theta。
简单计算就是：
double deltax=player.x-slug.x; // 注意，是以主角位置为起点，在上图中表示就是x1-x0
double deltay=player.y-slug.y; // y1-y0
为了防止在相除的时候分母为0，做一个判断，使分母近似为0，究竟是负的近似还是正的近似呢？这就需要比较子弹和你的Y坐标谁大谁小了。
if(deltax==0)
{
if(player.y>=slug.y) // 子弹需要下移
deltax=0.0000001;
else // 子弹需要上移
deltax=-0.0000001;
}
同理，对deltay作判断：
if(deltay==0)
{
if(player.x>=slug.x) // 子弹需要右移
deltay=0.0000001;
else // 子弹需要左移
deltay=-0.0000001;
}
现在对角度所处的项限作判断：
if(deltax>0 && deltay>0)
angle=atan(fabs(deltay/deltax)); // 第一项限
else if(deltax<0 && deltay<0)
angle=π-atan(fabs(deltay/deltax)); // 第二项限
else if(deltax<0 && deltay<0)
angle=π+atan(fabs(deltay/deltax)); // 第三项限
else
angle=2π-atan(fabs(deltay/deltax)); // 第四项限
其中π取3.1416926…………（呵呵，别忘记近似哦）。好了，现在已经得到正确的方向了，可以计算子弹坐标了。
slug.x+=slug.speed*cos(theta);
slug.y+=slug.speed*sin(theta);
这样，每次子弹移动之前做一下判断，重新计算角度，怎么样？“跟踪弹”出来了吧？
家园 实现一个非线性的故事 实现一个非线性的故事
目 录
1 故事内容
2 故事开始
--------------------------------------------------------------------------------
在这篇文章中，我将通过一个故事来讨论如何做到非线性。
1、故事内容
故事的背景是欧洲中世纪的一个国家，玩家扮演一名骑士，有一个邪恶的巫师绑架走了国王的继承人，你的任务是去打败他，夺回王子。
首先让我们整理一下在这个游戏中所用到的角色。我们有玩家扮演的骑士，他的随从，他的伙伴，王子，邪恶的巫师，以及大量为巫师效力的鬼怪。其它的一些角色并不需要被提及，因为他们基本上只是下角料，与故事的发展没有关系。
2、故事开始
所有的故事都需要一个开头，这个故事的开头是，做为主角的你与你的随从在国王城堡中一个庭院中，你们都刚刚听到王子被绑架的消息，并决定马上出发去拯救王子。
这就是这个故事发展的原因。直到现在为止，玩家对这个故事还了解得不够多，有很多的情节隐藏在后面，玩家有充分地可能去经历，去做一些令人振奋的事，这种模糊的希望使玩家能够沉浸下去。
故事中所涉及的事件，都是有关联的，这就可以做成分支，使玩家可以自由地选择。为了在游戏中实现一个非线性的故事，你并不一定非要非线性的游戏操作方式。因为故事中不同情节的发展依赖于玩家的具体选择。但我们可以想像到游戏操作方式的非线性将会带给玩家更多的自由空间。
2.1 第一个选择
在开始寻找王子的过程后，玩家马上发现王子是被巫师手下一个巨大的妖怪给带走了。这个妖怪并不能够被一般的方法杀死，传说只有用一把神秘的宝剑，才可以杀死怪物。玩家必须作出选择：
A：先去获取这把神秘的宝剑（可能会失去救回王子 宝贵时机）
B：不去拿剑，直接去救王子（那么不可能去杀死怪物）
依赖于玩家在这处的选择，我们需要为故事将来的发展设置二个不同的标志。如果做A，巫师将有足够的时间派遣他的手下去协助看守人质，玩家拿剑返回后将不得不与大量的怪物战斗来作为补偿。做B，玩家将会有一个更困难的任务，就是要想出计策去把怪物锁在牢笼内。
就象你已看到的，这个游戏仅仅刚开始，但是我们已经能够来改变故事的发展过程了，当玩家玩到了一定的阶段，他会发现先前做的选择会如何地影响后来情况的变化。这会使玩家觉得这种选择有意义，合理。这种前后关联的因果关系也是游戏给玩家快乐的一个重要部分。但如果这种关联设计得不合理，那么会使玩家感到迷惑，破坏游戏的沉浸感。
2.2 第二个选择
在离开国王的城堡后，玩家来到一座已被破坏的城镇上，看到巫师的军队正在攻击的一个骑士，而他正是主角以前的一个老朋友，解决了敌军后，得知巫师的军队将要对国王的城堡发动突袭。这时，玩家必须决定：
A：让他返回城堡里来警告国王即将到来的袭击（那么老朋友可能会因再遇到敌军而死亡）
B：让他加入进自己的队伍中，来共同对抗巫师（老朋友可能会在这个过程中出力不少）。如果选了B，那么玩家要面对一个困难的任务 ― 在敌军袭击城堡前去阻击敌军。如果玩家不能有效地牵制住敌军，那么城堡会遭到凶猛的攻击，许多无辜的人会死亡。而作为的补偿是得到了老朋友的帮助，使他在战胜巫师上更有把握。
这个选择是灰色的，因为其中的一个选择会导致多个事件的发生，也使故事产生了更多的分支。不过这个选择的设计很好，因为设计者用人类的道德来使玩家陷身其中，他们必须做出一个抉择来影响游戏中这些无辜的人，如果任务失败了，很多人会死亡，但如果成功了，很多人将幸免于难。这种紧密的联系使玩家沉浸到游戏中去了。
2.3 第三个选择
玩家已经成功地完成牵制敌军任务，准备进入巫师的地堡，这已经接近最终和巫师摊牌的时候了。战胜巫师手下一个头目后，玩家可以把它关起来，或把它杀死。这个小妖怪会试着与玩家做交易，如果饶它一命或把它放出来，它将会帮助玩家来摧毁巫师而且把王子送回城堡。如果玩家决定释放它，小妖怪会遵守诺言，不过结局会改变。如果玩家并不想去杀死巫师，想自立为王，那么另一个选择是杀死头目。这种决定虽然比较细小的，但需要慎重地考虑。在这种情况下，它会对最终的结局产生破坏。你给了你的玩家一个惊异的选择，而它本不应该出现在这种情况下。通过这个选择，主角变成了一个反面的角色，象换了一个人，这个分支选择让玩家感到突兀，而且不合情理
。
结论
我们看到了实现故事改变的三种不同方式，不过还有更多的改变游戏的方式。就我所知道的，《银翼杀手》（WestWood Studios）可能有三个不同特长和性格的主角，玩家根据自己的偏爱来选择主角。这可能是实现非线性的一种好的方式。而不是象上面提到的给玩家多个的选择点。研究非线性故事的实现方法将持续许多年。除了游戏以外，其它媒体所不能实现非线性，非线性将把视频游戏带入主流社会，并证明它的存在价值。我坚信这一点。
家园 国外专家谈游戏制作 国外专家谈游戏制作 瞬间工作室 李波
目 录
1 戏剧手法在游戏中的应用
2 电影语言在游戏中的应用
3 游戏剧本设计
4 多人在线游戏
--------------------------------------------------------------------------------
1998年5月14日，Intel公司在香格里拉饭店组织的发展商会议，由国外一些专家们进行技术讲座。其中交互式软件剧本设计课程，对计算机游戏软件设计的艺术和技术进行讲述。
此次课程的主讲是美国South Peak Interactive公司的Lee Sheldon先生。他从事影视剧本创作20余年，后转为从事游戏设计工作，可以说是经验丰富，对于电影以及戏剧的表现手法在游戏中的应用到了得心应手的地步。
在讲座中，他主要谈到了以下几个方面：
戏剧语言在电子游戏中的应用
电影语言在游戏中的应用
游戏剧本设计
简单说明多用户上网游戏
另外，我还问了Sheldon先生一些问题，具体附录在后。
注：下文的记述是根据Sheldon先生的原意加上我的理解和发挥写成的。
1、戏剧手法在游戏中的应用
1.1 开始设计游戏时如何确定游戏的主题
设计一款游戏，应该注意到具有一般、共同主题的游戏剧本适用于不同的文化背景的游戏者们。比如爱情主题、战争主题等等。容易引起游戏者们的共识与共鸣，对于游戏在不同地区的推广是有好处的。
如果游戏题材比较老旧的话，就应该试图从一个全新的角度来阐述一个古老的故事；或以全新的观念来诠释古老的题材；或以全新的体裁制作古老的题材。做到旧瓶装新酒或者是新瓶装旧酒，不能给游戏者乏味或雷同的感觉。要让游戏者在不同的方面领略到新意。
1.2 如何推动游戏的过程向前发展
在戏剧中，有两个重要因素是推动故事情节的动力：障碍与冲突。
具体应用到游戏中，可以将障碍变成为在游戏过程中，需要游戏者解决的难题；冲突变成为游戏者前进的阻碍，迫使游戏者根据自己目前的状况，想出有效的解决办法。再具体的说明就是障碍是谜题，冲突是战斗。在RPG游戏中，这两种因素应用最为广泛。
恰当的为游戏者设置障碍和冲突，是游戏者有不断克服困难前进的动力，从而带动故事情节向前发展。
1.3 故事的讲述方式
故事的讲述方式有两种：倒叙法和正叙法。
倒叙法是先将游戏者所处的环境给定，先使游戏者处于事件发生后的结果之中，然后再让游戏者回到过去，去自己发现事件到底是怎样发生的，或者阻止事件的发生。最典型的例子是AVG游戏《MYST》。
正叙法就是普通的方式，故事随着游戏者的遭遇而展开，游戏者对一切都是未知的，一切都等待游戏者自己去发现，去创造。一般的游戏都采用这种方式。
1.4 如何设定游戏的主人公
主人公是游戏的灵魂，只有出色的主人公才能使人流连于故事世界中，才能演绎出出色的故事。因此，成功的设定出一名主人公，游戏就有了成功的把握。
游戏中的主人公不一定非要是一名善良、优秀的人不可，也可以是邪恶的，或者是介乎与正邪之间的。
通常邪恶的主人公比善良的主人公更容易使游戏成功。主人公如果能够邪恶得让人虽然厌恶他，但却不能放弃他，让人想看看他到底能够做出什么、或能够遭遇到什么、或下场是什么，就比善良的主人公更好的抓住了游戏者的心。比如电影《沉默的羔羊》中的那名博士，或者是游戏《玛尔寇的复仇》中的玛尔寇。
还要注意一点的是，主人公的设计不要脸谱化、原形化，不要流俗。主人公如果没有自己的独特个性、独特形象，是不可能使游戏者感兴趣的。
1.5 游戏中的叙述角度
一般游戏中，最常用的是两种叙述角度，也可以称之为视角--即第一人称视角和第三人称视角。
第一人称视角是以游戏主人公的亲身经历为叙述角度，屏幕上不出现主人公的形象，是游戏者有“我就是主人公”的感觉，从而更容易使游戏者投入到游戏中。
第三人称视角是以旁观者的角度观看游戏的发展，虽然说是“旁观者清”，但在游戏者的投入感上，不如第一人称视角的游戏。
第一人称视角的游戏比第三人称视角的游戏编写难度大。欧美国家的RPG一般全部是采用的第一人称视角来进行游戏设计的。比如著名的《魔法门》系列。
其实我还是比较偏好第三人称视角的游戏，在第三人称视角的游戏中也可以利用不同的办法来加强游戏者的投入感，比如主人公的名字自己输入、自己挑选脸谱等。从游戏的表现效果来看，第一人称游戏也有它的局限性。
1.6 游戏中的情感与悬念
游戏中的情感因素非常重要，只有人的本性才可以触动人，使游戏者沉醉于这个游戏。作为游戏设计者，首先应该保证自己的设计能够感动自己，才可以说是成功的开始。一部作品如果连作者自己都没有感觉，怎么能够想象它能够打动其他的游戏者呢？
游戏中另外的一个重要因素是悬念。悬念--是游戏中带有紧张和不确定性的因素，不要让游戏者轻易猜出下一步将要发生些什么。加入适当的悬念可以使游戏更吸引人。比如：在一个箱子中放有游戏者所需要的道具，但箱子上加有机关，在开启的同时会爆炸。游戏者不知道箱子中放置的物品是什么，但通过提示，他知道这件物品会对他有帮助。可是他也知道打开箱子会有危险--同样，他也不知道危险是什么。如何即打开箱子有没有危险就成为了他所要解决的问题。这样就在制造悬念的同时，也给游戏者制造了一个难题。
游戏者在游戏中由于并不知道游戏内核的运行机制，因此对于自己的动作结果有一种忐忑不安的期待。在所有的游戏中，游戏者总是通过经验实现对不可预测性的抗争。
从不可预测性上看，游戏可以分为两种类型：一种称为技能游戏，另一种称为机会游戏。前一种游戏的内部运行机制是确定的，不可预测性的产生的原因是游戏设计者故意隐藏了运行机制，游戏者可以最终通过对游戏运行机制的理解和控制（即某种技能）解除这种不可预测性。而后一种游戏中游戏本身的运行机制具有模糊性，具有随机因素，不能通过完全对游戏机制的了解消除不可预测性，游戏动作产生的结果是随机的。
悬念以及由悬念所引起的期待在游戏中至观重要。在游戏中，不能使游戏者的期待完全落空，这样将使游戏者产生极大的挫折感；也不能使游戏者的期待完全应验，这将使游戏失去不可预测性。应该时而使游戏者的期待变成精确的结果，使其增强信心，获得欢乐；时而抑制游戏者的期待，使其产生疑惑，疑惑的时间越长，悬念的情绪就越强烈，建立起来的悬念紧张度越大，由解决引起的情感上的解脱感就越强。
悬念产生的价值不在其本身，而在于随之而来的解脱。悬念及其解除过程实际上与焦虑、释放过程是相对应的。
1.7 游戏的节奏
首先应该明确指出的是游戏中的时间观念与现实中的时间观念有所区别。游戏中的时间由定时器控制。定时器分两种：真实时间（实时）的定时器和基于事件的定时器。
实时的定时器就是类似C&C和DOOM的时间方式。
基于事件的定时器是指回合制游戏和一般RPG和AVG中的定时方式。
也有的游戏中轮流采用两种定时方式，或者同时采用两种定时方式。比如《红色警报》中一些任务关的设计。
在即时类游戏中，游戏的节奏直接由时间来控制，但在其他游戏中，真实时间的作用就不是很明显，这就需要用其他的办法。
在游戏中，尽量让游戏者控制游戏的节奏，而尽量少由设计者来做。设计者控制游戏节奏的方式应该是让游戏者难以察觉的。
比如：在AVG游戏中，调整游戏者活动空间（即ROOM）的大小；调整活动范围的大小（即世界）；调整谜题的难度；调整游戏中工具的种类，都可以起到改变游戏节奏的作用。
在ACT游戏中，可以采用调整敌人的数量；调整敌人的生命值等办法。
在RPG游戏中，除了可以采用与AVG游戏中类似的手法以外，还能调整事件的发生频率；调整游戏中敌人的强度等办法。
一般来讲，游戏的节奏应该是越来越快，越接近游戏的结尾部分，就越是游戏者感到自己正逐渐加快步伐接近游戏的真正尾声。就好象侦破一件案件一样，开始千头万绪，随着逐渐的深入调查，逐渐的排除，越到后来，案情就越明朗化。
另外，决不要使游戏显得冗长。过于罗嗦的进行一个事件的描述会使游戏者失去继续进行游戏的兴趣，要不断的给游戏者以新的挑战和刺激。
1.8 游戏的风格要一致
在一款游戏中，从头到尾保持一致的风格是很重要的。风格一致包括人物与背景的一致，游戏风格定位的一致等等。在一般的游戏中，如果不是游戏剧情的特殊需要，不要使人物说出超过当时历史时期的语言，要注意时代特征。
2、电影语言在游戏中的应用
2.1 铁的法则 ― 摄影机不能跨越轴线
见下图示例：
图1 摄影机不能跨越轴线
当摄影机拍摄两个物体时--比如说是两个面对面对话的人，物体之间的连线称之为轴线。当在摄影机在机位1先拍摄物体2后，下一个镜头应该在机位2的位置拍摄物体1，使物体在屏幕上的方向是相对的，这样即便在镜头剪辑以后再播放，也不会造成方向上的混乱。严禁在机位1先拍摄物体2后，到机位2a拍摄物体1，这样就使人物在屏幕上“一顺儿”了，这是拍摄时的大忌。换句话说，拍摄时严禁跨越轴线。
如果要跨越轴线，也不是不可以，那就一定要让观众能够看见摄影机的移动过程，不要将绕行的过程剪辑掉。这些手法一般在游戏的过场动画中会有所应用。
2.2 电影中的对话
对话在电影中占据了非常重要的位置。一定要保证各人有各人说话的风格，使每个人的性格和特点在对话中表现出来，同时，游戏的主题要在对话中得以体现。对话是体现主人公性格特点的最佳方法。对话不要单调呆板，要尽量夸张一些，也有必要带上一些幽默的成分。游戏毕竟是娱乐产品，让游戏者得到最大的享受和放松才是它最突出的功能。如果不是题材被严格限定于正正经经的严肃题材的话，不妨适当的放松对话的设计尺度，不必完全拘泥于时代和题材的限制。
对话对于体现游戏中各个人物的个性起着至观重要的作用。无论是在戏剧、电影还是游戏中，各人性格在对话的内容上体现得最为突出。
2.3 剪辑在游戏中的应用
很多原先从事影视创作的人员，非常喜欢在游戏中利用剪辑的手法来衔接游戏中的各个场景。其实在游戏中，除了特殊需要，剪辑手法很少应用到实际制作中。因为游戏总是跟着主人公的遭遇来发展的，很少有数线并行的情况发生。不过对于交代剧情和展示全局，剪辑是不错的选择。
2.4 视点在游戏中的应用
同戏剧部分一样，在电影的手法中也有第一人称视点和第三人称视点。要注意一点的是，在同一部游戏中，不要做视点之间的切换--即一会儿用第一视点，一会儿用第三视点，这样会造成游戏者的困惑和游戏概念的混淆。
目前有很多游戏设计就是犯了在游戏中切换视点的毛病，尤其是在游戏中的过关演示动画或游戏中交代剧情的动画中，才用了与游戏中不同的视点。最常见的是游戏全部以第一人称视角进行，但过场全部是第三视角的。
3、游戏剧本设计
3.1 游戏的类型（简单举例）
1）即时战略游戏
2）DOOM类游戏
3）RPG
4）AVG
5）混合类型：融合若干游戏类型的游戏，最具前景的游戏。很可能以后所有的游戏类型全部要由这种游戏类型所代替。
3.2 游戏设计中的一些诀窍
3.2.1 定时器的作用
在游戏中，定时器的作用是给游戏者一个相对的时间概念，使游戏的向前发展有一个参考系统。在游戏设计中，可以将两种定时器混合使用，但不能造成玩家的困扰。
3.2.2 界面的设计
在游戏中，界面应该设计得尽量的简单，易于游戏者理解，要尽量体贴玩家。多采用图象的、符号式的界面设计，少采用单调、呆板的文字菜单方式。而且也不一定是菜单式的，要更新界面设计的观念。
3.2.3 游戏中的真实与虚构
游戏者在玩游戏时，主要是可以体验不同于生活的历程，得到心灵上的解放。所以游戏的世界可以是虚构的，但游戏中的人物、感情等东西则必须是真实的。游戏的本质核心要贴近生活，但游戏的题材可以是各种各样的。
3.2.4 设计道具
道具的设计要注意合理。不可能将一辆坦克装到自己的背包中去。另外注意的是思考要全面。比如在游戏中，游戏者需要将一枚钉子钉进墙壁中，那么他需要一把铁锤，这也是游戏设计者设计的难题之一。可是如果这是在旁边有一块石头可以捡起来，在现实生活中，我们是可以用石头钉钉子的，那么在游戏中，你也应该允许游戏者使用石头在钉子上，而不能在游戏者使用石头在钉子上时，出现“喔，你不能这样使用”的提示，从而必须让游戏者按你所设计的方式进行游戏，这是不合理的。如果你的设计非让游戏者找铁锤不可，那么你就不要给他石头。
有一点要值得游戏设计者十分重视的是：你的任务是尽量帮助游戏者，而不是百般刁难他们。
3.2.5 RPG游戏设计的误区
RPG游戏中最常见的两个误区是：死路和游荡。
死路指游戏者将游戏进行到一定程度以后，突然发现自己进入了死路，没有可以进行下去的线索和场景了。通常出现这种情况是因为游戏设计者没有做到设计全面，没有将所有游戏的可能流程全部设计出来，而游戏者又没有按照游戏设计者所规定的路线前进，从而造成了在游戏过程中的死路。
游荡指游戏者在广阔的地图上任意移动而难以发现将游戏进一步发展下去的线索和途径。这种现象在表现上很类似于死路，但两者有本质的不同。解决游荡的方法是在故事发展到一定程度的时候，就缩小世界的范围，使游戏者可以到达的地方减少；或者使线索再更加明显，给予更多的提示，让游戏者能够轻松的找到自己的目标。
3.2.6 游戏的交互性与非线性
交互性指游戏对游戏者在游戏中所做的动作或选择有反应。举个很简单的例子，当一名英雄到达一座城镇中后，城中没有人知道他，但当他解决了城镇居民所遇到的难题后，他在城镇中应该就成为了一名知名人士。居民们见到他以后会有反应。还有例子就是，当主人公帮助了一名NPC后，这名NPC以后见到主人公的态度应该有所不同。更加完善的设计是给主人公加上某个参数，使他一系列的所作所为，最后影响到游戏的进程和结局。
非线性指游戏应该是开放时的结构，而不是单纯的单线或是单纯的多线制。即游戏的结构应该是网状，而不是线状或是树状。即游戏中的分支之间允许互相跳转，不是单纯的树状。
线状结构 线状结构 网状结构
3.2.7 游戏中的奖励和隐藏设计
游戏进行到一定程度要给游戏者一些奖励，比如漂亮的画面、精彩的过场动画甚至是有用的道具等在游戏过程中得不到的东西。与奖励类似的是游戏中的隐藏设计，比如Cheat Mode、无敌密码还有隐藏关卡、隐藏人物等设计。这些设计非常有意思，也很有必要加上，但是要注意这些设计不要影响游戏的正常进程，毕竟它们是属于噱头的范畴。
3.2.8 关于游戏中的死亡
要让游戏者从自己的死亡中学到东西，死亡这种惩罚措施才是有益的。
3.2.9 游戏中的对话
游戏中的对话种类分3种：
1）无对话游戏：例如MYST
2）有限对话游戏：例如Diablo
3）自然对话游戏：
对话的设计要带有情绪性，才能明确的让游戏者做出他想做的选择。
如果游戏者选择对话的一个，那么其他话题将消失，以后的话题是有他所选择的第一个引发的，不要让游戏者重复的看见以前的话题。
好的游戏设计者应该能够写出出乎游戏者意料的对话。
对话不要单调的重复，一般要有50句左右的常用无意义的对话，它们之间互相组合，才可以是游戏者不觉得对话单调。不要遇到某个NPC的话总是：“你好”、“你好”，而尽量要做到每次不同。
3.3 游戏设计者与其他部门人员之间的合作
3.3.1 如何合作
设计者超前的设计如果能够与编程人员合作恰当，能够创造出惊人的效果和成功的游戏 在编程人员水平不足的情况下，双方要相互协调，达成一致的结果，能够让双方都能接受。
组员中每个人对于游戏都有自己的想法，设计人员要充分采纳建议中好的部分，但一定要有一个明确的主设计思想和一个能够为整个游戏负责的人，当出现不一致的情况时，他可以有最终决定权。
3.3.2 游戏制作的关系
图3：游戏制作的关系图
游戏制作的三方面可以是一个稳固的三角形，这个三角形可以沿中心旋转，三方面任何一方都可以处于顶点位置，即以任何一方作为游戏制作的侧重点，都有可能制作出一款好游戏。
4、多人在线游戏（MUD）
4.1 理想的MUD结构
图4：理想的MUD结构
图中的大圈表示整个游戏世界，小圈表示有意思的事情的发生地点，其他的空白地方代表世界中的原野、城镇、乡村……游戏者在世界中不受限制，可以任意移动，随意触发事件。事件与事件之间没有必然的联系，但如果某件事件发生了以后，会对整个世界造成影响，比如其他地方的人们知道了事件的发生，从而对游戏者改变态度。
4.2 混沌理论
所谓混沌理论应用在游戏中，指事件接近随机的发生，但实际上是有规律可循的。
Lee Sheldon先生对此有他自己的一个理论：“糟糕的一天”理论。
比如，以下事件发生对你是有影响的：
1 领带皱了
2 和同事吵架了
3 被领导斥责
4 没有中午饭吃
5 钱包丢了
6 车子坏了
…… ……
这些事情可以在你的任何一天发生，但你又不知道它们什么时候发生，将要发生什么，但一旦它们发生了，肯定会对你的情绪有影响，而且发生的件数越多，对你的情绪影响就越大。当它们发生的次数足够多的时候，你就会认为你度过了“糟糕的一天”。在游戏中的情形也类似。游戏者不知道他将会遇到什么，如果遇到一定数量的事件，就可以让游戏者有感觉了。
结 语
目前，国内的游戏设计者们基本全部是从玩家们成长起来的，大家对游戏制作热情有余而经验、理论不足。所以我认为象这种讲座对我们游戏设计者来讲，是非常有必要的。由国外有经验的游戏设计者从理论到实际向我们讲述游戏的设计，对我们提高游戏的设计水平大有裨益。
实际上，游戏设计是一门非常特殊的艺术，它要求就业者有较高的综合素质。不仅要有创造力、文学功底，甚至对于电影、戏剧、历史、文化等都要有一定程度的根底，最好还对编程和美术有一定的了解，这样才能成为一名成功的游戏设计人员。目前国内业界流传着这样的话：“会编程的当程序员，会画画的当美工，什么都不会的当策划。”这在一定程度上反应了目前大陆游戏制作人员的情况，也指出只有游戏设计是非专业人员在从事这一份工作。我们在痛心的同时，一方面通过自己的努力，自己摸索前进；一方面也在迫切的寻找任何可以提高我们专业水平的机会。
家园 游戏Loading画面的实现 游戏Loading画面的实现
当游戏在必须调入大量的资源或者复杂的初始化时,这就需要用到Loading画面和用户耐心的等待...
实现思路如下,当开始等待时,起动一个线程接管画面的绘制,同时用一个全局变量控制绘制的百分比,至于绘出来的是一个弹匣在装子弹(命运战士的load画面)还是一个被点燃导火索的炸弹(盟军敢死队III)就完全由你决定了,设全局变量 g_iPrecent的最大值为100,如果你够有耐心的话,你可以load完一幅图片替他++一次,这就完全靠你的感觉,或者你可以先TimeGetTime在调试框内输出Load这些资源需要的时间...然后分配这个分成了100份的时间段...
下面演示一个很简单的颜色块进度条
UINT ThreadProc(LPVOID param )
{
SHAREDATA *pData=(SHAREDATA*)param;//从参数里选择数据指针
while(g_bShowLoadPrecent)//此变量判断是否load完毕
{
(*(pData->pDisplay))->DrawRect(CRect(262,370,762,398));//方块
(*(pData->pDisplay))->FillColorRect(CRect(262,370,pData->iLoadPrecent*5+100,398),RGB(0,255,0));//显示load的百分比
(*(pData->pDisplay))->PrintText(480,375,"ＬＯＡＤＩＮＧ???",RGB(255,0,0));
(*(pData->pDisplay))->Present();
Sleep(10);
}
return 0;
}
家园 游戏鼠标操作的思考 游戏鼠标操作的思考 出 处：GameRes.com
常规的游戏都是在进行屏幕更新的时候再进行鼠标绘制，一旦FPS降低，鼠标的控制将非常的困难，这点相信大家都遇到过，这次想和大家讨论的就是如何让鼠标操作更贴切，更顺畅。问题如何解决？相信我们每天在使用Windows，Windows在磁盘操作，或者CPU繁忙的时候都能保持鼠标的操作顺畅，我们的游戏完全可以学习Windows的做法来让我们的游戏鼠标操作更为方便。
我们先来说说Windows实现鼠标的做法，按照我的观察，Windows的鼠标应该是通过多线程来实现，而且鼠标线程的优先级非常之高，并且鼠标在屏幕上是使用局部更新，知道了原理，我们就可以开始动手实现我们的游戏鼠标了。首先，我们必须创建出我们可爱的鼠标线程，让我们的鼠标拥有较高的优先级，这样才能最大限度让鼠标灵活，参考如下代码：
// 我们的鼠标线程
DWORD WINAPI ThreadProc( LPVOID lpParameter )
{
... // 实现鼠标更新的部分代码
}
// 创建我们鼠标线程，详细请参考多线程编程文章
thread = CreateThread(NULL, 0, ThreadProc, 0, 0, &g_dwMouseThread);
// 提高线程的优先级
SetThreadPriority(thread, THREAD_PRIORITY_TIME_CRITICAL);
这样，我们的线程就创建完毕了，接下来我们来看看如何进行屏幕的局部更新，我们的游戏（2D）一般都是运行在DirectDraw的环境下，要进行屏幕的局部更新我们需要对主表面进行直接操作，可能你会想到，万一我们在进行鼠标更新的同时，游戏主线程也在对主表面进行如页面翻转等操作，一但这样，这将产生无法预料的结果，为了避免这种情况的产生，我们还必须进行双线程的同步处理，说了那么多废话，来看看我们如何实现：
// 用来标记鼠标进程是否进行
bool g_bMouseThreadRun = true;
// 用来处理同步，此类属于MFC线程处理部分，具体请参考MSDN
CCriticalSection critsection;
// 鼠标处理实现线程部分
DWORD WINAPI ThreadProc( LPVOID lpParameter )
{
// 进行鼠标线程的内部循环处理
while(g_bMouseThreadRun)
{
// 为了能进一步节省鼠标线程所消耗的系统资源
// 我们使用了DirectInput的鼠标事件响应操作
// 具体实现参看DirectInput的鼠标处理部分
DWORD dwResult = WaitForSingleObject(g_hMouseEvent, INFINITE);
if(dwResult == WAIT_OBJECT_0) // 有鼠标事件发生
{
// 重新获得鼠标的位置信息
// 此处非常重要，用来作为与屏幕刷新的同步处理
// 这里将线程锁定，使主线程无法进行屏幕刷新操作
critsection.Lock();
if(检测鼠标位置是否有更新)
{
// 恢复原鼠标位置的图象 bakbuffer <- save back image
// 保存鼠标将绘制部分的背景图象 save back image -> bakbuffer
// 在新位置绘制鼠标 draw mouse image
}
// 释放线程
critsection.Unlock();
}
}
}
完成了我们的鼠标线程，接下来我们来设计我们的屏幕刷新部分，此处要注意两个问题，一个是与鼠标进程一样的同步问题，还有就是实现对局部更新时的背景图象保存缓冲的更新，一但屏幕刷新，背景难免会产生变化，那此时我们在鼠标线程中所保存的局部图象数据（bakbuffer）将是无效错误过时的数据，所以，我们必须对局部图象保存数据进行与背表面（BackSurface）进行匹配处理，并且将鼠标图象绘制到屏幕上，参看如下：
// 屏幕刷新函数
HRESULT Present()
{
// 同上，为了满足同步需要
// 如果有其它线程调用了Lock()，那此处将处于等待状态
// 直到其它线程Unlock()，此函数才将返回。
critsection.Lock();
// 对鼠标线程所保存的局部图象数据（bakbuffer）
// 进行与背景的匹配操作 save BackSurface image -> bakbuffer
// 绘制鼠标到屏幕上，防止鼠标被背景覆盖
... // 屏幕刷新部分
// 恢复线程锁定
critsection.Unlock();
}
关于线程的释放，这里我们只需要简单的将g_bMouseThreadRun这个全局变量设置为false，这样线程就能自动退出，不过注意，为了防止鼠标线程还未退出，主线程已经将部分关键数据释放造成错误，最好能让主线程停止一会，以便鼠标线程的正确退出。
最后，我们来谈谈这种方法的利弊，优点很明显，可以让鼠标操作更为顺畅，缺点，使编程复杂化，而且多少会影响些主线程的性能。说了那么多，有兴趣的朋友可以去下载我的HoHo游戏引擎，里面有全部原代码，还有附带的实现例子。
家园 飞行射击游戏中的碰撞检测 飞行射击游戏中的碰撞检测
在游戏中物体的碰撞是经常发生的，怎样检测物体的碰撞是一个很关键的技术问题。在RPG游戏中，一般都将场景分为许多矩形的单元，碰撞的问题被大大的简化了，只要判断精灵所在的单元是不是有其它的东西就可以了。而在飞行射击游戏（包括象荒野大镖客这样的射击游戏）中，碰撞却是最关键的技术，如果不能很好的解决，会影响玩游戏者的兴趣。因为飞行射击游戏说白了就是碰撞的游戏――躲避敌人的子弹或飞机，同时用自己的子弹去碰撞敌人。
碰撞，这很简单嘛，只要两个物体的中心点距离小于它们的半径之和就可以了。确实，而且我也看到很多人是这样做的，但是，这只适合圆形的物体――圆形的半径处处相等。如果我们要碰撞的物体是两艘威力巨大的太空飞船，它是三角形或矩形或其他的什么形状，就会出现让人尴尬的情景：两艘飞船眼看就要擦肩而过，却出人意料的发生了爆炸；或者敌人的子弹穿透了你的飞船的右弦，你却安然无恙，这不是我们希望发生的。于是，我们需要一种精确的检测方法。
那么，怎样才能达到我们的要求呢？其实我们的前辈们已经总结了许多这方面的经验，如上所述的半径检测法，三维中的标准平台方程法，边界框法等等。大多数游戏程序员都喜欢用边界框法，这也是我采用的方法。边界框是在编程中加进去的不可见的边界。边界框法，顾名思义，就是用边界框来检测物体是否发生了碰撞，如果两个物体的边界框相互干扰，则发生了碰撞。用什么样的边界框要视不同情况而定，用最近似的几何形状。当然，你可以用物体的准确几何形状作边界框，但出于效率的考虑，我不赞成这样做，因为游戏中的物体一般都很复杂，用复杂的边界框将增加大量的计算，尤其是浮点计算，而这正是我们想尽量避免的。但边界框也不能与准确几何形状有太大的出入，否则就象用半径法一样出现奇怪的现象。
在飞行射击游戏中，我们的飞机大多都是三角形的，我们可以用三角形作近似的边界框。现在我们假设飞机是一个正三角形（或等要三角形，我想如果谁把飞机设计成左右不对称的怪物，那他的审美观一定有问题），我的飞机是正着的、向上飞的三角形，敌人的飞机是倒着的、向下飞的三角形，且飞机不会旋转（大部分游戏中都是这样的）。我们可以这样定义飞机：中心点O(Xo,Yo),三个顶点P0(X0,Y0)、P1(X1,Y1)、P2(X2,Y2)。中心点为正三角形的中心点，即中心点到三个顶点的距离相等。接下来的问题是怎样确定两个三角形互相干扰了呢？嗯，现在我们接触到问题的实质了。如果你学过平面解析几何，我相信你可以想出许多方法解决这个问题。判断一个三角形的各个顶点是否在另一个三角形里面，看起来是个不错的方法，你可以这样做，但我却发现一个小问题：一个三角形的顶点没有在另一个三角形的里面，却可能发生了碰撞，因为另一个三角形的顶点在这个三角形的里面，所以要判断两次，这很麻烦。有没有一次判断就可以的方法？我们把三角形放到极坐标平面中，中心点为原点，水平线即X轴为零度角。我们发现三角形成了这个样子：在每个角度我们都可以找到一个距离，用以描述三角形的边。既然我们找到了边到中心点的距离，那就可以用这个距离来检测碰撞。如图一，两个三角形中心点坐标分别为（Xo,Yo）和(Xo1,Yo1),由这两个点的坐标求出两点的距离及两点连线和X轴的夹角θ，再由θ求出中心点连线与三角形边的交点到中心点的距离，用这个距离与两中心点距离比较，从而判断两三角形是否碰撞。因为三角形左右对称，所以θ取-90～90度区间就可以了。哈，现在问题有趣多了，-90～90度区间正是正切函数的定义域，求出θ之后再找对应的边到中心点的距离就容易多了，利用几何知识，如图二，将三角形的边分为三部分,即图2中红绿蓝三部分，根据θ在那一部分而分别对待。用正弦定理求出边到中心点的距离，即图2中浅绿色线段的长度。但是，如果飞机每次移动都这样判断一次，效率仍然很低。我们可以结合半径法来解决，先用半径法判断是否可能发生碰撞，如果可能发生碰撞，再用上面的方法精确判断是不是真的发生了碰撞，这样基本就可以了。如果飞机旋转了怎么办呢，例如，如图三所示飞机旋转了一个角度α，仔细观察图三会发现，用（θ-α）就可以求出边到中心点的距离，这时你要注意边界情况，即（θ-α）可能大于90度或小于-90度。??罗嗦嗦说了这么多，不知道大家明白了没有。我编写了一个简单的例程，用于说明我的意图。在例子中假设所有飞机的大小都一样，并且没有旋转。
/////////////////////////////////////////////////////////////////////
//example.cpp
//碰撞检测演示
//作者 李韬
/////////////////////////////////////////////////////////////////////
//限于篇幅，这里只给出了碰撞检测的函数
//define/////////////////////////////////////////////////////////////
#define NUM_VERTICES 3
#define ang_30 -0.5236
#define ang60 1.0472
#define ang120 2.0944
//deftype////////////////////////////////////////////////////////////
struct object
{
float xo, yo;
float radio;
float x_vel, y_vel;
float vertices[NUM_VERTICES][2];
}
//faction/////////////////////////////////////////////////////////////
//根据角度求距离
float AngToDis(struct object obj, float angle)
{
float dis, R;
R = obj.radius;
if (angle <= ang_30)
dis = R / (2 * sin(-angle));
else if (angle >= 0)
dis = R / (2 * sin(angle + ang60));
else dis = R / (2 * sin(ang120 - angle));
return dis;
}
//碰撞检测
int CheckHit(struct object obj1, struct object obj2)
{
float deltaX, deltaY, angle, distance, bumpdis;
deltaX = abs(obj1.xo - obj2.xo);
deltaY = obj1.yo - obj2.yo;
distance = sqrt(deltaX * deltaX + deltaY * deltaY);
if (distance <= obj.radio)
{
angle = atan2(deltaY, deltaX);
bumpdis1 = AngToDis(obj1, angle);
return (distance <= 2 * bumpdis);
}
ruturn 0;
}
//End//////////////////////////////////////////////////////////////
上面程序只是用于演示，并不适合放在游戏中，但你应该明白它的意思，以便写出适合你自己的碰撞检测。游戏中的情况是多种多样的，没有哪种方法能适应所有情况，你一定能根据自己的情况找到最适合自己的方法。
家园 浅谈RSLG类游戏的人工智能 浅谈RSLG类游戏的人工智能
今天我们来看看关于RSLG人工智能的设计方式。
网络上的网友问到，到底在设计人工智能的时候，是如何来决定出每一行判断式的重要性。其实笔者可以很轻松的告诉各位，在设计人工智能的时候，先想想自己是如何去思考的，然后就依自己认为的重要程度来划分每一行判断式的重要性。这种设计方法的优点就是会相当的“人性化”，设计者很容易就可以在游戏中看到电脑以自己的思考方式去进行各项行动，但是相对的缺点就是若是设计者的本事很差，那么人工智能所表现出来的一定也会很差，因为这样子的人工智能完全会反映出设计者的思路。由于这种设计方式所表现出来的是设计者的思路，因此在一些国外的西洋棋游戏中，设计公司经常会和某些高段的棋手配合，让他们来提出各项的建议，使整个游戏的人工智能更加精确，这就是为什么他们会这样做的原因。
但是现在问题又来了，西洋棋游戏可以这样作，战略游戏怎么办呢？有那一个人是真正的战略天才呢？因此笔者在这里提出一种比较法让各位能够了解设计时会碰到的问题。我们就以战略游戏为例好了，也就是目前市面上最流行的所谓RSLG。在游戏中，当一名电脑控制的角色要行动的时候，它需要考虑以下的几件事情：
行动范围内有没有可以攻击到的敌人。
移动到地理位置较好的地方。
生命是不是已经低到会死的地步。
本身是不是拥有什麽特殊的能力可以使用。
以上是笔者粗略的将可能会发生的情况归类成四项，现在我们就一项一项的来看看。首先是第一项的行动后可以攻击到敌人，光是这一个情况我们就必需要做比较仔细的推算，像是不是只有一名可以攻击到的敌人？若是不只有一名可以攻击到的敌人时，要怎么挑选攻击的目标？以及这样的攻击是不是可以将敌人击毙？是不是要以可以在这一次就击毙的敌人为目标？以及在这一次攻击之后是不是会在下一个回合就遭到敌人的回击等等。如果先将这些情况加以判断，那么可能会归类出以下的几条判断式：
A.若是只有一名可以攻击到的敌人，那么目标就是它。
B.若是有数名可以攻击到的敌人，那么选择最弱的一名。
C.若是有可以在攻击后击毙的敌人，那么它会是目标。
D.在攻击后在多少名敌人的攻击范围内。
还记得上篇文章中笔者曾经提过条列式以及积点式两种人工智慧的设计方式吗？现在我们就以这两种方法来看看关于这一部份的判断式重要性。以笔者主攻的眼光来看，若是有一名敌人可以被击毙，那么这名敌人一定是最重要的目标，接下来才是攻击最弱的敌人，接下来是可以攻击到的敌人，最后才去判断会进入多少敌人的攻击范围内。因此这四条判断式若是以条列式的判断法来排序的话，将会是以下的情况：
C > B > A > D
在这样子的设计下，这些由人工智能所控制的角色将会展现出相当强悍的主攻个性，就算是这一次的攻击后可能会遭到敌方的围攻也毫不在乎。若是各位读者觉得自己并不喜欢由人工智能控制的角色会这样子行动，希望它们能够适当的避开一些会遭到敌人围攻的情况，那么判断式的排列顺序可能会变成：
C > B > D > A
在这样的情况下由人工控制的角色不会一看到有可以攻击到的敌人时，就会像疯狗似的追着打，而会考虑一下这样子的行动会不会就遭到敌人的围攻。但是当有敌人会被击毙，或是生命相当低的时候，就会不考虑那么多了。如果各位读者觉得这样子还是不好，那么也可以将判断式的排列顺序改成如下：
D > C > B > A
在这样的情况下，由人工智能控制的角色将会相当的小心，就算是可以将敌人击毙，但是若在下一回合有被其余的敌人围攻的可能，就不会发动攻击。
接下来我们看看以积点式来设计的话，会是什么样子。同样的判断式用积点式来设计的话，就必需要给每一行算式不同的积点，但是同时必需要将算式做一点修正，因为在积点式中会有复数计算的情况发生，因此这些判断式会变成：
A.可以攻击到一名敌人的位置。
B.可以攻击到的敌人中最弱一名的位置。
C.攻击时可以击毙敌人的位置。
D.一名敌人的攻击范围内。
各位读者可以看到，其中的第四条就是可能会复数计算的。在程序进行判断的时候，这一条可能会因为有多个敌人角色都合乎这个条件，而导致积点的重复计算，因此若是重复计算的次数够多了之后，反而可以将原本一些有利的情况抵消。以前面的这四条算式来举例，若是A的积点是+2、B的积点是+4、C的积点是+8、D的积点是1，那么当一个地点虽然可以将一名敌人击毙但是又会被五名敌人围攻的话，那么这个地点的重要性就会低于一个生命力较低的敌人的位置。也由于积点式的计算方式比较精密，因此人工智能所控制的角色就不会那么的死板，而会显得比较聪明。虽然条列式的作法可以用增加判断式的办法来达到相同的目的，但是比较起来就是差了些。
由以上的这个例子中，我们可以看到不论是一种人工智能的设计方式，整个人工智能的表现都是控制在设计者的手上。条列式表现在判断式的排列顺序，而积点式表现在积点数的不同，这些都是人工智能有“人性”的地方。
--------------------------------------------------------------------------------
额外的讨论
网络上有网友问到，像笔者在上篇文章中拿宾果作说明，但是并没有很详细的以实例说明，所以他实在是不明白为什么在那篇文章中会说(No A) = 4 x 2 > (No B) = 7 x 1。因此现在笔者就将那一篇文章的范例拿出来详细的解说一下。
首先各位看看以下的这个积点表，在这个表中列出了各种情况的重要性。至于为什么积点设定为这样，也就是要让积点真正的能够发挥作用：
判断式 绩点
划一个号码後能够完成一条线 31
划一个号码後在这一条线中出现四个点 15
划一个号码後在这一条线中出现三个点 7
划一个号码後在这一条线中出现两个点 4
划一个号码後在这一条线上只有一个点 1
现在我们看看下面的这个宾果盘，上面的那些「 」符号表示这个地点的数字已经被划掉了。
宾果盘
6 11 16 21
12 17 22
3 8 13 18 23
4 9 14 19 24
10 15 25
现在各位看看这个宾果盘，有两条已经有三个点的线以及两条有两个点的线，因此现在应该要划那一点比较好呢？我们就用上面的那积分表来计算每一个点的重要性，可以得到以下的数值：
o 03:9+1=10
o 04:9+1=10
o 06:3x2=6
o 08:3+1=4
o 09:3+1x2=5
o 10:5+3=8
o 11:3+1=4
o 12:5+1=6
o 13:5+3+1x2=10
o 14:3x2=6
o 15:5+1=6
o 16:3x2=6
o 17:5+3x2=11
o 18:3+1=4
o 19:3+1=4
o 21:3x2+1=7
o 22:5+1=6
o 23:3x2=6
o 24:3x2=6
o 25:5x2+1=11
从这些算式中，我们可以看到若是划下17或是25将可以赚得最多的积点，因此这两个数字就是我们现在要考虑的。接下来再以这两个数字在宾果盘上的重要地位来判断，25的位置要比17要好，因此就可以决定划下25这个数字。这种计算方式就是积点式的典型算法，人工智能会将整的盘上的所有数字都做一番推算，然后才选出最好的一点。
网友还问到，在上一次的文章中笔者曾经说过积点式的人工智能在进行判断的时候为什么会花掉比较多的时间。以下来说明：
各位读者可以想想看，若是每一格的计算需要花掉一分钟的话，那么在积点式的判断中，每一次不论如何的行动，都需要花掉相同的时间。而条列式的判断方式会因为当时判断的位置不同而略有不同。或许各位读者会说，不过是几个步骤而已嘛，时间上能够差多少？但是各位不要忘了，在这篇文章中笔者只不过是举例，所以看起来判断式好像不多，但是在真正游戏中的人工智能却不只是这么短短几行的判断。试着想想看，若是每一行判断式是十秒钟，那么当判断式一多了之后会是怎么样呢？
这一次再向各位读者解释人工智能的运算方式，希望各位读者都能够看得懂。
家园 电脑AI浅谈 电脑AI浅谈
一说到电脑AI（人工智能），就会有人认为它是高深莫测东西。其实并没那么复杂，电脑AI其实是一组if语句。各类型游戏有各类型的AI，RPG（冒险类）游戏的AI最简单，只要用函数产生随机数在对攻击对象取余即可，稍微复杂点的也只增加了道具、魔法攻击，其AI性质都是一样的。例如：
attack(((unsigned)biostime*rand())%3);/*电脑攻击函数*/
这是一个虚拟的函数，代码省略了。我们关心的只是它的入口，我们定义它的入口为要攻击的对象。选择对象使用了随机数与时间共同工作，这样敌人就在3个攻击对象中随机地选择攻击对象了。
在这个语句中，没有使用if选择语句。在这个语句中，我方3个对象受攻击的概率是均等的，其实我们还可以将电脑AI提高一下，让电脑选择我方最弱的对象攻击的机率提高一下。程序改为：
int i,leastblood=20000,weakest;/*leastblood存储最弱对象的血量（初始化为一个比所有对象的可能血量都大的值），weakest存储最弱对象的代号*/
for(i=0;i<3;i++)
{ if(blood[i]<leastblood)/*blood数组为已知的我方对象的血量*/
{leastblood=blood;weakest=i;}
}
i=((unsigned)biostime*rand())%4;
switch(i)
{ case 0:
case 1:i=leastblood;break;
case 2:i=(leastblood+1)%3;break;
case 3:i=(leastblood+2)%3;break;
}
attack(i);
这样，最弱对象受攻击的机率就提高到了1/2，哈，电脑变聪明了。电脑AI设计是不是很简单？其实电脑AI有深有浅，这只是一个最简单的而已。要深奥，只不过是把制约的条件增多罢了。
相对来说，RPG游戏AI是最容易设计的。其次是SLG游戏，SLG游戏电脑AI一般遵循的规则有：最弱对象攻击原则、就近攻击原则、最大攻击力原则。在这三个原则中，排在最先的是就近攻击原则，即电脑对象要攻击，则向距离该对象最近（最省MP）的对象靠近攻击。排在第二的是最弱对象攻击原则，在可以攻击到的对象中，选择最弱的对象进行攻击。排在第三的是最大攻击力原则，如果电脑选中了一个攻击目标，则会使用电脑对象能使用的最大攻击力的方式去攻击。你可能会问，知道电脑如何行动了，那玩游戏对电脑行动不是了如指掌了？不，我不是说过AI的深度与制约条件有关吗？制约电脑行动的条件远不止这些。如电脑游戏就有一种攻击指定目标的玩法。在这种模式下，电脑优先攻击的就是你指定保护的目标了。而且，如果加入魔法机制，电脑的行动就不光是攻击了，而且要定义使用魔法的条件，程序将更为复杂。
再谈谈影响电脑AI的状态的游戏脚本，游戏脚本就跟乐器演奏的乐谱一样，影响着整个游戏进程：在什么时候、什么条件下执行什么动作，地图上出现什么，消失什么，谁的状态（如攻击力、防御力等）的改变。都要在游戏脚本中详细说明，只不过是使用符号化的语言而已。可以说游戏脚本就是一种解释类的AI。游戏脚本是非常重要的，RPG游戏不用说，因为RPG游戏几乎是单线式的，绝对需要脚本的支持。而在SLG游戏中，也是非常的重要。比如说，在一关设计时我布置了大量的强大的敌人。如果不用脚本加以控制的话，那么敌人将蜂涌而上，玩家绝对吃不消。而使用脚本控制后，每隔一定时间后有一部分敌人进入搜寻并攻击状态，其它的敌人仍然在待机状态。玩家将敌人一部分一部分吃掉，即不费多大力，又有一种一对N的成就感，娱乐的目的就达到了。ACT（动作类游戏）中，也要使用脚本控制游戏进程，不过这种脚本非常简单，只要写明什么地方出现什么敌人，什么机关工作就可以了。即时战略游戏的脚本相对复杂和抽象，既然是浅谈，这里就不用说了
家园 谈谈模拟足球游戏中人工智能 谈谈模拟足球游戏中人工智能
当球队进攻时，对于有球队员来说，它(暂且用它咯)在每一个瞬间都会有一个行为指导，也就是下一步行为：是向某方向带球？还是以某种方式传球给队友中的某一人？或者即是立即射门。这个指导行为从何迩来？又如何根据状况得以改变？不管情况怎样变化，使球员能在任何时刻都有一种较为合理的下一步行为为备，这样大概便可以模拟出踢足球的AI了。
其实足球AI模拟的关键就在于会让球员能较为聪明合理地分析球场上瞬息万变的赛况，并根据这个判断得出一个更为聪明合理的下一步行为。能力好的球员会不断的分析，从而迅速地调整它的行为而得以使比赛向更为有利的趋向发展，这个过程不断地持续，一场计算机AI模拟的高水平足球赛便可得以实现了。
第一个难度便是如何教会让AI球员判断场上的情况，如何产生AI分析，如何得出结论并生成下一步行为。
第一步是视觉判断：
带球球员能看到队友及对方的行为，从离它近的到离它远，无论在它前面或是在它侧面甚至是在它身后的，优秀的球员都能够感知。也就是模拟使AI球员“视野开阔”。这些信息可以很方便地从SIM比赛中球员的坐标，速度，动作数据得来，模拟起来并不算太难。
第二步是赛况分析：
也就是说使球员在视觉信息采集后产生一个意图，使比赛能更为向我方有利地发展。（比如：队友位置都不太好，无法穿球，AI使它得出了继续运球的意图；当它离球门距离不太远，有一定的射门空挡，AI便使它得出带球射门的意图；当有队友的跑位出现空挡时，AI便使它产生了向其分球射门的意图；当两侧队友跟进到位时，AI便使它产生向其穿球打下底穿中的意图）
这些都是第一步行为意图，是战术的雏形。
从这些极其离散的视觉采集信息（就是那些敌我双方球员坐标，速度，行为甚至能力）而产生一个战术意图看起来是非常玄妙而神秘的。殊不知，聪明的人类却能够从这些离散而无规的数据中能提炼出非常多隐藏在内的有用的比赛信息！而AI模拟的任务就要让COM球员学会找出这些隐藏的信息！
因此可以将导向式思考（利用经验规则导向）与推论式思考（用极大极小法推导出最佳行为）两种方式合理巧妙地结合起来。
另一个重要的因素便是将大量隐藏信息进行“过滤”，也就是说，AI需要找出最有价值（或者讲是合适）的隐藏信息，这里有随机因素，也有权排序。
最后一步便是根据所产生战术意图而形成一个下一步行为：
这很像是一个细节处理，因为下一步行为行为是随时在频繁地改变，而战术意图相对来说是较为稳定的。（毕竟近处看得多，远处观的少）实现下一步行为便是这个SIM足球的“动作引擎元素”，合理的动作元素可以使模拟比赛的可视性更为真实，更重要的是它能够与AI相互配合，这两者可以说是相辅相成缺一不可的（呵呵~哲学课考试我用的最多就是这句话：）FIFA的缺陷便在于它的动作引擎元素没有WE系列合理真实，这便直接导致了它的真实性不如WE，AI做的再棒也无济于事。
总结：AI球员通过观察赛况，找出离散数据的隐藏信息，得出了一个战术意图，做出了一个动作行为，这便就似完成了一个TURN。剩下的，SidMeier有一个很有用的经验思路：“我先教它如何玩一个回合开始。然后教它如何玩两个回合，再后来就该考虑教它如何玩10个回合了。”当然，SIM足球的AI也许会更复杂，因为我们只考虑了有球球员AI模拟的一个例子，但是我相信这3个部件是适用与足球场上每一个情况的，要做的只是更深入的分析，体会，感悟。
家园 多元化的即时战略AI 多元化的即时战略AI
关于如今即时战略的AI，实在不想多说。如今没有几个不是通过电脑作弊
而完成看似高AI的即时游戏。因为电脑和其操作是一体的。所以自然速度
要快。但是如此就是对玩家不公平。
完成一个高AI，就需要赋予电脑在不同情况下的思考能力。思考的越严密，
仿真程度就越高。而其思考的过程就是分步的判断敌我双方的状态。
举个地形AI的例子：
我们把整个地图根据地形分成若干个区域，分别以不同的字母来标记。如
地图中央有一块易守的高地（攻10防10移3）。设区域为A，A的西北方三
块区域为缓坡，设为B、C、D三个区域，皆为草地（攻6防4移7）。A东南
三块区域为陡坡，设为E、F、G，为石路（攻7防3移8）。
A对其他的区域攻击可以用冲锋、弓箭和落石。冲锋是主动攻击，刨除在
外，单以守来说，对付B、C、D应该用落石，E、F、G用弓箭。如此才能
达到最大的效果。
除此之外还要判断敌人的兵种和速度，来决定进一步的细节战术。
因此在发现敌人后的第一部应该是判断敌人所在的区域，其次是自己的区
域，再后是敌我的兵种。如此一来就能判断最佳的攻击方式。
换低地的攻方，在判断攻取地形标记为A后判断自己的地形，然后决定前
进方式，如果是在缓坡，为了防落石应该采取蛇行前进，而陡坡则应该
突击来减小损失。最后实时检测敌人状态来变换战术。
然后应该加入兵种的判断，以决定最佳的战术。每种兵种应该有自己单
一的AI判定和对付任何兵种时的多种战术。在特殊的地形应该有其独有
的特殊处理AI，如，在一个关口，骑兵可以一夫当关，或是退后诱敌
（须判断自己周围的部队），然后弓箭手配合伏击……
按此方法引深，可以策划出一套极其优秀的战术性AI，但是其缺点是AI
运算取决于机器的速度，如果机器速度慢的话就会在运算时发生停顿。
对于机器配置低的玩家是不公平的，解决办法是尽量优化AI程序。
前面提到了兵种自己单一的AI，这种设置会使整体的战局变得多样。同
时因为，现在许多游戏都是总体AI，例如某士兵发现敌人，于是全军都
知道了。按理说应该是士兵的通报有一定的范围，就象盟军敢死队里一
样，只有离其最近的单位才有可能得知。
因此，玩家的设置应该是可以看得到所有部队，但是只能看到所选部队
势力范围内的敌人。敌人同样如此，一个士兵发现敌人以后，按其兵种
及其位置作出判断，有能力的话，单独进行破坏，不行的话，回去报告
部队。
如此方法，实时地图系统应该取消，代之以势力范围地图，只有自己变
化或己方部队发现敌人变化后，地图才产生变化。
………………
……………………
想来想去，即时战略的AI可以开发的地方实在是太多了……
家园 浅谈电脑游戏中的人工智能制作 浅谈电脑游戏中的人工智能制作
电脑游戏随着硬件执行效率与显示解析度等大幅提升，以往很多不可能或非常难以实现的电脑游戏如此都得以顺利完成。虽然电脑游戏的呈现是那么地多样化，然而却与我们今日所要探讨的主题，人工智能几乎都有着密不可分的关系。
在角色扮演游戏中，程序员与企划人员需要精确地在电脑上将一个个所谓的“怪物”在战门过程中栩栩如生地制作出来；所以半兽人受了重伤懂得逃跑，法师懂得施展攻性法术。
目前能让人立刻想到与人工智能有密切关系的游戏有两种：一是所谓的战棋／策略模拟游戏，二则是棋弈游戏。人工智能的比重与深浅度，在不同的游戏类型中各有不一。有的电脑游戏非标榜着高人工智能不可，不然没有人买；有的则是几乎渺茫到让玩家无法感觉有任何人工智能的存在。
导向式思考
AI最容易制作的的方式，同时也是早期游戏AI发展的主要方向就是规则导向或称之为假设导向。在一些比较简单的电脑游戏中，程序员可以好不困难地将游戏中的规则与设定转化成一条条的规则，然后将它们写成电脑程序。让我们以角色扮演游戏为例。决大多数的企画在设定所谓电脑怪物时，所设定的属性通常有以下几种：
生命值 攻击力 防御力 法力 属性
最后一个“属性”是我在设定时喜欢增加的项目之一。透过这项属性的设定，我可以把怪物设定成“贪生怕死的”，也可以把战士设定为“视死如归”。以目前我们所掌握的资料，在战门系统中的大纲如是诞生了：
规则一
if (生命值< 10) // 边临死亡了吗
{ if (属性== 贪生怕死)
结果 = 试图逃跑
if (有任何恢复生命值的物品或法术可用)
结果 = 使用或施展相关物品或法术
}
规则二
if (可施攻击性法术 && 有足够法力)
{
结果 = 施展攻攻击性法术
}
由以上一连串的“如果－－就－－”规则设定，建立了最基本的ＡＩ。说这样的制方式只能建立基本ＡＩ其实并不当然正确。只要建立足够及精确的规则，这样的方式仍然有一定水准的表现。
规则导向的最大优点就是易学易用。在没有深奥的理论概念的前提下，仍有广大的使用群。所以很多老道的玩家常常没两下就摸清楚敌人的攻击策略，移动方式等等。
推论式思考
相信曾经接触过电脑语言课程，或是自习过相关书籍的朋友们，都曾曾经听过一个著名的程序，那就是井字游戏。用井字游戏作为讨论AI的入门教材，我个人觉得是最适当的例子。或许有人还不知道井字游戏怎么玩。只要任何一方在三乘三的方格中先先成一线便胜利了。我们在前面谈过的规则导向，在这里也可以派得上用场。
if任何一线已有我方两子&&另外一格仍空//我方即将成一线吗
结果 = 该空格
if任何一线已有敌方两子&&另外一格仍空//防止敌方作成一线
结果 = 该空格
if任何一线已有我方一子&&另外两格仍空//作成两子
结果 = 该空格
有一次我在某本电脑书上，同样地也看到某些以井字游戏为介绍的范例。不同的是，我几乎看不到任何规则导向的影子。但在仔细分析该程序码后，我得到了极大的启发，原来AI是可以不用这么多规则来制作的。它用的方法正是在电脑AI课程中重要的概念：极大极小法。我在这里只说明这法则的概念。继续以井字游戏为例，电脑先在某处下子，接着会以假设的方式，替对方下子，当然，必须假设对方下的是最佳位置，否则一切则毫无意义。在假设对方下子的过程中，自然又需要假设我方的下一步回应，如此一来一往，直到下完整局游戏为止。
底下是节录书中的程序片段：
bestMove(int p, int*v)
{
int i;
int lastTie;
int lastMove;
int subV;
/*First, check for a tie*/
if (isTie()) {
*v=0;
return(0);
};
/*If not a tie, try each potential move*/
for (*v=-1, lastTie=lastMove=-1,i=0;i<9;i++)
{
/*If this isn't a possible, skip it*/
if (board[i]!=0) continue;
/* Make the move. */
lastMove=i;
board[i]=p;
/* Did it win? */
if (hasWon(p)) *v=1;
else{
/*If not, find out how good the other side can do*/
bestMove(-p,&subV);
/* If they can only lose, this is still a win.*/
if (subV==-1) *v=1;
/* Or, if it's a tie, remember it. */
else if (subV==0){
*v=0;
lastTie=i;
};
};
/* Take back the move. */
board[i]=0;
/*If we found a win, return immediately (can't do any better than that)*/
if (*v==1) return(i);
/*If we didn't find any wins, return a tie move.*/
if (*v==0) return(lastTie);
/*If there weren't even any ties, return a loosing move.*/
else return(lastMove);
};
国外的一些论坛曾举行过256字节的游戏设计比赛。作品非常多，其中有一件作品正巧也是井字游戏。作者用区区两百多行就写了与上述程序演算方式完全相同的作品，可见功力确实了的。另外，我也很希望类似的活动能在国内推展起来。对了，在这样的比赛条件限制下，除了汇编语言外，几乎没有其它的选择了。
.386c
code segment byte public use16
assume cs:code, ds:code
org 100h
tictac proc far
start:
push cs
pop ds
mov ax,0B800h ; 清除屏幕
mov es,ax ;
xor di,di ;
mov cx,7D0h ;
mov ax,0F20h ;
rep stosw ;
xor cx,cx ;
mov dl,5
loc_1:
call printBoard
loc_2:
mov ah,8 ; 等待按键
int 21h
movzx bx,al
sub bl,31h ; 如果不是1..9
jc loc_2 ; 则重新输入
cmp bl,8
ja loc_2
cmp data_1[bx],al
jne loc_2
mov byte ptr data_1[bx],'x'
dec dl
jz short loc_3
mov al,'o'
call bestMove
mov [si],al
call isWin ; 判断是否已取得胜利
jnc loc_1
loc_3:
call printBoard
mov ax,4C00h
int 21h
data_1 db '12'
data_2 db '3456789'
data_3 db 0
tictac endp
printBoard proc near
mov si,offset data_1
mov di,548h
mov cl,3
locloop_4:
movsb
add di,5
movsb
add di,5
movsb
add di,133h
loop locloop_4
retn
printBoard endp
isWin proc near
mov bx,1
mov bp,3
call sub_3 ; 检查横向是否完成
inc bx
inc bx
dec bp
dec bp
call sub_3 ; 检查纵向是否完成
call sub_4 ; 检查斜向是否完成
clc
retn
isWin endp
loc_5:
stc
retn
sub_3 proc near
mov ah,3
mov si,offset data_1
loc_6:
mov di,si
call sub_5
add si,bp
dec ah
jnz loc_6
retn
sub_3 endp
sub_4 proc near
mov di,offset data_1
inc bx
call sub_5
mov di,offset data_2
dec bx
dec bx
call sub_5
retn
sub_4 endp
sub_5 proc near
mov cl,3
locloop_7:
cmp [di],al
jne short loc_ret_8
add di,bx
loop locloop_7
add sp,4
jmp short loc_5
loc_ret_8:
retn
sub_5 endp
bestMove proc near
mov bx,31FEh
mov cl,9
mov di,offset data_1
locloop_9:
cmp [di],bh ; #empty?
jne short loc_12 ; #no, skip
mov [di],al
pusha
call isWin ; #CY: Win
popa ;
jnc short loc_10 ;
mov bl,1
mov si,di
mov [di],bh
retn
loc_10:
pusha
xor al,17h ; good! toggle 'o' / 'x'
call bestMove
mov data_3,bl
popa
mov ah,data_3
neg ah
cmp ah,bl
jle short loc_11
mov bl,ah
mov si,di
loc_11:
mov [di],bh
loc_12:
inc bh
inc di
loop locloop_9
cmp bl,0FEh
jne short loc_ret_13
xor bl,bl
loc_ret_13:
retn
bestMove endp
code ends
end start
Copyright © 1998-2003 www.chinagamedev.net All Rights Reserved.
网站维护 [email protected]
站务合作 [email protected]
家园 即时战略游戏中如何协调对象移动 即时战略游戏中如何协调对象移动
在图论中人们研究了通过怎样的计算才能找到一条从A点到B点的通路，以图论本身来说这已经解决了从A到B的问题，剩下的只是从A沿着找到的路线移动到B就可以了。这样的认识基于一个默认的假设--道路中的一切障碍物都是固定的，但是在现在已经广泛流行的即时战略类游戏中问题却远远不止这些。
在图论中人们研究了通过怎样的计算才能找到一条从A点到B点的通路，以图论本身来说这已经解决了从A到B的问题，剩下的只是从A沿着找到的路线移动到B就可以了。这样的认识基于一个默认的假设--道路中的一切障碍物都是固定的，但是在现在已经广泛流行的即时战略类游戏中问题却远远不止这些。举个例子说上下班高峰期的时候，路上的每一个人都清楚地知道自己的目的地和所要走的路径，但是由于某些个人不遵守规则或其他人为原因还是会造成堵车现象。而如果这样的事情发生在一个即时战略的游戏中，那么带给玩家的沮丧感和愤怒将远超过现实中的堵车现象。当游戏中的一个士兵接到玩家的命令要从基地的一侧移动到另一侧以帮助抵抗敌人的进攻时，它需要一个计划(更明确的说是一条寻找出来的路线)使它能够到达目的地，但很可能在它移动的过程中预定的路线上出现了变化(例如玩家让工人们在士兵的必经之路上修建一个建筑或另外一批士兵出现在路上，从而堵塞了道路)，这时如果没有一个优秀的移动系统，那么之前的寻道工作等于是白费工夫。
本文将介绍一种相当有效的个体移动系统，以从另一个角度探讨游戏中的自动移动问题。虽然本文主要是针对即时战略类型，但所介绍的方法可以很容易的扩展到其它的类型中使用。这里查看原文。
一些需要解决的问题
在进一步深入到我们的移动系统中之前，我将先简介一下人们在解决移动问题上遇到的一些问题，这些问题是消耗最少的CPU时间的同时达到最佳的智能效果和最高的移动精度的关键。
首先让我们对比一下同时移动单个对象与同时移动数十、数百个对象的不同。一次移动一个对象是非常简单的，但是一个可以相当完美的移动单个对象的算法并不一定能很好地解决数百个对象的同时移动，这其中最大的问题就是CPU时间的消耗。请一定要切记如果你要制作一个需要同时移动大量个体的游戏程序，那么在CPU的使用上一定要非常的保守。
某些移动算法是很依赖CPU速度的，这就是那些要同时移动大量个体的游戏中只有很少的一部分支持高级的移动方式(例如个体的加速和减速)的原因。玩家们总是认为游戏中的大船和被重装备武装起来的战士们应该具有能够加速和减速的能力，这样才能体现出真实性，但是这小小的真实性将会增加超乎想象的额外的CPU计算工作。这种情况下事实上用来处理个体移动的时间增加了，因为你不得不花费更多的时间来计算加速度，从而获得新的速度值。在后面我们扩展例子程序到处理移动的预操作部分时，你将清楚地看到这样的工作所增加的计算复杂度有多大。另一个将会大大增加CPU计算量的问题是个体的转动半径。大多数寻道算法都不考虑个体的转动半径(转动半径是指一个个体原地旋转一周所需的最小圆的半径，因为我们不可能让一个士兵倒退着走上半张地图去袭击敌人的基地，所以经常需要个体进行旋转)对道路选择的影响。于是就会出现一种情况，虽然我们的一头大象已经找到了一条通往目的地的通路，但是它却不能沿着这条路线移动到目的地，因为路线中的一个拐角面积要比大象的转动半径小一些。大多数移动系统通过减缓个体的速度，再作出一个缓慢而更节省空间的转身动作(相信很多人都看到过即时战略游戏中士兵在拐角处被堵住时所作的动作吧)来解决这一问题，但这种方法会极大的增加CPU的计算量。
正如大家所想象的那样，即使是即时战略游戏也并不是即时的，而是不断的进行循环，在每次循环中处理游戏的全部数据和玩家的指令(我们可以称它为UL-Update Loop)。为了增加游戏的性能，一般采用的方法是记录上一次UL的所消耗的时间，以预测下一次UL大约将要花费的时间(为了能尽可能地逼近即时处理，这样做是很有必要的)，但是这就给个体的移动带来了大问题--每次UL中个体的移动距离很可能是完全不同的，下面的图1就是这种情况的一个例子。负责个体移动的算法显然在面对每次移动相同距离时比每次都要为所有移动个体计算不同的时间下移动出的不同距离并将其显示出来要轻松得多。当然，如果游戏的UL系统制作的非常优秀，那将略微改善一点这样的窘境。
不要忘记处理个体移动中的碰撞问题。一旦你的游戏中的士兵们碰撞到了一起，你要怎样将他们分开呢？一种方法是是个体之间根本不发生碰撞，但在实际的应用中这是不可能做到的。不仅仅是实现这要求的程序代码非常难写，而且无论你写再多的代码也是无用的，这些个体总是会找到一些途径来使彼此重叠在一起，而在更多的情况中，这些个体的重合是必须的。一些使用近距离兵器进行战斗的游戏，例如《帝国时代》，就是一个要求个体重合的实例。另外，如果你要限制你游戏中的个体不能碰撞在一起，那么他们很可能为了避开彼此而离开预设的移动路线，暴露在其它对手的攻击之下，受到意外的伤害，这会使玩家对你的游戏极端不满。因此你必须决定好你的那些个体相互靠的有多近，重合多少是可以容忍的，还要设法处理由这些决定所带来的问题。
注意考虑地图的复杂性。在复杂的地图上实现良好的移动的算法比简单地图上做到同样效果的算法要复杂得多，由于现在地图越来越倾向于复杂和真实，对于移动算法的要求也进一步提高了。
随机生成的地图可能造成意想不到的问题。由于不能通过给固定道路编写预定路线来减小寻道的难度，因此随机生成的地图在复杂性上要更高于预设地图，尤其对于寻道而言。当寻道变得使CPU负担过重时，唯一的解决方法是降低寻道的精度和质量，这时就要求提高移动算法的质量以弥补寻道上的不足造成的程序反应迟钝。
一定要认真处理各类个体的体积和由此产生的空间问题，这个问题最能说明你所需要的移动算法的精度。如果你的程序中需要移动的物体很少，以至于几乎不会出现彼此互相碰撞的情况(例如大部分的第一人称射击游戏)，那你可以放心地使用一些简单的算法。如果你的程序所要处理的移动物体非常多，并且还要处理彼此的碰撞和诸如检测两个个体之间的缝隙是否足够更小的个体从中间穿过等等操作，这时对你的移动算法在精确度上和质量上的要求将会使计算量大幅度的增加。
一个简单的移动算法
让我们从一个简单的对个体状态进行处理的移动算法的伪码开始，这个算法所作的只是简单的使用一条给定路线前进，当遇到碰撞和冲突时重新寻道，因此它能在2D和3D游戏中都表现得很出色。使用该算法，我们将从一个给定的状态开始，持续循环直到找到一个可行的位置作为中继点作为个体移动的目标去接近之后才跳出循环。移动状态将会在整个UL中保存下来，这将使我们能够正确的设置未来的状态，例如"自动"添加中继点。这种保存机制可以保证减少一个个体在下一次UL中作出与当前UL移动相反的判断的可能性。
我们假定被给定了一条通向目的地的路径，并且这条路径在提供给我们时是精确的，并且是可行的(也就是不会发生碰撞)。由于大多数即时战略游戏拥有巨大的地图，以至于一个个体可能要花费几分钟的时间来走完整个路程，而在这几分钟里地图上可能发生使当前路径不在可用的变化(例如在路径上新建了建筑)。为了解决这个问题，现在我们加入少许碰撞检测，一旦遇到碰撞，就进行重新寻道。在后面你将看到，我们可以采取几种方法来避免重新寻道，以减少CPU消耗。
碰撞检测
所有碰撞检测系统的基本目标都是判断两个个体是否发生了碰撞。这次我们所介绍的碰撞检测都是假设两个物体的碰撞，将来我们会专门介绍大量物体互相碰撞的检测问题。但无论是两个物体还是多个物体发生碰撞有一点是共同的：每个物体都要收到碰撞信息以便作出适当的响应(分开彼此)。
大部分即时战略游戏中使用的简单的碰撞判断实际上是将每一个个体看作一个球体(2D中是圆)，再进行简单的球体碰撞检测，而不在意这样简单的判断是否能够满足游戏对于碰撞的要求。这样做确实有利于提升性能，即使一个游戏要进行非常复杂的碰撞判断--例如判断击出的拳头是否击中敌人，或者甚至是低精度的多边形(polygon to polygon)交叉判断，这时为可能出现的碰撞保有一个球体区域往往也能够提升程序的性能。
当我们设计一个碰撞检测系统时要注意面对3种截然不同的实体：单个的个体、一群个体的集合以及经过队形编制的个体群(就像《帝国时代2》中的阵形一样，见图2)。事实上对所有这3种类型使用简单的球形判断都能工作得很好，单个个体可以简单的使用单个球体进行它的全部碰撞判断，而对于其它两种情况只需要再稍微增加一点工作量。
对于一群个体的简单集合来说，可以接受的碰撞检测下限是对整个组中的每个个体进行检测。这种方法将允许那些不属于你所选定的组的个体轻松的混入你的组队中。相对来说，对编队所要进行的碰撞检测就要更加复杂一些了。我们还应该认识到这种简单的组群还有一种特殊的性质决定了我们应该尽可能的简化对它所采用的碰撞检测方法--这种组群应该能够随时随地的将排列方式变换成任何可能的适应当地空间大小的阵形。
对于编队来说，不仅仅要进行如上面的组群那样简单的个体碰撞检测，还要进行大量更加复杂的检测操作。首先要保证编队中的个体之间不能互相碰撞，同时如果编队中的各个个体之间有一定的缝隙，还要保证任何一个不属于该编队的个体不能占用这一空间。另外，一个编队应该不能改变队形或重组，但是游戏的规则又可能规定当没有足够大的通路提供给整个编队保持队形穿越某一障碍物时，编队可以先散开，待各个体越过障碍物之后再重新组成编队，这样的设计更加体贴玩家。
我们可以尝试使用基于时间的碰撞描述机制。立即碰撞用来描述当前正发生在两个个体之间的碰撞；未来碰撞用来记录预计在程序运行的后续时间中将会发生在预定地点的碰撞(当然，前提是将要碰撞的对象都不改变各自的移动路线)。在任何情况下立即碰撞的情况都应该比未来碰撞的情况更优先被处理。同时我们也应该定义碰撞的3种状态：未处理的、正在处理和已处理完毕的。
使用"离散"的算法达到"连续"的效果
大多数移动算法从根本上都是"离散"的，不同于数学上的离散定义，这里所说的"离散"指移动算法在按照给定路径从A点移动到B点的过程中从不考虑中间路径上可能出现什么东西，相反，在"连续"的算法中就会考虑这些情况。这样做的一个问题就是当我们进行一个Internet游戏时(众所周知，由于网络速度的限制，这类游戏的UL时间一般较长)那些速度较高的个体很可能在一次UL时间中移动相当大的一段距离(由于UL时间变长)，而当这样增长的UL连续出现时很可能出现个体跃过了其它本应发生碰撞的个体。如果这样的情况出现在一个工人的身上那并不会有人在意，但显然任何玩家也不会希望敌人能够从辛苦建设的城墙中穿越而过进而攻击玩家的基地(某些早期及时战略游戏中出现的"穿墙"的BUG就是有这种问题造成的)。大部分的移动系统现在采用限制个体移动距离的方法来对付这一问题，该方法可以有效的简化所需的处理。在离散型的移动算法中解决这类问题的方法如下图所示：
一种有效地解决方法是将一次移动拆分成多次移动的集合。这种拆分需要满足一定的移动距离上的要求，这要求就是要保证每次移动的距离刚好短于任何个体的长度，这就可以保证不可能有任何个体移动到当前个体的路径上来，从而避免了从其它个体之上跨越过去的情况。当每次这种拆分后的移动结束时我们就要使用碰撞检测系统对个体的当前位置进行碰撞检测。你可能会想到如此频繁的计算大量点的碰撞信息将会极大的增大系统消耗，没关系，在后面的章节中我们将会介绍一种方法来降低这种计算对系统的消耗。
另一种方法是创建一种称之为移动线路(Move Line)的对象。我们可以使用这条移动线路来描述个体的移动，个体的原始位置作为线段的起点，目的地作为线段的终点，就好像《红色警报2》里所表现出来的那样。这种方法并不用添加新的数据，但是会加大碰撞检测部分的复杂性--我们必须把简单的球形碰撞检测修改为对一个点到一条线段的距离的检测，而这样做将会增加计算的难度，也会消耗更多的时间。大多数3D游戏都已经实现了一种可以快速挑选出可被游戏者观察到的物体的分级系统(也就是能够迅速地判断出游戏中的哪些物体处于玩家角色的视野之内的系统)，我们可以对该类系统进行修改，使它们可以用来快速挑选出那些在我们的游戏中可能发生碰撞的个体。这样做的好处是大幅度地减少了需要进行碰撞判断的个体的个数，于是所需要的计算量常常就能够降低到所能允许的范围之内了。
位置预测
经过上周的工作，我们已经有了一个简单的移动算法和一个管理个体碰撞的列表，还有什么工作是强化个体之间协作所必需的呢？位置预测(Position prediction)。
预测的位置只不过是一个位置列表(至少包含个体的运动方向和时间标记，有时也需要记录加速度等信息)以指出未来某时刻个体所在的位置，参考图4。一个移动系统可以将用来实现个体移动的算法拿来负责计算个体的位置预测，这些预测越准确其可用性也就越大。当然预测计算也会增大计算量，为了不降低游戏的效率，下面我们就来讨论一下如何减少多余的CPU消耗。
显然，最方便的优化方法是避免在每一帧中重复计算每一个已经预测过的个体位置。一个简单的移动列表可以实现这样的目的并且能够工作得很好：你可以在每一帧中从表内删除当前的位置，并向表内添加新的预测位置以维持列表长度固定(见图5)。虽然这一方法并不会减少个体开始移动时创建整个列表的计算量，但可以保证在剩余的移动过程中维持固定数量的计算。
下一种优化方法是设计一种能够处理点和线的位置预测系统，由于我们的碰撞系统支持处理点和线，因次添加这一功能将是很容易的事。如果一个个体按照一条直线进行移动，那么我们可以利用当前个体位置、预测位置和个体运动半径来指定一段移动的轨迹及范围。然而如果个体正在进行一次圆运动那么整个处理就会略微复杂一些。当然你可以将这种运动过程作为一个函数保存起来，但这显然会加大系统的负担。作为替代可以尝试通过对圆上的点进行取样来作出正确的位置判断(见图6)。最后，再次建议一定要使用能够实现对点和线的无缝交替处理的预测系统，以便在任何可能的情况下通过使用直线来减少对CPU的耗用。
最后所要介绍的一种优化方法非常重要，但同时也可能有一些不够直观，不能简单的看出其优化作用。如果我们要使用这样的预测系统，为了尽可能少的消耗资源，显然不应该在计算了一次预测未知之后再进行一次计算来移动个体。因此解决的方法是精确地进行位置预测，并最终使用该位置移动个体。这样我们就能对每个个体的移动只计算一次并且除了前述的开始移动时的计算之外没有其他多余的计算开销。
在实际的应用中，你可能每次只能进行一个UL时间的计算来进行位置预测，这时要注意未来每次UL的时间很可能并不等长。如果只是简单的按照预测位置移动个体而不考虑每次UL的长度，这将有可能造成一些问题，当然某些游戏(或者游戏中的某些类个体)可以很好的适应这样的操作。一般的游戏都通过每次对列表中的数据进行一些修正来改善预测的准确性，而这样做的同时也应注意何时应该完全抛掉原来计算的已与现在情况有较大误差的预测而重新计算整个列表。
实际对位置预测的应用中主要的难题是由于我们在碰撞检测中将这些预测的位置做为个体的当前位置来使用所造成的。你将很容易的看到对某给定的区域内个体预测位置的比较所需要消耗的计算量，但是为了很好的实现个体间的协作我们必须知道未来一小段时间内每个个体的目的地以及它们可能会与哪些其它个体相碰撞，这都需要一个优秀而且快速的碰撞检测系统。此时最佳的优化措施就是如同前面所述使用3D引擎中的相关部分舍去那些不大可能碰撞的个体组合，这将允许你使用更多的CPU时间来处理最可能发生的那些碰撞。
个体之间的合作
我们已经建立了一个复杂的系统来确定个体未来的可能位置，它支持3D移动，同时对计算量的提升也并不比一个简单的方法多多少，重要的是该方法提供给我们一个记录了一个个体在未来一小段时间内移动所需的一切信息的列表，这正是我们所需要的。现在我们可以进入较为有趣的部分了。
如果我们的工作做得很好，那么我们所要处理的绝大部分碰撞将是未来的碰撞(因为我们已经使用位置预测尽量地避免了立即碰撞)。由于处理未来碰撞最后的方法将是停止移动并重新寻道，因此为了不使寻道过于频繁，尽量使用其他方法解决碰撞就变得很重要。
下面就详细的介绍对于这种个体与个体碰撞的方法。
未处理的碰撞：
CASE 1:if 个体已经全部停止移动：
1. if 是低优先级的个体，什么也不做
2. if 是高优先级的个体，找出哪一个个体将要移动(如果存在)，告知该个体进行尽可能最短的移动来解决碰撞，改变状态为正在处理的碰撞
CASE 2:if 个体没有移动，是另一个个体将要移动，什么也不做
CASE 3:if 当前个体正要移动，其它个体已经停止
1.if 是高优先级个体，其它停滞个体为低优先级并且能够从通路上移开，计算出下一步的位置并通知低优先级的个体从通路上移开(见图7)，改变状态为正在处理的碰撞
2.Else,if 可以避开另一个个体，避开他以解决碰撞
3.Else,if 是高优先级个体并且能够沿移动路线推动低优先级个体，推动它，改变状态为正在处理的碰撞
4.Else,if 停下，重新寻道
CASE 4:if 当前个体正在移动，另一个个体也在移动：
1.if 当前个体是低优先级，什么也不做
2.if 碰撞不可避免，并且当前个体是高优先级，通知另一个体停止移动，转状态为CASE 3.1
3.Else,if 当前个体是高优先级的，计算出下步移动位置，通知另一个体减速到足以避免碰撞。
正在处理的碰撞：
1.if 是一个移动的个体要处理CASE 1的碰撞，并已经移动到了目的地，碰撞解决
2.if 是CASE 3.1中低优先级个体，并且高优先级个体已经抵达预定位置，开始返回原位置，碰撞解决
3.if 是CASE 3.1中高优先级个体，等待(减速或停止)直到低优先级个体从通路上离开，之后继续移动
4.if 是CASE 3.3中高优先级个体并且现在低优先级个体已可以从通路中离开，转状态为CASE 3.1
5.if 是CASE 4.3中低优先级个体并且高优先级个体已经抵达预计地点，恢复移动速度，碰撞解决
解决碰撞的关键之一是排定个体优先级的顺序，如果没有一套强壮的完好定义的优先级体系，你将看到碰撞在一起的个体有如旋转木马一般运动，因为每个个体都要求对方让出道路，而同时又没有一个个体能拒绝这个要求。我们也应该为碰撞进行分级，在处理时应该优先处理那些有最高优先级的碰撞，当有足够富裕的时间时再去处理那些优先级低一些的碰撞。在游戏中碰撞处理也需要注意碰撞个体的密度。如果一场大型的战斗使得许多的战士在狭小的空间中碰撞在一起，那你就应该花费更多的CPU时间来处理这些碰撞而不是地图上远处两个矿工间的碰撞。对这类较容易发生碰撞的区域的关注的另一好处是你将能够在其它个体进行寻道时使它们避过这类区域。
计划编制基础
计划编制是个体协作的关键，虽然我们尽可能地提升预测和计算的精确性，但是显然事情总是会出错的。例如我们在《帝国时代》中所犯的一个错误是我们总是在一帧的时间内使个体作出移动的决定，虽然这样的决定多数是正确的，但我们并没有在以后的UL中参考它。这样就造成了一个问题：个体对移动路线作出了决定，实行时发现出现问题必须重新决断，结果是使个体再次返回它的出发点。计划编制可以有效地避免这类问题。我们保存一定数量的个体以前移动中所遇到的障碍和碰撞的解决步骤(由其它的游戏细节定义)，这就为我们未来遇到困境时提供了参考。举例来说，当我们要避免一次碰撞时我们将存储哪一个个体是我们所要闪避的。由于我们要设定一个可行的计划，没有任何理由对碰撞中的另一个体进行碰撞检测，除非其中的某一个个体得到了新的命令或发生其它类似的变化。一旦我们完成了闪避，就可以为其它的个体恢复正常的碰撞检测了。在下面的扩展中，你将看到我们将反复利用这一思想来达到我们的目的。
一些简单扩展
游戏编程的乐趣之一就是要不停地创新来开发新技术以使设计人员能作出更优秀的游戏。在即时战略游戏中，越来越多的开发人员希望能够在他们下一批作品中加入对编队的处理能力。在这里我不会介绍现在那些低技术含量的移动方法，我所要讨论的是如何协调编队的移动，使每一个个体都能在智能的维持编队队形的同时在地图上随意的移动。
组队(Group)移动
首先要弄清楚何谓组队(Group)：由用户(玩家)为方便操作而选取的简单的个体集合(一般会对其成员发布相同的命令)，除了在移动时要保持成员一同移动之外组队并没有其他对移动系统的限制。组队的使用使我们必须记录许多信息，例如组队成员的列表以及当整个组队还在一起时所能移动的最大速度。也许我们还应该保存整个组队的中心，以作为一个可以很容易得到的操作参考点。同时还应该选定一个组队的指挥者，大多数游戏中怎样选出这个个体并不重要，重要的是一定要有一个这样的个体。
在我们开始工作之前有一个问题需要回答：当组队在地图上移动时我们有必要保持所有个体在一起吗？如果不，组队将只是为使用户方便操作而存在的，每一个个体都会独自寻道和移动就如同用户对每个个体分别下达指示一样。当我们关注如何加强组队的管理时，我们可以发现组队的凝聚力可以分为多个等级。
组队中的个体都以相同的速度移动。一般地这将使用组队中速度最低的个体的最大速度，不过有时让那些速度较慢的个体在组对中移动的稍快一些会更好(见图8)。然而一般游戏的设计人员给一类个体较低的速度总是有原因的，例如如果允许强力的个体能够非常高速的在地图上移动将会极大的破坏游戏的平衡性。
组队中的个体都以相同的速度移动并使用同一条路径。这种方法可以有效的避免当组队中一半的个体从森林一侧前往目的地时另一半却从另一侧移动(见图9)，稍后你将看到实现这一方法的一条简单途径。
组队中的个体以相同的速度移动，使用同一条路径并同时抵达。这是最复杂的组队组织方式，它不但要求达到上述两点，并且还要求位于前面的个体能够等待落在后面的个体追上来，有时还要给后面的慢速个体短时间加速以使其能够追上前面的个体。
怎样才能实现最后的要求？这要使用一种分级的移动系统，这样我们就能在处理每个个体的移动时兼顾那些同属于某个组队的个体了。如果我们对组队的个体创建一个组队对象，我们就能够记录所有必需的数据，为整个组队计算最大速度，以及判断何时需要前面的个体等待后面的个体。下面就是一个组队类的简单定义：
Listing 2. BUnitGroup.
//*****************************************************************************
// BUnitGroup
//*****************************************************************************
class BUnitGroup
{
public:
BUnitGroup( void );
~BUnitGroup( void );
//Returns the ID for this group instance.
int getID( void ) const { return(mID); }
//Various get and set functions. Type designates the type of the group
//(and is thus game specific). Centroid, maxSpeed, and commander are
//obvious. FormationID is the id lookup for any formation attached to
//the group (will be some sentinel value if not set).
int getType( void ) const
{
return(mType);
}
void setType( int v )
{
mType=v;
}
BVector& getCentroid( void ) const
{
return(mCentroid);
}
float getMaxSpeed( void ) const
{
return(mMaxSpeed);
}
int getCommanderID( void ) const
{
return(mCommanderID);
}
BOOL getFormationID( void ) const
{
return(mFormationID);
}
BOOL setFormationID( int fID );
//Standard update and render functions. Update generates all of the
//decision making within the group. Render is here for graphical
//debugging.
BOOL update( void );
BOOL render( BMatrix& viewMatrix );
//Basic unit addition and removal functions.
BOOL addUnit( int unitID );
BOOL removeUnit( int unitID );
int getNumberUnits( void ) const
{
return(mNumberUnits);
}
int getUnit( int index );
protected:
int mID;
int mType;
BVector mCentroid;
float mMaxSpeed;
int mCommanderID;
int mFormationID;
int mNumberUnits;
BVector* mUnitPositions;
BVector* mDesiredPositions;
};
BGroup类在其内部管理整个组队中个体之间的交互操作。在任何时间点，它都应该有一个时间表以来处理组队内的个体之间的碰撞，它也应该有能力通过参数和优先级管理来控制或修正个体移动。如果你的游戏只支持一种移动优先级，那么你就应该为你在组队中的个体们添加第二种优先级。虽然一个组队对外的表现似乎只有一种优先级，但在其内部还是应该分为不同的移动优先级。基本上来说，BGroup类是另一个完善的封闭的移动系统。
组队的指挥者将负责整个组队的寻道工作，它将决定整个组队的移动路线，在简单的组队移动系统中所需的工作只是由这个个体本身来寻道即可。然而在下面的部分中我们将看到指挥者所能够作的其它事情。
编队控制基础
首先应该给出编队的定义：编队(Fomation)是一种更复杂的组队，编队有自己的方向(前方、后方、左翼和右翼)。编队中的每一个个体都试图保持自己在编队中的位置，而这个位置是唯一固定的也是相互关联的。更加复杂的模型使得编队中各个个体的朝向需要单独处理，而同时也要求在移动中提供整体旋转的方法。
编队是建立在组队系统之上的，它是一种限制更加严格的组队，因为我们必须非常详尽的规定编队中每个个体的位置。所有的个体在移动中必须保持一起行动，并要求在速度、路径上一致以及相互之间的位置和距离保持不变--如果在移动中编队出现了大间距的缝隙，那么它也就与组队没有什么不同了。
下面给出的这个BFomation类能够清晰的管理一个编队的预定位置(我们要求编队中的每个个体所处的位置以及它的方向)、编队方向和编队的状态。大多数游戏中所使用的编队都是预先定义的，显然，在开发过程中进行这项工作是很简单的(通过使用一些非专业人员也能熟练操作的文本编辑器就可以很好的完成这项工作)。我们当然希望能在游戏过程中实时的定义编队，但这样做就需要更多的内存以保证每一个由玩家定义的编队都能在内存中保留一份自身定义的副本。
Listing 3. The BFormation Class
//*********************************************************
// BFormation Class
//*********************************************************
class BFormation
{
public:
//The three formation states.
enum
{
cStateBroken=0,
cStateForming,
cStateFormed
};
BFormation( void );
~BFormation( void );
//Accessors for the formation’s orientation and state. The expectation
//is that BFormation is really a data storage class; BGroup drives the
//state by calling the set method as needed.
BVector& getOrientation( void )
{
return(mOrientation);
}
void setOrientation( BVector& v )
{
mOrientation=v;
}
int getState( void ) const
{
return(mState);
}
void setState( int v )
{
mState=v;
}
//The unit management functions. These all return information for the
//canonical definition of the formation. It would probably be a good
//idea to package the unit information into a class itself.
BOOL setUnits( int num, BVector* pos, BVector* ori, int* types );
int getNumberUnits( void ) const
{
return(mNumberUnits);
}
BVector& getUnitPosition( int index );
BVector& getUnitOrientation( int index );
int getUnitType( int index );
protected:
BVector mOrientation;
int mState;
int mNumberUnits;
BVector* mPositions;
BVector* mOrientations;
int* mTypes;
};
使用这个模型，我们必须时刻关注编队的状态。cStateBroken表示编队并没有被创建也没有创建的企图；cStateForming表明我们的编队正在建立但还没有达到cStateFormed状态；一旦所有的个体都已位于它们的预定位置，我们就可以将状态改变为cStateFormed。为了使编队的移动简单化，我们可以使一个编队在完成组建之前(达到cStateFormed状态之前)不可移动。
当我们准备使用一个编队时，第一件工作就是组建这个编队。当给定一个编队时，BFormation(译者注：原文这里是BGroup，但该类并没有编队管理功能，经过反复推敲认定为编写错误)控制每个个体移动到编队中的预定位置，该位置的计算是与当前编队方向相关的，如果这个方向发生了变化，那么预定位置将自动被重新计算并修正为正确的位置。
为了组建一个编队，我们可以使用预定安置--每一个预定位置拥有一个预设值(由定义规定或由算法确定)来指明个体组建编队时应该按照那种顺序进驻那些预定位置，这样才能使整个组建过程从里到外进行得相当有条理(见图10)。下面的算法列表说明如何实现这样的组建方式。
Listing 4.
设置组队中的所有个体移动优先级到一个相同的低优先级
设置状态为cStateForming
While 状态为cStateForming
{
找出离编队中心最近的未有个体占据的位置
If 没有个体再可用
设置状态为cStateFormed，跳出组建循环
选定一个个体前往所找出的位置，要求满足如下条件：
使个体移动距离最短
与其它编队成员碰撞的几率最小
移动时间最短
设置个体的移动优先级到中等值
等待直到个体就位(可能要经过多个UL时间)
设置个体移动优先级为最大值，这样做可以保证以后进行组建工作的个体不会使该个体离开其位置
}
现在我们所有的战士都已经就位了，接下来做什么呢？我们可以开始移动他们以穿过整个地图，我们可以假定寻道系统找出了一条以当前编队的形状和大小可以通过的路径来抵达目的地(见图11)，如果没有这样一条路经那就必须对整个编队进行操作(不久我们就会探讨这个问题)。当编队在地图上移动时我们需要选出一个指挥者来控制整个移动，当指挥者沿路径前进并改变方向时其它所有编队中的个体都要改变方向以追随它，这种操作一般被称为flocking(聚集)。
我们有两种方法处理编队的方向改变：忽略这种改变或者转动编队的方向。忽视方向的改变是简单的而且对于那些盒状的编队来说是非常合理的。
对编队进行旋转并不会增加多少复杂性而同时对于某些编队方式(如直线形)来说是非常合理的。进行编队旋转时首先要做的是停止编队移动，完成方向的旋转之后我们要重新计算每个预定位置，然后回到cStateForming状态(见图13)，使个体前往新的位置并在完成这一工作之后设置状态为cStateFormed，这样我们就可以继续原来的移动。
高级编队管理技术
现在我们已经可以将编队在整个地图中移动了，但是由于游戏的地图是动态而且复杂的，所以很可能出现选出的移动路径不可用的情况。如果这样的事情发生，就需要我们对编队进行操作，一般的操作方式有3种，下面就逐一介绍。
缩放个体间距(Scaling unit positions).由于编队中的预定位置都是由矢量进行定义的，因此我们可以很方便的对整个编队的间距进行放缩以使它变得更小，这就使得编队能够通过城墙或树林中更小的缝隙(见图14)。这种方法对于那些排列得较为分散的编队很有效，但对于那些排列紧凑的编队就没有什么用处了。
简单的障碍回避(Simple ordered obstacle avoidance).如果我们在移动编队时遇到与其它游戏中实体相碰撞的情况时(无论是当前还是未来碰撞)，我们可以假设即使有这样的碰撞发生，原来寻到的道路仍是可用的。简单的解决方法是沿着编队前进的路线找出第一个不再发生碰撞的位置，并在该位置完成编队的重组(见图15)。这样我们的步兵团就可以先分散，带穿越障碍物之后再在另一侧重新组建编队。在使用这一方法时一定要注意有时障碍物的范围非常大，以至于编队的重组工作必须在走出很远之后才能做，这时就得考虑是否应该重新寻道了。
二分和重组(Halving and rejoining).虽然简单的回避能够工作的很好，但是会降低玩家对整个编队穿越地图的感觉，相对来说二分法可以很好的保持住编队所带来的视觉冲击。当我们的编队在前方遇到一个障碍物时我们可以找出编队中的一个拆分点，从该点将编队一分为二，这两个编队分别通过障碍物之后再前进到重组位置恢复成一个编队(见图16)。这种方法只增加很少的计算量，但却能为编队移动带来良好的视觉效果。
路径栈
路径栈就是一种简单的用来记录个体移动路由信息的栈操作(后进先出，见图17)。一个路径栈记录的信息一般包括个体当前所采用的路线，现在个体正在向哪个中继点移动以及个体是否正处于巡逻中。一个路径栈对我们的目的有两大作用。
首先，它可以为一次分级寻道工作提供便利。一般来说游戏开发者会把寻道区分为两种明显不同的等级--高级(high-level)和低级(low-level)(见图18)。高级的寻道可以为个体找寻出穿越地图上不同地形和主要堵塞地点的道路，这就如同玩家大多数时候给个体制定的路径一样。低级的寻道则同时还会处理较小的障碍物并更注重处理细节。一个路径栈可以方便的存储高级和低级的寻道信息。我们可以先通过高级寻道找出一条路径并把它存储进路径栈中，而当我们必须注意避免与大片空地中的一颗树发生碰撞时就可以将低级寻道的一系列结果存入路径栈顶并执行它们。每当执行完一条路径，我们就可以将它从栈中弹出并继续执行现在位于栈顶的路径。
第二点，路径栈可以允许高级寻道被重用(reuse)。如果你回顾前面的介绍将看到组队和编队在移动时的一大要素就是所有的成员都使用相同的路径来移动到目的地。如果我们设计的路径栈可以允许多个个体参考一条路径，那就将使同一条高级寻道路径很容易的被重用。一个编队的指挥者将使用高级寻道找出一条路径并把它拷贝给编队中的每个个体，而其它个体则什么也不用做。
这样创建保存路径信息的结构还能提供给我们一些其它好处。通过将一条高级寻道路径拆分成多个低级寻道路径，我们可以在执行具体路径之前充分的对这些低级路径进行更精确的计算。而且如果我们确定高级寻道的结果是可用的话，也可以将低级寻道的工作略微推后再做。如果我们正在进行高协调度的个体移动，路径栈将允许我们向栈顶添加一条临时的用来避免碰撞的路径，并能够很好的使用这一路径修正个体移动(
解决混合碰撞
我们定义混合碰撞为同时发生在两个以上个体之间的碰撞。大多数游戏都对于可以解决的混合碰撞中的个体个数有限制，超过这个数目就只能分几次解决了。下面我们将探讨如何使用已有的移动系统对这类情况进行简单的处理。
如果我们遇到了一个由三个个体造成的混合碰撞(见图20)，首要的工作是找出其中优先权最高的个体。一旦找到它，我们就要立即找到与之碰撞的另一个个体并确定优先权最高的个体所遇到的最主要的碰撞(该碰撞可能发生在其与次优先的个体之间，也可能不是)。当我们找到了这两个个体后，剩下的工作就交给原来的碰撞处理部分解决即可了。
当最初的两个个体的碰撞被解决后，我们就要重新评估整个碰撞并更新个体之间的关系。一个更复杂的系统可以很好的解决这样的问题，但是如果简单的移走已经解决了碰撞问题的个体也能得到不错的效果。
一旦我们更新了碰撞中的个体，下一步工作就又回到寻找优先权最高的个体的碰撞上来了。我们将一直重复这一步骤直到所有的碰撞都被解决。
你可以在两个地方使用这一系统：碰撞解决部分或碰撞预测系统中。碰撞解决的规则必须被修改以适应对于个体优先级的要求，这样的修改并不难，但会增加一定的代码量。或者你可以修改你的碰撞预测系统使得只会发生两个个体碰撞的情况，然而这样做你仍然需要先找出一次碰撞中的全部个体并作出操作。
解决堆叠峡谷问题(The Stacked Canyon Problem)
所有移动系统的最终目的都是要实现智能的移动效果，而所有处理中最能体现智能的就是处理堆叠峡谷问题了(什么是堆叠峡谷问题呢？事实上当一个个体要从一群排列紧凑的个体之间穿过时所需要解决的问题就是堆叠峡谷问题，图21就是一个例子)。虽然此类问题并不能简单的一次解决，但我们可以重用前面的一些简单方法来解决它。
第一步是鉴定是否为一个堆叠峡谷问题。这是非常重要的，因为我们将要利用前进个体(driving unit)的优先级。当然我们可以利用每个个体自身的优先级来要求其它个体让出道路，但是更好的解决方法是使用前进个体的优先级。判断一个堆叠峡谷问题可以有两种方法：观察前进个体是否会把一个阻碍其移动的个体推到另一个身上或者观察移动个体的碰撞列表以寻找多重的碰撞。不论采用哪种方法，被推动的个体都应该拥有与前进个体相同的移动优先级。
一旦我们判断出将要解决一个堆叠峡谷问题，就可以采用一种简单的递归调用个体协调运动系统的方法来解决它。把第一个被推动的个体作为前进个体处理其于第二个个体之间的关系，并如此循环。每一个个体被它的前进个体推动直到它可以移动到一边而让出道路。当最后一个个体也从陆上让开后，原来的前进个体就可以继续移动了。
一个好的习惯是将已经移开的个体在移回原位。为了能够这样做，我们应该记录整个推动过程并在问题解决后倒序的执行该过程。另外如果负责移动的代码能够辨别出前进个体是否归属于一个组队，那就能保证组队中每个个体都能在原来阻碍道路的个体返回原位置之前通过。
注意
优化你的整体系统。如果你只是要做一个2D游戏，那就会有许多多余的计算是可以取消和简单化的。不论你是要做2D游戏还是3D的，你的碰撞检测系统都需要一个优秀的经过优化的个体分拣系统，这类系统已经不再仅仅用于绘图了。
对高级寻道和低级寻道使用不同的方法。过去大多数游戏对这两种寻道方式使用相同的算法。这样做的害处是如果对高级寻道使用低级寻道的算法将使高级寻道变得缓慢并且不能用于寻找长的通路；相反的，如果对低级寻道使用高级寻道的算法将会造成结果并没有将道路上的所有障碍物考虑在内或者造成一个个体能从其它个体之中穿过。一定要抓住要点制作两套寻道系统。
无论你做什么，个体总会交叠碰撞在一起。个体的交叠和碰撞是不可避免的，或者按最好情况说将是非常难以操作的。你最好尽早处理这些碰撞问题，这将使你的游戏更好一些。游戏的地图已经越来越复杂了，并且还会加入随机地图的处理。一个好的移动系统将能够很好的处理随机地图和相应的一切细节。
清楚地了解UL是怎样影响个体移动的。可变化的UL时间将是你的移动系统所必须解决的一大难题。可以使用一个简单的修正机制来解决此类大部分的问题。
只涉及单个UL的做法是过时的。没有计划的编制不可能解决好个体移动的协调问题，如果不记录上一次UL中的操作和将来要发生的问题又是不可能制作好的计划的。一个能够运作良好的移动协调系统必须在任何时候都能够参考以前的碰撞列表和预测碰撞的列表。切记解决碰撞的过程中出现的较小的变化是可以忽略的。
不要再出现傻乎乎的个体移动
简单的个体移动是简单的。一套优秀的协调系统是我们所应该追求的，因为它能使你的游戏步上一个等级并能增加玩家的乐趣。在本次的文章中我们研究了一个移动协调系统的基础功能--使用多个UL时间制定行动计划以及一套可以解决任何两个个体碰撞的方法等等。现在你应该不会再满足于你的游戏中那些傻乎乎的个体移动了。
附：
本文的部分基本定义：
移动(Movement):
本文主要指对于一条已知路径的执行。简单的移动算法使个体沿给定的路线运动，复杂的移动算法在移动的同时进行碰撞判断，调整各个体的运动以避免碰撞并允许个体组成特殊的队形共同运动。
寻道(Pathfinding):
找出所需路径的工作。所使用的算法可以是简单的遍历也可以是经过高度优化的A*算法。
中继点(Waypoint):
当个体要前往目的地是所必须经过的路径上的点。每一条路径拥有至少2个中继点：起点和终点。
个体(Unit):
游戏中可以在整个游戏地图中移动的实体。
移动算法伪码：
移动循环
{
if "增加中继点(Waypoint)"：
增加中继点。
if 正在巡逻：
沿指向目的地的方向获取下一个中继点
设置状态为"等待寻道"
else：
if 已经不能再得到下一个中继点：
设置状态为"已抵达目的地"
else：
设置设置状态为"等待寻道"
if "已抵达目的地"：
作出适当的通知(如果存在通知方式的话)
移动完成，停止播放移动动画，退出函数
if "等待寻道":
找出一条通路并将之保存
if 无法找到通路
失败，函数退出
计算出向中继点移动所需的方向
通过旋转改变个体的方向指向中继点
使用新的方向，计算一次UL时间将会移动到的位置
if 新位置将会导致碰撞
设置状态为"等待寻道"
返回循环头
判断现在和移动后的位置：
if 移动之前距离中继点更近：
设置状态为"增加中继点"
返回循环头
if 移动过程中将会经过中继点：
设置状态为"增加中继点"
跳出移动循环
}
设置加速度
进行移动
设置并更新所需要使用的动画
刷新预期位置
家园 【转载】关于帝国2中的寻路和行军算法 关于帝国2中的寻路和行军算法
一提起游戏中的寻路，很多人就会想起A*算法，的确，A*无疑是当前用的最多也是最先进的算法，在比较简单的地图上它的速度非常快，能很快找到最短路径(确切说是时间代价最小路径)，而且使用A*算法可以很方便地控制搜索规模以防止程序堵塞
一提起游戏中的寻路，很多人就会想起A*算法，的确，A*无疑是当前用的最多也是最先进的算法，在比较简单的地图上它的速度非常快，能很快找到最短路径(确切说是时间代价最小路径)，而且使用A*算法可以很方便地控制搜索规模以防止程序堵塞。
关于A*算法的文章已经很多了，上google随便一搜都能找到，但是国内网友原创的似乎不是很多，建议英文不太差的爱好者上国外的网站查找相关资料，比如http://www-cs-students.stanford.edu/~amitp/gameprog.html。
A*算法本身表述起来很简单，程序写起来也不难，两三百行轻松搞定，关键是要在代码优化上下功夫，这就很考验程序员的算法功底了。基本的思路一般都是以空间(也就是内存的占用)换取时间(搜索速度)，另外还有一些地图预处理(包括人工的预处理和用程序预处理)的技术比如多级地图精度或者地图分区域搜索等等，但我今天要讨论的不是A*算法本身，关于这方面有兴趣的网友可以另外和我交流。
不管怎么优化，寻路总是一项非常费时的工作，并且工作量和地图的大小基本成线性关系(不限制搜索规模的前提下)，现在的rts往往允许每方生产200个以上的移动单位，同时可能会有大量的移动物体需要寻路，如果同时选定100个单位点并向他们下达远程行军命令，假设每次寻路需要5ms(在复杂地图上，这个数值一点都不夸张，我是说在我的机器上)，那么就需要0.5秒的时间在寻路上，也就是说整个游戏将因此停顿0.5秒，你受的了么？
呵呵，俺们程序员是不会让这种情况出现地，通常有几种方法来避免寻路运算导致程序堵塞：
1、限制同时选定的移动单位个数
帝国2里面，这个限制是40个，当然这样一来，同一个编队里的人数就不可能超过40了，这一方面是为了减少寻路耗时，同时可能也有别的考虑，我能想到的是同时控制过多的单位攻击同一个目标可能效率会很低，我不知道其它rts游戏是否也有类似的限制，但是如果采用了下文所述的第2，第3种方案的话，这个限制就显得不那么重要了。
2、把寻路工作在时间上分散进行
可以估计一下每次寻路所花的时间，限制每个“回合”(就是游戏的一帧)最多让多少个单位寻路，其它的等下一个回合再说，这样游戏就不会停顿，但是缺点是可能会看到所有人不是同时动身，而是先后开始移动，网上有文章说为了避免选中的单位“发楞”而让玩家以为出了什么问题，可以让一时来不及寻路的单位花很少的时间凭“直觉”决定一个方向(通常就是目标所在的直线方向了)先走再说,等轮到自己寻路以后再改回来，这也是个办法，因为“直觉”的方向在大多数情况下就是正确的方向，但是据我观察在帝国2里面没有用到这个小伎俩,后面会说到。
3.这个是最实惠最有效的，就是距离相近的单位公用一条路径，所谓“相近”一般来说以互相都在视野之内为限
玩过帝国2的人都会感叹其中各种漂亮的阵型，连行军的时候都要摆的整整齐齐的一个方阵(当然前提是在空地上跑)。即使你故意挨个把他们分散了(不能距离太远)，同时选中他们并点取一个目的地以后，他们也会在行进中慢慢的自动靠拢，不一会又排成方阵了，而且，不管你让他们去地图的什么地方，他们都会全体立即响应，而不会出现上一条所说的那种停顿或者先后启动，这是怎么回事呢？聪明的你一定能想到，只要让一个人带队寻路，其他人跟着就行了，对！就是这么回事。让一个单位寻路而其余的单位跟随，这比让每个单位单独寻路要快的多了，这个带队的移动单位称之为“寻路兵”。
说到这里要提到帝国2的一个不知能不能算的bug，比如有一条很长的小河，你有一帮人马，一部分在河左边，另一部分在河右边，他们挨的很近，虽然隔着河。现在你画个框把他们同时选定，比如让他们都到河左边，因为他们相互都看得见，于是程序就选了一个人带路(怎么选的我不太清楚)，这时候可能出现两种情况：一种是寻路兵在河左边，于是他带着河左边的众弟兄朝目的地去了，河右边的一干人很想跟着(根据程序的设定，他们不需要自己寻路)但是无奈隔着河过不去，在河边彷徨了一会(帝国2的算法据我观察在原定路线不能走的情况下会先尝试从两边绕行，当然绕行的范围是有限的，如果发现绕不过去才重新寻路)，当对岸的人马走出他们视野的时候他们才想起来可以自己寻路，于是顺着河边绕过去了；另一种情况更搞笑，就是系统选出的寻路兵在河右边，本来河左边的人是离目的地很近的，但是他们不管，非要隔着河紧跟着那边的寻路兵，直到在河流的尽头与寻路兵所在的部队汇合以后，才一起排着方阵走向目的地。
关于帝国2中寻路兵的确定，就是在一队人马中选哪个来带头寻路，我还没有什么头绪。
另外，当寻路兵死亡(按了del键，呵呵)，或者被指定了另外的目的地时，剩下的单位中会重新产生一个寻路兵，重新寻路。
奇怪的是，帝国2中的农民的移动却没有采用寻路兵策略，即使彼此很靠近的一堆农民，他们移动时也不会排成方阵，而且点选目标的一瞬间会出现上文第2条所述的那种停顿，即有的农民先启动，有些后启动。在我的CII533的机器上，40个农民，huge空白地图从一头到另一头，最快启动的农民和最慢的大概相差0.5秒，延迟已经很明显了。我不太明白为什么这么设计，可能是农民行为的特殊性上的考虑，呵呵，农民嘛，向来是自由散漫无组织无纪律的:)
另外关于帝国2要说明的是它没有类似红警里面的同一方的“让路”算法，如果你让几个人把一个咽喉要道堵住，然后控制另一队人试图通过这个关口，可以看出寻路的时候算法没有考虑堵住关口的单位,因为你控制的人马径直就朝这个关口过来了，就像以为它是通的一样(这本身是合理的，因为他们不知道挡路者什么时候会离开)，到了跟前一看堵住了，左边右边的绕了两下没绕过去就回头找另一条路去了，挡路的人根本无动于衷。
现在的rts正在向网络化发展，在地图越来越大，移动单位越来越多的情况下，一方面是路径搜索算法本身的效率，另外行军算法(例如阵型，让路等等)的效率和巧妙程度也是个很值得研究的课题。
呵呵，居然写了这么多，我有时间的话还会研究一下其它游戏的寻路特点，如果有同好者欢迎和我交流，本文如果要转载，请注明是转载，谢谢！