Простая линия взгляда
Данная статья была написана для RLNews Darren'а Hebden'а
Эту статью некоторые из вас могут посчитать интересной. Я искал какой-нибудь простой код линии взгляда (line_of_sight, LOS), и после продолжительных поисков, я нашёл несколько исходников, которые и были именно тем, что я искал. На сайте x2ftp, я обнаружил коллекцию графических дагоценностей (graphical gems collection), которая содержала программу на Си, называвшуюся Цифровое Рисование Линии (Digital Line Drawing) Paul'а Heckbert'а. Программа была описана как: "digline: нарисуйте цифровую линию из (x1,y1) в (x2,y2), вызывая определяемую пользователем процедуру на каждом пикселе. Никаких отсечений. Использует алгоритм Брезенхема (Bresenham)". Если вам интересно посмотреть оригинальный код, я могу послать его вам или вы можете найти его на сайте x2ftp.
Оригинальный код LOS, который был в моей игре только проверяет, находится ли игрок в том же секторе, что и монстр. Если это так, то монстр может увидеть игрока. Я хотел, чтобы мой код LOS был такого типа, что зная координаты x,y монстра и координаты x,y игрока, вы могли бы нарисовать линию между этими двумя точками, чтобы проверить, блокируется ли обзор монстра какими-нибудь объектами. Это то, что сейчас есть у меня. Сейчас не имеет значения как далеко игрок, если обзор монстра не заблокирован, он может видеть игрока. Позднее я изменю это, чтобы ограничить расстояние, на которое монстр может видеть, но я также хочу, чтобы некоторые монстры могли видеть дальше, чем другие.
Код, о котором я буду рассказывать, будет модификацией кода, который я использую в моей программе. Я начал с попытки использовать код с как можно меньшими по возможности изменениями. При запуске моей программы выполнение этого кода вызывало её зависание на продолжительное время. После обширной диагностики и внесения изменений я, наконец, заставил её работать. Я обнаружил, что если игрок стоит в определенной позиции относительно монстра, то код не работает. Я выяснил, что если координата y игрока меньше или равна y монстра, программа работает правильно. Если x игрока меньше чем x монстра и y игрока больше, чем y монстра, тогда монстр не видит игрока, но программа не зависает. Если же x и y игрока больше, чем x и y монстра, программа зависает.
После продолжительного вырывания на себе волос и произнесения многих красочных фраз из области программирования :+) я, наконец, нашёл, в чём проблема. Оригинальный код использовал макрос, называвшийся SGN, чтобы возвращать знак разности x и y. Он определялся как:
#define SGN(a)(((a)<0) ? -1 : 0)
Посмотрите на описание макроса "взять знак a, как -1, так и 1 если >= 0". Я еще учусь но, похоже, что он возвращает только или -1 или 0, а не -1 или 1 как сказано в описании.
После замены макроса на следующий:
#define SGN(a)(((a)<0) ? -1 : 1)
всё по-видимому начнёт работать.
Вот код, который я использую в своей программе. Ремарки поясняют код настолько хорошо, насколько я могу. Если я допустил какую-либо неточность в своих объяснениях и кто-нибудь будет любезен мне об этом сообщить, я внесу изменения. Я надеюсь, что это поможет тем, кто ищет, как сделать что-то аналогичное.
/* Код линии взгляда это Boolean функция * * которая возвращает FALSE если * * монстр не может видеть игрока и TRUE * * если может * * Это x и y координаты монстра */ BOOL los(coord mx, coord my) { int t, x, y, ax, ay, sx, sy, dx, dy; dx = d.px - mx; dy = d.py - my; /* ax & ay: абсолютные значения dx & dy * * умноженные на 2 (сдвиг влево на 1) */ ax = abs(dx)<<1; ay = abs(dy)<<1; /* sx & sy: знак от dx & dy */ sx = SGN(dx); sy = SGN(dy); x = mx; y = my; /* Следующее утверждение проверяет если линия * * x доминирует над y или наоборот и соответственно зацикливает */ if(ax > ay) { /* Цикл по X */ /* t = обсолютное от y минус абсолютное от x деленное * на 2 (сдвиг вправо на 1) */ t = ay - (ax >> 1); do { if(t >= 0) { /* если t больше либо равно 0 тогда * * добавить знак от dy к y * * вычесть абсолютное от dx из t */ y += sy; t -= ax; } /* добавить знак dx к x * * добавить абсолютное значение dy к t */ x += sx; t += ay; /* проверить, если мы в позиции игрока */ if x == d.px && y == d.py) { /* возвращает, что чудовище может видеть игрока */ return TRUE; } /* продолжаем цикл, пока зрение чудовища не заблокировано */ while(sight_blocked(x,y) == FALSE); /* Заметьте: sight_blocked - функция возвращает true * * если объект по x,y координатам блокирует взгляд монстра */ /* цикл завершается т.к. взгляд монстра блокируется * * возвращаем FALSE: монстр не видит игрока */ return FALSE; } else { /* Цикл по Y */ t = ax - (ay >> 1); do { if(t >= 0) { x += sx; t -= ay; } y += sy; t += ax; if(x == d.px && y == d.py) { return TRUE; } } while(sight_blocked(x,y) == FALSE); return FALSE; } }
Ну вот и всё. Не слишком сложно, поскольку я просчитал как это работает. Я видел много line_of_sight кодов, но я был не в состоянии просчитать как они работают. Этот код очень простой, но он хорошо делает своё дело. Позже я собираюсь внести изменения, но вам нужно с чего-нибудь начинать.
Я надеюсь, это поможет кому-то, кто подобно мне только начинает, понять некоторые из тайн разработки Roguelike-игр.
Автор: Steve Register.
Источник: Line of Sight.
Перевел: Дмитрий О. Бужинский [Bu], 18.05.2005.