Добро пожаловать в Библию движений Doom! Во второй части, как и в первой разобраны и рассортированы по категориям все причуды и капризы кода движений в Doom, включая замысловатые трюки с описанием их работы.
До настоящего момента, все рассмотренные трюки с движением персонажа в игре опирались на дискретную природу перемещения в движке DOOM. Теперь же мы копнем код игры гораздо глубже, и доберемся до функции с невинным названием P_SlideMove. Функция содержит комментарий, предупреждающий неосторожного читателя кода, что перед ним «полнейшая неразбериха». Не знаю, добавил этот комментарий John Carmack или же Bernd Kreimeier, но он весьма и весьма точен.
Мы уже разбирали, как большой СПТ («Состояние Попытки Телепортации», которое можно воспринимать как направленный импульс движения персонажа, рассмотрено в части 1) может приводить к багам, например, line skip (пересечение границы). К счастью, движок игры не так уж и глуп и пытается учитывать такие ошибки! Итак, если баги начинаются, если персонаж движется слишком быстро, прекрасным решением будет попросту разделить одно перемещение на несколько подходящего размера, не так ли? И именно это делает движок игры: если X- или Y-вектор движения превышает 15 единиц (что, как можно заметить, на одну единицу меньше «радиуса» игрока), движок пытается разделить перемещения игрока на две части, чтобы каждую просчитать отдельно. Таким образом, если скорость слишком велика, программа проверяет не пересекает ли персонаж препятствие в «промежуточном» состоянии и, при необходимости, не пропускает его. Так как программа проводит два перемещения вместо одного, назовем этот процесс «двойным СПТ».
«Постой-ка!» — возмутится здесь читатель. – «Недавно ты рассказывал о пересечении границ при СПТ > 15, а теперь описываешь код, который не позволяет это сделать! Как вообще это может работать?». Ну, тогда давайте попросту глянем на код:
Заметили? Ну, и что же происходит при движении персонажа на юг или запад? X-СПТ, как и Y-СПТ внезапно оказываются… Отрицательными! И, по неизвестным причинам, движок игры никак не проверят этот любопытный факт.
Но вернемся к основной идее. Итак, движок использует СПТ, чтобы определить, куда «телепортировать» персонажа на следующем шаге. Если «зона высадки» занята, код игры вызывает функцию P_SlideMove, чья задача — проверить факт столкновения с препятствием и, если таковое произошло, обеспечить перемещение персонажа так, чтобы столкновение выглядело натурально. Для начала движок определяет направление движения игрока и рассчитывает три вектора, исходящие из трех ведущих углов коробки персонажа. Затем проверяет каждый вектор на предмет столкновения с преградой. Если столкновение обнаружено, программа определяет процент пути до препятствия и производит перемещение персонажа в найденную точку. А затем берет оставшуюся часть СПТ, направляет его параллельно стене, о которую ударился игрок – эта часть движения и есть «slide» (скольжение) вдоль стены.
И это работает, в большей или меньшей мере. Здесь прячется небольшая внутренняя проблема: для расчета «slide» подпрограмма использует начальный СПТ персонажа, даже если он был разделен на два отдельных перемещения из-за высокой скорости игрока.
Теперь, когда мы это знаем, давайте пошагово проверим весь процесс:
Подведем итог вышесказанному: если игрок движется в северном или восточном направлении с достаточно высокой скоростью (X-СПТ или Y-СПТ превышает 15 юнитов), при этом начальная попытка перемещения блокируется препятствием, движок выполняет два полных перемещения за один тик! Обратите внимание – в результате не изменяется СПТ или что-либо еще, просто происходит два перемещения за время одного.
трюк на 0:12
Теперь, когда мы освоили «wallrunning» («бег у стены»), давайте подумаем – а что если заменить стену на любой непроходимый объект, а лучше на длинный ряд таких объектов?
Движок попробует телепортировать игрока на новую позицию и обнаружит препятствие в зоне высадки. Тогда программа вызовет известную нам P_SlideMove, а та нарисует три вектора из углов и обнаружит: столкновения нет. И что же теперь сделает движок?
Как не странно, указанная функция на самом деле не проверяет столкновение персонажа с объектами, она проверяет только пересечение границ объектов «нарисованными» ей векторами. И если P_SlideMove не смогла найти линию, блокирующую перемещение – она применяет свое последнее секретное оружие: «stairstep» (бег лесенкой). Программа пытается переместить игрока ровно вдоль оси Y, а если не смогла – то вдоль оси X. Позвольте напомнить, что все предметы в DOOM заключены в «коробку» со сторонами, параллельными осям координат. Таким образом, если игрок движется вдоль препятствия, и программа «stairstep» решает двигать его горизонтально, игрок будет скользить вдоль одной стороны объекта.
Теперь, уложив вышесказанное в голове, легко понять что thingrunning происходит в точности так же, как и wallrunning: игрок движется на север или восток с «превышением скорости», проверка перемещения разделяет каждое движение на две равные части, и каждая половинка получает полный начальный вектор СПТ с щедрой подачи P_SlideMove (до тех пор, пока начальная точка высадки заблокирована). Персонаж успешно совершает два полных перемещения вместо одного за каждый тик, попросту скользя с удвоенной скоростью по «краю» предметов. Этот трюк наиболее известен своим применением на Map23, где игрок может разогнаться, выполняя thingrunning вдоль ряда бочек, и в результате перепрыгнуть часть карты, казалось бы, невозможным способом.
трюк на 10:17
Когда я впервые увидел этот трюк, он ошеломил меня настолько, что я принял решение написать статью о магии движка DOOM – тот самый гайд, что сейчас перед вашими глазами.
Одно из самых простых и понятных правил перемещения игрока в DOOM гласит: «air control не существует!» Это значит, что когда ноги персонажа не касаются земли, перемещения персонажа зависят только от местных законов физики, но не от игрока. И как же я был поражен, когда при просмотре спидрана Map14 я увидел, что игрок исполнил wallrunning высоко в воздухе, пробежав по стене прямо к выходу, а конце попросту развернулся над землей и направился к южной двери, хотя до этого мчался просто на восток.
Поначалу я просто не мог осознать, как такой трюк возможен – СПТ игрока был направлен в точности на восток! У него был нулевой Y-СПТ, как он мог начать движение на юг! Но, как всегда, казалось бы, понятный код содержит сюрпризы и подвохи.
Оказывается, если игрок находится вплотную к препятствию, движок не будет пытаться приблизить игрока к преграде. Он попросту применит свое последнее средство – уже привычный для нас «stairstep». Здесь мы знакомимся с волшебным числом 3.125%. Если один из векторов, нарисованный программой из «углов игрока», пересечет стену менее чем на 3.125% своей длины – программа даже не попытается совершить перемещение игрока в начальном направлении. Пропуская все лишние шаги, движок применит «stairstep». Ну а код лесенки, как мы помним, умеет двигать персонажа строго горизонтально (или вертикально), при этом никак не изменяя начальный СПТ игрока.
Теперь, когда мы рассмотрели логику процесса, невероятный «разворот в полете» можно объяснить. Игрок «идет на взлет», нажимая «вверх» у стены, имея при этом высокий X-СПТ и небольшой южный Y-СПТ. Каждый тик, пока игрок находится над землей, движок пытается переметить персонажа на восток и немного на юг, но обнаруживает стену в конечной точке перемещения. Движок мгновенно сдается и зовет на помощь «stairsteps» и отправляет персонажа на восток, при этом не изменяя вектор СПТ никоим образом. В результате Y-СПТ остается чуть-чуть отрицательным в течение всей «воздушной пробежки». И в финале, когда проход к выходу достигнут, проверка перемещения проходит успешно, и игрок меняет направление движения в воздухе, что, казалось бы, невозможно в реалиях физики DOOM.
Этот трюк не такой уж очевидный и зрелищный, как вышеописанные, и мне было трудно найти подходящее имя для него. Мне приходилось слышать название «door trick», и он очень часто используется спидраннерами в ожидании открытия двери.
Трюк банален – упираясь в непроходимую стену правильным способом, игрок может сохранить накопленный импульс движения (СПТ) в максимальном значении, оставаясь неподвижным (результат легко обнаружить визуально, наблюдая быстрое колебание оружия в руках игрока, как на полной скорости бега. Поэтому этот трюк называют «wobble glide» – скольжение покачиваясь). При спидране это означает, что игрок сохраняет максимальную скорость в ожидании открытия двери, и, когда проход становится достаточно большим, пулей несется дальше, сберегая драгоценные миллисекунды.
Но как работает этот трюк? Обычно, если персонаж вбегает в стену, его скорость (его СПТ) мгновенно снижается движком. Это можно обнаружить по изменению анимации оружии в руках игрока. Чтобы понять природу происходящего, нам снова придется углубиться в код движка DOOM и понять, как он определяет столкновения.
Вспомним, что обычно при столкновении со стеной известная нам подпрограмма P_SlideMove рассчитывает процент вектора движения, направленного в стену (или пропускает эту часть, если столкновение найдено на дистанции менее, чем 3.125% вектора), а затем перенаправляет «остаток» движения параллельно стене. В нормальной ситуации этот вполне разумный алгоритм погасит вашу скорость – если удариться с разбегу в стену под прямым углом, скорость скольжения будет пропорциональна косинусу разности углов между направлением движения и направлением стены, а cos 90 равен нулю.
Но давайте смотреть глубже. Как именно движок определяет будущее столкновение со стеной? Чтобы разрешить эту задачу, программа решает простое математическое уравнение: возьмем линию, представляющую собой непроходимую стену, возьмем вектор движения, направленный из одного из углов коробки персонажа и найдем точку пересечения. Эти расчеты можно произвести, используя вектора, матрицы и другие математические инструменты. Но движок DOOM применяет простейший способ: возьмем конечные точки отрезка А и проверим, с какой стороны они находятся относительно отрезка Б. Затем проверим с какой стороны от А находятся крайние точки отрезка Б. Если в обоих случаях крайние точки находятся по разные стороны линий, отрезки пересекаются.
Для выполнения такой несложной проверки понадобится немного деления и умножения. И здесь движок игры раскрывает еще один аспект. Все данные движок хранит в виде 32-битных значений, и, что особенно важно – в виде чисел с фиксированной запятой. При этом один бит используется для указания знака числа (положительное / отрицательное), 15 бит хранит целую часть и оставшиеся 16 – дробную. 15 бит – это весьма немного; фактически, допустимый диапазон значений от -32768 до 32768. Итак, если вам нужно перемножить два числа, придется быть очень осторожным, чтобы полученный результат не оказался за пределами диапазона. Квадратный корень от 32768 всего лишь 181, а значит, проверка пересечения двух линий размером 200 юнитов каждая приведет к переполнению ячейки памяти. И как же справится с такой задачкой?
Вот часть кода из функции «проверки пересечения», который справляется с проблемой:
Как вы видите, он попросту делит все значения на 256 до начала расчетов (если быть совсем точным, выполняет побитовый правый сдвиг на 8, хотя это ничего не меняет). Таким нехитрым способом движок гарантирует, что результат расчетов будет достаточно мал, чтобы избежать переполнения. При этом мы сократили дробную часть с 16 до 8 бит, так что никаких проблем, не так ли?
Ну, в большинстве случаев проблем нет. Но что произойдет, если СПТ в одном из направлений будет предельно мал? К примеру, игрок бежит в угол, имея X-СПТ 20 и Y-СПТ 0,001. Давайте рассмотрим детально:
Подытожим: если игрок бежит, упираясь в угол, с предельно малым Y_СПТ или X-СПТ, он может сохранять высокий СПТ, в результате ошибочного обнуления вектора.
трюк: 0:20
А теперь пора вывести тяжелую артиллерию. Вместо того, чтобы нарушать условные линии разделения, будем игнорировать абсолютно непроходимые линии.
На первый взгляд, этот трюк попросту невозможен. Чтобы пройти сквозь стену, персонаж должен мгновенно переместиться не менее чем на 32 юнита. Тогда, даже после деления на две части, каждая «половинка» будет >= 16 юнитов (размер персонажа). Мы уже знаем, что максимальная скорость, которой можно достигнуть с применением SR50, составляет 23,57 юнитов за тик, но даже если лимит достигнут, движок разобьет 23,57 на два отдельных перемещения. Более того, в коде игры зашито жесткое ограничение скорости в 30 юнитов, которое применяется в самом начале расчета передвижения. И как же в таких условиях добиться скорости перемещения персонажа на 32 юнита за одно движение?
В целом, это правда, что 23,57 – максимальная скорость, достижимая при использовании обычных средств управления персонажем, но что если «обычные средства» — не единственный способ увеличить СПТ? Вооружившись этим знанием, из движка DOOM можно выжать намного, намного больше. (Я намеренно не буду описывать damage boosts — его сложно контролировать и тестировать. Конечно, можно получить скорость более чем 23,57, например, подорвав себя ракетой, но есть гораздо более простой и безопасный способ).
Пора вернуться к P_SlideMove. Как я уже описывал, при столкновении, после выполнения частичного перемещения в направлении вектора, оставшаяся часть СПТ перенаправляется параллельно препятствию. Итак, как же реализована эта часть логики? Выполняются такие три шага:
Все эти расчеты очень просто выполнить, применяя синусы и косинусы. Но именно здесь код как будто бы забывает о существовании тригонометрии и использует просто блестящее упрощение. Вместо того, чтобы определить величину остатка СПТ правильно, он вызывает функцию под именем P_AproxDistance. И что же эта P_AproxDistance (ПриблизительнаяДистанция) делает?
Да, да, вы не ошиблись. Не нужны синусы и косинусы, ни к чему корни квадратные и кубические, нам хватит сложения. Просто добавим одну ось к половине второй оси. Вы можете представить, насколько приблизительно такое «aproximation» (приближение).
Таким образом, функция дает игроку очень серьезный бонус. Дело в том, что результат такого подсчета стабильно больше, чем верный результат. Давайте проверим на примере: посчитаем вектор «скольжения» игрока при X-СПТ = 3 и Y-СПТ = 4. Теорема Пифагора говорит нам, что размер вектора скольжения равен 5: это гипотенуза прямоугольного треугольника со сторонами 3 и 4. Но функция P_AproxDistance возвращает размер 5,5. И вот, мы получили ускорение на 10% просто из-за неточности вычислений! Размер такого бонуса зависит от угла движения игрока, и к сожалению, если угол составляет 45 градусов (обычная ситуация при трюке void glide), бонус составит жалкие 6%. И этого более чем достаточно.
Однако нужно еще немного усилий, чтобы добиться потрясающего результата. Обычно P_SlideMove поступает так:
Теперь логика происходящего стала очевидна: если игрок в углу, первое столкновение со стеной вызывает slide (скольжение) ко второй стене. Там сразу же происходит второе столкновение, и алгоритм запускается заново, принимая как начальные данные существующий СПТ – то есть остаток «скольжения» от прошлого цикла. Весь трюк сводится к созданию ситуации, когда P_SlideMove постоянно терпит неудачу при попытке перемещения. Вот что при этом происходит:
Но это еще не все: если при «беге в углу» СПТ игрока превышает 15 юнитов и направлен на север или восток, описанный процесс произойдет дважды, благодаря разбиению перемещения на две части. То есть, увеличение СПТ произойдет четыре раза за один тик!
Теперь мы увидели весь процесс. Нужно просто выбрать правильную позицию и код войдет в цикл, дающий постоянный прирост СПТ. Каждый тик СПТ увеличивается дважды (или четырежды) на относительно небольшую величину из-за грубого приближения. В конце каждого тика выросший СПТ, конечно, снижается «трением», но пока прирост СПТ за тик составляет не менее 10%, этого достаточно, что бы превысить снижение от трения и обеспечить постоянный прирост. Остаётся подождать, когда СПТ превысит 32 юнита.
«Но ведь игра жестко ограничивает игрока скоростью в 30 юнитов!» — скажет внимательный читатель. Да, верно. Поэтому в начале последнего тика перед «прыжком сквозь стену» СПТ будет чуть менее 30 юнитов, а в конце тика, после четырех циклов увеличения превысит 32 юнита. Вообще-то, таким способом можно получить мгновенный СПТ размером 37 или 38 юнитов.
Маленькая заметка напоследок: трюк сработает, только если стены возле вас не направлены параллельно осям координат. Иначе движок вернет чистый X-СПТ или же Y-СПТ, не создавая новый перенаправленный вектор. Так как большинство стен в игре все же расположены вдоль осей координат, возможность использования void glide сильно ограниченна.
Если void glide показался вам магическим трюком, я попробую удивить вас еще одним: «elastic collisions» (упругие столкновения). Не то чтобы это большая редкость, но они так случайны и непредсказуемы, что я никогда не слышал об использовании этого трюка спидраннерами.
Суть elastic collisions в мгновенном изменении направления СПТ на противоположное. Это может произойти неожиданно – вот вы имеете СПТ 15 юнитов, и через мгновение уже -15, без каких-либо переходных процессов. Создается впечатление, что вы столкнулись с чем-то очень упругим и отлетели в противоположном направлении, хотя на экране нет ничего, объясняющего такое поведение.
Чтобы понять elastic collisions, нам снова придется погрузиться в глубины кода DOOM. Помните, мы рассматривали баг с сохранением СПТ, где я описывал алгоритм нахождения пересечений? Так вот: кое-что я приберег напоследок. В игре на самом деле два алгоритма нахождения пересечений сегментов. Они почти идентичны, но применяются в разных случаях: один вызывается при абсолютном значении X-СПТ или Y-СПТ более 16 юнитов, а другой при значении меньше или равно 16.
«Хорошо, но что в результате?» — спросите вы. Ну, хотя алгоритмы почти одинаковые, вот что они делают по-разному: для больших величин СПТ алгоритм берет вектор, и сравнивает его с двумя вершинами линии пересечения. Для меньших размеров СПТ, алгоритм берет линию препятствия, и сравнивает ее с конечными точками вектора СПТ.
Похоже, не имеет значения, какой из алгоритмов применять. Тогда дам подсказку: если применяется алгоритм для малых значений СПТ, он не проверяет положение крайних точек линии пересечения относительно вектора движения. Вспомним определение line intersection (пересечения отрезков): нам необходимо проверить отрезок А относительно крайних точек отрезка Б, а затем отрезок Б относительно крайних точек отрезка А. Но в нашем случае движок DOOM останавливается на полпути и решает, что работа сделана.
В результате этой проверки для малых СПТ движок может определить пересечение вектора движения с препятствием, хотя пересечения нет. Это происходит, например, если игрок движется вдоль длинного ряда объектов. Главное, что бы «вглубь» от основной линии разделения отходили другие линии, перпендикулярные ей. В обычном геймплее такое случается крайне редко – хотя бы потому, что большую часть времени игрок не перемещается скольжением. Но если во время wall gliding вы внезапно остановились без видимой причины — это тот самый баг. Движок решил, что вы пересекли линию разделения, хотя этого, очевидно, не было.
Но это все еще не elastic collisions, это просто остановка! Это нечто противоположное эластичности. Ну что ж, давайте снова посмотрим в код «скольжения», чтобы заметить одну важную деталь.
Когда движок определяет остаток вектора СПТ, он должен перенаправить вектор вдоль линии препятствия. Для этого проверяется, по какую сторону от линии находится центр персонажа, а затем определяется разница между углом вектора движения и углом направления линии. При этом предполагается, что угол может быть между 0 (игрок движется параллельно препятствию) и 180 (тоже параллельно, но в противоположном направлении).
И вот вопрос: а что случится, если угол между вектором движения игрока и стеной, по каким-то причинам, окажется вне этого диапазона?
Случится вот что: игра «в панике» попросту поменяет угол – а значит, весь вектор, на противоположный. Правда подобная ситуация невозможна, так что переживать не о чем, не так ли?
А что же произойдет, если центр игрока будет по одну сторону линии, а угол (тот самый, из которого «рисуется» вектор) – по другую сторону? Тогда при расчете вектора «скольжения» будет получен недопустимый угол, и алгоритм развернет вектор в противоположную сторону.
Но как же игрок может двигаться, если центр игрока с одной стороны линии, а угол с другой? Игрок при этом пересекает непроходимую линию, и должен, как минимум, просто застрять. Обычно так и есть, но: если вектор СПТ менее 16 юнитов и поблизости окажется линия разделения, направленная под особым углом, то угловой вектор движения пересечется с этой, находящейся на расстоянии от игрока (внутри стены) линией (смотрите схему). Затем произойдет попытка найти «остаток скольжения» и провалится из-за неверных стартовых условий. Что вызовет замену вектора на противоположный и отправит игрока в неожиданном направлении, возможно, немало удивив.
Собственно, на данный момент это все, что я хотел рассказать. Но кто знает, какие еще трюки и секреты скрывает в себе код легендарной игры?
BLACK FRIDAY ПРОДОЛЖАЕТСЯ: скидка 30% на первый платёж по промо-коду BLACK30% при заказе на 1-6 месяцев!
Это не просто виртуальные серверы! Это VPS (KVM) с выделенными накопителями, которые могут быть не хуже выделенных серверов, а в большинстве случаев — лучше! Мы сделали VPS (KVM) c выделенными накопителями в Нидерландах и США (конфигурации от VPS (KVM) — E5-2650v4 (6 Cores) / 10GB DDR4 / 240GB SSD или 4TB HDD / 1Gbps 10TB доступными по уникально низкой цене — от $29 / месяц, доступны варианты с RAID1 и RAID10), не упустите шанс оформить заказ на новый тип виртуального сервера, где все ресурсы принадлежат Вам, как на выделенном, а цена значительно ниже, при гораздо более производительном «железе»!
Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5-2650 v4 стоимостью 9000 евро за копейки? Dell R730xd в 2 раза дешевле? Только у нас 2 х Intel Dodeca-Core Xeon E5-2650v4 128GB DDR4 6x480GB SSD 1Gbps 100 ТВ от $249 в Нидерландах и США!
SlideMove: cкользкие моменты
До настоящего момента, все рассмотренные трюки с движением персонажа в игре опирались на дискретную природу перемещения в движке DOOM. Теперь же мы копнем код игры гораздо глубже, и доберемся до функции с невинным названием P_SlideMove. Функция содержит комментарий, предупреждающий неосторожного читателя кода, что перед ним «полнейшая неразбериха». Не знаю, добавил этот комментарий John Carmack или же Bernd Kreimeier, но он весьма и весьма точен.
WALL RUNNING
Мы уже разбирали, как большой СПТ («Состояние Попытки Телепортации», которое можно воспринимать как направленный импульс движения персонажа, рассмотрено в части 1) может приводить к багам, например, line skip (пересечение границы). К счастью, движок игры не так уж и глуп и пытается учитывать такие ошибки! Итак, если баги начинаются, если персонаж движется слишком быстро, прекрасным решением будет попросту разделить одно перемещение на несколько подходящего размера, не так ли? И именно это делает движок игры: если X- или Y-вектор движения превышает 15 единиц (что, как можно заметить, на одну единицу меньше «радиуса» игрока), движок пытается разделить перемещения игрока на две части, чтобы каждую просчитать отдельно. Таким образом, если скорость слишком велика, программа проверяет не пересекает ли персонаж препятствие в «промежуточном» состоянии и, при необходимости, не пропускает его. Так как программа проводит два перемещения вместо одного, назовем этот процесс «двойным СПТ».
«Постой-ка!» — возмутится здесь читатель. – «Недавно ты рассказывал о пересечении границ при СПТ > 15, а теперь описываешь код, который не позволяет это сделать! Как вообще это может работать?». Ну, тогда давайте попросту глянем на код:
f (xtap > 15 OR ytap > 15)
Заметили? Ну, и что же происходит при движении персонажа на юг или запад? X-СПТ, как и Y-СПТ внезапно оказываются… Отрицательными! И, по неизвестным причинам, движок игры никак не проверят этот любопытный факт.
Но вернемся к основной идее. Итак, движок использует СПТ, чтобы определить, куда «телепортировать» персонажа на следующем шаге. Если «зона высадки» занята, код игры вызывает функцию P_SlideMove, чья задача — проверить факт столкновения с препятствием и, если таковое произошло, обеспечить перемещение персонажа так, чтобы столкновение выглядело натурально. Для начала движок определяет направление движения игрока и рассчитывает три вектора, исходящие из трех ведущих углов коробки персонажа. Затем проверяет каждый вектор на предмет столкновения с преградой. Если столкновение обнаружено, программа определяет процент пути до препятствия и производит перемещение персонажа в найденную точку. А затем берет оставшуюся часть СПТ, направляет его параллельно стене, о которую ударился игрок – эта часть движения и есть «slide» (скольжение) вдоль стены.
И это работает, в большей или меньшей мере. Здесь прячется небольшая внутренняя проблема: для расчета «slide» подпрограмма использует начальный СПТ персонажа, даже если он был разделен на два отдельных перемещения из-за высокой скорости игрока.
Теперь, когда мы это знаем, давайте пошагово проверим весь процесс:
- игрок бежит, прижавшись к длинной горизонтальной стене
- что СПТ игрока, к примеру, составляет X-СПТ = 20 и Y-СПТ = 2
- движок определяет, что X-СПТ слишком велик, и разделяет перемещение на два, каждое с импульсами X-СПТ = 10 и Y-СПТ = 1
- теперь движок проверяет первое из двух перемещений и определят столкновение со стеной к северу от игрока
- на помощь приходит P_SlideMove и рисует три вектора из «углов» персонажа, направленных к северу и востоку. Но для расчета векторов берет базовый СПТ, то есть X-СПТ = 20 и Y-СПТ = 2 (а не X-СПТ = 10 и Y-СПТ = 1, как должно бы)
- вектор пересекает стену на севере
- движок перемещает персонажа, к примеру, на 5% от текущего СПТ
- и, наконец, движок перенаправляет оставшиеся 95% базового СПТ вдоль стены, перемещая игрока на 19 юнитов.
- после чего, удовлетворенный проделанной работой, движок приступает ко второй половине перемещения игрока, выполняет привычную процедуру и отправляет персонажа еще на 19 юнитов на восток.
Подведем итог вышесказанному: если игрок движется в северном или восточном направлении с достаточно высокой скоростью (X-СПТ или Y-СПТ превышает 15 юнитов), при этом начальная попытка перемещения блокируется препятствием, движок выполняет два полных перемещения за один тик! Обратите внимание – в результате не изменяется СПТ или что-либо еще, просто происходит два перемещения за время одного.
THING RUNNING
трюк на 0:12
Теперь, когда мы освоили «wallrunning» («бег у стены»), давайте подумаем – а что если заменить стену на любой непроходимый объект, а лучше на длинный ряд таких объектов?
Движок попробует телепортировать игрока на новую позицию и обнаружит препятствие в зоне высадки. Тогда программа вызовет известную нам P_SlideMove, а та нарисует три вектора из углов и обнаружит: столкновения нет. И что же теперь сделает движок?
Как не странно, указанная функция на самом деле не проверяет столкновение персонажа с объектами, она проверяет только пересечение границ объектов «нарисованными» ей векторами. И если P_SlideMove не смогла найти линию, блокирующую перемещение – она применяет свое последнее секретное оружие: «stairstep» (бег лесенкой). Программа пытается переместить игрока ровно вдоль оси Y, а если не смогла – то вдоль оси X. Позвольте напомнить, что все предметы в DOOM заключены в «коробку» со сторонами, параллельными осям координат. Таким образом, если игрок движется вдоль препятствия, и программа «stairstep» решает двигать его горизонтально, игрок будет скользить вдоль одной стороны объекта.
Теперь, уложив вышесказанное в голове, легко понять что thingrunning происходит в точности так же, как и wallrunning: игрок движется на север или восток с «превышением скорости», проверка перемещения разделяет каждое движение на две равные части, и каждая половинка получает полный начальный вектор СПТ с щедрой подачи P_SlideMove (до тех пор, пока начальная точка высадки заблокирована). Персонаж успешно совершает два полных перемещения вместо одного за каждый тик, попросту скользя с удвоенной скоростью по «краю» предметов. Этот трюк наиболее известен своим применением на Map23, где игрок может разогнаться, выполняя thingrunning вдоль ряда бочек, и в результате перепрыгнуть часть карты, казалось бы, невозможным способом.
WALLRUN «AIR CONTROL»
трюк на 10:17
Когда я впервые увидел этот трюк, он ошеломил меня настолько, что я принял решение написать статью о магии движка DOOM – тот самый гайд, что сейчас перед вашими глазами.
Одно из самых простых и понятных правил перемещения игрока в DOOM гласит: «air control не существует!» Это значит, что когда ноги персонажа не касаются земли, перемещения персонажа зависят только от местных законов физики, но не от игрока. И как же я был поражен, когда при просмотре спидрана Map14 я увидел, что игрок исполнил wallrunning высоко в воздухе, пробежав по стене прямо к выходу, а конце попросту развернулся над землей и направился к южной двери, хотя до этого мчался просто на восток.
Поначалу я просто не мог осознать, как такой трюк возможен – СПТ игрока был направлен в точности на восток! У него был нулевой Y-СПТ, как он мог начать движение на юг! Но, как всегда, казалось бы, понятный код содержит сюрпризы и подвохи.
Оказывается, если игрок находится вплотную к препятствию, движок не будет пытаться приблизить игрока к преграде. Он попросту применит свое последнее средство – уже привычный для нас «stairstep». Здесь мы знакомимся с волшебным числом 3.125%. Если один из векторов, нарисованный программой из «углов игрока», пересечет стену менее чем на 3.125% своей длины – программа даже не попытается совершить перемещение игрока в начальном направлении. Пропуская все лишние шаги, движок применит «stairstep». Ну а код лесенки, как мы помним, умеет двигать персонажа строго горизонтально (или вертикально), при этом никак не изменяя начальный СПТ игрока.
Теперь, когда мы рассмотрели логику процесса, невероятный «разворот в полете» можно объяснить. Игрок «идет на взлет», нажимая «вверх» у стены, имея при этом высокий X-СПТ и небольшой южный Y-СПТ. Каждый тик, пока игрок находится над землей, движок пытается переметить персонажа на восток и немного на юг, но обнаруживает стену в конечной точке перемещения. Движок мгновенно сдается и зовет на помощь «stairsteps» и отправляет персонажа на восток, при этом не изменяя вектор СПТ никоим образом. В результате Y-СПТ остается чуть-чуть отрицательным в течение всей «воздушной пробежки». И в финале, когда проход к выходу достигнут, проверка перемещения проходит успешно, и игрок меняет направление движения в воздухе, что, казалось бы, невозможно в реалиях физики DOOM.
MOMENTUM PRESERVATION
Этот трюк не такой уж очевидный и зрелищный, как вышеописанные, и мне было трудно найти подходящее имя для него. Мне приходилось слышать название «door trick», и он очень часто используется спидраннерами в ожидании открытия двери.
Трюк банален – упираясь в непроходимую стену правильным способом, игрок может сохранить накопленный импульс движения (СПТ) в максимальном значении, оставаясь неподвижным (результат легко обнаружить визуально, наблюдая быстрое колебание оружия в руках игрока, как на полной скорости бега. Поэтому этот трюк называют «wobble glide» – скольжение покачиваясь). При спидране это означает, что игрок сохраняет максимальную скорость в ожидании открытия двери, и, когда проход становится достаточно большим, пулей несется дальше, сберегая драгоценные миллисекунды.
Но как работает этот трюк? Обычно, если персонаж вбегает в стену, его скорость (его СПТ) мгновенно снижается движком. Это можно обнаружить по изменению анимации оружии в руках игрока. Чтобы понять природу происходящего, нам снова придется углубиться в код движка DOOM и понять, как он определяет столкновения.
Вспомним, что обычно при столкновении со стеной известная нам подпрограмма P_SlideMove рассчитывает процент вектора движения, направленного в стену (или пропускает эту часть, если столкновение найдено на дистанции менее, чем 3.125% вектора), а затем перенаправляет «остаток» движения параллельно стене. В нормальной ситуации этот вполне разумный алгоритм погасит вашу скорость – если удариться с разбегу в стену под прямым углом, скорость скольжения будет пропорциональна косинусу разности углов между направлением движения и направлением стены, а cos 90 равен нулю.
Но давайте смотреть глубже. Как именно движок определяет будущее столкновение со стеной? Чтобы разрешить эту задачу, программа решает простое математическое уравнение: возьмем линию, представляющую собой непроходимую стену, возьмем вектор движения, направленный из одного из углов коробки персонажа и найдем точку пересечения. Эти расчеты можно произвести, используя вектора, матрицы и другие математические инструменты. Но движок DOOM применяет простейший способ: возьмем конечные точки отрезка А и проверим, с какой стороны они находятся относительно отрезка Б. Затем проверим с какой стороны от А находятся крайние точки отрезка Б. Если в обоих случаях крайние точки находятся по разные стороны линий, отрезки пересекаются.
Для выполнения такой несложной проверки понадобится немного деления и умножения. И здесь движок игры раскрывает еще один аспект. Все данные движок хранит в виде 32-битных значений, и, что особенно важно – в виде чисел с фиксированной запятой. При этом один бит используется для указания знака числа (положительное / отрицательное), 15 бит хранит целую часть и оставшиеся 16 – дробную. 15 бит – это весьма немного; фактически, допустимый диапазон значений от -32768 до 32768. Итак, если вам нужно перемножить два числа, придется быть очень осторожным, чтобы полученный результат не оказался за пределами диапазона. Квадратный корень от 32768 всего лишь 181, а значит, проверка пересечения двух линий размером 200 юнитов каждая приведет к переполнению ячейки памяти. И как же справится с такой задачкой?
Вот часть кода из функции «проверки пересечения», который справляется с проблемой:
left = (line->dy / 256) * (dx / 256);
right = (dy / 256) * (line->dx / 256);
Как вы видите, он попросту делит все значения на 256 до начала расчетов (если быть совсем точным, выполняет побитовый правый сдвиг на 8, хотя это ничего не меняет). Таким нехитрым способом движок гарантирует, что результат расчетов будет достаточно мал, чтобы избежать переполнения. При этом мы сократили дробную часть с 16 до 8 бит, так что никаких проблем, не так ли?
Ну, в большинстве случаев проблем нет. Но что произойдет, если СПТ в одном из направлений будет предельно мал? К примеру, игрок бежит в угол, имея X-СПТ 20 и Y-СПТ 0,001. Давайте рассмотрим детально:
- движок пытается переместить персонажа на 20 юнитов на восток, и на 0,001 юнит на север, но не может, так как обнаруживает на севере стену
- движок вызывает P_SlideMove для обработки столкновения, рисует три вектора из углов
- движок проверяет первый вектор и обнаруживает пересечение со стеной на севере, как и задумано
- движок проверяет второй вектор, но благодаря делению на 256, крошечный 0,001 Y-СПТ уже округлен до нуля, и программа не находит пересечения вектора со стеной на севере
- затем движок пытается совершить частичное перемещение игрока в направлении первого вектора, к примеру, на 50% размера вектора
- но когда движок пытается переместить игрока на 0,0005 юнитов в северном направлении, он терпит неудачу, обнаружив стену в конечной точке
- движок беспомощно опускает руки и вызывает «stairstep», который, как нам известно, никоим образом не изменяет начальный СПТ.
Подытожим: если игрок бежит, упираясь в угол, с предельно малым Y_СПТ или X-СПТ, он может сохранять высокий СПТ, в результате ошибочного обнуления вектора.
VOID GLIDE
трюк: 0:20
А теперь пора вывести тяжелую артиллерию. Вместо того, чтобы нарушать условные линии разделения, будем игнорировать абсолютно непроходимые линии.
На первый взгляд, этот трюк попросту невозможен. Чтобы пройти сквозь стену, персонаж должен мгновенно переместиться не менее чем на 32 юнита. Тогда, даже после деления на две части, каждая «половинка» будет >= 16 юнитов (размер персонажа). Мы уже знаем, что максимальная скорость, которой можно достигнуть с применением SR50, составляет 23,57 юнитов за тик, но даже если лимит достигнут, движок разобьет 23,57 на два отдельных перемещения. Более того, в коде игры зашито жесткое ограничение скорости в 30 юнитов, которое применяется в самом начале расчета передвижения. И как же в таких условиях добиться скорости перемещения персонажа на 32 юнита за одно движение?
В целом, это правда, что 23,57 – максимальная скорость, достижимая при использовании обычных средств управления персонажем, но что если «обычные средства» — не единственный способ увеличить СПТ? Вооружившись этим знанием, из движка DOOM можно выжать намного, намного больше. (Я намеренно не буду описывать damage boosts — его сложно контролировать и тестировать. Конечно, можно получить скорость более чем 23,57, например, подорвав себя ракетой, но есть гораздо более простой и безопасный способ).
Пора вернуться к P_SlideMove. Как я уже описывал, при столкновении, после выполнения частичного перемещения в направлении вектора, оставшаяся часть СПТ перенаправляется параллельно препятствию. Итак, как же реализована эта часть логики? Выполняются такие три шага:
- определим величину неиспользованного СПТ
- создадим вектор такой же величины, направленный вдоль препятствия
- разделим новый вектор на x- и y-составляющую, чтобы определить новый X-СПТ и Y-СПТ игрока.
Все эти расчеты очень просто выполнить, применяя синусы и косинусы. Но именно здесь код как будто бы забывает о существовании тригонометрии и использует просто блестящее упрощение. Вместо того, чтобы определить величину остатка СПТ правильно, он вызывает функцию под именем P_AproxDistance. И что же эта P_AproxDistance (ПриблизительнаяДистанция) делает?
return (the longer of XTAP or YTAP) + (half the shorter of XTAP or YTAP)
Да, да, вы не ошиблись. Не нужны синусы и косинусы, ни к чему корни квадратные и кубические, нам хватит сложения. Просто добавим одну ось к половине второй оси. Вы можете представить, насколько приблизительно такое «aproximation» (приближение).
Таким образом, функция дает игроку очень серьезный бонус. Дело в том, что результат такого подсчета стабильно больше, чем верный результат. Давайте проверим на примере: посчитаем вектор «скольжения» игрока при X-СПТ = 3 и Y-СПТ = 4. Теорема Пифагора говорит нам, что размер вектора скольжения равен 5: это гипотенуза прямоугольного треугольника со сторонами 3 и 4. Но функция P_AproxDistance возвращает размер 5,5. И вот, мы получили ускорение на 10% просто из-за неточности вычислений! Размер такого бонуса зависит от угла движения игрока, и к сожалению, если угол составляет 45 градусов (обычная ситуация при трюке void glide), бонус составит жалкие 6%. И этого более чем достаточно.
Однако нужно еще немного усилий, чтобы добиться потрясающего результата. Обычно P_SlideMove поступает так:
- запускает счетчик, начиная с единицы
- рисует векторы из углов, и пытается переместить игрока в направлении одного из них
- если есть остаток вектора после столкновения, обсчитывает новый вектор, направленный параллельно препятствию, и пытается переметить игрока в новом направлении
- если движение «скольжением» оказывается невозможным, начинает все сначала, увеличив счетчик на единицу
- ну а если счетчик уже достиг 3, беспомощно опускает руки и зовет на помощь «stairstep».
Теперь логика происходящего стала очевидна: если игрок в углу, первое столкновение со стеной вызывает slide (скольжение) ко второй стене. Там сразу же происходит второе столкновение, и алгоритм запускается заново, принимая как начальные данные существующий СПТ – то есть остаток «скольжения» от прошлого цикла. Весь трюк сводится к созданию ситуации, когда P_SlideMove постоянно терпит неудачу при попытке перемещения. Вот что при этом происходит:
- рисуются известные нам три вектора
- более короткий из них пересекается со стеной на расстоянии менее 3,125% собственной длины
- мгновенно рассчитывается «вектор скольжения», с использования 100% текущего СПТ
- в процессе подсчета СПТ вырастает из-за неточности «приближения» P_AproxDistance
- однако скольжение в новом направлении оказывается невозможным, поэтому процесс перезапускается
- описанные шаги повторяются дважды
- алгоритм сдается, вызывая stairstep, который так же терпит неудачу, но при этом сохраняет дважды увеличенный СПТ игрока.
Но это еще не все: если при «беге в углу» СПТ игрока превышает 15 юнитов и направлен на север или восток, описанный процесс произойдет дважды, благодаря разбиению перемещения на две части. То есть, увеличение СПТ произойдет четыре раза за один тик!
Теперь мы увидели весь процесс. Нужно просто выбрать правильную позицию и код войдет в цикл, дающий постоянный прирост СПТ. Каждый тик СПТ увеличивается дважды (или четырежды) на относительно небольшую величину из-за грубого приближения. В конце каждого тика выросший СПТ, конечно, снижается «трением», но пока прирост СПТ за тик составляет не менее 10%, этого достаточно, что бы превысить снижение от трения и обеспечить постоянный прирост. Остаётся подождать, когда СПТ превысит 32 юнита.
«Но ведь игра жестко ограничивает игрока скоростью в 30 юнитов!» — скажет внимательный читатель. Да, верно. Поэтому в начале последнего тика перед «прыжком сквозь стену» СПТ будет чуть менее 30 юнитов, а в конце тика, после четырех циклов увеличения превысит 32 юнита. Вообще-то, таким способом можно получить мгновенный СПТ размером 37 или 38 юнитов.
Маленькая заметка напоследок: трюк сработает, только если стены возле вас не направлены параллельно осям координат. Иначе движок вернет чистый X-СПТ или же Y-СПТ, не создавая новый перенаправленный вектор. Так как большинство стен в игре все же расположены вдоль осей координат, возможность использования void glide сильно ограниченна.
ELASTIC COLLISIONS
Если void glide показался вам магическим трюком, я попробую удивить вас еще одним: «elastic collisions» (упругие столкновения). Не то чтобы это большая редкость, но они так случайны и непредсказуемы, что я никогда не слышал об использовании этого трюка спидраннерами.
Суть elastic collisions в мгновенном изменении направления СПТ на противоположное. Это может произойти неожиданно – вот вы имеете СПТ 15 юнитов, и через мгновение уже -15, без каких-либо переходных процессов. Создается впечатление, что вы столкнулись с чем-то очень упругим и отлетели в противоположном направлении, хотя на экране нет ничего, объясняющего такое поведение.
Чтобы понять elastic collisions, нам снова придется погрузиться в глубины кода DOOM. Помните, мы рассматривали баг с сохранением СПТ, где я описывал алгоритм нахождения пересечений? Так вот: кое-что я приберег напоследок. В игре на самом деле два алгоритма нахождения пересечений сегментов. Они почти идентичны, но применяются в разных случаях: один вызывается при абсолютном значении X-СПТ или Y-СПТ более 16 юнитов, а другой при значении меньше или равно 16.
«Хорошо, но что в результате?» — спросите вы. Ну, хотя алгоритмы почти одинаковые, вот что они делают по-разному: для больших величин СПТ алгоритм берет вектор, и сравнивает его с двумя вершинами линии пересечения. Для меньших размеров СПТ, алгоритм берет линию препятствия, и сравнивает ее с конечными точками вектора СПТ.
Похоже, не имеет значения, какой из алгоритмов применять. Тогда дам подсказку: если применяется алгоритм для малых значений СПТ, он не проверяет положение крайних точек линии пересечения относительно вектора движения. Вспомним определение line intersection (пересечения отрезков): нам необходимо проверить отрезок А относительно крайних точек отрезка Б, а затем отрезок Б относительно крайних точек отрезка А. Но в нашем случае движок DOOM останавливается на полпути и решает, что работа сделана.
В результате этой проверки для малых СПТ движок может определить пересечение вектора движения с препятствием, хотя пересечения нет. Это происходит, например, если игрок движется вдоль длинного ряда объектов. Главное, что бы «вглубь» от основной линии разделения отходили другие линии, перпендикулярные ей. В обычном геймплее такое случается крайне редко – хотя бы потому, что большую часть времени игрок не перемещается скольжением. Но если во время wall gliding вы внезапно остановились без видимой причины — это тот самый баг. Движок решил, что вы пересекли линию разделения, хотя этого, очевидно, не было.
Но это все еще не elastic collisions, это просто остановка! Это нечто противоположное эластичности. Ну что ж, давайте снова посмотрим в код «скольжения», чтобы заметить одну важную деталь.
Когда движок определяет остаток вектора СПТ, он должен перенаправить вектор вдоль линии препятствия. Для этого проверяется, по какую сторону от линии находится центр персонажа, а затем определяется разница между углом вектора движения и углом направления линии. При этом предполагается, что угол может быть между 0 (игрок движется параллельно препятствию) и 180 (тоже параллельно, но в противоположном направлении).
И вот вопрос: а что случится, если угол между вектором движения игрока и стеной, по каким-то причинам, окажется вне этого диапазона?
if (deltaangle > ANG180)
deltaangle += ANG180;
Случится вот что: игра «в панике» попросту поменяет угол – а значит, весь вектор, на противоположный. Правда подобная ситуация невозможна, так что переживать не о чем, не так ли?
А что же произойдет, если центр игрока будет по одну сторону линии, а угол (тот самый, из которого «рисуется» вектор) – по другую сторону? Тогда при расчете вектора «скольжения» будет получен недопустимый угол, и алгоритм развернет вектор в противоположную сторону.
Но как же игрок может двигаться, если центр игрока с одной стороны линии, а угол с другой? Игрок при этом пересекает непроходимую линию, и должен, как минимум, просто застрять. Обычно так и есть, но: если вектор СПТ менее 16 юнитов и поблизости окажется линия разделения, направленная под особым углом, то угловой вектор движения пересечется с этой, находящейся на расстоянии от игрока (внутри стены) линией (смотрите схему). Затем произойдет попытка найти «остаток скольжения» и провалится из-за неверных стартовых условий. Что вызовет замену вектора на противоположный и отправит игрока в неожиданном направлении, возможно, немало удивив.
Собственно, на данный момент это все, что я хотел рассказать. Но кто знает, какие еще трюки и секреты скрывает в себе код легендарной игры?
BLACK FRIDAY ПРОДОЛЖАЕТСЯ: скидка 30% на первый платёж по промо-коду BLACK30% при заказе на 1-6 месяцев!
Это не просто виртуальные серверы! Это VPS (KVM) с выделенными накопителями, которые могут быть не хуже выделенных серверов, а в большинстве случаев — лучше! Мы сделали VPS (KVM) c выделенными накопителями в Нидерландах и США (конфигурации от VPS (KVM) — E5-2650v4 (6 Cores) / 10GB DDR4 / 240GB SSD или 4TB HDD / 1Gbps 10TB доступными по уникально низкой цене — от $29 / месяц, доступны варианты с RAID1 и RAID10), не упустите шанс оформить заказ на новый тип виртуального сервера, где все ресурсы принадлежат Вам, как на выделенном, а цена значительно ниже, при гораздо более производительном «железе»!
Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5-2650 v4 стоимостью 9000 евро за копейки? Dell R730xd в 2 раза дешевле? Только у нас 2 х Intel Dodeca-Core Xeon E5-2650v4 128GB DDR4 6x480GB SSD 1Gbps 100 ТВ от $249 в Нидерландах и США!
Mercury13
Вы ошиблись, в Doom ФИКСИРОВАННАЯ запятая.
Ошиблись именно вы, переводчик! В оригинале всё чётко.