Два года назад я уже экспериментировал с веществами тенями в Phaser 2D. На последнем Ludum Dare мы внезапно решили сделать хоррор, а какой же хоррор без теней и света! Хрустнул я костяшками пальцев…

… и ни черта не успел за LD. В игре конечно есть немного света и теней, но это жалкое подобие того, что должно было быть на самом деле.

Вернувшись домой уже после отправки игры на конкурс, я решил все-таки “закрыть гештальт” и доделать эти несчастные тени. Что получилось — можно пощупать в игре, поиграться в демке, посмотреть на картинке, и почитать в статье.

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

Источников света несколько (20-30), и все они круговые (spotlights) и расположены условно ниже чем освещаемые объекты (так что тени могут быть бесконечными).

Я видел у себя в голове следующие способы решения задачи:

1. Для каждого источника света строим текстуру размером с экран (ну или в 2-4 раза меньше). На этой текстуре мы просто рисуем трапеции BCC’D’, где A — источник света, BC — отрезок, B’C’ — проекция отрезка на край текстуры. После эти текстуры отправляются в шейдер, где смешиваются в единую картину.
   
   Примерно так сделал автор платформера Celeste, о чем хорошо написано в его статье на medium: medium.com/@NoelFB/remaking-celestes-lighting-3478d6f10bf
   
   Проблемы: 20-30 текстур размером с экран, которые надо перерисовывать чуть ли не каждый кадр и загружать в GPU. Я помню, что это было весьма и весьма не быстрым процессом.
   
   
   
   
2. Способ, описанный в посте на хабре — habr.com/post/272233. Для каждого источника света строим “карту глубин”, т.е. такую текстуру, где x = угол “луча” от источника света, y = номер источника света, а цвет == расстояние от источника до ближайшего препятствия. Если взять скажем шаг в 0.7 градуса (360/512), и 32 источника света, то получим одну текстуру 512х32, которую обновлять уже не так долго.
   
   
   ^{(пример текстуры для шага 45 градусов)}
   
3. Секретный способ, который я опишу в самом конце

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

“У нас тут в модели одни отрезки”, — подумал я, — “И в радиус любого источника света попадает 10-20 отрезков. Неужели я не могу быстро рассчитать карту расстояний исходя из этого?”.

Так я и решил поступить.

Для начала я просто вывел на экран стенки, условного “главного героя” и источники света. Вокруг источников света вырезал во мгле круг чистого ясного света. Чтобы получилось такое:

^(демо)

Я сразу начал делать с шейдером, чтобы не расслабляться. В него нужно было передать для каждого источника света его координаты и радиус действия (за пределами которого свет не доходит), это делается просто через uniform массив. И затем в шейдере (который фрагментный, который выполняется для каждого пикселя на экране) оставалось понять — входит у нас текущий пиксель в освещенный круг или нет.

class SimpleLightShader extends Phaser.Filter {

  constructor(game) {
    super(game);

    let lightsArray = new Array(MAX_LIGHTS*4);
    lightsArray.fill(0, 0, lightsArray.length);

    this.uniforms.lightsCount = {type: '1i', value: 0};
    this.uniforms.lights = {type: '4fv', value: lightsArray};

    this.fragmentSrc = `
      precision highp float;
          
      uniform int lightsCount;
      uniform vec4 lights[${MAX_LIGHTS}];
      
      void main() {
        float lightness = 0.;
        for (int i = 0; i < ${MAX_LIGHTS}; i++) {
          if (i >= lightsCount) break;
          vec4 light = lights[i];
          lightness += step(length(light.xy - gl_FragCoord.xy), light.z);
        }
        lightness = clamp(0., 1., lightness);
        gl_FragColor = mix(vec4(0,0,0,0.5), vec4(0,0,0,0), lightness);
      }
      
     `;
  }

  updateLights(lightSources) {
    this.uniforms.lightsCount.value = lightSources.length;
    let i = 0;
    let array = this.uniforms.lights.value;
    for (let light of lightSources) {
      array[i++] = light.x;
      array[i++] = game.world.height - light.y;
      array[i++] = light.radius;
      i++;
    }
  }
}

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

