2d видимость

1. Лучевое литье #
2. Отслеживание стены #
3. Детская площадка #
4. Объединение результатов #
5. Видение игрока
6. Объекты карты
7. Поведение AI
8. Реализация #
9. Рекомендации #

Июнь 2012, обновлено март 2018

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

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

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

Сообщество roguelike собрало несколько алгоритмов [1], особенно для сеток (см. этот обзор [2]). Алгоритмы вычитания начинаются со всего видимого, а затем вычитаются из скрытых областей; Аддитивные алгоритмы начинаются с ничего не видимого, а затем добавляют видимые области. Я опишу аддитивный алгоритм, который работает с отрезками, а не только со сплошными блоками или сетками.

Лучевое литье #

Простой подход - отбрасывать лучи из центра. Это разумный первый шаг, чтобы получить приблизительный ответ:

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

Это оно! Алгоритм:

1. Рассчитайте углы, где стены начинаются или заканчиваются.
2. Направьте луч из центра вдоль каждого угла.
3. Заполните треугольники, генерируемые этими лучами.

Отслеживание стены #

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

Для области между последовательными лучами мы хотим найти ближайшую стену . Эта стена освещена; все остальные скрыты. Наша стратегия будет состоять в том, чтобы развернуться на 360 ° и обработать все конечные точки стены. По ходу дела мы будем следить за стенами, которые пересекают линию разметки.

Переместите ползунок, чтобы линия развертки прошла конечные точки:

Следующий шаг - отслеживать, через какие стены проходит луч. Видна только ближайшая стена. Как вы узнаете, какая стена ближайшая? Самое простое - рассчитать расстояние от центра до стены. Тем не менее, этот подход не работает, если стены имеют разные размеры, поэтому в демонстрации используется немного более сложный подход, который я не буду здесь объяснять.

Переместите ползунок, чтобы смести углы с ближайшей стеной, нарисованной белым, а остальные стены - черным.

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

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

конечные точки var; # список конечных точек, отсортированный по углу var open = []; # список стен, по которым линия развертки пересекает петлю над конечными точками: запомните, какая стена является ближайшей, добавьте все стены, которые НАЧИНАЮТСЯ в этой конечной точке, к «стенам», удалите все стены, которые ЗАКОНЧИТЕСЬ в этой конечной точке, из «стен», выясните, какая стена сейчас ближайшая изменена ближайшая стена: заполните текущий треугольник и начните новый

Детская площадка #

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

Объединение результатов #

Мы можем использовать операции над множествами, чтобы объединить результаты этого алгоритма интересными способами. Они реализованы либо как логические операции в алгоритмах, которые анализируют выходные данные, либо как растровые операции в алгоритмах, которые визуализируют выходные данные.

Видение игрока

Самая простая операция - ограничить зрение игрока, пересекая вывод с пределом видимости. Например, пересекайте выходные данные алгоритма с кружком, чтобы ограничить радиус, который вы видите. Пересечь градиентный круг, чтобы свет падал с расстояния. Пересечение с конусом, чтобы создать эффект «фонарик», который позволяет вам видеть дальше перед собой, но не сильно позади вас (см. Трейлер Динамит Джек [3] для примера этого).

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

Объекты карты

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

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

Поведение AI

Видимость также может быть использована для построения поведения ИИ.

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

Эта диаграмма показывает аннотации карты, которые может рассчитать юнит AI:

Гранаты, брошенные в фиолетовые области, будут ударить по игроку. Оранжевые и фиолетовые области опасны для стояния; игрок может отстреливать ИИ оттуда. ИИ должен стоять в безопасной (синей) зоне и бросать гранату в пурпурную зону, а затем укрываться. Как вы рассчитываете покрытие? Снова запустите алгоритм видимости с того места, где ИИ планирует бросить гранату, чтобы шкафы и столы блокировали линию видимости.

Реализация #

