Движок для игры от первого лица в 265 строках Javascript

Сегодня окунёмся в мир, который можно потрогать. В этой статье мы исследуем, как с нуля, быстро и без особо сложной математики написать движок для игры от первого лица. Для этого мы воспользуемся приёмом под названием «бросание лучей» (raycasting). Возможно, вы видели примеры такой техники в играх Daggerfall ^[1] и Duke Nukem 3D ^[2], а из более свежего – в статьях из «ludum dare» от Нотча Перссона ^[3]. Что ж, для Нотча это неплохо, но не для меня! Вот демка (управление стрелками и тачпадом) [источник] ^[4].

Бросание лучей может показаться жульничеством, но я – ленивый программист, и мне этот метод очень нравится. Достигается погружение в трёхмерную среду, минуя многие сложности «реального 3D», которые могли бы замедлять разработку. Например, время, затрачиваемое на бросание луча – это константа, поэтому можно загрузить огромный мир, и он просто заработает без каких-либо оптимизаций, как заработал бы и маленький. Уровни определяются в виде простых клеточных гридов, а не деревьев или полигональных сеток, так что в такой мир можно погрузиться, даже не имея опыта 3D-моделирования или математического диплома.

Словом, техника удивительно простая. Через пятнадцать минут вы уже будете фотографировать стены в офисе и проверять в корпоративных документах, «запрещено ли программировать имитацию перестрелок на рабочем месте».

❯ Игрок

Откуда будем бросать лучи? Это – важнейший аспект создания игрока. Нам понадобится всего три свойства, x, y и направление.

function Player(x, y, direction) {
  this.x = x;
  this.y = y;
  this.direction = direction;
}

❯ Карта

Сохраним нашу карту как простой двумерный массив. В этом массиве 0 соответствует нет стены, а 1 соответствует стена. Конечно, можно сделать и гораздо сложнее… например, отображать стены произвольной высоты или упаковать в массив несколько «слоёв» данных о стенах. Но в качестве пробы пера вариант 0-или-1 подойдёт отлично.

function Map(size) {
  this.size = size;
  this.wallGrid = new Uint8Array(size * size);
}

❯ Бросаем луч

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

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

1. Найдите угол для каждого луча

Сначала найдём угол, под которым бросаем каждый луч. Угол зависит от трёх факторов: направления, в котором смотрит пользователь, фокусного расстояния камеры, а также от того, какой столбец мы сейчас отрисовываем.

var x = column / this.resolution - 0.5;
var angle = Math.atan2(x, this.focalLength);
var ray = map.cast(player, player.direction + angle, this.range);

2. Прослеживаем каждый из лучей по клеткам

Далее для каждого луча нужно проверить, есть ли у него на пути стены. Наша цель – получить массив, в котором перечислены все стены, оказывающиеся на пути луча, исходящего от игрока.

Считая игрока началом координат, найдём ближайшую горизонтальную (stepX) и вертикальную (stepY) линии сетки. Движемся к той из них, которая находится ближе, и проверяем, нет ли на этой линии стены (inspect). Затем повторяем процесс, пока не проследим луч на всю длину.

function ray(origin) {
  var stepX = step(sin, cos, origin.x, origin.y);
  var stepY = step(cos, sin, origin.y, origin.x, true);
  var nextStep = stepX.length2 < stepY.length2
	? inspect(stepX, 1, 0, origin.distance, stepX.y)
	: inspect(stepY, 0, 1, origin.distance, stepY.x);
 
  if (nextStep.distance > range) return [origin];
  return [origin].concat(ray(nextStep));
}

Находить пересечения линий в сетке просто: смотрим, где значения x являются целыми числами (1, 2, 3, т. д.). Затем находим соответствующий y, умножив это значение на уклон линии (вверх / вниз).

var dx = run > 0 ? Math.floor(x + 1) - x : Math.ceil(x - 1) - x;
var dy = dx * (rise / run);

Заметили, что в этой части алгоритма самое классное? Нас вообще не волнует размер карты! Мы смотрим только конкретные точки в сетке, а количество таких точек в каждом кадре примерно равное. В нашем примере рассматривается карта 32 x 32, но карта размером 32 000 x 32 000 пробегалась бы так же быстро!

3. Отрисовка столбца

Выполнив трассировку луча, мы должны отрисовать все стены, которые нашли у него на пути.

  var z = distance * Math.cos(angle);
  var wallHeight = this.height * height / z;

Высоту каждой стены определяем, разделив её максимальную высоту на z. Соответственно, чем дальше от нас стена, тем короче мы её отрисуем.

Ох, чёрт, а откуда же взялся этот косинус? Если учитывать только дистанцию от игрока как таковую, то у нас получится эффект «рыбьего глаза». Почему? Представьте, что смотрите на стену. Левый и правый края стены будут от вас дальше, чем её центральная часть. Но вы же не хотите, чтобы прямые стены посередине вспучивались! Чтобы отображать стены плоскими, такими, как мы их реально видим, строим треугольник на основе каждого луча и находим длину перпендикуляра до стены, а для этого нужен косинус. Вот так:

Обещаю, самая сложная математика в статье уже пройдена!

❯ Теперь отобразим всё это!

Воспользуемся объектом Camera, чтобы отрисовать карту каждого кадра с точки зрения игрока. Именно этот объект отвечает за отображение каждой полосы при смахивании на экране слева направо или справа налево.

