Урок рассматривает сеточную структуру (grid-based system) для карты, состоящей из тайлов (tiles). Реализуется широкая фаза опредления столкновений — когда нужно найти все объекты, для которых нужно произвести точную проверку столкновений в узкой фазе алгоритма.
Авторы: Raigan Burns, Mare Sheppard
Перевод: Nox Noctis
1. краткий обзор
2. базовая сетка и тайлы
3. усовершенствование сетки
4. сетка с динамическими объектами
5. трассировка лучей
6. выводы / исходник
+. примечания, ссылки по теме
назад к списку уроков N
1. Краткий обзор
В предыдущем уроке рассматривалась "узкая фаза" определения столкновения в игре N и решение задачи выведения объекта (окружности или AABB) из столкнования с тайлом (стационарной фигурой на игровом поле) методом проецирования на разделяющие оси.
Данный урок рассматривает "широкую фазу" определения столкновений: решается задача выбора тех тайлов, которые необходимо будет проверить в "узкой фазе" алгоритма. В игре N мы разбили всю игровую карту на равномерную сетку (grid) с квадратными ячейками; вместо того, чтобы проверять столкновение объекта со всеми тайлами (tiles) на карте, мы проверяем столкновения только с теми тайлами, которые содержатся в соседних от объекта клетках.
У такого подхода есть свои сложности, например, то, что все движущиеся объекты должны быть меньше ячейки сетки; это ограничение можно обойти, представляя большие объекты, как сочетание нескольких объектов поменьше, но при написании алгоритма на ActionScript, всё же лучше отказываться от усложнения задачи из соображений производительности. В нашей игре мы умышленно оставили это ограничение.
Использовать сеточные карты в играх удобнее всего при соблюдении двух условий — если все тайлы (кусочки, из которых собирается вся карта) примерно одинаковых габаритов и если размерность карты сравнительно небольшая; поскольку для представления карты размерности NxN требуется N2 ячеек сетки, этот метод может потребовать большого объёма памяти. Существуют сложные структуры, которые позволяют оптимизировать расход памяти и/или упростить обработку сильно отличающихся по размеру объектов. Например, деревья квадрантов (quadtrees) или сетки с изменяемым разрешением (multi-resolution grids).
в начало
2. Базовая сетка и тайлы
Основное, для чего используют сетку (tile-based grid), это хранение данных о непроходимых участках карты. Сама по себе сетка является двумерным массивом; каждый элемент массива — это объект, представляющий одну ячейку. В N каждую ячейку всегда занимает только один тайл (только одна из элементарных фигур, из которых составлена вся карта).
Прежде всего, хорошо бы уметь для данной точки определять в какой ячейки сетки она находится. Это несложно:
grid_column = Math.floor(pos.x / cell_width); grid_row = Math.floor(pos.y / cell_height);Теперь мы можем без труда определить, в какой ячейке находится центр нашего объекта; эту ячейку мы называем "текущей ячейкой объекта". Поскольку мы ограничили размер движущегося объекта размерами одной ячейки сетки, мы точно знаем, что объект одновременно может касаться не более 4 ячеек.
Пример 1: ячейки сетки, которых касается объект.
Прямоугольный объект может пересекаться с текущей ячейкой, с одной соседней ячейкой по горизонали, с одной соседней ячейкой по вертикали и с одной ячейкой по диагонали; диагональная ячейка при этом является соседней для вертикальной и горизонтальной. Здесь речь идет о прямоугольном объекте, поскольку для определения столкновений очень часто используется ограничивающий прямоугольник объекта (AABB). — прим. перев.
|
Легенда:
красным отмечены ячейки, которых касается объект. Комментарии: Перетаскивайте прямоугольник. Обратите внимание, если объект касается клетки слева от текущей, он не может касаться клетки справа. Аналогично для клеток сверху и снизу. |
Определить, с какими ячейками пересекается прямоугольный объект можно несколькими способами:
- можно просто проверить, в каких клетках находятся все 4 вершины прямоугольника
- можно определить, в какой клетке находится центр прямоугольника, а затем узнать индексы остальных клеток, используя сдвиг относительно индекса центральной клетки. То есть, зная, что объект всегда меньше одной клетки, достаточно узнать индекс [i][j] клетки, в которой находится его центр, и после этого проверить клетки с индексами [i-1][j], [i][j+1], [i-1][j+1].
Есть и более простой способ — можно "обернуть" сетку по периметру "непроходимыми" для объектов клетками, не позволяя им таким образом выходить за её пределы.
Определение столкновений с тайлами на карте при помощи сетки
Теперь, когда мы знаем, какие 4 ячейки сетки пересекает объект, необходимо определить столкновение объекта с тайлами, содержащимися в этих ячейках. Сам процесс определения столкновений между разными фигурами описан в предыдущей статье.
Каждая из ячеек сетки хранит информацию о тайле, который в этой ячейке содержится (напомним, в одной ячейке всегда содержится не больше одного тайла — это типичное ограничение при задании сетки, которое мы использовали). Информация о тайле включает в себя его тип, и все параметры, необходимые процедурам, определяющим столкновения с фигурами данного типа (например, x-вектор полуширины, центральная точка, нормаль к поверхности).
Для реализации такой сетки можно, к примеру, создать специальный тип объектов; каждый из объектов-представителей этого типа будет сам отвечать за определение столкновения между тайлом и динамическим объектом:
tile.Collide_Circle(myCircle);Или же можно использовать более простой известный подход: сделать и тайл и динамический объект всего лишь контейнерами каких-то описательных данных, а ссылки на функции определения столкновений хранить в двумерном хэше; тип тайла при этом используется как ключ для получения соответствующей функции из хэша:
Collide[tile.shape][myObj.shape](tile, myObj);
в начало
3. Усовершенствование сетки
Теперь, когда мы задали простую сетку для определения столкновений динамического объекта с тайлами карты, стоит подумать о том, как сделать вычисления более эффективными.
Первое, что можно сделать, это записать в каждый из объектов сетки ссылки на объекты четырёх соседних клеток. Таким образом, определив центральную клетку, мы сможем обращаться к соседним клеткам, используя свойства, а не обращения по индексам в массиве; это приведет к уменьшению количества вычислений при обращениях к соседям клетки, но увеличит расход памяти для хранения объектов-ячеек. Поскольку выигрыш в производительности, получаемый таким образом, в большинстве программных оболочек ничтожно мал, этот приём оптимизации не всегда достоин внимания.
В игре N мы всё же использовали ссылки на соседние ячейки следующим образом:
cell.nR // ячейка справа cell.nL // слева cell.nU // сверху cell.nD // снизу
Информация о сторонах ячеек сетки
Одно существенное усовершенствование к нашей сетке — сохранять в объекте-ячейке не только информацию о тайле, но и о её сторонах. Эта идея была позаимствована из статьи Тома Форсайта, входящей в сборник Game Programming Gems 3. В этой статье упоминалось, что игра X-Com использовала похожий приём.
Информация, которую нужно хранить о каждой из сторон — минимальна; это одна переменная, которая описывает состояние стороны:
- empty (пустая): в обеих ячейках, которые эта сторона разделяет, нет тайлов.
- solid (сплошная): грань по крайней мере одного из тайлов, полностью прилегает к стороне (речь, конечно, о тайлах, которые находятся в разделяемых стороной ячейках).
- interesting (пересекающая): по крайней мере одна из ячеек, которые эта сторона разделяет, содержит тайл, но тайл(ы) не прилегают к стороне полностью.
Рис. 1: 9 фигур-тайлов, используемых в N, и стороны ячеек,
в которых они содержатся.
Сплошные стороны обозначены красным, а пересекающие стороны — серым.
Эта информация о сторонах ячейки позволяет существенно упростить определение столкновений; если объект пересекается со сплошной стороной (что в играх, использующих сетку с тайлами, случается чаще всего), мы можем просто вывести его из столкновения методом проекций, вместо того, чтобы прибегать к более сложным вариантам определения столкновений между объектом и тайлом. Поскольку стороны ячеек, отмеченные как "сплошные" (solid) совпадают с гранями тайлов, мы можем обрабатывать случаи столкновений с ними так, как будто мы использовали полную процедуру определения столкновения с тайлами. Использовать полную процедуру определения столкновения с тайлом следует только в случае столкновения с "пересекающей" стороной.
в которых они содержатся.
Сплошные стороны обозначены красным, а пересекающие стороны — серым.
Такая информация о сторонах ячеек служит грубым приближением поверхности карты, состоящей из тайлов; это зачастую