Натрапив на цікавий матеріал про штучний інтелект в іграх. З поясненням базових речей про ІІ на простих прикладах, а ще всередині багато корисних інструментів та методів для його зручної розробки та проектування. Як, де і коли їх використовувати, теж є.
Більшість прикладів написані в псевдокод, тому глибокі знання програмування не знадобляться. Під катом 35 аркушів тексту з картинками та гіфками, так що приготуйтеся.
UPD. Вибачаюсь, але власний переклад цієї статті на Хабре вже робив . Прочитати його варіант можна Але чомусь стаття пройшла повз мене (пошуком користувався, але щось пішло не так). Оскільки пишу в блог, присвячений геймдеву, вирішив залишити свій варіант перекладу для передплатників (деякі моменти в мене оформлені по-іншому, деякі — навмисно пропущені за порадою розробників).
Що таке ІІ?
Ігровий ІІ зосереджений у тому, які дії має виконувати об'єкт, з умов, у яких перебуває. Зазвичай це називають керуванням «інтелектуальними агентами», де агент є ігровим персонажем, транспортним засобом, ботом, а іноді й більш абстрактним: цілою групою сутностей або навіть цивілізацією. У кожному випадку це річ, яка має бачити своє оточення, приймати на його основі рішення та діяти відповідно до них. Це називається циклом Sense/Think/Act (Відчувати/Думати/Діяти):
- Sense: агент знаходить або отримує інформацію про речі у своєму середовищі, які можуть вплинути на його поведінку (загрози поблизу, предмети для збору, цікаві місця для дослідження).
- Think: агент вирішує, як реагувати (розглядає, чи достатньо безпечно збирати предмети чи спочатку він має боротися/ховатися).
- Act: агент виконує дії для реалізації попереднього рішення (починає рух до супротивника чи предмета).
- …тепер ситуація змінилася через дії персонажів, тому цикл повторюється з новими даними.
ІІ, як правило, концентрується на Sense-частини циклу. Наприклад, автономні автомобілі роблять знімки дороги, поєднують їх із даними радара та лідара, та інтерпретують. Зазвичай це робить машинне навчання, яке обробляє вхідні дані і надає їм сенсу, витягуючи семантичну інформацію на кшталт «є ще один автомобіль у 20 ярдах попереду вас». Це так звані класифікації проблем.
Іграм не потрібна складна система для отримання інформації, оскільки більшість даних вже є її невід'ємною частиною. Немає необхідності запускати алгоритми розпізнавання зображень, щоб визначити, чи є ворог попереду — гра вже знає та передає відомості прямо у процесі прийняття рішень. Тому частина циклу Sense часто набагато простіше, ніж Think та Act.
Обмеження ігрового ІІ
У ІІ є низка обмежень, яких необхідно дотримуватися:
- ІІ не потрібно заздалегідь тренувати, начебто це алгоритм машинного навчання. Безглуздо писати нейромережу під час розробки, щоб спостерігати за десятками тисяч гравців та вивчати найкращий спосіб гри проти них. Чому? Бо гра не випущена, а гравців нема.
- Гра повинна розважати та кидати виклик, тому агенти не повинні знаходити найкращий підхід проти людей.
- Агентам потрібно виглядати реалістичними, щоби гравці відчували ніби грають проти справжніх людей. Програма AlphaGo перевершила людину, але обрані кроки були дуже далекі від традиційного розуміння гри. Якщо гра імітує супротивника-людини, такого почуття не повинно бути. Алгоритм потрібно змінити, щоб він приймав правдоподібні рішення, а чи не ідеальні.
- ІІ має працювати у реальному часі. Це означає, що алгоритм не може монополізувати використання процесора протягом тривалого часу для прийняття рішень. Навіть 10 мілісекунд на це занадто довго, тому що більшості ігор достатньо від 16 до 33 мілісекунд, щоб виконати всю обробку і перейти до наступного кадру графіки.
- Ідеально, якщо хоча б частина системи керується даними, щоб «некодери» могли вносити зміни, і щоб коригування відбувалося швидше.
Розглянемо підходи ІІ, які охоплюють весь цикл Sense/Think/Act.
Ухвалення базових рішень
Почнемо з найпростішої гри – Pong. Мета: перемістити платформу (paddle) так, щоб м'яч відскакував від неї, а не пролітав повз. Це як теніс, у якому ви програєте, якщо не відбиваєте м'яча. Тут ІІ відносно легке завдання — вирішити, в якому напрямку переміщувати платформу.
Умовні оператори
Для ІІ в Pong є найочевидніше рішення - завжди намагатися розташувати платформу під м'ячем.
Простий алгоритм для цього, написаний у псевдокод:
every frame/update while the game is running:
if the ball is to left of the paddle:
move paddle left
else if the ball is to the right of the paddle:
move paddle right
Якщо платформа рухається зі швидкістю м'яча, це ідеальний алгоритм для ІІ в Pong. Не потрібно нічого ускладнювати, якщо даних та можливих дій для агента не так уже й багато.
Цей підхід настільки простий, що весь цикл Sense/Think/Act ледь помітний. Але він є:
- Частина Sense знаходиться у двох операторах if. Гра знає де м'яч і де платформа, тому ІІ звертається до неї за цією інформацією.
- Частина Think теж входить до двох операторів if. Вони втілюють у собі два рішення, які у разі є взаємовиключними. В результаті вибирається одна з трьох дій - перемістити платформу вліво, перемістити вправо, або нічого не робити, якщо вона вже правильно розташована.
- Частина Act знаходиться в операторах Move Paddle Left та Move Paddle Right. Залежно від дизайну гри вони можуть переміщати платформу миттєво або з певною швидкістю.
Такі підходи називають реагуючими — є простий набір правил (у разі оператори if в коді), які реагують на поточний стан світу і діють.
Дерево рішень
Приклад з грою Pong фактично дорівнює формальній концепції ІІ, яка називається деревом рішень. Алгоритм проходить його, щоб досягти «аркуша» — рішення про те, яку дію зробити.
Зробимо блок-схему дерева рішень для алгоритму нашої платформи:
Кожна частина дерева називається node (вузол) - ІІ використовує теорію графів для опису подібних структур. Є два типи вузлів:
- Вузли ухвалення рішень: вибір між двома альтернативами на основі перевірки деякої умови, де кожна альтернатива представлена у вигляді окремого вузла.
- Кінцеві вузли: дія виконання, що представляє остаточне рішення.
Алгоритм починається з першого вузла («кореня» дерева). Він або приймає рішення про те, до якого дочірнього вузла перейти, або виконує дію, що зберігається у вузлі, і завершується.
У чому ж перевага, якщо дерево рішень, виконує ту ж роботу, що і if-оператори в попередньому розділі? Тут є загальна система, де кожне рішення має лише одну умову та два можливі результати. Це дозволяє розробнику створювати ІІ з даних, що представляють рішення в дереві, уникнувши його хардкодінгу. Подаємо у вигляді таблиці:
На стороні коду ви отримаєте систему читання рядків. Створіть вузол для кожної з них, підключіть логіку прийняття рішень на основі другого стовпця та дочірні вузли на основі третього та четвертого стовпців. Вам все ще потрібно запрограмувати умови та дії, але тепер структура гри буде складнішою. У ній ви додаєте додаткові рішення та дії, а потім налаштовуєте весь ІІ, просто відредагувавши текстовий файл із визначенням дерева. Далі передаєте файл геймдизайнеру, який зможе змінити поведінку без перекомпілювання гри та зміни коду.
Дерева рішень дуже корисні, коли вони будуються автоматично з урахуванням великого набору прикладів (наприклад, з використанням алгоритму ID3). Це робить їх ефективним та високопродуктивним інструментом для класифікації ситуацій на основі отриманих даних. Однак ми виходимо за межі простої системи для вибору дій агентами.
Сценарії
Ми розібрали систему дерева рішень, яка використовувала заздалегідь створені умови та дії. Людина, яка проектує ІІ, може організувати дерево так, як хоче, але вона все ще має покладатися на кодера, який це все запрограмував. Що, якщо ми могли б дати дизайнерові інструменти для створення власних умов чи дій?
Щоб програмісту не писати код для умов Is Ball Left Of Paddle та Is Ball Right Of Paddle, він може створити систему, в якій дизайнер записуватиме умови для перевірки цих значень. Тоді дані дерева рішень виглядатимуть так:
По суті це те саме, що і в першій таблиці, але рішення всередині себе мають свій власний код, трохи схожий на умовну частину if-оператора. На боці коду це зчитувалося б у другому стовпці для вузлів прийняття рішень, але замість пошуку конкретної умови для виконання (Is Ball Left Of Paddle) воно оцінює умовний вираз і повертає true або false відповідно. Це робиться за допомогою скриптової мови Lua чи Angelscript. За допомогою них розробник може приймати об'єкти у своїй грі (ball і paddle) та створювати змінні, які будуть доступні у сценарії (ball.position). Крім того, мова сценаріїв простіше, ніж C++. Він не потребує повної стадії компіляції, тому ідеально підходить для швидкого коригування ігрової логіки та дозволяє «некодерам» самим створювати потрібні функції.
У наведеному прикладі мова сценаріїв використовується лише з оцінки умовного висловлювання, але його можна використовувати й у дій. Наприклад, дані Move Paddle Right можуть стати оператором сценарію (ball.position.x += 10). Так, щоб дія також визначалася у скрипті, без потреби програмування Move Paddle Right.
Можна піти ще далі і повністю написати дерево рішень мовою сценаріїв. Це буде код у вигляді жорстко запрограмованих (hardcoded) умовних операторів, але вони будуть у зовнішніх файлах скрипта, тобто можуть бути змінені без перекомпіляції всієї програми. Найчастіше можна змінити файл сценарію прямо під час гри, щоб швидко протестувати різні реакції ІІ.
Реагування на події
Приклади вище ідеально підходять до Pong. Вони безперервно запускають цикл Sense/Think/Act та діють на основі останнього стану світу. Але в складніших іграх потрібно реагувати на окремі події, а не оцінювати все й одразу. Pong у разі вже невдалий приклад. Виберемо інший.
Уявіть шутер, де вороги нерухомі поки не виявлять гравця, після чого діють залежно від своєї спеціалізації: хтось побіжить вирішити, хтось атакуватиме здалеку. Це все ще базова система, що реагує — «якщо гравець помічений, то зроби що-небудь», — але її можна логічно розділити на подію Player Seen (гравець помічений) і реакцію (виберіть відповідь і виконайте її).
Це повертає нас до циклу Sense/Think/Act. Ми можемо накодувати Sense-частину, яка кожен кадр перевірятиме — чи бачить ІІ гравця. Якщо ні – нічого не відбувається, але якщо бачить, то створюється подія Player Seen. У коду буде окремий розділ, в якому говориться: «коли відбувається подія Player Seen, зроби», де відповідь, яка вам потрібна для звернення до частин Think і Act. Таким чином, ви налаштуєте реакції до події Player Seen: на «рішучого» персонажа ChargeAndAttack, а на снайпера HideAndSnipe. Ці зв'язки можна створити у файлі даних для швидкого редагування без необхідності заново компілювати. І тут також можна використовувати мову сценаріїв.
Ухвалення складних рішень
Хоча прості системи реакцій дуже дієві, буває багато ситуацій, коли їх недостатньо. Іноді потрібно приймати різні рішення, засновані на тому, що агент робить зараз, але представляти це за умову важко. Іноді існує занадто багато умов, щоб ефективно уявити їх у дереві рішень або скрипт. Іноді потрібно заздалегідь оцінювати, як зміниться ситуація, перш ніж приймати рішення про наступний крок. Для вирішення цих проблем потрібні складніші підходи.
Кінцевий автомат
Finite state machine або FSM (кінцевий автомат) - це спосіб сказати, що наш агент в даний час знаходиться в одному з кількох можливих станів, і що він може переходити з одного стану до іншого. Таких станів певна кількість – звідси й назва. Найкращий приклад із життя — дорожній світлофор. У різних місцях різні послідовності вогнів, але принцип той самий - кожен стан представляє щось (стій, йди і т.д.). Світлофор знаходиться тільки в одному стані в будь-який момент часу і переходить від одного до іншого на основі простих правил.
З NPC у іграх схожа історія. Для прикладу візьмемо варту з такими станами:
- Патрулюючий (Patrolling).
- Атакуючий (Attacking).
- Той, що тікає (Fleeing).
І такими умовами зміни його стану:
- Якщо вартовий бачить супротивника, він атакує.
- Якщо варта атакує, але більше не бачить противника, він повертається до патрулювання.
- Якщо варта атакує, але сильно поранений, він тікає.
Також можна написати if-оператори зі змінною-станом варти та різні перевірки: чи є поблизу ворог, який рівень здоров'я NPC і т. д. Додамо ще кілька станів:
- Бездіяльність (Idling) – між патрулями.
- Пошук (Searching) - коли помічений ворог зник.
- Просити про допомогу (Finding Help) - коли ворог помічений, але занадто сильний, щоб боротися з ним поодинці.
Вибір для кожного з них обмежений — наприклад, страж не піде шукати ворога, що втік, якщо у нього низьке здоров'я.
Зрештою величезний список «якщо , то », може стати занадто громіздким, тому слід формалізувати метод, який дозволить нам тримати в умі стани та переходи між станами. Щоб це зробити, візьмемо до уваги всі стани, і під кожним станом запишемо до списку всі переходи до інших станів, разом з необхідними для них умовами.
Це таблиця переходів станів – комплексний спосіб представлення FSM. Намалюємо діаграму та отримаємо повний огляд того, як змінюється поведінка NPC.
Діаграма відбиває суть прийняття рішень цього агента з урахуванням поточної ситуації. Причому кожна стрілка показує перехід між станами, якщо умова поруч із нею істинно.
Кожне оновлення ми перевіряємо стан агента, переглядаємо список переходів, і якщо умови для переходу виконані, він приймає новий стан. Наприклад, кожен кадр перевіряється чи закінчився 10-секундний таймер, і якщо так, то зі стану Idling варта переходить в Patrolling. Так само стан Attacking перевіряє здоров'я агента — якщо воно низьке, то він переходить у стан Fleeing.
Це обробка переходів між станами, але як щодо поведінки, пов'язаної із самими станами? Щодо реалізації фактичної поведінки для конкретного стану, зазвичай існує два типи «гака», де ми присвоюємо дії до FSM:
- Дії, що ми періодично виконуємо для поточного стану.
- Дії, які ми робимо під час переходу з одного стану в інший.
Приклади першого типу. Стан Patrolling кожен кадр переміщатиме агента за маршрутом патрулювання. Стан Attacking кожен кадр намагатиметься почати атаку або перейти в стан, коли це можливо.
Для другого типу розглянемо перехід «якщо ворог видно і ворог занадто сильний, перейти в стан Finding Help. Агент повинен вибрати, куди піти по допомогу, та зберегти цю інформацію, щоб стан Finding Help знав куди звернутися. Як тільки допомогу знайдено, агент переходить назад у стан Attacking. У цей момент він захоче розповісти союзникові про загрозу, тому може виникнути дія NotifyFriendOfThreat.
І знову ми можемо подивитися на цю систему через призму циклу Sense/Think/Act. Sense втілюється у даних, що використовуються логікою переходу. Think – переходами, доступними у кожному стані. А Act здійснюється діями, що здійснюються періодично в межах стану або переходах між станами.
Іноді безперервне опитування умов переходу може бути дорогим. Наприклад, якщо кожен агент буде виконувати складні обчислення кожен кадр, щоб визначити, чи бачить він ворогів і зрозуміти, чи можна переходити від стану Patrolling до Attacking - це займе багато часу процесора.
Важливі зміни у стані світу можна як події, які будуть оброблятися у міру їх появи. Замість того, щоб FSM кожен кадр перевіряв умову переходу «чи може мій агент бачити гравця?», можна налаштувати окрему систему, щоб виконувати перевірки рідше (наприклад, 5 разів на секунду). А результатом видавати Player Seen, коли перевірка відбувається.
Це передається до FSM, який тепер повинен перейти в умову Player Seen event received та відповідно відреагувати. Підсумкова поведінка однаково крім майже непомітної затримки перед відповіддю. Проте продуктивність стала кращою в результаті відділення частини Sense в окрему частину програми.
Hierarchical finite state machine
Однак працювати з великими FSM не завжди зручно. Якщо ми захочемо розширити стан атаки, замінивши його окремими MeleeAttacking (ближній бій) та RangedAttacking (далекий бій), нам доведеться змінити переходи з усіх інших станів, які ведуть до стану Attacking (поточні та майбутні).
Напевно, ви помітили, що в нашому прикладі багато дубльованих переходів. Більшість переходів у стані Idling ідентичні переходам у стані Patrolling. Добре не повторюватися, особливо якщо ми додамо більше схожих станів. Має сенс згрупувати Idling та Patrolling під загальним ярликом «небойові», де є лише один загальний набір переходів у бойові стани. Якщо ми представимо цей ярлик як стан, то Idling та Patrolling стануть підходами. Приклад використання окремої таблиці переходів для нового небойового стану:
Основні стани:
Стан поза бою:
І у формі діаграми:
Це та сама система, але з новим небойовим станом, який включає Idling і Patrolling. З кожним станом, що містить FSM з підсобами (а ці підстани, у свою чергу, містять власні FSM - і так далі скільки вам потрібно) ми отримуємо Hierarchical Finite State Machine або HFSM (ієрархічний кінцевий автомат). Згрупувавши небойовий стан, ми вирізали купу надлишкових переходів. Те саме ми можемо зробити для будь-яких нових станів із загальними переходами. Наприклад, якщо в майбутньому ми розширимо стан Attacking до станів MeleeAttacking and MissileAttacking, вони будуть підходами, що переходять між один одним на основі відстані до ворога та наявності боєприпасів. У результаті складні моделі поведінки та підмоделі поведінки можна уявити з мінімумом дубльованих переходів.
Дерево поведінки
З HFSM створюються складні комбінації поведінки простим способом. Тим не менш, є невелика складність, що прийняття рішень у вигляді правил переходу тісно пов'язане із поточним станом. І у багатьох іграх це саме те, що потрібно. А ретельне використання ієрархії станів може зменшити кількість повторів під час переходу. Але іноді потрібні правила, які працюють незалежно від того, в якому стані ви знаходитесь або які застосовуються майже в будь-яких станах. Наприклад, якщо здоров'я агента впало до 25%, ви захочете, щоб він тікав незалежно від того, чи був він у бою, байдикував чи розмовляв — вам доведеться додавати цю умову до кожного стану. А якщо ваш дизайнер пізніше захоче змінити поріг низького здоров'я з 25 до 10%, то цим знову доведеться займатися.
В ідеалі для цієї ситуації потрібна система, в якій рішення «у якому стані перебувати» знаходяться за межами самих станів, щоб вносити зміни лише в одному місці і не торкатися умов переходу. Тут з'являються дерева поведінки.
Існує кілька способів їх реалізації, але суть для всіх приблизно однакова і схожа на дерево рішень: алгоритм починається з «кореневого» вузла, а в дереві знаходяться вузли, що представляють рішення або дії. Щоправда, є кілька ключових відмінностей:
- Тепер вузли повертають одне із трьох значень: Succeeded (якщо робота виконана), Failed (якщо не можна запустити) або Running (якщо вона все ще запущена і немає кінцевого результату).
- Більше немає вузлів рішень щодо вибору між двома альтернативами. Замість них вузли Decorator, які мають один дочірній вузол. Якщо вони Succeed, виконують свій єдиний дочірній вузол.
- Вузли, що виконують дії, повертають значення Running для представлення дій, що виконуються.
Цей набір вузлів можна об'єднати для створення великої кількості складних моделей поведінки. Представимо HFSM вартового з попереднього прикладу у вигляді дерева поведінки:
З цією структурою не повинно бути явного переходу від станів Idling/Patrolling до стану Attacking чи будь-якого іншого. Якщо ворог видно, а здоров'я персонажа низьке, виконання зупиниться на вузлі Fleeing незалежно від того, який вузол він раніше виконував - Patrolling, Idling, Attacking або будь-який інший.
Дерева поведінки складні - є багато способів їх скласти, та й знайти правильне поєднання декораторів та складових вузлів може бути проблематично. Є також питання про те, як часто перевіряти дерево — ми хочемо проходити його кожну частину чи лише тоді, коли одна з умов змінилася? Як зберігати стан, що відноситься до вузлів - як дізнатися, коли ми були в стані Idling протягом 10 секунд або як дізнатися, які вузли виконували минулого разу, щоб правильно обробити послідовність?
Саме тому існує безліч реалізацій. Наприклад, у деяких системах вузли декоратора замінили вбудованими декораторами. Вони повторно оцінюють дерево за зміни умов декоратора, допомагають приєднатися до вузлів та забезпечують періодичні оновлення.
Utility-based system
Деякі ігри мають безліч різних механік. Бажано, щоб вони отримали всі переваги простих та загальних правил переходу, але не обов'язково у вигляді повного дерева поведінки. Замість того, щоб мати чіткий набір виборів або дерево можливих дій, простіше вивчити всі дії і вибрати найкраще в даний момент.
Utility-based system (система, заснована на корисності) якраз у цьому допоможе. Це система, де у агента є безліч дій, і він сам вибирає якесь виконати, ґрунтуючись на відносній корисності кожного. Де корисність — довільна міра того, наскільки важливим чи бажаним є виконання цієї дії для агента.
Розраховану корисність дії на основі поточного стану та середовища, агент може перевірити та вибрати найбільш відповідний інший стан у будь-який час. Це схоже на FSM, крім того, де переходи визначаються оцінкою для кожного потенційного стану, включаючи поточний. Зверніть увагу, що ми вибираємо найкориснішу дію для переходу (або залишаємося, якщо вже виконали її). Для більшої різноманітності це може бути виважений, але випадковий вибір із невеликого списку.
Система призначає довільний діапазон значень корисності - наприклад, від 0 (цілком небажано) до 100 (цілком бажано). Кожна дія має ряд параметрів, що впливають на обчислення цього значення. Повертаючись до нашого прикладу з вартовим:
Переходи між діями неоднозначні — будь-який стан може йти за будь-яким іншим. Пріоритети дій перебувають у значеннях корисності, що повертаються. Якщо ворог видно, і цей ворог сильний, а здоров'я персонажа низьке, і Fleeing, і FindingHelp повернуть високі ненульові значення. При цьому FindingHelp завжди буде вищим. Аналогічним чином, небойові дії ніколи не повертають більше 50, тому вони завжди будуть нижчими від бойових. Потрібно враховувати це при створенні дій та обчисленні їхньої корисності.
У прикладі дії повертають або фіксоване постійне значення, або одне з двох фіксованих значень. Більш реалістична система передбачає повернення оцінки безперервного діапазону значень. Наприклад, дія Fleeing повертає вищі значення корисності, якщо здоров'я агента низька, а дія Attacking повертає нижчі, якщо ворог занадто сильний. Через це дія Fleeing має пріоритет над Attacking у будь-якій ситуації, коли агент відчуває, що у нього недостатньо здоров'я для перемоги над супротивником. Це дозволяє змінювати пріоритети дій на основі будь-якої кількості критеріїв, що робить такий підхід більш гнучким та варіативним, ніж дерево поведінки чи FSM.
Кожна дія має багато умов розрахунку програми. Їх можна написати мовою сценаріїв або у вигляді серії математичних формул. The Sims, яка моделює розпорядок дня персонажа, додають додатковий рівень обчислень — агент отримує ряд «мотивацій», що впливають на оцінки корисності. Якщо персонаж голодний, то згодом він голодуватиме ще сильніше, і результат корисності дії EatFood зростатиме доти, поки персонаж не виконає його, знизивши рівень голоду, і повернувши значення EatFood рівним нулю.
Ідея вибору дій на основі системи оцінок досить проста, тому Utility-based system можна використовувати як частину процесів прийняття рішень ІІ, а не як їхню повну заміну. Дерево рішень може запросити оцінку корисності двох дочірніх вузлів та вибрати вищу. Аналогічно дерево поведінки може мати складовий вузол Utility для оцінки корисності дій, щоб вирішити, який дочірній елемент виконати.
Рух та навігація
У попередніх прикладах у нас була платформа, яку ми переміщали ліворуч чи праворуч, та страж, який патрулював чи атакував. Але як саме ми обробляємо рух агента протягом певного періоду часу? Як ми встановлюємо швидкість, як ми уникаємо перешкод, і як ми плануємо маршрут, якщо дістатися місця призначення складніше, ніж просто рухатися прямою? Давайте розглянемо.
Управління
На початковому етапі вважатимемо, кожен агент має значення швидкості, яке включає у собі, як швидко він рухається й у якому напрямі. Вона може бути виміряна в метрах за секунду, кілометрах за годину, пікселів за секунду і т. д. Згадуючи цикл Sense/Think/Act, ми можемо припустити, що частина Think вибирає швидкість, а частина Act застосовує цю швидкість до агента. Зазвичай в іграх є фізична система, яка виконує це завдання за вас, вивчаючи значення швидкості кожного об'єкта та регулюючи його. Тому можна залишити ІІ з одним завданням – вирішити, яку швидкість повинен мати агент. Якщо відомо, де агент повинен бути, потрібно перемістити його в правильному напрямку з встановленою швидкістю. Дуже тривіальне рівняння:
desired_travel = destination_position – agent_position
Уявіть 2D-світ. Агент знаходиться в точці (-2,-2), пункт призначення десь на північному сході в точці (30, 20), а необхідний шлях для агента, щоб опинитися там (32, 22). Припустимо, ці позиції вимірюються за метри — якщо прийняти швидкість агента за 5 метрів за секунду, то ми масштабуватимемо наш вектор переміщення і отримаємо швидкість приблизно (4.12, 2.83). З цими параметрами агент прибув до місця призначення майже через 8 секунд.
Перерахувати значення можна у будь-який час. Якщо агент був на півдорозі до мети, переміщення було б половиною довжини, але оскільки максимальна швидкість агента 5 м/с (ми це вирішили вище), швидкість буде однаковою. Це також працює для цілей, що рухаються, дозволяючи агенту вносити невеликі зміни в міру їх переміщення.
Але ми хочемо більше варіативності - наприклад, повільно наростити швидкість, щоб симулювати персонажа, що рухається зі стоячого стану і переходить до бігу. Те саме можна зробити в кінці перед зупинкою. Ці фічі відомі як steering behaviours, кожне з яких має конкретні імена: Seek (пошук), Flee (втеча), Arrival (прибуття) і т.д. Ідея полягає в тому, що сили прискорення можуть бути застосовані до швидкості агента на основі порівняння положення агента та поточної швидкості з пунктом призначення, щоб використовувати різні способи переміщення до мети.
Кожна поведінка має трохи іншу мету. Seek та Arrival – це способи переміщення агента до точки призначення. Obstacle Avoidance (уникнення перешкод) та Separation (поділ) коригують рух агента, щоб оминати перешкоди на шляху до мети. Alignment (узгодження) та Cohesion (зв'язок) тримають агентів при переміщенні разом. Будь-яке число різних стереонгів може бути підсумовано для отримання одного вектора шляху з урахуванням всіх факторів. Агент, який використовує поведінки Arrival, Separation та Obstacle Avoidance, щоб триматися подалі від стін та інших агентів. Цей підхід добре працює у відкритих локаціях без зайвих деталей.
У складніших умовах, складання різних поведінок працює гірше — наприклад, агент може застрягти у стіні через конфлікт Arrival і Obstacle Avoidance. Тому потрібно розглядати варіанти, які складніші, ніж просто додавання всіх значень. Спосіб такий: замість складання результатів кожної поведінки, можна розглянути рух у різних напрямках та вибрати найкращий варіант.
Однак у складному середовищі з глухими кутами та вибором, в який бік йти, нам знадобиться щось ще більш просунуте.
Пошук шляху
Steering behaviours відмінно підходить для простого руху на відкритій місцевості (футбольне поле або арена), де дістатися від А до Б - це прямий шлях з невеликими відхиленнями повз перешкоди. Для складних маршрутів нам потрібен шляхпоходження (пошук шляху), який є способом вивчення миру і прийняття рішення про маршрут через нього.
Найпростіший - накласти сітку на кожен квадрат поряд з агентом і оцінити в яких дозволено рухатися. Якщо один із них є пунктом призначення, то слідуйте з нього за маршрутом від кожного квадрата до попереднього, доки не дійдете до початку. Це і є маршрут. В іншому випадку повторюйте процес із найближчими іншими квадратами, поки не знайдете місце призначення або не закінчаться квадрати (це означає, що немає можливого маршруту). Це те, що формально відоме як Breadth-First Search або BFS (алгоритм пошуку завширшки). На кожному кроці він дивиться у всіх напрямках (тому breadth, "ширина"). Простір пошуку схожий на хвильовий фронт, який переміщається, доки досягне шукане місце — область пошуку розширюється кожному кроці до того часу, доки у неї потрапить кінцева точка, після чого можна відстежити шлях до початку.
У результаті ви отримаєте список квадратів, якими складається потрібний маршрут. Це і є шлях (звідси, pathfinding) — список місць, які агент відвідає, прямуючи до пункту призначення.
Враховуючи, що ми знаємо положення кожного квадрата у світі, можна використовувати steering behaviours, щоб рухатися шляхом — від вузла 1 до вузла 2, потім від вузла 2 до вузла 3 і так далі. Найпростіший варіант – попрямувати до центру наступного квадрата, але ще краще – зупинитися на середині грані між поточним квадратом та наступним. Через це агент зможе зрізати кути на крутих поворотах.
У алгоритму BFS є й мінуси — він досліджує стільки ж квадратів у «неправильному» напрямі, як у «правильному». Тут з'являється складніший алгоритм під назвою A * (A star). Він працює також, але замість сліпого вивчення квадратів-сусідів (потім сусідів сусідів, потім сусідів сусідів сусідів і так далі), він збирає вузли в список і сортує їх так, що наступний досліджуваний вузол завжди той, що приведе до найкоротшого маршруту. Вузли сортуються на основі евристики, яка враховує дві речі – «вартість» гіпотетичного маршруту до потрібного квадрата (включаючи будь-які витрати на переміщення) та оцінку того, наскільки далеко цей квадрат від місця призначення (зміщуючи пошук у правильному напрямку).
У цьому прикладі показано, що агент досліджує по одному квадрату за раз, щоразу вибираючи сусідній, який є найперспективнішим. Отриманий шлях такий самий, як і за BFS, але в процесі було розглянуто менше квадратів — а це має велике значення для продуктивності гри.
Рух без сітки
Але більшість ігор не викладено на сітці, і найчастіше її неможливо зробити без шкоди реалістичності. Потрібні компроміси. Яких розмірів мають бути квадрати? Занадто великими — і вони не зможуть правильно уявити невеликі коридори чи повороти, надто маленькими — буде надто багато квадратів для пошуку, який забере купу часу.
Перше, що треба зрозуміти, сітка дає нам граф зв'язаних вузлів. Алгоритми A* та BFS фактично працюють на графіках і взагалі не дбають про нашу сітку. Ми могли б поставити вузли в будь-яких місцях ігрового світу: за наявності зв'язку між будь-якими двома з'єднаними вузлами, а також між початковою та кінцевою точкою та принаймні одним із вузлів — алгоритм працюватиме також добре, як і раніше. Часто це називають системою колійних точок (waypoint), тому що кожен вузол є значущою позицією у світі, яка може бути частиною будь-якої кількості гіпотетичних шляхів.
Приклад 1: вузол у кожному квадраті. Пошук починається з вузла, де знаходиться агент, і закінчується у вузлі потрібного квадрата.
Приклад 2: менший набір вузлів (колійних точок). Пошук починається у квадраті з агентом, проходить через необхідну кількість вузлів, а потім продовжується до пункту призначення.
Це цілком гнучка та потужна система. Але потрібна деяка обережність у рішеннях, де і як помістити waypoint, інакше агенти можуть просто не побачити найближчу точку та не зможуть розпочати шлях. Було б простіше, якщо ми могли автоматично розставити дорожні точки на основі геометрії світу.
Тут утворюється navigation mesh чи navmesh (навігаційна сітка). Це зазвичай 2D-сітка трикутників, яка накладається на геометрію світу - скрізь, де агенту можна ходити. Кожен із трикутників у сітці стає вузлом у графі та має до трьох суміжних трикутників, які стають сусідніми вузлами у графі.
Ця картина є прикладом з движка Unity – він проаналізував геометрію у світі та створив navmesh (на скріншоті світло-блакитним кольором). Кожен полігон в navmesh — це область, де агент може стояти чи переміщатися з одного полігону до іншого полігон. У цьому прикладі полігони менші за поверхи, на яких вони розташовані — зроблено для того, щоб врахувати розміри агента, які виходитимуть за межі його номінального положення.
Ми можемо шукати маршрут через цю сітку, використовуючи алгоритм A*. Це дасть нам практично ідеальний маршрут у світі, який враховує всю геометрію і при цьому не потребує зайвих вузлів та створення дорожніх точок.
Pathfinding — надто велика тема, про яку мало одного розділу статті. Якщо хочете вивчити її детальніше, то в цьому допоможе .
планування
Ми переконалися з pathfinding, що іноді недостатньо просто вибрати напрямок і рухатися - ми повинні вибрати маршрут і зробити кілька поворотів, щоб дістатися потрібного місця призначення. Ми можемо узагальнити цю ідею: досягнення мети це не просто наступний крок, а ціла послідовність, де іноді потрібно заглянути вперед на кілька кроків, щоб дізнатися, яким має бути перший. Це називається плануванням. Pathfinding можна як одне з кількох доповнень планування. З погляду нашого циклу Sense/Think/Act це те, де частина Think планує кілька частин Act на майбутнє.
Розберемо з прикладу настільної гри Magic: The Gathering. Ми ходимо першими з таким набором карток на руках:
- Swamp – дає 1 чорну ману (карта землі).
- Forest – дає 1 зелену ману (карта землі).
- Fugitive Wizard – вимагає 1 синю ману для призову.
- Elvish Mystic – вимагає 1 зелену ману для призову.
Три карти, що залишилися, ігноруємо, щоб було простіше. За правилами гравцю дозволено грати 1 карту землі за хід, він може «тапнути» цю карту, щоб витягти з неї ману, а потім використовувати заклинання (включаючи виклик істоти) за кількістю мани. У цій ситуації гравець-людина знає, що потрібно грати Forest, "топнути" 1 зелену ману, а потім викликати Elvish Mystic. Але як про це здогадатися ігровому ІІ?
Просте планування
Тривіальний підхід — пробувати кожну дію по черзі, доки не залишиться потрібних. Дивлячись на карти, ІІ бачить, що може зіграти Swamp. І грає його. Чи залишилися інші дії на цьому ході? Він не може викликати ні Elvish Mystic, ні Fugitive Wizard, оскільки для їхнього заклику потрібна відповідно зелена і синя мана, а Swamp дає лише чорну ману. І він уже не зможе грати Forest, бо вже зіграв Swamp. Таким чином, ігровий ІІ сходив за правилами, але зробив це погано. Можна покращити.
Планування може знайти список дій, які призводять до гри в бажаний стан. Також, як кожна квадрат на шляху мав сусідів (в pathfinding), кожна дія в плані теж має сусідів чи наступників. Ми можемо шукати ці дії та наступні дії, доки не досягнемо бажаного стану.
У нашому прикладі бажаний результат «викликати істоту, якщо це можливо». На початку ходу ми бачимо лише дві можливі дії, дозволені правилами гри:
1. Зіграти Swamp (результат: Swamp у грі)
2. Зіграти Forest (результат: Forest у грі)
Кожна прийнята дія може призвести до подальших дій та закрити інші, знову ж таки залежно від правил гри. Уявіть, що ми зіграли Swamp - це видалить Swamp як наступний крок (ми його вже зіграли), також це видалить і Forest (бо за правилами можна зіграти одну карту землі за хід). Після цього ІІ додає як наступний крок - отримання 1 чорної мани, тому що інших варіантів немає. Якщо він піде далі і вибере Tap the Swamp, то отримає одну одиницю чорної мани і нічого з нею не зможе зробити.
1. Зіграти Swamp (результат: Swamp у грі)
1.1 "Тапнути" Swamp (результат: Swamp "тапнутий", +1 одиниця чорної мани)
Немає доступних дій – КІНЕЦЬ
2. Зіграти Forest (результат: Forest у грі)
Список дій вийшов коротким, ми зайшли в глухий кут. Повторюємо процес для наступної дії. Ми граємо Forest, відкриваємо дію «отримати одну зелену ману», яка у свою чергу відкриє третю дію – заклик Elvish Mystic.
1. Зіграти Swamp (результат: Swamp у грі)
1.1 "Тапнути" Swamp (результат: Swamp "тапнутий", +1 одиниця чорної мани)
Немає доступних дій – КІНЕЦЬ
2. Зіграти Forest (результат: Forest у грі)
2.1 «Тапнути» Forest (результат: Forest «тапнутий», +1 одиниця зеленої мани)
2.1.1 Закликати Elvish Mystic (результат: Elvish Mystic у грі -1 одиниця зеленої мани)
Немає доступних дій – КІНЕЦЬ
Нарешті, ми вивчили всі можливі дії і знайшли план, який закликає істоту.
Це дуже спрощений приклад. Бажано вибирати найкращий можливий план, а не будь-який, який відповідає якимось критеріям. Зазвичай, можна оцінити потенційні плани з урахуванням кінцевого результату чи сукупної вигоди від виконання. Можна нарахувати собі 1 очко за гру карти землі та 3 очки за виклик істоти. Грати Swamp було б планом, що дає одне очко. А зіграти Forest → Tap the Forest → закликати Elvish Mystic відразу дасть 1 очки.
Ось так працює планування Magic: The Gathering, але за тією ж логікою це застосовується і в інших ситуаціях. Наприклад, перемістити пішака, щоб звільнити місце для ходу слона в шахах. Або сховатися за стіною, щоб безпечно стріляти в XCOM так. Загалом ви зрозуміли суть.
Поліпшене планування
Іноді буває надто багато потенційних дій, щоб розглядати кожен можливий варіант. Повертаючись, наприклад, з Magic: The Gathering: припустимо, що у грі і на вас на руках по кілька карт землі та істот — кількість можливих комбінацій ходів може обчислюватися десятками. Є кілька розв'язків проблеми.
Перший спосіб - backwards chaining (зворотне формування ланцюга). Замість перебору всіх комбінацій краще почати з підсумкового результату і спробувати знайти прямий маршрут. Замість шляху від кореня дерева до певного аркуша, ми рухаємося у зворотному напрямку – від аркуша до кореня. Цей спосіб простіше та швидше.
Якщо у противника 1 одиниця здоров'я, можна знайти план «завдати 1 або більше одиниць шкоди». Щоб досягти цього, потрібно виконати ряд умов:
1. Втрата може завдати заклинання — воно має бути в руці.
2. Щоб розіграти заклинання – потрібна мана.
3. Щоб отримати ману, потрібно розіграти карту землі.
4. Щоб розіграти карту землі, потрібно мати її в руці.
Інший спосіб - best-first search (найкращий перший пошук). Замість перебору всіх шляхів, ми вибираємо найбільш вдалий. Найчастіше цей спосіб дає оптимальний план без зайвих витрат за пошуки. A* — це форма найкращого першого пошуку — досліджуючи найперспективніші маршрути від початку, він може знайти найкращий шлях без необхідності перевіряти інші варіанти.
Цікавим та все більш популярним варіантом best-first search є Monte Carlo Tree Search. Замість вгадування, які плани кращі за інших при виборі кожної наступної дії, алгоритм вибирає випадкових наступників на кожному кроці, поки не досягне кінця (коли план призвів до перемоги або поразки). Потім підсумковий результат використовується підвищення чи зниження оцінки «ваги» попередніх варіантів. Повторюючи цей процес кілька разів поспіль, алгоритм дає хорошу оцінку того, який наступний крок кращий, навіть якщо ситуація зміниться (якщо противник вживе заходів, щоб завадити гравцю).
У розповіді про планування в іграх не обійдеться без Goal-Oriented Action Planning або GOAP (цілеспрямоване планування дій). Це метод, що широко використовується і обговорюється, але крім декількох відмінних деталей це, по суті, метод backwards chaining, про який ми говорили раніше. Якщо завдання було «знищити гравця», і гравець перебуває за укриттям, план може бути таким: знищ гранатою → дістань її → кинь.
Зазвичай є кілька цілей, кожна зі своїм пріоритетом. Якщо ціль з найвищим пріоритетом не може бути виконана (жодна комбінація дій не створює план «знищити гравця», тому що гравця не видно), ІІ повернеться до цілей із нижчим пріоритетом.
Навчання та адаптація
Ми вже говорили, що ігровий ІІ зазвичай не використовує машинне навчання, тому що це не підходить для управління агентами у реальному часі. Але це не означає, що не можна щось запозичити з цієї галузі. Ми хочемо такого супротивника в шутері, у якого можна чогось навчитися. Наприклад, дізнатися про найкращі позиції на карті. Або противника у файтингу, який блокував би комбо-прийоми, що часто використовуються гравцем, мотивуючи використовувати інші. Отже, машинне навчання в таких ситуаціях може бути дуже корисним.
Статистика та ймовірності
Перш ніж ми перейдемо до складних прикладів, прикинемо, як далеко ми можемо зайти, взявши кілька простих вимірів та використовуючи їх для прийняття рішень. Наприклад, стратегія в реальному часі — як нам визначити, чи зможе гравець розпочати атаку в перші кілька хвилин гри та яку оборону проти цього приготувати? Ми можемо вивчити минулий досвід гравця, щоб зрозуміти, якою може бути майбутня реакція. Почнемо з того, що ми не маємо таких вихідних даних, але ми їх можемо зібрати — щоразу, коли ІІ грає проти людини, вона може записувати час першої атаки. Через кілька сесій ми отримаємо середнє значення часу, через яке гравець атакуватиме у майбутньому.
Середні значення мають і проблему: якщо гравець 20 разів «вирішив», а 20 разів грав повільно, то потрібні значення будуть десь у середині, а це нічого корисного нам не дасть. Одним із рішень є обмеження вхідних даних – можна враховувати останні 20 штук.
Аналогічний підхід використовується при оцінці ймовірності певних дій, припускаючи, що попередні переваги гравця будуть такими ж у майбутньому. Якщо гравець атакує нас п'ять разів фаєрболом, двічі блискавкою і один раз врукопашну, очевидно, що він віддає перевагу фаєрболу. Екстраполуємо та побачимо ймовірність використання різної зброї: фаєрбол=62,5%, блискавка=25% та рукопашна=12,5%. Нашому ігровому ІІ потрібно підготуватися до захисту від вогню.
Ще один цікавий метод — використовувати Naive Bayes Classifier (наївний класифікатор Байєса) для вивчення великих обсягів вхідних даних і класифікувати ситуацію, щоб ІІ реагував належним чином. Байєсівські класифікатори найбільш відомі за використання у фільтрах спаму електронної пошти. Там вони досліджують слова, порівнюють їх з тим, де з'являлися ці слова раніше (у спамі чи ні), і роблять висновки про вхідні листи. Ми можемо зробити те саме навіть з меншою кількістю вхідних даних. На основі всієї корисної інформації, яку бачить ІІ (наприклад, які ворожі юніти створені, або які заклинання вони використовують, або які технології вони досліджували), та підсумкового результату (війна чи мир, «вирішувати» чи оборонятися тощо) — ми виберемо потрібну поведінку ІІ.
Усіх цих способів навчання достатньо, але бажано використовувати їх на основі даних із тестування. ІІ навчиться адаптуватися до різних стратегій, які використовували ваші плейтестери. ІІ, який адаптується до гравця після релізу, може стати занадто передбачуваним або, навпаки, занадто складним для перемоги.
Адаптація на основі значень
Враховуючи наповнення нашого ігрового світу та правил, ми можемо змінити набір значень, які впливають на прийняття рішень, а не просто використовувати вхідні дані. Робимо так:
- Нехай ІІ збирає дані про стан миру та ключові події під час гри (як зазначено вище).
- Змінимо кілька важливих значень (value) з урахуванням цих даних.
- Реалізуємо свої рішення, що ґрунтуються на обробці або оцінці цих значень.
Наприклад, агент має кілька кімнат для вибору на карті шутера від першої особи. Кожна кімната має своє значення, яке визначає наскільки вона бажана для відвідування. ІІ випадково вибирає в яку кімнату йти, ґрунтуючись на значенні value. Потім агент запам'ятовує, в якій кімнаті його вбили, і зменшує її значення (ймовірність, що він туди повернеться). Аналогічно для зворотної ситуації - якщо агент знищує багато противників, то значення кімнати збільшується.
Марківська модель
Що, якщо ми використовуємо зібрані дані для прогнозування? Якщо запам'ятати кожну кімнату, в якій бачимо гравця протягом певного періоду часу, ми передбачатимемо яку кімнату гравець може перейти. Відстеживши та записавши переміщення гравця по кімнатах (values), ми можемо прогнозувати їх.
Візьмемо три кімнати: червону, зелену та синю. А також спостереження, які ми записали під час перегляду ігрової сесії:
Кількість спостережень за кожною кімнатою майже рівна — де зробити гарне місце для засідки ми й досі не знаємо. Збір статистики також ускладнюється респауном гравців, які поступово з'являються по всій карті. Але дані про наступну кімнату, в яку вони входять після появи на карті, вже корисні.
Видно, що зелена кімната влаштовує гравців — більшість людей із червоної переходять до неї, 50% яких залишається там і надалі. Синя кімната навпаки не користується популярністю, в неї майже не ходять, а якщо ходять, то не затримуються.
Але дані говорять нам дещо важливіше — коли гравець перебуває в синій кімнаті, то наступна кімната, в якій ми його, швидше за все, побачимо буде червоною, а не зеленою. Незважаючи на те, що зелена кімната популярніша за червону, ситуація змінюється, якщо гравець знаходиться в синій. Наступний стан (тобто кімната, до якої гравець перейде) залежить від попереднього стану (тобто кімнати, де гравець перебуває зараз). Через дослідження залежностей ми робитимемо прогнози точніше, ніж якби просто підраховували спостереження незалежно друг від друга.
Передбачення майбутнього стану на основі даних минулого стану називається марківською моделлю (Markov model), а такі приклади (з кімнатами) називають марківськими ланцюгами. Оскільки моделі є ймовірністю змін між послідовними станами, візуально вони відображаються у вигляді FSM з ймовірністю біля кожного переходу. Раніше ми використовували FSM для представлення поведінкового стану, в якому був агент, але ця концепція поширюється на будь-який стан, незалежно від того, пов'язано це з агентом чи ні. У цьому випадку стану представляють кімнату, яку займає агент:
Це простий варіант уявлення відносної ймовірності змін станів, що дає ІІ певну можливість передбачати такий стан. Можна передбачати кілька кроків уперед.
Якщо гравець у зеленій кімнаті, то є 50% шанс, що він там і залишиться при наступному спостереженні. Але якою є ймовірність, що він все ще буде там навіть після? Є не тільки шанс, що гравець залишився у зеленій кімнаті після двох спостережень, а й шанс, що він пішов та повернувся. Ось нова таблиця з урахуванням нових даних:
З неї видно, що шанс побачити гравця в зеленій кімнаті після двох спостережень дорівнюватиме 51% - 21%, що він прийде з червоної кімнати, 5% з них, що гравець відвідає синю кімнату між ними, і 25%, що гравець взагалі не піде із зеленої кімнати.
Таблиця – просто наочний інструмент – процедура вимагає лише множення ймовірностей на кожному кроці. Це означає, що ви можете заглянути далеко в майбутнє з однією поправкою: ми припускаємо, що шанс увійти до кімнати залежить від поточної кімнати. Це називається марківською властивістю (Markov Property) – майбутній стан залежить лише від сьогодення. Але це не повністю точно. Гравці можуть змінювати рішення в залежності від інших факторів: рівень здоров'я чи кількість боєприпасів. Оскільки ми не фіксуємо ці значення, наші прогнози будуть менш точними.
N-грамів
А що щодо прикладу з файтингом та передбаченням комбо-прийомів гравця? Теж саме! Але замість одного стану чи події, ми досліджуватимемо цілі послідовності, з яких складається комбо-удар.
Один із способів зробити це — зберегти кожне введення (наприклад, Kick, Punch або Block) у буфері та записати весь буфер у вигляді події. Отже, гравець неодноразово натискає Kick, Kick, Punch, щоб використовувати атаку SuperDeathFist, система ІІ зберігає всі введення в буфері і запам'ятовує останні три, які використовуються на кожному кроці.
(Жирним виділено рядки, коли гравець запускає атаку SuperDeathFist.)
ІІ побачить всі варіанти, коли гравець вибрав Kick, слідом за іншим Kick, а потім помітити, що наступне введення завжди Punch. Це дозволить агенту спрогнозувати комбо прийом SuperDeathFist і заблокувати його, якщо це можливо.
Ці послідовності подій називаються N-грамами (N-grams), де N - кількість елементів, що зберігаються. У попередньому прикладі це була 3-грама (триграма), що означає: перші два записи використовуються для прогнозування третього. Відповідно в 5-грамі перші чотири записи пророкують п'яту і так далі.
Розробнику потрібно ретельно вибирати розмір N-грам. Менше число N вимагає менше пам'яті, але зберігає меншу історію. Наприклад, 2-грама (біграма) записуватиме Kick, Kick або Kick, Punch, але не зможе зберігати Kick, Kick, Punch, тому ІІ не відреагує на комбо SuperDeathFist.
З іншого боку, великі числа вимагають більше пам'яті та ІІ буде складніше навчитися, оскільки з'явиться набагато більше можливих варіантів. Якщо у вас було три можливі введення Kick, Punch або Block, а ми використали 10-граму, то вийде близько 60 тисяч різних варіантів.
Модель біграми це простий марківський ланцюг – кожна пара «минулий стан/поточний стан» є біграмою, і ви можете передбачити другий стан на основі першого. 3-грама та більші N-грами також можна розглядати як марківські ланцюги, де всі елементи (крім останнього в N-грамі) разом утворюють перший стан, а останній елемент - другий. Приклад з файтинг показує шанс переходу від стану Kick і Kick до стану Kick і Punch. Розглядаючи кілька записів вхідної історії як одну одиницю, ми, по суті, перетворюємо вхідну послідовність частину цілого стану. Це дає нам марківську властивість, що дозволяє використовувати марківські ланцюги для прогнозування наступного введення та вгадати, який комбохід буде наступним.
Висновок
Ми поговорили про найбільш поширені інструменти та підходи у розробці штучного інтелекту. А також розібрали ситуації, в яких їх потрібно застосовувати та де вони особливо корисні.
Цього має бути достатньо для розуміння базових речей у ігровому ІІ. Але, звичайно, це далеко не всі методи. До менш популярних, але не менш ефективних відносяться:
- алгоритми оптимізації, включаючи сходження по горбах, градієнтний спуск та генетичні алгоритми
- змагальні алгоритми пошуку/планування (minimax та alpha-beta pruning)
- методи класифікації (перцептрони, нейронні мережі та машини опорних векторів)
- системи для обробки сприйняття та пам'яті агентів
- архітектурні підходи до ІІ (гібридні системи, підмножина архітектур та інші способи накладання систем ІІ)
- інструменти анімації (планування та узгодження руху)
- фактори продуктивності (рівень деталізації, алгоритми anytime, і timeslicing)
Інтернет-ресурси на тему:
1. На GameDev.net є , а також .
2. містить безліч презентацій та статей щодо широкого спектру пов'язаних з розробкою ігрового ІІ.
3. включає топики з саміту GDC AI, багато з яких доступні безкоштовно.
4. Корисні матеріали також можна знайти на сайті .
5. Томмі Томпсон, дослідник ІІ та розробник ігор, робить ролики на YouTube-каналі з поясненням та вивченням ІІ в комерційних іграх.
Книги на тему:
1. Серія книг Game AI Pro є збірниками коротких статей, які пояснюють, як реалізувати конкретні функції або як вирішувати конкретні проблеми.
2. Серія AI Game Programming Wisdom – попередник серії Game AI Pro. В ній старіші методи, але майже всі актуальні навіть сьогодні.
3. — це один із базових текстів для всіх бажаючих розібратися у спільній галузі штучного інтелекту. Це книга не про ігрову розробку — вона навчає базових засад ІІ.
Джерело: habr.com