Главная » Программирование игр под Android » ОПРЕДЕЛЕНИЕ СТОЛКНОВЕНИЙ И ПРЕДСТАВЛЕНИЕ ОБЪЕКТОВ В 2D – РАЗРАБОТКА ИГР ДЛЯ ОС ANDROID

0

 

Поскольку в нашем мире есть движущиеся объекты, существуют и взаимодействия между ними. Одним из видов таких взаимодействий является столкновение. Два объекта считаются столкнувшимся, когда они каким-либо образом пересекаются. Мы уже встречались со столкновениями, когда проверяли, что поглощает мистер Ном – себя или чернильное пятно. Определение столкновений обычно сопровождается ответом на столкновение: после того как мы определили, что два объекта столкнулись, мы должны отреагировать на столкновение корректировкой положения и/или движения наших объектов должным образом. Например, когда Марио прыгает на гриб Гумба, Гумба отправляется в свой грибной рай, а Марио выполняет еще один маленький прыжок. Более точный пример – столкновение и реакция на столкновение двух и более бильярдных шаров. Мы не будем углубляться в разбор этого вида реакции на столкновение, поскольку это не нужно для наших целей. Наша реакция на столкновение обычно будет состоять в изменении состояния объекта (например, объект может взорваться, умереть, забрать монетку и т. д.). Тип реакции зависит от игры, поэтому мы не будем говорить о ней в этом разделе. Итак, как же мы определяем, что два объекта столкнулись? В первую очередь надо подумать, когда проверять, есть ли столкновения. Если наши объекты соответствуют каким-либо простым физическим моделям, о чем говорилось в предыдущем разделе, мы можем производить проверку на столкновения после того, как переместили все наши объекты на текущий кадр и шаг по времени вперед.

Ограничивающие фигуры

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

Рис. 8.8. Различные ограничивающие фигуры вокруг Боба

Это три типа ограничивающих фигур. Каждая, соответственно, имеет следующие свойства.

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

Ограничивающий прямоугольник с привязкой к осям координат. Ограничивает объект посредством прямоугольника, который привязан к осям координат, то есть его верхняя и нижняя стороны всегда совпадают с осью х, а правая й левая стороны – с осью у. Такая фигура обеспечивает легкость проверок, но точность будет ниже, чем у треугольной сети. Ограничивающая рамка обычно хранится в виде координаты ее нижнего левого угла и ее ширины и длины (при работе с 2D фигуры также могут называться ограничивающими прямоугольниками).

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

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

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

Корректировка при изменении положения выполняется просто: мы всего лишь перемещаем ограничивающую фигуру в соответствии с этими изменениями. Если используется треугольная сеть, мы перемещаем каждую вершину, если ограничивающий прямоугольник – нижний левый угол, если ограничивающий круг – то перемещается его центр.

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

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

Рис. 8.9. Ограничивающие фигуры после вращения при центре объекта как точке вращения

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

Создание ограничивающих фигур

В этом примере я просто построил ограничивающие фигуры от руки, взяв за основу изображение Боба. Но изображение Боба сделано в пикселах, а расстояния в нашем мире могут измеряться метрами. Для решения этой проблемы потребуется нормализация и применение пространства модели. Представьте себе два треугольника, которые мы можем использовать для Боба в пространстве модели, когда будем визуализировать его при помощи OpenGL. Прямоугольник находится по центру в начале координат пространства модели и имеет такое же соотношение ширины и высоты, как и текстурное изображение Боба (например, 32 х 32 пиксела на текстурной карте и 2 х 2 м в пространстве модели). Теперь мы можем применить растровое изображение Боба и выяснить, где в пространстве модели будут находиться точки ограничивающих фигур. На рис. 8.10 показано, как мы создаем ограничивающие фигуры вокруг Боба в пространстве модели.

Рис. 8.10. Ограничивающие фигуры вокруг Боба в пространстве модели

Этот процесс может показаться несколько трудоемким, хотя на самом деле предпринимаемые шаги не так и сложны. В первую очередь мы должны помнить, как работает обработка текстур. Мы задаем текстурные координаты для каждой вершины прямоугольника Боба (который состоит из двух треугольников) в текстурном пространстве. Верхний левый угол растрового изображения в текстурном пространстве находится в (0; 0), а нижний левый угол – в (1; 1) независимо от ширины и высоты изображения в пикселах. Чтобы перейти из пиксельного пространства в текстурное, мы можем использовать такое несложное преобразование:

