`

游戏中的碰撞检测

 
阅读更多

 

 

游戏中的碰撞检测方式有很多,不同的算法之间主要是在精度和速度之间权衡。以下几种方式按照速度排序说明。以2D为例,3D不过是增加了一维罢了,算法理解上没太大区别。


一、地图格子划分检测


最简单的一种检测,就是把地图(或者称为场景,总之是指碰撞发生的范围)划成一个个格子,类似仙剑奇侠传这样。假设地图有800*600px,20*20个像素为一格。那么可以划为40*30个格子。地图中参与检测的对象都存储着自身所在的格子坐标,判断碰撞就显而易见了,例如可以认为两个物体在相邻格判为碰撞,或者两个物体在同一格。采用这种方式有个要求,就是地图中所有可能参与碰撞的物体都要是20*20像素左右大小或者是其整数倍,例如房子占了3*3个格子,诸如此类。如果不遵守这个规则,有的物体只占了格子的一半,那么在玩家眼里这种检测就显得非常的粗糙。这种检测就像是把地图的像素点放大几十倍一样,与逐像素检测相比,效率提高了几十倍甚至上百倍。这种方式可运用于对检测要求不严格的游戏,例如踩地雷的RPG、推箱子之类的智力游戏。


二、矩形检测


当地图中的物体不能严格按照某个块大小的整数倍来绘制时,那么就需要另想其他的方法。这种方法适用于地图中的物体近似为矩形或者虽然不是矩形,但是碰撞精度要求不高的情况下。每个物体记录一个能够将自己框住的最小矩形的左上角坐标和矩形长宽。碰撞退化为判断矩形与矩形之间是否重叠,而这仅需要4次比较即可得出,速度很快。但为了判断整个场景中的物体,必须取第一个物体,迭代其他所有物体进行判断,再取第二个物体,迭代除第一第二个物体外的所有物体进行判断,以此类推。总计要进行(n-1)!次矩形判断才能准确得出场景中所有的碰撞可能。


三、圆形检测


与上一种方法类似,区别在于用一个能够包含物体的最小圆代替了矩形。主要是考虑到游戏中的物体外形以平滑为主,例如人物角色。而判断两个圆是否碰撞的计算也很简单,就是判断两个圆心之间的距离是否小于两个圆的半径之和。虽然球形检测在某些情况下提高了精度,但却损失了速度,因为点距离的计算需要用到平方和开方。具体相比慢多少我就不太清楚了。另外,为了计算整个地图的所有碰撞可能,也要进行(n-1)!次比较。


四、像素检测


精确到像素级,已经不能比这更精确了,相对的,效率也是最低的。怎样判断两个物体是否碰撞呢?在过去png格式图片还不盛行的时候,游戏中用到的图片中的透明部分是指定用某种颜色来表示的,例如洋红色。就像电影中的绿幕蓝幕,通过处理把这些颜色的像素点当做透明点处理,而为了判断检测,需要准备一张原图像的黑白图,黑色区域表示透明,这张图片中的每个像素值为0或者1,判断检测的时候取两张图片的黑白图,进行与运算,结果为1(有白点重叠),则判为碰撞。但是现在有了PNG和XNA,逐像素检测就相对简单一些。首先仍然需要有一个矩形框包围物体,通过矩形检测得到重叠的矩形区域可以大大减少检测的像素点数量。然后在这个区域内,取两个图片的点逐行逐列迭代,如果遇到某个点两张图片均有颜色存在,即判为碰撞。同理,进行(n-1)!次比较后得到全地图的碰撞可能。


五、四叉树检测


准确的说这事在第三四五种方法的基础上的优化策略,或者说是第一种方法同后三种方法的组合应用。主要是针对那最后的(n-1)!次比较。方法是,像第一种方法一样将地图分为格子,格子的大小应该能够容纳10个左右的地图中最大物体,例如一个800*600的地图可能就划为9个区。同样的,每个物体要记录自己所在的区坐标以及矩形包围盒。如果该物体完全位于该区内,则只要将其与该区内的其他物体判断碰撞。如果该物体虽然位于某个区,但是小部分位于隔壁区,则额外的需要迭代隔壁区的物体,这点效率损失是可以容忍的,相比于迭代全地图的物体。


有个问题,我怎么知道哪些物体是跟该物体位于同一个区呢?那不是还是要迭代一遍所有物体?这时候就是题目发挥的地方的,之所以称为四叉树检测(当然,这名字是我自己取的),就是因为那些区块是以四叉树的方式链接的,即得到一个区块的对象,就可以直接得到其上下左右相邻的区块的对象,而物体可以是存储在所在区的一个列表中。这样就不用遍历所有物体也可以直接取出隔壁区的物体了。当地图很大的时候,四叉树的优势体现得很好。


六、3D中的碰撞检测


以上是我所掌握碰撞方法,可能还有更多吧。那么3D中的检测其实是2D的延伸,例如矩形检测变为立方体检测,圆形检测引申为球形检测,四叉树检测进化为八叉树检测。


当然了,凡是有例外。逐像素检测方法在3D中没有相对应的方法,因为3D中的物体的表示最小单元是三角型而非点。其实也可以说逐三角片检测是逐像素检测的3D版,但毕竟是平面碰撞的检测,需要一定的计算公式,而不是与或一下就OK的。这里就不赘述了。


总结


我的表达能力不是很OK,另外手打得也有些酸。


选择哪种方法,要根据你的游戏需要,例如推箱子游戏,显然只要格子碰撞检测就足够了。而一些以球作为主要物体的游戏例如射击游戏则可以考虑圆形碰撞。


同样的,在有些碰撞精度要求很高的游戏中,还要对这些方法进行一定的变化,例如格斗游戏,作为判断的单元不是整个人而是四肢、身体等部位,需要更多的包围盒来表示一个物体。


原文地址:http://darkey2s.blog.163.com/blog/static/739930262010115105333989/

分享到:
评论

相关推荐

    游戏中碰撞检测最详细

    1. 碰撞检测基础:涵盖了空间分割技术、边界体积层次结构、四叉树、八叉树和k-d树等,这些是实时碰撞检测中常用的数据结构。 2. 几何形状处理:详细解释了点、线、多边形、球体、凸包、包围盒、多面体等基本几何体...

    3D游戏中碰撞检测的应用

    ### 3D游戏中碰撞检测的应用 #### 引言 碰撞检测是计算机图形学、虚拟现实、计算机辅助设计与制造等多个领域的重要技术之一。随着计算机技术的进步和个人电脑的普及,游戏产业迅速发展,游戏成为了许多人休闲娱乐...

    OPENGL游戏中碰撞检测

    OpenGL 游戏开发中的碰撞检测是一项至关重要的技术,它确保了游戏对象间的交互真实可信,为玩家提供沉浸式的游戏体验。碰撞检测不仅涉及到物体是否相交,还涉及到如何精确、高效地判断碰撞以及如何响应碰撞事件。...

    cocos2d-x游戏碰撞检测(中文翻译)毕设也肯定用的上

    提供的文档《cocos2d-x游戏碰撞检测(中文翻译)_doc.doc》和《cocos2d-x游戏碰撞检测(中文翻译)_pdf.pdf》应包含了详细的步骤和示例,可以帮助读者深入理解cocos2d-x中的碰撞检测机制。而《cocos2d-x collision ...

    Java打砖块游戏,碰撞检测

    在这个场景中,我们关注的核心是"碰撞检测",这是游戏开发中的一个重要环节,尤其是对于像打砖块这样需要实时反应的游戏。下面我们将深入探讨Java打砖块游戏中球与矩形(通常是游戏中的砖块)的碰撞检测及其相关知识...

    碰撞检测 有关C++

    碰撞检测在计算机图形学、游戏开发、物理模拟等领域中扮演着至关重要的角色。C++作为一门强大且广泛应用的编程语言,被广泛用于实现各种复杂的碰撞检测算法。本篇将深入探讨C++中的碰撞检测技术,旨在帮助开发者更好...

    《MFC游戏开发》笔记十 碰撞检测 配套源代码

    在游戏开发中,碰撞检测是不可或缺的一个重要环节,特别是在使用MFC(Microsoft Foundation Classes)进行Windows应用程序开发时。本篇笔记主要围绕《MFC游戏开发》中的第十章内容,深入探讨了如何在C++环境下实现...

    2D游戏碰撞检测

    2D游戏碰撞检测是一项基础的计算机图形学技术,主要用于游戏中物体之间是否发生了接触或相交的判断。在游戏开发中,碰撞检测用于确定物体是否相撞,以实现诸如判断子弹击中目标、敌人的视线覆盖、赛车碰撞、鼠标悬停...

    3D游戏碰撞检测解决方案

    早期的3D游戏碰撞检测方法主要分为基于格子和BSP树两种。格子系统虽然实现简单,但其精度较低,难以应对复杂的3D环境。BSP树则提供了一种更为精确的方法,但由于预处理时间长和资源消耗大,它逐渐不再适用于现代游戏...

    OSG中碰撞检测程序

    OSG中碰撞检测程序 OSG(OpenSceneGraph)是一...3. 电影特效:OSG中的碰撞检测程序可以用于电影特效、游戏开发等领域。 OSG中的碰撞检测程序是一个功能强大且广泛应用的技术,能够满足各种复杂的三维图形处理需求。

    AABB包围盒碰撞检测算法1

    在游戏开发中,碰撞检测是至关重要的,尤其是在3D场景中。AABB(Axis-Aligned Bounding Box,轴对齐包围盒)是一种常用的简单碰撞检测方法,尤其适用于Unity 3D和Cocos2d-x等游戏引擎。AABB通过创建一个与坐标轴平行...

    基于QT的C++的碰撞检测

    在IT领域,尤其是在游戏开发、物理模拟或者图形用户界面(GUI)设计中,碰撞检测是一项重要的技术。本项目聚焦于使用C++编程语言,并结合QT框架实现碰撞检测功能。QT是一个跨平台的开发框架,广泛应用于桌面应用和...

    碰撞检测:实时碰撞检测+bullet3碰撞检测库

    本资源用于碰撞检测: 1.bullet3库:用于检测碰撞及最小距离,常用在游戏建模、机器人等应用中 2.Real-Time Collision Detection,一个包含实时碰撞检测算法原理+代码的文档 3.CVPR2022:将bullet用于深度学习中的...

    flash碰撞检测小游戏

    用flash制作的一款碰撞检测的小游戏,玩家需要控制目标物不被四处移动的物体碰到

    xna中的碰撞检测

    在XNA这个强大的游戏开发框架中,碰撞检测是游戏编程中的关键部分,它涉及到游戏对象间的交互,确保了游戏逻辑的正确性。本资源重点讲解如何在2D环境中实现碰撞检测,这对于创建像《超级玛丽》这样的平台跳跃游戏...

    Tiled Map中使用碰撞检测

    本篇文章将深入探讨如何在基于Tiled Map的游戏中实现碰撞检测,特别是使用cocos2d框架。cocos2d是一个强大的开源游戏引擎,广泛应用于iOS和Android平台,对于iPhone游戏开发尤其适用。 首先,我们需要理解Tiled Map...

    《实时碰撞检测算法技术》

    包围体技术是碰撞检测中的核心概念,包括轴对齐包围盒、球体、方向包围盒等类型。这些包围体能够简化物体的表示,加快碰撞检测的速度。作者详细讲解了各种包围体的特点及其适用场景,以及如何选择合适的包围体来优化...

    GameMaker Studio开发:生存游戏碰撞检测与物理效果-(10).生存游戏中的物理挑战设计.docxGameMaker Studio开发:生存游戏碰撞检测与物理效果-(11).实战案例:生

    GameMaker Studio开发:生存游戏碰撞检测与物理效果_(10).生存游戏中的物理挑战设计.docx GameMaker Studio开发:生存游戏碰撞检测与物理效果_(11).实战案例:生存游戏碰撞与物理系统开发.docx GameMaker Studio...

Global site tag (gtag.js) - Google Analytics