Перевод статьи Fast platform collisions by Mike.
Перевод: Dmi7ry. Публикация на других сайтах только с обязательной ссылкой на данное сообщение на этом сайте.
Прошу прощения за любительский перевод. Корректировки принимаются.
Хочется сделать примечание, что данный способ применим не только к платформерам, но и к TDS и другим видам, где можно использовать тайлы.

продолжение статьи Определение столкновений

С запуском GameMaker:HTML5, появился один новый фактор, который должен быть ключевым для любой игры, которую Вы сейчас проектируете — скорость. Видите ли, переход от исполняемых фалов для Windows к HTML5 несет некоторые проблемы производительности, и иногда весьма существенные. Очевидно, что JavaScript не такой быстрый, как родной код, и это означает, что Вам придется создавать более оптимальный, более изящный код. Это в свою очередь означает, что требуется некоторая корректировка того, как мы сейчас делаем некоторые вещи в GameMaker. Речь о играх-платформерах, так как, в то время как они хорошо работают под Windows, в GameMaker:HTML5 оригинальные примеры продемонстрировали, что они весьма далеки от оптимальности. Тем не менее, не беспокойтесь: всё, что Вы изучаете здесь, может быть перенесено на обычные приложения Windows, и Вы будете также видеть прирост скорости, таким образом, это будет весьма полезно.

Итак, почему же? Почему в платформерах получается такой результат в JavaScript? А получается он благодаря командам перемещения вроде move_outside_solid(). Посмотрите, что в настоящий момент происходит, когда Вы пишете платформер: Вы ожидаете от системы событие столкновения, а затем используете команды вроде move_outside_solid(), чтобы двигаться за пределы объекта. Проблема с функциями вроде этой — количество работы, которую придется выполнить для того, чтобы исполнить такое простое на вид действие…

Как GameMaker выполняет команду move_outside_solid()? Давайте рассмотрим это. Хорошо… В первую очередь, прочитайте мою статью про столкновения (перевод тут), потому что Вы должны понимать, как работает точное столкновение, и сколько усилий нужно процессору, чтобы проделать эту работу. После прочтения Вы будете понимать, что даже одно точное столкновение может занять довольно долгое время, и возможно, Вы уже догадались, что move_outside_solid() придется делать это несколько раз для того, чтобы «выйти за пределы» столкновения, которое только что произошло..

Итак, давайте проследим подробно, что происходит… Сначала Вы перемещаете игрока/объект как обычно, а затем система генерирует событие столкновения (возможно, с использованием медленной проверки столкновения) и после сообщает Вам, что ваш экземпляр только что столкнулся с чем-то. Теперь Вы проверяете направление, откуда Вы только что пришли, и используете move_outside_solid(), чтобы выйти «обратно» из этого столкновения. Если бы Вы были глубоко внутри столкновение (скажем, на несколько точек внутри блока, с которым столкнулись), то это может занять несколько итераций точного столкновения чтобы переместить ваш экземпляр обратно. Добавив к тому, что помимо игрока Вы можете делать то же самое и у противников, Вы сможете увидеть, что это весьма существенная растрата процессорного времени. Итак, как же еще можно сделать? Как бы Вы могли бегать по платформе, и остановить прыжки игрока (и противников) в стены, или падение сквозь пол?

Для начала, почему бы нам не оглянуться на некоторые старые ретро системы: NES, C64, Megadrive, SNES — все эти системы хорошо известны платформерами, и делали обнаружение столкновения с платформами таким же образом, через тайлмапы. В то же время, это не тайлмапы, как их определяет GameMaker, так как GameMaker использует несколько извращенную версию тайлмапов. Большинство из этих старых систем, использует характерное фиксированное отображение экранов, то есть, экран из X на Y символов. (Например, C64 имеет экран 40×24 клеток, которые он использует в качестве символов, используемые играми в качестве тайлов). Эти символы были затем использованы в качестве тайлов, и эти тайлы были затем определены в платформах и фоне, и простые столкновения происходят с ними..

Игра выше («The Great Giana Sisters» для C64) показывает, как, возможно, в игре выстроены тайлы на этом уровне. Большие тайлы фактически будут состоять из нескольких тайлов, связаны вместе, чтобы сделать большой объект. Это существенное отличие от тайлов GameMaker‘а, потому что они на самом деле не настоящие тайлы, а очень простые спрайты. Это проблема, потому что мы не можем легко определить, с каким тайлом мы столкнулись — по крайней мере, не без обширной проверки. Так как же эти старые и очень медленные системы, сталкиваются с фоном так быстро? Просто они использовали фиксированную сетку из тайлов. Это означало, Вы легко можете сказать, в какие тайлы Вы попали, просто путем деления своих координат (как правило, 8, 16, 32 и т.д. На самом деле, любой степени двойки), а затем используя эти числа, они указывают непосредственно в сетке тайлов..

10000001
10200101
11111111

