Umělá inteligence v počítačových hrách

Note

Pohyb, kinematika, řízení chování. Prohledávání a hledání cest: A* nad datovými strukturami a heuristiky, reprezentace herního světa, Monte Carlo prohledávání, hierarchické hledání cest. Rozhodování, rozhodovací stromy, stavové automaty, stromy chování. Strategie a taktika, navigační body, taktická analýza.

PA217

Pohyb

Postavy ve hrách se často hýbou, tedy mění svoji pozici a orientaci v herním světě. Mnohdy je žádoucí, aby se pohybovaly věrohodně:

zpomalovaly,
zrychlovaly,
vyhýbaly se překážkám,
utíkaly před nepřáteli,
interagovaly s prostředím.

Pozice: Tradičně je dána jako vektor $(x, z)$ nebo $(x, y, z)$ .
Orientace: Obvykle v radiánech. Desetinné číslo z intervalu $[0, 2 π)$ .
Rychlost / velocity: Změna pozice. Vektor $(x, z)$ nebo $(x, y, z)$ .
Úhlová rychlost / angular velocity / "rotace": Změna rotace. Desetinné číslo z intervalu $[0, 2 π)$ .
Agent: Postava / objekt / entita vykonávájí pohyb a činící rozhodnutí.

Kinematika

Postavy se prostě pohybují bez ohledu na fyzikální korektnost.

Výhodou je jednoduchost a předvídatelnost.
Nevýhodou je, že pohyb nemusí být věrohodný.
Příkladem je pohyb většiny postav ovládaných hráčem. Pokud hráč pustí W, chce obvykle zastavit hned.

Update

V každém frame:

void Update(float deltaTime)
{
    Position += Velocity * deltaTime;
    Orientation = (Orientation + (AngularVelocity * deltaTime))
        % (2 * Math.PI);
    Velocity += SteeringLinear * deltaTime;
    AngularVelocity = (AngularVelocity + (SteeringAngular * deltaTime))
        % (2 * Math.PI);
}

Řízení chování / steering behaviors

Jednoduché algoritmy pro pohyb. Jsou škálovatelné a předvídatelné, ale mají problém s lokálními pastmi (zaseknou se a neví, jak ven).

Dynamic movement

Fyzikálně korektní pohyb. Postavy zrychlují ve směru cíle, dosahují maximální rychlosti a zpomalují, pokud je cíl blízko.

Seek

Přímočárý… doslova. Najde vektor mířící k cíli a aplikuje je jej jako steering.

Obrázek 1. Seek schematic [3]

Flee

Jako seek, ale od cíle místo k cíli.

Arrival

Jako seek, ale začne zpomalovat, když je blízko cíle, takže jej "nepřestřelí".

Obrázek 2. Arrival schematic [3]

Departure

Flee, ale agent zpomalí, jakmile je dostatečně daleko od cíle.

Pursue

Agent pronásleduje agenta. Najde vektor mířící k cíli a aplikuje jej jako steering. Pokud se cítí obzvlášť chytrý, může předvídat, kterým směrem se cíl bude ubírat.

Příklad: predátor loví kořist.

Evade

Agent se vyhýbá agentovi. Jako pursue, ale snaží se cíli vyhnout.

Příklad: kořist se vyhýbá predátorovi.

Wander

Agent se hýbe náhodně. Není to ale tak jednoduché, jak se zdá, protože nechceme, aby sebou agent jen házel ze strany na stranu. Jako seek, ale k cíli se v každém kroku přidává drobný náhodný posun.

Object avoidance / vyhýbání se překážkám

Agent detekuje, zda se v blízké době srazí s překážkou — ray castingem, testy na overlapping — a pokud ano, najde cíl, který je mimo překážku a aplikuje seek.

Má problém s úzkými překážkami a pastmi.

Flocking / chování hejna

Chování celé skupiny agentů:

Separation / oddělení: agent se snaží nenarážet do ostatních agentů v daném okolí.
Alignment / zarovnání: pohybuj se (průměrně) stejným směrem a rychlostí jako ostatní agenti v okolí.
Cohesion / soudržnost: pohybuj se směrem ke středu hmoty hejna.

Path following

Agent směřuje ne jen k pouhému bodu, ale k nejbližšímu bodu na dané cestě a ten seekuje.

Predictive path following

Agent předvídá, kde bude za krátkou chvíli a hledá nejbližší bod na dané cestě k této predikci. Pohyb je plynulejší.

Kombinování steering behaviors

Steering behaviors se dají kombinovat.

Blending: provádí více steering behaviors najednou a výsledný vektor je jejich váženým průměrem.
Arbitration: volí jedno steering behavior, které má absolutní moc.

Pathfinding / hledání cest

