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

猴与花果山

最可恨的是，还怪不到底层程序问题，我们老大优化了送显卡的算法，的确，上万个entity，带Sprite的这种，都能有稳定60的FPS，所以现在被肯定是我的算法出了问题了，真心坑啊，虽然我认为比当时做百战天虫的算法已经优化了很多了。

daofeng

猴与花果山 发表于 2013-7-23 00:15
另外关卡内确实没有三角形碰三角形的问题，所以忽略了你这个问题，不过从数学的角度上来说我还是得承认这 ...

我只是举了个三角形的例子，甭管几边形，都有例外情况。四边形，两个长条组成的一个十字架，就是例外。算法是严谨的，程序是要对bug负责的，你不能因为你碰巧碰到的问题没有特殊情况，就认为你的算法是正确的。出了问题谁来查谁来改？

我给你点料好了
计算一个点是否在多边形内部，有两种不用管凹凸多边形的方法。你说的射线法和有向角。射线法就你这个意思，只是计算射线和线段的端点错了。方法就是判断两条直线的交点（都不用解方程，因为有条线是 y=n，带入计算就得到x），然后看看点是否在线段和射线上。这个方法就是各种边界情况要考虑，诸如点和边重合，点和多边形端点重合啥的。

有向角就简单了，具体算要用到向量叉积之类的。最后的结果就是0 多边形外
2*pi 多边形内
pi 多边形的一条边上
其他值  多边形的顶点（当然要保证没有退化的一个顶点，使得相邻的两条边呈180度）
完全不用考虑凹凸

这两个能不能避免除法，没细想，可能不太容易。

这些都是现成结论，算法导论上清清楚楚，有兴趣去看看好了。大学生有专门的算法竞赛，叫acm/icpc，这种都是最基本的题。别拿着知道一点皮毛的东西就出来。这玩意我估计也没啥人仔细看，错误根本就发现不了，等以后有个策划心血来潮看一下，悲剧了。

效率更是一个程序的活了，都是属于比较难的，留个程序搞吧。一个策划你纠结这些也没有，你可以去了解下，国外一些软件项目的外包类型叫2x2x2x，啥意思？就是 时间或者空间或者什么东西减半，最后能减少10%人就验收了。还是专职本身工作吧。

（真是个悲剧，每小时只能发两个贴，一起编辑在这里了）老大都是很能否决的，如果你有兴趣，可以深入了解啊

浮点数这个，你如果代码上都避免了浮点数，那基本都是错的。计算几何是需要最精确的浮点数运算的。先定义一个eps=1e-8，然后所有的 a<b都要改成 a<b-eps，所有的a <=b 都要改成a < b+eps，所有的相等都要改成 abs(a-b)<eps

算了，不说了，都在讨论一些程序的东西。数值策划还是专注于数值，数值和算法是两个东西。程序 = 算法 + 数据结构， 这玩意不是随便说说的。

猴与花果山

daofeng 发表于 2013-7-23 00:55
我只是举了个三角形的例子，甭管几边形，都有例外情况。四边形，两个长条组成的一个十字架，就是例外。算 ...

你的这个算法就是我现在用回的……除此之外有没更高效点的，网上还有另外个常用的算法（那个更多的是Coding的，不是数学的），看起来也不是很靠谱，主要还是循环过多了这个就不太好办了。换回之后这个比较特殊的多边形碰撞也被取消了，不再使用了，采用Flash自带的Intersects了，绝对准确且效率相对最高了……你说的射线法，就是我列的那个方法，倒真不用管你这里说的这些存在的问题，因为我只要知道射线与线段是否相交，在程序里可以清楚地获得每条线段，不会发生重合了就有N次判断的问题。

猴与花果山

daofeng 发表于 2013-7-23 00:55
我只是举了个三角形的例子，甭管几边形，都有例外情况。四边形，两个长条组成的一个十字架，就是例外。算 ...

这些算法我都查了，可是的确不好避免除法问题，算法到实现毕竟有巨大的鸿沟……所以说应用数学到游戏开发中，就已经不再是简简单单的书本知识了，这才是我要说的“数值策划”最重要的工作——如何将书本知识合理的运用到一个“未知”领域。其实这个算法，如果我优化不了，相信别人也很难优化了，优化的做法都是一样的，至少在这块上是这样的。
有人认真看了，我相信他一定会看回帖的，本来就是讨论，有错误是再所难免的……抓着编译等待（到真机上1次至少4分钟）的时间过来瞎聊几句，没工夫验算一些东西了，有时候就是激动想到了新方案了或者看到一些帖子内容的鼓动，会写些东西发表个看法和急于把研究内容共享下罢了。

猴与花果山

daofeng 发表于 2013-7-23 00:55
我只是举了个三角形的例子，甭管几边形，都有例外情况。四边形，两个长条组成的一个十字架，就是例外。算 ...

还好我没1小时2帖的限制啊。
Float的做法理论上是对的，但是现实是残酷的，Float和除法还是尽量避免的好，除非必须用到，虽然其实这俩也并不会对效率产生很大的影响（如果我不高要求自己的话）。不过程序，在我们这里的定义是：底层，包括和各种设备的接口的开发，包括渲染等问题的处理，逻辑层问题，全部策划解决。其实早个10年有人提出过——“5年内行业策划的标准是可以独立完成游戏项目”，可惜，现实就和房价一样残酷……不过这并不影响我去写代码，反正做了一辈子游戏，设计到Coding对我来说都很愉快。
这个属于瞎扯淡了，反正怎么做游戏都挺开心的，不过有个现象没错——行业内策划和程序之间缺乏的是类似我现在在做的工作的这种连接者，有时候策划不能理解我因为我会告诉他们残酷的现实是想法很难实现或者他们的语无伦次没人理解，有时候我知道策划要什么也知道怎么做但很难让程序明白，毕竟“翻译”不好做啊，这已经是个长久问题了，于是后来我就更坚定了自己动手的信念。

阿部か

你们说的好高级，完全看不懂。

kk3987986

留名顶贴。12楼比较厉害啊。
顺便发表下，LZ所说的策划一个人干项目很多年前的确是有的，不过现在都是团队了，分工明确配合好才是关键。
优化问题一直认为是程序的工作。
其实我没怎么弄明白LZ讨论的跑酷问题=。||

qowp332

这都是被人研究烂的东西，各种开源代码不要太多，取来拿来直接用就行

猴与花果山

qowp332 发表于 2013-7-25 09:57
这都是被人研究烂的东西，各种开源代码不要太多，取来拿来直接用就行

求指点，有什么好的可以直接用的代码，给个名字我自己搜索就好，不要物理的。横版游戏就做过波斯王子（很老的版本了）和百战天虫，所以思维限制在类似的横板游戏了，最好有高效些的跑酷的，毕竟地图无限生成麻烦很多。

qowp332

猴与花果山 发表于 2013-7-25 11:02
求指点，有什么好的可以直接用的代码，给个名字我自己搜索就好，不要物理的。横版游戏就做过波斯王子（很 ...

http://www.box2d.org
这个比较简单，只需要碰撞算法的话，只看Collision部分的代码就行了