人工智能、数理算法

oraclelang · 发表于 2006-4-27 12:28

碰撞检测

　　所有碰撞检测系统的基本目标都是判断两个个体是否发生了碰撞。这次我们所介绍的碰撞检测都是假设两个物体的碰撞，将来我们会专门介绍大量物体互相碰撞的检测问题。但无论是两个物体还是多个物体发生碰撞有一点是共同的：每个物体都要收到碰撞信息以便作出适当的响应(分开彼此)。

oraclelang · 发表于 2006-4-27 12:28

大部分即时战略游戏中使用的简单的碰撞判断实际上是将每一个个体看作一个球体(2D中是圆)，再进行简单的球体碰撞检测，而不在意这样简单的判断是否能够满足游戏对于碰撞的要求。这样做确实有利于提升性能，即使一个游戏要进行非常复杂的碰撞判断--例如判断击出的拳头是否击中敌人，或者甚至是低精度的多边形(polygon to polygon)交叉判断，这时为可能出现的碰撞保有一个球体区域往往也能够提升程序的性能。

oraclelang · 发表于 2006-4-27 12:28

当我们设计一个碰撞检测系统时要注意面对3种截然不同的实体：单个的个体、一群个体的集合以及经过队形编制的个体群(就像《帝国时代2》中的阵形一样，见图2)。事实上对所有这3种类型使用简单的球形判断都能工作得很好，单个个体可以简单的使用单个球体进行它的全部碰撞判断，而对于其它两种情况只需要再稍微增加一点工作量。

oraclelang · 发表于 2006-4-27 12:28

对于一群个体的简单集合来说，可以接受的碰撞检测下限是对整个组中的每个个体进行检测。这种方法将允许那些不属于你所选定的组的个体轻松的混入你的组队中。相对来说，对编队所要进行的碰撞检测就要更加复杂一些了。我们还应该认识到这种简单的组群还有一种特殊的性质决定了我们应该尽可能的简化对它所采用的碰撞检测方法--这种组群应该能够随时随地的将排列方式变换成任何可能的适应当地空间大小的阵形

oraclelang · 发表于 2006-4-27 12:29

对于编队来说，不仅仅要进行如上面的组群那样简单的个体碰撞检测，还要进行大量更加复杂的检测操作。首先要保证编队中的个体之间不能互相碰撞，同时如果编队中的各个个体之间有一定的缝隙，还要保证任何一个不属于该编队的个体不能占用这一空间。另外，一个编队应该不能改变队形或重组，但是游戏的规则又可能规定当没有足够大的通路提供给整个编队保持队形穿越某一障碍物时，编队可以先散开，待各个体越过障碍物之后再重新组成编队，这样的设计更加体贴玩家。

oraclelang · 发表于 2006-4-27 12:29

我们可以尝试使用基于时间的碰撞描述机制。立即碰撞用来描述当前正发生在两个个体之间的碰撞；未来碰撞用来记录预计在程序运行的后续时间中将会发生在预定地点的碰撞(当然，前提是将要碰撞的对象都不改变各自的移动路线)。在任何情况下立即碰撞的情况都应该比未来碰撞的情况更优先被处理。同时我们也应该定义碰撞的3种状态：未处理的、正在处理和已处理完毕的。

oraclelang · 发表于 2006-4-27 12:29

使用"离散"的算法达到"连续"的效果

　　大多数移动算法从根本上都是"离散"的，不同于数学上的离散定义，这里所说的"离散"指移动算法在按照给定路径从A点移动到B点的过程中从不考虑中间路径上可能出现什么东西，相反，在"连续"的算法中就会考虑这些情况。这样做的一个问题就是当我们进行一个Internet游戏时(众所周知，由于网络速度的限制，这类游戏的UL时间一般较长)那些速度较高的个体很可能在一次UL时间中移动相当大的一段距离(由于UL时间变长)，而当这样增长的UL连续出现时很可能出现个体跃过了其它本应发生碰撞的个体。如果这样的情况出现在一个工人的身上那并不会有人在意，但显然任何玩家也不会希望敌人能够从辛苦建设的城墙中穿越而过进而攻击玩家的基地(某些早期及时战略游戏中出现的"穿墙"的BUG就是有这种问题造成的)。大部分的移动系统现在采用限制个体移动距离的方法来对付这一问题，该方法可以有效的简化所需的处理。在离散型的移动算法中解决这类问题的方法如下图所示

oraclelang · 发表于 2006-4-27 12:29

一种有效地解决方法是将一次移动拆分成多次移动的集合。这种拆分需要满足一定的移动距离上的要求，这要求就是要保证每次移动的距离刚好短于任何个体的长度，这就可以保证不可能有任何个体移动到当前个体的路径上来，从而避免了从其它个体之上跨越过去的情况。当每次这种拆分后的移动结束时我们就要使用碰撞检测系统对个体的当前位置进行碰撞检测。你可能会想到如此频繁的计算大量点的碰撞信息将会极大的增大系统消耗，没关系，在后面的章节中我们将会介绍一种方法来降低这种计算对系统的消耗。

oraclelang · 发表于 2006-4-27 12:30

另一种方法是创建一种称之为移动线路(Move Line)的对象。我们可以使用这条移动线路来描述个体的移动，个体的原始位置作为线段的起点，目的地作为线段的终点，就好像《红色警报2》里所表现出来的那样。这种方法并不用添加新的数据，但是会加大碰撞检测部分的复杂性--我们必须把简单的球形碰撞检测修改为对一个点到一条线段的距离的检测，而这样做将会增加计算的难度，也会消耗更多的时间。大多数3D游戏都已经实现了一种可以快速挑选出可被游戏者观察到的物体的分级系统(也就是能够迅速地判断出游戏中的哪些物体处于玩家角色的视野之内的系统)，我们可以对该类系统进行修改，使它们可以用来快速挑选出那些在我们的游戏中可能发生碰撞的个体。这样做的好处是大幅度地减少了需要进行碰撞判断的个体的个数，于是所需要的计算量常常就能够降低到所能允许的范围之内了。

oraclelang · 发表于 2006-4-27 12:30

位置预测

　　经过上周的工作，我们已经有了一个简单的移动算法和一个管理个体碰撞的列表，还有什么工作是强化个体之间协作所必需的呢？位置预测(Position prediction)。

　　预测的位置只不过是一个位置列表(至少包含个体的运动方向和时间标记，有时也需要记录加速度等信息)以指出未来某时刻个体所在的位置，参考图4。一个移动系统可以将用来实现个体移动的算法拿来负责计算个体的位置预测，这些预测越准确其可用性也就越大。当然预测计算也会增大计算量，为了不降低游戏的效率，下面我们就来讨论一下如何减少多余的CPU消耗