四叉树碰撞优化

2021-12-24 ~ 2022-1-13 wuli丁小敏 (0)

编写思路

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