Пересечение объектов требуется определять во многих прикладных программах. Например, когда вы наводите курсор мыши на кнопку, чтобы нажать её, это пересечение курсора мыши и кнопки, и его нужно определять.
Я, естественно, буду рассматривать этот вопрос с уклоном в игры. Потому что именно в играх пересечение объектов это основа всего.
Если персонаж запрыгивает на ступеньку – он пересекается со ступенькой. Если выпустил пулю во врага – она пересекается с врагом.
Рассчитывать пересечения можно с использованием разных моделей, и сейчас мы бегло вспомним несколько способов.
- Точка и прямоугольник.
Проще всего рассчитать, попадает ли точка внутрь заданного прямоугольника.
if x > x0 and x < x1 and y > y0 and y< y1 ... - Вертикальный / горизонтальный отрезок и прямоугольник. Немного сложнее точки.
- Прямоугольник и прямоугольник. Каждый прямоугольник это 2 вертикальных и 2 горизонтальных отрезка, так что получаем просто несколько лишних условий.
- Круг и круг. Два круга пересекаются, если дистанция между их центрами меньше, чем сумма их радиусов.
Какая точность достаточна?
Некоторые игры идеально подходят под некоторые методы расчёта пересечений. Например, в игре Pong мячик и ракетка это прямоугольники, и значит пересечения между ними рассчитываются абсолютно точно.
В игре Arkanoid кирпичи прямоугольные, а мячик круглый.
но мячик "круглый" лишь условно, поэтому его легко считать квадратным.
Нас же больше интересуют пересечения сложных объектов. Например:
Обычной практикой является использование ограничивающих прямоугольников (Bounding Box):
Здесь независимо от формы объекта пересечение рассчитывается как для прямоугольников. Во многих случаях этого достаточно, так как столкновения происходят примерно там, где они должны происходить, и игрок попросту ничего не замечает, либо это считается допустимым свойством игры.
Что же делать, если игровой объект слабо заполняет свой ограничивающий прямоугольник, и будет хорошо заметно, что пересечение срабатывает там, где его по факту нет?
Можно уменьшить прямоугольники так, чтобы в них оставалось меньше пустого пространства:
Это приведёт к тому, что в иных случаях объекты начнут немного задевать друг за друга, но пересечение не будет считаться. Нередко это также выглядит нормально для игрока.
Но бывает, что и этого недостаточно. Тогда каждый объект можно представить как набор прямоугольников:
И соответственно, чтобы рассчитать пересечение между двумя объектами, нужно каждый прямоугольник одного объекта сравнить с каждым из второго.
Попиксельное сравнение
Последний описанный метод очевидно наиболее точный. Мы всегда можем дробить крупные прямоугольники на более мелкие, пока полученная точность нас не удовлетворит.
Но сложность здесь представляет именно дробление. Это должен сделать или дизайнер, или какой-то специальный алгоритм.
В более простом случае можно представить каждый пиксел изображения как прямоугольник 1x1, тогда мы добиваемся идеальной точности и не нуждаемся ни в каких алгоритмах разбиения или работе дизайнера, всё происходит автоматически. Также упрощается формат хранения – пикселы изображения имеют информацию о самих себе, дополнительные структуры, описывающие размеры и местоположение прямоугольников, не нужны.
Но недостаток данного метода – его вычислительная сложность. Изображение размером 32*32 пиксела будет содержать 1024 пиксела, и чтобы вычислить пересечение с другим изображением такого же размера, придётся совершить 1 048 576 операций (в худшем случае, так как вычисления заканчиваются, как только найдена пара совпадающих пикселов).
Само по себе это число, хоть и большое, не является чем-то запретительным, так как всё зависит от задачи, которую мы решаем, и контекста использования. Но очевидно, что если в кадре есть сотни или тысячи объектов, и каждый надо проверить на пересечение с персонажем, данный метод приведёт к очень серьёзной нагрузке на процессор.
Методы оптимизации
Во-первых, если ограничивающие прямоугольники не пересекаются, то и объекты, находящиеся в них, заведомо не пересекаются. Обычно, даже если на экране присутствует 1000 врагов или снарядов, физически контактировать с персонажем может только... пусть будет 10 из них. Сделав первичное сравнение прямоугольников, можно задачу для любого количества объектов N свести к задаче для N < 10.
Во-вторых, с помощью того же пересечения прямоугольников мы можем получить область пересечения. И считать результат только внутри этой области, а не по полным прямоугольникам.
А далее нам поможет игровая магия. Скажем, будет самоубийственно считать попиксельное пересечение двух крупных объектов. Но именно крупные объекты в игре, как правило, не могут столкнуться так, чтобы значительно перекрыть друг друга. Пересечение произойдёт там, где проходит граница объекта, то есть ближе к его краю. А значит, и область пересечения получится очень маленькая, которую можно будет быстро посчитать.
В-третьих, можно по пикселам объекта построить битовую маску, где 1 обозначает непрозрачный пиксел, а 0 – прозрачный. В одном байте маски будет содержаться информация о 8 пикселах. И сравнивать эту маску с другой маской можно будет побайтово. То есть в 8 раз быстрее. Требуется только дополнительная память для масок.
Ещё мысли
Не могу пока доказать, что это принесёт какую-то пользу :)
Можно вернуться к модели множества прямоугольников, но генерировать их из последовательностей одинаковых пикселов в маске. Скажем, если в маске последовательно идут биты 11111, то они образуют прямоугольник 5*1. Так мы получаем нечто среднее между чистыми пикселами и набором прямоугольников. В нашем случае все прямоугольники будут высотой 1 пиксел.
Можно чуть усложнить, и если в двух соседних строках изображения оказались одинаковые по ширине прямоугольники, то объединять их по высоте.
Данная модель может работать, если принять во внимание контент. Как правило, изображение игрового объекта будет иметь пустые пикселы по углам и сплошные в середине, поэтому на каждую строку изображения придётся в среднем по 3 прямоугольника, и это будет слабо зависеть от его размера.
Ультимативный метод O(1)
Вот мы и добрались до финала.
Суть метода, который за O(1) операций может определить, пересекаются ли попиксельно два объекта, состоит в следующем:
Нужно взять все возможные положения двух объектов относительно друг друга, при которых они могут пересекаться (зона, помеченная красным):
И для каждого их этих положений спокойно попиксельно вычислить, пересекаются они или нет. Результаты нужно сохранить.
Таким образом, у нас получится массив: индекс в нём это номер взаимного положения объектов, а значение это есть пересечение или нет.
Далее в игре мы проверяем пересечения как обычно с помощью ограничивающих прямоугольников. Если они пересеклись, то по их взаимному положению мы получаем индекс, и по индексу в массиве узнаём про пересечение. Всё!
Гениально, но есть очень большая проблема.
Для двух объектов размером 256*256 придётся посчитать 262144 положений. Можно упаковать значения опять же в битовые маски, что даст 32768 байт. 32 килобайта на пару объектов – в сущности не так много, но если у нас 256 уникальных объектов, и каждый может пересечься с каждым, то общий объём хранимых данных вырастает до гигабайта.
Далее можно решать, приемлемо это или нет.
Я привёл достаточно экстремальный пример: и размеры объектов большие, и число их большое, и пересекаются все со всеми. В конкретной игре всё может быть проще: скажем, объекты размером не более 64*64, уникальных (одновременно на уровне) не более 64, и пересекаются только два (игрок и его оружие) с остальными (врагами). Итого получится 262 килобайта данных, что очень даже приемлемо. В принципе, с учётом объёмов современной памяти, приемлемо всё до нескольких десятков мегабайт, не так ли?
В рукаве у меня осталась ещё пара способов оптимизации данного решения для больших объектов, но нужно подумать :)