где u и у – текстурные координаты пиксела, находящегося под координатами хну в пространстве изображения. ImageWi dth и i mageHei ght устанавливаются по размерам изображения в пикселах (в случае Боба – 32 х 32). На рис. 8.11 изображено, как центр изображения Боба переносится в текстурное пространство.

Текстура применяется к прямоугольнику, который мы задаем в пространстве модели. На рис. 8.10 был показан пример, где верхний левый угол находился в точке (-1; 1), а нижний правый – в (1; -1). Для измерений в нашем мире используем метры, поэтому ширина и длина прямоугольника равны 2 м каждая. Кроме того, мы знаем, что верхний правый угол имеет текстурные координаты (0; 0), а нижний правый угол – (1; 1), и таким образом мы наносим полную текстуру Боба. Однако в одном из следующих разделов вы увидите, что это не всегда работает подобным образом.

Рис. 8.11. Перенесение пиксела из пространства изображения в текстурное пространство

Рассмотрим универсальный способ ассоциирования текстурного пространства с пространством модели. Мы можем упростить себе задачу, ограничивая обработку только привязанными к осям координат прямоугольниками в текстурном пространстве и пространстве модели. Это значит, что мы допускаем, что привязанная к осям координат прямоугольная область в текстурном пространстве переносится в привязанный к осям координат прямоугольник в пространстве модели. Для преобразования нам нужно знать ширину и длину прямоугольника в пространстве модели и ширину и длину прямоугольника в текстурном пространстве. В нашем примере с Бобом у нас есть прямоугольник 2 х 2 в пространстве модели и прямоугольник 1 х 1 в текстурном пространстве (поскольку мы переносим полную текстуру в прямоугольник). Нам также необходимо знать координаты верхнего левого угла каждого прямоугольника в соответствующем пространстве. Для прямоугольника в пространстве модели это (-1; 1), а для прямоугольника в текстурном пространстве – (0; 0) (опять же, поскольку мы переносим всю текстуру, а не ее часть). С этими данными и координатами и я у пиксела, который мы хотим перенести в пространство модели, мы можем произвести преобразование при помощи следующих двух уравнений:

Переменные и и v – это координаты, которые мы вычислили в последнем преобразовании из пиксельного в текстурное пространство. Переменные min U и min V – это координаты верхнего левого угла области, которую мы переносим из текстурного пространства. Переменные tWidth и tHeight – ширина и длина нашей области текстурного пространства. Переменные mWidth и mHeight – ширина и длина прямоугольника нашего пространства модели. Переменные minx и minY, как вы догадались, – координаты верхнего левого угла прямоугольника в пространственной модели. И наконец, х и у являются преобразованными координатами в пространстве модели.

Эти уравнения принимают координаты ассоциируют их с диапазоном от 0 до 1, затем масштабируют и помещают в пространство модели. На рис. 8.12 изображен тексел в текстурном пространстве и то, как он перенесен в прямоугольник в пространстве модели. По бокам вы видите tWi dth, tHeight, mWidth и mHeight соответственно. Верхний левый угол каждого прямоугольника соответствует координатам (mi пи; minV) в текстурном пространстве и (min X; min.Y) в пространстве модели.

Рис. 8.12. Перенос из текстурного пространства в пространство модели

Заменив первые два уравнения, мы можем прямо перейти от пиксельного пространства к пространству модели:

Мы можем использовать эти два уравнения для вычисления ограничивающих фигур наших объектов, построенных на основе изображения, которое мы переместили в их прямоугольники с помощью обработки текстуры. В случае треугольной сети это может быть несколько сложным; ограничивающий прямоугольник и ограничивающий круг намного проще. Обычно мы не идем этим сложным путем, а стараемся создать текстуры таким образом, чтобы хотя бы ограничивающие прямоугольники имели такое же соотношение сторон, как и прямоугольник, который мы визуализируем для объекта при помощи OpenGL ES. Таким образом мы можем строить ограничивающий прямоугольник прямо по размерам изображения объекта. Это же будет верным и для ограничивающего круга. Я просто хотел показать, как вы можете создать какую-либо ограничивающую фигуру вокруг изображения, которое переносится в пространство модели.

Вам следует знать, как строить подходящую ограничивающую фигуру для своих 20-объектов. Но помните, что мы определяем размеры этих ограничивающих фигур вручную, когда создаем наши графические ресурсы и задаем компоненты и размеры объектов в игровом мире. Затем мы используем эти размеры в нашем коде для столкновения объектов друг с другом.

 

Атрибуты игровых объектов

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

