задача: организовать "широкую фазу" определения столкновений в играх во флэше.

Урок рассматривает сеточную структуру (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 (пересекающая): по крайней мере одна из ячеек, которые эта сторона разделяет, содержит тайл, но тайл(ы) не прилегают к стороне полностью.
После задания состояний сторон ячеек, схему можно немного упростить: любую сторону, которая имеет статус solid (сплошная) в обеих ячейках, можно считать пустой (empty). Это не повлияет на правильность определения столкновений, поскольку такое сочетание возможно только внутри монолитных блоков на карте, а столкновения динамических объектой нужно проверять с поверхностью игрового мира.
Рис. 1: 9 фигур-тайлов, используемых в N, и стороны ячеек,
в которых они содержатся.

9 фигур-тайлов, используемых в N, и стороны ячеек, в которых они содержатся. Сплошные стороны обозначены красным, а пересекающие стороны — серым.

Сплошные стороны обозначены красным, а пересекающие стороны — серым.
Эта информация о сторонах ячейки позволяет существенно упростить определение столкновений; если объект пересекается со сплошной стороной (что в играх, использующих сетку с тайлами, случается чаще всего), мы можем просто вывести его из столкновения методом проекций, вместо того, чтобы прибегать к более сложным вариантам определения столкновений между объектом и тайлом. Поскольку стороны ячеек, отмеченные как "сплошные" (solid) совпадают с гранями тайлов, мы можем обрабатывать случаи столкновений с ними так, как будто мы использовали полную процедуру определения столкновения с тайлами. Использовать полную процедуру определения столкновения с тайлом следует только в случае столкновения с "пересекающей" стороной.

Такая информация о сторонах ячеек служит грубым приближением поверхности карты, состоящей из тайлов; это зачастую полезно, поскольку карта тайлов сама по себе не содержит никакой информации об общей поверхности игрового мира, а эта информация может понадобится, например, для того, чтобы задать движение противников по поверхности.
Рис. 2: пример карты, содержащей монолитные участки тайлов
с обозначенными состояниями сторон ячеек.

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

Сплошные стороны обозначены красным, а пересекающие стороны — серым. Обратите внимание, непустые стороны ячеек образуют периметры монолитных тайловых блоков. Эти периметры являются грубым приближением поверхности карты.
В игре N было легко реализовать двери за счет изменения состояний сторон ячейки с дверью. Это полезный побочный эффект использования состояний сторон ячеек. Более того, в реализации AI (искусственного интеллекта) противников стороны ячеек были использованы в алгоритме нахождения пути; это позволяет противникам взаимодействовать с дверьми и следовать по поверхности карты. Наши алгоритмы трассировки луча тоже используют информацию о сторонах ячеек для оптимизации вычислений.

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

4. Сетка с динамическими объектами

Сетка может одновременно служить и хранилищем сведений о динамических объектах на карте.

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

Существует два основных подхода при использовании сетки с динамическими объектами:

"нормальная" сетка: ссылка на динамический объект записывается в каждую из ячеек, которой он касается. В нашем случае таких ячеек будет от 1 до 4. При каждом перемещении объекта ссылка на него удаляется из ячеек, которых он перестал касаться и записывается в те ячейки, коотрых он касается в своей новой позиции. Всякий раз, когда нам необходимо определить столкновения объекта, мы проверяем только содержимое тех ячеек, которых объект в данный момент касается.
  • плюсы: при определении столкновений необходимо проверить содержимое максимум 4 ячеек, которых он касается.
  • минусы: объект необходимо добавлять/удалять в списки объектов 4 ячеек в худшем случае; вдобавок к этому, необходимо учитывать случай, когда два объекта касаются одних и тех же ячеек. Поскольку для каждой пары объектов столкновение нужно проверить единожды, нужен дополнительный флаг, который будет означать, что столкновение данных двух объектов уже определялось.
"рыхлая" сетка: каждый объект содержится только в одной ячейке — в той, которая содержит его центр. Когда объект двигается, ссылка на него удаляется из этой (единственной) ячейки и вставляется в список той ячейки, которая содержит его центр в новой позиции. При определении столкновений необходимо проверить не только содержимой текущей ячейки объекта, но и содержимое 8 клеток, окружающих текущую. Идея "рыхлой" сетки может казаться немного странной, до тех пор пока вы не рассмотрите её практическое использование. Более подробно этот вариант описан здесь.
  • плюсы: каждый объект при движении добавляется/удаляется всего в список всего 1 ячейки.
  • минусы: при определении столкновений приходится проверять содержимое 9 клеток для каждого объекта.
В игре N мы выбрали рыхлую сетку, из-за простоты перемещения в ней объектов; однако, большинство идей, изложенных в этом уроке, подойдет для любого типа сетки.

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

В нашей реализации у каждой ячейки есть следующие свойства: 
.next // ссылка на начало списка
.prev // всегда null, поскольку .next — начало списка
У каждого динамического объекта: 
.cell // ссылка на текущую ячейку
.prev // ссылка на предыдущий объект в списке объектов ячейки .cell
.next // ссылка на следующий объект в списке объектов ячейки .cell
Всякий раз, когда объект перемещается, его расположение внутри сетки обновляется в списках соответствующих ячеек.

Подробнее о широкой фазе определения столкновений

Существует два основных подхода к реализации широкой фазы определения столкновений. Первый — позволить каждому движущемуся объекту самостоятельно собирать данные из сетки и вызывать функции определения столкновений. Второй — создать объект-менеджер, который будет определять все столкновения для всех движущихся объектов и вызывать соответствущие действия с ними.

В игре N мы использовали первый вариант, в его наиболее простом виде: только персонаж при движении опрашивает ячейки карты на столкновения и все остальные объекты получают результаты этого опроса. Это хороший вариант с точки зрения производительности, однако он ограничичивает дизайн игры в целом. Например, противники не реагируют друг на друга (как в Super Mario Bros., где противники после столкновения друг с другом изменяют направлене движения).

Итак, в каждом кадре наш персонаж проверяет содержимое своей текущей ячейки и содержимое 8 окружающих клеток; проверяются столкновения со всеми найденными объектами.

Более общий и элегантный способ, который лучше подходит для симуляции среды, в которой все объекты должны сталкиваться друг с другом, заключается в том, чтобы на каждом шаге перебирать все движущиеся объекты и порверять их столкновения:
  • со всеми объектами, предшествующими данному объеку в списке объектов текущей ячейки
  • со всеми объектами, находящимися в 4 соседних ячейках. При этом вы можете выбрать любой набор из 4 соседних клеток, которые примыкают друг к другу. Например, [правая, правая-нижняя, нижняя, левая-нижняя], или [верхняя, верхняя-левая, левая, левая-нижняя], и т. п.
Может показаться, что таким образом некоторые столкновения будут упущены, но если вы попробуете проверить этот метод на бумаге, вы убедитесь, что все возможные столкновения объектов будут найдены. Это позволяет сократить число проверяемых клеток с 9 до 5 для каждого движущегося объекта, не прибегая при этом к флагам или другим неуклюжим решениям.

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

Это означает, что пули не нужно перемещать по сетке — достаточно того, что они при движении определяют столкновения с окружающими объектами. Это экономит массу действий по удалению/добавлению объектов-пуль в связные списки клеток; при этом в игре теряется всего одна возможность — вы не можете останавливать своими пулями пули противника.
в начало

5. Трассировка лучей

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

Хороший пример такой задачи — трассировка луча; луч — это просто прямая линия, ограниченная с одной стороны точкой. Лучи обычно используются для определения того, могут ли объекты друг друга "видеть", или для моделирования быстро движущихся снарядов: в Quake, например, railgun моделируется лучом, начинающимся от игрока и идущим в сторону цели.

Основное, что нам нужно знать о луче — первое препятствие, которое он встретит (под "первым" понимается точка пересечения с препятствием ближайшая к основанию луча); или же, по данным двум точкам часто необходимо узнать, пересекает ли отрезок между этими точками какое-либо препятствие.

В игре N мы использовали трассировку лучей для AI тех противников, которые могут "видеть" персонажа, а также для моделлирования некоторых видов оружия. Определения столкновений луча реализуется в два (уже знакомых) шага:
  • широкая фаза: определить, через какие ячейки сетки проходит луч (и, соответственно, с какими тайлами и объектами он может пересечься).
  • узкая фаза: выполнить определение столкновений с объектами, найденными на предыдущем шаге, найти точки пересечения.
Широкая фаза

В нашей сеточной структуре широкая фаза сводится к нахождению ячеек, которых касается луч; всё, что содержится в других ячейках сетки коснуться луча точно не может. (Внимание! Строго говоря, это не всегда верно, поскольку мы используем "рыхлую" сетку для динамических объектов; подробнее см. ниже.)

Самое простое, можно взять ограничивающий прямоугольник (AABB) луча и считать, что все ячейки сетки, которые попадают в этот прямоугольник, пересекаются лучом. Для коротких лучей этого может быть достаточно, равно как и для горизонтальных/вертикальных лучей, однако для всех прочих лучей такой подход приведет к проверке столкновений в n^2 ячейках, что сильно снизит производительность.

Гораздо лучше, конечно, было бы определить каких именно ячеек касается луч; для этого существует замечательный (и довольно простой) алгоритм, описанный Амантидесом и Биккером; в общих чертах, этот алгоритм проходит луч с определенным шагом и "посещает" каждую ячейку, которой луч касается.

Для игры N, мы реализовали этот алгоритм; а в каждой клетке, которой касается луч, мы запускаем процедуры определения столкновений, о которых было рассказано в предыдущей статье.

Узкая фаза алогоритма — столкновения с тайлами

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

Если же луч встретит "пересекающую" сторону, необходимо будет запустить процедуру определения столкновений с содержимым той клетки, в которую луч вошел. В большинстве случаев мы использовали алгоритмы определения точки пересечения луча с прямой и луча с отрезком прямой. Основные наши источники по этой теме: Архив геометрических алгоритмов и книга Джозефа О'Рурка. Для круглых фигур мы адаптировали алгоритм проверки в протяженности, описанный в статье Мигеля Гомеза.

Узкая фаза алогоритма — столкновения с динамическими объектами

Одна главная проблема в использовании "рыхлой" сетки — то, что объекты, которые не находятся в клетке, через которую проходит луч, всё же могут его пересекать.
Рис. 3: ячейки сетки, которых касается луч.

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

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

6. Выводы / исходник

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

Чтобы использовать вышеописанные методы с объектами любого размера, необходимо только добавить возможность нахождения ячеек, которых касается объект, чтобы его можно было добавлять в их связные списки объектов (и желательно быстро). Для объектов, чьи размеры меньше размеров ячеек это не составит труда; но чем больше объект, тем сильнее на производительности сказывается задача добавления его в списки затронутых ячеек сетки и последующее удаление из них.

Наилучший вариант организации сетки всегда связан со спецификой конкретной игры.

Еще одно дополнение к сказанному — совершенно не обязательно использовать тайлы для реализации сеточной структуры; вы можете использовать сетку и алгоритмы определения столкновений из предыдущего урока для карты, соатоящей из фигур разного размера и разной формы — таким образом, вы избежите ограничений в дизайне игры, связанных с тайлами. Всё что вам нужно — это уметь определять набор тайлов, из которых состоит данная произвольная фигура. Далее можно использовать изложенный выше алгоритм так, как будто вы имеете дело с картой из тайлов.

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

Исходник

[ посмотреть ] [ исходник ]

Приложение содержит часть исходного кода игры N, которая относится к материалу этого урока.

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

Как с нами связаться

Если у вас есть замечания или дополнения к этому уроку, напишите нам по адресу tutorials@harveycartel.org

УБЕДИТЕЛЬНАЯ ПРОСЬБА, не писать нам письма с вопросами об исходном коде — с этим вам придётся разобраться самостоятельно.

На нашем форуме есть специальный раздел об уроках.
в начало

+. Примечания, ссылки по теме

Ниже приводятся ссылки на весьма полезные материалы на английском языке. Если вы знаете, где можно найти аналогичные материалы на русском языке — напишите мне. — прим. перев.
в начало
назад к списку уроков N