Правильный ответ в некоторой степени зависит от конкретной игры, которую вы разрабатываете, и для выбора одной из них действительно потребуется реализовать обе функции и выполнить профилирование, чтобы определить, какая из них более эффективна по времени или пространству в вашей конкретной игре.
Обнаружение сетки, по-видимому, применимо только для обнаружения столкновений между движущимися объектами и статическим фоном. Самым большим преимуществом этого является то, что статический фон представляется в виде непрерывного массива памяти, и каждый поиск столкновений - это O (1) с хорошей локализацией, если вам нужно выполнить несколько операций чтения (поскольку объекты охватывают более одной ячейки в сетке). Недостаток, если статический фон большой, заключается в том, что сетка может быть довольно расточительной.
Если вместо этого вы представляете статический фон в виде дерева квадрантов, то стоимость отдельных поисков возрастает, но поскольку большие блоки фона занимают мало места, требования к памяти снижаются, и поэтому в фоновом режиме может находиться больше фона. кэш. даже если для поиска в такой структуре требуется в 10 раз больше операций чтения, если все в кеше, он все равно будет в 10 раз быстрее, чем один поиск с пропуском кеша.
Если бы я столкнулся с выбором? Я бы пошел с реализацией сетки, потому что это глупо просто сделать, лучше тратить свое время на другие, более интересные проблемы. Если я замечу, что моя игра работает немного медленно, я сделаю некоторое профилирование и посмотрю, что может помочь. Если кажется, что игра тратит много времени на обнаружение столкновений, я бы попробовал другую реализацию, например, quadtree (после исчерпания всех простых исправлений), и выяснил, помогло ли это.
Редактировать: я не знаю, как обнаружение столкновений в сетке связано с обнаружением столкновений нескольких мобильных объектов, но вместо этого я отвечу, как пространственный индекс (Quadtree) улучшает производительность обнаружения по сравнению с итеративным решением. Наивное (и, как правило, прекрасно) решение выглядит примерно так:
foreach actor in actorList:
foreach target in actorList:
if (actor != target) and actor.boundingbox intersects target.boundingbox:
actor.doCollision(target)
Это, очевидно, имеет производительность около O (n ^ 2), с n числом действующих лиц в игре, включая пули, космические корабли и инопланетян. Он также может включать небольшие статические препятствия.
Это работает фантастически хорошо, пока количество таких предметов достаточно мало, но начинает выглядеть немного бедным, когда есть более чем несколько сотен объектов для проверки. 10 объектов - всего 100 проверок на столкновение, 100 - 10000 проверок. 1000 результатов в миллион проверок.
Пространственный индекс (например, дерево квадрантов) может эффективно перечислять элементы, которые он собирает, в соответствии с геометрическими соотношениями. это изменит алгоритм столкновения на что-то вроде этого:
foreach actor in actorList:
foreach target in actorIndex.neighbors(actor.boundingbox):
if (actor != target) and actor.boundingbox intersects target.boundingbox:
actor.doCollision(target)
Эффективность этого (при условии равномерного распределения сущностей): обычно O (n ^ 1,5 log (n)), так как для прохождения индекса требуется около log (n) сравнений, для сравнения будет около sqrt (n) соседей и есть n актеров, чтобы проверить. Реально, однако, число соседей всегда весьма ограничено, так как, если столкновение действительно происходит, большую часть времени один из объектов удаляется или удаляется от столкновения. Таким образом, вы получите только O (n log (n)). Для 10 сущностей вы делаете (примерно) 10 сравнений, для 100 - 200, для 1000 - 3000.
Действительно умный индекс может даже комбинировать поиск соседей с массовой итерацией и выполнять обратный вызов для каждой пересекающейся сущности. Это даст производительность около O (n), поскольку индекс сканируется один раз, а не запрашивается n раз.
Извините за возрождение древней нити, но имхо простые старые сетки не используются достаточно часто для этих случаев. У сетки много преимуществ в том, что вставка / удаление ячеек очень дешевы. Вам не нужно беспокоиться об освобождении ячейки, поскольку сетка не предназначена для оптимизации для разреженных представлений. Я говорю, что, сократив время на выделение выделенных элементов в устаревшей кодовой базе с 1200 мс до 20 мс, просто заменив четырехугольное дерево сеткой. Справедливости ради, однако, это квад-дерево было действительно плохо реализовано, сохраняя отдельный динамический массив для каждого конечного узла для элементов.
Другой, который я считаю чрезвычайно полезным, заключается в том, что ваши классические алгоритмы растеризации для рисования фигур могут использоваться для поиска в сетке. Например, вы можете использовать растеризацию по Брезенхэму для поиска элементов, которые пересекают линию, растеризацию по отсканированной линии, чтобы найти, какие ячейки пересекают многоугольник и т. Д. Поскольку я много работаю в обработке изображений, очень приятно иметь возможность использовать точно такие же оптимизированный код, который я использую для построения пикселей на изображении, когда я использую его для обнаружения пересечений с движущимися объектами в сетке.
Тем не менее, чтобы сделать сетку эффективной, вам не нужно больше 32 бит на ячейку сетки. Вы должны иметь возможность хранить миллион ячеек размером менее 4 мегабайт. Каждая ячейка сетки может просто индексировать первый элемент в ячейке, а первый элемент в ячейке может затем индексировать следующий элемент в ячейке. Если вы храните какой-то полноценный контейнер с каждой отдельной ячейкой, это быстро взрывается при использовании памяти и ее распределении. Вместо этого вы можете просто сделать:
Вот так:
Хорошо, так что до минусов. Я пришел к этому по общему признанию с уклоном и предпочтением к сеткам, но их главный недостаток - то, что они не редки.
Доступ к определенной ячейке сетки с заданной координатой происходит постоянно и не требует спуска по дереву, которое дешевле, но сетка плотная, а не разреженная, поэтому вам может потребоваться проверить больше ячеек, чем требуется. В ситуациях, когда ваши данные распределены очень редко, для сетки может потребоваться проверка большего количества элементов, чтобы определить элементы, которые пересекаются, например, линия или заполненный многоугольник, прямоугольник или ограничивающая окружность. Сетка должна хранить эту 32-битную ячейку, даже если она полностью свободна, и когда вы делаете запрос на пересечение фигуры, вы должны проверить эти пустые ячейки, если они пересекают вашу форму.
Основным преимуществом четырехъядерного дерева, естественно, является его способность хранить разреженные данные и делить их только на необходимое количество. Тем не менее, это действительно трудно реализовать очень хорошо, особенно если у вас есть вещи, движущиеся вокруг каждого кадра. Дерево должно очень эффективно разделять и освобождать дочерние узлы на лету, в противном случае оно превращается в плотную сетку, которая тратит непроизводительные затраты на хранение родительских и дочерних ссылок. Реализовать эффективное четырехугольное дерево очень удобно, используя методы, очень похожие на те, что я описал выше для сетки, но, как правило, это займет больше времени. И если вы делаете это так, как я это делаю в сетке, это тоже не обязательно оптимально, так как это приведет к потере способности гарантировать, что все 4 дочерних элемента узла четырех деревьев сохраняются непрерывно.
Также и квад-дерево и сетка не справляются с задачей, если у вас есть несколько крупных элементов, которые охватывают большую часть всей сцены, но, по крайней мере, сетка остается плоской и в этих случаях не делится на n-ую степень. , Четырехъядерное дерево должно хранить элементы в ветвях, а не просто листья, чтобы разумно обрабатывать такие случаи, иначе оно захочет разделить на сумасшедшие и очень быстро ухудшить качество. Есть и другие патологические случаи, о которых вам нужно позаботиться, используя квад-дерево, если вы хотите, чтобы оно обрабатывало самый широкий диапазон контента. Например, другой случай, который действительно может сбить с толку квад-дерево, - это если у вас есть множество совпадающих элементов. В этот момент некоторые люди просто устанавливают ограничение глубины для своего четырехугольного дерева, чтобы предотвратить его бесконечное деление. У сетки есть привлекательность, что она делает достойную работу,
Стабильность и предсказуемость также полезны в игровом контексте, поскольку иногда вам необязательно нужно самое быстрое решение, которое возможно для обычного случая, если оно может иногда приводить к сбоям в частоте кадров в редких сценариях по сравнению с решением, которое достаточно быстрое для всех. вокруг, но никогда не приводит к таким сбоям и сохраняет частоту кадров гладкой и предсказуемой. Сетка обладает таким последним качеством.
С учетом всего сказанного, я действительно думаю, что дело до программиста. С такими вещами, как сетка, квад-дерево или окт-дерево, kd-дерево и BVH, я голосую за самого плодовитого разработчика, имеющего опыт создания очень эффективных решений, независимо от того, какую структуру данных он / она использует. На микроуровне тоже есть много чего, например, многопоточность, SIMD, удобная для кэша компоновка памяти и шаблоны доступа. Некоторые люди могут рассмотреть эти микро, но они не обязательно оказывают микро-влияние. Такие вещи могут иметь 100-кратное различие от одного решения к другому. Несмотря на это, если бы мне лично дали несколько дней и сказали, что мне нужно реализовать структуру данных, чтобы быстро ускорить обнаружение столкновений элементов, движущихся вокруг каждого кадра, я бы лучше справился с этой сеткой за короткое время, чем с квадратором. -tree.
источник