Блукаючий монстр: як позбутися від проблем на карті


Вже в процесі створення The Witness стала однією з найулюбленіших моїх ігор. Я почав грати в неї з того моменту, коли Джонатан Блоу почав її розробку, і не міг дочекатися її релізу.

На відміну від попередньої гри Джона Braid, масштаб ресурсів і програмування The Witness був набагато ближче до AAA-проектів, ніж до інді-ігор. Всім, хто працює над подібними проектами, відомо, що обсяг роботи при виборі такого шляху значно зростає. Над The Witness працювало набагато більше людей, ніж над Braid, але як і у випадку з будь-яким проектом такого рівня, в ньому є безліч аспектів, які вимагають більше уваги, ніж може дозволити собі керівництво проекту.

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

Walkmonster in Wall

У контексті The Witness, завдання коду руху гравця — бути як можна більш ненав’язливим. Гравець повинен повністю зануритися в альтернативну реальність, і в цьому ігровому досвіді важлива кожна деталь. Найменше нам хотілося, щоб гравець зауважив, що він сидить за комп’ютером і переміщує віртуальну камеру.

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

Після нашого обговорення я приступив до роботи над цим завданням. Першим ділом я вирішив написати інтегровані інструменти для роботи з кодом руху гравця, щоб ми могли аналізувати його і спостерігати за його поточною поведінкою. Відкривши проект, я зіткнувся з вже відомоїю мені серйозною проблемою: як назвати перший файл вихідного коду? Це завжди найважливіша частина будь-якого проекту (як одного разу сказав Боб Поллард про назви музичних груп та альбомів). Якщо ви дасте файлу ісходника відповідну назву, то подальша робота буде чіткою і плавною. Виберете неправильне — можете погубити і весь проект.

Але як назвати систему для забезпечення якості коду руху гравця? Раніше мені ніколи не доводилося писати подібний код. Коли я задумався про це, то усвідомив, що особисто бачив приклад такого коду тільки одного разу: при грі в ранню бету Quake. У ній були присутні баги з розташуванням монстрів, а у вікні консолі можна було бачити повідомлення про помилки, що свідчать, що монстри, замість створення на поверхні землі, створюються, частково перетинаючись з геометрією рівнів. Кожне експериментальне повідомлення починався з фрази «walkmonster in wall at…»

Бінго! Складно підібрати для файлу коду кращу назву, ніж «walk_monster.cpp». І я був майже впевнений, що з цього моменту код буде створюватися без проблем.

Рух до точки

Коли ви хочете тестувати систему, то найважливіше — це насправді тестувати систему. Хоча це правило виглядає простим, які пишуть тести людям часто не вдається його виконати.

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

Але насправді ми протестували дані, а не код. Дуже ймовірно, що в коді руху знайдуться помилки, що призводять до поганої поведінки навіть при якісних даних.

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

Перша процедура найбільш близька до реальних дій людини. Це виклик оновлення, який підключається до системи обробки введення The Witness і передає їй синтезовані події клавіатури і миші. Вона здатна на прості речі, які може робити людина: озиратися по сторонах, йти напряму до точки, дивитися на точку, і так далі. Процедура виконує ці дії простий емуляцією взаємодії користувача з клавіатурою і мишею, тому я був впевнений, що при обробці введення The Witness все буде виконуватися саме так, як і при тестуванні. У наступних статтях я детальніше розповім про цю систему та її використанні.

Друга процедура — це один етап, не використовується на даному рівні. Це функція під назвою DriveTowardPoint, яка отримує дві точки світу і, викликаючи вже існуючу систему колізій гравця, намагається безпроблемно переміститися з однієї точки в іншу. Виконуючи повернення, вона передає інформацію про спробу: які перешкоди зустрілися їй на шляху і вдалося досягти кінцевої точки.

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

Читайте також  Віконце з кнопками на JavaFX:

Варто також зауважити, що цієї функції не передаються фізичні вхідні дані; наприклад, для початкової точки не зазначаються швидкості. Так зроблено тому, що The Witness — це не екшн-гра, тому у гравця є мало значущих фізичних властивостей. Гравці не можуть стрибати, бігати по стінах, включати «bullet time». Підтримувати такі поведінки можна з допомогою систем, які я опишу пізніше, але вони додають рівні складності, які в нашому проекті не були потрібні.

Як би то не було, після реалізації DriveTowardPoint я міг приступити до виконання першого завдання системи: визначення того, куди гравець може рухатися на острові The Witness.

Rapidly Exploring Random Trees

Куди можуть рухатися гравці? Здається, що це просте питання, але ви здивуєтеся, дізнавшись, як багато ігор випускалося, коли команда розробників не знала справжньої відповіді. Якщо це можливо, то я хотів, щоб The Witness була однією з тих небагатьох ігор, в якій розробники перед випуском точно знали, куди може і куди не може потрапити гравець — ніяких сюрпризів.