Примечание: определение пересечения — это своего рода предварительная оптимизация. Она нужна для того, чтобы сократить время дальнейшей обработки, исключив большие куски отрезков за пределами радиуса действия источника света. Это имеет смысл, когда у нас много отрезков, чья длина много больше радиуса “свечения”. Если это не так, и у нас много коротких отрезков, может оказаться правильным не тратить время на определение пересечения и обрабатывать отрезки целиком, т.к. экономии времени все равно не получится.

Для этого я воспользовался широкоизвестной формулой по нахождению пересечения прямой и круга, которую каждый помнит наизусть из школьного курса геометрии… в чьем-то воображаемом мире. Я вот ее так и не вспомнил, так что пришлось погуглить.

Кодируем, смотрим что получилось.
^(демо)
Вроде норм. Теперь мы знаем какие отрезки могут отбрасывать тень и можем выполнять рейкаст.

Тут у нас тоже варианты:

1. Просто идем в цикле по кругу, бросаем лучи и ищем пересечения. Расстояние до ближайшего пересечения и есть нужная нам величина
2. Можно идти только по тем углам, которые попадают в отрезки. Ведь точки мы уже знаем, посчитать углы несложно.
3. Далее, если мы идем вдоль отрезка, то нам не надо бросать лучи и рассчитывать пересечения — мы можем двигать по отрезку с нужным шагом. Вот как это работает:

Тут $$ — отрезок(стена), $$ — центр источника света, $$ — перпендикуляр к отрезку.

Пусть $$ — угол к нормали, для которого надо узнать расстояние от источника до отрезка, $$ — точка на отрезке $$, куда падает луч. Треугольник $$ — прямоугольный, $$ — катет, и его длина известна и постоянна для этого отрезка, $$ — искомая длина. $$. Если знать заранее шаг (а мы его знаем), то можно заранее рассчитать таблицу обратных косинусов и искать расстояния очень быстро.

Приведу пример кода такой таблицы. Почти вся работа с углами заменена на работу с индексами, т.е. целыми числами от 0 до N, где N = количество шагов в круге (т.е. угол шага = $$)

class HypTable {

  constructor(steps = 512, stepAngle = 2*Math.PI/steps) {
    this.perAngleStep = [1];
    for (let i = 1; i < steps/4; i++) { //не надо больше pi/2
      let ang = i*stepAngle;
      this.perAngleStep[i] = 1/Math.cos(ang);
    }
    this.stepAngle = stepAngle;
  }

 /**
  * @param distancesMap - таблица расстояний, сюда идет запись
  * @param angle1 - угол от источника света к первой точке пересечения с отрезком
  * @param angle2 - угол от источника света ко второй точке пересечения с отрезком
  * @param normalFromLight - перпендикуляр, от источника света к отрезку
  */
  fillDistancesForArc(distancesMap, angle1, angle2, normalFromLight) {
    const D = Math.hypot(normalFromLight.x, normalFromLight.y);
    const normalAngle = Phaser.Math.normalizeAngle(Math.atan2(normalFromLight.y, normalFromLight.x)); 

    const normalAngleIndex = (normalAngle / this.stepAngle)|0;
    const index1 = (angle1 / this.stepAngle)|0;
    const index2 = (angle2 / this.stepAngle)|0;
        
    for (let angleIndex = index1; angleIndex <= index2; angleIndex++) {
      let distanceForAngle = D * this.perAngleStep[normalize(angleIndex - normalAngleIndex)];  
      distancesMap.set(angleIndex, distanceForAngle);
    }
  }
}

Конечно, такой способ вносит погрешность для случаев, когда начальный угол ACD не кратен шагу. Но для 512 шагов я визуально не вижу никакой разницы.

Итак, что мы уже умеем делать:

1. Находить отрезки в радиусе действия источника света, которые могут отбрасывать тень
   
2. Для шага t составлять таблицу dist(angle), проходя по каждому отрезку и рассчитывая расстояния.

Вот как эта таблица выглядит, если ее нарисовать лучами.

^(демо)

А вот как она выглядит для 10 источников света, если записать в текстуру.

