2D пространственная структура данных, подходящая для Flocking Boids в Java

Честно говоря, я бы начал с неоптимизированной версии и посмотрел, как далеко вы сможете зайти (сколько боидов). После этого попробуйте разные методы и измерьте, какую разницу они дают. Я думаю, что это был бы лучший способ учиться.

Quadtrees — довольно стандартная структура данных, используемая для обнаружения попаданий в видеоиграх. Я думаю, что это было бы хорошо подходит для вашей цели.

https://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374

Девять лет слишком поздно, чтобы помочь Iskar Jarak, но я вмешаюсь, так как другие могут найти этот старый вопрос в поиске.

Ключевым моментом является то, что почти все лучше, чем наивный подход O(n²), рассматривающий каждую пару boids. Итак, как предполагает Искар, любая пространственная структура данных на основе дерева является значительным улучшением, поскольку в основном составляет O(n log n). То есть: каждый из n boids должен искать своих соседей, каждый из которых равен O(log n).

Следует отметить, что «обнаружение попаданий», упомянутое Десмондом Вехаром, представляет собой немного другую проблему. расположить «внутри» любого из «объектов» в моей структуре данных?» В многоагентных симуляциях мы хотим найти несколько соседей. Иногда «ближайшие N соседей» или, возможно, «все соседи в пределах заданного радиуса позиции запроса». Обычно достаточно описать боид как его центральную точку и отфильтровать по расстоянию между точками, создав «сферу запроса».

В своих курсах по алгоритмам Тим Рафгарден постоянно спрашивает: «Можем ли мы сделать лучше?» И в самом деле, хотя O(log n) лучше, чем O(n) для поиска соседа, лучшим является поиск за постоянное время, O(1). Здесь хеш-таблицы (они же несортированные карты) — наши друзья.

Эти две идеи, множественные соседи и хеширование, приводят к хорошему подходу для ускорения многоагентного моделирования: пространственное хеширование в воксели(/boxes/lattices). Каждый воксель содержит набор boids/агентов. Непрерывное пространственное положение (обычно 2 или 3 числа с плавающей запятой) агента преобразуется в координаты вокселя (2 или 3 целых числа с помощью масштабированной операции «пола»), которые хешируются вместе для получения «идентификатора вокселя», который используется в качестве ключ в хеш-таблице вокселей. Таким образом, в постоянном времени O(1), подобно ссылке на массив, вы можете найти воксель, который содержит коллекцию всех агентов, находящихся в настоящее время в одном и том же вокселе. «Сфера запроса» обычно перекрывает несколько вокселей. Их можно найти, сместив точку запроса на расстояние, кратное расстоянию между вокселами. Содержимое этих нескольких вокселей объединяется вместе, чтобы сформировать набор потенциальных соседей, а затем фильтруется по расстоянию. По мере перемещения агенты/боиды сравнивают свой старый и новый «идентификатор вокселя» и, если они не совпадают, удаляют себя из структуры данных, а затем снова вставляются в новую позицию.

Сфера запроса в воксельном пространстве:

Ресурсы:

Существует примерно миллион типов «пространственной структуры данных»/«пространственной базы данных». См. эту статью в Википедии для опроса: Пространственная база данных. См. также ранние работы Ханана Самета: Hierarchical Spatial Data Structures, 1989 г. и Пространственные структуры данных 1995 года.

В моей собственной работе в начале 2000-х я использовал коллекцию вокселей фиксированного размера, адресуемую координатами i,j,k: Взаимодействие с группами автономных персонажей в 2000 году и Big Fast Crowds на PS3 в 2006 году. Позднее я переключился на использование подхода «пространственного хэширования в воксели», который не требует априорного указания размеров трехмерной воксельной сетки и не имеет накладных расходов на разреженное распределение агентов с множеством пустых вокселей.