Есть у меня список точек с их координатами, находящихся в рандомных местах на карте. Стоит задача найти соседей возле определенной точки в пространстве в некоем радиусе из этого списка. Как это можно сделать быстрее, чем линейным перебором? Учитывая, что все это происходит в контексте голдсурса, где можно BSP-дерево использовать для каких-то своих целей.
А сам алгоритм в чем заключается? Со всякими деревьями и теорией информатики у меня пока дела плохо обстоят, было бы хорошо если кто-то указал где можно найти информацию по этой теме.
SNMetamorph алгоритм есть на википедии https://ru.wikipedia.org/wiki/K-d_%...%B5%D0%B2%D0%BE
Если дела плохо обстоят, можно другие варианты рассмотреть. Ты говоришь про БСП - точки являются частью карты, и для них уже построено дерево?
SNMetamorph писал: Проблема еще в том, что они могут постоянно менять своё расположение.
Вот AABB-tree идеально для этого подходит. Энтити ведь тоже постоянно меняют своё положение, думаешь что делает UTIL_SetOrigin? Из одного узла дерева убирает, в другой добавляет.
Делишь боксы до желаемого объема и линкуешь к ним все объекты, которые имели неосторожность их пересечь. Ну или полностью уместились внутри.
Это немного разные типы деревьев, в вики можешь глянуть.