云风的 BLOG: 碰撞检测

我始终认为，在 MMORPG 里采用多边形碰撞检测是件很傻的事情。当然傻不是坏事，基于多边形碰撞检测，一帧检查一次的这种做法，实现起来非常简单。很符合 kiss 原则。我们只需要一点点数学知识和一点点编程技能就能做出来了。反正 client 上，也就检查一个主角。加上可以使用简化的碰撞模型，进一步的减少运算量。

但是放在服务器上，这个运算量可不小。所以这几天我寻思着找个更好的方法出来。

据看过代码的朋友说，使用 unreal2 引擎的天堂2 当年用的打格子的方法来检测碰撞的。打格子同样是一个老土而且巨傻的方案。从 2d 的年代一直流传下来。非常非常的符合 kiss 原则 :D 同时我知道的还有我们公司已经上市的游戏产品，几乎都采用这个方案。

魔兽世界似乎不是这样做的，我想是因为 wow 的地图过大，如果把整个阻挡信息用位图保存起来，会吃掉大量的内存。即使大部分内存根本不需要访问，那被占用的地址空间也非常可观。早期 wow 的做法是，服务器不于检测。从先前的 wow 外挂那飞天遁地的能力来看是如此。

关于阻挡信息的压缩，这里就不想详述了。如果做连续地图如魔兽世界那么大，必须压缩的话。至少四叉树会比较有效。

这两天，我的想法是尝试用多层的平面来描述地图信息。每个平面上采用线段和园构成的矢量图形。（后来实际编码时，偷懒去掉了圆）

采用矢量信息，数据量比阻挡信息位图少了不只一个数量级。所以在单次运算量不增加很多的前提下，总的运算量会下降很多。具体思路是这样的：

当需检测物体有了一个速度后，从出发点发出一条射线，判断跟最近的障碍物（通常是一条线段或一个圆）相交的距离，并估算出时间。设置一个 timer 当时间时做出相应处理。

这个估算的距离不必完全精确，只需要小于等于实际距离即可。所以无论是判断线段相交还是圆相交都不必解方程精确计算。我们只需要取障碍物的外截矩形，做一个简单的碰撞检测。再可能发生碰撞时，以 x 方向和 y 方向的靠近速度来估算距离就够了。

采取这种逐步逼近的方法，障碍物比较稀疏的场合，会非常的有效。

利用这个矢量地图来做寻路，更是非常有效。这次就懒的写了 :D

Comments

关于碰撞我正在找前人用过的各种方法，最好，有前人总结成书。那样，就可以很好的在前人的基础上做出自己的新方式。

Posted by: 笑笑和尚 | (12) November 21, 2008 04:22 PM

我不知道为什么大家都推崇4叉树方式或者tile方式，毕竟如果是真3d那么collision detect是绕不开的，而且在convex或者bounding box/cylinder模型下并不太耗费,server端只是校验客户端位置不需要每一个刷新周期都做。。。

Posted by: Mandi Zu | (11) March 24, 2007 11:15 PM

抱谦，中文打字不方便

Posted by: Mani Zu | (10) March 24, 2007 09:50 PM

Server-side collusion detection don't have to be simple and tricky, use less Collusion detective routines in server side , or do it less frequently compares to the client, also path finding is more an issue than collusion detection when it comes to cpu consuming....that should be the last to worry about when making a succesefuly MMOG in china. And regarding lineeage2 server implementation, must be some sort of geometry hull i believe, while the client uses original collision detection routines from UE2 which is quite fast already.

Posted by: Mani Zu | (9) March 24, 2007 09:49 PM

大忽悠

Posted by: Anonymous | (8) March 7, 2007 07:51 PM

这个问题云风想的简单了。即使是client端的碰撞检测，要做到精确和高效并不是一件简单的事情，不是“只需要一点点数学知识和一点点编程技能”。现在的3d游戏，包括wow，碰撞模型都是很精细的。

Posted by: llazyworm | (7) January 3, 2007 05:04 PM

我想wow的服务器从一开始就有3D障碍的数据，只是没有用来做玩家行为的检测。否则服务器端的npc行走如何计算？

Posted by: N/A | (6) January 2, 2007 02:01 PM

用位图加上4叉树压缩的内存消耗不会很大，在数据制作上要比线段简单。

Posted by: analyst | (5) December 29, 2006 08:47 PM

多层地图，韩国一些3D游戏是采用这种手段解决的。

Posted by: sunway | (4) December 29, 2006 06:01 PM

另外，如果是真 3d ，碰撞检测就必须用八叉树了 (IMHO)