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

Привіт! Моя остання гра – ізометрична бродилка, однією з особливістю якої є «дослідження» території: спочатку карта чорна і гравець відкриває цей «shadow war» по ходу гри. Причому видимість тайлів залежить не тільки від відстані до персонажа, але і від оточення: клітини за непрозорими стінами не видно, навіть якщо підійти впритул, а, наприклад, чагарник погіршує видимість клітин за ним на 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
(монетки мають невелике світіння)

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



Спасибі за увагу!
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.