在范围内查找对象而不循环遍历所有其他对象的算法？

Question

背景：

我正处于制作游戏的开始，它的对象应该能够通过“声音”彼此通信（不一定是真实的声音，可以是模拟声音，但它应该表现得像声音）。

这意味着如果它们在听觉范围内，它们只能与彼此通信。

题：

是否有一些聪明的方法来测试另一个对象是否在听觉范围内而不必遍历所有其他对象？ （当它们很多时，它会变得非常低效）。

注意：听力范围内可以有多个对象，因此听力范围内的所有对象都会添加到阵列（或列表，尚未确定）进行通信。

数据

目前，该对象具有这些属性（如果需要可以更改）。

Object {
    id = self.id,
    x = self.x,
    y = self.y,
    hearing_max_range = random_range(10, 20), // eg: 10
    can_hear_other = []; // append: other.id when in other in range
}

Answer 1

您可以查看一些聪明的数据结构，例如四叉树或kd树，但对于固定范围查询的问题，仅使用简单的分箱可能不会太糟糕。我将在类似python的伪代码中呈现通用算法。

首先构建你的箱子：

from collections import defaultdict

def make_bin(game_objects, bin_size):
    object_bins = defaultdict(list)
    for obj in game_objects:
        object_bins[(obj.x//bin_size, obj.y//bin_size)].append(obj)

然后根据需要查询：

def find_neighbors(game_object, object_bins, bin_size):
    x_idx = game_object.x // bin_size
    y_idx = game_object.y // bin_size
    for x_bin in range(x_idx - 1, x_idx + 2):
        for y_bin in range(y_idx - 1, y_idx + 2):
            for obj in object_bins[(x_bin, y_bin)]:
                if (obj.x - game_object.x)**2 + (obj.y - game_object.y)**2 <= bin_size**2:
                    yield obj