Как подразделить 2d игровой мир для лучшего обнаружения столкновений

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

У меня есть несколько особых проблем для этого игрового мира...

  • Я хочу иметь возможность использовать большое количество объектов в игровом мире сразу. Однако,% сущностей не будет сталкиваться с объектами того же типа. Например, снаряды не будут сталкиваться с другими снарядами.

  • Я хочу иметь возможность использовать большой диапазон размеров сущностей. Я хочу, чтобы между наименьшими сущностями и самым большим была разница между большими размерами.

  • В игровом мире очень мало статических или не движущихся объектов.

Мне интересно использовать что-то похожее на то, что описано в ответе здесь: Quadtree vs Red-Black tree для игры на С++?

Мое беспокойство заключается в том, насколько хорошо дерево дерева может обрабатывать большие различия в размерах сущностей? Чтобы разделить мир на более мелкие сущности, более крупные должны будут занимать большое количество регионов, и меня беспокоит, как это повлияет на производительность системы.

Другая серьезная проблема заключается в том, как правильно обновлять список занятых районов. Поскольку существует много движущихся объектов и некоторые очень большие, кажется, что разделение мира приведет к значительным накладным расходам для отслеживания того, какие объекты занимают регионы.

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

Ответы

Ответ 1

Если бы я был вами, я бы начал с реализации простого дерева BSP (двоичного пространства). Так как вы работаете в 2D, проверка привязки коробки очень быстро. Вам в основном нужны три класса: CBspTree, CBspNode и CBspCut (не нужны)

  • CBspTree имеет один корень node экземпляр класса CBspNode
  • CBspNode имеет экземпляр CBspCut
  • CBspCut символизирует, как вы разрезаете множество в двух непересекающихся множествах. Это может быть эффективно решено путем введения полиморфизма (например, CBspCutX или CBspCutY или какой-либо другой линии резания). CBspCut также имеет два CBspNode

Интерфейс к разделенному миру будет проходить через древовидный класс, и может быть действительно хорошей идеей создать еще один слой поверх этого, если вы хотите заменить BSP-решение, например. квадратное дерево. Как только вы получите это. Но, по моему опыту, BSP будет очень хорошо.

Существуют различные стратегии хранения ваших элементов в дереве. Я имею в виду, что вы можете выбрать, например, какой-то контейнер в каждом node, который содержит ссылки на объекты, занимающие эту область. Это означает, что (как вы сами спрашиваете себя), что крупные предметы будут занимать много листьев, т.е. Будет много ссылок на большие объекты, и очень маленькие предметы будут отображаться на отдельных листьях.

По моему опыту это не оказывает такого большого влияния. Конечно, это важно, но вам нужно будет провести некоторое тестирование, чтобы проверить, действительно ли это проблема. Вы могли бы обойти это, просто оставив эти элементы в разветвленных узлах в дереве, т.е. Вы не будете хранить их на "уровне листа". Это означает, что вы быстро найдете эти объекты, пройдя по дереву.

Когда дело доходит до вашего первого вопроса. Если вы собираетесь использовать это подразделение для тестирования столкновений и ничего другого, я предлагаю, чтобы вещи, которые никогда не могут столкнуться, никогда не вставляются в дерево. Ракета, например, как вы говорите, не может столкнуться с другой ракетой. Это означало бы, что вам даже не нужно хранить ракету в дереве.

Однако вам может понадобиться использовать bsp для других вещей, но вы не указали это, но помните об этом (для выбора объектов, например, с помощью мыши). В противном случае я предлагаю вам хранить все в bsp и позже разрешать столкновение. Просто спросите bsp списка объектов в определенной области, чтобы получить ограниченный набор возможных кандидатов на столкновение и выполнить проверку после этого (предполагая, что объекты знают, с чем они могут столкнуться, или какой-либо другой внешний механизм).

Если вы хотите ускорить работу, вам также нужно позаботиться о слиянии и split, т.е. когда вещи удаляются из дерева, многие узлы будут становятся пустыми или количество элементов ниже некоторого уровня node будет уменьшаться ниже некоторого порога слияния. Затем вы хотите объединить два поддерева в один node содержащий все элементы. Разделение происходит, когда вы вставляете предметы в мир. Поэтому, когда количество элементов превышает некоторый порог разделения, вы вводите новый разрез, который разбивает мир пополам. Эти пороги слияния и разделения должны быть двумя константами, которые вы можете использовать для настройки эффективности дерева.

