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

Question

背景:

我正处于制作游戏的初期，它的对象应该能够通过“声音”相互交流(不一定是真实的声音，可以是模拟的声音，但它应该表现得像声音)。

这意味着他们只有在听力范围内才能相互交流。

问题:

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

注意:听觉范围内的物体可能不止1个，所以将所有听觉范围内的物体都添加到一个数组(或列表，尚未确定)中进行通信。

数据

当前对象具有这些属性(如果需要可以更改)。

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