[数值设计] 分享一个高效的动作类、格斗类游戏碰撞做法

猴与花果山

qowp332 发表于 2013-7-27 19:48
http://www.box2d.org
这个比较简单，只需要碰撞算法的话，只看Collision部分的代码就行了 ...

呵呵，辛苦你找了这么久才找了个只要写代码的人都知道的box2d，没必要去研究他的算法，何况他的算法并不简单，你能说出“比较简单”我真挺佩服。
看得出你用心问了人了才得到这么一个答案，但是人家肯定不知道你为什么问这个，我来告诉你好了，我们游戏采用的是伪物理的，所以box2d并不合适，用他的话我们需要设定太多的特殊处理，去排除掉我们不需要的物理规则，而且太多的条件要去排除，不好用。box2d也解决不了传统游戏的一些特殊需求，比如站在山上按下和跳到下一层，所以才会去思考这么一个碰撞。
一般看到题目，懂行的就知道了本意上已经不是要做愤怒小鸟这样用物理引擎的游戏了，所以说不可能会推荐box2d之类的，更何况box2d对于开发游戏尤其是手游的人来说……怎么讲呢？你要怀疑一个开发手游的程序员不知道box2d，反而显得自己比较无知了……

qowp332

猴与花果山 发表于 2013-7-27 21:30
呵呵，辛苦你找了这么久才找了个只要写代码的人都知道的box2d，没必要去研究他的算法，何况他的算法并不 ...

   我的意思是让你看看现成的算法，不要再搞一些自创算法什么射线相交了，有现成的完美算法不用，自创算法容易漏洞百出，box2d里面的多边形碰撞算法就几个函数，和物理运算什么都分离的，很快就能看完。

还有策划没事别太研究算法，除非你真想深入搞程序

猴与花果山

qowp332 发表于 2013-7-28 17:50
我的意思是让你看看现成的算法，不要再搞一些自创算法什么射线相交了，有现成的完美算法不用，自创算法 ...

我可真没那么大本事自创算法…………只是想想更优化的算法而已，Box2d那套东西不适合这个类型的游戏的，跑酷类游戏，伪物理引擎的，所以不太适合，策划在项目开始前必须思考好自己要做的游戏是什么技术范畴的，才能跟程序交流算法问题。
其实这贴讨论的东西可以说是一个边界问题，程序和策划边界上的，很多项目是2边都不管，结果互相推责任到最后做不了，但是其实这种问题就是策划应该管的，工作的目的只有一个就是把事情做出来，我们小团队和大公司作风不一样，出了问题谁能就谁解决，快速有效，不是什么问题发生了，信里来会里去的，结果折腾一礼拜上班打游戏想借口不干事儿。
现在这个问题基本已经解决了，楼上有人还不知道问题是啥……我简单说说，就是一个横板跑酷游戏，需要支持任何角度的地形，那么问题来了：
1，如何建立地形的数据结构（策划关卡设计表、程序逻辑运算都需要）。
2，如何解决碰撞和一些边际问题，毕竟游戏中很多功能为物理，伪物理就是伪科学，所以你要想好大多情况下人类能接受的，这问题很主观，但是由于本身就违背客观，所以才去这么思考，但是没办法，你玩过很多游戏的确都是伪物理的，百战天虫其实就是，这个我最清楚了。
3，为何不能用box2d这样的物理性质的，这个在立项时我们已经明确——游戏的难度适合大多人，而物理类游戏其实难度相对较高（我个人是没觉得高，但是的确……），另外就是很多动作游戏习惯性操作是物理环境下很难实现（麻烦，也不是说绝对不能，项目能做3个月就能，现在是3礼拜内要从头到尾做成产品，产品比游戏复杂多了，包括各种小细节都要搞定了），所以避免使用这种物理引擎去开发（但肯定不是说这个不好，也许以后项目会用到）。
4，在以上前提下，如何去做到各种地形都能支持，其实就是一个挺麻烦的问题，事实上国内还几乎没有解决这个问题的团队，至少还没人肯共享心得。你可以想象一下，假如它不是跑酷，是FC上的冒险岛，要支持一个50度的斜坡，还是在按照轨道移动的，那么——首先我人能不能站上去？其次地形移动的时候人的移动轨道如何？两个地形相交的时候怎么处理？
我们采用entity system这种3D很多成熟引擎的思路，实际上是为了一个项目做完了不能只积累了开发人员的经验，而是希望一些component和system可以沿用到今后的项目中去，因此从策划设计开始就必须很关注它的“客观性”，这才是设计的难点，毕竟我们的目标是要将别人3个星期能做的游戏在3天内做完，1周内成为产品，所以积累，随时随地都在进行。
这套东西最后应该不亚于box2d，甚至战略意义上远超过box2d，于是，这个问题就浮出水面了。这就是系统策划的活——分析需求-〉推理机制-〉设计系统-〉布局细节-〉着手开工（后2步就是本贴讨论的焦点），程序员要做的是搭建环境（当然不是教你用开发软件）-〉优化算法-〉根据实际分析如何更好地加入到底层大家庭，这样才能升华到引擎。
所以说，实际上你说box2d，那是对的，但是在我们的环境下，那不合适，所以没法沿用，只能“自创”（这真算不上自创，我们谁都没这本事，人家可是创了几千年了……）。

