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

Вы определенно захотите проверить этот список ресурсов обнаружения столкновений с gamedev.net . Он полон ресурсов с соглашениями о разработке игр.

Для целей, отличных от обнаружения столкновений, проверьте их весь список статей и ресурсов .

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

Use a quad tree. For objects that exist in multiple areas you have a few options:

• Store the object in both branches, all the way down. Everything ends up in leaf nodes but you may end up with a significant number of extra pointers. May be appropriate for static things.

• Split the object on the zone border and insert each part in their respective locations. Creates a lot of pain and isn't well defined for a lot of objects.

• Store the object at the lowest point in the tree you can. Sets of objects now exist in leaf and non-leaf nodes, but each object has one pointer to it in the tree. Probably best for objects that are going to move.

By the way, the reason you're using a quad tree is because it's really really easy to work with. You don't have any heuristic based creation like you might with some BSP implementations. It's simple and it gets the job done.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ура!

---

Править

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

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

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

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

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

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