一种优化碰撞检测算法在游戏AI设计中的应用

摘  要： 碰撞检测是游戏人工智能设计领域中的基本研究问题，快速智能的碰撞检测算法直接决定游戏效果的好坏。针对捕鱼类游戏的碰撞要求，设计了一种以空间网格划分为基础结合多重因素分析的高效智能碰撞算法，增加了相关游戏的可玩性及运行效率。
关键词： 游戏算法；人工智能；碰撞检测；网格

　人工智能技术在游戏设计中的应用越来越广泛，已经成为游戏设计成功与否的关键因素。碰撞问题则是游戏AI设计领域中的基本研究问题。碰撞问题的解决过程大致可以分为碰撞模型建立、碰撞检测、碰撞确认与响应三个阶段。碰撞模型建立就是建立参与碰撞的对象以及建立便于碰撞检测的数据模型，碰撞检测过程是根据一定的碰撞规则和因素对参与碰撞的对象在既定的数据模型下进行检测的过程，对碰撞检测的反馈数据进行分析筛查得出确认结果并执行相应的操作就是碰撞响应。虽然国内外有关学者就碰撞问题也作了大量的研究，但是针对游戏设计的算法不多，若在游戏AI设计中实现，需要进行修改优化。另一方面，不同类型、玩法、主题的游戏对于对象的碰撞要求存在着很大的差异。例如，射击类游戏比较关注子弹与目标物体的碰撞，又如动作类游戏则比较关心对象运动间的碰撞。由此可见，要根据具体游戏碰撞需求设计适合的碰撞算法来给予解决。本文根据当下热门的捕鱼游戏中的碰撞要求，设计了一种以空间网格划分为基础，结合多重因素分析的高效智能碰撞算法，增加了相关游戏的可玩性及运行效率。
1 碰撞检测模型的建立  
　近年来以捕鱼为题材的休闲类游戏发展相当迅速。例如，《捕鱼达人》成为2011年iPhone付费应用收入最高的国产游戏之一[1]。该类游戏大体是由玩家购买子弹，调整网枪的威力，就可以攻击游戏中游动的鱼类以获取积分。被攻击的鱼类品种不同，其积分也不同。玩家用来攻击鱼类的网枪共分为若干个等级，等级越高的网枪耗费的子弹越多，但其渔网捕鱼能力也越大。对于该类游戏碰撞问题的关键是如何检测渔网与鱼类动态碰撞的情况。不少开发者改良使用GJK算法[2]和LC算法[3]等有关碰撞位置计算的著名算法。以上算法都是通过计算物体间表面的最小距离来确定碰撞位置，实施过程中需要遍历检测所有鱼类对象与渔网的实时距离来判断碰撞。这样的算法虽然实现简单，但是对于变速转向对象的碰撞检测精度不高，而且随着对象数量的上升而增加运算量影响运行速率。
　本文提出的一种基于空间网格划分的碰撞检测优化算法既能增加碰撞检测精度又能减少CPU的运算量。具体是根据某种规则将游戏场景划分成一个个小的网格，为每个网格对应一个列表用来记录所有属于该单元网格的对象。由于不相邻单元网格的对象之间距离较远，因此只需检测同一个单元网格或相邻单元网格内的对象间的相交情况即可。在捕鱼类游戏中，主要检测的是渔网与鱼类的碰撞，所以渔网也要进行网格化，可以利用场景网格来记录即可，这样只要直接检查渔网打开时所属网格矩阵范围内有可能碰撞的鱼类对象，而无需遍历所有的鱼类对象了，因此大大减少了检测的数量。
　为了不影响碰撞检测的精确度，场景分割网格应以正方形单元格为单位，大小与最小鱼类的正方形包围盒一致。鱼类要设置捕捉特征点，等级越高的鱼类越大，特征点就越多（最多有6个）。特征点也可以是动态变化的，例如魔鬼鱼当翅膀全部打开的时候所有特征点才可以被捕捉到，如图1所示。然后根据鱼类对象特征点所在的位置将各个鱼类对象分配到该网格的对应单元格内。