Це робить постановку проблеми (але, ймовірно, не її рішення) дуже простою: при наявності функції DriveTowardPoint, надійно визначає, чи може гравець рухається по прямій лінії між двома точками, створити карту покриття, демонструючу, де може виявитися гравець.

За якихось причин я, ще не написавши жодного рядка коду, чомусь вважав, що найкраще буде використовувати Rapidly Exploring Random Tree. Для тих, хто незнайомий з цим алгоритмом, поясню: це дуже простий процес, в якому ми записуємо всі точки, відвідані нами з посиланням на точку, з якої ми прийшли. Щоб додати в дерево точку, ми беремо випадкову цільову крапку в будь-якому місці світу, вибираємо найбільш близьку до неї точку, уже знаходиться в дереві, і намагаємося дістатися з цієї точки до цільової. Те місце, де ми опинилися в результаті, стає наступною точкою вибірки.

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

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


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


Якщо б я задумався про це перед початком роботи, то зрозумів би, що перевага алгоритмів зразок Rapidly Exploring Random Tree полягає в тому, що вони ефективно досліджують багаторозмірні простори. Насправді, зазвичай це основна причина їх використання. Але в The Witness немає великих просторів. У нас є двовимірний простір (так, розподілений за складного різноманіття, але це все-таки двовимірний простір).

У цьому низькорозмірному просторі переваги Rapidly Exploring Random Tree проявляються слабо, а його недолік критично важливий для мого завдання: алгоритм призначений для найбільш ефективного пошуку шляхів до сполучених парам точок у просторі, а не для ефективного пошуку всіх досяжних точок цього простору. Якщо у вас таке завдання, то насправді у Rapidly Exploring Random Tree піде на її рішення величезну кількість часу.

Тому я швидко зрозумів, що мені потрібно шукати алгоритм, що ефективно повністю покриває низьковимірні простори.

3D Flood Filling

Коли я по-справжньому задумався про вибір алгоритму, то стало очевидним, що насправді мені потрібно щось на кшталт старої доброї двомірної заливки, яка використовується для заповнення областей бітової карти. Для будь стартової точки мені потрібно було просто заповнити весь простір, вичерпно перевіряючи кожен можливий шлях. На жаль, з багатьох причин рішення для The Witness буде набагато складніше, ніж для двомірної бітової карти.

По-перше, у нас немає чіткої концепції кінцевої зв’язності точки. Весь простір безперервний. Це для пікселя ми з легкістю можемо перерахувати 4 можливі місця, в які можна потрапити з заданої точки, і перевірити кожне з них по черзі.

По-друге, немає фіксованого розміру положення в просторі, на зразок пікселя на бітовій карті. Поверхні, по яких рухається гравець, і перешкоди можуть перебувати де завгодно, у них немає максимального або мінімального топологічного розміру, як немає прив’язки до якоїсь зовнішньої сітки.

По-третє, хоча рух простору The Witness локально можна вважати переміщенням по площині, сам простір насправді є глибоко взаємопов’язаним і мінливих різноманіттям, в якому прохідні для гравця області знаходяться безпосередньо над іншими областями (іноді може бути декілька розташованих один над одним рівнів). Крім того, існують сполуки, що змінюються залежно від станів світу (відкриті/закриті двері, що піднімаються/опускаються ліфти тощо).

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

Читайте також  Будуємо простий GraphQL API сервер express і nodeJS

Відразу мені в голову мені не спадало жодного хорошого рішення, тому я вирішив почати з простих експериментів. Скориставшись написаним мною кодом Rapidly Exploring Random Tree, я змінив вибір цільових точок з випадкового на дуже контрольований. При кожному додаванні нової точки дерево я вказував, що точки знаходяться на одиничній відстані вздовж основних напрямків від точки, яка буде вважатися майбутньої цільової точкою, як це буває в простій двовимірний заливці.

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


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


В областях без перешкод алгоритм працює добре, виконуючи вибірки на відносно рівних відстанях. Але при попаданні на кордон перетинання створюють точки, що знаходяться «поза ґратами», тобто не вирівняні згідно з паттерном вибірок, за яким алгоритм заповнював сусідню відкриту область. Причина, по якій точки, що знаходяться «в сітці» не створюють надмірно щільною тесселяцію, полягає в тому, що кожна нова точка, яка намагається повернутися до одного з попередніх знаходить там попередню точку і знову відмовляється перераховувати її. Але при створенні нових точок на грані вони абсолютно не вирівняні, тому ніщо не може перешкодити їм повернутися до вже дослідженого простору. Це призводить до створення хвилі зміщених вибірок, яка триває, поки не добереться до випадкової лінії точок десь в іншому місці, яка виявиться досить близькою, щоб алгоритм міг порахувати її збігаючись з рухомим фронтом точок.

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

Однак існує просте рішення цієї конкретної проблеми: потрібно розширити відстань, на якому дві точки вважаються «досить близькими». Зробивши так, ми зменшимо щільність семплювання в місцях, які нам не важливі, але і втратимо при цьому щільність семплювання в місцях, які нам важливі, наприклад, області навколо кордонів, які ми хочемо ретельно перевірити на наявність «дірок».

