分享四叉树空间划分算法，快速查询邻近物体

通过四叉树结构划分并存储二维空间内的大量物体，可以做到快速搜索邻近的物体，可以用于：场景中有大量交互物需要靠近时显示交互按钮、探测周围大量物体等逻辑。

四叉树原理和实现可以参考：
https://davidhsu666.com/archives/quadtree_in_2d/
https://thecodingtrain.com/challenges/98-quadtree

作者在此基础上实现了四叉树的动态更新，可以检测到附近的动态物体。
实现效果：脚底探测范围内的球会被放大

使用方法：首先构建场景的总体范围，并创建四叉树：

然后将所有场景中需要被检测的物体插入到四叉树中：


物体位置发生变化时，通过调用update方法更新四叉树：

最后查询时，先创建探测范围，再调用四叉树的查询方法得到附近的物体点位：

具体用法可见附件的代码，其中有详细注释。
detection.rar (294.58 KB, 下载次数: 59)

2023-11-28 11:28 上传

点击文件名下载附件
代码

这个和人身上挂个触发器哪个更快点呢

汽汽汽汽水 发表于 2023-11-29 09:35
这个和人身上挂个触发器哪个更快点呢

同问同问

汽汽汽汽水 发表于 2023-11-29 09:35
这个和人身上挂个触发器哪个更快点呢

试了下，触发器进入和退出时会稍微耗时点，影响也不大，主要是提供了一种不用触发器的实现方法。
触发器进入、退出时的：



四叉树判断的每个update都在2.3~2.7ms左右：