27.11.2018 21:18
rebuilder 16 2100 Источник


Уважаемые Хабровчане, представляю вашему вниманию продолжение изысканий на тему поиска подходящих теней для 2D рогалика.

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

В своих комментариях, уважаемые критики, совершенно справедливо отметили, что в замкнутых пространствах тени получились угловатыми, и несколько не естественными. Было предложено несколько вариантов решения, мне понравилось предложение использовать ray casting для расчёта тени.



Уточняю, я не работаю с видеокартой (пока не работаю), все результаты смоделированы на ЦПУ.

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

Здесь мы будем использовать упрощённую разновидность рейкастинга, основанную на пересечении лучом тайловой сетки. Данный метод широко использовался в псевдотрёхмерных играх прошлого (например Wolfenstein_3D, почтение тем кто в теме), мы его адаптируем для двумерного пространства.



Алгоритм, достаточно прост как для понимания, так и воплощения. Приведу собственную его реализацию:

Pascal
// i,j - координаты тайла, а - угол
// X,Y - начальное смещение координат
// r - максимальный радиус для расчёта

// Инициализация направления
if cos(a)<0 then
  begin di :=-1; ddi:= 0; end
else
  begin di := 1; ddi:= 1; end;

if sin(a)<0 then
  begin dj :=-1; ddj:= 0; end
else
  begin dj := 1; ddj:= 1; end;

// Предварительный расчёт первой точки по Х и Y
x1 := (i+ddi) * tile_size;
y1 := y+ (x1-x) * tan(a);
Dx := len(x,y,x1,y1);

y1 := (j+ddj) * tile_size;
x1 := x+ (y1-y) * cotan(a);
Dy := len(x,y,x1,y1);

sum_lenX := 0;
sum_lenY := 0;

// Размер тайла по X и Y под углом a
rX := abs(tile_size / cos(a));
rY := abs(tile_size / sin(a));

// выбираем точки пересечения
repeat
  if sum_lenX+DX < sum_lenY+DY then
    begin  
      x1 := (i+ddi) * tile_size;
      y1 := y+ (x1-x) * tan(a);
      i  := i+di;
      // Проверяем тайл на наличие стены или границ экрана
      key  := is_wall(i,j); 
      sum_lenX := sum_lenX + DX;
      if DX<>rX then DX:=rX;
      // Если радиус больше нужного обрываем цикл
      if r<sum_lenX then Break;
    end
    else
    begin
      y1 := (j+ddj) * tile_size;
      x1 := x+ (y1-y) * cotan(a);
      j  := j+dj;
      // Проверяем тайл на наличие стены или границ экрана
      key  := is_wall(i,j);
      sum_lenY := sum_lenY + DY;
      if DY<>rY then DY:=rY;
      // Если радиус больше нужного обрываем цикл
      if r<sum_lenY then Break;
    end; 
until (Пока не найдём стену или границу экрана); 

// x1,y1 искомые координаты

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

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

Запустив лучи во все стороны с нужным шагом получим примерно такую картину:



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



Дальше начинается работа со слоями.

Область видимости. Здесь и далее лучи немного проходят в глубь объектов. Такая игровая условность создаёт уникальный антураж, свойственный 2D Играм.



Генерация карты освещения. Статичные источники света генерируем заранее и кешируем для улучшения быстродействия, динамические накладываем в процессе вывода на экран.



Сведение всего вместе. Не хватает только жутких монстров и сокровищ… много сокровищ.



Стены с изменяемой кривизной проникновения света мне не зашли, но возможно это на любителя.



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



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

Спасибо за внимание.

Ссылка поиграться (exe для виндовс)

