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