Мне всегда нравились игры вроде "rogue" ("бродяга"); возможно вы тоже играли в некоторые из них. В этих играх вы смотрите сверху вниз на мозаичный мир и у вас сколько угодно времени на принятие решения. Классический пример - войти в подземелье, добраться до низа, заполучить амулет Йендора (Amulet of Yendor), а затем выбраться с ним наружу. Как можно ожидать, первоначальная игра с такими свойствами называлась "Rogue" ("Бродяга") и породила множество гораздо более сложных подражаний. Особенно понравилась версия Nethack , которую мне удалось завершить лишь дважды из многих и многих сотен попыток. Крепкая игрушка Nethack.
В исходной Rogue был очень упрощенный подход к освещению подземелья: когда вы заходили в освещенную комнату, вы видели всё в ней, независимо от находящихся там препятствий. Более современные варианты "Rogue" использовали гораздо более сложные алгоритмы для расчета освещения, принимающие во внимание препятствия, интенсивность света и т. д. Мне были любопытны различные приемы для моделирования реалистичного освещения в таких играх и я быстро обнаружил коллекцию статей на сайте RogueBasin под рубрикой "Поле зрения" (Field of View).
Хотя я высоко ценю усилия, затраченные на их написание и разработки программ - особенно статьи Гордона Липфорда (Gordon Lipford), Бьёрна Бергстрёма (Björn Bergström) и Генри Хакла (Henri Hakl) - должен сказать, что мне показалось, что некоторые из них сложны для восприятия. Есть много тонкостей в этих алгоритмах, а некоторые из статей используют общие важные геометрические термины (вроде "наклона", "линии" и "угла") необычным или противоречивым способом. Когда я взглянул на различные реализации разных алгоритмов, опубликованных - опять же, очень любезно - авторами, то обнаружил много хороших вещей, но также и некоторые спорные программистские приемы и необъясненные случаи выбора в тонких ситуациях.
Я подумал, что смог бы описать один из алгоритмов чрезвычайно подробно , как для самообразования, так и для общей пользы, а также реализовать его и рассказать о различных рассмотренных факторах при выборе способа реализации.
Прежде всего, до погружения в детали, вот небольшое приложение на Silverlight, показывающее, что я имею в виду. Щелкните мышью на окошке, расположенном ниже, и затем используйте клавиши стрелок для своего (знак "@") движения повсюду. Заметьте, что вы можете видеть лишь девять-десять квадратов в любом направлении, и что препятствия отбрасывают тени. Особенно отметьте поведение теней в области, содержащей множество тесно расположенных "колонн". Тени ведут себя реалистично? Пока обдумываете этот вопрос, попробуйте найти сокровище и возвратиться с ним!
Моя первая опубликованная игра класса "Rogue" оказалась, очевидно, довольно простой.
Распространение лучей
Алгоритм, который приходит в голову большинству людей, сталкивающимся с проблемой создания реалистического освещения, называется распространением лучей ("ray casting"). Вообразите окружность вокруг игрока, ограниченную мощностью источника света. Для каждой ячейки на окружности представьте себе луч света, исходящий из игрока по направлению к центру рассматриваемой ячейки. Зафиксируем первый объект, если таковой имеется, который луч встретит на своем пути. Все ячейки, через которые луч проходит до первого препятствия, являются "видимыми"; распространение луча прерывается первым препятствием.
Этот алгоритм работает, но имеет ряд недостатков. Главный из них заключается в том, что если окружность велика, то число лучей, которые необходимо обсчитать, большое. Множество лучей означает, что область, близкая к игроку "посещается" снова и снова, что, вроде бы, не полезно для производительности. Было бы прекрасно, если бы каждая ячейка обрабатывалась лишь один раз, или хотя бы, только небольшое количество раз.
Построение теней
Алгоритм, который я в действительности реализовал, называется "построение теней". Его основная идея состоит в том, что вместо отслеживания каждого индивидуального луча света, мы предположим, что все точки внутри окружности освещены, а затем вычислим, какие ячейки находятся в тени. Я собираюсь начать с геометрического описания алгоритма, а потом мы увидим, в чем реализация кода соответствует или отличается от геометрического описания.
Давайте аккуратно определим здесь некоторые термины. Наш мир состоит из двухмерной эвклидовой плоскости точек. Точки представляются парами действительных чисел в форме (x, y). Мы используем стандартное геометрическое соглашение о том, что x увеличивается по мере продвижения к "востоку", а y увеличивается, когда мы движемся на "север"(*). Точка (0,0) называется "началом".
Мир содержит объекты, населяющие эту плоскость. Каждый объект центрирован на "точку решетки" (x,y), где x и y целые числа, и полностью заполняет квадрат ограниченный точкой (x-0.5, y-0.5) левого нижнего угла и точкой (x+0.5, y+0.5) верхнего правого. Эта область называется "ячейкой", связанной с точкой решетки.
Проблема "области видимости" (field of vision - FoV) заключается в определении того, какие ячейки находятся на "линии взгляда" из заданной точки (или, в некоторых алгоритмах, из любой точки данной ячейки) при заданном наборе объектов, которые могут заслонять обзор, и заданном максимальном расстоянии.
Без потери общности мы собираемся решить проблему FoV, предполагая, что "заданная точка", о которой идет речь, это начало. Как мы позже увидим, можно выполнить простое преобразование координат, чтобы решить задачу для других точек.
Векторы направлений
Основным инструментом, который мы собираемся использовать для решения этой задачи, является "вектор направления". "Вектор" подобен отрезку прямой линии, исходящей из начала. Вектор имеет направление и длину, но для наших целей мы сосредоточимся лишь на направлении. Направление вектора (ненулевой длины) можно определить несколькими способами:
- Укажите точку, отличную от начала, через которую пройдет вектор при продлении прямой линии из начала; это определяет направление вектора.
- Укажите точку, как и в первом случае; поделите координату y этой точки на координату x, чтобы получить "наклон" (**)
- Проведите из начала единичную окружность. Продлите, если нужно, вектор до пересечения с окружностью. Теперь, двигаясь против часовой стрелки, измерьте расстояние от точки пересечения окружности осью x до точки пересечения окружности вектором. Длина дуги представляет собой угол вектора, измеренный в радианах. Умножьте его на 180/π, чтобы получить угол в градусах.
Можно использовать любой из этих методов. Недостатком методов "наклона" и "угла" является то, что в приложении, наклоны и углы зачастую будут дробями, которые невозможно точно представить с помощью плавающей арифметики; было бы прекрасно иметь возможность выполнять все действия точно. (Другой недостаток заключается в том, что наклоны увеличиваются до бесконечности, когда угол вектора приближается к 90°, хотя, как мы увидим, мы никогда не будем работать с векторами, чьи наклоны больше одного или меньше нуля.) В нашем приложении, как оказывается, все векторы, с которыми нам придется иметь дело, будут проходить через точки решетки. Поэтому мы будем использовать механизм "задания точки" для описания вектора направления.
Здесь у нас картинка, иллюстрирующая ситуацию. Пустой квадрат с серой границей представляет ячейку, центрированную на начало. Заполненный серый квадрат представляет объект, находящийся в ячейке (2, 1). Красная линия обозначает вектор направления, исходящий из начала и проходящий через точку (5, 1).
Главная идея алгоритма
Главную идею алгоритма можно сформулировать следующим образом:
Мы уже отмечали, что без потери общности, будем решать задачу FoV, предполагая, что заданная ячейка располагается в начале. Более того, мы собираемся решить задачу только в нулевом октанте плоскости. Если представить себе векторы направлений на углах 0°, 45°, 90°, 135°, 180°, 225°, 270° и 315°, то видно, что эти восемь векторов делят плоскость на восемь "октантов" (***):
Если мы решим задачу для октанта ноль, то сможем решить ее и для каждого другого октанта с помощью простого отражения нужного октанта на нулевой.
Итак, как нам решить задачу в нулевом октанте? Мы разделим ячейки, чьи центры попадают внутрь или на край этого октанта, на столбцы (****). Здесь мы видим столбцы с нулевого по шестой; три из них заняты ячейками препятствий. Вопрос состоит в том, какие ячейки на расстоянии шести единиц от начала наблюдатель, находящийся в начале, сможет увидеть?
Мы собираемся переходить от столбца к столбцу слева направо. Внутри каждого столбца будем перебирать ячейки сверху вниз. Начнем с пары векторов. Эта пара векторов представляет область мира, которая не находится в тени.
Начинаем путь с векторов (1,0) и (1,1) так как вся нулевая колонка видима. Помним, что нас интересует в векторах лишь направление, а не длина, так что я неограниченно продолжу векторы вдоль их направлений. При обработке нулевой колонки имеем следующую ситуацию:
"Верхний" вектор голубой, а "нижний" - зеленый. О ячейках, попадающих между этих двух векторов, до сих пор можно было предположить, что они находятся в поле зрения начала для этого октанта. Отметим, что ячейка (0,0) видна из нулевого столбца.
Затем начнем сканировать первый столбец сверху вниз. Мы не найдем ничего, что могло бы закрыть взгляд, поэтому состояние векторов не изменяется после сканирования первого столбца, и каждая ячейка в нем видима из начала. То же самое произойдет и со вторым столбцом. Однако когда мы перейдем к столбцу три, мы немедленно наткнемся на его вершине на непрозрачную ячейку, но ниже нее расположены прозрачные ячейки. Поэтому опустим верхний вектор, так как ячейка (3,3) возможно заслоняет что-то в следующем столбце.
Больше мы в третьем столбце ничего непрозрачного не нашли, поэтому после его обработки состояние алгоритма выглядит следующим образом (известные видимые ячейки помечены солнышком):
Все ячейки в третьем столбце видимые, включая непрозрачную. Но теперь верхний вектор опущен. Когда мы начинаем сканировать четвертый столбец, то начинаем сверху, но верхняя ячейка четвертого столбца теперь находится вне области, ограниченной векторами. Она невидима. Мы начинаем сканирование четвертого столбца с ячейки (4,3) и движемся вниз. Мы обнаружим непрозрачную ячейку внизу столбца, и на этот раз поднимем нижний вектор. После завершения обработки четвертого столбца состояние алгоритма следующее:
Отметим интересную вещь: угол видимости становится меньше и меньше, несмотря на то, что столбцы становятся выше, и реальное число ячеек, которые мы сканируем по столбцам, не растет. Это означает, что вероятно, алгоритм имеет лучшую производительность, когда имеется больше препятствий! Это прекрасное свойство.
И вот мы подходим к первой, действительно интересной части алгоритма. Является ли ячейка (5,4) видимой? С точки зрения строгой физической перспективы ясно, что никакая часть ячейки (5,4) не видна для наблюдателя, расположенного точно в начале. Любые возможные векторы по линиям взгляда из начала либо проходят через непрозрачную ячейку (3,3), либо через непрозрачную ячейку (5,3). Однако мы сканируем каждый столбец сверху вниз; мы еще не обработали ячейку (5,3). Другой интересный вопрос состоит в следующем: предположим ячейка (5,3) оказалась прозрачной; тогда была бы видна ячейка (5,4)? Ее нижний правый угол виден из начала, а центр нет. Что это означает? К счастью нам не надо давать ответа на этот вопрос, потому что ячейка (5,4) находится вне пределов видимости; мы можем видеть лишь на шесть единиц, а (5,4) находится от начала немного дальше. Однако, в общем случае, нам придется рассмотреть этот вопрос более аккуратно.
Аналогично мы должны решить, видима ли ячейка (5,0). Из физического рассмотрения ясно, что нет; она полностью блокируется ячейкой (4,0). Однако возможно, что по причинам реализации или сюжету игры нам придется слегка сжульничать и позволить точке (5,0) быть видимой. Мы вернемся к этим вопросам и детально рассмотрим их, когда погрузимся в точную реализацию. А теперь, ради представления идеи алгоритма давайте предположим, что случилось чудо, и мы решили, что ячейка (5,3) будет верхней видимой ячейкой пятого столбца, а (5,1) - самой нижней. Так же как и при обработке третьего столбца, мы обнаружим видимые непрозрачные ячейки над видимой прозрачной, опустим верхний вектор:
И теперь больше не осталось видимых ячеек, находящихся ближе шести единиц от начала; мы закончили. Поле зрения определено.
Давайте кратко рассмотрим другой сценарий. Предположим, что мы уже обработали часть столбцов:
Все ячейки в четвертом столбце видимые. Но каковы векторы для вычисления видимости ячеек в столбцах пять и шесть? Теперь нам потребуется два набора векторов!
При вычислении FoV для столбцов пять и шесть мы рассмотрим обе пары векторов, как возможно содержащие видимые области. Естественно, при больших столбцах со многими зазорами в них мы можем сгенерировать и больше пар векторов.
Такова основная идея алгоритма; в следующий раз мы постараемся реализовать ее на C# и увидим, с какими трудностями мы столкнемся.
(*) Тот факт, что многие компьютерные системы отображения не следуют этому соглашению, является одной из тех вещей, которые делают ненужно сложными рассуждения о коде, реализующем системы освещения. В некоторых реализациях предполагается, что в заданном прямоугольника с углами (0,0) и (1,1) начало располагается в верхнем левом углу, а не в нижнем левом, как принято в геометрии. Мне кажется, что лучше всего следовать геометрическим соглашениям и выполнять преобразования к координатной системе экрана в коде, специально предназначенном для этого.
(**) Некоторые реализации этого алгоритма, которые можно найти в Интернете определяют "наклон", как "прохождение" со знаком минус, деленное на "подъем" со знаком минус. Более удобно определить наклон, как "подъем", деленный на "прохождение", как сделал я.
(***)Некоторые реализации этого алгоритма, которые можно найти в Интернете определяют нулевой октант, как я определил второй. Я считаю, что более последовательно нумеровать октанты против часовой стрелки, начиная от оси х, так как углы обычно измеряются против часовой стрелки от оси х.
(****) В некоторых реализациях эта коллекция ячеек называется "линией", что немного сбивает с толку, это не геометрические линии, а столбцы ячеек.