Позиция, ориентация, масштаб, скорость и ускорение. Используя их, мы можем применить нашу физическую модель из прошлого раздела. Конечно, некоторые объекты могут быть статичными и иметь только позицию, ориентацию и масштаб. Иногда можно даже опустить и ориентацию с масштабом. Позиция объекта обычно совпадает с его началом координат в пространстве модели, как на рис. 8.10. Это делает некоторые вычисления проще.

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

Графическое представление. Как показано на рис. 8.12, мы все так же используем два треугольника, чтобы создать один прямоугольник для Боба, и переносим его изображение на прямоугольник. Прямоугольник определяется в пространстве модели, однако он необязательно равен ограничивающей фигуре, как показано на рис. 8.10. Графический прямоугольник Боба, который мы посылаем в OpenGL ES, немного больше, чем его ограничивающий прямоугольник.

Такое разделение атрибутов позволяет нам снова применить паттерн Модель – вид – контроллер (MVC).

Со стороны модели у нас есть физические атрибуты Боба, включающие его позицию, масштаб, вращение, скорость, ускорение и ограничивающую фигуру. Позиция, масштаб и ориентация Боба определяют, где его ограничивающая фигура располагается в мире.

Вид принимает графическое представление Боба (например, два текстурных треугольника, определенных в пространстве модели) и отображает их на соответствующих позициях в игровом мире, в зависимости от позиции, вращения и масштаба Боба. Здесь мы можем использовать матричные операции OpenGL ES, как делали ранее.

Контроллер отвечает за обновление физических атрибутов Боба в соответствии с вводимыми пользователем данными (например, нажатие клавиши Влево подвинет его влево), а также в соответствии с такими физическими силами, как ускорение свободного падения (как те, которые мы применяли к пушечному ядру в предыдущем разделе).

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

Широкая и узкая фазы определения столкновений

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

Широкая фаза. На этом этапе мы пытаемся определить, какие объекты в принципе могут столкнуться. Представьте, что есть 100 объектов, каждый из которых может столкнуться с остальными. Если мы решим упрощенно проверить каждую возможную пару объектов, нам придется провести 100 х 100 / 2 проверок на пересечение. Этот метод тестирования на пересечение имеет асимптотическую сложность 0(п2); это означает, что потребуется п2 шагов для завершения теста (на самом деле мы закончим, выполнив лишь половину операций, но асимптотическая сложность не учитывает константы). При использовании более умного алгоритма для широкой фазы мы пытаемся определить, какие пары объектов имеют вероятные шансы на столкновение. Другие пары (например, два объекта, которые расположены слишком далеко друг от друга, чтобы столкнуться), не будут проверяться. Таким образом мы сможем уменьшить вычислительную нагрузку на этом этапе, так как в узкой фазе тестирование требует больше затрат.

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

 

Узкая фаза

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

Столкновение кругов. Ограничивающие круги – наименее сложный инструмент для проверки столкновений. Определим простой класс Circle (листинг 8.4).

Листинг 8.4. Circle.java, простой класс Circle

Мы сохраняем центр как Vector2 и радиус как обычное число с плавающей точкой. Как проверить, перекрывают ли два круга друг друга? Смотрим на рис. 8.13.

Рис. 8.13. Два круга, перекрывающие друг друга, и два круга, не перекрывающие друг друга

Это действительно просто и удобно в плане вычислений. Нам нужно выяснить расстояние между двумя центрами. Если расстояние больше, чем сумма двух радиусов, круги не пересекаются. В коде это будет выглядеть так:

Сначала измеряем расстояние между центрами, а потом узнаем, превышает это расстояние сумму радиусов или равно ему.

Нам придется извлечь квадратный корень в методе Vector2. di st . Это не очень хорошо, поскольку извлечение квадратного корня – затратная операция. Можем ли мы сделать это быстрее? Можем – достаточно только переформулировать наши условия:

Мы можем избавиться от квадратного корня, возведя в степень обе части неравенства, из чего получится:

Мы заменяем квадратный корень дополнительными сложением и умножением в правой части.

Так уже лучше. Создадим функцию Vector2.distSquared, которая вернет нам возведенное в квадрат расстояние между двумя векторами:

Тогда метод over. apCircles  будет таким:

Столкновение прямоугольников. Займемся прямоугольниками. Для начала нам понадобится класс, который будет представлять прямоугольник. Ранее мы уже упоминали, что собираемся определять прямоугольник его нижним левым углом, шириной и длиной. Сделаем это, как в листинге 8.5.

Листинг 8.5. Rectangle.Java, класс Rectangle

