我正在做一个植绒模拟，只是为了好玩，我想对其进行一些优化。需要工作的区域是在给定的 boid 附近寻找 boid。我认为要做到这一点，某种适合该任务的空间数据结构将是我最好的选择（请参阅此处并向下滚动一下。）。
无论我做什么，我都会用 Java 从头开始实现自己。这样一来，我将比仅调用一堆库函数了解更多有关我选择的数据结构的信息。
我知道R-Trees、kd trees和Quadtrees。在我看来，它们都是可行的选择。但我对这些数据结构没有任何经验，我不完全确定什么最适合我的目的。我不需要这种规模的任何东西——我说的可能是几百个，最多可能是一千，而不是一百万，尽管请记住，我最终可能最终会在 Android 手机上运行它。
请为此推荐一个数据结构（当然不限于上述），并给我一个选择它而不是替代方案的充分理由。
是的，我见过这个问题。不，我对答案不满意——根本没有给出任何理由。
哦，还有一件事——正如标题所说，这仅适用于二维。
帮助Iskar Jarak已经晚了九年，但我会插话，因为其他人可能会在搜索中找到这个老问题。
关键是几乎任何事情都比查看每一对 boid 的天真 O(n²) 方法要好。所以正如 Iskar 所建议的，任何一种基于树的空间数据结构都是一个巨大的改进，基本上是 O( n log n )。也就是说：n个boid中的每一个都需要查找它的邻居，每个邻居都是O（log n）。
需要注意的是， Desmond Vehar提到的“命中检测”是一个稍微不同的问题，询问“这个查询位置是否在我的数据结构中的任何‘对象’内部？” 在多智能体模拟中，我们希望找到多个邻居。有时是“最近的 N 个邻居”，或者可能是“查询位置给定半径内的所有邻居”。通常将一个 boid 描述为其中心点并根据点之间的距离进行过滤，从而产生一个“查询球体”就足够了。</p>
在他的算法课程中， Tim Roughgarden一直在问“我们能做得更好吗？” 事实上——虽然 O(log n ) 比 O( n ) 更适合查找邻居——但最好的是恒定时间查找，O(1)。这里哈希表（又名未排序的地图）是我们的朋友。
这两个想法，多邻居和散列，导致了加速多智能体模拟的好方法：空间散列到体素（/盒子/格子）。每个体素都包含一组 boids/agents。代理的连续空间位置（通常为 2 或 3 个浮点数）被转换为体素坐标（2 或 3 个整数，通过缩放的“地板”操作），这些坐标被散列在一起以产生一个“体素 ID”，用作键入体素的哈希表。因此，在 O(1) 恒定时间内，就像数组引用一样，您可以查找包含当前在同一体素中的所有代理的集合的体素。“查询球体”通常会重叠多个体素。这些可以通过将查询点偏移体素间距距离的倍数来找到。这几个体素的内容合并在一起形成潜在邻居的集合，然后按距离过滤。当代理/实体移动时，它们会比较新旧“体素 ID”，如果不相等，
体素空间中的查询球体：
资源：
大约有无数种“空间数据结构”/“空间数据库”。请参阅此 Wikipedia 文章进行调查：空间数据库。另请参阅 Hanan Samet 的早期论文：1989 年的分层空间数据结构和 1995 年的空间数据结构。
在我自己在 2000 年代初期的工作中，我使用了固定大小的体素集合，并使用 i、j、k 坐标： 2000 年与自治字符组的交互，以及 2006年 PS3 上的大快速人群。后来，我转而使用“空间散列到体素”方法，它不需要 3d 体素网格尺寸的先验规范，并且对于具有许多空体素的稀疏代理分布具有零开销。
老实说，我会从一个未优化的版本开始，看看你能走多远（多少博德）。之后，尝试不同的方法并测量它们产生的差异。我认为这将是最好的学习方式。
四叉树是一种非常标准的数据结构，用于视频游戏中的命中检测。我认为这将非常适合您的目标。