Итак, мы нашли верхнюю и нижнюю ячейки в заданном фрагменте столбца, ограниченном верхним и нижнем векторами. Теперь перед нами стоят две задачи. Первая: все ячейки фрагмента, которые находятся в радиусе видимости, нужно пометить как видимые. Вторая: мы должны вычислить, какие фрагменты следующего столбца видимы через данный фрагмент, и поставить их в очередь для обработки.

Первая задача легко решается. Благодаря замечательным комментариям к моим прежним постам, я понял, что, конечно же, лучше рассмотреть вопрос: «находится ли нижний левый угол ячейки внутри радиуса видимости?» Это порождает круг, который выглядит гораздо лучше. Я ввел вспомогательный метод «IsInRadius», который выполняет это. ( Отметьте, что это порождает еще один вид артефактов; предположим, что изо всех четырех углов ячейки, только нижний правый угол находится ниже верхнего вектора, но лишь нижний левый лежит внутри радиуса видимости. В ячейке может не оказаться точек, которые лежали бы внутри радиуса и не были бы блокированы. Мы игнорируем эти детали; радиус, по своей природе, приближенное понятие.)

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

bool wasLastCellOpaque = null;
for (int y = topY; y >= bottomY; --y)
{
    bool inRadius = IsInRadius(x, y, radius);
    if (inRadius)
    {
        // Текущая ячейка находится в поле зрения.
        setFieldOfView(x, y);
    }

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

    bool currentIsOpaque = !inRadius || isOpaque(x, y);
    if (wasLastCellOpaque != null)
    {
        if (currentIsOpaque)
        {

Мы обнаружили переход от прозрачной ячейки к непрозрачной. Отложим работу на потом.

            if (!wasLastCellOpaque.Value)
            {

Новый нижний вектор касается верхнего левого угла непрозрачной ячейки, ниже которой находится прозрачная.

                 queue.Enqueue(new ColumnPortion(
                     x + 1,
                     new DirectionVector(x * 2 - 1, y * 2 + 1),
                     topVector));
            }
        }
        else if (wasLastCellOpaque.Value)
        {

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

Как правило, я не корректирую формальный параметр вроде этого, но в данном контексте это выглядит довольно безопасно.

            topVector = new DirectionVector(x * 2 + 1, y * 2 + 1);
        }
    }
    wasLastCellOpaque = currentIsOpaque;
}

И наконец, мы ставим задачу в очередь для самого нижнего перехода от непрозрачной к прозрачной ячейки, если она есть.

if (wasLastCellOpaque != null && !wasLastCellOpaque.Value)
    queue.Enqueue(new ColumnPortion(x + 1, bottomVector, topVector));

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

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