Урок рассматривает сеточную структуру (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) совпадают с гранями тайлов, мы можем обрабатывать случаи столкновений с ними так, как будто мы использовали полную процедуру определения столкновения с тайлами. Использовать полную процедуру определения столкновения с тайлом следует только в случае столкновения с "пересекающей" стороной.
в которых они содержатся.

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

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

Сплошные стороны обозначены красным, а пересекающие стороны — серым. Обратите внимание, непустые стороны ячеек образуют периметры монолитных тайловых блоков. Эти периметры являются грубым приближением поверхности карты.
К сожалению, состояние каждой стоорны ячейки определяется не только состоянием самой ячейки, но и состоянием её соседа; наш алгоритм автоматического определения состояний сторон ячеек был очень сложен и подвержен ошибкам, поскольку приходилось учитывать все возможные сочетания двух ячеек. Вероятно, существует более простй способ задавать состояния ячеек; пожалуйста, сообщите нам, если вы знаете какой-нибудь алгоритм, решающий эту проблему.
в начало
4. Сетка с динамическими объектами
Сетка может одновременно служить и хранилищем сведений о динамических объектах на карте.
Ячейка помимо сведений о содержащемся в ней тайле может содержать и информацию о динамическом объекте, который в данный момент в ней находется. В таком случае каждая ячейка содержит список динамических объектов; по мере того, как динамический объект двигается по сетке, мы добавляем его в список ячейки, в которую он переходит и удаляем из списка той ячейки, в которой он был до этого.
Существует два основных подхода при использовании сетки с динамическими объектами:
"нормальная" сетка: ссылка на динамический объект записывается в каждую из ячеек, которой он касается. В нашем случае таких ячеек будет от 1 до 4. При каждом перемещении объекта ссылка на него удаляется из ячеек, которых он перестал касаться и записывается в те ячейки, коотрых он касается в своей новой позиции. Всякий раз, когда нам необходимо определить столкновения объекта, мы проверяем только содержимое тех ячеек, которых объект в данный момент касается.
- плюсы: при определении столкновений необходимо проверить содержимое максимум 4 ячеек, которых он касается.
- минусы: объект необходимо добавлять/удалять в списки объектов 4 ячеек в худшем случае; вдобавок к этому, необходимо учитывать случай, когда два объекта касаются одних и тех же ячеек. Поскольку для каждой пары объектов столкновение нужно проверить единожды, нужен дополнительный флаг, который будет означать, что столкновение данных двух объектов уже определялось.
- плюсы: каждый объект при движении добавляется/удаляется всего в список всего 1 ячейки.
- минусы: при определении столкновений приходится проверять содержимое 9 клеток для каждого объекта.
Каждая ячейка в нашей сетке содержит двусвязный список ссылок на динамические объекты; в этот список добавляются ссылки тех объектов, чей центр содержится внутри ячейки. (Если вам незнакомо понятие "связные списки" — гугл вам обязательно поможет.)
В нашей реализации у каждой ячейки есть следующие свойства:
.next // ссылка на начало списка .prev // всегда null, поскольку .next — начало спискаУ каждого динамического объекта:
.cell // ссылка на текущую ячейку .prev // ссылка на предыдущий объект в списке объектов ячейки .cell .next // ссылка на следующий объект в списке объектов ячейки .cellВсякий раз, когда объект перемещается, его расположение внутри сетки обновляется в списках соответствующих ячеек.
Подробнее о широкой фазе определения столкновений
Существует два основных подхода к реализации широкой фазы определения столкновений. Первый — позволить каждому движущемуся объекту самостоятельно собирать данные из сетки и вызывать функции определения столкновений. Второй — создать объект-менеджер, который будет определять все столкновения для всех движущихся объектов и вызывать соответствущие действия с ними.
В игре N мы использовали первый вариант, в его наиболее простом виде: только персонаж при движении опрашивает ячейки карты на столкновения и все остальные объекты получают результаты этого опроса. Это хороший вариант с точки зрения производительности, однако он ограничичивает дизайн игры в целом. Например, противники не реагируют друг на друга (как в Super Mario Bros., где противники после столкновения друг с другом изменяют направлене движения).
Итак, в каждом кадре наш персонаж проверяет содержимое своей текущей ячейки и содержимое 8 окружающих клеток; проверяются столкновения со всеми найденными объектами.
Более общий и элегантный способ, который лучше подходит для симуляции среды, в которой все объекты должны сталкиваться друг с другом, заключается в том, чтобы на каждом шаге перебирать все движущиеся объекты и порверять их столкновения:
- со всеми объектами, предшествующими данному объеку в списке объектов текущей ячейки
- со всеми объектами, находящимися в 4 соседних ячейках. При этом вы можете выбрать любой набор из 4 соседних клеток, которые примыкают друг к другу. Например, [правая, правая-нижняя, нижняя, левая-нижняя], или [верхняя, верхняя-левая, левая, левая-нижняя], и т. п.
Определение столкновений в каждой игре очень зависит от специфики игрового дизайна; обычно можно достигнуть существенного повышения производительности, задав разумные правила поведения для объектов в вашем игровом мире. Например, в такой игре как Soldat, где движущихся объектов очень много, причем большая их часть — это пули, очень правильным решением будет отказаться от столкновений пуль друг с другом.
Это означает, что пули не нужно перемещать по сетке — достаточно того, что они при движении определяют столкновения с окружающими объектами. Это экономит массу действий по удалению/добавлению объектов-пуль в связные списки клеток; при этом в игре теряется всего одна возможность — вы не можете останавливать своими пулями пули противника.
в начало
5. Трассировка лучей
Кроме проецирования/определения столкновений в играх также часто встречается другой тип задач, которые связаны с тем, что объектам нужно узнавать состояние окружающего мира для осуществления различных действий.
Хороший пример такой задачи — трассировка луча; луч — это просто прямая линия, ограниченная с одной стороны точкой. Лучи обычно используются для определения того, могут ли объекты друг друга "видеть", или для моделирования быстро движущихся снарядов: в Quake, например, railgun моделируется лучом, начинающимся от игрока и идущим в сторону цели.
Основное, что нам нужно знать о луче — первое препятствие, которое он встретит (под "первым" понимается точка пересечения с препятствием ближайшая к основанию луча); или же, по данным двум точкам часто необходимо узнать, пересекает ли отрезок между этими точками какое-либо препятствие.
В игре N мы использовали трассировку лучей для AI тех противников, которые могут "видеть" персонажа, а также для моделлирования некоторых видов оружия. Определения столкновений луча реализуется в два (уже знакомых) шага:
- широкая фаза: определить, через какие ячейки сетки проходит луч (и, соответственно, с какими тайлами и объектами он может пересечься).
- узкая фаза: выполнить определение столкновений с объектами, найденными на предыдущем шаге, найти точки пересечения.
В нашей сеточной структуре широкая фаза сводится к нахождению ячеек, которых касается луч; всё, что содержится в других ячейках сетки коснуться луча точно не может. (Внимание! Строго говоря, это не всегда верно, поскольку мы используем "рыхлую" сетку для динамических объектов; подробнее см. ниже.)
Самое простое, можно взять ограничивающий прямоугольник (AABB) луча и считать, что все ячейки сетки, которые попадают в этот прямоугольник, пересекаются лучом. Для коротких лучей этого может быть достаточно, равно как и для горизонтальных/вертикальных лучей, однако для всех прочих лучей такой подход приведет к проверке столкновений в n^2 ячейках, что сильно снизит производительность.
Гораздо лучше, конечно, было бы определить каких именно ячеек касается луч; для этого существует замечательный (и довольно простой) алгоритм, описанный Амантидесом и Биккером; в общих чертах, этот алгоритм проходит луч с определенным шагом и "посещает" каждую ячейку, которой луч касается.
Для игры N, мы реализовали этот алгоритм; а в каждой клетке, которой касается луч, мы запускаем процедуры определения столкновений, о которых было рассказано в предыдущей статье.
Узкая фаза алогоритма — столкновения с тайлами
Упомянутый выше алгоритм прохождения сетки лучем не только позволяет нам узнать, каких именно ячеек сетки касается луч, он также позволяет нам узнать, где именно луч входит в ячейки — т.е. точки, в которых луч пересекает линии сетки. Это очень полезная информация, поскольку наша сетка хранит данные о сторонах ячеек, и мы можем остановить алгоритм сразу, как только луч пересечет сторону ячейки, обозначенную как "сплошная" — дальнейшие вычисления в этом случае просто не нужны.
Если же луч встретит "пересекающую" сторону, необходимо будет запустить процедуру определения столкновений с содержимым той клетки, в которую луч вошел. В большинстве случаев мы использовали алгоритмы определения точки пересечения луча с прямой и луча с отрезком прямой. Основные наши источники по этой теме: Архив геометрических алгоритмов и книга Джозефа О'Рурка. Для круглых фигур мы адаптировали алгоритм проверки в протяженности, описанный в статье Мигеля Гомеза.
Узкая фаза алогоритма — столкновения с динамическими объектами
Одна главная проблема в использовании "рыхлой" сетки — то, что объекты, которые не находятся в клетке, через которую проходит луч, всё же могут его пересекать.
Рис. 3: ячейки сетки, которых касается луч.

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