　场景网格分割更好地记录了鱼类对象在屏幕的位置和渔网捕鱼矩阵，从而利于随后的碰撞检测。鱼类对象的位置可以通过其特征点定位实现，给每一个单元格建立一个寄存器来存储该单元格中不同鱼类对象的特征点。实际应用时可以利用一个二维数组来实现单元格特征点存储器的功能，二维数组行数是网格单元格总数，列数是游戏鱼类对象的实例数上限。当一种鱼类对象实例化时都需要产生一个对应流水标识号，利用单元格索引号和鱼类对象流水标识号构成二维数组内特征点存储单元的索引值。这样的算法能迅速实现数据查找和更新。与此同时，鱼类对象也需要设置一个存储特征点所在单元格索引值的存储器，存储器的大小根据对应鱼类特征点数量来确定。该存储器可以使用一个一维数组来实现，特征点标识号可以作为数组的索引下标。
　鱼类对象在游动过程中，特征点位置必然发生变化，因此需要实时判断特征点所在的单元格，更新单元格特征点寄存器对应的数据项目，并且把单元格索引值重新计入鱼类对象的特征点存储器。这样就可以实时地为碰撞检测提供准确的数据基础。
2 碰撞检测的过程
　碰撞检测首先需要建立监听器，监听对象的状态变化以便触发碰撞检测过程。例如，鱼类对象碰撞检测可以利用游戏场景网格，监听单元格特征点寄存器，若寄存器存有不同鱼类对象的特征点，就可以触发鱼类对象碰撞检测过程进行处理。
　当玩家使用某种等级网枪撒网捕鱼时，根据撒网点所在的单元格，推算出渔网阵列，即可获得一个单元格索引值集合Ai。碰撞检测过程是逐一抽取集合中的单元格，检测其中存在有特征点的鱼类对象，然后逐一把这些鱼类对象的特征点位置寄存器数据集合Bi直接与渔网单元格索引值集合Ai进行比较，若是Bi∈Ai，则可以判断该鱼类对象所有特征点都包含在渔网中。

　传统碰撞检测过程最重要的是准确地检测碰撞，但从游戏的可玩性来说，仅以对象物理状态来判断碰撞是不够的，需要分析其他游戏性因素进行判断。由此可以设定碰撞检测函数Pi=f（x1+x2+x3+x4+x5+xn）， Pi代表某鱼类对象与渔网碰撞值，x1~xn代表各项因素，每项因素都有不同的权重，从而影响最终的碰撞值。各项因素设定及权重分配（以5项因素为例）如表1所示。

　根据不同因素所起的作用，可以动态调节它们之间的权重值，游戏在相同的框架下也能体现出不同的游戏性。例如，动态修改x1与x2之间的权重，则捕鱼技巧和游戏难度之间的体验感就会发生变化。再者，可以在一些因素中加入动态参数，使因素权值发生游戏性的变化。例如，对用户在线时间参数x4引入相关计算公式y=[1+sin（x×π/t）]×x/30，y是因数权值，x是时间值，t是游戏送分减分周期，如图4所示，曲线的斜率和周期都可以作适当调节，使权重值随在线时间波动上升。

3 碰撞的确认与响应
　此外，必须是在渔网矩阵单元格中存在特征点的鱼类对象才会触发碰撞检测函数，函数是根据各项因素权重值返回碰撞值，以此决定是否发生实质性碰撞。例如，上文提到的鲤鱼和墨鱼，因为B1∈A1、B2∈A1，所以它们的x1权重值都可以得到40，而魔鬼鱼因为B3∩A1=20，只有一个特征点与渔网碰撞，它的x1权重值只为8（魔鬼鱼共有5个特征点）。从难度系数上来说，魔鬼鱼最高、鲤鱼最低，通过随机换算可得魔鬼鱼x2=10，墨鱼x2=12，鲤鱼x2=20。若其他因素假定都一样合共为20，则可以推算出鲤鱼碰撞值P1=40+20+20=80，墨鱼P2=72，魔鬼鱼P3=38。碰撞确认与响应的过程如图5所示，碰撞检测Y值低于60分，则判断渔网捕鱼不成功，需要累计该鱼类对象被攻击的次数，以增加下次被捕的得分值。最重要的是要触发鱼类转向逃跑的函数。若碰撞检测Y值高于或等于60，则判断该鱼类对象被捕获，鱼类对象触发捕获函数启动捕获动画，并实时增加玩家的积分值。但一个游戏往往会暗含一些非常规因素。例如，玩家突然获得了超级鱼枪，只要及时使用超级渔网接触的所有鱼类都被捕获。在实现中，直接将非常规因素折算成相应的得分值与Pi累加后再进行判断就可以了。

　游戏AI算法跟一般程序的算法要求不同的是除了要考虑时间复杂度与空间复杂度的因素外，还要考虑游戏复杂多样的可玩性要求。本文提出了一种新的基于空间网格划分结合多重因素分析的智能碰撞算法，利用空间网格划分和特征点来判断对象碰撞关系，并分析游戏性的各项因素，合理分配权重实现碰撞检测，从而提高了算法的执行速度，增加了游戏的可玩性。对相关游戏程序设计具有一定的应用参考价值。
参考文献
[1] 艾瑞咨询.2011年中国网络游戏行业四大盘点[DB/OL].（2011-12-13）[2012-02-01].http：//game.iresearch.cn/15/20111213/158889.shtml.
[2] Matthew Peterson. Interactive QuickTime[M]. Elsevier Inc.2004：99-115.
[3] DOBKIN D P， KIRKPATRICK D G. A linear algorithm for determining the separation of convex polyhedra[J]. Journal of Algorithms， 1985（6）：381-392.
[4] PETERS K. Flash ActionScript3.0动画高级教程[M].苏金国，译.北京：人民邮电出版社，2010.
[5] STAHLER W.游戏编程数学和物流基础[M].北京：机械工业出版社，2008.