Простая линия взгляда

Данная статья была написана для 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.