Комментарии (16)


  1. DrZlodberg
    28.11.2018 08:48
    #19424518

    Если нужен метод только для ограничения области видимости, то есть более простой вариант (если не ошибаюсь, он используется, например, в teleglitch): просто над препятствием рисуем чёрную вертикальную стену с сильной перспективой, которая просто загораживает лишнее.


    1. rebuilder Автор
      28.11.2018 09:16
      #19424648

      Ранее не сталкивался с данной игрой, вы правы, отдаленно похоже, но эффект несколько иной.


      1. AngReload
        28.11.2018 11:05
        #19425172

        В вашей прошлой статье ведь тот же принцип построения теней был?
        Кстати, как там полигоны теней отрисовывались: что-то быстрое типа такого?


        1. rebuilder Автор
          28.11.2018 11:12
          #19425210

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


          1. AngReload
            28.11.2018 11:17
            #19425236

            Нет, я про то что говорил DrZlodberg. Он ведь предложил то же самое что вы и в прошлый раз сделали.


  1. GCU
    28.11.2018 14:22
    #19426508

    Точечные источники освещения отбрасывают очень уж жёсткие тени. Для теней многоугольников можно упростить рейкастинг, например, как тут ncase.me/sight-and-light.

    Мягкие тени сделать сложнее, т.к. источник света не точка, а, например, отрезок. И вместо видно/не видно точку нужно считать под каким углом виден отрезок освещения из точки (получается как-бы обратный рейкастинг от точки к источнику/ам освещения). Хотя это и вычислительно сложно, можно заранее «запечь» карту освещения для статических источников.


    1. rebuilder Автор
      28.11.2018 14:54
      #19426780

      Метод что указан по ссылке будет хорошо работать только когда объектов не много. Например: при разрешении Full HD — разрешение 1920?1080 и размере тайла 32х32, получим сетку 60х33 видимых тайла, итого верхняя граница 1980х4 ~ 8к лучей, без мягкой тени. Перспективно нужно пробовать.

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


      1. GCU
        28.11.2018 15:11
        #19426904

        Не соглашусь с рассчётом :). В сетке 60х33 будет (60+1)х(33+1) ~ 2к точек.


        1. rebuilder Автор
          28.11.2018 15:18
          #19426970

          Один тайл мы отдадим на откуп обрамлению ).
          Про то, что у каждого тайла 4 угла вы забыли, или я не правильно понял метод?
          Хотя, карта должна состоять хотя бы наполовину из коридоров, а не только стен, так что 2-4к лучей вполне реально.


          1. GCU
            28.11.2018 15:33
            #19427100
            +1

            Лучи идут к точкам.
            Одна и та-же точка может быть использована для нескольких тайлов. Например для одного тайла она верхняя левая, для другого она же нижняя правая. Нет смысла трассировать одну и ту-же по факту точку дважды.
            В плотном блоке 2х2 тайла действительно по 4 угла на тайл, но точек по факту 9, а не 16. Внутренняя точка общая для всех 4х тайлов, точки на серединах граней общие для 2х смежных блоков (сколько тайлов используют точку):
            1 2 1
            2 4 2
            1 2 1


            1. rebuilder Автор
              28.11.2018 16:24
              #19427568

              Очень разумное решение, руки чешутся применить, по моим расчётам выигрыш на математике будет 2-3 раза, жаль, что на общем фоне расчётов это мизер.
              Сейчас основная нагрузка идёт на тайловый движок и слияние слоёв.

              Основная идея состоит в том, что хоть расчёты придется делать для всех тайлов экрана, но соединения стен можно просчитать заранее и кэшировать.


  1. 1dNDN
    28.11.2018 14:46
    #19426726

    В лабиринте стоит докрашивать освещение до полного блока, если освещено больше 1/3 блока


    1. rebuilder Автор
      28.11.2018 14:47
      #19426732

      Реализовать не проблема, но в чём эффект такого подхода?


      1. GCU
        28.11.2018 15:26
        #19427042

        Полагаю чтобы игрок чётко понимал — согласно игры он видит содержимое тайла или нет. В DoomRL, например, от этого зависит можно ли выстрелить в противника. Если механика игры это предусматривает, то логично как-то однозначно трактовать видимость в спорных ситуациях. Субъективно для игрока по факту противник виден, а выстрелить по нему по непонятным причинам нельзя. Дополнительная подсветка в таком случае устранила бы неоднозначность видим/не видим можно/нельзя попасть.


      1. 1dNDN
        28.11.2018 18:46
        #19428496

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


  1. SSS135
    28.11.2018 20:26
    #19428942

    Как-то писал систему 2D освещения на рейтресинге в шейдерах. Работало довольно быстро, но со своими минусами. Ещё из особенностей была поддержка любых форм источников света, задавались они через обычные спрайты. Сейчас, к сожалению, забросил проект и он не заработает на последних версиях Unity3D.