Поле зору: як ігрових NPC насправді бачать вас

Бачення світу через трикутники

Дайте ігровому персонажу очі, і ви отримуєте геометрічне запитання, яке він повинен вирішувати шістдесят разів на секунду: які частини карти він може бачити зараз? Грубий розрахунок – відправляти промінь до кожного пікселя та перевіряти, що він потрапляє – надто повільний. Ефективний варіант – тіні: відправляти промені лише до кутів перешкод, сортувати точки контакту за кутом відносно глядача та з’єднувати їх в одну полігонал. Всередині цієї полігона видно; все зовні приховано за стіною.

Це одна з тих самих алгоритмів, що лежать в основі туману війни в стратегічних іграх, лінців у жахах та систем видимості, які роблять стелс-ігри можливими: якщо полігон, який містить позицію гравця, також містить позицію охоронця, то охоронець, в принципі, може бачити гравця.

Чому кути, а не пікселі

Полігон видимості повністю визначається кутами кожного об’єкта в сцені, а також двома крайніми променями, які торкаються силуету кожного об’єкта. Для кожного кута промінь від глядача або зупиняється точно в цьому куті (все, що знаходиться за ним, не видно в цьому напрямку), або продовжується дотично поки не зіткнеться з чимось іншим. Таким чином, алгоритм кидає один промінь безпосередньо на кожен кут і ще два промені під кутом, який трохи відхиляє його від кута, щоб зловити тінь, що відкривається за краєм:

для кожного кута об’єкта c: кинути промінь під кутом(c) - епсилон кинути промінь під кутом(c) кинути промінь під кутом(c) + епсилон сортувати всі точки зіткнення за кутом з’єднати їх у порядку → полігон видимості Сортування за кутом навколо NPC перетворює розсип точок перетину променів і стін у єдину зв'язану форму. Розкладіть точки зіткнення по спіралі, пройдіться навколо них один раз, і кожна послідовна пара плюс глядач утворюють одне трикутник полігону — намалюйте всі трикутники як заповнену фігуру, і ви отримаєте світло-кольоровий кут, який бачить гравець, з гострими краями тіні точно в кутах об’єктів.

for each obstacle corner c:
  cast ray at angle(c) - epsilon
  cast ray at angle(c)
  cast ray at angle(c) + epsilon
sort all hit points by angle
connect them in order  →  visibility polygon

Додавання поля зору конуса та радіусу видимості

Повна модель полігону зору 360° моделює всевидкого датчика; справжні NPC дивляться в один бік з обмеженим конусом і максимальною дальністю видимості. Обидва це недорогі доповнення: обрізайте промінь, який відкидає тіні, до кутів всередині [facing − fov/2, facing + fov/2], і обмежуйте довжину кожного променя на відстані видимості, розглядаючи межу радіусу як вигнутий «перешкоду», дугу якої заповнюють додатковими променями, щоб полігон видимості плавно закривався замість того, щоб закінчуватися нерівним краєм.

visible = angle_in_fov(target, npc.facing, npc.fovAngle)
       and distance(npc.pos, target) < npc.sightRange
       and not blocked_by_any_obstacle(npc.pos, target)

Від геометрії до ігрової механіки

Після того, як ви отримаєте полігон видимості, механіка стелсу практично виникає сама по собі. Тест на наявність точки всередині багатокутника визначає, чи бачить гравець зараз противника. Накопичення часу перебування всередині кону перед повним тривожним станом (замість миттєвого виявлення) робить відчуття проходження непомітною, а не випадковим – більшість ігор у жанрі стелсу використовують «індикатор підозри», який заповнюється, поки гравець знаходиться всередині полігона, та зменшується, коли він залишає його, замість жорсткого булевого значення.

Тот самий полігон видимості може керувати й поширенням звуку та світла: промінь вогню, радіус розповсюдження шуму пострілу, що перетинається з лінією зору, або обертовий конус охоплення камери спостереження – все це є ідентичними обчисленнями тіні, які виконуються за допомогою променів, діапазонів та швидкостей оновлення, але з різними параметрами.

Технологічні примітки

Для сцени з n кутами перетину (опори) алгоритм сортування та обрізання, описаний вище, працює за часом O(n log n) на запит, що визначається сортуванням за кутом – достатньо швидко для перерахунку кожного кадру для десятків NPC проти кількох сотень стінових сегментів, що точно відповідає симуляції на цій сторінці з прямокутними перешкодами, які ви можете перетягувати та змінювати розмір. У великих іграх-певному типу замість цього попередньо обчислюється статична структура видимості один раз (подвійний граф навігаційної сітки або портал/розділення комірок рівня), а потім виконуються промені для перевірки видимості лише для рухомих перешкод, оскільки повторне сортування тисяч кутів шістдесят разів на секунду для кожного патруля дійсно додає навантаження.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Field of View і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.