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

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