四叉树碰撞优化

编写思路

  1. 关于四叉树碰撞优化部分就是看了一些四叉树的帖子,很杂,具体看了哪些急不太清楚了,Youtube 上有一个博主 The Coding Train 有四叉树相关的教程,感兴趣可以去看一下。简单来说就是每一帧基于所有的碰撞对象建立一棵四叉树,然后在碰撞检测时我们不需要把每个对象与其它对象进行碰撞判定,我们可以从四叉树中查询某个区域的对象,然后在查询到的对象中进行碰撞判断。在该程序中,我只是查询了每个对象为中心的一个矩形范围,当然你可以写自己的 QuadTree.Query() 函数实现不同的查询策略。理论上来说它是 O( nlog(n) ) 的时间复杂度。我测试了一下,在我的 i7 7700Hq CPU 上,2000 个对象可以跑到 30 帧左右吧(Release 模式下),使用 VS 分析工具可以看到大部分时间都花在了 easyx 图形绘制上,如下图所示。我们每帧都需要建立一颗四叉树,按讲这里应该使用对象池的,但是本来编写时候就想着写着玩,试一试,就没使用对象池。但是我经过自己测试,程序从早上 9:40 左右开始跑,一直到晚上 8 点结束,内存占用在我电脑上始终是 5MB 上下,没有发生内存问题。也许有 BUG 没有表现出来,如果你电脑上运行遇到什么 BUG,欢迎跟我讨论。
  2. 关于 GUI 的部分,我只是基于观察者模式去尝试处理一下鼠标键盘消息,有些类的名字我自己随心取得,可能不是那么规范,其中一些适合单例模式的地方我也使用了单例模式;建议有一定的面向对像基础的小伙伴来参考吧,我自己也是在学习中,所以有很多写的不是很好的地方。由于我也经常使用 EasyX 去写一些小程序,所以这次想花点时间认真将 GUI 边思考边做吧,设计模式看了又看,不写代码始终不会理解其中的奥秘的,也当作自己学习过程中的实践了吧。

运行环境

  1. VS2019, EasyX_20211109, C++11, Windows 操作系统

关于作者

  1. QQ:1226598193 孙小鱼

运行截图

主界面

显示检测区域以及四叉树的构建

源码

源码地址:https://gitee.com/sunxiaoyu1999/quadtree.git

编译后的 exe 地址:https://gitee.com/sunxiaoyu1999/quadtree/attach_files/929733/download/QuadTree.exe

添加评论