使用四叉树优化碰撞检测

四叉树是干什么的?

百度百科
四元树又称四叉树是一种树状数据结构,在每一个节点上会有四个子区块。四元树常应用于二维空间数据的剖析与分类。 它将数据区分成为四个象限。数据局限可以是方形或矩形或其他随便形状。
从界说我们可以看出重点信息:

  1. 树状结构
  2. 四个区块
  3. 分类
  4. 矩形

图示解说

解说之前需要先说明一下四叉树是用来做什么的,明了了原理才好明白它的行为。
使用四叉树就是使用分类的方式,削减碰撞节点的个数,只取出与给定碰撞体相同区域或者压在碰撞体所在区域边上的工具。

  1. 将游戏屏幕分为四个区域。
    使用四叉树优化碰撞检测
  2. 插入工具
    使用四叉树优化碰撞检测
  3. 插入的工具跨越了我们设置的阈值时,划分
    使用四叉树优化碰撞检测
  4. 插入的工具再次跨越了我们设置的阈值时,继续分。
    使用四叉树优化碰撞检测

剖析

插入

从上面的图示我们可以很好明白四叉树的原理。涉及的都是插入操作。
那么插入操作详细都做了什么呢?
使用四叉树优化碰撞检测
使用四叉树优化碰撞检测
从代码中我们可以看出:

  1. 当插入第一个工具的时刻只走了2;这个时刻没有子树,以是不会走1,由于objects(治理的工具)的长度还没有跨越我们设置的阈值MAX_OBJECTS,以是也不会走3。
  2. 一直插入,当objects中的数目,跨越了我们设置的阈值MAX_OBJECT,就会最先划分,发生子树,有了nodes,划分之后将自己治理的节点插入到子树中。再此之前,都不会走1,由于还没有发生子树。
  3. 划分之后再次插入新工具,若是工具可以获得对应的象限,就会走1 不会走2和3,若是没有获得对应的象限才会走2,3(没有获得的情形可能是你建立的工具在屏幕外,游戏中许多情形是敌人从屏幕外走进屏幕的,详细可参考我做的《星际迷航》或者《星际战》游戏)。

更新工具

使用四叉树优化碰撞检测
我是把四插入作为了工具治理器使用,要不然工具也需要更新,以是有了这一步操作。若是不这样你需要自己建立工具治理器,一个一个放进去,删除。通过四叉树直接治理省了不少事情。

更新象限信息。

这是一个递归操作,更新象限做的事情对照多了。

  1. 检查工具是否存活,若是殒命就接纳,我这里使用了工具池,以是工具实现了poolAble接口。
    使用四叉树优化碰撞检测

  2. 判断工具的所占区域是否在四叉树的区域内
    这里需要说明的是一个四叉树自己的区域是它治理的四个象限这么大。也就是一个四叉树治理四个象限
    使用四叉树优化碰撞检测
    使用四叉树优化碰撞检测
    不在治理区域的话需要判断当前this是否为根节点,若是是说明工具已经出屏了。(这个时刻可以通过工具实现的isVisible接口来控制是否接纳,由于不是所有在屏幕外的都要接纳,比如要进入屏幕的敌人,是不可能接纳的,以是需要自己用isVisible接口来控制)。若是不是就将工具放入根节点,重新划分。

    利用Azure Functions和k8s构建Serverless计算平台

  3. 在治理区域内,就看看在四叉树治理的哪个象限里。更新象限信息。
    使用四叉树优化碰撞检测
    若是没有转变什么都不外,若是有转变,先判断象限是否为-1,为什么会泛起-1,也就是不在四个象限的任何一个象限?由于压线了。此番操作后的效果如下图。
    使用四叉树优化碰撞检测

凭据给定矩形获取工具列表

使用四叉树优化碰撞检测

  1. 第一个是步长,用于获取深度,固然深度越长,处置的时间越长,获取的工具也精致。这个可以凭据自己游戏的同屏四叉树层级而定了。
  2. 若是通过obj的rect获得工具所在象限若是获得了对应的象限,用获得的象限的四叉树再获取。若是压线的话就需要将碰撞的两个象限的内容都取出来。
  3. 返回四叉树中没有支解象限的工具。

怎么用呢?

使用四叉树优化碰撞检测
自然就是把要碰撞的工具传给retrieve函数获得需要碰撞的工具列表举行碰撞检测了。
也就是文章靠头说的:
使用四叉树就目的是为了削减碰撞节点的个数。使用的是分类的方式。
至于用什么样的碰撞检测函数,不是四叉树体贴的事情,
使用四叉树优化碰撞检测
至于用几个四叉树治理工具,也不是四叉树体贴的事情。
使用四叉树优化碰撞检测

结语

想要demo的同砚可以去我的微店或者官方creator商城购置《跨引擎游戏框架》源码,跟demo是一个项目。买过的同砚请加我密友,群已经建好,有更新我会群里直接发包。

源码购置入口:
使用四叉树优化碰撞检测
demo展示:
使用四叉树优化碰撞检测

项目截图:
使用四叉树优化碰撞检测
框架的相关模块教程可以到《我的专辑》游戏开发进阶教程中获取。
后续还会推出更多与框架有关的教程:如:战斗框架,教学框架等等。并附带完整的游戏实现(航行射击游戏为例,学会做航行射击游戏不是目的,目的是通过这一款游戏,你可以获得做其他所有类型的游戏的思绪)。希望可以在不饿死自己的前提下辅助更过的朋友们快速找到开发思绪。

长按下方二维码,关注《微笑游戏》民众号,获取更多精彩内容。
使用四叉树优化碰撞检测

迎接扫码关注民众号《微笑游戏》,浏览更多内容。

原创文章,作者:admin,如若转载,请注明出处:https://www.2lxm.com/archives/16989.html