Алгоритм нахождения объекта в диапазоне, не проходя через все другие объекты?

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

Вы можете взглянуть на некоторые умные структуры данных, такие как quadtree или kd-tree, но для проблемы с запросом с фиксированным диапазоном, может быть, не так уж и плохо просто использовать простой биннинг.Я представлю общий алгоритм в 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