Как 3-строчный алгоритм обеспечивает достойную альтернативу raycast

В моей предыдущей статье Короткая и прямая прогулка с треугольником Паскаля я объясняю, как можно улучшить поиск пути на основе сетки, чтобы получить очень прямые пешеходные пути без использования тестов прямой видимости. В этой последующей статье будет показан родственный метод, называемый видимость на основе сетки, который вычисляет видимые области без проверки прямой видимости. Видимость на основе сетки практически неизвестна в компьютерном сообществе, но это практичный метод, который имеет смысл для различных приложений искусственного интеллекта. Его также чрезвычайно легко реализовать, для этого требуется всего 3 строки кода. Читайте дальше, чтобы найти самый простой вариант решения проблем с видимостью в видеоиграх, мобильной робототехнике или архитектурном дизайне.

Проблема видимой области

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

Основная проблема заключается в следующем: по двумерной карте сверху вниз вычислить область пространства, видимую из точки.

Если вы спросите ученого-компьютерщика, как решить эту проблему, крайне маловероятно, что он даже рассмотрит то, что я называю алгоритмом на основе сетки: метод, при котором числа в каждой ячейке сетки вычисляются на основе чисел. в соседних ячейках сетки. Проблема видимой области почти всегда решается с помощью алгоритма векторной видимости, включающего тесты прямой видимости. Одним из самых популярных векторных методов визуализации является распределение лучей, при котором многочисленные лучи отбрасываются в разных направлениях с точки обзора. Если вы не знакомы с raycasting и другими векторными решениями проблемы видимой области, учебник Red Blob Games по 2D Visibility представляет собой отличный справочный материал.

Подходы на основе сетки и вектора популярны для других пространственных приложений, таких как поиск пути и 2D-графика. Мы все знакомы, например, с растровыми (на основе сетки) и векторными изображениями, и мы понимаем, что оба типа изображений имеют свои преимущества и недостатки. Так почему же для наглядности широко используются только векторные подходы? Я пришел к выводу, что, хотя методы, основанные на сетке, и методы, основанные на векторах, имеют свои преимущества и недостатки для решения проблем видимости, видимость на основе сетки странным образом упускается из виду и заслуживает того, чтобы о ней знали лучше.

Видимость на основе сетки

Вот видимость на основе сетки, написанная тремя строками кода Python.

for x in range(grid.shape[0]):
    for y in range(int(x==0), grid.shape[1]):
        grid[x,y] *= (x*grid[x-1,y] + y*grid[x,y-1]) / (x + y)

Алгоритм берет сетку, представляющую карту, и модифицирует ее для получения результатов видимости. Как мы видим, преобразование состоит из перебора каждой ячейки сетки и применения линейной интерполяции. Давайте протестируем эти 3 строки кода, поместив их в короткую программу. Не стесняйтесь копировать и запускать скрипт Python ниже.

import numpy as np
import matplotlib.pyplot as plt

# Set dimensions
nx = 25
ny = 25

# Create map
grid = np.ones((nx,ny))
wx = nx//10 + 1
wy = ny//10 + 1
grid[int(.3*nx):int(.3*nx)+wx,int(.1*ny):int(.1*ny)+wy] = 0
grid[int(.1*nx):int(.1*nx)+wx,int(.5*ny):int(.5*ny)+wy] = 0
grid[int(.6*nx):int(.6*nx)+wx,int(.6*ny):int(.6*ny)+wy] = 0

# Display map
plt.figure("Map")
plt.imshow(np.transpose(grid))

# Compute visibility
for x in range(grid.shape[0]):
    for y in range(int(x==0), grid.shape[1]):
        grid[x,y] *= (x*grid[x-1,y] + y*grid[x,y-1]) / (x + y)

# Display visibility
plt.figure("Visibility")
plt.imshow(np.transpose(grid))
plt.show()

Сначала программа создает и отображает карту, сетку 25x25, где ячейки, заполненные препятствием, имеют значение 0, а пустые ячейки имеют значение 1. Как показано ниже, карта имеет три квадратных препятствия.

Затем программа преобразует карту в сетку видимости и отображает ее. Сетка видимости заполнена показателями видимости, которые приблизительно отражают степень видимости каждой ячейки сетки с точки обзора в верхнем левом углу. Оценки видимости варьируются от 0 (полностью заблокировано) до 1 (полностью видно). Вот сетка видимости.

Каждое препятствие отбрасывает тень от верхнего левого угла, хотя вы заметите, что края теней размыты. Один из способов сделать эти края более четкими — увеличить разрешение карты. Если мы изменим размер сетки с 25 до 225 ячеек в обоих измерениях…