Я написал Реализация Haxe 3 этого алгоритма с открытым исходным кодом под лицензией Apache v2 (аналогично MIT и BSD, его можно использовать в коммерческих проектах). Haxe [4] код может быть скомпилирован в Javascript, Actionscript, C ++, Java, C # или PHP. Я скомпилировал его в Javascript для этой веб-страницы и скомпилировал во Flash для некоторых других моих проектов. Я собрал это на эти языки:

• Actionscript ; удобочитаемый, так как Actionscript не слишком отличается от Haxe
• Javascript (используется для демонстраций на этой странице); в основном читабельный.
• Javascript [5] перенесено вручную Кириллом Сильверманом; более читабельным, чем тот, который собран из Haxe.
• Джава ; мягко читаемый, но не отличный.
• C # ; мягко читаемый, но не отличный. Рой Triesscheijn имеет лучшую версию Вот [6].
• Алекс Холл имеет версию GDscript [7].

Уэйд Тричлер предлагает портирование вручную [8] будет генерировать более чистые результаты, чем при использовании вывода Haxe. Согласен. Вы также поймете алгоритм лучше, если конвертируете код вручную.

Предупреждение: моя реализация посредственная . Отсутствует оптимизация и есть проблемы с числовой устойчивостью. Он генерирует лишние пустые треугольники на выходе. Эта страница [9] стоит прочитать. Таш опубликовал в комментариях Версия C ++ [10], который также обрабатывает сложные случаи.

Хотя основная часть алгоритма привязана к процессору, графический процессор можно использовать для рендеринга треугольника в растровое изображение и операций компоновки для объединения выходных данных растрового изображения. (Логическая операция «И» становится умножением растрового изображения; логическое «ИЛИ» становится добавлением и зажимом растрового изображения.) В моих проектах производительности было недостаточно, поэтому я не создал версию для графического процессора. Если ваша игра связана с процессором, подумайте об использовании вычитающего алгоритма (вместо аддитивного, показанного здесь), который отображает тень каждого отрезка в виде квадрата. Это увеличит нагрузку рендеринга на GPU, но не требует сортировки на CPU. Если скорость заполнения является проблемой, рассмотрите рендеринг легкого растрового изображения с более низким разрешением, чем у игрового экрана, и масштабирование его.

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

1. Bungiu, Francisc, et al. «Эффективное вычисление полигонов видимости». [11] Препринт arXiv arXiv: 1403.3905 (2014). В этой статье рассматривается несколько алгоритмов, в том числе тот, который значительно быстрее, чем тот, который я использую на этой странице. Эта статья вышла после того, как я написал свою страницу; Я хотел бы однажды вернуться и попробовать их алгоритм.
2. Асано, Тецуо. «Эффективный алгоритм нахождения многоугольника видимости для многоугольной области с отверстиями». [12] СДЕЛКИ IEICE (1976-1990) 68,9 (1985): 557-559. Это алгоритм развертки [13] Как я использую на этой странице, применяется к полярным координатам вместо декартовых координат. Кажется, это статья, которая представила алгоритм, но я не могу найти статью в Интернете.

связанные с #

Взгляд и свет Никки Кейс [14] использует тот же алгоритм для решения проблемы видимости. Страница Сундарама Рамасвами [15] покрывает видимость дугами вместо окружностей и включает подробное объяснение алгоритма и реализации. Мой блог [16] имеет больше ссылок на подобные проекты. Великолепные обложки алгоритмы видимости, оптимизированные для сеток [17], с интерактивными диаграммами и примерами кода. Кевин Зунига имеет подход «разделяй и властвуй» [18] с параллельной реализацией в CUDA. Проблема горизонта [19] похож на 2d видимость, за исключением того, что он в декартовых координатах вместо полярных координат. Там также проблема художественной галереи [20] о размещении нескольких охранников в окружающей среде, чтобы они могли видеть каждую область карты. Я делаю список на Trello возможные будущие обновления на этой странице [21].

Похожие