Линия взгляда

Материал из Клуб любителей рогаликов
Перейти к: навигация, поиск

Эта статья описывает мои наблюдения, существующих систем линии зрения в roguelike-играх и подробно описывает метод, который я принял для своего собственного экспериментального движка.

Ранняя LOS (Line Of Sight - линия зрения) (Moria)

Когда я начал играть в Moria на Amiga в 1990, меня немедленно зацепило на roguelike-играх. Исследование подземелий было одним из основных 'зацепляющих факторов'. Поскольку игрок перемещался в подземелье, новая часть должна была освещаться, показывая чуть больше. Вы действительно не знали, что будет за следующим углом, или как изменится местность подземелья.

По сравнению с более последними roguelike-играми, Moria использует очень простой метод определения линии зрения. Источник света игрока может распространяться только на 1 ячейку вокруг игрока. Когда игрок входит в комнату, которая освещена, вся комната появляется и запоминается игроком. Определить, видны ли монстры, позволяет остлеживание линии от монстра к игроку. Если линия прослеживается без пересечения любых ячеек стены, то монстр видим.

В этой системе есть одно довольно серьёзное узкое место. Необходимо чтобы каждый монстр, мог быть видим, чтобы линия прослеживалась. Для карты с высокой концентрацией монстров (как например, нерест червей), это приводит к ухудшению работы.

Тем не менее, для большинства случаев система линии зрения в Moria - быстрая и эффективная. Moria была написана во второй половине 80-х, так что это было необходимо. С увеличением скоростей процессора и технологий компиляторов, новые roguelike-игры усовершенствовали процесс LOS далее, чтобы создавать более реалистичные движки.

Более реалистичная LOS (Angband)

В большинстве последних roguelike-игр, код линии зрения расширился, чтобы охватывать 'поле зрения' ('field of view'). Чтобы представить себе это, вообразим источник света, испускающий лучи света в заданном радиусе. Каждая ячейка, которая пересекается лучом света помечается как видимая. Тем не менее некоторые ячейки могут быть в тени источника света. Рисунок ниже показывает простой пример этого.

 %%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%      Обозначения:
 %%      %%%%%%%
 %#...   %%%%%%%        @ Источник света
 %#......#######        # Стена, освещённая лучом света
 %#.......@.....        % Стена в тени
 %#......#######        . Пол, освещённый лучом света
 %#...   %%%%%%%          Пол в тени (пустой)
 %%      %%%%%%%
 %%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%

Есть несколько преимуществ в выполнении такой системы. Если ячейка 'знает' о любых монстрах, которые на ней стоят, при помечании ячейки как видимой, мы можем также пометить всех монстров, которые находятся на линии зрения игрока. Нам больше не нужно делать затратный алгоритм отслеживания линии между монстром и игроком, чтобы определять видимость монстров. Это также позволяет нам, включать хорошие визуальные эффекты такие например, как затенение области карты, которая находится в памяти игрока, но не видна в данный момент.

Как мы должны подойти к написанию такой программы?

Для простоты скажем, что у нас есть поле зрения с радиусом 6 ячеек. Один метод должен отслеживать линию между источником света и каждой ячейкой на краю поля зрения. Если мы немного упростим этот процесс, давайте скажем, что наше поле зрения - квадрат с источником света с координатами (0, 0). Рисунки ниже показывают первые три итерации этого метода.

1-я Итерация: Отслеживает линию между (0, 0) и (6, 0)

  +-----+-----+
  |           |
  |           |
  |           |
  |           |
  |           |
  |           |
  +     @******
  |           |
  |           |
  |           |
  |           |
  |           |
  |           |
  +-----+-----+

2-я Итерация: Отслеживает линию между (0, 0) и (6, 1)

  +-----+-----+
  |           |
  |           |
  |           |
  |           |
  |           |
  |           |
  +     @***  +
  |         ***
  |           |
  |           |
  |           |
  |           |
  |           |
  +-----+-----+

3-я Итерация: Отслеживает линию между (0, 0) и (6, 2)

  +-----+-----+
  |           |
  |           |
  |           |
  |           |
  |           |
  |           |
  +     @**   +
  |        ** |
  |          **
  |           |
  |           |
  |           |
  |           |
  +-----+-----+

Если любое отслеживание линии упёрлось в стену, тогда отслеживание завершено и начинается новое. Каждая ячейка, которую пересекает линия помечается как видимая.