Здесь каждый пиксель по горизонтали соответствует углу, а цвет — расстоянию в пикселях.
Пишется все это в js так, используя imageData

  fillBitmap(data, index) {
    let total = index + this.steps*4;
    let d1, d2;
    let i = 0;
    //data[index]   = Red
    //data[index+1] = Green
    //data[index+2] = Blue
    //data[index+3] = Alpha
    for (; index < total; index+=4, i++) {
      //максимальное расстояние 512, так что в R пишем результат деления на 2.
      d1 = (this.distances[i]/2)|0;
      data[index] = d1;
      d1 = this.distances[i] - d1*2;
      d2 = (d1*128)|0;
      // а в G - остаток от деления на 2.
      data[index+1] = d2;
      // в B и A пишем 255, они нам пока не нужны.
      data[index+2] = 255;
      data[index+3] = 255;
    }
  }

Теперь передаём текстуру в наш шейдер, в котором уже есть координаты и радиусы источников света. И обрабатываем так:

	
// здесь текстура с картой расстояний
uniform sampler2D  iChannel0;
            
#define STRENGTH 0.3
#define MAX_DARK 0.7
#define M_PI 3.141592653589793
#define M_PI2 6.283185307179586
       
// выполняем обратное преобразование цвета в расстояние
float decodeDist(vec4 color) {
  return color.r*255.*2. + color.g*2.;
}            
            
float getShadow(int i, float angle, float distance) {
  // смещение по x в текстуре == углу
  float u = angle/M_PI2;
  // смещение по y в текстуре == порядковому номеру источника света
  float v = float(i)/${MAX_LIGHTS}.;
  float shadowAfterDistance = decodeDist(texture2D(iChannel0, vec2(u, v)));
  // возвращаем 1 если есть тень, и 0 если нету.
  return step(shadowAfterDistance, distance);
}            
        
        
void main() {
  float lightness = 0.;
  for (int i = 0; i < ${MAX_LIGHTS}; i++) {
  if (i >= lightsCount) break;
    vec4 light = lights[i];
    //вектор от источника света к текущей точке
    vec2 light2point = gl_FragCoord.xy - light.xy;
                    
    float radius = light.z;
    float distance = length(light2point);
    float inLight = step(distance, radius);
    //если точка за пределами действия источника света, то и не надо для нее 
    // ничего считать.
    //хотя использовать ветвления в шейдерах не рекомендуется,
    // я не раз замечал, что вот такие вот отсечения неплохо ускоряют некоторые шейдеры
    //например в данном случае для каждой точки делается запрос в текстуру
    // с картой расстояний только тогда, когда это требуется
    if (inLight == 0.) continue;
    float angle = mod(-atan(light2point.y, light2point.x), M_PI2);
                    
    //получаем 1 для освещенного участка и 0 для неосвещенного
    float thisLightness = (1. - getShadow(i, angle, distance));
    //считаем, что каждая “лампочка” светит неярко, и надо несколько, чтобы 
    // полностью осветить пиксель
    lightness += thisLightness*STRENGTH;
  }
  lightness = clamp(0., 1., lightness);
            
  gl_FragColor = mix(vec4(0,0,0,MAX_DARK), vec4(0,0,0,0), lightness);
}

Результат:
^(демо)
Теперь можно навести немного красоты. Пусть свет затухает с расстоянием, а тени будут размытыми.

Для размытия я смотрю соседние углы, +- шаг, вот так:

thisLightness =  (1. - getShadow(i, angle, distance)) * 0.4 
  + (1. - getShadow(i, angle-SMOOTH_STEP, distance)) * 0.2   
  + (1. - getShadow(i, angle+SMOOTH_STEP, distance)) * 0.2
  + (1. - getShadow(i, angle-SMOOTH_STEP*2., distance)) * 0.1   
  + (1. - getShadow(i, angle+SMOOTH_STEP*2., distance)) * 0.1;

Если собрать все вместе и замерить фпс, то получается так:

• На встроенных видеокартах — все плохо (<30-40), даже для простых примеров
  
