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

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

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

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

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

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

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

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

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

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

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

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

Ваше здоровье !

Редактировать

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

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

Чтобы узнать только об обнаружении столкновений, проверьте их полный список статей и ресурсов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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