Слияние и разделение в основном используются для поддержания сбалансированного дерева и обеспечения его эффективности как можно в соответствии со своими спецификациями. Это действительно то, о чем вам нужно беспокоиться. Перемещение вещей из одного места и, таким образом, обновление дерева происходит быстро. Но когда дело доходит до слияния и разделения, это может стать дорогостоящим, если вы делаете это слишком часто.

Этого можно избежать, введя какую-то ленивую систему слияния и сплита, т.е. у вас есть какая-то грязная отметка или изменение счетчика. Выгружайте все операции, которые могут быть загружены, т.е. Перемещение 10 объектов, а вставка 5 может быть одной партией. Как только эта партия операций будет завершена, вы проверите, загрязнено ли дерево, а затем выполните необходимые операции слияния и/или разделения.

Опубликуйте несколько комментариев, если вы хотите, чтобы я объяснил далее.

Приветствия!

Изменить

В дереве есть много вещей, которые можно оптимизировать. Но, как вы знаете, преждевременная оптимизация - это корень ко всему злу. Так что начните просто. Например, вы можете создать некоторую общую систему обратного вызова, которую вы можете использовать при обходе дерева. Таким образом, вам не нужно запрашивать дерево, чтобы получить список объектов, которые соответствовали связанным полям "вопрос", вместо этого вы можете просто перемещаться по дереву и выполнять этот вызов каждый раз, когда вы что-то нажимаете. "Если этот связанный ящик, который я предоставляю, пересекает вас, затем выполните этот обратный вызов с этими параметрами"

Ответ 3

Моя забота о том, насколько хорошо будет дерево подразделение мира сможет обрабатывать большие различия в размерах юридические лица? Разделить мир вверх достаточно для небольших объектов более крупные должны будут занять большое количество регионов, и я обеспокоены тем, как это повлияет производительность системы.

Используйте квадратное дерево. Для объектов, которые существуют в нескольких областях, у вас есть несколько вариантов:

  • Храните объект в обеих ветвях, вплоть до конца. Все заканчивается в листовых узлах, но вы можете получить значительное количество дополнительных указателей. Может быть уместным для статических вещей.

  • Разделите объект на границе зоны и вставьте каждую часть в соответствующие местоположения. Создает много боли и не очень хорошо определен для большого количества объектов.

  • Сохраните объект в самой нижней точке дерева, которое вы можете. Наборы объектов теперь существуют в листовых и нелистовых узлах, но каждый объект имеет один указатель на него в дереве. Вероятно, лучше всего для объектов, которые будут перемещаться.

Кстати, причина, по которой вы используете квадровое дерево, состоит в том, что с ней действительно очень легко работать. У вас нет эвристического создания, как вы могли бы с некоторыми реализациями BSP. Это просто, и он выполняет свою работу.

Моя другая главная проблема заключается в том, как правильно сохранить список занятых области до настоящего времени. Поскольку там много движущихся объектов, а некоторые очень большие, кажется, разделение во всем мире создаст значительный количество накладных расходов для отслеживания из которых лица занимают регионы.

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

Очевидно, что в зависимости от количества объектов, размера игрового мира и т.д. компромисс может не стоить того. Обычно это победа, но ее трудно понять, не делая этого.

Ответ 4

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

Многие структуры ускорения (например, хороший BSP) могут занять некоторое время для настройки и, как правило, неприемлемы для быстрой анимации.

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

Ответ 5

У меня возникнет соблазн просто наложить грубую сетку поверх игровой зоны, чтобы сформировать 2D-хеш. Если сетка, по крайней мере, имеет размер самого крупного объекта, тогда у вас есть только 9 квадратов сетки для проверки на наличие столкновений, и это намного проще, чем управление четырьмя деревьями или произвольными деревьями BSP. Накладные расходы на определение того, какой грубой квадрат сетки вы находитесь, как правило, всего 2 арифметические операции, и когда обнаружено изменение, сетка просто должна удалить одну ссылку/идентификатор/указатель из одного квадратного списка и добавить то же самое к другому квадрату.

Дальнейшие успехи могут быть достигнуты при сохранении снарядов из системы поиска grid/tree/etc - так как вы можете быстро определить, где находится снаряд в сетке, вы знаете, какие квадраты сетки запрашивают потенциальные столкновения. Если вы поочередно проверяете столкновения с окружающей средой для каждого снаряда, нет необходимости в том, чтобы другие объекты затем проверяли на столкновение с снарядами в обратном направлении.