nx = 225
ny = 225

… получаем следующие результаты.

Здесь мы видим более четкие и точные тени. Если мы продолжим увеличивать разрешение, показатели видимости будут становиться все более и более точными. На самом деле, результаты будут сходиться к точному решению, когда шаг сетки будет приближаться к нулю.

В зависимости от приложения мы можем захотеть классифицировать каждую ячейку сетки как видимую (1) или невидимую (0). Мы можем сделать это, применив порог 0,5 после цикла.

for x in range(grid.shape[0]):
    for y in range(int(x==0), grid.shape[1]):
        grid[x,y] *= (x*grid[x-1,y] + y*grid[x,y-1]) / (x + y)
grid[:] = (grid >= 0.5)

Вставка этой 4-й строки в скрипт дает нам результат ниже.

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

Прежде чем мы двинемся дальше, я должен признаться, что использовал несколько приемов, чтобы сократить алгоритм до 3 строк:

  1. Выражение int(x==0) во 2-м цикле for — хитрый трюк, который пропускает ячейку сетки [0, 0], где формула интерполяции может привести к ошибке деления на ноль.
  2. Я полагаюсь на тот факт, что библиотека NumPy позволяет обращаться к массивам с использованием отрицательных индексов. Другие языки программирования могут потребовать еще несколько строк кода для проверки этого условия.
  3. Весь приведенный выше код предполагает, что точка обзора находится в углу карты. Перемещение точки обзора в произвольную ячейку с координатами x0 и y0 требует повторения расчета четыре раза, по одному разу в каждом из четырех квадрантов.

Чтобы разместить точку обзора в центре карты, замените код в разделе Compute visibility скрипта следующим.

# Set viewpoint
x0 = nx//2
y0 = ny//2

# Define visibility function
def visibility_from_corner(grid):
    for x in range(grid.shape[0]):
        for y in range(int(x==0), grid.shape[1]):
            grid[x,y] *= (x*grid[x-1,y] + y*grid[x,y-1]) / (x + y)

# Compute visibility
visibility_from_corner(grid[x0:,y0:])
visibility_from_corner(grid[x0::-1,y0:])
visibility_from_corner(grid[x0::-1,y0::-1])
visibility_from_corner(grid[x0:,y0::-1])

Вот результаты с точкой обзора в центре.

Аккуратный трюк с Excel

Вот небольшой трюк, который я не могу не показать: видимость на основе сетки, реализованная в Excel. Следующая запись экрана длится примерно 1 минуту.

Хотите попробовать сами? Следуйте приведенным ниже инструкциям. Это должно занять всего 1 или 2 минуты.

  1. Откройте MS Excel и создайте пустую книгу.
  2. Выберите ячейку B2, щелкните Панель формул (или нажмите F2), вставьте следующий текст и нажмите Enter:
    =((COLUMN(B2)-2)*A2+(ROW(B2)-2)*B1)/((COLUMN(B2)-2)+(ROW(B2)-2))
  3. Повторно выберите ячейку B2, нажмите Ctrl-C, чтобы скопировать, выберите диапазон ячеек от B2 до Z26, нажмите Ctrl-V, чтобы вставить.
  4. На вкладке Главная выберите Условное форматирование, Правила выделения ячеек, Меньше. Введите 0.5 в первое поле («Форматировать ячейки МЕНЬШЕ»), затем выберите любой вариант «Заливка» в раскрывающемся меню справа (например, «Светло-красная заливка с темно-красным текстом»). Нажмите ОК.
  5. Выберите ячейку B2 и нажмите 1, затем Enter.
  6. Выберите все ячейки, щелкнув зеленый треугольник выше и слева от ячейки A1, затем щелкните и перетащите вертикальную линию между A и B, чтобы уменьшите ширину ячейки так, чтобы все ячейки были примерно квадратными.
  7. Создавайте препятствия, нажимая на ячейки и нажимая Backspace. Тени, отходящие от верхнего левого угла, должны появиться автоматически.

Обратите внимание, что препятствия должны иметь ширину в несколько ячеек, чтобы создавать разумно выглядящие тени.

Краткая история видимости на основе сетки

История видимости на основе сетки объясняет, почему этот метод так и не получил широкого признания. Прежде всего, несмотря на свою простоту, видимость на основе сетки не была изобретена до 2004 года [2], а ее свойства сходимости не были установлены до 2008 года [3]. К тому времени векторные подходы, такие как raycasting, стали повсеместными. Ученые-компьютерщики больше не искали конкурирующие подходы. Во-вторых, первые статьи о видимости на основе сетки пришли из области математики, называемой теорией множеств уровней, где геометрия представлена ​​в неявном виде, незнакомом большинству ученых-компьютерщиков. В то время как метод видимости набора уровней работает в 2D или 3D и использует линейную интерполяцию, строго трехмерная альтернатива с использованием билинейной интерполяции была разработана исследователями архитектурной и городской информатики в 2013 году [4].