Локалізоване спрямоване семплірування

Ймовірно, тому, що я почав з Rapidly Exploring Random Tree, мій мозок витіснив усі інші ідеї, крім ідеї близькості. Всі попередні алгоритми для виконання свого завдання використовували близькість, наприклад, для того, щоб визначити нову точку, яку потрібно розглянути наступного, або для того, щоб вибрати точку, з якої слід почати, щоб добратися до нової цільової точки.

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

Коли я поміняв погляд на речі, то правильний підхід до семпліювання здався очевидним. Кожен раз, коли я хотів розширювати дослідження простору з точки, я здійснював запит про існування в локальному оточенні найближчих точок. Однак замість того, щоб використовувати для дослідження відстань до цих точок, я буду класифікувати їх за їх напрямами (до цього я використовував лише вісім основних напрямків, але мені хотілося поекспериментувати і з іншими ядрами).

У будь-якому напрямку, в якому не «бачу» точку, я проходжу задану відстань і додаю крапку в будь-якому місці, де зупинився (незалежно від того, зіткнувся я з чимось, чи ні). Якщо в якомусь із напрямків я бачу точку, то рухаюся туди і перевіряю, чи зможу я туди дістатися. Якщо можу, то я просто додаю видиме ребро, щоб користувач легко міг побачити, що точки з’єднані. Якщо не можу, то я додаю нову точку в місці колізії, визначаючи кордон перешкоди.

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


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


Більш того, алгоритм абсолютно не схильний до впливу зміни станів або проблем зі складними різноманіттями. Він має справу тільки з крапками, і ці точки можуть бути де завгодно, а нові можна додати в будь-який момент часу. Якщо ви вже склали карту області з закритими дверима, то після відкриття дверей вам достатньо помістити єдину точку дослідження по іншу сторону дверей і наказати алгоритмом продовжити розширення цієї карти, після чого він правильно з’єднається і належним чином досліджує всю область за дверима.

Читайте також  Швидкий ресайз джипегов на відеокарті

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

Рудиментарна перевірка ребер

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

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

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


А ось та ж область з перевіркою ребер:


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

Швидкі перемоги

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


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


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



Ці об’єкти повинні були стати непрохідними скелями, але Walk Monster виявив, що цього не сталося. Гірше того — Walk Monster виявив, що шлях чомусь проходимо тільки в одному напрямку (на скріншоті — зліва направо), а такого бути не повинно. Я переконався, що гравець справді може це зробити (мені вдалося). Дуже цікаво спостерігати за виникненням таких помилок!

Відкриті питання

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

По-перше, яку постобробку потрібно провести з даними, щоб їх легше візуалізувати? Людям складно буде розібратися в необробленої мережі з точок і ребер, але якщо покращити опис даних, то це, можливо, зашкодить з першого погляду оцінювати складні прохідні області.

По-друге, як можна поліпшити патерни семплювання навколо кордонів, щоб гарантувати знаходження максимальної кількості «дірок»? Чи існують хороші способи характеризації відомості фігур в решітку, і є якісні схеми тесселяції, максимально збільшують ймовірність перетину і проходження через ці фігури?

В-третіх, які патерни семплювання краще для заповнення пространсв — регулярні або рандомізовані? Я з легкістю можу змінити критерії вибору цільових точок, щоб створити більш рандомізовані патерни, але не дуже зрозуміло, чи варто так робити, і якщо варто, то які типи рандомізованих патернів будуть краще.

По-четверте, яку інформацію ми хочемо отримувати з карт прохідних областей, якщо ми вже навчилися їх будувати? Наприклад, дуже просто розширити вже наявну систему такими функціями, як пошук шляхів або карти відстаней, щоб користувач міг вибрати точку і запросити найкоротший шлях між нею і якоюсь іншою точкою, або побачити теплову карту відстані між точкою та іншими точками карти. Корисними будуть такі запити? Які ще можна використовувати запити?

На даний момент, одержуваних з допомогою Walk Monster візуалізацій прохідних областей більш ніж достатньо, щоб показати, що код руху гравця досить поганий. Я планував перейти до створення системи для нічного тестування карт за допомогою методу імітації інтерфейсу вводу, але очевидно, що у нас і без цього кроку вже є достатньо проблем для вирішення. Тому наступним етапом буде підвищення надійності коду руху гравця. І поки я працюю над цим, мені хотілося б перевірити, чи можна підвищити швидкість виконання на один-два порядки, тому що поки роботу Walk Monster дуже сильно уповільнює гальмівна система колізій.

Степан Лютий

Обожнюю технології в сучасному світі. Хоча частенько і замислююся над тим, як далеко вони нас заведуть. Не те, щоб я прям і знаюся на ядрах, пікселях, коллайдерах і інших парсеках. Просто приходжу в захват від того, що може в творчому пориві вигадати людський розум.

You may also like...

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *