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

Question

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

Требуемые характеристики:

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

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

Answer 1

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

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

Answer 2

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

Answer 3

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

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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