Примерно в 2019 году мы с коллегами заинтересовались видимостью на основе сетки как средством анализа большого количества компьютерных проектов зданий. В нашей журнальной статье с открытым доступом «Подсчет путей для навигации на основе сетки» [1] мы сделали следующие наблюдения:

  1. Исходный метод видимости набора уровней легко адаптируется для работы с явной геометрией, знакомой специалистам по информатике. Код Python в начале этой статьи является примером реализации, сочетающей исходную формулу интерполяции с явной сеткой. геометрия на основе.
  2. Размер окрестности сетки можно увеличить для получения более точных результатов. В примерах в этой статье до сих пор использовалось 4-окрестность, где информация течет на север, юг, восток и/или запад. Мои коллеги и я использовали 8-окрестность, которая позволяет информации течь по диагонали, как в документе, так и в инструменте архитектурного проектирования под названием Пространственный анализ.
  3. Можно показать, что результаты видимости на основе сетки сходятся к точному решению, используя теорию вероятностей, в частности центральную предельную теорему. Первоначальное доказательство от сообщества наборов уровней использовало численный анализ [3].
  4. Показатели видимости, полученные с помощью линейной интерполяции, можно интерпретировать как долю кратчайших путей сетки, уходящих от точки обзора, которые не заблокированы препятствиями.

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

Чтобы продемонстрировать видимость путем подсчета, мы, как и прежде, предположим, что точка обзора находится в верхнем левом углу. Мы начинаем с того, что ставим 1 в этот угол, затем многократно копируем числа вниз и вправо. Когда два числа сходятся в одной ячейке сетки, мы складываем их вместе. В результате каждая ячейка сетки содержит количество путей сетки, уходящих от точки обзора и заканчивающихся в этой ячейке. Например, таких путей от точки обзора до правого нижнего угла 742.

Далее повторяем процесс, игнорируя все препятствия. Каждая ячейка сетки заканчивается максимально возможным количеством путей сетки от точки обзора до этой ячейки. На самом деле это всего лишь Треугольник Паскаля, хорошо известный числовой шаблон, который подробно обсуждается в предыдущей статье. Обратите внимание, что существует максимум 2002 пути сетки от точки обзора до нижнего правого угла.

В нашем подходе поиск пути путем подсчета мы взяли два набора счетчиков пути и перемножили их. В видимости путем подсчета мы берем два набора счетчиков пути и делим их. Взяв фактическое количество путей к каждой ячейке сетки (первая анимация выше), а затем разделив на максимально возможное количество путей к этой ячейке (вторая анимация), мы получим показатель видимости для каждой ячейки сетки. Затем мы классифицируем каждую ячейку как видимую, если ее оценка составляет не менее 0,5. Например, ячейка в правом нижнем углу достигается 742 из возможных 2002 путей сетки. Его показатель видимости составляет 472/2002, или примерно 0,37, и он классифицируется как невидимый.

Опять же, в статье мы продемонстрировали, что показатели видимости, вычисленные путем подсчета, математически эквивалентны показателям, полученным по исходной формуле интерполяции. Другими словами, оба метода являются жизнеспособными способами решения проблемы видимой области. Однако, если мы решим реализовать видимость путем подсчета, мы должны помнить, что количество путей увеличивается экспоненциально с расстоянием. Если мы представим эти счетчики с помощью 64-битных чисел с плавающей запятой, счетчики пути переполнятся после достижения 1030 шагов сетки от точки обзора. По этой причине я считаю, что имеет смысл по умолчанию использовать метод линейной интерполяции при реализации видимости на основе сетки. В то же время я чувствую, что связь с подсчетом путей интересна и заслуживает того, чтобы ею поделились.

Большие районы

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

Сказав это, есть способ повысить точность результатов видимости на основе сетки без увеличения разрешения сетки. До сих пор в наших примерах использовалась только 4-окрестность, которая является самой простой, но наименее точной окрестностью двумерной сетки. Как упоминалось ранее, у нас есть возможность выбрать большую окрестность сетки для получения более точных результатов. На приведенной ниже диаграмме показаны 4-, 8- и 16-окрестности для прямоугольных сеток, а также 6- и 12-окрестности для треугольных сеток.

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

import numpy as np
import matplotlib.pyplot as plt