Реализация такой программы очень легка. Я не вдаюсь здесь в подробности относительно того, как проходить вдоль линии. Поищите существующие программы рисования линии или сделайте её сами. Одна вещь, которой следует избегать - использование чисел с плавающей запятой - выполняйте все вычисления во внутреннем цикле с целыми числами.

Здесь нужно заметить следующее. Когда Вы отслеживаете линию, Вы должны тщательно проследить за тем, чтобы проверялась каждая из ячеек, через которые проходит линия. Это чуть сложнее, чем Вы можете сначала подумать. Рассмотрим следующий рисунок.

     0   1   2

   +---+---+---+
   |   |   |   |
 0 | @ |   |   |
   |  *|   |   |
   +--*+---+---+
   |   *   |   |
 1 |   |*  |   |
   |   |*  |   |
   +---+-*-+---+
   |   |  *|   |
 2 |   |  *|   |
   |   |   *   |
   +---+---+*--+

Линия проходит сквозь ячейки (0, 1), (1, 1), (1, 2) и (2, 2). Если мы пройдём вдоль линии с интервалами в 1 ячейку вдоль оси y, то мы можем пропустить пересечение с ячейками (0, 1) и (2, 2). Чтобы решить эту проблему, нам в действительности нужно проходить вдоль линии с интервалами в 0.5 ячейки.

Этот простой метод очерчивает основное приближение к реализации определения линии зрения. Тем не менее, если Вы должны использовать его, Вы найдете, что его эффективность очень слабая. Позвольте мне объяснить почему. Скажем, у нас есть радиус 25 ячеек. Прохождение от центра до края поля зрения, предполагая, что пересечений со стенами нет, займёт 50 итераций (при прохождении на 0.5 ячейки). В общей сложности на каждых 4 краях 50 ячеек следовательно общее число итераций будет (50 * 4) * 50 = 10000 предполагая, что пересечений со стенами нет. Всего в нашем поле зрения 2600 ячеек (не включая центральную ячейку). Это означает, что алгоритм почти по четыре раза проверяет каждую из имеющихся в поле зрения ячеек!

Очевидно, нам нужно найти способ оптимизировать исполнение так, чтобы требовалось проверять меньшее количество ячеек. Для моего собственного экспериментального движка, я использовал следующий метод. Это почти идентично алгоритму первоначально предложенному и осуществленному в Angband 2.8.3.

Улучшенная обработка LOS (Angband 2.8.3)

Наиболее очевидный путь оптимизации обработки заключается в том, чтобы разделить поле зрения и сконцентрировать нашу оптимизацию только в одном секторе. Мы можем затем зеркально отобразить процесс во всех других секторах. Если мы разделим поле зрения на восемь, мы создадим 8 треугольных октантов, как показано на рисунке ниже. Для простоты, я полагаю поле зрения квадратным. Октанты пронумерованы от 0 на 7 и расположены по часовой стрелке вокруг источника света. Каждый октант имеет общие края с двумя соседними октантами.

    +------+------+
    |\     |     /|
    | \  5 | 6  / |
    |  \   |   /  |
    |   \  |  /   |
    | 4  \ | /  7 |
    |     \|/     |
    +------@------+
    |     /|\     |
    | 3  / | \  0 |
    |   /  |  \   |
    |  /   |   \  |
    | /  2 | 1  \ |
    |/     |     \|
    +------+------+

Если мы оптимизируем наш алгоритм, чтобы он работал только для октанта 0, мы сможем легко переключать x и y и изменять их знаки, чтобы отобразить алгоритм на любой из других 7 октантов. Например, прохождение через x в октанте 0 такое же как и прохождение через -x в октантах 3 или 4, через -y в октантах 5 или 6, и через y в октантах 1 или 2.

Вторые правила оптимизации - заранее вычислять столько, сколько Вы можете и, сколько позволяет память. Поскольку нам нужно обрабатывать только 1/8 нашего поля зрения, мы уменьшили сумму памяти требовавшейся, чтобы хранить наши таблицы поиска.

