Построение теней на C#. Часть 2

Article
02/16/2012

Я надеюсь, что основная идея алгоритма построения теней теперь ясна. Давайте приступим к его реализации. Есть две главные проблемы. Более простая – «на что должен быть похож интерфейс для вычислений?» Вторая – «как его реализовать?» Давайте начнем с более простой: спроектируем 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). Любая другая ячейка этого столбца находится на расстоянии, превышающем шесть единиц от начала. Почему мы сделали такой выбор?

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

OOOOOOO

OOOOOOOOO

OOOOOOOOOOO

OOOOOO@OOOOOO

OOOOOOOOOOO

OOOOOOOOO

OOOOOOO

Что выглядит странно. Кривизна круга по определению должна быть везде одинакова; а это делает круг заостренным в четырех местах. Граница круга должна быть выпуклой повсюду; если представить себе линию, соединяющую центры букв О вдоль границы, то она представит собой выпуклую кривую за исключением восьми точек, где кривая внезапно становится вогнутой. Это ужасно; чтобы устранить это мы округлили восьмиугольник, опустив крайний столбец:

OOOOOOO

OOOOOOOOO

OOOOOOOOOOO

OOOOO@OOOOO

OOOOOOOOOOO

OOOOOOOOO

OOOOOOO

Это намного лучше. И «ошибка» невелика, с одной стороны, только четыре точки удаляются, а с другой – эти четыре точки являются наиболее удаленными от центра; если уж намереваешься удалять точки, то эти – наиболее разумные кандидаты на удаление.

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

(*) Множество реализаций этого алгоритма в Интернете без необходимости повторяют этот код восемь раз, по разу для каждого октанта.

Оригинал статьи

Построение теней на C#. Часть 2

Additional resources