返回

碰撞检测优化-四叉树

发布时间:2022-02-22 14:26:38 2213
# 前端

首先说明下四叉树并不是一个碰撞引擎,它只是一种减少碰撞候选者的算法,所以在利用四叉树得到碰撞候选元素后,还需要去检测这些候选元素与目标元素是否发生碰撞

2D中是四叉树,3D中则对应的为八叉树

项目(微信小游戏《宇宙少女》)中实测:

同屏极限情况下,可碰撞元素为:

200左右子弹+70左右怪物+若干buff+玩家

碰撞关系为:

子弹和怪物碰撞

特定怪物和其他怪物碰撞反弹

玩家和怪物碰撞

玩家和buff碰撞

使用cocos的碰撞系统,在H5表现良好,微信小游戏的Android平台也还可以,但是在ios平台上,FPS只有20+
使用四叉树做空间规划,对子弹做进一步的优化,减少碰撞元素

碰撞检测使用圆圆碰撞和圆矩碰撞,放弃了pow()和sqrt()方法, 其相对于加减乘除会消耗更多的CPU(之前在QQ群讨论过)

改良后的碰撞检测在微信小游戏的Android平台性能良好,IOS平台的FPS也达到了50+

项目中使用每帧重建四叉树,当然也可以自己维护四叉树中碰撞元素的位置

1四叉树概念

四叉树(quad-tree)是一种数据结构,是一种每个节点最多有四个子树的数据结构。四叉树是在二维图片中定位像素的唯一适合的算法。因为二维空间(图经常被描述的方式)中,平面像素可以重复的被分为四部分,树的深度由图片、计算机内存和图形的复杂度决定。四叉树可以用来在数据库中放置和定位文件(称作记录或键)。这一算法通过不停的把要查找的记录分成4部分来进行匹配查找直到仅剩下一条记录为止。

2空间规划

游戏编程模式-空间分区

将对象存储在根据位置组织的数据结构中来高效地定位它们。 你有一组对象(可能还挺多),将对象存储在一个根据对象位置来组织的数据结构中,该数据结构可以让你高效查询位于或靠近某处的对象。当对象位置改变时,更新并继续维护该空间数据对象。用更复杂的数据结构(空间)来换取大量查询时的性能优化(时间)。

博客园中一篇讲解详细的blog

https://www.cnblogs.com/xin-lover/p/12216053.html 280

3
quadtree-js

在GitHub上找到的一个前辈实现的四叉树:

https://github.com/timohausmann/quadtree-js 216

并提供了两个在线演示的demo,其中红色为四叉树节点,空白方块为四叉树中的元素,灰色方块为鼠标的位置,即目标元素,绿色方块为碰撞候选元素

特别声明:以上内容(图片及文字)均为互联网收集或者用户上传发布,本站仅提供信息存储服务!如有侵权或有涉及法律问题请联系我们。
举报
评论区(1)
按点赞数排序
用户头像
精选文章
thumb 中国研究员首次曝光美国国安局顶级后门—“方程式组织”
thumb 俄乌线上战争,网络攻击弥漫着数字硝烟
thumb 从网络安全角度了解俄罗斯入侵乌克兰的相关事件时间线