Итак, давайте взглянем на простой тайлмэп. Выше Вы можете видеть очень простой тайлмэп, где 1 является твердым телом, 0 пусто, и 2 — подбираемый предмет. Это означает, что все, что нам нужно сделать, это проверить тайл непосредственно под экземпляром (в нашем примере это игрок). Итак, как же мы это сделаем? Ну, если мы использовали тайлсет 16×16, и наш спрайт 16×16, тогда, стоя непосредственно на тайле, его координаты х и у будут кратны 16. Тогда проверяя тайл непосредственно под нами, нужно просто добавить 16 к Y, затем разделить координату Y на 16, и округлить результат. Это дает нам указатель на тайл (по оси Y) для тайла под ногами. Если тайл 1, то мы не падаем, если 0, то делаем падение.
Это всё хорошо и здорово, но что, если мы падаем, и что если мы попадаем внутрь тайла? Как мы можем выйти из него без функций вроде move_outside_solid()? Здесь мы используем некоторые трюки старой школы, которые легко позволяли реализовывать платформеры и стрелялки на старых 1МГц системах.

Первым делом, нужно освежить в памяти кое-что из двоичной математики. Двоичная система очень удобна, и Вы должны свободно, насколько это возможно, использовать трюки, которые она позволяет Вам делать. Давайте посмотрим на пару чисел..

%1      1
%10     2
%100    4
%1000   8
%10000 16

Каждый установленный бит добавляет степень двойки к итогу. Как Вы можете видеть из приведенных выше цифр, у них есть только один установленный бит, и поэтому результат — «чистая» степень числа 2 (1,2,4,8,16,32,64,128 и т.д., все степени двойки. Каждое число умножается на 2, оно удваивается.)

Итак, если у нас есть некоторые комбинации этих битов … Что это значит?

%110   6
%1101 13
%11    3
%1001  9

Используя таблицу приведенную выше, вы можете сложить биты вместе, и получить результирующие числа. Довольно понятно пока. Так компьютеры хранят числа, при этом каждый байт содержит значения 8 бит, что означает диапазон чисел от 0 до 255. Для больших чисел, компьютер просто использует больше байт. 2 байта даёт 16 бит, то есть число от 0 до 65535, и так далее…

Итак… Зачем этот урок по основам вычислений? А… Вот теперь начинается самое интересное. Что произойдет, если мы будем смещать эти биты? Допустим, сдвинуть их влево или вправо на какое-то количество бит? Хорошо, %1 сдвигаемый влево на три бита даст %1000, и это дает результатом число 8. Соответственно, если мы имеем %1000 и сдвигаем вправо на три бита, мы должны получить %1, что даст нам в результате число 1. Другими словами, мы можем сделать простое умножение и деление, сдвигая биты (Это опять же, то, как компьютер делает основную двоичную математику).

Так… Что произойдет, если мы «сбросим» младшие биты?.. Допустим, у нас было %1011 (11), и мы сделаем с ним AND %1000 (8), мы бы в конечном итоге получили… 8. Обнулив эти младшие биты, мы эффективно округляем до ближайшего наименьшего числа, кратного 8.

Теперь это удобно …. Что, если наш tilemap был сделан из 16×16, и что если бы мы «залезли» в один на 4 пикселя по координате Y? Например, Y координата была 68. Как мы можем переместить его обратно из тайла? Ну, поскольку мы знаем, что все тайлы на фиксированных границах пикселей, мы знаем, что ВНЕ тайла координата будет 64. Используя двоичные трюки, о которых говорили выше, мы можем сделать простой AND с Y координатой (Y = Y & $fffffff0), и это избавит нас от изменения значения младших битов множителя 16, и помещает его вне столкновения, и обратно до 64, так как %1001000 (68) и $fffffff0 = %1000000 (64).

Итак, давайте посмотрим на это снова. Если мы знаем, что есть столкновение по Y (см. ниже), мы можем просто вернуться назад прямо в пустое пространство с помощью операции AND с $fffffff0 и удаления проблемных битов.

Эта система столкновений молниеносна, но для её использования Вы должны иметь фиксированную тайловую карту (tilemap), а не такую, которая помещает плитки в произвольном месте. В будущих версиях GameMaker эта способность будет удалена, но это также даст доступ к карте для использования со столкновениями, так как это бесценный инструмент. После столкновения с картой, Вы можете столкнуться с чем угодно на этом уровне. Собираемые предметы, ловушки, твердые объекты, триггеры, почти все, что Вы используете для экземпляров с точки зрения столкновения, Вы можете использовать тайлмэпы, делая это быстрее. У вас есть ограничение: ваши объекты должны вписываться размером в тайл, но для большинства вещей это не проблема. В конце концов, если Вы хотите, чтобы сработал триггер чего-либо, когда игрок идет по ней, не все ли равно, если он на несколько пикселей левее? То же самое с бонусами… Вы просто должны привыкнуть размещать их в этой манере, а затем Вы можете использовать tilemap для фактического столкновения.

GameMaker:HTML5 идет с демонстрационным примером этого метода, таким образом, сейчас прочитав про это, Вы можете ковырять исходник до тех пор, пока не поймёте смысл.

Mike. 13 Октября 2011