适用于Java中的Flocking Boids的2D空间数据结构

Question

我正在进行植绒boids仿真,只是为了好玩,我想稍微优化一下.需要工作的区域是在给定的boid附近找到boids.我认为要做到这一点,某种适合任务的空间数据结构将是我最好的选择(见这里并向下滚动一下.).

无论我采用什么,我都会用Java从头开始实现自己.这样我就可以学到更多关于我选择的数据结构的知识,而不是我刚才调用的一堆库函数.

我知道R-Trees,kd trees和Quadtrees.在我看来,它们都是可行的选择.但我对这些数据结构没有任何经验,我不完全确定最适合我的目的.我不需要这么大规模的任何东西- 我说的可能只有几百个,也许最多只有一千个,而不是一百万个,但请记住,我最终可能最终在Android手机上运行它.

请为此推荐一个数据结构(当然不限于上述内容),并给我一个很好的理由选择它.

是的,我已经看到了这个问题.不,我对答案不满意 - 根本没有任何理由.

哦,另外一件事 - 就像标题所说的那样,这仅仅是针对两个维度的.

Answer 1

九年太晚了，无法帮助Iskar Jarak，但我会插话，因为其他人可能会在搜索中找到这个老问题。

\n

关键点是，几乎任何事情都比查看每对群体的天真的 O( n \xc2\xb2) 方法更好。因此，正如 Iskar 所建议的，任何一种基于树的空间数据结构都是一个巨大的改进，基本上是 O( n log n )。也就是说：n 个boids 中的每一个都需要查找其邻居，每个邻居的时间复杂度为 O(log n )。

\n

需要注意的是，Desmond Vehar提到的\xe2\x80\x9chit检测\xe2\x80\x9d是一个稍微不同的问题，询问\xe2\x80\x9cis这个查询位置\xe2\x80\x98inside\xe2\x80\x99我的数据结构中的任何 \xe2\x80\x98objects\xe2\x80\x99 吗？\xe2\x80\x9d 在多智能体模拟中，我们希望找到多个邻居。有时 \xe2\x80\x9cn 最近的 N 个邻居\xe2\x80\x9d 或者可能 \xe2\x80\x9 在查询位置的给定半径内调用邻居。\xe2\x80\x9d 通常将一个 boid 描述为其中心就足够了点并按点之间的距离进行过滤，生成 \xe2\x80\x9cquery 球体。\xe2\x80\x9d

\n

在他的算法课程中，Tim Roughgarden不断询问 \xe2\x80\x9c 我们可以做得更好吗？\xe2\x80\x9d 确实\xe2\x80\x94，而 O(log n ) 比 O( n ) 更好地查找邻居\ xe2\x80\x94 最好的是常数时间查找，O(1)。这里哈希表（又名未排序的映射）是我们的朋友。

\n

多个邻居和散列这两个想法带来了一种加速多智能体模拟的好方法：空间散列到体素（/boxes/lattices）。每个体素包含一组 boids/agent。代理的连续空间位置（通常是 2 或 3 个浮点数）被转换为体素坐标（2 或 3 个整数，通过缩放 \xe2\x80\x9cfloor\xe2\x80\x9d 操作），它们被散列在一起以产生\xe2\x80\x9cvoxel ID\xe2\x80\x9d 用作体素哈希表中的键。因此，在 O(1) 恒定时间内，就像数组引用一样，您可以查找包含当前位于同一体素中的所有代理的集合的体素。\xe2\x80\x9cquery 球体\xe2\x80\x9d 通常会重叠多个体素。这些可以通过将查询点偏移体素间距距离的倍数来找到。这几个体素的内容被合并在一起以形成潜在邻居的集合，然后按距离进行过滤。当智能体/机器人移动时，它们会比较新旧 \xe2\x80\x9cvoxel ID\xe2\x80\x9d，如果不相等，则将自己从数据结构中删除，然后重新插入到新位置。

\n

体素空间中的查询球体:\n

\n

资源：

\n

\xe2\x80\x9cspatial 数据结构\xe2\x80\x9d/\xe2\x80\x9cspatial 数据库大约有无数种类型。\xe2\x80\x9d 请参阅此 Wikipedia 文章进行调查：空间数据库。另请参阅 Hanan Samet\xe2\x80\x99s 早期论文： 1989\xe2\x80\x99s Hierarchical Spatial Data Structures和 1995\xe2\x80\x99s Spatial Data Structures。

\n

在我自己 2000 年代初期的工作中，我使用了固定大小的体素集合，用 i,j,k 坐标进行寻址：\n 2000 年与自主角色组的交互，以及 2006 年PS3 上的 Big Fast Crowds。后来，我切换了使用 \xe2\x80\x9cspatial 哈希到 voxels\xe2\x80\x9d 方法，该方法不需要 3d 体素网格尺寸的先验规范，并且对于具有许多空体素的稀疏代理分配具有零开销。

\n

[2023 年编辑：我应该提到：Nie\xc3\x9fner、Zollh\xc3\xb6fer、Izadi、Stamminger。2013。使用体素哈希进行大规模实时 3D 重建。ACM TOG]

\n