Демо City In A Bottle – система рейкастинга в 256 байтах

Привет всем любителям size coding, сегодня я расскажу о чём-то потрясающем: крошечном движке трассировки лучей (raycasting) и генераторе города, умещающихся в автономном файле HTML размером 256 байтов.

В этом посте я поделюсь секретами работы этой волшебной программы. Вот видео результата из моего твита:

Возможно, вы уже видели этот пост в моём Twitter. После публикации два года назад он стал самым популярным моим твитом.

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

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

Весь код

Для начала можно взглянуть на весь код. Это не просто блок JavaScript, а полная валидная HTML-программа.

<canvas style=width:99% id=c onclick=setInterval('for(c.width=w=99,++t,i=6e3;i--;c.getContext`2d`.fillRect(i%w,i/w|0,1-d*Z/w+s,1))for(a=i%w/50-1,s=b=1-i/4e3,X=t,Y=Z=d=1;++Z<w&(Y<6-(32<Z&27<X%w&&X/9^Z/8)*8%46||d|(s=(X&Y&Z)%3/Z,a=b=1,d=Z/w));Y-=b)X+=a',t=9)>

Это невероятно плотный 256-байтный блок минифицированного кода, так что для его понимания придётся приложить усилия.

HTML-код

Прежде чем переходить к JavaScript, давайте взглянем на HTML-часть кода. Вот сам HTML

<canvas style=width:99% id=c onclick=setInterval('',t=9)>

Это просто элемент canvas с событием onclick. Я щедро выставил ширину CSS на 99%; хотя демо отлично работает и без этого, так я оставил пространство для возможных экспериментов в будущих ремейках. id элемента canvas присвоено значение c, что позволит получать доступ к нему из JavaScript.

Запускает программу событие onclick. Вызов setInterval — это JavaScript, создающий цикл обновления. Время интервала равно 9 миллисекундам, что чуть меньше, чем 60, но достаточно близко к этому. Переменная времени t тоже для экономии места инициализируется значением 9.

Есть небольшой баг, возникающий, если на canvas нажать несколько раз. Интервал тоже начинает выполняться несколько раз, приводя к замедлению. Это не особая проблема, но о ней стоит помнить. Существует множество разных способов создания HTML-части этого кода, каждый из которых имеет свои плюсы и минусы. Подойдёт и обычный блок скрипта, только для него понадобится чуть больше места.

Код на JavaScript

Дальше идёт полезная нагрузка на JavaScript из 199 байтов, выполняемая после нажатия на canvas…

for(c.width=w=99,++t,i=6e3;i--;c.getContext`2d`.fillRect(i%w,i/w|0,1-d*Z/w+s,1))for(a=i%w/50-1,s=b=1-i/4e3,X=t,Y=Z=d=1;++Z<w&(Y<6-(32<Z&27<X%w&&X/9^Z/8)*8%46||d|(s=(X&Y&Z)%3/Z,a=b=1,d=Z/w));Y-=b)X+=a

Разбираем JavaScript

Этот код полностью совместим с dwitter, поэтому его можно вставить туда или в CapJS для экспериментов, только не забудьте добавить t=60, чтобы скорректировать скорость.

Первым делом я разобью код на части, чтобы его было удобнее читать. JavaScript по большей мере игнорирует пробелы, так что мы можем изменить структуру кода и добавить пространства. Точки с запятой обычно не требуются для завершения оператора, поэтому используются только внутри структуры цикла for.

c.width = w = 99
++t
for (i = 6e3; i--;)
{
  a = i%w/50 - 1
  s = b = 1 - i/4e3
  X = t
  Y = Z = d = 1
  for(; ++Z<w &
    (Y < 6 - (32<Z & 27<X%w && X/9^Z/8)*8%46 ||
    d | (s = (X&Y&Z)%3/Z, a = b = 1, d = Z/w));)
  {
    X += a
    Y -= b
  }
  c.getContext`2d`.fillRect(i%w, i/w|0, 1 - d*Z/w + s, 1)
}

Анализ кода

Давайте разберём код построчно.

c.width = w = 99 

