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

Editovat
Note

Pohyb, kinematický a dynamický pohyb. Hledání cest, algoritmy prohledávání grafu, A* s jeho datovými strukturami a heuristikami, reprezentace herního světa, hierarchické hledání cest. Rozhodování, rozhodovací stromy, stavové automaty, stromy chování, cílem orientované chování. Taktická a strategická umělá inteligence, navigační body a taktika, taktická analýza. Deskové hry, minimax algoritmy, Monte Carlo prohledávání.

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 nebo .

Orientace

Obvykle v radiánech. Desetinné číslo z intervalu .

Rychlost / velocity

Změna pozice. Vektor nebo .

Úhlová rychlost / angular velocity / "rotace"

Změna rotace. Desetinné číslo z intervalu .

Agent

Postava / objekt / entita vykonávájí pohyb a činící rozhodnutí.

Kinematický pohyb

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

  • Charakter má pozici, orientaci, rychlost a úhlovou rychlost.

  • Nemá zrychlení - rychlost se může měnit okamžitě.

  • Orientace může být počítána podle směru rychlosti.

  • 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);
}
Algoritmy kinematického pohybu
  • Seek: agent se snaží dostat k cíli. (velocity = (target.pos - character.pos).normalized * maxSpeed)

  • Flee: agent se snaží dostat od cíle. (velocity = (character.pos - target.pos).normalized * maxSpeed)

  • Arrival: agent se snaží dostat k cíli a zpomaluje, když je blízko.

  • Wander: agent se hýbe náhodně - náhodně mění rotaci a jde neustále vpřed. (rotation = ranom(0, 1) - random(0, 1) * maxRotation)

Dynamický pohyb

Postavy mění rychlost a zatáčí podle fyzikálních zákonů. Oproti kinematickému pohybu obsahují zrychlení (lineární i úhlové) - plynule zrychlují, dosahují maximální rychlosti a plynule zpomalují.

Ří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). Základními algoritmy jsou:

Seek

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

Seek schematic
Obrázek 1. Seek schematic [3]
Flee

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

Align

Agent se snaží zarovnat svou orientaci s cílem.

Velocity matching

Agent se snaží mít stejnou rychlost jako cíl.

Pomocí těchto základních algoritmů lze vytvořit složitější chování:

Arrival

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

Arrival schematic
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.

Obstacle 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.

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ší.

Cohesion

Agent se snaží být blízko ostatním agentům ve skupině. Jeho target je průměrná pozice blízkých agentů.

Separation

Agent se snaží udržet si odstup od ostatních agentů ve skupině. Jde o Evade, jehož síla je závislá na vzdálenosti od ostatních agentů.

Jednotlivé 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.

    Flocking / chování hejna

    Blenduje 3 chování, díky kterým se agenti drží pohromadě a pohybují se jako hejno.

  • 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.

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

Dvojice , kde je množina uzlů a 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 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 —  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 pro výběr dalšího uzlu k prozkoumání. Kombinuje Dijsktrův algoritmus s greedy best-first hledáním. [5]

vph06 astar
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;
}
Datové struktury pro A*

A* vyžaduje priority queue, která umí rychle vybírat prvek s nejnižší prioritou. Nejjednodušší je implementovat ji pomocí binární haldy. Pokud je však prohledávání na velmi velkém grafu (millions of nodes), lze pro urychlení použít například Bucketed Priority Queue (PBQ). Ta rozdělí uzly do bucketů podle jejich priority - buckety jsou seřazené, ale jejich obsah ne. Pro velký počet uzlů může být PBQ rychlejší díky menšímu počtu operací s pamětí.

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]

vph06 euclidean distance
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).

    vph06 cluster heuristic
    vph06 heuristic comparison
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.

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.

vph06 civilization
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.

vph06 voronoi
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.

vph06 points of visibility
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í.

Navigation System in Unity
Obrázek 7. Navigation System in Unity [4]
vph06 polygonal mesh graph
Obrázek 8. Polygonal mesh graph [2]

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.

vph06 decision trees
Obrázek 9. 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.

vph06 state machine
Obrázek 10. State machine [2]
Hierarchické stavové automaty

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

vph06 hierarchical state machine
Obrázek 11. 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.

vph06 decision tree state machine
Obrázek 12. 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.

