移动点距离内的点

Question

我正在做一个关于捕食者、猎物和食物的进化模拟(植物在地形上生长，取决于环境和生物死亡时释放的肉)。它们中的每一个都有一个(x，y)位置。

目前，每个生物都有几只对红色、绿色和蓝色通道敏感的“眼睛”，当生物或一块食物在它们的视线范围内时，眼睛会根据它们看到的物体的颜色、相对角度和与生物的距离，向它们的神经网络发送输入。

我现在要做的是遍历所有的植物、肉块和生物，并检查它们是否在生物的视线范围内。如果该条件为真，则计算网络的输入。

问题是，与生物的观看距离相比，世界是巨大的(大约10,000*10,000个“单位”)，通常在150到300个“单位”之间。最重要的是，植物数量可能会变得非常高，这取决于地形条件(也可以达到几千株)，连同所有其他生物和肉块。

因此，我通常会为每个生物执行一个巨大的循环，这真的会减慢模拟速度，因为大多数生物和食物都是完全不相关的(离得太远)。

我要求的是一些方法或算法，可以减少每个循环中检查距离的点的数量，限制检查点的距离，或者其他一些技术。

PS:我想将模拟分成不同的“区域”，这样如果一个生物在一个区域中，它只会检查那个特定区域中的其他点(食物和其他生物)。然而，由于他们不断移动，如果他们在一个区域的边缘，这将使他们的观点非常不准确。我还略微提高了速度，检查了距离^2(不做sqrt)，并且只在它小于viewing_distance^2的情况下才计算它。

Answer 1

将世界划分为不同的区域。如果区域宽度略大于最大观看距离，您只需检查最多4个区域。

使用四叉树或kd树的缺点是需要不断更新结构。但它可能会更有效，做一些侧写。

Answer 2

四叉树结构可以用于几何表示：http://en.wikipedia.org/wiki/Quadtree

这完全取决于你需要多大的效率。区域答案还有一个问题，如果你的生物在一个区域的边界附近，你可能需要扫描4个区域。