Открываем карту

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

Алгоритм очень простой и основан на физическом законе о том что свет распространяется по прямой.

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

Герой может видеть только по прямой, соответственно он увидит следующую картину.

Значит карту нужно открыть вот таким образом.

Теперь от простого алгоритма к простой реализации, тут нужно вспомнить математику, а те кто думают, что в программирование не нужна математика, те смело могут идти работать продавцами мороженого.
Итак нам всего-то нужно перевод из радиальные координат в декартовые, где вектором будет линия зрения, поворачивающая на угол от 0…360. При наползании на стену луч останавливается.

char *signMap = new char[map.w*map.h];
memset(signMap,0,map.w*map.h);
for(double a=0;a<2*M_PI;a+=0.05)
{
int px1=x;
int py1=y;
for(double r=0;r<=(double)radius+0.5;r+=0.5)
{
int x1= x+(int)(r * cos(a));
int y1= y+(int)(r * sin(a));
if (x1<0 || y1<0 || x1>=map.w || y1>=map.h) break;

signMap[y1*map.w+x1]=1;
if (map.data[y1*map.w+x1]) break;
if (x1!=px1 && y1!=py1)
{
int dx = x1>px1?1:-1;
int dy = y1>py1?1:-1;
if (map.data[ (py1+dy)*map.w+px1] && map.data[ py1*map.w+px1+dx]) break;
}
px1=x1;
py1=y1;
}
}
Заморочка только с прохождением луча ровно по диагонали между двумя препятствиями, по законам большинства игр, так ходить нельзя, а вот можно ли смотреть – остается под вопросом.

Сложности.
Алгоритм не так быстр, вернее так-то он быстр, а вот при многократном и/или большом угле зрения на пустом месте может считаться долго (синусы и косинусы).
Можно разбить лучи по 15 градусов и вручную проверять только их, на небольших расстояниях (<10 клеток) действие алгоритма будет такое же.