Сегодня окунёмся в мир, который можно потрогать. В этой статье мы исследуем, как с нуля, быстро и без особо сложной математики написать движок для игры от первого лица. Для этого мы воспользуемся приёмом под названием «бросание лучей» (raycasting). Возможно, вы видели примеры такой техники в играх Daggerfall и Duke Nukem 3D, а из более свежего – в статьях из «ludum dare» от Нотча Перссона. Что ж, для Нотча это неплохо, но не для меня! Вот демка (управление стрелками и тачпадом) [источник].
Бросание лучей может показаться жульничеством, но я – ленивый программист, и мне этот метод очень нравится. Достигается погружение в трёхмерную среду, минуя многие сложности «реального 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 для текстурного изображения.
❯ Попробуйте сами
Погуляйте в жутких руинах.
Что дальше?
Поскольку механизмы бросания лучей такие простые и быстрые, с ними можно оперативно протестировать сразу множество идей. Можно покататься на пещерном вездеходе, написать шутер от от первого лица или сделать песочницу для игры в стиле GTA. Мне вообще постоянно хочется запилить олдскульную MMORPG с огромным процедурно генерируемым миром.
Сделайте форк!
Вот вам несколько заданий, чтобы потренироваться:
- Иммерсия. В этом примере просто напрашивается полноэкранный режим с блокировкой мыши. На фоне сцены пусть идёт дождь и слышатся раскаты грома, синхронизированные со вспышками молний.
- Оптимизация. Здесь открывается масса возможностей ускорить программу – начиная с кэширования идентичных вызовов Math.atan2 и Math.cos, которые сотни раз делаются в каждом кадре.
- Уровень «в помещении». Замените скайбокс симметричным градиентом или, если не боязно, попробуйте отобразить замощение пола и потолка (представьте, что пол и потолок – это просто зоны между стенами, которые вы и так уже рисуете!)
- Подсветка объектов. У нас уже хорошо проработана модель освещения. Почему бы не разместить в игровом мире источники света и, в зависимости от их положения, не вычислить степень освещённости стен? Свет – это 80% игровой атмосферы.
- Улучшить качество касаний. Я смог внедрить в игру пару простейших сенсорных элементов управления, так что, ребята с телефонами и планшетами – можете попробовать демку. Здесь есть огромный простор для доработок.
- Эффекты камеры. Например, увеличение, размытие, пьяный режим, пр. Технология бросания лучей на удивление упрощает все эти вещи. Для начала попробуйте модифицировать camera.fov в консоли.
Комментарии (28)
Kodzo
27.06.2023 14:48+1Не трогал серьёзно JS, но каждый раз поражаюсь, что может язык созданный буквально на коленке.
iburanguloff
27.06.2023 14:48-5PHP был создан на коленке, но не JS
Kodzo
27.06.2023 14:48+7Разве не js описали за 10 дней?
MadeByFather
27.06.2023 14:48А ничего, что с тех пор прошло -цать лет и изначальная версия была на 110 страниц, а текущая спека на 840?
И даже для первой версии это мягко говоря преувеличиние, что он написан на коленке.
https://www.ecma-international.org/publications-and-standards/standards/ecma-262/
Wesha
27.06.2023 14:48+1А лично я каждый раз поражаюсь, сколько
электричества портитбесполезной работы (то есть не относящейся непосредственно к решаемой задаче) — вроде выделения-освобождения памяти, создания-уничтожения объектов и т.п. — выполняет JS (да и любой другой интерпретируемый язык).
DaneSoul
27.06.2023 14:48+15Эта работа необходимая, я бы даже сказал неизбежная.
Просто в одних языках ради максимальной производительности ее делает сам программист, тратя свое время и силы, а в других ему работу облегчили и это делает интерпретатор языка, расплачиваясь большим потреблением ресурсов.
Оба подхода правильные - разным задачам, разные инструменты.Wesha
27.06.2023 14:48+1в одних языках ради максимальной производительности ее делает сам программист, тратя свое время и силы
Как говорил один мой знакомый, "это только первые двести раз — а потом привыкаешь, втягиваешься, и делаешь всё, что надо, на автомате".
bolk
27.06.2023 14:48+6А потом мы читаем в CVE про ошибки двойного освобождения или ловим утечки.
Wesha
27.06.2023 14:48+3А потом мы читаем в CVE
А ведь я говорил — два стека надо делать было! Дык нет — запихали пользовательские данные вперемешку с адресами возврата — теперь разгребают.
pennanth
27.06.2023 14:48+1Тогда уж надо было делать 2 памяти: для кода и для данных. И даже тогда будут баги, когда в ОС передали не тот указатель и в итоге данные утекли в код.
Wesha
27.06.2023 14:48Тогда уж надо было делать 2 памяти: для кода и для данных
Эту Вашу идею уже украли!
superconductor
27.06.2023 14:48+12Не грустите сильно по поводу JS - ребята из Гугла и мозилы сделали довольно много чтобы не считать его "интерпретируемым" в чистом виде, да и нет в нормально написано коде лишних созданий-уничтожений объектов, т.к. передача объектов по ссылке.
А бэкенды-перекладыватели-json'ов сам скотч велел писать на JS.
Впрочем по поводу зря сожженных ресурсов я лично впадаю в уныние от косоруких программистов, которые не умеют делать фронтенд без реакта, и этот самый реакт теперь на каждом втором сайте отжирает память и CPU просто так.
GrandLegion
27.06.2023 14:48Шаблонное обучение выпускает шаблонных программистов, шаблонные программисты не способны творить новое и понимать как всё работает, как следствие оптимизировать. К сожалению современным миром управляют деньги, кто платит, тот и заказывает. А на реакте можно выпустить говнецо гораздо быстрее, чем хороший программист постарается. Больше всего бесит во всём этом, что стадо шаблонщиков считает себя программистами и просят за это хорошие зарплаты
PuerteMuerte
27.06.2023 14:48+2После коленок там прошло четверть века профессиональной и интенсивной разработки.
DeepFakescovery
27.06.2023 14:48+1жаль только браузеры жрут как не в себя . Поэтому создавать что-то серьезное для веба чуть менее чем хочется.
acordell
27.06.2023 14:48+12Спасибо, неплохой перевод! Статейка только старенькая, 9 лет уже исходникам на гидхабе и они не очень совпадают что со статьей, что с опубликованной страничкой, где можно побегать. Но прикольно. Все равно все в несколько строк.
azTotMD
27.06.2023 14:48Интересно, насколько сложно добавить объекты и анимированных персонажей, чтобы корректно отрисовывались даже если из-за угла стены видна только их часть?
Подумываю сделать такой клиент для своего сетевого проекта.
shiru8bit
27.06.2023 14:48+1В таких рейкастерах объекты рисутся столбцами, как и стены, как бы по Z буферу, только не он не попиксельный, а постолбцовый - таким образом легко решается проблема отрисовки объектов за углом стены. Главная проблема с объектами в рейкастере в том, что они отдельная от стен сущность, с совсем другой математикой и принципом работы (типа классического 3D, крутим точки в мировых координатах согласно камере, проецируем в экран), и получается, что по сути нужно подружить два разнородных движка. Поэтому многие, кто пробует делать рейкастер, останавливаются на стенах. Не то, чтобы это было сложно, просто внезапно оказывается, что всё, что было изучено и понято для отрисовки стен, к объектам отношения не имеет, и надо понимать заново.
А если нужна ещё и текстура пола-потолка - то это ещё одна отдельная история, а если разновысотность и диагональные стенки - то третья, а если карта не по сетке - то четвёртая. И все эти разнородные вещи нужно совмещать. В этом смысле полигональный рендер типа Quake устроен значительно проще.
azTotMD
27.06.2023 14:48Круто! Спасибо за развернутый ответ
они отдельная от стен сущность, с совсем другой математикой и принципом работы
а нельзя тут использовать спрайтовую логику? т.е. просто взять картинку с прозрачным фоном, отмасштабировать её с учетом дальности, обрезать если торчит из-за стены и ляпнуть на вычисленное место? Еще бы конечно здорово, если поддерживались гифки, можно было сразу анимированные спрайты фигачить, но это больше вопрос к элементу canvas.
А если нужна ещё и текстура пола-потолка
Да текстура пола не помешала бы. Возможность замостить разными плитками.
а если карта не по сетке - то четвёртая
С этим у меня, к счастью, проблем нет. У меня всё на квадратной дискретной сетке. Сейчас у меня игра отрисовывается как вид сверху, очень удобно реализовать. Если кто-то поворачивается - просто крутануть картинку. Здесь получается нужны разные спрайты для этого. Было бы конечно круто к клиенту с видом сверху добавить клиент вот с таким псевдо-3Д. Одна игра с такими разными представлениями, просто разрыв шаблона
shiru8bit
27.06.2023 14:48+1С объектами в рейкастере две проблемы. Более простая - как рисовать. Это по сути и есть спрайтовая логика, только спрайт рисуется не сразу весь целиком, а столбцами в один пиксель шириной. В зависимости от глубины спрайта в сцене (на весь спрайт одна глубина) и глубины уже нарисованной в этом столбце пикселей стены можно определить, нужно ли рисовать столбец спрайта (если стена ближе спрайта, он за ней, его не видно). Более сложная проблема - что и где рисовать. Найти объекты на карте трассировкой лучей не получится, если конечно они не двигаются по клеткам, а плавно. Надо спроецировать их в экран, то есть каждый спрайт повернуть на угол камеры, сделать 3D проекцию, отсечь лишние спрайты (хотя бы за спиной), отсортировать оставшиеся по дальности, и тогда уже рисовать - всё как в традиционных 3D движках.
azTotMD
27.06.2023 14:48Найти объекты на карте трассировкой лучей не получится, если конечно они не двигаются по клеткам, а плавно
К счастью у меня всё дискретно. Объекты находятся на клетках и не могут занимать промежуточных положений. По сути - это разновидность стен, только прозрачные для дальнейшего распространения взгляда. Думаю, это сильно упрощает задачу
Надо ещё правильно сделать порядок отрисовки, чтобы дальние объекты не рендерились раньше ближних
shiru8bit
27.06.2023 14:48+1Тогда должно быть попроще. Это примерно как устроены двери и диагональные стены в подобных движках. - особый случай клетки, в которой трассировка не прекращается. Для объектов понадобится запоминать их по мере трассировки и потом рисовать в обратном порядке, чтобы они корректно накладывались друг на друга.
da-nie
В Duke Nukem 3D raycasting? Не порталы?
Raycasting есть в Wolfenstein 3D.
anonymous
НЛО прилетело и опубликовало эту надпись здесь
shiru8bit
Build определённо портальный движок. Но заблуждение, что это рейкастер, довольно распространено.