Главная » Программирование игр под Android » Пространственная сетка – РАЗРАБОТКА ИГР ДЛЯ ОС ANDROID

0

Наша пушка будет ограничена прямоугольником размером 1 х 1 м; ограничивающий прямоугольник пушечного ядра будет размером 0,2 х 0,2 м, а у мишеней будут ограничивающие прямоугольники по 0,5 х 0,5 м каждый. Чтобы все стало немного проще, ограничивающие прямоугольники центрированы относительно позиции каждого объекта.

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

Константы WORLDWIDTH и WORLDHEIGHT определяют размеры игрового мира. Все действия должны происходить в прямоугольнике, описанном координатами (0; 0) и (W0RLD WIDTH, WORLDHEIGHT). На рис. 8.17 показан небольшой макет нашего игрового мира.

Рис. 8.17. Макет нашего игрового мира

Так наш мир будет выглядеть позже, но пока наложим на него пространственную сетку. Насколько большими должны быть ячейки пространственной сетки? Здесь нет однозначного ответа, но я обычно выбираю такой размер, чтобы ячейка была в пять раз больше самого большого объекта в кадре. В нашем примере самый большой объект – это пушка, но с пушкой мы ничего не сталкиваем. Поэтому лучше определить размер ячейки сетки в соответствии со следующими по величине объектами – мишенями. Мишени у нас размером 0,5 х 0,5 м. Тогда ячейка сетки должна иметь размер 2,5 х 2,5 м. На рис. 8.18 показана сетка, наложенная на наш мир.

Рис. 8.18. Наш игровой мир, на который наложена пространственная сетка из 12 ячеек

У нас есть определенное количество ячеек – в случае с этим пушечным миром их 12. Мы присваиваем каждой ячейке уникальный номер, начиная с нижней левой, которая получает ID 0. Обратите внимание, что верхние ячейки выходят за пределы нашего мира. Это не проблема; стоит только убедиться, что все объекты нашего мира находятся в его пределах. Мы хотим определить, к какой ячейке или ячейкам принадлежит объект. В идеале мы хотим вычислить ID ячеек, в которых содержится объект. Это позволяет нам использовать простую структуру данных для хранения ячеек:

Да, именно, мы описываем каждую ячейку как список классов GameObject. Сама пространственная сетка, таким образом, представляет собой массив списков классов GameObject.

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

Чтобы вычислить ID ячейки для объекта, мы можем взять точки в углах его ограничивающего прямоугольника и проверить, в какой ячейке находится каждая точка. Определить ячейку, в которой находится точка, просто: нужно разделить ее координаты на ширину ячейки в первую очередь. Например, у нас есть точка с координатами (3; 4) и ячейка размером 2,5 х 2,5 м. Точка будет находиться в ячейке с ID 5 на рис. 8.18.

Мы можем разделить каждую координату точки на размер ячейки, чтобы получить целочисленные 20-координаты, как здесь:

И из этих координат ячейки мы можем просто получить ID ячейки:

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

Можно вычислить, сколько ячеек приходится на столбец, вот так:

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

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

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

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

Листинг 8.10. Фрагмент класса SpatialHashGrid.Java: реализация пространственно сетки

Как уже обсуждалось, мы сохраняем два списка ячеек: один – для динамических объектов, второй – для статических. Мы также храним количество ячеек в ряду и столбце, чтобы позже иметь возможность проверить, находится ли точка, которую мы проверяем, внутри или за пределами нашего мира. Размер ячейки также следует сохранить. Массив eel 1 sds – это рабочий массив, который мы используем для временного хранения ID четырех ячеек, в которых содержится GameObject. Если он находится только в одной ячейке, то только первому элементу массива будет присвоен ID ячейки, которая полностью содержит объект. Если объект располагается в двух ячейках, первые два элемента массива будут содержать ID ячеек и т. д. Чтобы обозначить количество ID ячеек, мы присвоим всем пустым элементам массива значение -1. Список foundObjects также рабочий, который мы будем возвращать по вызову getPotentialColliders. Зачем держать эти два элемента, если можно создавать новый массив и список каждый раз, когда будет требоваться? Вспомните нашего старого знакомого – страшного сборщика мусора.

Конструктор этого класса берет размер мира и желаемый размер ячейки. По данным параметрам мы вычисляем, сколько ячеек нам надо, и заполняем массивы ячеек и списки, содержащие объекты, находящиеся в каждой ячейке. Мы также инициализируем список foundObjects. Все созданные нами списки ArrayList будут иметь исходный размер в 10 GameObject. Мы предполагаем, что вероятность нахождения 10 GameObject в одной ячейке очень мала. Пока это так, массивы не требуют изменения в размерах.

Далее следуют методы insertStaticOb ject  и insertDynamicObject. Они вычисляют ID ячеек, в которых содержится объект, путем вызова getCel 1 Ids  и вставляют объект в подходящие списки. Метод getCel 1 Ids  будет заполнять массив переменных eel 1 Ids.

Нам также потребуется метод removeObjectO, который мы используем для выяснения, в каких ячейках содержится объект, и затем для удаления его из списков динамических и статических объектов соответственно. Это понадобится, например, если игровой объект умирает.

