В прошлом году я участвовал в соревнованиях JS13K 2019, на которых людям предлагается разрабатывать игры в менее чем 13 КБ кода на JavaScript. Я участвовал с клоном Doom, который назвал… «Ещё один клон Doom» (Yet Another Doom Clone).
Поиграть в него можно здесь. Исходный код выложен сюда.
Зачем создавать клон Doom?
Зачем писать FPS на JavaScript всего в 13 КБ (с учётом сжатия)? По нескольким причинам. Но лучше всего на этот вопрос отвечает раздел FAQ соревнований JS13K «Можно ли использовать WebGL?»:
«Да, но может быть сложно уместить его в 13 килобайта, если вы планируете писать FPS».
Кроме того, в то время я как раз написал 3D-рендерер и хотел поработать над ним ещё. К тому же мне нравится создавать сильно сжатый код. (Например, много лет назад я создал язык и написал компилятор для нового языка, предназначенный специально для использования в код-гольфинге.)
Именно поэтому я выбрал FPS. Остаётся вопрос: «Почему Doom?» На него ответить проще: если вы хотите написать FPS, и чтобы он при этом был небольшим, то Doom — практически самый минималистичный вариант.
Причина, по которой Doom настолько прост (по современным стандартам) понятна: Doom должен был работать на «железе» на пять порядков более медленном, чем сегодня. За ту же цену сейчас можно собрать машину, которая способна выполнять в сотню тысяч раз больше работы, чем Pentium 1994 года. Поэтому я решил, что будет интересно попробовать воссоздать нечто наподобие Doom, но вместо ограничений производительности использовать ограничения объёма кода.
Фундамент: 3D-рендерер на JavaScript
Движок игры я начал строить на основе написанного ранее 3D-рендерера, который я хотел реализовать как можно более простым. Оказалось, что благодаря своей простоте он к тому же довольно мал: ядро движка 3D-рендеринга заняло всего примерно 5 КБ сжатого JavaScript, то есть на игру осталось всего 8 КБ. Я решил, что ситуация не так уж и плоха. Если я не будут использовать большие спрайты или файлы объектов, то всё должно получиться.
Движение игрока
Для перехода от 3D-рендерера к движку 3D-игры, по сути, требуется только одно изменение: управляемое игроком движение камеры и повторный рендеринг после каждого движения. Для реализации этого я поместил игрока внутрь параллелепипеда и работал над движком, пока движение не стало правильным. Doom имел очень характерный стиль движения, который я стремился воссоздать.
Первый шаг к этому — реализация ускорения движения игрока в направлении его взгляда до какой-то (высокой) максимальной скорости. Я добавил больше ускорения, чем в оригинальном Doom, потому что сегодня это ощущается привычнее. Важнее для воссоздания ощущения Doom было добавление раскачивания камеры при движении игрока.
В состоянии постоянного движения это просто синусоида, но при переходе от неподвижности к ходьбе я добавил обязательные детали, чтобы перемещение казалось естественным.
Если ничего не добавлять, то игрок будет продолжать раскачивание с того самого состояния, в котором он находился во время остановки. Это выглядит очень неестественно. Чтобы это исправить, потребовались крошечные изменения: у игрока есть переменная текущего состояния анимации в цикле (по модулю 2 пи), и когда игрок прекращает двигаться во всех направлениях, то переменная сбрасывается на ноль. Это делает движение более чётким, а его начало и завершение выглядят правильно.
Также я добавил одну особенность, которой не было в Doom — небольшую величину поворота камеры вдоль продольной оси на каждом шаге. (В Doom его не было, потому что движок позволял выполнять поворот только по оси Z, то есть игрок даже не мог взглянуть вверх.)
Затем я добавил ограничение движения. Нет никакого смысле создавать сложные лабиринты в стиле Doom, если игрок может проходить сквозь стены. Для «правильной» реализации ограничений нужно сделать игрока сферой, стены — плоскостями и вычислять пересечения сферы с плоскостью. Я беспокоился, что это займёт слишком большую часть наших 13 КБ.
Поэтому вместо этого игра испускает восемь лучей из текущей позиции игрока и определяет, пересекается ли какой-нибудь из этих лучей со стеной. Если да, то я отталкиваю игрока назад, чтобы он оставался не менее чем в пяти единицах от этой стены. Так я реализовал распознавание коллизий сферы «для бедных», на что мне понадобилась всего сотня байтов.
Реализовать эту систему было довольно сложно, особенно обработать случаи одновременного пересечения лучей с несколькими стенами. Во некоторых ситуациях система даёт сбои, поэтому при создании дизайна уровней я вручную тестировал их на баги и проектировал их так, чтобы баги распознавания коллизий не возникали. (Главное ведь, чтобы работало...)
Object Lathing
Чтобы в игре были объекты, мне нужно каким-то образом их описать. Логичным способом было бы использование формата файлов .obj. К сожалению, он довольно большой и неуклюжий. (Я использовал его в своём предыдущем 3D-рендерере для загрузки стандартного чайника.)
Поэтому вместо него я решил написать минималистичный метод «точёных» объектов (object lathe):
мы задаём 2D-контур, представленный в виде ряда точек, обтачиванием вращаем точки по кругу для генерации 3D-объекта. Это позволяет создавать красивые объекты, занимающие мало пространства. Например, для описания показанного выше кувшина потребовалось примерно двадцать байтов.
Задолго до разработки игры я также создал тщательно минимизированную до 300 байт реализацию подразделения поверхностей (surface subdivisioning) (которую ранее использовал для 3D-рендерера). Но в конечном итоге мне не хватило места и от неё пришлось отказаться. Однако я особо не жалею, потому что она не добавляла в игру ничего важного.
Игровой цикл
Всё описанное выше было довольно статичным, по миру перемещалась только камера. Однако для создания игры требуется интерактивность. И здесь нам пригодится игровой цикл.
Мы будем использовать совершенно стандартный игровой цикл. Изначально в коде он выглядел так:
function game_step(now) {
if (game_is_over) return;
frame = requestAnimationFrame(game_step);
player_check_dead();
player_move();
player_clip_walls();
player_fall();
player_set_position();
lights.map(light => light.compute_shadowmap());
camera.draw_scene();
objects.map(object => object.update(dt));
garbage_collect();
}Да, это красивый и удобный код, но каждая из функций вызывается только один раз. Поэтому они превратились во встроенные функции, и цикл стал некрасивым.
Оружие и враги
Шутер от первого лица не особо интересен, если нам нечем и не в кого стрелять.
Я начал с реализации стрельбы. Я не был уверен, хватит ли у меня места на несколько видов оружия (в результате его и не хватило), поэтому решил, что в шутере логично будет использовать пулемёт (chaingun) из Doom.
Модель оружия — это просто несколько цилиндров, созданных при помощи object lathe. Первым этапом здесь была реализация естественного движения с оружием. Для этого я снова воспользовался уже имеющимся отслеживанием движения вверх-вниз при ходьбе: пулемёт движется вверх-вниз и в стороны, в зависимости от текущего состояния цикла ходьбы игрока.
Следующим обязательным этапом стала реализация правильных ощущений от самой стрельбы. Она состоит из трёх компонентов. Во-первых, при стрельбе возникает небольшая отдача. Во-вторых, оружие вращается. В-третьих, при каждом выстреле появляется небольшая вспышка. Всё это хорошо влияет на ощущения от игры, которая посвящена стрельбе.
Распознавание попаданий реализовано как простое сканирование испускаемым лучом (в нём используется тот же код, что и в распознавании коллизий со стенами при движении игрока). При попадании создаются частицы взрыва с небольшой вспышкой.
Для сканирования попаданий пришлось внести в систему испускания лучей несколько изменений. Во-первых, поскольку первая версия проверяла коллизии только по горизонтали, мне нужно было теперь проверять, произошла ли коллизия на нужной высоте по Z. Это сделать было не особо сложно: вычисляем, насколько далеко объект от игрока, из наклона игрока по поперечной оси определяем, какой должна быть высота пули, и если она находится в пределах ограничивающего параллелепипеда объекта, то коллизия произошла.
(Чтобы можно было стрелять по потолку и полу, потребовалось ещё одно небольшое дополнение. В противном случае при высоком прицеливании не было бы взрывов, и это казалось бы неправильным. Вся остальная система распознавания коллизий определяет коллизии только по горизонтали, а эти коллизии ориентированы по вертикали, а значит, им требуется специализированный код. На самом деле, написать его было не так сложно: записываем начальную высоту по Z и наклон игрока по поперечной оси (угол относительно плоскости xy), а затем для каждого полигона всей карты проверяем, насколько далеко должен растянуться луч, чтобы попасть по потолку и полу этого полигона; затем проверяем, действительно ли при движении луча на такое расстояние он сталкивается с полигоном в этом месте.)
После этого я сортирую все потенциальные коллизии и выбираю ближайшую.
Для стрельбы также требуется тряска экрана, и, поскольку в игре нет боеприпасов, замедление движения игрока. Важно, чтобы у игрока была причина не держать всю игру палец на спусковом крючке.
Затем я перешёл к задаче стрельбы по врагам. Сначала я создал очень простую модель-коробку персонажа. Он полностью состоит из кубов, благодаря чему его очень легко хранить: сохраняя просто модель куба, я могу растягивать его в произвольных направлениях и создать врага. Простейший враг состоит из восьми кубов.
Сначала анимация смерти была очень простой, враги всего лишь падали на землю. Это выглядело неплохо, но стрельба ощущалась слабой и скучной. Поэтому я внёс несколько изменений: враг запоминает каждый из составляющих его кубов и при попадании взрывается на части. Это выглядит гораздо лучше.
Сначала блоки, из которых состоял враг, просто разлетались сквозь стены и пропадали с экрана. Это сбивало с толку, поэтому я добавил эффект отскакивания блоков от стен. Если говорить кратко, то отскоки совершенно физически недостоверны. Коллизии снова реализованы при помощи пересечения лучей. Если ближайшая стена полностью находится на плоскости xz, то объекты меняют знак свой скорости по y. Если стена полностью на плоскости, то меняется знак скорости по x. Во всех остальных случаях меняются знаки скоростей по x и y.
Когда позиция объекта меньше, чем высота пола текущей комнаты, скорость по z меняет свой знак и уменьшается на 20%. Каждую секунду объект замедляется на 50% (как будто к нему применяется какое-то гипотетическое трение).
ИИ врагов
Несмотря на то, что я изучал и имел дело в работе с "«ИИ»" (со множеством кавычек), враги в игре довольно неинтеллектуальны. У врагов есть позиция и поворот. Они постоянно ходят туда и обратно, пока не пробудятся по одной из двух причин:
(а) игрок находится в поле их зрения
или
(б) игрок подстреливает врага, находящегося в поле зрения.
Определение поля зрения тоже реализовано при помощи испускания лучей. Чтобы не тратить впустую такты ЦП на испускание лишних лучей, враг проверяет других врагов всего раз в секунду.
После пробуждения враг начинает двигаться к игроку по прямой. Если на его пути что-то встаёт, то он выбирает новое случайное направление и делает несколько шагов, а затем снова начинает двигаться к игроку. Иногда движущиеся враги стреляют по игроку.
Кроме того, в момент смерти враг запрашивает помощь у других врагов, которых может видеть (снова при помощи испускания лучей). Благодаря этому сложно устранять врагов по одному из-за угла, потому что это скучная механика, и не стоит её поощрять.
Текстуры
Пока картинка выглядит очень скучной, ведь используется всего одна текстура. Я знал, что никак не смогу уместить в игру нарисованные от руки текстуры, даже самые маленькие, поэтому сгенерировал их процедурно. Я решил использовать всего три текстуры: плитки пола, кирпичный паттерн для стен и простой шум Перлина для лавы и взрывов.
Генерация кирпичей довольно тривиальна. Отрисовываем горизонтальные линии через каждые N шагов, а затем вертикальные линии через каждые N со смещением на N/2 в чётных строках. Код выглядит так:
make_texture(cartesian_product_map(range(256),range(256),(y,x) => {
if ((y%64) <= 2 || Math.abs(x-(((y/64)|0)%2)*128) <= 2) {
return [0,0,0,1];
} else {
var r = .9-perlin_noise[x*256+y]/20;
return [r,r,r,1];
}
}).flat())С генерацией плиток всё чуть сложнее. Сначала я создал шестиугольную решётку, а затем для каждого пикселя плитки я вычисляю расстояние до ближайших двух точек решётки. Если расстояние до ближайшей точки равно удвоенному расстоянию до второй по близости, то рисуем линию. Так мы получаем стандартный паттерн из плиток.
Шум Перлина визуально гораздо красивее, чем другие типы шумов. Его случайность выглядит намного естественнее, чем простой белый шум. Генерация шума Перлина довольно сложна, поэтому я просто дам ссылку на Википедию и скажу, что сделал так же. Также я добавил небольшое количество шума Перлина к кирпичному паттерну, чтобы он был менее скучным.
Анимации врагов
Простое скольжение врагов по карте выглядит не особо интересным, поэтому я добавил анимацию ходьбы. Она заняла на удивление мало места и заключалась в движении конечностей как маятников.
Один тип врагов — это слишком скучно, поэтому затем я добавил небольшого летающего врага, он быстрее движется и в него сложнее попасть. Внешний вид его опять-таки очень минималистичен: это просто две похожие на крылья трапецоида и прямоугольное тело. Чтобы показать, что он как будто летает, враг немного машет крыльями и раскачивается вверх-вниз; здесь снова используется код анимаций шагающего врага.
Звук
Казалось очевидным, что для добавления звука нужно использовать JSFXR, однако на этом этапе места уже начинало не хватать. Взглянув ещё раз на код, я увидел, что ещё многое можно оптимизировать.
Благодаря последовательности небольших изменений мне удалось сократить его почти в два раза. Самая большая экономия получилась благодаря удалению map из массива в воспроизводимый файл WAV и замене его на вызов функции WebAudio, получающей непосредственно массив float. Ещё одна серьёзная экономия получилась благодаря замене куче операторов case на операции поиска в массиве. То есть я реализовал принцип мультиплексора и вычислил все возможные случаи внутри массива, а затем просто выбирал индекс нужного значения. Это медленнее, зато код короче. После замены циклов for на map и создания вспомогательной функции clamp код оказался достаточно коротким, чтобы можно было написать красивые звуковые эффекты.
Затем я захотел сделать так, чтобы аудиосистема реагировала на то, где находится игрок в 3D-пространстве. Я думал, что эта часть потребует много усилий, но оказалось, что это довольно просто, и теперь в коде есть функция createStereoPanner, выполняющая эту задачу.
В качестве фоновой музыки я переписал среднюю часть токкаты и фуги ре минор. Она просто повторяется бесконечно.
Описание карты
Одной из уникальных особенностей Doom были уровни. Каждая карта больше напоминала лабиринт, по которому игрок бегал в поисках выхода. Для создания клона это был обязательный компонент.
Однако для простого хранения карт потребовалось бы слишком много места: при наивном задании (т.е. при сохранении позиций всех стен) даже несколько простейших уровней занимали более килобайта. Поэтому карты записываются как набор многоугольников (которые могут быть и вогнутыми). У каждого многоугольника есть высота пола и потолка, а если два соседних многоугольника имеют общее ребро, то игрок может пройти из одного в другой (иногда спускаясь ниже или поднимаясь).
Для создания кода, превращающего многоугольники в трёхмерные комнаты, потребовалось довольно много усилий. Хоть и легко разместить стены вокруг каждого многоугольника, основной сложностью стало определение того, когда стены быть не должно из-за двух соседних рёбер. Чтобы упростить процесс, проём создаётся только тогда, когда у двух стен обе координаты совпадают точно.
Изначально я создавал карты, вручную задавая координаты многоугольников, но у такого подхода было две проблемы: во-первых, они занимали много места, и, что более важно, на создание тратилась куча времени. Если я хотел успеть спроектировать достаточное количество карт, то нужно было придумать что-то получше.
Возможно, хорошая идея позволит одновременно решить обе проблемы. Я реализовал очень крошечный язык программирования turtle для задания расположения областей карты. То есть вместо использования черепашки для рисования я применил её для создания многоугольников, заменив карандаш функцией задания многоугольников. Изначально этот язык был очень похож на реализацию принципа черепашки: команды перемещали черепаху, поворачивали её и заставляли двигаться на определённое расстояние.
Я даже добавил функции, позволяющие создавать циклы for и вызовы/возвраты, чтобы можно было, например, изготавливать лестницы, а затем многократно применять функцию make-stairs там, где мне были нужны лестницы.
К сожалению, проектировать карты всё равно было сложно, потому что для этого требовалось программирование черепашки на языке ассемблера, который разрабатывался как максимально компактный. У меня был всего месяц на создание всей игры, поэтому я никак не мог себе позволить потратить несколько дней на проектирование карт. Более того, на самом деле это не экономило особо много пространства. Так как ограничение в 13 килобайта относится к размеру запакованного zip исходного кода, вполне можно было использовать дублирование одной функции: сжатие zip сэкономит пространство.
Поэтому код черепашки стал таким:
function run_turtle(commands) {
var regions = []
var turtle_location = [ZERO];
var floor_height = 4;
var ceil_height = 40;
var do_later = [];
for (var i = 0; i < commands.length;) {
var cmd = commands[i++];
// Get the "opcode" and "argument" to the command
var [low, high] = [cmd&31, cmd>>5];
// Opcode 0 is a "make polygon" command
if (high <= 1) {
var coordinates = [turtle_location[0]]
coordinates.push(...range(low).map(x=> {
var dydx = NewVector(((commands[i]>>4)-7)*8,
((commands[i++]%16)-7)*8, 0)
turtle_location.unshift(turtle_location[0].add(dydx));
return turtle_location[0];
}));
regions.push(new MapPolygon(coordinates,
floor_height,
ceil_height))
// Opcode 1 is a "goto" command
if (high == 1) {
regions.pop();
}
}
// Opcodes 4: adjust ceiling
floor_height += 2*(low-15)*(high==4);
// Opcodes 5: adjust floor
ceil_height += 4*(low-15)*(high==5);
// Opcodes 6: backtrack
turtle_location.splice(0,low*(high==6));
}
return [regions, do_later];
}Чтобы упростить создание карт, я избавился от большей части языка и создал гораздо более простой язык. Я убрал циклы, вызовы функций, повороты и реализовал всего два опкода: make-polygon и goto. Опкод make-polygon получает количество вершин и последовательность байтов, где старшие 4 бита определяют сдвиг по оси x, а младшие 4 бита — сдвиг по оси y. После достижения последней вершины цикл завершается и черепашка создаёт многоугольник. Опкод move просто перемещает черепашку в новое место для создания нового многоугольника.
После создания нескольких карт я посмотрел, какие части моего языка turtle занимают больше всего места. Я понял, что трачу много места на перемещение черепашки от многоугольника к многоугольнику. Как можно сократить этот процесс? Обратим внимание, что обычно многоугольники не изолированы: они соединяются с другими многоугольниками вершиной. Поэтому я добавил ещё одну функцию backtrack. При каждом движении черепашки она добавляет своё местоположение в стек. Backtrack извлекает позицию черепашки определённое количество значений назад. Это очень эффективно: более 95% перемещений черепашки было заменено командами backtrack.
Редактор карт
Для удобства создания карт я быстро набросал WYSIWYG-интерфейс. Этот редактор компилирует карты на язык turtle, чтобы их можно было использовать в игре.
Обновление карты в редакторе в реальном времени обновляет рендерящуюся игру, чтобы я сразу видел, что происходит. В видео показан процесс создания новой карты.
Так как этот редактор не будет находиться в составе игры, я мог не волноваться о качестве кода или удобстве редактора. Он невероятно уродлив и некрасив, в нём используются непонятные горячие клавиши. (Хотите добавить новый многоугольник? Выберите созданную вершину и нажмите Shift-A для выделения соседнего ребра, а затем E (для экструдирования). Хотите добавить вершину к уже существующему ребру? Shift-A и S (для разбиения). Нужно удалить многоугольник? Shift-Q. Если знать, что делать, то всё вполне логично, но не особо интуитивно понятно.)
Мысли об экономии пространства
Для успешного создания полной игры в 13 килобайтах сжатого JavaScript требуется постоянно помнить о занимаемом кодом пространстве.
Основная цель заключается в том, чтобы всегда понимать размер кода. Я загрузил скрипт на Python для отслеживания каждого изменения файла исходников и пересборки пакета. Он показывал количество свободных байтов, оставшихся для самой игры, чтобы они всегда были видимы и я мог понять, стоит ли внесённое изменение повышения сложности.
Пригодилось и то, что я написал множество вспомогательных функций, которые использовал во многих частях программы. Вот некоторые из них, которые я считаю наиболее полезными:
var pairs = (lst,fn) => lst.slice(0,-1).map((x,i)=>fn(x,lst[i+1],i))
var transpose = (mat) => mat[0].map((x,i) => mat.map(x => x[i]))
var range = (N,a) => Array(N).fill().map((_,x)=>x+(a||0));
var reshape = (A,m) =>
range(A.length/m).map(x=>A.slice(x*m,(x+1)*m));
var urandom = _ => Math.random()*2 - 1;
var push = (x,y) => (x.push(y), x);
var clamp = (x,low,high) => Math.min(Math.max(low, x), high)
var sum = (x) => x.reduce((a,b)=>a+b)Также я реализовал собственную математику для матриц и векторов, чтобы код был максимально сжатым. Все повороты задаются как произведения матриц 4x4: гораздо более эффективными были бы кватернионы, но они занимают больше места, поэтому я их не использовал.
В самом некрасивом моём коде я сделал так, что умножения матриц 4x4 стали и очень эффективными, и одновременно очень короткими; для этого пришлось потрудиться:
var mat_product_symbolic = B =>
`(a,b)=>[${reshape(range(16),4).map(c=>B[0].map((_,i)=> B.reduce((s,d,j)=>`${s}+b[${d[i]}]*a[${c[j]}]`,0))).flat()}]`;
multiply = eval(mat_product_symbolic(reshape(range(16),4));Для постоянного отображения текущего размера сборки требовался автоматизированный процесс сборки. Сначала скрипт сборки просто запускал uglifier, за которым выполнялся стандартный zip, чтобы я мог отслеживать занимаемое пространство. Вскоре я осознал, что есть оптимизации, которые позволят мне автоматизировать процесс, чтобы ещё больше сжать код. Я написал короткий скрипт, определяющий все имена переменных webgl и заменяющий их короткими однобуквенными именами (потому что uglify этого не делал). Затем я модифицировал эту программу так, чтобы она переписывала длинные имена функций WebGL, например, framebufferTexture2D, коротким трёхсимвольным кодом вида e2m (я брал восьмой символ с конца, второй символ с конца и третий символ с начала). Ближе к концу разработки я узнал о advzip, который ещё больше помог мне с улучшением сжатия.
Автор: PatientZero
