痕迹

汤锴(42350817) 02:24:44
基本看完了QuakeIII的AI代码，同时浏览了一份由开发QuakeIII Bot AI的程序员所写的文档。

感想太多，一套强劲的AI引擎并不是那么简单的，虽然我已经非常认真地看，但也只不过了解大概

QuakeIII的AI体系分成4层：

4 Team leader AI
3 Misc. AI，AI Network，Commands
2 Fuzzy，Character，Goals，Navigation，Chats
1 Area Awareness System，Basic Actions

其中第1层是基础，AAS是一套由BSP计算出来的空间解析数据，保存在单独到文件

而我们通常意义上最为关心的寻路，其实只不过是Navigation这一个子项而已

下面只讨论AAS和Navigation。

AAS作为整套AI引擎的核心，也是基于BSP的基本思想而创建的，它的最基本单位是Area，Area必须是凸集，并且不能包括Gaps（悬崖）因为Gap会导致Bot掉进去，AAS编译器用了一整套数学方法确保这一点，算法其实不是非常复杂，但对Area进行了高强度的优化和纠错（合并，融合等）

而AAS的思想，一句话概括就是：存储了Area之间的连通性。
听起来很简单，其实极其复杂，Area之间的连通方式在QuakeIII中有非常多种：
直线游泳
直线行走
直线蹲着走
跳上一个移动平台
从悬崖边落下
跳出水
跳
传送
使用电梯
使用跳板
Using a bobbing platform（不知道什么意思）
火箭跳

文档作者逐个分析了每一种连通性的数学计算方法，实在是足够复杂，尤其是涉及到“跳”的算法，这里就不说了，很难说清楚

有了AAS，QuakeIII在游戏中使用A*算法进行寻路。
又是A*，听起来很熟悉不是？我查了很多论坛，很多程序员试图在3D游戏中使用他们熟悉的A*但却不知道该如何下手，原因很简单：3D游戏关卡是基于复杂的几何数据，而不是简单的2D网格，而A*算法必须依赖于类似于网格这样的“场景拓扑图”才能工作
但QuakeIII有了AAS，AAS正是对场景拓扑结构的描述，所以A*得以应用

细节方面，AAS中场景被划分成Area，由于Area本身是凸的并且不存在Gap，所以在Area内部的寻路被认为是“基本寻路”，也就是直线过去（当然其实情况复杂的多因为还包括游泳，传送等复杂情况），而Area之间则用AAS连通性由A*计算路径。

QuakeIII为了实时效率，并且由于QuakeIII的场景很少动态变化，所以缓冲了临时计算结果，结果分成Area Cache和Cluster Cache两种。

Cluster是Area的集群，在Cluster内部具备相对简单的寻路方式，Cluster之间由Cluster Portal相连，而Cluster Portal本身就是一个Area
汤锴(42350817) 02:32:33
然后我才开始谈到我的想法：
1 A*算法是可调节的，而且7Days中敌人数量不多，所以即使是手机的CPU也应该能够负担
2 相对于手动放置路点，AAS文件容量开销大得多
3 7Days中的AI（其实大部分AVG游戏都是如此）是极度简化的，我们基本上只要考虑Navigation（寻路）就行了，在这个狭义的范围内，我们可以认为AI难点就是寻路
4 我们不光是只考虑Navigation，而且我们的移动方式也极度简化：没有游泳，没有跳（更没有那些稀奇古怪的东西比如火箭跳），没有电梯（至少敌人不会进入电梯），没有移动的平台（打死我也不做，太复杂了），没有蹲着走，甚至也不存在“悬崖”这种东西（也就是不会从高处落下），所以QuakeIII的那么一大堆连通性只剩下“直线行走”这一种，被极度简化
5 即然不存在“悬崖”，那么AAS计算中的GravitySubdivision就不需要做，换句话说，我们不需要考虑Gaps

总结一下：
我们只用考虑“寻路”，并且只需要考虑“直线行走”，而且AAS计算不需要考虑Gaps
汤锴(42350817) 02:45:00
然后我认为现在其实只剩下两个选项：
1 做一个相对简单的AAS编译器（因为要考虑的情况少得多了），这应该会花一定的时间但我想可以实现，在游戏中利用AAS寻路但不见得非要用A*
2 仍然手动放置路点，换句话说，沿用以前老的做法，但做少量修改

先说一个前提：其实直到QuakeIII之前，都没有任何游戏能自动生成场景拓扑（为什么又是Quake...），包括大名鼎鼎的半条命，虚幻，虚幻竞技场，都需要手动放置路点

然后分析两种做法的优缺点：
方法1：
优点：
不需要手动放路点（同时意味着较少的BUG，因为路点必须被正确放置才能起作用，而人总会出错的）
缺点：
更大的容量开销，更多的编程代价

方法2：
优点：
不需要复杂的编程，容量很小
缺点：
需要手动放置路点

其实方法1和方法2的优缺点正好互相相反

经过思考，我认为“不需要手动放路点”是一个足够“诱惑”的优点，因为7Days做到现在，只出现过很少几个需要放置路点的场景，而这些场景几乎每一个都出过问题。如果以后路点放置的场景数量增加（比如，第5天），我感觉反复调整路点的工作简直就是噩梦！
和这个优点比起来，“更多的编程代价”显得就比较值得了
而“更大的容量开销”对于手机游戏来说不能忽视，我想首先我可以下载QuakeIII观察AAS文件的平均尺寸，从而大概推断容量开销；其次我认为也值得先把AAS编译器做出来看看，再下结论

最后，如果AAS编译器由于种种原因开发失败，那我们至少还有方法2作为后路可以用
汤锴(42350817) 02:50:09
现在的任务就是开始实现AAS编译器，然后才是写游戏引擎代码

AAS编译器有现成的代码可以参考，但他们弄得太复杂了，我们完全没有必要（原因上面也反复解释过了）只有先完全看懂代码，然后从中提取对我们有用的部分。

其实，我猜测，由于我们只需要考虑寻路，而且寻路又如此简化，AAS计算过程和最终数据应该可以更简单，最终我很可能完全重写一套简单的AAS编译器，而不是直接摘抄。

OK，到此为止，准备睡觉