Прежде, чем отрисовать стены, отобразим скайбокс – это просто большая картинка на заднем плане, на которой есть звёзды и горизонт. Закончив с созданием стен, бросим на переднем плане оружие.

Camera.prototype.render = function(player, map) {
  this.drawSky(player.direction, map.skybox, map.light);
  this.drawColumns(player, map);
  this.drawWeapon(player.weapon, player.paces);
};

Самые важные свойства камеры – это разрешение, фокусное расстояние и дальность.

• Разрешение определяет, сколько полос мы рисуем в каждом кадре, то есть, сколько лучей отбрасываем.
• Фокусное расстояние определяет ширину объектива, через который мы смотрим, а значит – и углы, под которыми расходятся лучи.
• Дальность определяет, насколько далеко «видит» камера, то есть, максимальную длину каждого луча.

❯ Подытожим

При помощи объекта Controls будем слушать клавиши со стрелками (и события касания), а объект GameLoop будет вызывать requestAnimationFrame. Наш простой игровой цикл укладывается всего в три строки:

loop.start(function frame(seconds) {
  map.update(seconds);
  player.update(controls.states, map, seconds);
  camera.render(player, map);
});

❯ Детали

Дождь

Дождь можно симулировать, расставив в случайных точках множество очень коротких стен.

var rainDrops = Math.pow(Math.random(), 3) * s;
var rain = (rainDrops > 0) && this.project(0.1, angle, step.distance);
 
ctx.fillStyle = '#ffffff';
ctx.globalAlpha = 0.15;
while (--rainDrops > 0) ctx.fillRect(left, Math.random() * rain.top, 1, rain.height);

Вместо того, чтобы рисовать такие стены в полную ширину, мы рисуем каждую из них в один пиксель.

Освещение и молнии

Фактически, здесь освещение – это затенение. Все стены рисуются в полную яркость, а потом стена накрывается чёрным прямоугольником с некоторым показателем непрозрачности. Непрозрачность зависит от расстояния, а также от ориентации стены (север/юг/восток/запад).

ctx.fillStyle = '#000000';
ctx.globalAlpha = Math.max((step.distance + step.shading) / this.lightRange - map.light, 0);
ctx.fillRect(left, wall.top, width, wall.height);

Чтобы симулировать молнию, задаём для map.light случайные всплески до 2 с последующим быстрым затуханием.

Обнаружение столкновений

Чтобы пользователь не мог проходить сквозь стены, мы просто проверяем по карте, каково будет его следующее положение. Проверка по осям x и y проводится независимо, так, чтобы пользователь мог скользить вплотную к стене:

Player.prototype.walk = function(distance, map) {
  var dx = Math.cos(this.direction) * distance;
  var dy = Math.sin(this.direction) * distance;
  if (map.get(this.x + dx, this.y) <= 0) this.x += dx;
  if (map.get(this.x, this.y + dy) <= 0) this.y += dy;
};

Текстуры стен

Без текстур стены могут выглядеть достаточно уныло. Как узнать, какой элемент стенных текстур применить к конкретному столбцу? На самом деле, это весьма просто: берём остаток от значения в точке пересечения.

step.offset = offset - Math.floor(offset);
var textureX = Math.floor(texture.width * step.offset);

Например, ширина пересечения со стеной в точке (10, 8.2) даёт остаток 0,2. Таким образом, точка пересечения на 20% удалена от левого края стены (8) и на 80% от правого края (9). Поэтому умножаем 0.2 * texture.width, чтобы найти координату x для текстурного изображения.

❯ Попробуйте сами

Погуляйте в жутких руинах ^[4].

Что дальше?

Поскольку механизмы бросания лучей такие простые и быстрые, с ними можно оперативно протестировать сразу множество идей. Можно покататься на пещерном вездеходе, написать шутер от от первого лица или сделать песочницу для игры в стиле GTA. Мне вообще постоянно хочется запилить олдскульную MMORPG с огромным процедурно генерируемым миром.

Сделайте форк ^[5]!

Вот вам несколько заданий, чтобы потренироваться:

• Иммерсия. В этом примере просто напрашивается полноэкранный режим с блокировкой мыши. На фоне сцены пусть идёт дождь и слышатся раскаты грома, синхронизированные со вспышками молний.
• Оптимизация. Здесь открывается масса возможностей ускорить программу – начиная с кэширования идентичных вызовов Math.atan2 и Math.cos, которые сотни раз делаются в каждом кадре.
• Уровень «в помещении». Замените скайбокс симметричным градиентом или, если не боязно, попробуйте отобразить замощение пола и потолка (представьте, что пол и потолок – это просто зоны между стенами, которые вы и так уже рисуете!)
• Подсветка объектов. У нас уже хорошо проработана модель освещения. Почему бы не разместить в игровом мире источники света и, в зависимости от их положения, не вычислить степень освещённости стен? Свет – это 80% игровой атмосферы.
• Улучшить качество касаний. Я смог внедрить в игру пару простейших сенсорных элементов управления, так что, ребята с телефонами и планшетами – можете попробовать демку. Здесь есть огромный простор для доработок.
• Эффекты камеры. Например, увеличение, размытие, пьяный режим, пр. Технология бросания лучей на удивление упрощает все эти вещи. Для начала попробуйте модифицировать camera.fov в консоли.