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

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

Мы можем решить задачу «наблюдатель в любой точке» проводя преобразование координат в функции «непрозрачная?» и действия «ячейка видима». Предположим, алгоритм хочет знать, является ли ячейка (3, 1) непрозрачной. И предположим, что наблюдатель находится не в начале, а в точке (5,6). Алгоритм в действительности запрашивает, является ли непрозрачной ячейка (3 + 5, 6 + 1). Аналогично, если эта ячейка оказывается видимой, то преобразованная ячейка видима из (5, 6). Можно легко преобразовать один делегат в другой:

private static Func<int, int, T> TranslateOrigin<T>(Func<int, int, T> f, int x, int y)
{
return (a, b) => f(a + x, b + y);
}

private static Action<int, int> TranslateOrigin(Action<int, int> f, int x, int y)
{
return (a, b) => f(a + x, b + y);
}

Аналогично можно провести преобразование октанта; если вы хотите отобразить точку в октанте один в точку октанта ноль, просто поменяйте координаты (x,y)! Каждый октант имеет простое преобразование координат, отображающее его на октант ноль:

private static Func<int, int, T> TranslateOctant<T>(Func<int, int, T> f, int octant)
{
switch (octant)
{
default: return f;
case 1: return (x, y) => f(y, x);
case 2: return (x, y) => f(-y, x);
case 3: return (x, y) => f(-x, y);
case 4: return (x, y) => f(-x, -y);
case 5: return (x, y) => f(-y, -x);
case 6: return (x, y) => f(y, -x);
case 7: return (x, y) => f(x, -y);
}
}

(И так же для действий.)

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

public static void ComputeFieldOfViewWithShadowCasting(
int x, int y, int radius,
Func<int, int, bool> isOpaque,
Action<int, int> setFoV)
{
Func<int, int, bool> opaque = TranslateOrigin(isOpaque, x, y);
Action<int, int> fov = TranslateOrigin(setFoV, x, y);

    for (int octant = 0; octant < 8; ++octant)
{
ComputeFieldOfViewInOctantZero(
TranslateOctant(opaque, octant),
TranslateOctant(fov, octant),
radius);
}
}

Очень просто, да?

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

Если вам потребуется полный рабочий пример, я опубликовал проект, который собирает элемент Silverlight из первой части статьи здесь.

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