Сначала мы очищаем canvas, задаём ему ширину 99 пикселей и сохраняем в w значение 99. Это число будет использоваться многократно. По умолчанию высота canvas равна 150, что нам подходит. Всё, что будет находиться ниже отрисовываемого нами, просто останется пустым.

++t

Для анимирования сцены мы должны выполнять инкремент времени один раз за кадр.

for (i = 6e3; i--;)

Этот цикл выполняет итерации при помощи переменной цикла i; он определяет яркость каждого отдельного пикселя.

Для определения яркости мы испускаем из камеры луч, используя для управления углом луча позицию пикселя. Когда луч с чем-то сталкивается, мы отправляем его в направлении солнца, чтобы понять, находится ли он в тени. Звучит сложно, но на самом деле всё довольно просто!

Получаем вектор камеры

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

a = i % w / 50 - 1

Горизонтальная компонента вектора камеры сохраняется в a. Мы можем вычислить её из i, сначала поделив i с остатком на ширину, то есть на 99. Затем мы делим на 50, чтобы получить значение от 0 до 2, а потом вычитаем 1, чтобы нормализовать его между -1 и 1. К счастью, больше скобок не требуется, что позволяет сэкономить место.

b = s = 1 - i / 4e3 

Вертикальная компонента вектора камеры хранится в b. Вычисления схожи с вычислениями a. Корректный способ вычисления вертикального процента: сначала поделить i на ширину, затем округлить вниз, потом поделить на высоту.

Однако если смириться с присутствием почти незаметного наклона, мы можем упростить и поделить i на половину количества пикселей, а затем вычесть 1, чтобы нормализовать между -1 и 1. Значение 4e3 было выбрано. чтобы сместить горизонт вниз от центра. Можете поэкспериментировать с этими значениями, чтобы увидеть, как они влияют на результат.

Также обратите внимание на то, что s присваивается то же значение, что и b , чтобы создать вертикальное линейное осветление на фоне, если луч не попал ни во что в сцене. Значение s в дальнейшем будет использоваться для управления затенением в сцене.

Получение позиции камеры

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

X = t

Ещё нам нужно инициализировать компоненты Y и Z, а также d, которое используется для примешивания тумана на расстоянии. Для всех них хорошо подходит значение 1.

Y = Z = d = 1

Система рейкастинга

Этот внутренний цикл — самая сложная часть всей программы, здесь система рейкастинга выполняет шаги, пока с чем-то не столкнётся, а затем выполняет отражение луча, чтобы проверить наличие теней.

for(; ++Z<w &

Большую часть работы здесь выполняет условная часть цикла for , поэтому для понятности разобьём её на несколько строк. Первая часть просто перемещает Z вперёд на один шаг, пока не уйдёт слишком далеко. В этом случае мы повторно используем переменную w, равную 99. Переменные X и Y обновляются внутри цикла.

Проверка высоты зданий

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

    (Y < 6 - (32<Z & 27<X%w && X/9^Z/8)*8%46 ||

Чтобы проверить, находится ли луч внутри коллизии, мы проверяем, меньше ли значение Y высоты в этой позиции. Город формируется управлением высотой в каждой локации XZ.

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

А вот в скобках происходит настоящая магия…

• Оставляем немного пространства между камерой и первым рядом зданий, проверяя, что Z сдвинулась не менее чем на 32 единиц.

• Создаём боковые улицы и побережье, проверяя, что X mod w (константа 99) больше 27. Это периодически оставляет пустые пространства наподобие дорог, делящие город на кварталы. Плюс это всегда возвращает false при отрицательных значениях, удобным образом создавая океан.

• Генерируем функцию шума для высот зданий при помощи X/9^Z/8. Здесь используется функция XOR для создания интересного распределения значений, придавая высоте зданий впечатление случайности.

• Деление необходимо для масштабирования значений, чтобы здания были 9 единиц в высоту и 8 единиц в глубину. При бóльших значениях увеличится размер зданий.

• Значение X/9 здесь тоже связано с тем, что ширина боковых улиц находится в интервале от 27 до 99, все эти числа делятся на 9. Это предотвращает создание очень тонких зданий по бокам.

Результат всех вычислений в скобках умножается на 8 и делится с остатком на 46, то есть на максимальную высоту. Эти значения были выбраны после экспериментов, чтобы получить интересное разнообразие высот зданий.

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

Создание тени и текстуры

Если мы попали в этот код, значит, была пройдена первая проверка, то есть луч с чем-то столкнулся. Здесь мы получаем текстуру того, с чем мы столкнулись, и отражаем свет в сторону солнца, чтобы создать тень. Тут всё немного хитро, потому что на самом деле в одном цикле находятся два.

    d | (s = (X&Y&Z)%3/Z, a = b = 1, d = Z/w));)