# Set dimensions
nx = 25
ny = 25
# Create map
grid = np.ones((nx,ny))
wx = nx//10 + 1
wy = ny//10 + 1
grid[int(.3*nx):int(.3*nx)+wx,int(.1*ny):int(.1*ny)+wy] = 0
grid[int(.1*nx):int(.1*nx)+wx,int(.5*ny):int(.5*ny)+wy] = 0
grid[int(.6*nx):int(.6*nx)+wx,int(.6*ny):int(.6*ny)+wy] = 0

# Display map
plt.figure("Map")
plt.imshow(np.transpose(grid))

# Define visibility function
def visibility_within_cone(grid, u_direction, v_direction):
    u = np.asarray(u_direction, dtype=int)
    v = np.asarray(v_direction, dtype=int)
    origin = np.array([0,0], dtype=int)
    dims = np.asarray(grid.shape, dtype=int)
    m = 0
    k = 0
    position = np.array([0,0], dtype=int)
    while np.all(position < dims):
        while np.all(position < dims):
            if not np.all(position == 0):
                pos = tuple(position)
                pos_minus_u = tuple(np.maximum(origin, position - u))
                pos_minus_v = tuple(np.maximum(origin, position - v))
                grid[pos] *= (m*grid[pos_minus_u] + 
                              k*grid[pos_minus_v]) / (m + k)
            k += 1
            position += v
        m += 1
        k = 0
        position = m*u

# Compute visibility
visibility_within_cone(grid, [1,0], [0,1])

# Display visibility
plt.figure("Visibility")
plt.imshow(np.transpose(grid))
plt.show()

Поскольку мы вызываем функцию с векторами [1,0] и [0,1], мы по-прежнему используем 4-окрестность. Результаты такие же, как и у нашего первого скрипта.

Но теперь мы можем легко изменить код, чтобы использовать 8-окрестность. Для этого замените код в разделе Compute visibility кодом ниже. Теперь функция видимости применяется дважды: сначала внутри конуса между диагональю [1,1] и осью сетки [1,0], а затем между [1,1] и [0,1].

# Compute visibility
visibility_within_cone(grid, [1,1], [1,0])
visibility_within_cone(grid, [1,1], [0,1])

Вот результаты для 8-окрестности. Края тени стали более резкими.

Наконец, мы можем перейти к 16-окрестности, применив функцию видимости в пределах 4 конусов.

# Compute visibility
visibility_within_cone(grid, [2,1], [1,0])
visibility_within_cone(grid, [2,1], [1,1])
visibility_within_cone(grid, [1,2], [1,1])
visibility_within_cone(grid, [1,2], [0,1])

Вот результаты 16-окрестности.

Кажется, что 16-окрестность обеспечивает более чем достаточную точность для большинства приложений. Однако можно продолжить обновление до 32-окрестности, 64-окрестности и т. д., если требуются более качественные результаты.

Это заботится о прямоугольных сетках. Треугольные сетки, также известные как шестиугольные сетки, сложнее реализовать, потому что не существует идеального способа индексации ячеек сетки. Различные стратегии индексации описаны в руководстве Red Blog Games по Шестиугольным сеткам, которое включает раздел о видимости с использованием тестов прямой видимости. Я оставляю вам задачу реализовать видимость на основе сетки на треугольной сетке.

Заключение

Видимость на основе сетки — это простая и практичная альтернатива трассировке лучей и другим векторным методам видимости. Из-за времени и контекста его открытия этот подход остается в значительной степени неизвестным ученым-компьютерщикам. Но я надеюсь, вы согласитесь, что пришло время сделать видимость на основе сетки видимой, и я надеюсь, что вы найдете возможность использовать ее в одном из ваших собственных проектов искусственного интеллекта.

Рекомендации

[1] Р. Гольдштейн, К. Уолмсли, Дж. Библиович, А. Тессье, С. Бреслав, А. Хан, Подсчет путей для навигации на основе сетки (2022), Журнал исследований искусственного интеллекта, том. 74, стр. 917–955.

[2] Ю.-Х. Р. Цай, Л.-Т. Ченг, Х. Ошер, П. Берчард, Г. Сапиро, Видимость и ее динамика в неявной структуре на основе PDE (2004) [PDF]. Журнал вычислительной физики, том. 199, нет. 1, стр. 260–290.

[3] С.-Ю. Као, Р. Цай, Свойства алгоритма набора уровней для задач видимости (2008) [PDF], Journal of Scientific Computing, vol. 35, стр. 170–191.

[4] Д. Фишер-Гевирцман, А. Шашков, Ю. Дойтшер, Объемный анализ видимости городской среды на основе вокселей (2013), Survey Review, vol. 45, нет. 333, стр. 451–461.