|
|
问题在跑酷类和动作类游戏中，我们会遇到要求多边形碰撞检测的问题，很多时候我们采取逃避，还是用Tile式的模式，只是添加一些30度45度的角来解决斜坡的需求。但是其实好的跑酷类游戏中，地形的形状应该是任意的，就像索尼克这样的相对来说就比马里奥有了进步，当然索尼克在马里奥之后这么多年也该有了进步。
从策划的角度来说，当我们需要设计一个跑酷类游戏或者动作类游戏或者百战天虫玩法游戏的时候，我们游戏的主系统中有这么一个有趣的数值设计要做，那就是结合多边形地形的碰撞算法。这里分享一下我们在最近一个跑酷类游戏中的应用数学解决这个问题的方法，希望能对大家有所帮助。
思路
看过很多多边形碰撞的算法，优化的做法是先算外框（矩形），如果矩形相交则进一步判断其中多边形是否有共同位置的点。这个做法不错，但并不适合跑酷、格斗、百战天虫这样需要像素级运算的游戏，我们需要从数学的角度出发去想一个办法——数值设计。我们把多边形碰撞先拆解为“一个点是否在多边形内”这样一个问题，毕竟在跑酷游戏中，逻辑上角色完全可以就是一个点。
解决办法
这个算法很简单：
设：点m和多边形p，多边形p由点p1,p2...pn组成。
1，从点引申一条平行于X轴并与X轴同向的射线（计为mx，千万不要“复杂”到向量问题上，向量在我们那时候是高中级别的，单是射线是初中级别的，Keep it "Simple"）。
2，判断射线与p的每条线段是否相交，若与奇数条线段相交，则有m与p相交；若与偶数条线段相交，则有m与p不相交。
3，策划设计如果m在p上某条线段上（相切），也算是相交的话，则m为虚点，否则m为实点。
这样一来，问题进一步简化为“一条平行于x轴的射线与线段是否相交”，这个方法很简单：
设：线段ab的两端点(ax,ay) (bx,by)，射线ma(y=n)，从虚点(m,n)射出。
那么：
1，如果ax和bx都小于等于m，ma与ab不相交。
2，ay,by同时大于或者小于n时，ma与ab不相交。
3，其余情况下，ma与ab相交。
因此我们可以得到伪代码(haxe)：
public function SegmentIntersect(m:Int, n:Int, aX:Int, aY:Int, bX:Int, bY:Int):Bool{
//你当然可以用Float，但我们的目的是像素级别的，而不是Flash自带的向量方式，因此点应该都是Int的。
return !((aX<=m && bX<=m) || ((aY<n && bY<n)||(aY>n && by>n)));
}
之后我们For循环去对多边形p的每条线段进行判断，看相交次数得到是否点m在p内：
public function PointInPolygon(mX:Int, mY:Int, p:Array<Array<Int>>):Bool{
//p是一个数组，代表多边形的每一个点，p的每一个单元都是[x,y]坐标，一个点。
var intersectTimes:Int = 0; //相交了多少次
for (i in 0...p.length){
intersectTimes += SegmentIntersect(mX,mY,dasP[0], dasP[1], dasP[(i+1) % p.length][0], dasP[(i + 1)% p.length][1])==true?1:0;
}
return ((intersectTimes % 2)==1); //奇数次代表相交。
}
依靠这个判断2个多边形是否相交
有一个性质：假如点m与多边形p相交，那么m所在的多边形pm一定与p相交。注意！pm与p相交时，pm未必有任何一个点m会与p相交，但是，两个多边形p1和p2，就有性质：
1，如果p1中的某一点pm1与p2相交，则p1与p2相交。
2，如果p2中的某一点pm2与p1相交，则p1与p2相交。
3，如果p1中没有这个pm1（能与p2相交），p2中也找不到pm2，那么我们可以认定p1与p2不相交（这个没有实际测试过，边际问题可能我考虑的还不周全，但目前有效），因此有：
function PolygonIntersectPolygon(p1:Array<Array<Int>>, p2:Array<Array<Int>>):Bool{
for (p in p1){
if (PointInPolygon(p[0],p[1],p2)==true){
return true;
}
}
for (p in p2){
if (PointInPolygon(p[0],p[1], p1)==true){
return true;
}
}
return false;
}
总结
这样的碰撞算法，其实适合于你需要得知若干个多边形之间互相是否相交，但不需要知道他们相交面积的时候，比如格斗游戏，再比如跑酷游戏中（角色碰到某个地形就死了，但却要在地形上跑，所以有双重计算多边形碰撞的地方）。
如果你一个策划不想总被程序说这个不能实现，那个没有办法，那你就该把如何实现的逻辑想法按照这样先设计好，毕竟程序说不能实现，大多时候是因为他/她不知道你要实现什么，虽然有时候的确是为了偷懒。一个数值策划存在的意义，就是利用数学知识建立模型来辅助游戏系统的设计，然后进一步提炼出参数用于关卡设定，而不是关起门来重造车轮，去修改别人已经证实可用的公式——那无异于让整个行业原地踏步。
|
|
发表于 2013-7-22 12:13:06
发表于 2013-7-22 14:33:38
楼主