Pathfinding řeší problém s agenty, kteří se chytají do pastí. Umožňuje jim naplánovat si cestu okolo konkávních oblastí i pomalu se měnících překážek. Není však užitečný v oblastech, které se často mění, a proto je kombinován se steering behaviors.

Pathfinding vnímá scénu jako graf, ve kterém hledá (obvykle nejkratší) cestu.

Příklad 1. Opakování Grafových problémů

Graf $G$: Dvojice $(V, E)$ , kde $V$ je množina uzlů a $E$ je množina hran mezi nimi.
Orientovaný / directed graf: Záleží na směru hran.
Neorientovaný / undirected graf: Na směru hran nezáleží.
Vážený / weighted graf: Hrany mají cenu / váhu.
Breadth-first search / prohledávání do šířky (BFS): Prouzkoumává nejprve uzly v okolí počátečního uzlu, pak teprve uzly v okolí těchto uzlů, atd.
Depth-first search / prohledávání do hloubky (DFS): Prozkoumej jednoho souseda, pak jeho souseda, pak souseda toho souseda atd. dokud jsi tak hluboko, že nemáš kam jít. Pak se teprve vynoř o úroveň výš a zkus prozkoumat jiného souseda.
Shortest path algorithms / algoritmy pro nejkratší cestu: Hledají nejkratší cestu mezi dvěma uzly. Používají nějakou heuristiku $f$ pro výběr dalšího uzlu k prozkoumání.
Dijkstra’s algorithm / Dijkstrův algoritmus: Podobný BFS, ale snaží se najít nejkratší cestu, ne nutně prozkoumat celý graf. Hranám přiřazuje cenu a vybírá ty s nejnižší cenou — $f$ je nejnižší vzdálenost od počátečního uzlu.

A* algoritmus

Podobný Dijkstrovu algoritmu, ale navíc se snaží odhadnout, který směr je nejlepší. Používá heuristiku $h$ pro výběr dalšího uzlu k prozkoumání. Kombinuje Dijsktrův algoritmus s greedy best-first hledáním. [5]

Obrázek 3. A* algoritmus [5]

record Node
{
    Vector3 Position;
    List<Node> Neighbors = new();

    // NB: We keep both scores because the heuristic is not guaranteed to be consistent.
    float GScore = float.Infinity; // Distance from start
    float FScore = float.Infinity; // Distance from start + heuristic
    Node? CameFrom = null;
}

// NB: Assumes all nodes are initialized as above.
List<Node> AStar(Node start, Node goal) {
    var toVisit = new PriorityQueue<Node, float>();
    start.GScore = 0;
    start.FScore = 0;
    toVisit.Enqueue(start, 0);

    Node current = start;
    while (current != goal) {
        var (current, gCurrent) = toVisit.Dequeue();

        foreach (var neighbor in current.Neighbors) {
            var gNeighbor = gCurrent + Distance(current, neighbor);
            if (gNeighbor < neighbor.GScore) {
                neighbor.GScore = gNeighbor;
            }

            var fNeighbor = neighbor.GScore + Heuristic(neighbor, goal);
            if (fNeighbor < neighbor.FScore) {
                neighbor.FScore = fNeighbor;
                neighbor.CameFrom = current;
                toVisit.Enqueue(neighbor, fNeighbor);
            }
        }
    }

    return null;
}

float Heuristic(Node a, Node b) {
    // Example: Euclidean distance
    return Vector3.Distance(a.Position, b.Position);
}

Nejkratší cestu lze pak zrekonstruovat takto:

List<Node> ReconstructPath(Node goal) {
    var path = new List<Node> { goal };
    var current = goal;
    while (current.CameFrom is not null) {
        current = current.CameFrom
        path.Add(current);
    }
    path.Reverse();
    return path;
}

Volba heuristiky

Čím přesnější bude odhad vzdálenosti k cíli, tím rychlejší A* bude.
Pokud heuristika podceňuje vzdálenost k cíli, bude algoritmus pomalejší.
Pokud heuristika přeceňuje vzdálenost k cíli, algoritmus nemusí najít nejkratší cestu.
Heuristika je admissible pokud nepřeceňuje.

Heuristika — Euklidovská vzdálenost

Poskytuje poměrně přesný nebo podceněný odhad vzdálenosti k cíli. Funguje dobře v exteriérech, ale v interiérech dává kvůli stěnám a dalším překážkám silně podhodnocené odhady. [1]

Clusterová (shluková) heuristika

Shlukuje uzly blízko sebe (např. v rámci místnosti).
V rámci clusteru aplikuje Euklidovskou vzdálenost.
Pro vzdálenosti mezi clustery si udržuje look-up table (LUT).

Reprezentace herního světa

Agenti nevidí herní svět stejně jako hráči, vidí ho spíš jako graf s uzly a hranami.

Division scheme

Popisuje, jak je level rozdělen na uzly a hrany. Má vlastnosti:

