Эффективная структура данных для перекрывающихся пространственных областей

Question

Я пишу игру, в которой большое количество объектов будет иметь «эффекты области» над областью мозаичной 2D-карты.

Необходимые функции:

• Некоторые из этих эффектов области могут перекрываться и влиять на одну и ту же плитку
• Должен быть возможен очень эффективный доступ к списку эффектов для любогоданная плитка
• Эффекты области могут иметь произвольные формы, но обычно имеют вид "до X плиток на расстоянии от объекта, вызывающего эффект", где X - это небольшое целое число, обычно 1-10
• Эффекты области будут часто меняться, например, при перемещении объектов в разные места на карте
• Карты могут быть потенциально большими (например, 1000 * 1000 плиток)

Какая структура данныхбудет работать лучше для этого?

Answer 1

Если у вас действительно есть много эффектов области, происходящих одновременно, и что они будут иметь произвольные формы, я бы сделал это следующим образом:

• при создании нового эффекта хранится в глобальном списке эффектов (не обязательно глобальная переменная, просто то, что относится к вся игра или текущая игровая карта)
• вычисляет, какие плитки влияет и сохраняет список этих тайлов против эффекта
• каждая из этих плиток уведомлены о новом эффекте и сохраняет ссылку на него в список на плитку (в C ++ я бы использовал std :: vector для этого, что-то с непрерывное хранилище, не связанное список)
• окончание эффекта обрабатывается путем итерации заинтересованные тайлы и удаление ссылок на них, прежде чем уничтожить их
• перемещение или изменение его формы обрабатывается удалением ссылки, как указано выше, выполняя расчеты изменений, затем повторное присоединение ссылок в тайлах теперь влияет на
• у вас также должна быть инвариантная проверка только для отладки, которая выполняет итерацию вся ваша карта и проверяет, что список плиток в эффекте точно соответствует плиткам на карте, которые ссылаются на нее.

Answer 2

Обычно это зависит от плотности вашей карты.

Если вы знаете, что каждая плитка (или большая часть плиток) содержит хотя бы один эффект, вам следует использовать обычную сетку - простой двумерный массив плиток.

Если ваша карта заполнена слабо и в ней много пустых тайлов, имеет смысл использовать некоторые пространственные индексы , такие как квад-дерево, R-дерево или BSP-деревья.

Answer 3

Если у вас есть известный максимальный диапазон каждого эффекта области, вы можете использовать выбранную структуру данных и хранить только фактические источники, оптимизированные для обычного 2D Collision Testing.

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

Если у вас есть небольшое (<10) количество «полевых» форм эффекта, вы даже можете сделать уникальное обнаружение столкновений для каждого типа поля эффекта в пределах их предварительно вычисленного максимального диапазона. </p>

Answer 4

Некоторые решения для перебора, не основанные на причудливой информатике:

1000 x 1000 не слишком большой - просто мег. Компьютеры имеют концерты. Вы могли бы иметь 2d массив. Каждый бит в байтах может быть «типом области». «Зона воздействия», которая больше, может быть еще немного. Если у вас есть достаточное количество областей разных типов, вы все равно можете использовать многобайтовую битовую маску. Если это смешно, вы можете указывать элементы массива на списки перекрывающихся объектов типа области. Но тогда вы теряете эффективность.

Вы также можете реализовать разреженный массив - используя ключ хеш-таблицы вне координат (например, key = 1000 * x + y) - но это во много раз медленнее.

Если, конечно, если вы не возражаете против кодирования причудливых способов информатики, они обычно работают намного лучше!

Answer 5

Обычно BSP-Trees (или quadtree или octrees ).