Мы сохраняем координаты нижнего левого угла как Vector2, а ширину и длину как два числа с плавающей точкой. Как проверить, перекрываются ли два прямоугольника? Представление об этом можно получить на рис. 8.14.

Рис. 8.14. Перекрывающиеся и неперекрывающиеся прямоугольники

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

Проверка на пересечение для прямоугольников на первый взгляд кажется сложной. Однако немного логики – и мы можем получить довольно простой тест. Вот самый простой метод проверки на пересечение между двумя прямоугольниками:

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

Столкновение круга и прямоугольника. Можем ли мы проверить наличие столкновения между кругом и прямоугольником? Да, можем, однако это будет сложнее. Рассмотрим рис. 8.15.

Рис. 8.15. Проверка на пересечение круга и прямоугольника путем нахождения самой близкой к кругу точки на/в прямоугольнике

Общая концепция проверки на пересечение круга и прямоугольника выглядит примерно так.

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

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

Если точка, определяемая ближайшими х- и у-координатами, находится в пределах круга, круг и прямоугольник пересекаются. Хотя этот метод не изображен на рис. 8.15, он также работает для кругов, полностью содержащих прямоугольник. Отобразим метод в коде:

Описание выглядело страшнее, чем исполнение. Мы определяем ближайшую точку прямоугольника относительно круга, а потом просто проверяем, находится ли точка внутри круга. Если это так, то круг и прямоугольник пересекаются. Обратите внимание, что я добавил перегруженный метод distSquared к Vector2, который берет две переменные float вместо еще одного Vector2. Я сделал то же самое для функции diSt О.

Все вместе

Проверка, лежит ли точка внутри круга или прямоугольника, тоже может быть полезной. Закодируем еще два метода и отправим в класс под названием Overl apTester вместе с тремя другими методами, которые мы уже определили (листинг 8.6).

Листинг 8.6. OverlapTester.java: проверка на пересечение кругов, прямоугольников и точек

Прекрасно, теперь у нас есть полностью функциональная математическая 2D-библиотека, которую мы можем использовать для всех наших маленьких физических моделей и определения столкновений. Теперь более подробно обсудим широкую фазу.

Широкая фаза

Как же нам получить от широкой фазы максимум пользы? Посмотрите на рис. 8.16, на котором показана типичная сцена из Супер Марио.

Рис. 8.16. Супер Марио и его враги; рамки вокруг объектов – ограничивающие прямоугольники; большие прямоугольники создают сетку, наложенную на картинку

Догадываетесь, что мы можем сделать, чтобы избежать некоторых проверок? Сетка на рис. 8.16 представляет собой ячейки, на которые мы делим наш игровой мир. Каждая ячейка имеет один и тот же размер; ячейки покрывают весь мир. Марио в данный момент в двух из этих ячеек. Другие объекты, с которыми Марио может столкнуться, находятся в других ячейках. Таким образом, нам не нужно проводить никаких проверок столкновения, поскольку Марио не может находиться в тех же ячейках, что и другие объекты в кадре. Необходимо сделать следующее:

Обновить все объекты мира на основе применяемой физики и управления.

Обновить позицию каждой ограничивающей фигуры каждого объекта согласно с позицией объекта. Конечно, мы также можем включить сюда и обновление ориентации и масштаба.

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

Проверить на столкновения, но только те пары объектов, которые могут столкнуться (например, Гумбы не могут столкнуться с другими Гумбами) и которые находятся в одной ячейке. На этом этапе широкой фазы применяется пространственная сетка (spatial hash grid), реализация этого этапа не составляет труда. Первое, что нам необходимо определить, – размер каждой ячейки. Он во многом зависит от масштаба и компонентов, которые мы используем в игровом мире.

Усложненный пример

Продолжим рассматривать широкую фазу с пространственной сеткой на нашем последнем примере с пушечным ядром. Мы полностью переделаем этот пример, включив все, о чем шла речь в этом разделе. Кроме пушки и ядра у нас должны быть мишени для стрельбы. Не будем усложнять себе жизнь и используем в качестве мишеней квадраты размером 0,5 х 0,5 м. Эти квадраты статичны и не двигаются. Наша пушка также статична. Единственное, что двигается, – это, собственно, само ядро. В целом мы можем разделить объекты в нашей игре на статичные (неподвижные) и динамичные (подвижные). Создадим класс для представления таких объектов.

                                                                

Источник: Mario Zechner / Марио Цехнер, «Программирование игр под Android», пер. Егор Сидорович, Евгений Зазноба, Издательство «Питер»

По теме:

  • Комментарии