Як керувати ордою з тисяч ворогів в Unity DOTS

Орду з тисяч ворогів в Unity DOTS ведіть одним flow field для всієї мапи та кількома дешевими локальними правилами: відштовхування від сусідів і від стін, вартість шляху залежно від щільності натовпу та стан «чекаю» в заторі. В Unity Editor на MacBook з M3 Pro це витримує близько 9 600 ворогів одночасно при 90 FPS.

Проблема виникає в tower defense, стратегіях і survival іграх, де до цілі одночасно йдуть тисячі юнітів. Класичний пошук шляху для кожного окремо надто дорогий, а без локальних правил натовп перекривається, липне до стін і застрягає у вузьких проходах. Unity DOTS (Data-Oriented Technology Stack, тобто Entities, ECS і Job System) дає продуктивність для тисяч сутностей, але саму навігацію не розв'язує. Описаний нижче підхід ми використовуємо в нашій tower defense грі для ПК (вона є в нашому портфоліо). Зображення взяті зі спрощеної 2D-симуляції, що працює за тими самими правилами, це не кадри з гри.

#Крок 1: Flow field замість шляху для кожного

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

Поділіть мапу на клітинки по 1 м (наш тестовий рівень має 128 × 128) і для кожної цілі один раз порахуйте відстань від кожної клітинки до цілі. Статичне поле достатньо порахувати в редакторі під час підготовки рівня і зберегти в асеті.

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

8 напрямків

Плавне поле

Кращий результат дає плавне поле. Відстань порахуйте розв'язанням рівняння ейконалу (рівняння поширення хвильового фронту, розв'язком якого є найкоротша відстань у неперервному просторі, а не лише вздовж ребер сітки) методом fast sweeping, який багаторазово проходить сітку з усіх чотирьох кутів. Тоді напрямок це не напрямок клітинки, а градієнт відстані в точному місці ворога. До вартості клітинки додайте надбавку за близькість до стіни, тож поле саме тримає натовп трохи далі від перешкод.

#Крок 2: Окреме поле для кожного розміру ворога

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

#Крок 3: Відштовхування від сусідів

Flow field дає напрямок, але нічого не знає про сусідів. Основа це спрощена модель boids (класичні правила зграї): кожен ворог відштовхується від сусідів у радіусі 0,9 м. Сусідів шукайте в spatial hash, тобто в просторовій сітці, де кожна клітинка тримає список юнітів у ній. Будуйте hash щотіку заново й сортуйте, щоб порядок був детермінованим.

Самого відштовхування замало. При 3 000 ворогах у 83,7 % із них найближчий сусід був ближче ніж 0,8 м, а найменша відстань становила 4 см, тобто двоє ворогів майже один в одному.

Більша вага відштовхування проблему не розв'язує. При вазі 6 замість 1,5 частка надто тісних упала до 54,6 %, при 12 до 44,3 %, при 24 далі нічого (48,2 %). До того ж натовп починає підстрибувати, бо необмежені поштовхи від багатьох сусідів додаються одночасно.

Допомагає позиційна корекція. Після руху розсуньте кожну пару, що перекривається, кожного на половину перекриття, а зсув за тік обмежте 0,15 м. Без цього обмеження корекція стрибає так само, як висока вага. З ним надто тісних залишається 60,8 %, але найменша відстань зростає до 28 см і натовп не підстрибує.

Лише відштовхування

Корекція перекриття

#Крок 4: Відштовхування від стін

Біля стіни корекція між ворогами не спрацьовує. Рух у стіну заборонено (зсув розкладається по осях, а складова в стіну відкидається), тож притиснутому ворогу нікуди ухилитися, і корекція від сусіда губиться. Із 938 ворогів, що перекривалися, ненульовий поштовх від стіни мали лише 35.

Тому додайте відштовхування від найближчих непрохідних клітинок у 4 напрямках і по діагоналі. Дві помилки, яких можна уникнути:

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

#Крок 5: Вартість за щільністю та сповільнення

Навіть із плавним полем увесь натовп іде найкоротшим шляхом впритул навколо кута, незалежно від того, скільки ворогів там уже є. Рішення пропонує Continuum Crowds (Treuille та ін., 2006): вартість клітинки зростає зі щільністю натовпу. Раз на 10 тіків порахуйте ворогів у клітинках, згладьте результат і перерахуйте поле однієї цілі. Біля переповненого кута поле тоді відправляє ворога в обхід, через вільніші клітинки.

Без щільності

Вартість за щільністю

Друга половина це сповільнення. Ворог у щільній клітинці рухається повільніше, щонайменше на 15 % швидкості. На 2 250 ворогах вони в розріджених клітинках ішли в середньому на 94 % швидкості, у помірно щільних на 71 %, а в заторі на 20 %. Нехай сповільнення починається раніше: з порогом вільної щільності 0,6 ворога на клітинку замість 1 частка надто тісних у вузькому проході впала до 36,7 %.

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