Kvantizace: metoda převodu pozice na uzel.
Lokalizace: metoda převodu uzlu na pozici.
Generace: metoda vytvoření uzlů a hran. Může být manuální (třeba Dirichletovy domény) nebo automatická (třeba Visibility points).
Validita: všechny uzly, mezi kterými je cesta, musí být vzájemně dosažitelné ve hře.

Tile-based / dlaždicové

Některé hry, např real-time strategie (RTS), mají svět rozdělen do čtvercových / hexagonálních dlaždic. Díky tomu je jednoduché je převést na graf, neboť co dlaždice to uzel.

Obrázek 4. Sid Meier’s Civilization V [6]

Dirichletova doména / Voronoiův diagram

Level designer určí charakteristické body. Vytvořené regiony jsou složeny z bodů nejbližších danému charakteristickému bodu.

Obrázek 5. 20 points and their Voronoi cells by Balu Ertl

Points of visibility

Je automatická metoda generování charakteristických bodů (typicky pro generování Voronoiova diagramu). Generuje je v místech, kde se geometrie levelu mění z konvexní na konkávní a naopak (např. v rozích místností). Posouvá je o šířku hráče.

V praxi může generovat příliš mnoho bodů, ale může sloužit jako užitečný základ pro manuální úpravy.

Obrázek 6. Points of visibility [2]

Navmesh / navigation mesh / navigační sítě

Populární technika, kdy level designer popíše podlahové polygony. Agenti mohou chodit kamkoliv v rámci těchto polygonů a přecházet mezi těmi, které jsou spojené. Využívá geometrii už přítomnou v levelu nebo svoji vlastní.

Obrázek 7. Navigation System in Unity [4]

Obrázek 8. Polygonal mesh graph [2]

D* algoritmus

Varianta A*, která se umí vyrovnat s dynamickými změnami v grafu.

Iterative Deepening A* (IDA*)

Depth-first search s heuristikou. Iterative deepening znamená, že se postupně zvyšuje maximální hloubka prohledávání. [9]

Simplified Memory Bounded A* (SMA*)

A* co má nižší paměťové nároky.

Monte Carlo prohledávání

Tip	Monte Carlo Město známé pro svá casina. Monte Carlo metoda Algoritmy a techniky spoléhající na náhodou, mega velké množiny vzorků a statistickou analýzu. [7]

Monte Carlo tree search (MCTS)

Heuristický algoritmus pro prohledávání stromových grafů. V kontextu deskových her se používá pro hledání nejlepšího tahu.[8]

Selection: vyber uzel reprezentující stav hry, ze kterého ještě hra neskončila.
Expansion: vytvoř možné volby ze zvoleného tahu.
Simulation: vyber volbu náhodně a odsimuluj hru až do konce.
Backpropagation: aktualizuj statistiky v uzlech na cestě od kořene k listu.

Obrázek 9. Step of Monte Carlo tree search by Rmoss92

Tree boundary

Metoda (policy), kdy v uzlech nad MCTS tree boundary jsou akce voleny inteligentně. Pod touto hranicí jsou akce voleny náhodně.

Upper confidence bound (UCT)

Metrika pro volbu nejlepšího uzlu.

UCT = \overline{X_{j}} + C \frac{ln n}{n _{j}}

kde:

$\overline{X_{j}}$ je střední hodnota odměny z akce v uzlu $j$ . Může být třeba počet výher / počet her.
$C$ je exploration parameter, který určuje, jak moc se má algoritmus zaměřovat na prozkoumávání nových uzlů.
$n$ je počet her, ve kterých byl zvolen rodičovský uzel.
$n_{j}$ je počet her, ve kterých byl zvolen uzel $j$ .

Hierarchické hledání cest

Nejdřív najde cestu mezi domy, pak teprve cestu od vchodových dveří k ledničce.

Nejprve hledá cestu na vysoké úrovni (mezi clustery), pak v rámci clusteru.

Important

Výhodou je, že zrychluje hledání cest.

Warning

Nevýhodou je, že vzdálenost mezi clustery se blbě měří, protože hráč do něj mohl vstoupit z různých míst. V praxi se používá třeba:

nejkratší vzdálenost,
nejdelší vzdálenost,
průměrná minimální vzdálenost.

Rozhodování

Agenti obvykle musí činit rozhodnutí ohledně toho, co budou dělat dál: zaútočit, ukrýt se, prchat, atd.

Decision trees / rozhodovací stromy

Rozhodnutí jsou reprezentována jako strom. Vniřní uzly jsou podmínky, listy jsou akce, hrany reprezentují možnosti. Rozhodovací proces začíná u kořene a postupuje dolů stromem, dokud nenarazí na list — ta akce se následně provede.

Obrázek 10. Průchod rozhodovacím stromem [2]

State machines / stavové automaty

Reprezentuje aktuální chování agenta pomocí stavů ve stavovém automatu. Každý stav zahrnuje nějaké akce. Přechody mezi stavy jsou spojeny s podmínkami a akcemi.

Obrázek 11. State machine [2]

Hierarchické stavové automaty: Stavy mohou obsahovat celé další stavové automaty. To umožňuje rozdělit chování agenta na části.

Obrázek 12. Hierarchical state machine [2]
Stavový automat s rozhodovacími stromy v přechodech: V přechodech mezi stavy jsou decision trees. Listy jsou další stavy.

Obrázek 13. State machine with decision tree transitions [2]

Behavior trees / stromy chování

Návrhový vzor používáný v herním vývoji.
Je orientovaný na úkoly (tasks) spíš než na stav (state).
Kombinuje množství jiných technik.
Dá se vyrobit modulárně a znovupoužitelně.
Často pro něj existují i custom editory s GUI.

Obrázek 14. Behavior tree [2]

Obrázek 15. Parallel behavior tree [1]

Listy

Conditions (podmínky): vyhodnocují nějakou podmínku vůči postavě, hráči nebo hře. Mohou uspět nebo selhat.
Actions (akce): mění stav hry, pouští animace, interagují s hráčem. Obvykle uspějí, ale mohou selhat (např. pokud jsou přerušeny).

Vnitřní uzly

Sequences (sekvence) $\to$ : vykonávají své potomky po řadě, dokud první neselže. Uspěje jen pokud uspějí všichni. Je to takový AND.
Selectors (selektory) $?$ : vykonávají své potomky po řadě, dokud první není úspěšný. Selže, pokud neuspěje žádný. Je to takový OR.
Parallel sequence/selector $⇉$ / $???$ : pouští všechny potomky najednou. Vyhodnocení zůstavá stejné.

Decorator / dekorátor: Obaluje nějaký uzel a mění jeho chování.
Filtery: Rozhodují, jestli akci provedou nebo ne, případně až po nějakém čase či s nějakou pravděpodobností. Např. nemusí být žádoucí, aby se agent pořád dokola snažil otevřít dveře.

Strategie a taktika

Řeší rozhodování při nedostatku informací, koordinaci více agentů, plánování, atd.

Waypoints / navigační body

Waypoint je pozice v levelu, která je něčím zajímavá.

Pathfinding nodes: Místa kudy se dá projít.
Tactical locations / rally points: Místa kde se skrýt před útokem, místa ke snipení, místa pro ambush, atd.

Obrázek 16. Tactical locations [2]
Context sensitive locations / závislost na kontextu: Tactical locations mohou záviset na kontextu, třeba pozici protihráčů a jejich chování. Závislost na kontextu je implementována tak, že hodnota waypointu je předpočítána pro několik různých situací, či dodatečnou prací (např. ray castem) za běhu hry.

Taktická analýza

Vyskytuje se primárně ve real-time strategických (RTS) hrách.

Influence maps

Reprezentují aktuální vojenské působení agentů v dané oblasti.
Může být např. dán počtem jednotek a budov a jejich silou.
Upadá se vzdáleností od jednotek.
Používají se k určení toho, které oblasti jsou bezpečné a kterým je lepší se vyhnout, nebo kde jsou nepřátelské hranice nejslabší.

Obrázek 17. Influence map by gamedev.net

Terrain analyses

Podobné waypointům ale pro vnější prostředí. Popisují, jak težké je daným terénem projít, jaká je na něm viditelnost, cover, možnost útect, potenciál ke snipení, atd.

Multi-layer analyses

Informace v taktických analýzách lze rozdělit do tří kategorií:

Statické: např. pozice budov, terén, atd. Dají se předpočítat.
Vyvíjející se / evolving: např. vojenský vliv, zdroje. Počítají se průběžně, ale analýzu lze přerušit.
Dynamické: např. urgentní nebezpečí, dynamické stíny. Počítají se ad hoc za běhu.

Příklad 2. Umístění radaru

Zajímá nás:

Bezpečnost lokace. Nechceme, aby ho hned zničili.
Viditelnost lokace. Čím viditelnější, tím lépší. Je to radar; chce vidět.
Vzdálenost od jiných radarů. Nemá smysl je stavět blízko sebe.

Možné řešení:

Vhodnost = Bezpe \overset{c}{ˇ} nost \cdot Viditelnost \cdot Vzd \overset{a}{ˊ} lenost

Zdroje

[1] PA217 AI for Games
[2] Ian Millington, John Funge: Artificial Intelligence for Games
[3] Steering Behaviors
[4] Navigation System in Unity
[5] Introduction to the A* Algorithm
[6] Sid Meier’s Civilization V
[7] Wikipedia: Monte Carlo method
[8] Wikipedia: Monte Carlo tree search
[9] Wikipedia: Iterative deepening A*