Первая часть (d |) нужна для проверки, испускаем ли мы луч из камеры, или отправляем его в направлении света, чтобы проверить на наличие тени. До начала цикла мы уже присвоили d значение 1, а к концу этой строки ему будет присвоено значение меньше 1, которое комбинируется побитово или приравнивается к false. Это позволяет циклу выполниться второй раз, двигаясь по направлению к свету, чтобы проверить на наличие тени. Если луч находится в тени, то при следующем попадании в этот код будет выполнен выход из цикла и отрисовка пикселя.

Значение текстуры в градациях серого хранится в s; оно генерируется применением оператора & к X, Y и Z с последующим делением с остатком на 3. Это создаёт эффект, похожий на разные типы окон. Кроме того, результат делится на Z, чтобы создать туман на расстоянии.

Чтобы направить луч в сторону источника света, и a, и b присваивается значение 1. Это отлично работает для направленных источников света наподобие солнца.

Значение тумана сохраняется в d делением текущего значения Z на w (99) и используется для осветления зданий вдали. То же значение d теперь гарантировано будет меньше 1, а это значит, что, как и говорилось выше, мы выполняем проверку на наличие тени.

X += a
Y -= b

Каждая компонента обновляется, чтобы переместить конечную точку луча. Части X и Y управляются, соответственно, переменными a и b. Часть Z всегда сдвигается вперёд на 1, так как направленный источник освещения находится в направлении камеры и никогда не должен меняться.

Отрисовка каждого пикселя

Далее при помощи простого вычисления i (чтобы избавиться от координат X и Y) отрисовывается каждый пиксель. Управление яркостью выполняется уменьшением размера пикселя. Это очень компактный способ создания изображений в градациях серого по одному пикселю за раз.

c.getContext`2d`.fillRect(i%w, i/w|0, 1 - d*Z/w + s, 1)

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

Значение тумана d умножается на текущее расстояние Z/w, так и создаются тени. Если луч не в тени, то он прошёл максимальное расстояние w, поэтому Z/w будет равно 1. И наоборот, если он в тени, то Z будет меньше w, поэтому эта область будет темнее. Это создаёт что-то типа рассеянного затенения (ambient occlusion), потому что чем ближе объект, блокирующий свет, тем гуще тень.

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

Вот и вся программа! Этот крошечный 256-байтный движок рейкастинга и генератор города показывает, сколь многого можно добиться минимальным кодом. Надеюсь, вам понравилось знакомство с внутренним устройством «City In A Bottle».

Дополнительное чтение

Это демо участвовало в демо-пати Revision 2022 и выложено на Pouet. В то время оно получило не очень высокую оценку, потому что я отправил её не в ту категорию (увы!), но я считаю, что это одно из самых впечатляющих 256-байтных демо на JavaScript.

Кроме того, мы продолжили развивать эту концепцию на Shadertoy, где с Xor и несколькими другими хакерами мы создали 256-байтный шейдер, полностью воспроизводящий версию на JavaScript. Он выглядит потрясающе и работает в HD при 60FPS, посмотрите сами!

Наконец, Даниэль Дарабос создал на observable интерактивный инструмент, позволяющий поэкспериментировать с различными аспектами программы в реальном времени: Decoding A City In A Bottle

Подведём итог

Спасибо, что дочитали до конца. Если хотите углубиться, то можете модифицировать код на Dwitter или просто экспериментировать с ним на CapJS. Мне всегда радостно видеть творческие вариации и улучшения, придуманные сообществом.

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

Продолжайте кодить, продолжайте экспериментировать и расширять границы того, что можно реализовать в крошечном коде!