- PVSM.RU - https://www.pvsm.ru -

Техника тотального предрасчёта в алгоритме освещения для тайловой 2D игры

Привет! Моя последняя игра – изометрическая бродилка, одной из особенностью которой является «исследование» территории: изначально карта чёрная и игрок открывает этот «туман войны» по ходу игры. Причём видимость тайлов зависит не только от расстояния до персонажа, но и от окружения: клетки за непрозрачными стенами не видны, даже если подойти в упор, а, например, кустарник ухудшает видимость клеток за ним на 50%.

image

Чтобы не нагружать процессор покадровой трассировкой лучей (для определения какая клетка насколько в данный момент «видима»), я использовал довольно интересный метод «тотального предрасчёта» – основные параметры для фактически всех возможных ситуаций считаются до игры в большую матрицу, и во время игры остаётся только обращаться к ней, выбирая нужные значения.

Что я имею ввиду под предварительными расчётами:

Герой ставится в клетку начала координат (0;0). Для каждой клетки в пределах видимости экрана (с запасом, в пределах двух экранов) считаются различные игровые параметры, в том числе список клеток, которых пересекает отрезок от начала координат до её центра:

image

Если быть точнее, то подобные списки считаются для каждого из 4х углов каждой клетки:

image

Все эти данные записываются в «матрицу видимостей» M.

Как это работает? У каждого объекта в игре есть параметр «непрозрачность» — величина от 0 до 1, процент загораживаемости обзора. В игре, чтобы узнать насколько виден тайл (xt;yt) относительно положения героя (x0;y0), мне нужно:

1. Обратиться к элементу матрицы Mt = M[xt-x0;yt-y0]
2. Посчитать насколько виден каждый из углов этого тайла (причём не учитываются углы, которые загораживаются самим тайлом (xt;yt), так что их 2 или 3): для этого я считываю из Mt вектор тайлов, которые встречаются на пути до угла и перемножаю «степени видимости» всех объектов, которые в них находятся (и да, как только встречается объект с нулевой видимостью, прохождение по списку можно не продолжать).
3. Степень видимости тайла Vt= среднее арифметическое видимостей каждого из его углов.

Так я делаю для каждого из тайлов в некоторой области вокруг героя, когда что-то меняется (положение героя или объектов).

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

image

Способ, как вы понимаете, не совсем точный (по сравнению с честной «аналоговой» трассировкой луча), но даёт хорошие значения. Дискретность заметна тем меньше, чем визуально меньше клетки в игре.

Насколько будет повышать производительность предварительный расчёт всех параметров в «матрицу видимостей» (по сравнению с определением параметров на ходу) будет зависеть от языка, но по сути все геометрические расчёты заменяются на операцию доступа к элементу матрицы/вектора. У меня на AIR прирост в скорости колеблется от 7 до 11 раз (зависит от степени нагруженности области карты объектами)

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

image
(монетки имеют небольшое свечение)

Демонстрация смены видимости тайлов в динамике:

Спасибо за внимание!

Автор: AntonRiot

Источник [1]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/algoritmy/212991

Ссылки в тексте:

[1] Источник: https://habrahabr.ru/post/315970/?utm_source=habrahabr&utm_medium=rss&utm_campaign=sandbox