快乐杰克

从本帖看来，猴子做引擎还是蛮有点心得的嘛。

要完成手游这样小规模的游戏产品，程序兼任策划是常见现象。

qowp332

猴与花果山 发表于 2013-7-28 18:30
我可真没那么大本事自创算法…………只是想想更优化的算法而已，Box2d那套东西不适合这个类型的游戏的， ...

真长。把我都绕晕了。
你的意思是说你那个游戏的地形是一堆线段连成的轨道是吧，我明白了

还有百战天虫不是伪物理吧，里面物理效果可很全啊

Yuki001

昨天看到这个帖子，勾起遥远的做横版平台游戏的回忆了。稍微回复补充下碰撞处理整体的知识流程。具体的内容网上都有。
游戏的完整碰撞处理流程分为2大步：1.碰撞检测。2.碰撞响应。碰撞检测分为2步，粗检查和细检查。LZ 说到的只是碰撞检测的细检查而已。
关于粗检查：在碰撞检测前的优化剔除步骤，就是LZ说的先检查包围盒，前面有人推荐看看Box2D的代码实际上是很有好处的，因为Box2D里面的粗检查做的挺不错的。以前的版本用的扫描轴算法，后面用的是动态AABB树。这2种方法对大量的动态物体比较适合。另外静态的关卡地形可以预处理用空间4叉树剖分，粗检查起来很快。
细检查的多边形碰撞，其实有一个定理叫做SAT(轴分离定理)，可检查多边形以及圆的情况。一般用这个就够了。因为粗检查剔除的东西差不多了。细检查不需要特别去优化。
碰撞响应也是比较关键的：你知道2个物体碰撞了。但是你怎么让这2个物体脱离碰撞状态。怎么样把一个物体从另外一个物体内推出。按法线推出还是按xy方向推出，物体速度很快穿过另外一个物体怎么办。物理引擎里面一般按物理计算推出。不过不是很适合横版游戏。横版另外有一种2次移动法推出，就是分解速度为x 和 y轴移动。先y后xy。

猴与花果山

Yuki001 发表于 2013-7-30 14:27
昨天看到这个帖子，勾起遥远的做横版平台游戏的回忆了。稍微回复补充下碰撞处理整体的知识流程。具体的内容 ...

4叉树的做法是个不错的思路，我也试过，但是后来仅把它用于储存已经产生过的地形了……关键是没想到后来做的地形块会这么大，只能说初期设计思路上除了点瑕疵。
移动的确是x和y分开的，这个其实大家都是这么做的。
关于box2d，我的态度就像对cocos2dx一样，我不说它不好，只能说它已经无法满足我们的技术层面需要了……cocos2dx和box2d，在我们的entity system里面还有一样的代码，我们都把它们拆解了并在我们的体系下完美重现了，不过正在考虑以除掉这些component和system，因为他们的好处我们已经发挥到更好的地方去了，剩下的那些也是不需要的东西了，这就是残酷的知识吸收，也是一种互相学习的结果。

千两

先用四叉树进行筛选，精细的检测可否使用图片来处理呢？
网上有这样说的，取两个图片的点逐行逐列迭代，如果遇到某个点两张图片均有颜色存在，即判为碰撞。同理，进行（n-1）！次比较后得到全地图的碰撞可能。
不使用数学的方法的优点就是可以在各种环境下都能良好的工作，就是不知道效率如何。

Yuki001

千两 发表于 2013-7-31 09:24
先用四叉树进行筛选，精细的检测可否使用图片来处理呢？
网上有这样说的，取两个图片的点逐行逐列迭代，如 ...

也是可以的，只不过不是用图片，而是用一张mask图，有可能比原来的图片小的多。这种方法在大致像素级别可以比较精确。
另外补充一种4叉树的方法。4叉树在2D tilemap里面可辅助进行大物件的存放，使用TILE格子作为叶节点反向向上构建树，然后把大物体放在可完全包围该物体的节点里面，碰撞的时候先根据包围盒拿到TILE范围，逐步往根查找就可以。这种叫逆向4叉树，在有的地方会比较有用。

猴与花果山

Yuki001 发表于 2013-7-31 13:29
也是可以的，只不过不是用图片，而是用一张mask图，有可能比原来的图片小的多。这种方法在大致像素级别可 ...

的确是mask的，这是唯一标准的做法了，因为逻辑层和肉眼看到的渲染层必须是不同的世界。
逆向四叉树是一个思路，还有前面daofeng说到过的一个拆多个凸多边形（实际上现在流行拆成多个三角形），都是一种不错的思路，而且可以在关卡生成前先进行，但是核心问题是…………关卡每块都是随机的，这是个难点，所以最后不得不放弃这些需要预先就知道地图什么样的方式。随机其实是个很讨厌的问题，而且跑酷还要不断地新生成（因为看似相同的一些地形，每次产生时还会有些特殊的地方是随机决定是否出现的，比如一个凸字型的，下次出现可能就是口字形的或者凹字形的，这只是一个例子，因为不太容易找到有斜边的汉字举例），这样做原本其实是为了资源优化，但没想到成了恶化，当然其实也不能说是完全的恶化……