Эффективная структура данных для наложения пространственных областей
Я пишу игру, где большое количество объектов будет иметь "эффекты области" по региону мозаичной 2D карты.
Необходимые функции:
- Несколько из этих эффектов области могут перекрыть и влиять на ту же мозаику
- Должно быть возможно очень, эффективно получают доступ к списку эффектов для любой данной мозаики
- Эффекты области могут иметь произвольные формы, но будут обычно иметь форму "до X расстояний мозаик от объекта, вызывающего эффект", где X маленькое целое число, обычно 1-10
- Эффекты области будут часто изменяться, например, когда объекты перемещены в различные местоположения на карте
- Карты могли быть потенциально большими (например, 1000*1000 мозаик)
Какая структура данных работала бы лучше всего на это?
5 ответов
Если у вас действительно одновременно происходит много эффектов площади, и что они будут иметь произвольную форму, я бы сделал это следующим образом:
- когда создается новый эффект, он хранится в глобальном списке эффектов (не обязательно глобальная переменная, просто то, что относится к вся игра или текущая игровая карта)
- вычисляет, какие плитки он влияет и хранит список этих плиток против эффекта
- , каждая из этих плиток уведомлен о новом эффекте, и сохраняет ссылку на него в список для каждой плитки (в C ++ я бы использовал std :: vector для этого, что-то с непрерывное хранилище, а не связанное list)
- завершение эффекта обрабатывается путем повторения интересующие плитки и удаление ссылок на них перед тем, как их уничтожить
- , перемещение или изменение формы обрабатывается путем удаления ссылки, как указано выше, выполняя вычисления изменений, затем повторно прикрепляя ссылки в затронутых фрагментах
- , вы также должны иметь инвариантную проверку только для отладки, которая повторяется через всю карту и проверяет, что список плиток в эффекте точно соответствует плиткам на карте, которые на него ссылаются.
Обычно это зависит от плотности вашей карты.
Если вы знаете, что каждая плитка (или большая часть плиток) содержит хотя бы один эффект, вам следует использовать обычную сетку - простой 2D-массив плиток.
Если ваша карта слабо заполнена и на ней много пустых плиток, имеет смысл использовать некоторые пространственные индексы , такие как дерево квадратов, R-дерево или BSP-деревья.
Если у вас есть известный максимальный диапазон каждого эффекта области, вы можете использовать структуру данных по вашему выбору и хранить только фактические источники, оптимизированные для обычного 2D тестирования столкновений.
Затем, при проверке эффектов на плитке, просто проверьте (в стиле обнаружения столкновений, оптимизированном для вашей структуры данных) все источники эффектов в пределах максимального диапазона, а затем примените определенную функцию проверки (например, если область - круг, проверьте, если расстояние меньше константы; если это квадрат, проверьте, если расстояния x и y находятся в пределах константы).
Если у вас есть небольшое (<10) количество фигур "полей" эффектов, вы можете даже сделать уникальное обнаружение столкновений для каждого типа поля эффектов в пределах их предварительно вычисленного максимального диапазона.
Некоторые решения для грубой силы, которые не Я полагаюсь на причудливую информатику:
1000 x 1000 не слишком много - всего лишь мег. У компьютеров есть концерты. У вас может быть 2-мерный массив. Каждый бит в байтах может быть «типом области». «Зона воздействия», которая больше, могла бы быть совсем другой. Если у вас есть разумное количество различных типов областей, вы все равно можете использовать многобайтовую битовую маску. Если это станет смешным, вы можете сделать указатели элементов массива на списки перекрывающихся объектов типа области. Но тогда вы теряете эффективность.
Вы также можете реализовать разреженный массив - используя ключ хеш-таблицы вне координат (например, key = 1000 * x + y) - но это во много раз медленнее.
Если, конечно, вы не возражаете против программирования причудливыми методами информатики, они обычно работают намного лучше!