#Крок 6: Затор у вузькому проході: чекати, а не тиснути

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

Ухилитися вбік, наприклад на 35° у бік із меншою кількістю сусідів, краще, але натовп починає мерехтіти. Згладжування повороту й нижча швидкість обертання (180 замість 360 °/с) лише приглушують симптом. Причина в іншому: при врівноваженій щільності ворог щотіку обирає інший бік. Допомагає гістерезис, тобто перевага попереднього рішення: бік із минулого тіку отримує під час порівняння знижку в 3 сусіди.

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

для кожного ворога, щотіку:
    швидкість = напрямок із flow field × швидкість × сповільнення за щільністю
    швидкість += відштовхування від сусідів
    якщо попереду торкається сусіда:
        якщо є вільний бік: обходь (бік із гістерезисом)
        інакше: чекай
    відкинь складову швидкості в сусідів, яких торкаєшся
    зрушся, складову в стіну відкинь
потім для всіх:
    розсунь пари, що перекриваються (половина перекриття, щонайбільше 0,15 м)
    відштовхни від стін

Зверніть увагу на три речі:

• Терпіння. Коли двоє ворогів зустрічаються лоб у лоб, нехай чекає той, у кого вищий ID. Ланцюг сусідів може блокувати його тисячі тіків, тому після ліміту очікування він пробує аварійно ухилитися.
• Нульова швидкість. Ворог із нульовою бажаною швидкістю ніколи не виходить зі стану «чекає» і після хвилі залишається стояти на відкритому місці. Хто не хоче рухатися, має завжди бути в стані «іде».
• Вузький конус. Шукайте сусіда попереду у вузькому конусі з короткою пробою. При 45° налаштування відправляло в очікування чи обхід 55 до 60 % натовпу навіть на відкритому місці, при 30° і коротшій пробі 41 %.

#Крок 7: Обгін великих ворогів

Типи ворогів різного розміру та швидкості додають нових випадків. Наш великий повільний ворог має радіус у натовпі 1,25 м і йде зі швидкістю 1,1 м/с. Швидкий ворог позаду не міг його обігнати: бічні проби навскіс уперед завжди були ближче до великого, ніж сума радіусів, обидва боки виявлялися зайнятими, і швидкий чекав. Виправлення: сусіда, якого ворог обходить, проба враховує лише з його власного боку. Сусід точно попереду не блокує жодного боку.

Великий ворог, навпаки, відкидає малих зі свого шляху вбік, у секторі ±45° перед собою. Не відкидайте тих, хто рухається в його напрямку швидше, ніж хоче йти він сам, інакше він відкине й тих, хто саме його обганяє.

#Крок 8: Слоти біля цілі атаки

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

• Обхід по колу. Якщо пропонувати слот лише тоді, коли до нього веде пряма лінія, задні слоти залишаються порожніми, бо спереду лінія до них перетинає вежу. Нехай ворог обходить вежу по дузі до вільного слота.
• Без витіснення. Не витісняйте ворога, що йде до слота, на користь іншого претендента, це запускає ланцюг витіснень.
• Без відштовхування біля слота. Ворога, що підходить поруч із зайнятим слотом, відштовхує сусід, і він опиняється за 13 см від цілі або зовсім осторонь. Вороги в слоті та в межах 0,5 м від нього не відштовхують одне одного.

#Продуктивність симуляції та рендерингу

Benchmark в Unity Editor (M3 Pro, близько 9 600 простих ворогів, два вузькі проходи) дав 90 FPS при 1440p і 100 при 1080p. Роздільна здатність майже не змінює FPS, а прискорення часу змінює: при 10× падає до 20 FPS, бо на один кадр припадає десять кроків симуляції. На звичайній швидкості симуляція має запас.

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

У симуляції окупаються три речі:

• Два проходи по сусідах. Дешевий (дотики, блокування) працює завжди, дорогий (бічні проби, щільність боків) лише для заблокованих, яких у вільному потоці меншість. Порівнюйте відстані в квадраті, без кореня.
• Просте сортування. Синхронне сортування spatial hash тривало при 3 000, 10 000, 20 000 і 50 000 записів 0,37, 1,49, 3,16 і 8,46 мс, версія в job 0,18, 0,93, 3,12 і 15,53 мс. Job не є стабільно швидшим, простого сортування достатньо.
• Hash стану. На тіках 600 і 1800 рахуйте hash позицій і здоров'я. Рефакторинг має дати той самий hash, зміна поведінки його змінює, і ви можете пояснити чому. Це працює завдяки детермінованому порядку в spatial hash.

#Обмеження підходу

• Два повні зустрічні натовпи в одному вузькому проході застрягають назавжди. Це обмеження моделі без фізики.
• Цифри отримано в Unity Editor на M3 Pro. Вимірювань на Steam Deck і в справжньому build у нас поки немає, лише оцінка з публічних benchmark процесорів.

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