Если в вашей игре требуется точное определение пересечения лучей с динамическими объектами, лучше используйте нормальную сетку, с ней нет таких проблем.
в начало
6. Выводы / исходник
Как уже было сказано ранее, главным ограничением нашей сеточной структуры является то, что все объекты в ней должны вписываться в одну ячейку. Это не недостаток самого алгоритма, но наше умышленное ограничение, призванное облегчить реализацию и увеличить производительность (что для ActionScript является особенно острой проблемой).
Чтобы использовать вышеописанные методы с объектами любого размера, необходимо только добавить возможность нахождения ячеек, которых касается объект, чтобы его можно было добавлять в их связные списки объектов (и желательно быстро). Для объектов, чьи размеры меньше размеров ячеек это не составит труда; но чем больше объект, тем сильнее на производительности сказывается задача добавления его в списки затронутых ячеек сетки и последующее удаление из них.
Наилучший вариант организации сетки всегда связан со спецификой конкретной игры.
Еще одно дополнение к сказанному — совершенно не обязательно использовать тайлы для реализации сеточной структуры; вы можете использовать сетку и алгоритмы определения столкновений из предыдущего урока для карты, соатоящей из фигур разного размера и разной формы — таким образом, вы избежите ограничений в дизайне игры, связанных с тайлами. Всё что вам нужно — это уметь определять набор тайлов, из которых состоит данная произвольная фигура. Далее можно использовать изложенный выше алгоритм так, как будто вы имеете дело с картой из тайлов.
Короче, мы надеемся, данный материал дал вам представление об использовании такой простой и эффективной структуры, как сетка, для описания игрового пространства.
Исходник
[ посмотреть ] [ исходник ]
Приложение содержит часть исходного кода игры N, которая относится к материалу этого урока.
От переводчика
Приведенный здесь исходный код работает на ура, но уже морально устарел: всё-таки оригинал статьи был написан два года назад. :) Если у вас есть более совершенный исходник, подходящий к этому уроку, и вы захотите им поделиться — напишите мне.
Как с нами связаться
Если у вас есть замечания или дополнения к этому уроку, напишите нам по адресу tutorials@harveycartel.org
УБЕДИТЕЛЬНАЯ ПРОСЬБА, не писать нам письма с вопросами об исходном коде — с этим вам придётся разобраться самостоятельно.
На нашем форуме есть специальный раздел об уроках.
в начало
+. Примечания, ссылки по теме
Ниже приводятся ссылки на весьма полезные материалы на английском языке. Если вы знаете, где можно найти аналогичные материалы на русском языке —
- Джон Амантидес — Быстрый алгоритм прохождения вокселей для трассировки луча
- Жако Биккер — Трассировка лучей, различные приёмы — Часть 4: Деление пространства
- Том Форсайт — Клеточный автомат для физического моделирования
- Мигель Гомез — Простые тесты пересечений фигур для игр
(материал расположен на gamasutra.com, для его чтения требуется регистрация. регистрация бесплатна, требует всего лишь немного терпения. материал того стоит. - прим. перев.) - Джозеф О'Рурк — Вычислительная геометрия в Си
- Захарий Симпсон — Паттерны проектирования для компьютерных игр
- Тэтчер Ульрих — Пространственное деление с рыхлыми восьмиричными деревьями
в начало
назад к списку уроков N