Помните, что мы использовали аналогию источника света, испускающего лучи света? Если мы заранее рассчитаем каждый луч света, проходящий через октант и также найдём лучи света, который заблокированы, если в данной ячейке стена. Одновременно, мы можем сканировать через сетку октанта, перемещаясь от источника света, освещающего ячейки которых достигает по крайней мере один луч света. Любые ячейки, содержащие стены, сигнализируют, что луч, попавший на них заблокирован, этим самым оставляя другие в тени. Следующий рисунок (надеюсь), демонстрирует этот принцип.

        0       1       2       3       4

    +-------+-------+-------+-------+-------+
    |       |       |       |       |       |
    |       |       |       |       |       |
    |       |       |       |       |       |
  0 |   @11 |       |       |       |       |
    |    65322221111111     |       |       |
    |     65333 22222  11111111111  |       |
    |      6|54333  |22222  |     11111111  |
    +-------6-55--333#####22222-----+#####111
            |6  554 #333    #  22222#       #
            | 6   5444  333 #       22222   #
            |  6   55 444  333      #    2222
  1         |   6   #55  44 # 333   #       #
            |    6  #  5   44    333#       #
            |     6 #   55  #444    333     #
            |      6#     55#   444 #  333  #
            +-------6#######5------444####333
                    |6      |55     | 44    |
                    | 6     |  55   |   444 |
                    |  6    |    5  |      44
  2                 |   6   |     55|       |
                    |    6  |       55      |
                    |     6 |       | 5     |
                    |      6|       |  55   |
                    +-------6-------+----55-+

На рисунке показано предварительное вычисление 6 лучей света где каждая линия (кроме 1) пересекает ячейку (2, 1). Линии 2 и 6 'вычищают' границы ячейки, и линии 3, 4 и 5 проходят через середину ячейки. Поскольку в ячейке (2, 1) есть стена, линии 3, 4 и 5 должны быть помечены как 'заблокированные'. Это означает что никакой из лучей не способен осветить ячейки (3, 2) или (4, 2) оставляя их, таким образом, в тени.

Если мы заранее вычислим каждую линию до каждой угловой ячейки в октанте, исключая любые идентичные линии, и отсортируем их по списку, мы сделаем список всех уникальных линий отсортированных от горизонтали до диагонали октанта. Мы можем затем предварительно вычислить таблицу поиска для каждой ячейки в октанте и сохранить радиусы лучей, которые заблокированы стенами. Например, на вышеуказанном рисунке ячейка (2, 1) должна блокировать все лучи между 2 и 6. Ячейка (4, 1) должна блокировать все лучи от 1 до 4.

Мы можем сохранить списки лучей в битовом векторе, или булевом массиве. Если обнаружена ячейка со стеной, мы просто отмечаем, что биты между внешними границами данной ячейки как заблокированные. Аналогичную проверку можно использовать, чтобы определить, проходят ли через ячейку незаблокированные лучи. Просто проверьте каждый бит на векторе между двумя внешними углами, если обнаружится открытый бит, то ячейка видима.

Этот метод очень быстрый, поскольку ему требуется сканировать большинство ячеек только по одному разу. За исключением ячеек, лежащих вдоль горизонтали, вертикали и диагоналей, который расположены между двумя октантами. Эти ячейки должны сканироваться дважды, по одному разу в каждом прилежащем октанте.

Легко приспособить этот алгоритм, чтобы обеспечить круговое поле зрения по сравнению с квадратным полем зрения. Просто используйте теорему Пифагора, чтобы определять лежит ли данная координата (x, y) в пределах радиуса;

 (x * x) + (y * y) < (radius * radius)

Angband использует восьмиугольное поле зрения;

 max(x, y) + (min(x, y) / 2) <= radius

Мы можем также использовать этот алгоритм, чтобы определять, видна ли данная ячейка из другой. Есть два способа как это сделать. Найдите октант относительно ячейки-источника в котором расположена требуемая ячейка. Затем используйте метод 'блокировки луча' описаный выше. Когда мы достигнем требуемой ячейки и на неё не попадёт ни один из лучей, то она не видна. Второй метод заключается в том, чтобы найти требуемую ячейку и для каждого из лучей, пересекающих эту ячейку, проследить линию до ячейки-источника. Если один из прослеженных лучей достигает ячейки-источника без пересечения со стеной, то ячейка видна.

Результаты

Я осуществил этот алгоритм на Java и использовал радиус в 25 ячеек с круговым полем зрения. Он выполнялся особенно хорошо когда было только несколько ячеек стены, или если источник был перекрыт многими ячейками стены. Между этими предельными случаями алгоритм выполнялся не так хорошо. Тем не менее на моем P120, скорость проверки в наихудшем случае была 5 мс (200 в секунду).

Благодарности

Для более подробного описания этого метода, скачайте исходник Angband 2.8.3 и посмотрите файл 'cave.c'. Благодарности Mat Hostetter и Ben Harrison за разработку и реализацию алгоритма.

Если у вас есть любые вопросы по этой статье пишите мне на email.



Автор: Tobias Downer.
Источник: неизвестен.
Перевел: Дмитрий О. Бужинский, 21.02.2006.