• На остальных — все хорошо, пока источники света не очень сильные. Т.е.важно количество источников света на 1 пиксель, а не общее количество.
  

Такой результат меня вполне устроил. Можно было бы еще поиграться с цветом освещения, но я уже не стал. Чуть докрутив и добавив немного карт нормалей, я выложил обновленную версию NOPE. Выглядела она теперь так:


Потом начал готовить статью. Посмотрел на такую гифку и задумался.

“Так это же почти что псевдо-3д вид, как в Wolfenstein” — воскликнул я (да, у меня хорошее воображение). И в самом деле — если считать, что все стены одной высоты, то карты расстояний нам хватит для построения сцены. А чего бы не попробовать?

Сцена должна выглядеть как-то так.


Значит, наша задача:

1. По точке на экране получить мировые координаты для случая, когда стен нет.
   
   Считать будем так:
   
   • Для начала нормализуем координаты точки на экране так, чтобы в центре экрана была точка (0,0), а по углам (-1,-1) и (1,1) соответственно
     
     
   • Координата x становится углом от направления взгляда, надо только домножить ее на A/2, где A — угол обзора
     
   • Координата y определяет расстояние от наблюдателя до точки, в общем случае d ~ 1/y. Для точки на нижнем краю экрана расстояние = 1, для точки по центру экрана расстояние = бесконечность.
     
     
   • Таким образом, если не учитывать стены, то для каждой видимой точки мира будет 2 точки на экране — одна выше середины (на “потолке”) другая ниже (на “полу”)
     
2. Теперь можем смотреть в таблицу расстояний. Если там есть стена ближе, чем наша точка, значит надо рисовать стену. Если нет — значит пол или потолок
   

Получаем как заказывали:
^(демо)
Добавляем освещение — точно так же, итерируемся по источникам света и сверяем мировые координаты. И — последний штрих — добавляем текстуры. Для этого в текстуру с расстояниями надо еще и записывать смещение u для текстуры стены в этой точке. Тут нам и пригодился канал b.
^(демо)
Идеально.

Шучу.

Неидеально, конечно. Но черт возьми, я еще джва года 15 лет назад читал, как сделать свой Wolfenstein через рейкаст, и все хотел его сделать, а тут такая возможность!

Вместо заключения

В начале статьи я упомянул ещё один секретный способ. Вот он:

Просто возьмите движок который это уже умеет.

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

А вот зачем.

В 10 классе я перешел в другую школу и столкнулся с проблемами по математике. Я не помню точный пример, но это было уравнение со степенями, которое по всем признакам надо было упростить, да только никак не удавалось. Отчаявшись, я посоветовался с сестрой, и она сказала: “так добавь с обеих сторон x², и все разложится”. И это и было решением: добавить то, чего не было.

Когда много позже я помогал своему знакомому строить мне дом, понадобилось положить в порог брусок — заполнить нишу. И вот стою я и перебираю обрезки брусков. Один вроде подходит, но не совсем. Другие сильно меньше. Стою думаю как тут собрать слово счастье, а знакомый и говорит: “так выпили циркуляркой пазы там где мешает”. И вот большой брусок уже стоит на месте.

Эти истории объединяет такой эффект, который я назову “эффект инвентаря”. Когда пытаешься сделать решение из существующих деталей, не видя в этих деталях материал, поддающийся обработке и доработке. Числа это, дерево, деньги или код.

Я много раз наблюдал этот же эффект у коллег по программированию. Не чувствуя уверенности в материале, они иногда пасуют, когда надо сделать, скажем, нестандартный контрол. Или добавить юнит-тесты туда, где их не было. Или пытаются предусмотреть все-все при проектировании какого-либо класса, и тогда у нас получается диалог вроде:
— Это сейчас не нужно
— А вдруг станет нужно?
— Тогда и допишем. Оставь точки расширения, и все. Код — это не гранит, это пластилин.

И чтобы научиться видеть и чувствовать материал, с которым мы работаем, и нужны велосипеды.

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

Всем спасибо, что дочитали.

Ссылочки, на случай, если забыли куда-то кликнуть:

• Все демки вместе
• Код демок
• Собственно LD-игра с тенями