MFC游戏开发笔记十 游戏中的碰撞检测进阶：地图类型&障碍物判定 - VC.NET教程 - 编程入门网
MFC游戏开发笔记十 游戏中的碰撞检测进阶：地图类型&障碍物判定
在这个教程中主要内容是2D游戏，关于3D游戏，雾央也还在努力学习之中，等以后有时间，一定会把自己学到的知识分享给大家，所以这一节中主要讲解的就是2D游戏中的障碍物判定了，45度地图以后要有时间雾央会讲。
上一节中讲解了近似的矩形判定，这是一种比较常用的判定方式，很适合于两个移动的物体之间，比如很多跳跃类游戏中移动的台阶和人物之间的碰撞，但是在地图障碍物判定上就显得有些力不从心了。这一节雾央将会给大家讲解几种新的碰撞检测方法，对于新手朋友们可能内容略多，不过只要认真阅读，多思考思考，应该是不难理解的，如果有什么问题，欢迎大家留言讨论。
在玩游戏的时候，有些河流断崖等地方是不能通过的，高处跳跃落下的时候是不会穿过地平线的，石头挡着的地方是绝对不能路过的&&&&这些检测都属于地图障碍物判定的范围。
大家在开发游戏的时候，地图的结构类型不同，采用的障碍物判定一般也就不同，地图类型和障碍物检测联系密切，因此雾央会介绍一下不同地图类型可以采取的方法。
在介绍之前，雾央必须要说明一个前提：在雾央的教程里，做碰撞检测时，人物都是使用最小外接矩形进行的。大家当然可以逐像素进行，即遍历整个人物矩形，当检测到人物图形和背景图片在同一位置都具有像素且是障碍物的时候，即发生碰撞。这样去掉了人物图片透明处带来的误差，但是太过于低效，雾央觉得大家初学游戏没有必要追求这么高的精确度，同时也可以大大简化问题。
一、TileMap
现在在家的同学请回头看一下背后，嗯，什么诡异的事情都没有发生，呵呵，开个玩笑了。我们要看的其实是地面，大家看到的是不是像下面这样？
这个地面是雾央在网上找的一张图，大家想象一下，如果将其中的某些块瓷砖画上石头，画上树木、房屋等，在把瓷砖之间的分界线给隐藏起来，比如下面这样，那么它像什么？
应该说它就是一张2D游戏中的地图！
更多精彩内容：/Programming/VC_NET/弹幕游戏的碰撞检测一般是怎么实现的？
在存在大量活动物体，且对象数量非常大的弹幕游戏中，碰撞检测一般用什么方式实现？从早期游戏（如街机）到现代弹幕游戏，实现有没有什么进化？最好有已经存在的游戏做实例。补充：受“用像素碰撞才能真正重现街机的打机感”这条匿名回答的启发，老的街机游戏是不是可以在渲染的时候顺便就把碰撞检测做了？记得JavaME的API都是支持像素级检测的。
在碰撞检测的粗略阶段（broad phase）可以使用空间划分（space partitioning）[1]，把子弹动态地放置于区域里，例如二维的时间最简单是把屏幕空间划分成网格（grid），把每个子弹放至于方格之内。假设k是方格的数量，最好的时间复杂度得以提升至O(n/k)，但最坏仍然是O(n)，因为所有子弹可能集中在一起。常用的动态空间划分方式还有四叉树／八叉树（quadtree/octree）、哈希空间（hash space）等。上述的是说多个子弹与一个物体的碰接，而子弹与子弹之间是不会碰撞的。更通用的要检查每个物体与其他每个物体是否碰撞，即最坏情况是O(n^2)的。传统上可使用各种空间划分方法，及／或扫掠裁减（sweep and prune）算法[2][3]。由于sweep-and-prune的做法最早见于1992年，所以之前的游戏应该不会使用，更多的是用最简单的网格空间划分。关于这个问题也可参考[4]，它把space partition当作一个游戏编程模式。[1] Gregory著，叶劲峰译，《游戏引擎架构》，p. 562，电子工业出版社，2014。[2] Bara, David. "Dynamic simulation of non-penetrating rigid bodies." Computer Graphics (SIGGRAPH'92) (1992): 303-308.[3] Cohen, Jonathan D., et al. "I-COLLIDE: An interactive and exact collision detection system for large-scale environments." Proceedings of the 1995 symposium on Interactive 3D graphics. ACM, 1995.[4] Nystrom, Robert. Game programming patterns. Genever Benning, 2014.
上个月正好在公司花两天做了个弹幕游戏的demo。弹幕碰撞主要是将敌人和自己的子弹区分开，分别存入两个网格对象中。网格对象持有一个二维数组（当然一维数组也可以），数组的长度为（屏幕长度/单个网格的长度 * 屏幕高度/单个网格的高度）。效果如下图：数组用于存放处在该网格中的所有子弹。假设屏幕为480*800，我们选定网格为80*80，则共有480/80*800/80=60个网格，我们指定有斜线的网格对应数组[0][0]。接下来根据子弹的位置将其加入到数组中。公式如下：
row = math.floor(子弹Y轴位置/网格高度）
col = math.floor(子弹X轴位置/网格长度）比如子弹位置为（100，200），则将其加入到数组中的[1][2]中，在子弹位置发生改变同时更新其在数组中的位置。需要与网格对象中的子弹进行检测的飞机以同样的方法计算出（col，row），则只需与数组[col][row]中的子弹进行碰撞检测即可。
不知道有没有说清楚……
个人觉得：以前的街机游戏显然没有做碰撞测试也不需要做碰撞测试。它所做的只是一个调色盘中的像素色彩对比而已。
自己找到了几个有意思的东西，有空可以尝试用这个工具研究下弹幕游戏也许。
其实弹幕游戏没那么麻烦，一个一个比就好了。敌人的子弹只要和player算一次，而player发出的子弹一点都不多，和每个敌人算也没关系......然后一般碰撞用矩形或者圆作为hitbox即可......
好像还没怎么特别在意过这个问题，现代游戏引擎做这种普遍压力不大我是用unity，可以从unity这个角度聊聊，其他引擎就没那么清楚Unity是二维三维都支持的游戏引擎三维的话基本使用三维碰撞体（很多射击游戏会用raycast做射线判断，那种情况一般忽略子弹的速度，弹幕应该不适合）所以一般就是普通的collider,三维物体的碰撞，那比较重要的应该是子弹之间无碰撞，而仅仅与目标物体如敌人或主角，（因为如果大量子弹相互碰撞的话，很多会在短时间出现复数级别的碰撞，虽然引擎也不是不能承受，但是总会有些意外情况）所以一般会把子弹和敌人自己分层分开，设定层之间的碰撞，这样或者自身子弹可以击毁敌人的子弹之类的判定也就可以做。unity创建大量物体的瞬间，是有可能卡断的，另外还有就是子弹不会永远存在，要有出屏幕的销毁机制，unity下面会做pool,也就是一个子弹设定它的最多出现的上限，那开机的时候就创建了这么多子弹出来，只不过都隐藏起来，如果被创建就显示一个子弹到相应的位置，这样不会导致游戏的性能下降。如果是用2d的算法，会更快一些，但是思路也大抵是一样，那如果要做什么子弹弹回的立场，时间压缩等等的特效也都很简单，。补充，另外还有一种情况，比如说射线类武器，那就是穿过所有的物体，这种情况，可以考虑用raycast。
大大已经高屋建瓴得说明该问题属于空间划分，已有N多NB论文等着你。 童鞋给出的实现方案已经很细节了，我之前的项目也采用了类似方案。说说我自己的实现细节吧。曾经也开发过一款2D横版弹幕端游。一般弹幕游戏的子弹都会有矩形碰撞框让策划配置（不会只是一个质点），以实现不同大小或多种组合的物体。比如这种常规的还有这种长条的还有这种长条的所以可以把问题抽象成如何在网格数组中快速判定矩形相交，当然我们前提是矩形数量众多，否则O(N^2)枚举就行，就不用上网格了。按矩形大小塞入不同网格，如橙色的矩形塞入[0][0],[0][1],[1][0],[1][1] 4个网格中对每个矩形，遍历其所覆盖的网格，将每个格子的矩形放进set中进行去重从set中去掉本体矩形，对set中剩下的所有矩形进行碰撞检测个人经验以供参考：网格处理方式简单，效率一般情况下比四叉树好网格大小很重要，过小的话大矩形会被分割的过细，过大的话单个网格内有太多待判定矩形先保存，后面再补~
弹幕游戏永远是新手学习游戏开发第一个做的游戏里最合适的一种，所用的碰撞也是最简单的。基本上用矩形检测可以解决全部碰撞测试。子弹的碰撞体一个矩形解决问题，机体和复杂一些的形状用组合矩形解决问题。矩形万岁。
东方project似乎是用圆做hitbox。因为椭圆弹、箭弹、符札都是圆形判定。
用像素碰撞才能真正重现街机的打机感
已有帐号？
无法登录？
社交帐号登录请使用支持脚本的浏览器！
你试图访问的日志地址不存在,请检查你输入的地址是否正确。
网易公司版权所有&&&在存在大量活动物体，且对象数量非常大的弹幕游戏中，碰撞检测一般用什么方式实现？从早期游戏（如街机）到现代弹幕游戏，实现有没有什么进化？最好有已经存在的游戏做实例。补充：受“用像素碰撞才能真正重现街机的打机感”这条匿名回答的启发，老的街机游戏是不是可以在渲染的时候顺便就把碰撞检测做了？记得JavaME的API都是支持像素级检测的。
上个月正好在公司花两天做了个弹幕游戏的demo。弹幕碰撞主要是将敌人和自己的子弹区分开，分别存入两个网格对象中。网格对象持有一个二维数组（当然一维数组也可以），数组的长度为（屏幕长度/单个网格的长度 * 屏幕高度/单个网格的高度）。效果如下图：数组用于存放处在该网格中的所有子弹。假设屏幕为480*800，我们选定网格为80*80，则共有480/80*800/80=60个网格，我们指定有斜线的网格对应数组[0][0]。接下来根据子弹的位置将其加入到数组中。公式如下：
row = math.floor(子弹Y轴位置/网格高度）
col = math.floor(子弹X轴位置/网格长度）比如子弹位置为（100，200），则将其加入到数组中的[1][2]中，在子弹位置发生改变同时更新其在数组中的位置。需要与网格对象中的子弹进行检测的飞机以同样的方法计算出（col，row），则只需与数组[col][row]中的子弹进行碰撞检测即可。
不知道有没有说清楚……
在碰撞检测的粗略阶段（broad phase）可以使用空间划分（space partitioning）[1]，把子弹动态地放置于区域里，例如二维的时间最简单是把屏幕空间划分成网格（grid），把每个子弹放至于方格之内。假设k是方格的数量，最好的时间复杂度得以提升至O(n/k)，但最坏仍然是O(n)，因为所有子弹可能集中在一起。常用的动态空间划分方式还有四叉树／八叉树（quadtree/octree）、哈希空间（hash space）等。&br&&br&上述的是说多个子弹与一个物体的碰接，而子弹与子弹之间是不会碰撞的。更通用的要检查每个物体与其他每个物体是否碰撞，即最坏情况是O(n^2)的。传统上可使用各种空间划分方法，及／或扫掠裁减（sweep and prune）算法[2][3]。&br&&br&由于sweep-and-prune的做法最早见于1992年，所以之前的游戏应该不会使用，更多的是用最简单的网格空间划分。关于这个问题也可参考[4]，它把space partition当作一个游戏编程模式。&br&&br&[1] Gregory著，叶劲峰译，《游戏引擎架构》，p. 562，电子工业出版社，2014。&br&[2] Bara, David. &Dynamic simulation of non-penetrating rigid bodies.& &i&Computer Graphics (SIGGRAPH'92)&/i& (1992): 303-308.&br&[3] Cohen, Jonathan D., et al. &I-COLLIDE: An interactive and exact collision detection system for large-scale environments.& &i&Proceedings of the 1995 symposium on Interactive 3D graphics&/i&. ACM, 1995.&br&[4] Nystrom, Robert. &i&Game programming patterns&/i&. Genever Benning, 2014. &a href=&///?target=http%3A///spatial-partition.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Spatial Partition ? Optimization Patterns ? Game Programming Patterns&i class=&icon-external&&&/i&&/a& 中译版：&a href=&///?target=https%3A///GameDevelopmentCollege/Game-Programming-Patterns-CN/blob/master/06.4-Spatial%2520Partition.md& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Game-Programming-Patterns-CN/06.4-Spatial Partition.md at master ? GameDevelopmentCollege/Game-Programming-Patterns-CN ? GitHub&i class=&icon-external&&&/i&&/a&
在碰撞检测的粗略阶段（broad phase）可以使用空间划分（space partitioning）[1]，把子弹动态地放置于区域里，例如二维的时间最简单是把屏幕空间划分成网格（grid），把每个子弹放至于方格之内。假设k是方格的数量，最好的时间复杂度得以提升至O(n/k)，但…
个人觉得：&br&以前的街机游戏显然没有做碰撞测试也不需要做碰撞测试。它所做的只是一个调色盘中的像素色彩对比而已。
个人觉得： 以前的街机游戏显然没有做碰撞测试也不需要做碰撞测试。它所做的只是一个调色盘中的像素色彩对比而已。
已有帐号？
无法登录？
社交帐号登录
here comes a new challenger