Освещение применяют, наверное, во всех играх всех сортов. Во многих современных движках для этого есть встроенные инструменты, однако если хочется просто взять и просто сделать какой нибудь пошаговый Dungeon Crawler, то движок по типу Unity будет только мешать.
Применять сложные технологии для освещения ячеек дело неблагородное, уйдет много времени, сил, да и не факт что в таком случае это оправдано. Для написания простой пошаговой игры нужно нечто более простое, чем явно непростые инструменты во главе с шейдером. В общем, как вы могли догадаться, сегодня поговорим о простом алгоритме освещения тайловых карт.
Парадоксально, но реализовывать такое освещения я буду на движке Godot v3.3.2, однако сам алгоритм от движка никак не зависит.
По ходу моего рассказа мы разберем и реализуем способ, способный выдавать подобные тени, причем свет может быть в принципе любой формы, не только круглым (да, даже логарифмическим или тангенциальным):
Данный алгоритм был выведен мной, поэтому не стоит воспринимать его как научно обоснованный и выверенный годами способ - сегодняшний рассказ не выйдет за рамки школьной программы. Ладно, от лирики ближе к сути.
Главный принцип
По факту сутью любого алгоритма освещения является определение освещенности пикселя, только вот достигается это по-разному. Кто то использует рейкастинг, кто то тупую проверку для каждого пикселя, а кто то - геометрию 7-8 класса. Эти крайние "кто то" как раз мы. Смотрите, каждый объект отбрасывает тень от своих углов, тем самым образуя две линии:
Получается, что все ячейки внутри двух синих линий загорожены этим объектом. Таким образом, для определения видимости точки мы можем просто сравнить углы, образуемые двумя синими линиями и прямой, проходящей через центр ячейки, с осью X. Получается, точка лежит внутри тени, если ее угол больше α и меньше β:
Здесь ячейка, помеченная красной точкой в центре - не освещена, т.к. ее угол лежит между углами препятствия. Работать с углами как то не очень, поэтому будем работать с отношениями координат - это как раз будут тангенс (y к x) и котангенс ( x к y).
Давайте считать координаты ячейки как ее центр, тогда тангенс верхнего угла будет иметь значение (y+0.5)/(x-0.5), тангенс нижнего угла - (y-0.5)/(x+0.5). Котангенс, естественно, - наоборот.
Значит теперь вместо углов сравниваем значения функций - вуаля! Но, не все так просто, давайте посмотрим на крайние значения углов - 0 и π/2. Как вы наверняка знаете - в пером не определен котангенс, во втором - тангенс, поэтому будем считать их бесконечностью, ведь именно к ней значения стремятся. Эти углы достигаются при координатах относительно источника света y = 0 и x = 0 соответственно.
Давайте для примера возьмем тангенс. Представим препятствие с координатами, ну, скажем, {0, 4} - тогда тангенс его левого верхнего угла будет 4.5/-0.5 = -9, тангенс нижнего правого 3.5/0.5 = 7.
Напомню - чем больше тангенс, тем больше угол (в первой - нашей четверти). Тогда ячейка не видима, если ее тангенс больше 7 и меньше -9. Опа, отношение двух положительных чисел должно быть меньше отрицательного. Получается, что это препятствие тупо игнорируется. С котангенсом тоже самое, только с правым нижним углом.
Тогда вместо только одной функции будем считать сразу две - тангенс и котангенс, а для углов препятствия возьмем по одной функции - главное чтобы они были разные. Например, для верхнего угла котангенс, тогда для нижнего - тангенс. В будущем значения функций в этих местах я буду называть ограничивающими значениями.
Теперь снова рассмотрим то же препятствие {0, 4}. Котангенс его верхнего левого угла имеет значение -0.5/4.5 ≈ -0.11 , тангенс правого нижнего - 3.5/0.5 = 7. Теперь все отлично - ячейка не видима, если ее котангенс больше -0.11(больше, т.к. чем больше котангенс - тем меньше угол) и тангенс меньше 7. В таком случае левый верхний угол нам больше не мешает и мы сравниваем только тангенсы. При координате y = 0 получится тоже самое, только выпадет нижний угол.
Теперь, разобравшись с принципом работы, можно перейти и к реализации.
Начальная реализация
Наверняка вы задались одним правильным вопросом - ведь если ячейка перед препятствием, но имеет значения неосвещенной ячейки, мы все равно посчитаем ее тенью. Да, это так, если рассматривать все препятствия сразу. Мы же поступим хитрее.
Точка в принципе может отбрасывать тень только в зоне, помеченной на рисунке серым, ведь в других местах прямая видимость с источником света:
Тогда мы можем проходить в типичном двойном цикле от нуля до дальности свечения и, натыкаясь на препятствие, записывать ограничевающие значения в массивы, чтобы постоянно их не вычислять. Таким образом, мы будем учитывать только те препятствия, которые потенциально могут отбрасывать тень. Но ведь если ячейка левее, но выше препятствия - мы все равно препятствие учитываем. Да, но котангенс этой ячейки будет гораздо меньше котангенса левого верхнего угла препятствия, т.к. координата x меньше, координата y больше, а котангенс - это отношение x к y. Точно также и с ячейкой ниже, но правее препятствия.
Давайте ближе к делу. Пусть у нас будет два массива для хранения ограничивающих значений - один с котангенсами левых верхних углов препятствий, другой с тангенсами нижних углов:
var obsts_ctg:PoolRealArray = PoolRealArray() # для котангенсов
var obsts_tg:PoolRealArray = PoolRealArray() # для тангенсовА за дальность светила будет отвечать переменная distance:int, которая идет параметром для функции рисования света, как и ячейка cell:Vector2, из которой мы хотим излучать свет. Для удобства я записал ее x и y в отдельные переменные x0:int и y0:int. Также понадобится флаг видимости ячейки - назовем его is_visible:bool. Думаю на создание переменных смотреть не особо интересно, поэтому сразу к сути.
Для создания освещения нам так и так придется смотреть на каждую ячейку, поэтому пробегаем в циклах x и y координаты от нуля до distance и смотрим, если наткнулись на препятствие, то добавляем ограничевающие значения в соответствующие массивы:
...
for y in range(distance+1):
for x in range(distance+1):
tg = float(y)/x if x != 0 else distance*distance
ctg = float(x)/y if y != 0 else distance*distance
if Vector2(x0+x, y0+y) in obstacles:
# Эти переменные я объявил ранее, просто не писал об этом
obst_ctg = (x-0.5)/(y+0.5) # Котангенс левого верхнего угла (в декартовой системе координат, в экранной это левый нижний)
obst_tg = (y-0.5)/(x+0.5) # Тангенс правого нижнего (тоже в декартовой, в экранной это правый верхний)
obsts_ctg.append(obst_ctg)
obsts_tg.append(obst_tg)
continue # Если препятствие, то его не освещаем, поэтому пропускаем итерациюВ критических значениях функций (если x или y равны 0) вместо бесконечности (да, в годо есть INF) я взял distance2, т.к. в наших вычислениях ничего не будет больше него, так что это вполне сойдет за бесконечно большое число.
Для определения видимости точки пробегаем по массивам и сравниваем углы, предварительно определив флаг видимости как истину, ведь пока ячейку никто не перекрывает:
...
is_visible = true # Флаг видимости
for i in range(len(obsts_ctg)):
if tg > obsts_tg[i] and ctg > obsts_ctg[i]: # Точка попадает в тень
is_visible = false
break # Достаточно хотя бы один одним препятствием заблокировать точку, поэтому другие не смотримЗдесь засчет того, что мы всегда одновременно добавляем значения в оба массива, нет необходимости как то проверять длины, ведь в таком случае они всегда совпадают.
И, если флаг остался истиной, освещаем ячейку:
...
if is_visible:
light_cell(Vector2(x+x0, y+y0), 1) # второй параметр - яркость, пока просто оставляем ее единицейОтлично, теперь у нас готова база для написания полноценной функции освещения. Под спойлером я оставлю полный код функции и результат ее работы:
Спойлер
Функция:
func add_lighter(cell:Vector2, distance:int, color:Color=Color.white):
var x0:int = cell.x
var y0:int = cell.y
var obsts_ctg:PoolRealArray = PoolRealArray()
var obsts_tg:PoolRealArray = PoolRealArray()
var tg:float
var ctg:float
var obst_ctg:float
var obst_tg:float
var is_visible:bool
for y in range(distance+1):
for x in range(distance+1):
tg = float(y)/x if x != 0 else distance*distance
ctg = float(x)/y if y != 0 else distance*distance
if Vector2(x0+x, y0+y) in obstacles:
obst_ctg = (x-0.5)/(y+0.5)
obst_tg = (y-0.5)/(x+0.5)
obsts_ctg.append(obst_ctg)
obsts_tg.append(obst_tg)
continue
is_visible = true
for i in range(len(obsts_ctg)):
if tg > obsts_tg[i] and ctg > obsts_ctg[i]:
is_visible = false
break
if is_visible:
light_cell(Vector2(x+x0, y+y0), 1) Работает прекрасно:
Перед написанием полноценной функции давайте немного побалуемся, ведь я же не просто так сказал в начале, что свет может быть любой формы.
У нас цикл двойной, поэтому можно легко сделать зависимость одной переменной от другой. Во внутреннем (x) цикле может быть что угодно, не только distance+1. Давайте, например, поставим tan(float(y)/distance)*distance+1:
...
for y in range(distance+1):
for x in range(tan(float(y)/distance)*distance+1):
...Получим свет такой формы:
Тангециальный свет
Или можем использовать логарифм (в годо он натуральный):
...
for y in range(distance+1):
for x in range(log(y)*distance+1):
...Получим тоже интересный результат:
Логарифмический свет
Ну и наконец сделаем самый обычный, кргуглый источник света, воспользовавшись уравнением окружности x*x + y*y = r*r:
...
for y in range(distance+1):
for x in range(sqrt(distance*distance - y*y)+1):
...Всем светам свет
Ну и как вы наверняка поняли, во второй цикл можно запихнуть в принципе любую двумерную функцию x = f(y). У меня получается зависимость x от y, потому что первым циклом я прохожу по вертикали - вы можете во главенство поставить x, тогда у вас будет привычная зависимость y от x.
Однако при использовании этого способа имейте в виду, что это может сильно повлиять на производительность. У меня логарифмический свет работал медленно уже при значениях distance > 40 (фпс падал ниже 30), при отсутствии препятствий.
Любая форма это конечно хорошо, но свет в одной четверти как то невесело - поэтому давайте делать свет таким, каким его придумала матушка природа.
Полная реализация
Чтобы сделать освещение во все стороны вовсе не обязательно как то расширять циклы - только если вы не хотите сделать разные функции в разных четвертях. Этим мы заниматься не будем, а займемся отражением координат.
Разумеется, мы не будем просто отражать координаты рисования, ведь получится так, что одно препятствие имеет тень сразу во всех четвертях. Вместо этого мы будем проверять точку на препятствие не только по координатам {x+x0, y+y0}, но и по {x-x0, y+y0}, {x-x0, y-y0} и {x+x0, y-y0}. Тогда будет необходим еще один список, в котором будет храниться четверть препятствия с ограничевающими значениями из массивов по тому же индексу:
...
var quarts:PoolByteArray = PoolByteArray()
...И при проверке препятствия помимо ограничивающих значений добавляем его четверть в этот массив. Получается четыре проверки, в которых уже нельзя пропускать итерацию, ведь мы можем поймать не только одно препятствие:
...
obst_ctg = (x-0.5)/(y+0.5)
obst_tg = (y-0.5)/(x+0.5)
if Vector2(x0+x, y0+y) in obstacles:
obsts_ctg.append(obst_ctg)
obsts_tg.append(obst_tg)
quarts.append(1)
if Vector2(x0-x, y0-y) in obstacles:
obsts_ctg.append(obst_ctg)
obsts_tg.append(obst_tg)
quarts.append(2)
if Vector2(x0+x, y0-y) in obstacles:
obsts_ctg.append(obst_ctg)
obsts_tg.append(obst_tg)
quarts.append(3)
if Vector2(x0-x, y0+y) in obstacles:
obsts_ctg.append(obst_ctg)
obsts_tg.append(obst_tg)
quarts.append(4)
...Координатные циклы у нас, напомню, не изменились. Здесь я использовал не типичные математические четверти, ибо нам без разницы - главное как то их различать.
Тогда для определения видимости точки одного флага будет мало - необходимо по флагу на четверть. В цикле точно также смотрим на значения из массивов с ограничивающими значениями и выключаем нужный флаг.
Если условие верно, это значит что в какой то четверти данная точка не видна, а чтобы определить эту четверть смотрим в новоиспеченный массив и выключаем флаг соответствующей четверти:
...
is_visible1 = true
is_visible2 = true
is_visible3 = true
is_visible4 = true
for i in range(len(obsts_ctg)):
if tg > obsts_tg[i] and ctg > obsts_ctg[i]:
match quarts[i]:
1:
is_visible1 = false
2:
is_visible2 = false
3:
is_visible3 = false
4:
is_visible4 = false
...Здесь точно также нельзя использовать break, т.к. во время цикла может выключиться сразу несколько ячеек. Хорошо, теперь осталось только нарисовать ячейки в тех четвертях, чьи флаги включены:
...
if is_visible1:
light_cell(Vector2(x+x0, y+y0), 1)
if is_visible2:
light_cell(Vector2(-x+x0, -y+y0), 1)
if is_visible3:
light_cell(Vector2(x+x0, -y+y0), 1)
if is_visible4:
light_cell(Vector2(-x+x0, y+y0), 1)
...После этого получаем свет, излучающий во все стороны. Опять же, под спойлером функция целиком и пример ее работы:
Спойлер
Функция:
func add_lighter(cell:Vector2, distance:int, color:Color=Color.white):
var x0:int = cell.x
var y0:int = cell.y
var obsts_ctg:PoolRealArray = PoolRealArray()
var obsts_tg:PoolRealArray = PoolRealArray()
var quarts:PoolByteArray = PoolByteArray()
var tg:float
var ctg:float
var obst_ctg:float
var obst_tg:float
var is_visible1:bool
var is_visible2:bool
var is_visible3:bool
var is_visible4:bool
for y in range(distance+1):
for x in range(distance+1):
tg = float(y)/x if x != 0 else distance*distance
ctg = float(x)/y if y != 0 else distance*distance
obst_ctg = (x-0.5)/(y+0.5)
obst_tg = (y-0.5)/(x+0.5)
if Vector2(x0+x, y0+y) in obstacles:
obsts_ctg.append(obst_ctg)
obsts_tg.append(obst_tg)
quarts.append(1)
if Vector2(x0-x, y0-y) in obstacles:
obsts_ctg.append(obst_ctg)
obsts_tg.append(obst_tg)
quarts.append(2)
if Vector2(x0+x, y0-y) in obstacles:
obsts_ctg.append(obst_ctg)
obsts_tg.append(obst_tg)
quarts.append(3)
if Vector2(x0-x, y0+y) in obstacles:
obsts_ctg.append(obst_ctg)
obsts_tg.append(obst_tg)
quarts.append(4)
is_visible1 = true
is_visible2 = true
is_visible3 = true
is_visible4 = true
for i in range(len(obsts_ctg)):
if tg > obsts_tg[i] and ctg > obsts_ctg[i]:
match quarts[i]:
1:
is_visible1 = false
2:
is_visible2 = false
3:
is_visible3 = false
4:
is_visible4 = false
if is_visible1:
light_cell(Vector2(x+x0, y+y0), 1)
if is_visible2:
light_cell(Vector2(-x+x0, -y+y0), 1)
if is_visible3:
light_cell(Vector2(x+x0, -y+y0), 1)
if is_visible4:
light_cell(Vector2(-x+x0, y+y0), 1)Четыре четверти это как одна, только в четыре раза лучше:
Естественно можно точно также сделать свет разной формы, вот для примера обычный круглый свет:
Тот самый свет, созданный природой
За свою жизнь вы точно видели такое, что свет с расстоянием тусклеет, а у нас он везде одинаково белый - так дело не пойдет.
За яркость света будет отвечать переменная brightness:float, которую мы будем передавать функции light_cell. Даже для полного освещения достаточно одной переменной, ведь яркость полностью симметрична для всех четвертей. Очевидно, что чем дальше ячейка от источника света, тем она тусклее.
Я буду работать с круглым светом, поэтому вычислять расстояние будем как линейное расстояние от ячейки до центра. В таком случае чем дальше от источника, тем светлее, поэтому отнимем от дистанции свечения расстояние до ячейки, ведь последнее никогда не будет больше дистанции. Также значение должно быть относительным, поэтому разделим разницу на дистанцию - таким образом получим значение от 0 до 1, то что нужно:
...
brightness = (distance - point_distance(Vector2(x0, y0), Vector2(x+x0, y+y0)))/distance
...Тут функция point_distance вычисляет евклидово расстояние между точками и выглядит так:
func point_distance(cell1:Vector2, cell2:Vector2):
return (cell1-cell2).length()Теперь просто запишем значение brightness во все light_cell:
...
if is_visible1:
light_cell(Vector2(x+x0, y+y0), brightness)
if is_visible2:
light_cell(Vector2(-x+x0, -y+y0), brightness)
if is_visible3:
light_cell(Vector2(x+x0, -y+y0), brightness)
if is_visible4:
light_cell(Vector2(-x+x0, y+y0), brightness)
...И вот, казалось бы все готово, но вот незадача - при нулевых координатах возникают яркие полосы:
Происходит это потому что при, например, x = 0 ячейки {x-x0, y+y0} и {x+x0, y+y0} имеют одну и ту же координату, поэтому там ячейка освещается два раза. Чтобы от этого избавится просто ограничим рисование условием x != 0 и y != 0 в нужных местах. Я сделал следующем образом, но вы можеет сделать по-своему, это не имеет значения:
...
if is_visible1:
light_cell(Vector2(x+x0, y+y0), brightness)
if is_visible2:
if x != 0:
light_cell(Vector2(-x+x0, -y+y0), brightness)
if is_visible3:
if y != 0:
light_cell(Vector2(x+x0, -y+y0), brightness)
if is_visible4:
if x != 0 and y != 0:
light_cell(Vector2(-x+x0, y+y0), brightness)
...Тут главное чтобы при нулевых значениях рисовалось только две симметричные точки, ведь другие две будут повторять эти. Смотрите, если x = 0, а y нет, то сработает первое и третье условия, если наоборот то первое и второе, а в общем случае - все четыре.
Оставлять код всей функции не буду, думаю сможете сами, поэтому под спойлером только пример работы:
Спойлер
Вот и все, освещение готово. Только работает как то медленновато...
Оптимизация
Что бы нормально оптимизировать надо для начала понять, где это можно сделать. Давайте посмотрим на код функции:
Функция
func add_lighter(cell:Vector2, distance:int, color:Color=Color.white):
var x0:int = cell.x
var y0:int = cell.y
var obsts_ctg:PoolRealArray = PoolRealArray()
var obsts_tg:PoolRealArray = PoolRealArray()
var quarts:PoolByteArray = PoolByteArray()
var tg:float
var ctg:float
var obst_ctg:float
var obst_tg:float
var is_visible1:bool
var is_visible2:bool
var is_visible3:bool
var is_visible4:bool
var brightness:float
for y in range(distance+1):
for x in range(sqrt(distance*distance - y*y)+1):
tg = float(y)/x if x != 0 else distance*distance
ctg = float(x)/y if y != 0 else distance*distance
obst_ctg = (x-0.5)/(y+0.5)
obst_tg = (y-0.5)/(x+0.5)
if Vector2(x0+x, y0+y) in obstacles:
obsts_ctg.append(obst_ctg)
obsts_tg.append(obst_tg)
quarts.append(1)
if Vector2(x0-x, y0-y) in obstacles:
obsts_ctg.append(obst_ctg)
obsts_tg.append(obst_tg)
quarts.append(2)
if Vector2(x0+x, y0-y) in obstacles:
obsts_ctg.append(obst_ctg)
obsts_tg.append(obst_tg)
quarts.append(3)
if Vector2(x0-x, y0+y) in obstacles:
obsts_ctg.append(obst_ctg)
obsts_tg.append(obst_tg)
quarts.append(4)
is_visible1 = true
is_visible2 = true
is_visible3 = true
is_visible4 = true
for i in range(len(obsts_ctg)):
if tg > obsts_tg[i] and ctg > obsts_ctg[i]:
match quarts[i]:
1:
is_visible1 = false
2:
is_visible2 = false
3:
is_visible3 = false
4:
is_visible4 = false
brightness = (distance - point_distance(Vector2(x0, y0), Vector2(x+x0, y+y0)))/distance
if is_visible1:
light_cell(Vector2(x+x0, y+y0), brightness)
if is_visible2:
if x != 0:
light_cell(Vector2(-x+x0, -y+y0), brightness)
if is_visible3:
if y != 0:
light_cell(Vector2(x+x0, -y+y0), brightness)
if is_visible4:
if x != 0 and y != 0:
light_cell(Vector2(-x+x0, y+y0), brightness)Очевидно, что чем больше препятствий, тем дольше будут идти проверки по типу Vector2(x+x0, y+y0) in obstacles, причем в этом учавствуют все препятствия - не только те, что хоть как то могут отбрасывать тень. По умолчанию годо использует линейный поиск - оно и понятно, ведь наш массив никак не отсортирован. Это значит, что надо вставлять элементы в нужное место, тем самым получая отсортированный массив, а затем использовать бинарный поиск.
Хорошо, при следующих данных время выполнения снизилось с ~140мс до ~65мс:
Причем даже при большем количестве препятствий время практически не меняется, ведь теперь зависимость времени выполнения алгоритма от их количества сведена к минимуму. Что бы вы понимали масштабы, если у нас было 1024 препятствия, то вместо 1024 итераций тратится только 10. Но это для одной ячейки, для четырех естественно в 4 раза больше.
На самой функции освещения это никак не отразилось, я просто при добавлении препятствия добавлял его в список на такое место, что бы тот оставался отсортированным, а при проверке точки на препятствие использовал бинарный поиск:
...
func is_obst(cell:Vector2):
var t = obstacles.bsearch(cell)
if t != len(obstacles):
return obstacles[t] == cell
else:
return false
...
obstacles.insert(obstacles.bsearch(mouse_cell), mouse_cell)
...В годо функция Array.bsearch возвращает индекс элемента если таковой имеется, иначе индекс, по которому тот бы находился в случае отсортированного массива.
И вместо Vector2(x0+x, y0+y) in obstacles я использовал is_obst(Vector2(x0+x, y0+y)). Ну, разумеется, для всех четвертей. Поглазеть на полный код сможете кликнув по ссылке в конце статьи.
Также можно заметить, что если препятствие само находится в тени, то нет смысла его рассматривать, т.к. оно не даст новой тени. Однако просто сравнив угол ячейки, в которой находится это препятствие также, как и для обычной, мы полчим неверный результат, ведь если не видно ее центра, не факт что не видно какой то из углов, который отбрасывает тень:
В таком количестве цветов сложно что то понять, сейчас поясню. Черная линия проходит через центр правого препятствия и сравнив его как обычную ячейку мы получили бы, что оно не дает новой тени, т.к. заслонено другим препятствием, однако нижняя зеленая линия явно видна и потому дает тень. В таком случае для препятствий будем сравнивать его ограничивающие значения с другими препятствиями, и, если под условие не подпадает хотя бы одно из, то добавляем препятствие как обычно.
Разумеется, запускать цикл проверки на видимость в каждом условии слишком жирно, поэтому перенесем этот цикл на место перед добавлением препятствий и добавим еще четыре флага (по одному на четверть), которые показывают, надо ли препятствие добавлять.
Тогда перед основным циклом проверки на видимость проверяем на препятствия точку и поднимаем нужный флаг в случае совпадения, а в цикле проверки на видимость дополнительно сравниваем ограничивающие значения что бы понять, добавляет ли препятствие новую тень.
Под спойлером функция целиком:
Спойлер
func add_lighter(cell:Vector2, distance:int, color:Color=Color.white):
var x0:int = cell.x
var y0:int = cell.y
var obsts_ctg:PoolRealArray = PoolRealArray()
var obsts_tg:PoolRealArray = PoolRealArray()
var quarts:PoolByteArray = PoolByteArray()
var tg:float
var ctg:float
var obst_ctg:float
var obst_tg:float
var is_visible1:bool
var is_visible2:bool
var is_visible3:bool
var is_visible4:bool
var is_obst1:bool
var is_obst2:bool
var is_obst3:bool
var is_obst4:bool
var brightness:float
for y in range(distance+1):
for x in range(sqrt(distance*distance - y*y)+1):
tg = float(y)/x if x != 0 else distance*distance
ctg = float(x)/y if y != 0 else distance*distance
obst_ctg = (x-0.5)/(y+0.5)
obst_tg = (y-0.5)/(x+0.5)
is_obst1 = false
is_obst2 = false
is_obst3 = false
is_obst4 = false
if is_obst(Vector2(x0+x, y0+y)):
is_obst1 = true
if is_obst(Vector2(x0-x, y0-y)):
is_obst2 = true
if is_obst(Vector2(x0+x, y0-y)):
is_obst3 = true
if is_obst(Vector2(x0-x, y0+y)):
is_obst4 = true
is_visible1 = not is_obst1 # Если мы наткнулись на препятствие, то не освещаем ячейку
is_visible2 = not is_obst2
is_visible3 = not is_obst3
is_visible4 = not is_obst4
for i in range(len(obsts_ctg)):
if tg > obsts_tg[i] and ctg > obsts_ctg[i]:
match quarts[i]:
1:
is_visible1 = false
# та самая проверка
if obst_tg > obsts_tg[i] and obst_ctg > obsts_ctg[i]:
is_obst1 = false
2:
is_visible2 = false
if obst_tg > obsts_tg[i] and obst_ctg > obsts_ctg[i]:
is_obst2 = false
3:
is_visible3 = false
if obst_tg > obsts_tg[i] and obst_ctg > obsts_ctg[i]:
is_obst3 = false
4:
is_visible4 = false
if obst_tg > obsts_tg[i] and obst_ctg > obsts_ctg[i]:
is_obst4 = false
if is_obst1:
obsts_tg.append(obst_tg)
obsts_ctg.append(obst_ctg)
quarts.append(1)
if is_obst2:
obsts_tg.append(obst_tg)
obsts_ctg.append(obst_ctg)
quarts.append(2)
if is_obst3:
obsts_tg.append(obst_tg)
obsts_ctg.append(obst_ctg)
quarts.append(3)
if is_obst4:
obsts_tg.append(obst_tg)
obsts_ctg.append(obst_ctg)
quarts.append(4)
brightness = (distance - point_distance(Vector2(x0, y0), Vector2(x+x0, y+y0)))/distance
if is_visible1:
light_cell(Vector2(x+x0, y+y0), brightness)
if is_visible2:
if x != 0:
light_cell(Vector2(-x+x0, -y+y0), brightness)
if is_visible3:
if y != 0:
light_cell(Vector2(x+x0, -y+y0), brightness)
if is_visible4:
if x != 0 and y != 0:
light_cell(Vector2(-x+x0, y+y0), brightness)Время выполнения функции при следующих данных снизилось с типичных ~65мс до ~40мс:
Наверняка внимательный читатель заметил, что в затравке к статье препятствия были синего цвета, а в самой статье они всегда красные. Это не просто так.
Я думаю многие слыхали легенды о медленности Gdscript, поэтому я просто не мог пройти мимо оболочки GDNative, которая позволяет писать код для ноды не только на C++, но и некоторых других языках, однако я буду использовать именно первый вариант.
Алгоритм, разумеется, не поменялся, поэтому я просто переписал код с gdscript на c++ и спустя нескольких неотразимых балетов с бубном мне все таки удалось заставить это работать. Я компилировал только под Windowns, счастливым обладателям Linux видимо придеться самим. Теперь, при следующей конфигурации время выполнения функции всего то около 10 мс:
Под спойлером код на c++:
Спойлер
tile_lights.h:
#ifndef TILELIGHTS_H
#define TILELIGHTS_H
#include <Godot.hpp>
#include <Node2D.hpp>
#include <VisualServer.hpp>
namespace godot{
class TileLighter : public Node2D{
GODOT_CLASS(TileLighter, Node2D)
private:
RID surface;
int cell_size;
Array obstacles;
public:
static void _register_methods();
TileLighter();
~TileLighter();
void _init();
void _process(float delta);
Vector2 pixel2cell(Vector2 pixel);
Vector2 cell2pixel(Vector2 cell);
void light_cell(Vector2 cell, float brightness);
void fill_cell(Vector2 cell, Color color);
bool is_obstacle(Vector2 cell);
void add_obstacle(Vector2 cell);
void clear_obstacles();
Array get_obstacles();
void clear_obstacles_canvas();
void add_circle_lighter(Vector2 cell, int distance);
float point_distance(Vector2 p1, Vector2 p2);
};
}
#endiftile_lights.cpp:
#include <tile_lights.h>
using namespace godot;
void TileLighter::_register_methods(){
register_method("_process", &TileLighter::_process);
register_method("fill_cell", &TileLighter::fill_cell);
register_method("light_cell", &TileLighter::light_cell);
register_method("is_obstacle", &TileLighter::is_obstacle);
register_method("add_obstacle", &TileLighter::add_obstacle);
register_method("clear_obstacles", &TileLighter::clear_obstacles);
register_method("get_obstacles", &TileLighter::get_obstacles);
register_method("clear_obstacles_canvas", &TileLighter::clear_obstacles_canvas);
register_method("add_circle_lighter", &TileLighter::add_circle_lighter);
register_method("pixel2cell", &TileLighter::pixel2cell);
register_method("cell2pixel", &TileLighter::cell2pixel);
register_property<TileLighter, int>("cell_size", &TileLighter::cell_size, 4);
}
void TileLighter::_process(float delta){
}
void TileLighter::_init(){
cell_size = 4;
obstacles = Array();
surface = VisualServer::get_singleton()->canvas_item_create();
VisualServer::get_singleton()->canvas_item_set_parent(surface, get_canvas_item());
}
TileLighter::TileLighter(){
}
TileLighter::~TileLighter(){
}
void TileLighter::fill_cell(Vector2 cell, Color color){
Rect2 rect = Rect2(cell2pixel(cell), Vector2(cell_size, cell_size));
VisualServer::get_singleton()->canvas_item_add_rect(surface, rect, color);
}
void TileLighter::light_cell(Vector2 cell, float brightness){
fill_cell(cell, Color(1.0, 1.0, 1.0, brightness));
}
bool TileLighter::is_obstacle(Vector2 cell){
int i = obstacles.bsearch(cell);
if (i < obstacles.size())
return obstacles[i] == cell;
else
return false;
}
void TileLighter::add_obstacle(Vector2 cell){
obstacles.insert(obstacles.bsearch(cell), cell);
}
void TileLighter::clear_obstacles(){
obstacles.clear();
}
Array TileLighter::get_obstacles(){
return obstacles;
}
void TileLighter::clear_obstacles_canvas(){
VisualServer::get_singleton()->canvas_item_clear(surface);
}
Vector2 TileLighter::pixel2cell(Vector2 pixel){
return (pixel/cell_size).floor();
}
Vector2 TileLighter::cell2pixel(Vector2 cell){
return cell*cell_size;
}
void TileLighter::add_circle_lighter(Vector2 cell, int distance){
int x0 = cell.x;
int y0 = cell.y;
PoolRealArray obsts_tg = PoolRealArray();
PoolRealArray obsts_ctg = PoolRealArray();
PoolIntArray quarts = PoolIntArray();
bool is_visible1, is_visible2, is_visible3, is_visible4;
bool is_obst1, is_obst2, is_obst3, is_obst4;
float tg, ctg;
float obst_tg, obst_ctg;
float o1, o2;
float brightness;
for(int y = 0; y <= distance; y++){
for(int x = 0; x < sqrt(distance*distance - y*y) + 1; x++){
tg = x != 0 ? (float)y/x : distance*distance;
ctg = y != 0 ? (float)x/y : distance*distance;
is_obst1 = false;
is_obst2 = false;
is_obst3 = false;
is_obst4 = false;
obst_tg = (y-0.5)/(x+0.5);
obst_ctg = (x-0.5)/(y+0.5);
if (is_obstacle(Vector2(x+x0, y+y0))){
is_obst3 = true;
}
if (is_obstacle(Vector2(-x+x0, -y+y0))){
is_obst1 = true;
}
if (is_obstacle(Vector2(-x+x0, y+y0))){
is_obst2 = true;
}
if (is_obstacle(Vector2(x+x0, -y+y0))){
is_obst4 = true;
}
is_visible1 = !is_obst1;
is_visible2 = !is_obst2;
is_visible3 = !is_obst3;
is_visible4 = !is_obst4;
for(int i = 0; i < obsts_tg.size(); i++){
o1 = obsts_tg[i];
o2 = obsts_ctg[i];
if (tg > o1 && ctg > o2){
if (quarts[i] == 3){
is_visible3 = false;
if (obst_tg > o1 && obst_ctg > o2)
is_obst3 = false;
}
else if (quarts[i] == 1){
is_visible1 = false;
if (obst_tg > o1 && obst_ctg > o2)
is_obst1 = false;
}
else if (quarts[i] == 2){
is_visible2 = false;
if (obst_tg > o1 && obst_ctg > o2)
is_obst2 = false;
}
else if (quarts[i] == 4){
is_visible4 = false;
if (obst_tg > o1 && obst_ctg > o2)
is_obst4 = false;
}
}
}
if (is_obst1){
obsts_tg.append(obst_tg);
obsts_ctg.append(obst_ctg);
quarts.append(1);
}
if (is_obst2){
obsts_tg.append(obst_tg);
obsts_ctg.append(obst_ctg);
quarts.append(2);
}
if (is_obst3){
obsts_tg.append(obst_tg);
obsts_ctg.append(obst_ctg);
quarts.append(3);
}
if (is_obst4){
obsts_tg.append(obst_tg);
obsts_ctg.append(obst_ctg);
quarts.append(4);
}
brightness = (distance-point_distance(Vector2(x0, y0), Vector2(x+x0, y+y0)))/distance;
if (x != 0){
if (is_visible3)
light_cell(Vector2(x+x0, y+y0), brightness);
if (y != 0 && is_visible4)
light_cell(Vector2(x+x0, -y+y0), brightness);
}
if (y != 0 && is_visible1)
light_cell(Vector2(-x+x0, -y+y0), brightness);
if (is_visible2)
light_cell(Vector2(-x+x0, y+y0), brightness);
}
}
}
float TileLighter::point_distance(Vector2 p1, Vector2 p2){
return (p1-p2).length();
}Тут наверно стоит сказать, что я полный дилетант в области c++ и знаком лишь с его основами, поэтому видя нечто ужасное просто пишите об этом в комментарии, плакать не стоит.
Наверняка можно придумать еще кучу вещей для оптимизации, однако я остановился на самых жирных и думаю что этого вполне достаточно, ведь вряд ли вы будете обновлять свет каждый кадр как это делал я, а делать это только когда меняется положение источника. Также не думаю, что вам понадобится дальность света больше 15, а при меньших значениях скорость c++ реализации просто запредельна. По этой же причине я думаю бессмысленно пытаться сделать это на видиокарте через шейдер.
Завершение
Разумеется, данный алгоритм предназначен только для тайлмапов и его не следует использовать для обычного освещения. В целом я думаю получилось вполне неплохо, на мой взгляд этот алгоритм гораздо больше подходит для освещения тайлмапа, чем какой нибудь рейкастинг.
Не смотря на все этот алгоритм просвечивает в соединениях препятствий углами, однако я считаю что это просто особенность дискретности, поэтому на это можно закрыть галаза, но учитывать при проектировании уровней.
Также я думаю для этого способа можно придумать кучу куч всяких модификаций, например для получения сглаженных границ свет-тень. Если вдруг что то такое сделаете, пишите мне - разберемся и я добавлю сюда вашу реализацию.
Я начинаю потихоньку осваивать искусство git и github, поэтому заглядывайте ко мне в репозиторий, в котором лежит не только код с этой статьи, но и парочка других функций для освещения.
Что ж, надеюсь вы приятно провели время и приметили что то для себя, читая этот пост. Если это не так - прочитайте еще раз :) А так до следующих встреч - да будут они скорыми.
