Всем привет! Сразу хочу извиниться если материал покажется вам скопированным откуда-то, или просто очень знакомым. Часть всего, что я здесь расскажу, действительно была описана несколько тысяч раз и давно уже используется, но мне всё же хочется верить, что самое главное в этой статье я придумал сам :)
Итак, сама идея пришла во время разработки одного 2d платформера, когда мне понадобилось освещение. После недолгих поисков я нашел некоторые библиотеки которые мне помогли в решении моей задачи, однако я заметил, что работают они не так быстро как я хотел бы этого. Тогда я начал думать как бы это соорудить самому, и уже в процессе наткнулся на статью Nicky Case’а о 2d освещении. Так что предупреждаю что начало у нас будет совпадать (тем более что это достаточно известный алгоритм).
Вообще начнем с постановки задачи, ведь формулировки: «хочу чтоб был свет», немного недостаточно. Мы хотим получить набор набор точек «видимых» из некой точки X. Видимая точка - это такая точка, что если мы проведем отрезок из источника света в эту точку, то этот отрезок не пересечет никакое препятствие. В роли препятствий будут выступать отрезки, так как с некоторой точностью мы можем представить любую фигуру в виде набора отрезков, а еще с ними удобно работать. Сразу после постановки задачи мы уже можем написать первую программу которая будет делать то что мы хотим. Просто проведем всевозможные отрезки из источника света в каждый пиксель, и окрасим «видимые» пиксели в какой-нибудь цвет. Отлично, работает! Правда работает жуть как долго, и это явно нас не устраивает.
Теперь я хотел бы немного изменить механику с которой мы работаем. Давайте вместо отрезков использовать лучи, во-первых они требуют 3х значений (вместо 4х у отрезка) для их задания (x, y, angle), а во-вторых просто впоследствии нам это очень поможет(не хочу раскрывать все карты сразу).
Теперь вместо отрезков мы можем пускать лучи. Начальная точка нашего луча это, очевидно, позиция нашего источника света а, направление луча задаёт некий угол, соответственно изменяя угол мы будем менять наш луч. Нам остаётся только проверять пересекается ли он с препятствиями, и самое важное где он с ними пересекается. Делается это с помощью незамысловатой функции: (Мб опишу её работу поподробнее ибо у ники не оч всё правильно)
function Dist(ray,segment){
let r_px = ray.x,
r_py = ray.y,
s_px = segment.x1,
s_py = segment.y1,
r_dx = ray.dx,
r_dy = -ray.dy,
s_dx = segment.x2 - segment.x1,
s_dy = segment.y2 - segment.y1;
if((r_dx == s_dx && r_dy == s_dy)||(r_dx == -s_dx && r_dy == -s_dy)){
return Infinity;
}
let T2 = (r_dx*(s_py-r_py) + r_dy*(r_px-s_px))/(s_dx*r_dy - s_dy*r_dx);
let T1 = (s_px+s_dx*T2-r_px)/r_dx;
if(Math.abs(r_dx) <= 0.00001){
T1 = (s_py+s_dy*T2-r_py)/r_dy;
}
if(T1 >= 0 && T2 >= -0.00000000001 && T2 <= 1.000000000001){
return T1;
}else return Infinity;
}Стоит уточнить, что для корректной работы, неплохо бы ограничить область которую мы освещаем. Например я просто добавил прямоугольник размером с экран. И вот наша первая демка готова, просто двигаем мышку и пускаем луч из центра в направлении курсора.
Если вам кажется, что это не совсем свет, то вы неправы. Ну так давайте просто пустим лучи во все стороны, скажем штук 30. И вот что у нас получится:
Однако вот какой тут подводный камень: если мы соединим все точки пересечения, то получим область которая местами не очень совпадает с реальным «рельефом». И даже если увеличить количество точек до 360 ничего путного не получается.
P.S. после увеличения количества лучей до 3600 картинка стала заметно лучше, однако на производительности это плохо сказалось.
Небольшая зарисовка, почему так получается:
Если вкратце, то мы просто промахиваемся мимо отрезка.
Тогда мы делаем очень важное замечание: вообще-то говоря нам надо пускать лучи только в концы каждого отрезка! Кратко поясняю почему. Если наши лучи(красный цвет) пересекают только этот отрезок, то мы получим линию(зеленый цвет) идеально совпадающую с отрезком.
Если у нас на пути встретится другой отрезок, то всё тоже получится, конечно не так, как мы бы хотели. И чтобы это исправить пустим для каждой вершины отрезка по 2 дополнительных луча сдвинутых например на 0.001 и -0.001 радиан. Получится что-то вроде этого:
И в конце концов мы получили хороший алгоритм который работает и выдает хороший результат (его визуализацию вы сможете увидеть в конце статьи, так как визуально мы больше ничего не поменяем).
Ура, мы пришли к самой интересной и алгоритмической части, присаживайтесь по-удобнее, берите чаёк и наслаждайтесь!
Как мы можем видеть самая затратная часть алгоритма это нахождение ближайшего пересечения луча, и пока что мы это делали тривиально (брали минимум среди пересечений со всеми отрезками), и в конечном итоге это выливается в O(n^2). Конечно же это можно делать быстрее. Например можно использовать kd дерево, но я хочу предложить вашему вниманию другой алгоритм.
Пока мы перебирали все отрезки и брали минимум среди их расстояний до луча, большое количество отрезков просто не пересекались с ним. Поэтому нам надо как-то их отсекать. В kd дереве мы делим плоскость (в нашем случае) с помощью линий параллельных одной из осей, и отсекаем части в которых наш луч просто не проходит. Но что если мы будем делить нашу плоскость не прямыми, а тоже лучами. Вот о чем я говорю: Пусть у нас есть источник света и некий отрезок, проведем два луча в каждую из точек и запомним углы этих лучей. Тогда чтобы какой-либо луч пересек наш отрезок нам достаточно чтобы угол под которым мы его пускаем лежал между углами лучей которые мы пускали в концы это отрезка.
class Interval{
constructor(_s,_f,_ref){
this.begin = _s;
this.end = _f;
this.reference = _ref;
}
}
function Rad(dx,dy){
let cs = dx/(Math.sqrt(dx*dx+dy*dy));
let angle = acos(cs);
if(dy < 0.){
angle = 2*Math.PI - angle;
}
return angle;
}
function SegmentToInterval(lightPoint,segment){
let first,second;
let dx = segment.x1 - lightPoint.x;
let dy = lightPoint.y - segment.y1;
first = Rad(dx,dy);
dx = segment.x2 - lightPoint.x;
dy = lightPoint.y - segment.y2;
second = Rad(dx,dy);
if(second > first){
if(second - first >= Math.PI){
first += 2.*Math.PI;
}
}else{
if(first - second >= Math.PI){
second += 2.*Math.PI;
}
}
return new Interval(Math.min(first,second),Math.max(first,second),segment);
}Теперь мы можем получить все отрезки которые ТОЧНО пересекаются с нашим лучом. Остается только научиться оптимально это делать. Тут нам на помощь приходит дерево интервалов. Работает оно очень просто, также как и обычное бинарное дерево. Заменим наши отрезки на упорядоченные пары значений (интервалы), углов между источником света и концами отрезка. Для каждой вершины мы будем выбирать некое значение (позже разберем каким именно образом) X. В левое поддерево мы передадим все интервалы которые левее X, а в правое все которые правее. В самой же вершине мы будем хранить два массива интервалов, которые пересекают X, отсортированных по первому значению и по второму. Весь код можно найти здесь. Понятно, что если дерево будет сбалансировано, то за время O(log(n)+k), где n это количество отрезков, а k это размер ответа, мы сможем найти все интервалы удовлетворяющие условию. Теперь придумаем как нам так выбирать значения X чтобы в итоге у нас получилось сбалансированное дерево. Можно взять медиану середин всех отрезков, но это не гарантирует хорошее разбиение. К счастью был придуман прекрасный алгоритм поиска k-ой порядковой статистики за время O(n). Мне достаточно лень его здесь описывать поэтому я просто сошлюсь на статью об этом алгоритме. Благодаря этому, мы можем построить хорошо сбалансированное дерево за время O(n*log(n)) и быстро находить в нем ответ.
Хочется добавить, что дерево нам придется строить каждый раз как перемещается источник света, так как нету способа как-то сопоставить старые интервалы с новой позицией источника.
Ну и собственно сам результат: