Hogyan navigáljunk több ezer ellenséget Unity DOTS-ban

Több ezer ellenségből álló hordát Unity DOTS-ban egyetlen, az egész pályára kiterjedő flow fielddel és néhány olcsó helyi szabállyal irányítson: taszítás a szomszédoktól és a falaktól, a tömegsűrűségtől függő útköltség és egy „várok” állapot a dugóban. A Unity Editorban egy M3 Pro-s MacBookon ez nagyjából 9600 ellenséget bír egyszerre 90 FPS mellett.

A probléma tower defense, stratégiai és survival játékokban jelentkezik, ahol egyszerre több ezer egység tart egy cél felé. A klasszikus, egységenkénti útkeresés túl drága, helyi szabályok nélkül pedig a tömeg átfedi egymást, a falakhoz tapad és elakad a szűkületekben. A Unity DOTS (Data-Oriented Technology Stack, azaz Entities, ECS és Job System) megadja a teljesítményt több ezer entityhez, a navigációt viszont nem oldja meg. Az alábbi módszert a PC-re készülő tower defense játékunkban használjuk (szerepel a referenciáink között). A képek egy egyszerűsített, ugyanazokkal a szabályokkal futó 2D szimulációból származnak, nem a játékból.

#1. lépés: Flow field egységenkénti útvonal helyett

A flow field egy az egész pályát lefedő rács, amelyben minden cella tudja, merre kell belőle a cél felé menni. Az ellenség nem keres utat, csak leolvassa az irányt azon a helyen, ahol áll. A költség 10 és 10 000 ellenségnél is ugyanannyi.

Ossza fel a pályát 1 m-es cellákra (a tesztpályánk 128 × 128-as), és minden célhoz egyszer számolja ki minden cella távolságát a céltól. A statikus mezőt elég a szerkesztőben, a pálya előkészítésekor kiszámolni és egy assetben tárolni.

A legegyszerűbb változat a Dijkstra 8 szomszéddal, minden cellában a 8 irány egyikével. Működik, de az ellenségek átlósan mennek, és libasorban a falakhoz tapadnak.

8 irány

Sima mező

Jobb eredményt ad a sima mező. A távolságot az eikonál-egyenlet megoldásával számolja ki (hullámfront-egyenlet, amelynek megoldása a folytonos térben mért legrövidebb távolság, nem csak a rács élei mentén), a fast sweeping módszerrel, amely a rácsot ismételten mind a négy sarokból bejárja. Az irány így nem a cella iránya, hanem a távolság gradiense az ellenség pontos helyén. A cella költségéhez adjon felárat a fal közelségéért, így a mező magától távol tartja a tömeget az akadályoktól.

#2. lépés: Külön mező minden ellenségmérethez

A nagy ellenség nem fér be mindenhová, ahová a kicsi. Vezessen be méretosztályokat: mindegyiknek saját járhatósága van (a cellának elég messze kell lennie a faltól), és minden célhoz saját mezője. Az osztályokat pályaadatként tartsa, ne a kódban. Nálunk három van.

#3. lépés: Taszítás a szomszédoktól

A flow field megadja az irányt, de a szomszédokról semmit sem tud. Az alap egy egyszerűsített boids modell (a raj klasszikus szabályai): minden ellenség taszítja a 0,9 m-en belüli szomszédait. A szomszédokat spatial hashben keresse, vagyis egy térbeli rácsban, ahol minden cella a benne lévő egységek listáját tartja. A hasht minden tickben építse fel újra és rendezze, hogy a sorrend determinisztikus legyen.

A taszítás önmagában nem elég. 3000 ellenségnél 83,7 %-uk legközelebbi szomszédja 0,8 m-nél közelebb volt, a legkisebb távolság pedig 4 cm, vagyis két ellenség szinte egymásban állt.

A taszítás súlyának növelése nem oldja meg. 1,5 helyett 6-os súlynál a túl szorosan állók aránya 54,6 %-ra esett, 12-nél 44,3 %-ra, 24-nél már nem javult (48,2 %). Ráadásul a tömeg ugrálni kezd, mert sok szomszéd korlátlan lökései egyszerre adódnak össze.

A pozíciókorrekció segít. Mozgás után minden átfedő párt toljon szét, mindkettőt az átfedés felével, és tickenként korlátozza az eltolást 0,15 m-re. Korlát nélkül a korrekció ugyanúgy ugrál, mint a nagy súly. Vele a túl szorosak aránya 60,8 % marad, de a legkisebb távolság 28 cm-re nő, és a tömeg nem ugrál.

Csak taszítás

Átfedéskorrekció

#4. lépés: Taszítás a falaktól

A falnál az ellenségek közötti korrekció csődöt mond. A falba mozgás tilos (az eltolás tengelyenként bomlik fel, a falba mutató összetevő elvész), így a falhoz szorult ellenség nem tud kitérni, és a szomszédtól jövő korrekció elvész. 938 átfedő ellenségből csak 35-nél volt egyáltalán nyomás a fal felől.

Ezért adjon hozzá taszítást a legközelebbi járhatatlan cellák felől, 4 irányban és átlósan is. Két hiba, amelyet elkerülhet:

• Belső sarok. A két él és a sarok nyomása összeadódik, és elhajítja az ellenséget. Sarokból jövő nyomást csak külső saroknál adjon hozzá.
• Valódi falak. A valódi falaktól taszítson, ne a méretosztály járhatóságától. Egy nagy ellenség számára a „fal” már egy méterrel a valódi előtt kezdődik. Egy folyosó bejáratánál így a sarok nyomása kioltotta egy nagy ellenség előrehaladását, és a mögötte haladó egész csoport megállt.

#5. lépés: Sűrűségfüggő költség és lassítás

Sima mezővel is az egész tömeg a legrövidebb úton, szorosan a sarok mellett megy, függetlenül attól, hányan vannak már ott. Megoldást a Continuum Crowds (Treuille és mtsai, 2006) kínál: a cella költsége a tömegsűrűséggel nő. 10 tickenként számolja meg az ellenségeket cellánként, simítsa ki az eredményt, és számolja újra egy cél mezőjét. Zsúfolt saroknál a mező így körbeküldi az ellenséget, a szabadabb cellákon át.

Sűrűség nélkül

Sűrűségfüggő költség

A másik fele a lassítás. A sűrű cellában lévő ellenség lassabban megy, legfeljebb a sebessége 15 %-ára lassul. 2250 ellenségnél a ritka cellákban átlagosan a sebességük 94 %-ával haladtak, közepes sűrűségnél 71 %-kal, dugóban 20 %-kal. A lassítás kezdődjön korán: cellánként 1 helyett 0,6 ellenséges szabad sűrűségi küszöbbel a túl szorosan állók aránya a szűkületben 36,7 %-ra esett.

Gyakorlati tanács: a csak futásidőben létrejövő tömböket (például a sűrűségtérképet) foglalja le, mielőtt egy job először használná őket. Egy még létre nem hozott tömbbel ütemezett job natívan összeomlasztja a Unity Editort, mindenféle exception nélkül.

#6. lépés: Dugó a szűkületben: várni, nem tolni

Ha a tömeg sehová sem tud szétterülni, marad a szűkület. A legegyszerűbb ötlet az, hogy eldobjuk a sebesség azon összetevőjét, amely az érintett szomszéd felé mutat. A hátsók ekkor kitérés helyett megállnak, és fenntartják a dugót.

Oldalra kitérni, például 35°-kal a kevesebb szomszéd felé, jobb, de a tömeg villogni kezd. A fordulás simítása és alacsonyabb fordulási sebesség (360 helyett 180 °/s) csak tompítja a tünetet. Az ok máshol van: kiegyenlített sűrűségnél az ellenség minden tickben más oldalt választ. A hiszterézis segít, vagyis az előző döntés előnyben részesítése: az előző tick oldala az összehasonlításnál 3 szomszédnyi kedvezményt kap.

A végső megoldás érintkezési korlátot és három állapotot kapcsol össze: halad, kitér, vár. Az érintett szomszéd felé mutató sebességösszetevő elvész, az oldalirányú megmarad. Akinek nincs szabad oldala és maga előtt sincs helye, az vár, és nem tol.

minden ellenségre, minden tickben:
    sebesség = irány a flow fieldből × tempó × sűrűség szerinti lassítás
    sebesség += taszítás a szomszédoktól
    ha elöl szomszédhoz ér:
        ha van szabad oldal: kitér (oldal hiszterézissel)
        különben: vár
    eldobja az érintett szomszédok felé mutató sebességösszetevőt
    elmozdul, a falba mutató összetevőt eldobja
utána mindenkire:
    az átfedő párokat széttolja (az átfedés fele, legfeljebb 0,15 m)
    taszít a falaktól

Három dologra figyeljen:

• Türelem. Ha két ellenség szemből találkozik, a nagyobb azonosítójú (ID) várjon. Egy szomszédlánc azonban ezernyi tickig blokkolhatja, ezért a várakozási korlát után vészkitéréssel próbálkozik.
• Nulla sebesség. A nulla kívánt sebességű ellenség soha nem lép ki a „vár” állapotból, és egy hullám után a nyílt terepen állva marad. Aki nem akar mozogni, legyen mindig „halad” állapotban.
• Keskeny kúp. Az elöl lévő szomszédot keskeny kúpban, rövid szondával keresse. 45°-nál a beállítás nyílt terepen is a tömeg 55-60 %-át küldte várakozásba vagy kitérésbe, 30°-nál és rövidebb szondával 41 %-át.

#7. lépés: Nagy ellenségek megelőzése

A különböző méretű és sebességű ellenségtípusok újabb eseteket hoznak. A nagy, lassú ellenségünk sugara a tömegben 1,25 m, sebessége 1,1 m/s. A mögötte haladó gyors ellenség nem tudta megelőzni: az átlósan előre néző oldalsó szondák mindig közelebb voltak a nagyhoz, mint a sugarak összege, mindkét oldal foglaltnak bizonyult, és a gyors várt. A javítás: a megkerült szomszédot a szonda csak a saját oldalán veszi figyelembe. A pontosan előtte álló szomszéd egyik oldalt sem blokkolja.

A nagy ellenség viszont oldalra löki útjából a kicsiket, a maga előtti ±45°-os szektorban. Ne lökje el azokat, akik gyorsabban haladnak az ő irányában, mint amennyire ő akar, különben azokat is ellöki, akik éppen megelőzik.

#8. lépés: Slotok a támadás célpontja körül

Ha az ellenségek közelharcban támadnak, hely kell nekik a célpont körül. A tornyunknak 24 slotja van az 5 × 5 m-es alapterület kerületén, minden ellenség egyet foglal el, a többiek sorban várnak.

• Körben kerülés. Ha csak akkor kínál fel slotot, ha egyenes vonal vezet hozzá, a hátsó slotok üresek maradnak, mert elölről a hozzájuk vezető vonal átmetszi a tornyot. Az ellenség ívben kerülje meg a tornyot a szabad slotig.
• Kiszorítás nélkül. Ne szorítsa ki a slot felé tartó ellenséget egy másik jelentkező javára, mert kiszorítások láncolatát indítja el.
• Taszítás nélkül a slotnál. A foglalt slot mellé érkező ellenséget a szomszédja ellöki, így 13 cm-re a céljától vagy teljesen mellette köt ki. A slotban lévő és tőle 0,5 m-en belüli ellenségek nem taszítják egymást.

#A szimuláció és a renderelés teljesítménye

Egy benchmark a Unity Editorban (M3 Pro, nagyjából 9600 egyszerű ellenség, két szűkület) 1440p-n 90 FPS-t, 1080p-n 100-at adott. A felbontás alig változtat az FPS-en, az időgyorsítás viszont igen: 10×-nél 20 FPS-re esik, mert egy képkockára tíz szimulációs lépés jut. Normál sebességnél a szimulációnak van tartaléka.

Kapszula helyett részletes ellenségmodellel a szűk keresztmetszet a renderelésbe kerül át:

A szimulációban három dolog térül meg:

• Két szomszédkeresési menet. Az olcsó (érintkezések, blokkolás) mindig fut, a drága (oldalsó szondák, oldalak sűrűsége) csak a blokkoltaknál, akik szabad áramlásban kisebbségben vannak. A távolságokat négyzetesen hasonlítsa össze, gyökvonás nélkül.
• Egyszerű rendezés. A spatial hash szinkron rendezése 3000, 10 000, 20 000 és 50 000 bejegyzésnél 0,37, 1,49, 3,16 és 8,46 ms-ig tartott, a jobos változat 0,18, 0,93, 3,12 és 15,53 ms-ig. A job nem következetesen gyorsabb, az egyszerű rendezés elég.
• Állapothash. A 600. és az 1800. tickben számoljon hasht a pozíciókból és az életerőből. Egy refaktornak ugyanazt a hasht kell adnia, a viselkedés megváltozása megváltoztatja, és meg tudja magyarázni, miért. Ez a spatial hash determinisztikus sorrendjének köszönhetően működik.

#A módszer korlátai

• Két teli, egymással szemben haladó tömeg egy szűkületben végleg beragad. Ez a fizika nélküli modell korlátja.
• A számok a Unity Editorból származnak, M3 Pro-n. Steam Decken és valódi buildben még nincs mérésünk, csak becslésünk nyilvános processzor-benchmarkok alapján.

Ha saját tömeget szeretne kipróbálni, a Unity Entities dokumentációja jó kiindulópont. Hasonló utat a legegyszerűbb megoldástól a működőig a sudokugenerátorról szóló cikkünk is bemutat. Hogy egy ilyen horda ellenségeit hogyan repítheti szét egy robbanás anélkül, hogy mindegyikükre drága ragdollt szimulálna, azt a fake ragdoll Unity DOTS-ban útmutató mutatja be. Ha hasonló szimuláción dolgozik Unityben, és segítség kellene, írjon nekünk.