AI монстрів і пошук шляху за допомогою теплових карт

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

image


Дисклеймер
Відразу скажу, що це досить відомий метод: він використовувався для ІІ супротивників в іграх (наприклад, brogue, РТС-ботів, забезпечення руху частинок, і багато чого ще. Нижче я буду обговорювати рогалик, тобто припустимо, що світ складається з дискретних квадратних плиток і кожен об'єкт знаходиться хоча б на одному з них, [отя в принципі те ж саме можна зробити з будь топологією світу, яка ізоморфна (зв'язного) графу. Картинки запозичені з цієї статті roguebasin.com
Зомбі
Щоб пояснити, як працюють теплові карти, я для початку створю самого простого можливого монстра – зомбі. Він повинен просто гнатися за гравцем, не відволікаючись на увесь інший світ, а опинившись поруч – кидатися в рукопашну. Життя нам спростить ще й той факт, що в рогаликах ближня атака і переміщення традиційно виконуються однією командою, так що насправді зомбі робить рівно одну річ: прет найкоротшим шляхом у напрямку гравця. Весь ШІ, відповідно, зводиться до пошуку цього самого найкоротшого шляху.
Для пошуку шляху нам знадобиться двовимірний масив розміром з мапу, кожна комірка якого містить відстань від цього тайла до гравця. Нехай значення в тайлі, в якому знаходиться гравець, дорівнює нулю; в сусідніх тайлах воно дорівнює одиниці, в наступному ряду двійці і так далі. У загальному випадку, значення тайла на одиницю більше, ніж найменше значення серед його сусідів. Непрохідні тайли ігноруються, тобто туди ставиться None або яке-небудь безмежно велике число. Повинно вийти приблизно ось так:

image

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



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

Множинні атрактори


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



Виникає очевидна проблема: що, якщо додати в одну гру і зомбі, і гоблінів? Вони мають різну поведінку і вже не можуть використовувати одну і ту ж карту. А якщо завести по тепловій карті для кожного типу ІІ, перевага у швидкості може швидко зійти нанівець. Рішення полягає в тому, щоб створити по карті для кожного типу аттрактора. Кожен ІЇ тоді буде брати значення всіх його цікавлять карт і вибирати наступний крок на підставі зваженої суми. Яким чином «Карта з гравцем», «Карта з золотом» і «Карта зі стрілами» швидше, ніж «Карта для зомбі», «Карта для гоблінів» і «Карта для кентаврів»? Вся справа в частоті обрахунку. Картку потрібно оновлювати тільки тоді, коли змінюються її атрактори. Як правило, гравець або рухається, або підбирає з підлоги золото, або стріляє в монстра, але не всі одночасно. Тобто за хід зазвичай оновлюється всього одна картка, а в разі окремих карт з ІІ довелося б перераховувати всі відразу.

Розширюємо ІІ


Гобліну потрібно думати ще про одну проблему, яка не хвилювала зомбі. Мається на увазі, що він хоче зібрати золото, але теплова карта може наказати йому тільки підійти до нього. На щастя, штучний інтелект не обмежується однією тільки карткою. Перевірка напрямки руху відбувається вже після того, як монстр з'ясував, що в поточній локації йому робити, власне, нічого. Можна збільшити швидкодію, перевіряючи можливість інших дій тільки в локальних мінімумах карти, але це зазвичай передчасна оптимізація: багато клітини, на яких монстрові насправді є чим зайнятися, локальними мінімумами не є.
Ще один мінус описаної імплементації: зомбі буде битися об гравця, навіть якщо у нього залишився 1 HP, а вмираючи від голоду гоблін не припинить збирати золото. Окей, для цих двох істот таке швидше норма, але взагалі-то у монстра має бути кілька типів поведінки в залежності від обставин. Як правило, тут нам допоможе кінцевий автомат. Особливість у разі теплових карт тільки в тому, що для кожного стану автомата заданий свій вектор ваг карт. Тяжелораненный противник буде швидше відступати від гравця, тобто множити значення відповідної карти на щось негативне, але з усіх ніг бігти до найближчої лечилке, віддаючи велику вагу значенням з карти зіль. Голодний буде таким же чином прагнути до їжі, намагатися не потрапляти на очі гравцеві і зовсім ігнорувати лежать на підлозі боєприпаси.

Підводні камені


Таких особисто я знайшов три. По-перше, шляхів з точки A в точку B може бути більше одного. Для ІІ-це не проблема: монстри, що йдуть до гравця різними шляхами, трохи менше тицяють в очі детермінованістю своєї поведінки і навіть виглядають трохи розумніший, ніж вони є насправді. Але в статті на roguebasin пропонується з допомогою тих же карт показувати шлях від гравця до курсору при навігації за допомогою мишки або стрільби. Це дуже погана ідея: шлях, який таким чином відображається на екрані, може бути, і оптимальний, але не зобов'язаний співпадати з шляхом, яким в ту ж точку відправиться персонаж. Для стрільби або заклинань ця проблема ще серйозніше, тому що карти не забороняють обходити кути і рухатися по кривій (якщо це дозволяє топологія карти). А стріляти за кут повинна тільки покладена на бік мортира з відомого анекдоту.
По-друге, цей метод ігнорує поле зору монстрів. Зомбі цілком здатний гнатися за гравцем через половину карти, навіть якщо він його ні разу не бачив і не мав би взагалі знати про його існування. Можна припустити, що якщо гравець бачить монстра – то монстр його бачить теж (з поправкою на скритність). Тоді теплова карта оновлюється лише в межах поля зору гравця і тайли за його межами ігноруються так само, як непрохідні. Це милицю, але, на жаль, чесне поле зору для всіх NPC на коліні не обсчитаешь.
По-третє, кожен супротивник діє сам по собі. Створивши карту з монстрами в якості атракторів, можна задати поведінки типу «Збиватися в зграї» або «Слідувати за лідером», але складна тактична взаємодія монстрів теж вимагає більш серйозної роботи над штучним інтелектом.

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

0 коментарів

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