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

Question

背景：

我刚开始做一个游戏，它有一些对象可以通过"sound"相互交流（不一定是真实的声音，可以是模拟的声音，但它应该表现喜欢声音）。

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

问题：

是否有一些聪明的方法来测试另一个物体是否在听力范围内而不必循环遍历所有其他物体？（当它是很多）。

注意：听觉范围内的物体可以有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

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

Algorithm for finding object in range without looping through all other objects?

algorithm

collision-detection