vph06 behavior tree
Obrázek 13. Behavior tree [2]
vph06 parallel behavior tree
Obrázek 14. 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) : 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í (např. inverze výsledku, opaková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.

Cílem orientované chování

Charakter má své cíle a snaží se jich dosáhnout za pomoci mnoha různých akcí.

  • Množina cílů, každý cíl má různou prioritu.

  • Množina akcí závyslích na stavu světa (např. podle oběktů v okolí).

    • Akce mohou být atomické (např. sněz jídlo) nebo složené (např. jdi do supermarketu, kup jídlo, vrať se domů, sněz jídlo).

    • Provedené akce ovlivňují cíle (např. když sníme jídlo, změní se priorita cíle "sníst jídlo" na 0).

  • Vybrání nejlepší akce není tak jednoduché.

    • Nejjednodušší je vybrat akci s nejvyšší prioritou. To ale může mít nevyžádané vedlejší efekty (např. mám žízeň, vypiju vodu, počůrám se, protože jsem měl i potřebu jít na záchod).

    • Můžeme určit celkovou nespokojenost na základě všech potřeb a vybrat akci, která ji nejvíce sníží. (Počůrání by zvýšilo nespokojenost, proto se charakter rozhodne jít první na záchod.)

    • Výběr akce by měl zohledňovat i délky jednotlivých akcí a jak se v průběhu času mění priority cílů.

    • Jednou akcí můžu znemožnit jinou. Proto je potřeba plánovat akce dopředu.

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. Do scény je může přidat přímo level designer nebo se mohou generovat automaticky.

vph06 tactical locations
Obrázek 15. 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.

Cover points

Místa, kde se agent může schovat před nepřítelem. Kvalita je závyslá na množství a směru krytí a aktuální pozici nepřítele.

Visibility points

Místa s dobrým výhledem na důležité body v levelu. Visibility point může být zároveň i cover point, ale ne vždy.

Shadow points

Místa ve stínu.

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ší.

  • Pokud strana nemá všechny informace, můžeme vytvořit dvě influence mapy - každou pro jednoho hráče dle jemu dostupných informací.

    vph06 influence maps
    Obrázek 16. 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.

Frag-map

Mapa, která obsahuje hodnoty zabití - pokud agent dostane hit, hodnota klesne, pokud zasáhne nepřítele hodnota stoupne. Dá se předpočátat offline při testování a poté adaptovat za běhu hry.

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í:

Deskové hry

Typicky turn-based hry pro dva hráče, často s perfektní informací.

Perfect information

Od začátku hry jsou známe všechny možnosti a jejich následky.

Imperfect information

Některé informace jsou skryté nebo náhodné, např. karty v ruce, hod kostkou.

Zero-sum games

Hra, kde výhra jednoho hráče je prohrou druhého (např. šachy).

Non-zero-sum games

Výhra jednoho hráče nemusí být prohra druhého, stejně tak prohra jednoho hráče nemusí být výhra druhého (např. kooperativní hry, prisoner’s dilemma).

AI turn-based algoritmy

Algoritmy pro hledání nejlepšího tahu v tahových zero-sum deskových hrách pro dva hráče s perfektní informací.

Game tree

Hru lze reprezentovat jako strom, kde uzly jsou stavy hry a hrany jednotlivé tahy. Listy jsou koncové stavy hry a mají hodnotu (výhru, prohru, remízu). Prohledáváním stromu lze najít nejlepší tah.

  • Branching factor: dán počtem možných tahů v daném stavu.

  • Depth: počet tahů do konce hry.

  • Transposition: do některých stavů se dá dostat více cestami.

Minimax algoritmus

Projdi strom a vyber nejlepší možný tah pro nás s ohledem na to, že soupeř bude volit nejlepší tah pro sebe.

  • Vybíráme nejlepší pozici pro nás - výběr maximální hodnoty.

  • Oponent vybírá nejhorší pozici pro nás - výběr minimální hodnoty.

  • Výběr se opakuje až do listu stromu - koncový stav s danou hodnotou. V případě, že nejsme schopní z časových důvodů prohledat celý strom, můžeme použít heuristiku pro ohodnocení nody (třeba počet a ohodnocení bílích figurek - černých figurek).

    Alpha-beta pruning

    Stromy pro hry jsou obvykle příliš velké na to, aby se daly prohledat celé (tic-tac-toe 9! stavů, šachy > 10^40 stavů). Zároveň ale nepotřebujeme prohledávat části, u kterých víme, že se určitě nestanou. Např. pokud najdeme v maxovi větev s hodnotou 5, nemusíme prohledávat podstrom mina, o kterém víme, že vybere menší hodnotu než 3. Této optimalizaci se říká alpha-beta pruning.

Tip

Minmax i alpha-beta pruning se chápe nejlíp s vizualizací. Můžete kouknout například na Algorithms Explained – minimax and alpha-beta pruning.

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]

  1. Selection: vyber uzel reprezentující stav hry, ze kterého ještě hra neskončila.

  2. Expansion: vytvoř možné volby ze zvoleného tahu.

  3. Simulation: vyber volbu náhodně a odsimuluj hru až do konce.

  4. Backpropagation: aktualizuj statistiky v uzlech na cestě od kořene k listu.

vph06 mcts
Obrázek 17. 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.

kde:

  • je střední hodnota odměny z akce v uzlu . Může být třeba počet výher / počet her.

  • je exploration parameter, který určuje, jak moc se má algoritmus zaměřovat na prozkoumávání nových uzlů.

  • je počet her, ve kterých byl zvolen rodičovský uzel.

  • je počet her, ve kterých byl zvolen uzel .