Метод clearDynami cCels  будет использоваться для очистки всех списков динамических объектов. Нам нужно будет вызывать этот метод перед каждым кадром, прежде чем мы будем заново вставлять динамические объекты, что уже обсуждалось ранее.

И наконец, есть еще метод getPotenti а 1 Col 1 i ders . Он берет объект и возвращает список соседних от него объектов, которые содержатся в тех же ячейках, что и этот объект. Мы будем использовать рабочий список foundObjects для хранения списка найденных объектов. Опять же, мы не хотим создавать новый список каждый раз, когда вызываем этот метод. Все, что нам надо выяснить, – это в каких ячейках находится объект, переданный в метод. Затем мы просто добавляем все статические и динамические объекты, найденные в этих ячейках, в список foundObjects и убеждаемся, что в нем нет дубликатов. Применять foundObjects. contai ns  для проверки на дубликаты, конечно, не совсем оптимально. Но поскольку количество найденных объектов в данном случае никогда не будет большим, он вполне приемлем. Если у вас возникнут проблемы при реализации, это первое, что стоит оптимизировать. К сожалению, это не так и просто. Конечно, мы можем задействовать Set, но тогда новые объекты будут создаваться внутри каждый раз, когда мы будем добавлять объект в Set. Пока оставим все как есть, запомнив, к чему вернуться в случае чего.

Я не упомянул метод Spatial HashGrid.getCel 1 Ids . В листинге 8.11 показан код. Не бойтесь, он не такой страшный, каким кажется на первый взгляд.

Листинг 8.11. Остаток файла SpatialHashGrid.Java: реализация getCellldsO

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

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

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

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

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

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

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

Все вместе

Применим все знания, приобретенные в этом разделе, на маленьком хорошем примере. Разовьем пример с пушкой, который мы обсуждали несколько страниц назад. Используем объект Cannon для пушки, объект Dynami cGameOb ject для пушечного ядра и несколько объектов GameObject для мишеней. Каждая мишень будет иметь размеры 0,5 х 0,5 м, и они будут расположены в мире в произвольном порядке.

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

Поскольку этот пример уже достаточно большой, разделим его на несколько листингов. Назовем тест Colli si onTest и соответствующий экран Colli si onScreen. Как обычно, мы смотрим только на экран. Начнем с элементов теста и конструктора в листинге 8.12.

Листинг 8.12. Фрагмент Colli sionTest.Java: элементы и конструктор

Мы многое заимствовали из CannonGravityScreen. Начинаем с определения нескольких констант, указывая количество мишеней и размеры мира. Далее идет экземпляр класса GLGraphics и объекты для пушки, ядра и мишеней, которые мы помещаем в список. Есть также Spati а 1 HashGri d, конечно. Для визуализации мира нам понадобится несколько сеток: одна для пушки, одна для ядра и одну мы будем использовать для отображения каждого объекта. Вспомните, что в BobTest мы применяли только одну треугольную сетку для визуализации на экране ста Бобов. Мы задействуем этот принцип и здесь вместо того, чтобы заводить по экземпляру Verti ces для каждой мишени. Последние два члена класса те же, что и в CannonGravityTest. Мы используем их, чтобы стрелять ядром и применять законы гравитации, когда пользователь дотрагивается до экрана.

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

Рассмотрим следующий метод в классе Col1isi onTest (листинг 8.13).

Листинг 8.13. Фрагмент Col1isi onTest. java: метод updated

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

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

Последняя часть метода – код определения столкновений. Нам нужно найти в пространственной сетке мишени, которые находятся в тех же ячейках, что и ядро. Для этого используем метод SpatialHashGrid.getPotentialCol 1 idersC. Поскольку ячейки, в которых находится ядро, рассчитываются прямо в методе, нет необходимости вставлять ядро в сетку. Далее проходим в цикле по всем объектам, с которыми возможно столкновение, и проверяем, есть ли действительно пересечение ограничивающего прямоугольника ядра с ограничивающим прямоугольником объекта, с которым возможно столкновение. Если есть, мы просто удаляем эту мишень из списка мишеней. Помните, что мы добавили мишени в сетку только как статические объекты.

И все это и есть законченный механизм нашей игры. Последний кусок головоломки, по сути, и есть сам этап визуализации, который вряд ли вас чем-то удивит (листинг 8.14).

Листинг 8.14. Фрагмент Colli sionTest.java: метод present

Здесь нет ничего нового. Как и всегда, мы определяем проекционную матрицу и область просмотра и сначала очищаем экран. Далее отображаем все мишени, вновь используя прямоугольную модель, сохраненную в targetVertices. Это, по существу, то же, что мы делали в BobTest, но на этот раз мы отображаем мишени. Далее отображаем ядро и пушку, как мы делали в Coll isionGravityTest.

Я изменил порядок расположения изображений, чтобы ядро всегда было над мишенями, а пушка всегда была над ядром. Я также сделал мишени зелеными, вызвав glColor4f.

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

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

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

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

По теме:

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