На вашем месте я бы начал с простого дерева BSP (раздел двоичного пространства). Так как вы работаете в 2D, проверки с привязанными ящиками выполняются очень быстро. Вам в основном нужны три класса: CBspTree, CBspNode и CBspCut (не очень нужны)
- CBspTree имеет один экземпляр корневого узла класса CBspNode
- CBspNode имеет экземпляр CBspCut
- CBspCut символизирует, как вы разрезаете набор в два непересекающихся набора. Это можно аккуратно решить путем введения полиморфизма (например, CBspCutX или CBspCutY или какой-либо другой линии разреза). CBspCut также имеет два CBspNode
Интерфейс к разделенному миру будет проходить через древовидный класс, и было бы неплохо создать еще один слой поверх него, на случай, если вы захотите заменить решение BSP, например, на. четырехугольное дерево. Как только вы освоитесь с этим. Но по моему опыту, BSP будет хорошо.
Существуют разные стратегии хранения ваших предметов в дереве. Я имею в виду, что вы можете выбрать, например, иметь некоторый вид контейнера в каждом узле, который содержит ссылки на объекты, занимающие эту область. Это означает, что (как вы спрашиваете себя), что большие предметы будут занимать много листьев, то есть будет много ссылок на большие объекты, и очень маленькие предметы будут отображаться на отдельных листьях.
По моему опыту, это не имеет такого большого влияния. Конечно, это имеет значение, но вам нужно провести некоторое тестирование, чтобы проверить, действительно ли это проблема или нет. Вы сможете обойти это, просто оставив эти элементы в разветвленных узлах дерева, то есть вы не будете хранить их на «уровне листьев». Это означает, что вы быстро найдете эти объекты, пройдя по дереву.
Когда дело доходит до вашего первого вопроса. Если вы собираетесь использовать это подразделение только для тестирования столкновений и ничего другого, я предлагаю, чтобы вещи, которые никогда не сталкивались, никогда не вставляются в дерево. Ракета, например, как вы говорите, не может столкнуться с другой ракетой. Что означало бы, что вам даже не нужно хранить ракету на дереве.
Однако вы можете использовать bsp и для других вещей, вы не указали это, но имейте это в виду (для выбора объектов, например, с помощью мыши). В противном случае я предлагаю вам сохранить все в bsp и разрешить конфликт позже. Просто попросите bsp списка объектов в определенной области, чтобы получить ограниченный набор возможных кандидатов на столкновение, и выполните проверку после этого (предполагая, что объекты знают, с чем они могут столкнуться, или какой-то другой внешний механизм).
Если вы хотите ускорить процесс, вам также необходимо позаботиться о слиянии и разбиении , т.е. когда вещи будут удалены из дерева, многие узлы станут пустыми или количество элементов ниже некоторого уровня узла уменьшится ниже некоторого порога слияния. Затем вы хотите объединить два поддерева в один узел, содержащий все элементы. Разделение происходит, когда вы вставляете предметы в мир. Поэтому, когда количество предметов превышает некоторый порог разделения, вы вводите новый разрез, который разделяет мир на две части. Эти пороги слияния и разделения должны быть двумя константами, которые вы можете использовать для настройки эффективности дерева.
Слияние и разделение в основном используются для поддержания сбалансированности дерева и обеспечения его максимальной эффективности в соответствии с его спецификациями. Это действительно то, что вам нужно беспокоиться. Перемещение объектов из одного места и, соответственно, обновление дерева - это очень быстро. Но когда дело доходит до слияния и разделения, это может стать дорогим, если вы делаете это слишком часто.
Этого можно избежать, введя какую-то ленивую систему слияния и разделения, то есть у вас есть какая-то грязная пометка или изменение счетчика. Пакетируйте все операции, которые можно пакетировать, то есть перемещение 10 объектов и вставка 5 могут быть одним пакетом. По завершении этого пакета операций вы проверяете, не является ли дерево грязным, а затем выполняете необходимые операции слияния и / или разделения.
Оставьте несколько комментариев, если вы хотите, чтобы я объяснил дальше.
Ура!
Редактировать
Есть много вещей, которые можно оптимизировать в дереве. Но, как вы знаете, преждевременная оптимизация является корнем всего зла. Так что начните с простого. Например, вы можете создать некую общую систему обратного вызова, которую вы можете использовать при обходе дерева. Таким образом, вам не нужно запрашивать дерево, чтобы получить список объектов, которые соответствуют ограниченному полю «вопрос», вместо этого вы можете просто пройти по дереву и выполнить этот обратный вызов каждый раз, когда вы что-то нажимаете. «Если это ограниченное поле, которое я предоставляю, пересекает вас, то выполните этот обратный вызов с этими параметрами»