Використання потенційних полів у сценарії стратегії реального часу

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

Цей урок описує метод планування течії гри та навігації юнітів, який використовує багатоагентні потенційні поля. Він заснований на роботах під номерами [1, 2, 3]. (Дивіться кінець статті посилання на матеріали, які використовуються)

Що таке потенційне поле?

ПП (Потенційне Поле) має ряд подібностей з картами впливу (influence maps). Карти впливу часто використовуються для визначення чи знаходиться зона в ігровому світі під контролем гравця або ворогів (в зоні далекобійності зброї або пересування), або ж це зона, яка в даний момент не знаходиться під контролем кого-небудь (нічия земля). Ідея полягає в тому, щоб помістити позитивні значення на клітини під контролем гравця, а негативні - під контролем ворога. Плавно зменшуючи значення до нуля, ми створимо карту, що відображає вплив своїх і ворожих юнітів в зоні. Малюнок нижче показує приклад карти впливу з одним своїм і одним ворожим юнітом.

Потенційні поля працюють схожим чином - на цікаву позицію в ігровому світі кладеться заряд і генерує поле, яке поступово сходить на нуль. Заряд може бути притягуючим (додатним) або відштовхуючим (від'ємним). Зверніть увагу, що в деякій літературі про потенційні поля негативні заряди притягують і навпаки. У цьому уроці позитивні заряди завжди прятивають. Малюнок нижче показує простий ігровий світ з деякою непрохідною територією (коричнева), ворожого юніта (зелений) і пункт призначення юніта (Е). Притягуючий заряд розташований в точці призначення.

Заряд генерує поле, яке поширюється по ігровому світу:

І загасає до нуля:

Навігація за допомогою ПП

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

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

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

Переваги використання ПП

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

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

Приклад рівняння, як таке поле може бути згенеровано:

Тут W1 - значення для зміни відносної сили поля. D - максимальна дальність стрільби і R - максимальна дальність виявлення (звідки наш агент бачить ворожого агента)

Інша поведінка, яка легко реалізувати це «пнув-втік». Спершу юніт підходить на максимальну відстань атаки.

Після атаки наш юніт повинен перезарядити свою зброю і відступає від ворожого юніта до тих пір, поки не буде готовий стріляти знову.

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

Картинка нижче - скріншот нашого бота, заснованого на ПП для ORTS engine. Ліва сторона зображення - це 2D вигляд поточного стану гри. Воно показує наші танки (зелені кола), що йдуть атакувати ворожі бази (червоні квадрати) і юніти (червоні кола). Коричневі та чорні зони - непрохідна територія (гори). З правого боку зображення показано потенційне поле цього стану гри. Як і на інших картинках з цього уроку, блакитні зони найбільш притягуючі. Світлі лінії - атаки наших танків. ПП-уявлення чітко показує як наші юніти оточують ворога на максимальній дистанції пострілу, в той же час уникаючи зіткнень один з одним і місцевістю. Поведінка оточення ворога працює відмінно і була, можливо, однією з ключових у нашому успіху 2008го року на ORTS tournament.

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

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

Нотатки щодо реалізації

З хорошим планом і реалізацією ПП системи, витрати ресурсів на розрахунок не перевищать традиційних рішень на основі алгоритму А *. Наш ORTS бот використовував найменшу кількість ресурсів ЦП в порівнянні з двома іншими ботами, що працюють на алгоритмах пошуку шляху, з турніру 2007-го року. Однак, ми відзначимо, що складно точно порахувати використання ЦП, через те, що перемагаючий бот використовує більше ресурсів в кінці гри, так як у нього залишається більше юнітів під контролем. Багатопоточність також ускладнює завдання підрахунку необхідних ресурсів ЦП. Порівняння було проведено шляхом порівнення загальної кількості ресурсів ЦП, використаних кожним клієнтським процесом в середовищі Лінукса протягом 100 ігор. Принаймні ми можемо зробити висновок, що бот був хороший в рамках виділеного часу в 0.125 сек, використовуваному в ORTS.

Для поліпшення продуктивності ми поділили ПП на три категорії:

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

Ми експериментували з двома основними архітектурами для генерації ПП...

Пре-генерація

Поле, що генерується кожним типом об'єкта було заздалегідь розраховане і зберігалося в статичних масивах у заголовковому файлі. Під час виконання програми ці поля просто додавалися до загального ПП на потрібній позиції. Щоб зробити це відмоним ігровий світ був поділений на тайли, в нашому випадку кожен тайл складався з 8х8 точок ігрового світу. Цей підхід показав недостатню деталізацію і бот виступив погано (2007 рік турніру ORTS). Так як ігровий світ був поділений на значно більші тайли, ми стикалися з проблемами вирішення того, який тайл (які тайли) об'єкт займає. Припустимо об'єкт (помаранчеве коло) і база (помаранчевий квадрат). Які тайли (сірі квадрати) займає наш зелений юніт і які тайли повинна займати база?

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

Обчислення у реальному часі

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

Завдяки:

• Ми вважаємо потенціали тільки тих точок, які є кандидатами на пересування в них юнітів. У пре-генерованому варіанті вважаються всі потенціали всього ігрового світу (природно, це можна оптимізувати схожим методом).
• Розрахувавши відстань до об'єкта швидким методом Манхеттена, ми можемо уникнути дорогого розрахунку відстані в Евклідовому просторі для великої кількості об'єктів в ігровому світі.

Цей підхід був використаний у другій версії нашого бота (турнір ORTS 2008 року). Приклад формули ПП (з 2Д і 3Д графіками), який використовується для підрахунку потенціалу, що генерується качем в точці з відстанню «а» від ранку.

А що з проблемою локального оптимуму?

Одна з найбільш звичайних проблем з ПП це проблема локального оптимуму. На картинці знизу приклад коли це проблема з'являється. Пункт призначення «Е» генерує кругове поле, яке блокується горою. Юніт рухається до позицій з найбільш високими потенціалами і закінчує на найбільшому, де він в даний момент і стоїть. Юніт застряг.

Ми вирішили це використанням сліду, схожого зі слідом феромонів, описаному в [4]. Кожен агент, який контролює юніт, додає слід в останніх N позиціях, відвіданих юнітом, а також у поточну позицію юніта. Слід генерує легкий відштовхуючий потенціал і «штовхає» юніт вперед. Дивіться як слід штовхає юніта навколо локального оптимуму (жовта лінія) і юніт може знайти шлях до точки призначення.

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

Таке можна вирішити шляхом заповнення пустот:

Ув'язнення

Нижче ми склали критику проти рішень, заснованих на ПП з нашої точки зору:

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

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

Засновані на ПП рішення складні для реалізації та налаштування. ПП можуть бути реалізовані з дуже простою архітектурою. Налаштування може бути складним і обов'язковим, але відносна важливість між полями була б тут до речі (наприклад що важливіше знищити базу або юнітів?). Графічна вистава ПП теж дуже цінна.

Посилання

Using Multi-agent Potential Fields in Real-time Strategy Games

Johan Hagelbäck and Stefan J. Johansson

International Conference on Autonomous Agents and Multi-agent Systems (AAMAS), 2008.

1. Звантажити PDF

The Rise of Potential Fields in Real Time Strategy Bots

Johan Hagelbäck and Stefan J. Johansson.

Proceedings of Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 2008.

2. Звантажити PDF

A Multiagent Potential Field-Based Bot for Real-Time Strategy Games

Johan Hagelbäck and Stefan J. Johansson

International Journal of Computer Games Technology, 2009.

3. Звантажити PDF

Learning Human-like Movement Behavior for Computer Games

C. Thurau, C. Bauckhage, and G. Sagerer

International Conference on the Simulation of Adaptive Behavior (SAB), 2004.

4. Звантажити PDF