Построение теней на C#. Часть 2
Я надеюсь, что основная идея алгоритма построения теней теперь ясна. Давайте приступим к его реализации. Есть две главные проблемы. Более простая – «на что должен быть похож интерфейс для вычислений?» Вторая – «как его реализовать?» Давайте начнем с более простой: спроектируем API.
Что должна предоставить вызывающая программа?
- Координаты центральной точки
- Радиус поля зрения
- Информацию о непрозрачных ячейках
Что должна сделать реализация для вызывающей программы?
- Обеспечить способ сообщить вызывающей программе, какие ячейки видимы из центральной точки.
Последнее потребует некоторых ухищрений. Реализация может вернуть список точек, которые видны. Или может создать двухмерный массив булевых значений и установить их в true, если ячейка видна и в false в противном случае. Или может видоизменить коллекцию, предоставляемую вызывающей стороной. И так далее. Мы не знаем, как работает вызывающая программа или что она собирается делать с этой информацией. Мы даже не знаем, хранится эта информация в виде булевых величин или битовых флагов или списка точек. Сложно узнать, в чем состоит правильное решение, так что мы оставим это. Предоставим это решать вызывающей программе, передающей нам функцию Action, которая всё и сделает за нас!
public static class ShadowCaster
{
// Получить окружность в виде центральной точки и радиуса и функцию,
// которая говорит, видна ли заданная точка. Вызвать функцию setFoV для
// каждой точки, находящейся внутри окружности и видимой из центра.
public static void ComputeFieldOfViewWithShadowCasting(
int x, int y, int radius,
Func<int, int, bool> isOpaque,
Action<int, int> setFoV)
{
// Здесь происходят чудеса
}
Хорошо, это точка входа для вызывающей программы. Как насчет реализации?
Мне бы хотелось, чтобы реализация имела следующие свойства:
Первое и главное, реализация должна быть ясной и корректной. Она должна быть достаточно производительной для небольших демонстраций, но не выжимать последние капли из производительности процессора. Если код ясный и корректный, но недостаточно быстрый, анализ окончательной производительности поможет найти проблемы позже. Для целей отладки мне бы хотелось, чтобы операции кода более или менее следовали описанию алгоритма, который я набросал. Кроме того, код должен удовлетворять условию DRY (Don't Repeat Yourself – не повторять себя). (*)
Мне бы хотелось, чтобы реализация не слишком заботились о раздражающих бухгалтерских подробностях. Мы строили алгоритм в предположении, что наблюдатель находится в начале и поле зрения формируется лишь для нулевого октанта; наша реализация должна делать то же самое, а не пытаться сохранить детали, вроде того, где на самом деле находится наблюдатель.
Этот алгоритм часто применяется рекурсивно, но я хотел бы избежать этого по двум причинам. Во-первых, потому что типичная рекурсивная реализация будет вызывать рекурсии, по крайней мере, один раз в столбце; можно вообразить сценарий, в котором длинный узкий туннель в сотни ячеек длиной вызовет переполнение стека. Во-вторых, потому что типичная рекурсивная реализация рассматривает октант, начиная с больших столбцов. Это означает, что когда необходимо поделить видимую область на мелкие части, каждая из которых имеет свой собственный верхний и нижний вектор направления, рекурсивный метод рассматривает каждую часть, начиная с последнего столбца; более приоритетно рассматривать каждую часть целиком до перехода к следующей. Но мы описали этот алгоритм как движущийся слева направо и сверху вниз, что подразумевает полное рассмотрение каждой колонки до перехода к следующей. И как я сказал прежде, для доходчивости и возможности отладки было бы прекрасно, если бы реализация соответствовала описанию.
Основная идея моей реализации развивается следующим образом:
- Для каждого столбца взять в качестве входного значения набор ячеек в столбце, про которые известно, что они либо точно находятся в поле зрения, либо с некоторой вероятностью, обусловленной только выходом за радиус видимости.
- Исходя из этого набора, вычислить какие ячейки в следующем столбце либо точно находятся в поле зрения, либо с некоторой вероятностью, обусловленной только выходом за радиус видимости.
- Повторять до тех пор, пока столбец не окажется целиком за пределами радиуса видимости; остановиться здесь.
Это хороший обзор верхнего уровня, теперь сделаем это немного более четко:
- Разбить каждый столбец (отождествляемый х-координатой, которая определяет середину столбца) на одну или несколько непрерывных «фрагментов», каждый из которых ограничен верхним и нижним вектором направлений.
- Для каждого фрагмента текущего столбца, определить набор видимых фрагментов в последующем столбце.
- Добавить каждый из этих последующих фрагментов в очередь на обработку.
- Обрабатывать фрагменты из очереди пока она не закончиться.
Этого описания достаточно для написания реального кода, реализующего данную абстракцию. Мы можем сделать это с помощью двух небольших неизменяемых структур.
Вспомним, что мы решили представлять вектор направления как точку на линии вектора, и что мы не будем беспокоиться о его длине, а только о направлении. Как мы увидим, нам понадобятся лишь векторы направлений, попадающие в точки решетки, поэтому в качестве координат мы можем использовать целые числа.
private struct DirectionVector
{
public int X { get; private set; }
public int Y { get; private set; }
public DirectionVector(int x, int y)
: this()
{
this.X = x;
this.Y = y;
}
}
Фрагмент столбца, с которым мы будем иметь дело, характеризуется тремя параметрами: x-координатой середины столбца, вектором направления, обозначающим верх фрагмента и вектором направления, обозначающим низ фрагмента
private struct ColumnPortion
{
public int X { get; private set; }
public DirectionVector BottomVector { get; private set; }
public DirectionVector TopVector { get; private set; }
public ColumnPortion(int x, DirectionVector bottom, DirectionVector top)
: this()
{
this.X = x;
this.BottomVector = bottom;
this.TopVector = top;
}
}
Теперь, когда у нас есть структуры данных, мы можем заняться главным циклом всего механизма. Напомним, что теперь мы предполагаем, что центральная точка находится в начале и что нас интересует только нулевой октант. Каким-то образом точка входа должна будет вычислить, что делать с этим требованием, но эту задачу мы решим позже.
private static void ComputeFieldOfViewInOctantZero(
Func<int, int, bool> isOpaque,
Action<int, int> setFieldOfView,
int radius)
{
var queue = new Queue<ColumnPortion>();
queue.Enqueue(new ColumnPortion(0, new DirectionVector(1, 0), new DirectionVector(1, 1)));
while (queue.Count != 0)
{
var current = queue.Dequeue();
if (current.X >= radius)
continue;
ComputeFoVForColumnPortion(
current.X,
current.TopVector,
current.BottomVector,
isOpaque,
setFieldOfView,
radius,
queue);
}
}
Действия главного цикла прямолинейны. Мы создаем рабочую очередь. Мы знаем, что весь нулевой столбец виден, и что его верхний и нижний векторы – линии, выходящие из начала и охватывающие весь октант. Мы помещаем их в рабочую очередь. Затем мы переходим к циклу, занимающемуся очередью, и обрабатывающему каждый фрагмент столбца. Делая так, мы можем получить произвольно больше работы в следующем столбце. Поскольку рабочая очередь – это все-таки очередь, мы гарантируем, что завершим один столбец прежде, чем начнем работать со следующим; это делает действия алгоритма похожими на его описание.
Внимательный читатель заметит, что мы уже сделали очень интересный выбор, который фактически не дает правильно реализовать сформулированный алгоритм. Если фрагмент столбца в очереди находится вне радиуса видимости, тогда мы отказываемся от него без обработки. Это гарантирует, что алгоритм завершится, и дает уверенность в том, что нам не придется обрабатывать колонку, которая целиком выходит за радиус видимости. Само по себе это хорошо, интересный выбор заключается в том, что сравнение выглядит так:
if (current.X >= radius)
а не так
if (current.X > radius)
Если мы задаем поле видимости радиуса шесть, мы не должны реально делать видимыми никакие ячейки из столбца шесть, даже если одна из них точно будет видима – а именно, ячейка (6,0). Любая другая ячейка этого столбца находится на расстоянии, превышающем шесть единиц от начала. Почему мы сделали такой выбор?
Эстетика. Предположим, что препятствия отсутствуют, и мы вычисляем поле видимости радиуса шесть для всех восьми октантов. Результат выглядит так:
O
OOOOOOO
OOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOO@OOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOO
OOOOOOO
O
Что выглядит странно. Кривизна круга по определению должна быть везде одинакова; а это делает круг заостренным в четырех местах. Граница круга должна быть выпуклой повсюду; если представить себе линию, соединяющую центры букв О вдоль границы, то она представит собой выпуклую кривую за исключением восьми точек, где кривая внезапно становится вогнутой. Это ужасно; чтобы устранить это мы округлили восьмиугольник, опустив крайний столбец:
OOOOOOO
OOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOO
OOOOOOO
Это намного лучше. И «ошибка» невелика, с одной стороны, только четыре точки удаляются, а с другой – эти четыре точки являются наиболее удаленными от центра; если уж намереваешься удалять точки, то эти – наиболее разумные кандидаты на удаление.
Сегодня мы увидели, что решение о небольшом округлении может иметь значительное влияние на эстетику алгоритма; в следующий раз мы займемся первой строкой метода ComputeFoVForColumnPortion и обнаружим, что тонкие решения об управлении ошибками округления могут привести в большим различиям в определении того, как ввод будет выглядеть для игрока.
(*) Множество реализаций этого алгоритма в Интернете без необходимости повторяют этот код восемь раз, по разу для каждого октанта.