AI for Games

Syllabus

Introduction and history.
Movement:
- kinematic movement,
- steering behaviors,
- combining steering behaviors.
Search and pathfinding:
- introduction to search algorithms,
- A* data structures and heuristics,
- world representation,
- hierarchical pathfinding.
Decision making for a single character:
- decision trees,
- state machines,
- behavior trees,
- fuzzy logic,
- Markov systems,
- goal-oriented behavior,
- rule-based systems,
- blackboard architectures,
- action execution.
Strategy and tactics:
- tactical waypoints,
- tactical analyses,
- tactical pathfinding,
- coordinated action.
Board games:
- minimaxing,
- transposition tables,
- Monte Carlo search.
Implementation of AI algorithms in Unity.

Introduction and history

What is the Turing test? How would you define artificial intelligence?

Turing test — test schopnosti stroje chovat se jako člověk.
Artificial intelligence — něco, co není člověk, ale dokáže to plnit úkoly jako zvířata a lidi.

What is the difference between academic AI and game AI? What type of questions were studied by them?

Akademická AI se snaží být optimální a nezáleží jí až tak moc na HW, zatímco herní AI se snaží zabavit hráče na běžně dostupném HW.

Discuss early days of AI.

AI před počítači: Co jsou hergot myšlenky? Jak můžeme dát šutrům vědomí?
První počítače: Simulace válek, prolamování šifer.

What were the achievements of AI from 1950 till 1985?

Symbolic artificial intelligence — reprezentuje svět pomocí symbolů, pak s nimi manipuluje a tím "myslí".
Expert systems — symbolický přístup, kdy má AI velkou databázi vědomostí, ze které pomocí pravidel vyvozuje nové závěry.

Discuss important ideas of AI since 1986.

Díky backpropagation se začaly znovu rozvíjet neuronky.
Bayesian Neural Network — učí se pravděpodobnosti jevů na základě trénovacích dat.
Convolutional Neural Network — neuronky na obrázcích.

What ideas are behind AI in the Pac-Man game?

State machine.
Různí duchové, různý cíl pronásledování.
Náhoda na křižovatkách.
Víc důchů dává iluzi složitosti.

What kind of AI features were explored in particular games over the years?

1979: Pac-Man ← state machine
1994: Warcraft ← pathfinding
1997: Goldeneye 007 ← sense simulation system
1998: Warhammer: Dark Omen ← emotional models of soldiers, robust formation motion
1998: Half-Life ← AI characters collaborate with the player
1997-2001: Creatures ← simulated hormone system and NN-based brain
2001: Halo ← decision trees
2005: F.E.A.R. ← goal-oriented action planning

Give examples of the simple things that can look good.

Pac-Man a semi-náhodná rozhodnutí duchů na křižovatkách.

Give examples of the complex things looking bad.

Black and White — hráči omylem naučili NN špatné návyky.

Why the perception window is important?

Hráči obvykle potkávají AI jen chvilkově, což nemusí být dost na to, aby pochopili, jak funguje.

What is important to create an illusion of intelligence?

Že hráč věří, že ta která postava je inteligentní. Takže vizuály, zvuky a animace jsou klíčové.

What kinds of AI can be in games?

Hacky, heuristiky a algoritmy. Pravděpodobně všechny dohromady.

Pathfinding, steering behaviours, state machines, behaviour trees, PRNG, sensorové systémy, machine learning, atd.

Discuss the AI model.

World interface — něco, co AI říká, co v tom světě je.
Animace a fyzika — vnější projevy AI na obrazovce.
Execution management — co dělá AI v runtime.
- Decision making a movement — každé AI za sebe.
- Strategie — interakce více AI jako skupiny.

What type of AI is represented by movement?

Taková, která nemá ranged zbraně a vrhá se na hráče. Taková, která se potřebuje vyhýbat překážkám.

What is decision making in games? Do you know some examples?

Když se AI může rozhodovat mezi více chováními. Třeba kráva se může pást nebo se posunout o půl metru a pást se tam.

What is the role of strategy in games? Do you know some examples?

Ve skupině charakterů se sice každý rozhoduje za sebe, ale s nějakým společným cílem.

Movement

Kinematic movement

Kinematic movement

Věci se prostě hýbou konstantní rychlostí, bez ohledu na fyziku.

What is movement concerned about?

Pohyb postavy v rámci levelu (tedy obvykle ne animace ksichtů).

What dimensions do we consider?

Obvykle jen dvě (a půl), pokud postava vysloveně nelétá.

How is the orientation represented?

Jako úhel / směrový vektor / quaternion.

What are the base kinematic characteristics? What is the difference between kinematic and steering (dynamic) movement algorithms?

Kinematic movement — prostě se hýbou (často jen konstantní rychlostí) a nezajímají se o fyziku.
Dynamic movement — rychlost se mění, zohledňuje i zrychlení a respektuje fyziku (setrvačnost, tření, atd).

How do we update the position?

Za předpokladu, že FPS jsou dostatečně vysoká, tak

position += velocity * delta_time # pozice ve světě
orientation += rotation * delta_time # směr pohledu
velocity += steering.linear * delta_time # rychlost
rotation += steering.angular * delta_time # úhlová rychlost

What is the goal of seeking? How is the kinematic seek implemented?

Otočit postavu směrem k cíli.

velocity = normalize(target.position - position) * max_speed
orientation = atan2(- velocity.x, velocity.z) # dívej se směrem k cíli
rotation = 0

What is the difference between seek, flee, and arrival?

Seek — jde k cíli.
Flee — jde od cíle.
Arrival — jde k cíli, ale zastaví se kousek před ním, aby do něj nevrazil.

How is the kinematic arrival implemented?

vec = target.position - position
if (|vec| >= radius)
    seek

What is wandering? How is the kinematic wandering implemented?

Charakter jde přímo za nosem (orientation).

velocity = orientation.vec * max_speed
rotation = (random(0, 1) - random(0, 1)) * maxRotation # čísla v intervalu (-1, 1) ale nejčastěji kolem 0

Base steering behaviours

Dynamic movement

Zrychlení, tření a podobné srandy.

What are the characteristics of the dynamic movement? What is the goal of matching?

Dynamic movement / steering behaviour — postavy akcelerují a brzdí v souladu s fyzikou.
_Variable matching — vezmeš dvě kinematiky (proměnné), třeba orientaci postavy a orientaci cíle, a snažíš se postavu zarovnat podle cíle.

How is the dynamic position update implemented?

position += velocity * time_delta
orientation += rotation * time_delta
velocity += steering.linear * time_delta # když steering.linear < 0, postava zpomaluje
rotation += steering.angular * time_delta
if (|velocity| > max_speed)
    velocity = normalize(velocity)
    velocity *= max_speed

How is the (dynamic) seek implemented?

steering.linear = max_acceleration * normalize(target.position - character.position)
steering.angular = 0

Compare the base differences in implementations of dynamic behaviors seek, flee, and arrival

Seek — target.position - character.position
Flee — character.position - target.position
Arrival — počítá optimální rychlost.

How is the (dynamic) arrival implemented?

dir = target.position - character.position
if (|dir| < target_radius)
    return

target_speed =|dir| > slow_radius
    ? max_speed
    : max_speed * |dir| / slow_radius

target_velocity = normalize(dir) * target_speed

steering.linear = (target_velocity - character.velocity) / time_to_target

if (|steering.linear| > max_acceleration)
    steering.linear = normalize(steering.linear) * max_acceleration

steering.angular = 0

What is the goal of alignment?

Match the orientation of the character with the orientation of the target.

What is the goal of velocity matching? How is it implemented?

Equalize the velocity of the character with the velocity of the target.

steering.linear = (target_velocity - character.velocity) / time_to_target
if (|steering.linear| > max_acceleration)
    steering.linear = normalize(steering.linear) * max_acceleration

steering.angular = 0

Delegated and combined behaviors

Delegated behaviours

Spočítají target a pak delegují práci seeku & flee, arrivalu nebo velocity matchingu.

Do you know how the pursue behavior can improve over seek?

Předvídá, kde target bude.

Describe the implementation of the pursue behavior.

dir = target.position - character.position
if (speed <= |dir| / max_prediction)
    prediction = max_prediction
else
    prediction = |dir| / speed
seek(target.velocity * prediction)

Describe the face behavior and its implementation.

Chceme, aby se postava dívala na cíl.

dir = target.position - character.position
if (|dir| == 0)
    return

align(atan2(-dir.x, dir.z))

Describe "looking where you’re going" behavior and its implementation.

Chceme, aby se postava dívala ve směru své rychlosti.

if (|character.velocity| == 0)
    return

align(atan2(-character.velocity.x, character.velocity.z))

How can we improve over kinematic wandering?

Randomizovat orientaci místo úhlové rychlosti a započítat orientaci z minulého frameu. Pohyb pak bude méně trhaný.

How is the base path following processed? How can you improve it? Are there any issues?

Najdi bod na křivce, který je postavě nejblíže.
Najdi bod na křivce, který je od toho nejblížšího trochu dál.
Seek.

Predicted path following je plynulejší a řeže zatáčky.

Describe and compare implementations of path following and predictive path following.

# get the parameter of the path nearest the character's position
current_par = path.get_param(character.position)
target.position = path.get_position(current_par + offset)
seek(target.position)

V predictive path following se míto character.position použije future_pos = character.position + character.velocit * predict_time.

Describe separation and cohesion.

Separation — snaha udržovat si daných entit odstup.
Cohesion — snaha shlukovat se s danými entitami.

How could the separation behavior be implemented?

Pokud detekuješ, že entita je moc blíko, pak evade! Evade může mít různou sílu:

lineární: $max_acceleration \cdot \frac{threshold - distance}{threshold}$
inverse square: $min (\frac{decay}{distance ^{2}}, max_acceleration)$

Describe how does obstacle avoidance work. Are there any issues with obstacle avoidance? How would you solve particular cases?

Charakter raycastuje a podle detekovaných překážek modifikuje svůj cíl. Má problémy s úzkými překážkami, délkou rayů a lokálními pastmi.

What is the difference between blending and arbitration?

Blending — kombinuje steering behaviours váženým součtem.
Arbitration — kombinuje steering behaviours tím, že jedno zvolí (a nebo blenduje podmnožinu).

Can you describe some example of a weighted blending?

Dav, co se snaží zůstat v jednom shluku (cohesion), ale zároveň do sebe nenarážet (separation).

What is flocking?

Separation + alignment + cohesion.

Can you describe examples of blending problems?

Equilibria — postava se zasekne mezi dvěma cíli (a ani zaokrouhlovací chyba jí nepomůže).
Constrained environments — nemůže se vyhnout překážkám zatímco někoho pronásleduje, nemůže trefit dveře, nevidí slepé uličky na dlouhé vzdálenosti.

How does the blending with priorities work?

Jednotlivá steering behaviours jsou sdružena do skupin podle priorit. Třeba collision avoidace, seperation a arrive budou ve skupině s nejvyšší prioritou. Pokud vyprodukují jen malý steering, pak se teprve bere v úvahu skupina se seek and evade.

What is formation? And formation motion?

Formation — množina pozic, které mohou postavy ve skupině zaujmout, přičemž jedna z postav jim obvykle velí.
Formation motion — takový pohyb skupiny postav, že zachovává formaci.

Can you describe fixed formations?

Podle velitele se počítají sloty pro ostatní postavy (pomocí nějakého offsetu). Ostatní postavy tak nemusí mít kinematiku ani steering, ale velitel musí brát v úvahu velikost svojí skupiny.

Explain emergent formations.

Každá postava má svůj steering behaviour, ale vybere si jinou postavu, kterou se řídí. Dohromady udělají strom a chovají se jako hejno ptáků.

How do you combine fixed and emergent formation?

Na dvou úrovních, kde na první je leader se svojí fixed formation a na druhé je emergent formation.
Bez velitele ale s anchor pointem, kterým taky můžeme šibovat.

How can we work with slot roles and their assignment?

Ne každý slot je vhodný pro každou postavu. Sloty mohou mít různou cenu pro každou postavu → optimalizační NP-úplný problém.

Pathfinding

Algoritmus A*: Dijkstra + heuristika.
Hierarchical pathfinding: Pathfinding na vícero úrovních scény.

Search algorithms

Why should we combine movement and pathfinding?

Movement je efektivní, ale jen lokální a může se zaseknout. Pathfinding je pomalý ale globální.

What is a search problem? What types of search problems do you know?

Když se snažíš v množině stavů najít nějaký konkrétní stav pomocí nějaké successor funkce.

Obvykle hledání v nějakém grafu.

Define the base terminology related to pathfinding graphs.

State space — množina stavů.
Initial spate — startovní stav.
Goal state — cílový stav.
Set of actions / successor function — možnosti přechodu mezi stavy.
Action cost — cena přechodu / váha hrany.

Describe graph representation using adjacency lists.

$A d j [x] = y ∣ (x, y) \in E$

Describe graph representation using the adjacency matrix.

$E_{ij} = {10 if (i, j) \in E jinak$

How would you represent a tile-based map? What is the waypoint graph?

Záleží na velikosti mapy. U malé mapy je matice gut, u velké not so much.

Waypoint graph — uzly jsou důležitá místa na mapě (ne každý jeden bod), hrany jsou pak cesty bez kolizí.

How is the graph explored by BFS? Describe the implementation of BFS.

Po "vlnách". Má frontu.

How is the graph explored by DFS? Describe the implementation of DFS.

Po "alternativních vesmírech". Má zásobník.

Compare BFS and DFS.

BFS najde nejkratší cestu, DFS najde každou cestu.

Describe the implementation of the Dijkstra algorithm.

How would you implement the Dijkstra algorithm to compute the shortest path for all nodes?

Discuss exploration of the graph on slide 24 using the Dijkstra algorithm.

BFS s prioritní frontou, takže zohledňuje váhy na hranách. Prochází postupně vrcholy a hrany z nich a pokud narazí na "zkratku", tak ji vezme. Tím, že používá prioritní frontu se nemůže stát, že by později narazil na něco, co způsobí "kaskádu" updatů.

The A* algorithm

Compare the differences between BFS, Dijkstra, greedy, and A* algorithms.

BFS — neumí váhy.
Dijkstra — najde nejkratší cestu, ale neumí cykly a trvá mu to dlouho.
Greedy "Best-first" — rychlý, ale nenajde nejkratší cestu.
A* — jako Dijkstra ale pomáhá si k efektivitě heuristikou.

Describe the implementation of the A* algorithm.

astar(source, goal, V, Adj, h)
    // f is the heuristic-enhanced distance to from source to every node
    for (u in V)
        f[u] = Infinity
    v = source
    f[v] = 0
    // g is the true non-heuristic distance from source to every node
    g[v] = 0
    Q = (V, f) // priority min queue on V where f is the priority
    enqueue(Q, v)
    while (v != goal)
        v = dequeue(Q)
        for (u in Adj[v])
            // cost is the actual weight of (v, u)
            new_g = g[v] + cost(v, u)
            if (new_g < g[u])
                g[u] = new_g

            // h is the heuristic
            new_f = g[u] + h(u)
            if (new_f < f[u])
                f[u] = new_f
                update(Q, u, new_f)
                // set parent
                p[u] = v
    return path to goal

What is admissible heuristics? Why is it important? What would happen if the heuristic would overestimate the length of the path to the goal?

A heuristic is admissible ⟺ (\forall v \in V) (h (v) \leq h^{*} (v)),

kde $h^{*}$ je opravdová nejkratší vzdálenost.

Jinými slovy, $h$ nikdy nenadcení cestu k cíli. Je optimistická.

What data structures are needed by the A* algorithm?

Prioritní fronta, seznam sousedností, pár polí.

What is the priority heap? Discuss the complexity of operations.

Prioritní fronta je fronta, kde prvky s (obvykle) nižší prioritou mají přednost. Složitost závisí na implementaci, binární halda má složitost operací (s výjimkou hledání nejmenšího prvku) $O (lo g n)$ .

What are the bucketed priority queues?

Prioritní fronty, kde jsou prvky rozděleny do více malých polí. Pole polí je seřazené, prvky v těch polích ne. Ve hrách to moc užitečné není, ale když máš miliony uzlů, tak to bodne, protože CPU cache.

Compare underestimating and overestimating heuristics for A*.

Podceňující — poběží dýl, ale najde správné řešení.
Nadceňující — bude rychlejší, ale nemusí najít nejkratší cestu.

What are the characteristics of the Euclidian distance heuristics?

Cesta vdušnou čarou.
Je vždy přesná nebo podceňující.
Dobrá v exteriérech, špatná v interiérech.

Describe and discuss cluster heuristic.

Seskupovaní uzlů v clusterech (manuálně, algoritmicky, jako vedlejší produkt level designu). Pro cestu v rámci jednoho clusteru se používá Euklidovská heuristika. Inter-clusterové cestování používá look-up table cest mezi clustery.

World representations

What is the division scheme and what are its properties?

Definuje, jak se z levelu stane graf a obráceně.

Quantization / Localization — pozice hráče → uzel / uzel → pozice ve světě.
Generation — způsob rozdělování prostoru levelu do regionů a spojení.
Validity — každé dva body v dotýkajících se regionech musí mít mezi sebou cestu (v praxi se na to trochu sere).

Describe and discuss tile-based graphs.

2D pole čtvercových regionů (hexagonů, kostek, …). Je jich hrozně moc a neporadí si s částečnou zabraností.

Describe and discuss world representation using Dirichlet domains.

Taky se jim říká Voronoiovy diagramy. Rozmístíš po mape body a necháš je růst. Kvůli pofidérním tvarům se může stát, že cesta mezi dvěma regiony povede přes třetí region, který není průchozí, takže tento přístup není vždy validní. Nicméně, v praxi se ty charakteristické body rozmisťují podle překážek, takže nevalidnost je vzácná.

Describe and discuss points of visibility graph.

Protože optimální cesty skrz prostředí mají body ohybu u konvexních vertexů prostředí (sevřený úhel je menší než 90 stupňů), je výhodné právě tam umístit charakteristické body. Mezi nimi bude hrana, pokud ray cast netrefí překážku. Bodů však může vzniknout příliš mnoho.

Describe and discuss navigation meshes.

Využívá polygony v podlaze jako regiony.

How can we use as cost functions for world representations?

Vzdálenost.
Čas nutný k přechodu.
Viditelnost (reconnaissance).
Obtížnost terénu (tanky).

What is path smoothing? Discuss the algorithm for simple path smoothing.

Pokud se dvě hrany cesty dají sloučit, aniž by postava do nečeho vrazila, tak je sluč. Opakuj, dokud se něco děje.

What is hierarchical pathfinding? How does it work?

Např. nejdřív naji cestu mezi domy, pak teprve od vchodových dveří k ledničce.

Nejdřív clusteruje uzly, pak clusteruje clustery, atd.

How do you compute the distance between clusters using minimum distance? Discuss it for the example.

Optimistický odhad. Minimální vzdálenost mezi dvěma uzly v různých clusterech.

How do you compute the distance between clusters using maximin distance? Discuss it for the example.

Pesimistický odhad. Očekává, že přinejhorším musí postava projít celým regionem.

Najdi tu nejdelší z nezkratších cest mezi libovolným vstupním a libovolným výstupním uzlem z clusteru.
Přičti tuhle cenu k ceně nejkratší cesty mezi dvěma clustery.

How do you compute the distance between clusters using average minimum distance? Discuss it for the example.

Pragmatický odhad. Podobná jeko maximin, ale nebereš maximum, nýbrž aritmetický průměr.

What is the instance graph?

Když máš nějakou budovu milionkrát, tak nemáš pro každou zvlášť pathfinding graf, ale máš jeden graf pro budovu jako takovou a dekorátor, který změní idčka uzlů, aby se tvářily unikátně. Obvykle se předpokládá, že exit node budovy má cenu rovnu 0.

Varianty A*

What does it mean open goal pathfinding? Discuss approaches to solve it.

Rozhodovací logika v pathfindingu. Když chceš náboje, tak tě nemusí nutně zajímat ty nejbližší. Obvykle se někdo jiný rozhodne a pathfindingu předá jen cíl.

What is the interest in dynamic pathfinding? Discuss its solution approaches.

Prostředí se mění, nemusí bý statitické.

D* — přepočítává jen tu část levelu, která se změnila. Vyžaduje však velké množství paměti.
Iterative deepening A* (IDA*)
Simplified memory-bounded A* (SMA*)

Explain IDA* and its properties.

Má cut-off value. Pokud je cena cesty vyšší než cut-off value, zkusí jinou cestu. Pokud nenajde řešení, zvýší cut-off value. Je úplný a optimální, s exponenciální časovou a lineární prostorovou složitostí.

Explain SMA* and its properties.

Fixní limit na počet uvažovaných uzlů. Prostě nimi naplníš paměť, co to jen jde, a doufáš, že to na tu nejkratší cestu bude stačit.

What are the ideas behind interruptible pathfinding?

A* se dá přerušit, takže pokud je pathfinding požadavků mnoho, dají se plánovat.

Why pool of planners is needed?

Protože CPU zvládne jen omezený počet pathfinding požadavků najednou.

Explain vehicle pathfinding as an example of continuous time pathfinding. What graph representation is behind it? How is such pathfinding processed?

Hráče nahání policie. AI policie si musí vybrat, kolik času stráví v kterém pruhu.

Uzly tak představují stavy spíš než pozice v prostoru. Graf se tvoří dynamicky, takže continuous time pathfinding by se měl používat jen velice lokalizovaně a na nejnižším levelu hierarchie. SMA* je dobrá volba.

What is movement planning and why it is used? Explain graph representation behind it

Není tak úplně pathfinding. Spíš je to podobné příkladu s policajty výše. Cílem je naplánovat takovou posloupnost animací, aby se postava dostala, kam má, a zároveň byla posloupnost validní (a vypadala přirozeně).

Describe an example with the walking bipedal character.

Má animace typu: chůze, vstaň, sedni, ukroč, otoč se na místě. Každá animace začne a skončí buď uprostřed chůze nebo v klidovém stání. Naším cílem je najít takovou posloupnost anmimací, abychom se dostali z bodu A do bodu B.

Decision making

What’s going on in decision making? Can you give some examples?: Postava si musí vybrat, co bude dělat, aby splnila svůj cíl. Třeba kráva se může hýbat, pást se, nebo kadit.

Decision trees

What is the decision tree? How do you work with it?: Strom, kde vnitřní uzly jsou podmínky a listy akce. Začneš u kořene a sestupuješ dolů, dokud nedostaneš tu jednu akci, kterou máš provést.
How do you combine decisions using the decision trees?: Zapojíš je do stromu (podobně jako při parsování booleanovských expressions).
Discuss binary and non-binary decision trees.: Nebinární můžou být někdy rychlejší, ale binární se líp reprezentují, existují pro ně cool algoritmy a mají tooling.
Why and how do we use random decision trees?: Rozhodovací stromy jsou moc deterministické → AI vypadá moc jednoduše. Takže se přidá do rozhodování random. Nicméně, proces musí být stabilní. Pokud se příště AI rozhodne jinak, musí to být protože se něco změnilo ve světě.

State machines

Describe the basic state machine using the example. Discuss properties of state machines.

Postavy mají nějaký stav, při přechodech mezi stavy provádí akce. Pokud jsou splněny podmínky pro přechod je přechod triggered. Pokud přejde po přechodu, pak je přechod fired. Přechod může mít entry a exit akce.

Jsou jednoduché.
Je pro ně notace.
Efektivní.
Ale jsou orientované na stav, těžko se v nich implementují cíle.

Why are hierarchical state machines helpful? Can you also explain it on the example from slides?

Občas máš robota, co se musí jít nabít nehledě na to, co právě dělá. Tam se hodí mít vícevrstvý DFA.

Behavior trees

What do leaf nodes represent in behavior trees?

Conditions a actions.

What is selector and sequence in the behavior tree? Give their examples.

Discuss example on slide 6. Think about alternate sequences and selectors on slide 9.

Vnitřní uzly behavior tree. Potomci jsou vyhodnocování ve striktiním pořadí. Selector je efektivně liné ořítko. Sequence je pak líné andítko.

Tip	Přestav si jak to funguje v céčku. Selector skončí u prvního dítěte, co vrátí `true`. Sequence u prvního, co vrátí `false`.

Why are non-deterministic behavior trees helpful? Can you describe it using an example?

Aby to AI vypadalo složitější, než je, tak můžeš potomka vybrat náhodně. Chceš to jen u některých composites.

What are the decorator and filter? Why do you use decorators for a limited resource? Discuss some examples. Discuss guarding resources using decorators.

Decorator — podobně jako v OOP modifikuje jiný uzel, ale zachovává jeho rozhraní. Dají se použít k animacím i k naroubování synchronizace na omezené zdroje (třeba dveře).
Filter — rozhodují se, jestli nechají svého potomka vyhodnotit nebo ne.

When parallel versions of sequence and selector are helpful? Describe it using an example.

Třeba, když mám group AI a chci, aby každý vojáček dělal jinou činnost, ale všichni naráz.

Parallel sequence — zkus všechny děti paralelně, pokud jeden selže, požádej ostatní aby přestali a vrať false.
Prallel selector — zkus všechny děti paralelně, selži, až pokud selžou všichni do jednoho.

Why do we add data to behavior trees? What is the behavior blackboard? Demonstrate it on the example.

Velká kolekce dat, odkud můžou uzly číst a kam můžou psát. Může být globální nebo hierarchická (overriding, yay!)

Hodí se to například, pokud jeden uzel hledá viditelného protivníka, a jiný na něj útočí.

Why and how we reuse behavior trees?

Při vývoji, protože reuse je obvykle efektivnější (co se doby vývoje týče) než přepis.
Za běhu hry, protože pamět je resource a není radno s ní plýtvat.

What do you think about behavior trees? Discuss their limitations.

Je těžké udělat je tak, aby reagovaly rychle. Dají se ale použít interrupter dekorátory nebo zkombinovat s DFA.

Do you have any experiences with the implementation of decision making (in Unity), for example using behavior trees or finite state machines? Can you discuss it?

Z HW. :D

Fuzzy logic

What is the difference between fuzzy sets and normal sets? What are fuzzification and defuzzification?

Do obyčejné množiny prvky buď patří, nebo nepatří. Do fuzzy množiny patří s nějakou "jistotou" z intervalu [0, 1]. Hodí se například v případech, kdy má být postava buď opatrná nebo odvážná — intuitivně by tu mělo být dost prostoru mezi oběma.

Fuzzification — překlad obyčejné příslušnosti (0 / 1) na fuzzy příslušnost ([0, 1]).
Defuzzification — opačný proces.

Describe defuzzification using the highest membership, blending, and center of gravity.

Highest degree of membership — vyber tu množinu, do které patří nejvíc.
Blending — výstupní hodnota bude lineární kombinace hodnot charakteristických pro každou množinu.

Note

$v = \frac{0.2}{s u m} v_{creep} + \frac{0.4}{s u m} v_{walk} + \frac{0.2}{s u m} v_{run}$ , kde $s u m = 0.2 + 0.4 + 0.7$ .
Center of gravity — seřízni funkci každého stavu na hodnotě, kterou prvek má, nanes je na jedny osy a spočítej těžiště plochy pod křivkou.

What fuzzy set operators do you know and how do they work?

AND — průnik ploch funkcí — $min (m_{A}, m_{B})$ .
OR — sjednocení ploch funkcí — $max (m_{A}, m_{b})$ .
NOT — inverze — $1 - m_{A}$ .

What is the fuzzy rule? Can you describe fuzzy rule inference?

IF 'antecedent A' THEN 'consequent B'
Pokud jsme blízko odbočky a jedeme rychle, měli bychom zpomalit.
Crips inputs -Fuzzification→ Fuzzy inputs -Fuzzy rules→ Fuzzy outputs -Defuzzification→ Crisp outputs

Can you explain the fuzzy logic decision making using the example on page 16?

Předpoklady jsou booleanovské výrazy, které se vyhodnocují pomocí fuzzy set operací, výsledek je přiřazen do výstupního stavu za THEN.

Pokud je pro jeden výstupní stav vícero pravidel, pak se ORují, tedy bere se maximum.

Rules
- IF corner-entry AND going-fast THEN brake
- IF corner-exit AND going-fast THEN accelerate
- IF corner-entry AND going-slow THEN acceleerate
- IF corner-exit AND going-slow THEN acceleerate
Inputs
- corner-entry = 0.1
- corner-exit = 0.9
- going-fast = 0.4
- going-slow = 0.6
Results
- brake = min(0.1, 0.4) = 0.1
- accelerate = max(min(0.9, 0.4), min(0.1, 0.6), min(0.9, 0.6))

Why and how do we use the Combs method in fuzzy logic decision making? Discuss it with help of the example from slides.

Combs metods využívá $((p \land q) ⟹ r) ⟺ ((p ⟹ r) \lor (q ⟹ r))$ , aby zabránila kombinatorické explozi v počtu uvažovaných pravidel.

Z IF a_1 AND a_2 AND … AND a_n THEN c, dělá IF a_1 THEN c, IF a_2 THEN c, …, IF a_n THEN c.

What are fuzzy state machines? Discuss it with the help of an example.

Jako state machines, ale všechny stavy s degree of membership (DOM) > 0 jsou aktivní. Každou iteraci:

Procházej všechny aktivní stavy od toho s nejvyšším DOM.
Projdi všechny přechody z aktuálního aktivního stavu a rozhodni jsem mají být fired.
Vytvoř nový seznam aktivních stavů.

Note
Funguje to, protože AND i OR jsou asociativní.

Markov processes

Describe what is the Markov process/non-deterministic state machine.
Discuss on the example from page 24 how can we use Markov processes in games.: Takové stavové stroje, kde se přechází do více stavů najednou. Každý přechod má určitou pravděpodobnost. Iniciálním stavovým vektorem může být třeba (1, 0, 0, 0, 0) pro stavy (start, approach, right, left, jump). Na začátku tak postava je ve stavu start se 100% pravděpodobností. Tyto hodnoty se mění pronásobením transition matrix.

Akce jsou nepřímým důsledkem interpretace stavového vektoru.

Goal-oriented behavior

AI nemusí být jen reaktivní, ale může aktivně chtít něco robiť.

What are goals and actions in goal-oriented behavior? How do they interact?

Goals (Motives) — jez, zabíjej nepřátele, zůstaň naživu. Každý má prioritu (Insistance).
Actions — interakce se světem, které má postava k dispozici.
Akce mění parametry, kterých se goals snaží dosáhnout.
Simple selection — vyber nejdůležitejší goal, vyber akci, která ho nejvíc plní.

Can you explain goal-oriented behavior using the example on page 30?

Goal:   Eat = 4
Goal:   Sleep = 3
Action: Get-Raw-Food (Eat –= 3)
Action: Get-Snack (Eat –= 2)
Action: Sleep-In-Bed (Sleep –= 4)
Action: Sleep-On-Sofa (Sleep –= 2)

Závěr, Eat má nejvyšší insistance, takže vyber Get-Raw-Food, protože to ji sníží nejvíce.

Why and how do we use the overall utility in goal-oriented behavior?

Aby simíci šli na záchod před tím, než se půjdou znova napít.

Global utility (Discontentment, Energy metric) — rovnice udávající celkovou insistance/nespokojenost/energii postavy. Např.: Discontentment = Eat^2 + Bathroom^2, pak si simík rozmyslí, jestli si dá tu limonádu předtím, než půjde na záchod.

How would you add timing into the goal-oriented behavior (GOB)?

Zakomponovat do Discontentment.
Započítat čas přímo do goals a actions (třeba Goal: Eat = 4 + 4 per hour).
Pokaždé, když přijde na řadu vyhodnotit GOB, přepočítej aktuální goals, protože se můžou měnit i méně předvídatelně.

How can we solve goal-oriented planning using search?

Ne všechny akce jde provést kdykoliv (třeba meč jde přibrousit jen před bojem), přístup výše tohle neuvažuje. Můžeme uvažovat sekvenci $k$ akcí, sestavit strom, prohledat ho do hlobky a vybrat tu nejlepší variantu.

Je to jednoduché, ale neefektivní ( $O (n m^{k})$ , kde $n$ je počet goals, $m$ počet dostupných akcí a $k$ počet kroků). Taky nemůže vědět, které akce budou v kterém kroku k dispozici.

Alternativně můžeme simulovat celý svět, nejen naši postavu (a ukládat si do stromu jen diffy). Na to pak aplikovat heuristiky jako "nikdy nevol cestu zvyšující discomfort". Taky můžeme použít A*, jen potřebujeme heuristiku, která určí, jak daleko je svět od toho, aby postava splnila svůj cíl.

How does the smelly goal-oriented behavior work?

Každý způsob, jak může postava dosáhnout svého cíle nějak voní. Zápach se pomalu šíří světem a postava jen čuchá.

Rule-based systems

What do rules look like in rule-based systems? How is the database matching processed?

Tradičně v expertních systémech. Májí podobu IF Conditions THEN Action, třeba IF Whisker.health < 15 AND Whisker.has-radio THEN Sell the radio.

V každé iteraci se změní stav světa a zkontroluje se, která pravidla byla triggnuta. Pravidla mohou používát wildcards (ANYONE, MY), pak jsou unifikováná. Akce mění databázi nepřímo, zejména nemusí uspět. Pravidla mohou měnit ostatní pravidla.

Forward chaining — aplikuj pravidla, dokud se něco mění.

How can we select rules?

Rule arbitration:

First applicable — první možné, je potřeba ho vyřadit na další kolo.
Least recently used — použité nejvíc dávno.
Random.
Most specific condition.
Dynamic priority allocation — priorita pravidel se mění podle situace (když mám málo života, chci lékárničku).

How do you complete processing in a rule-based system using the Rete algorithm? Describe computation using the example on page 9.

Top nodes — patterny v podmínkách.
Join nodes — vnitřní uzly, konjunkce.
Bottom nodes — pravidla, která mohou být aplikována.

Algoritmus:
1. Nasyp world state do top nodes.
2. Matches jsou podsunuty join nodes, u wildcardů si držíš jeden nebo více bindings.
3. Rule arbiter se rozhodne, které z namatchovaných pravidel zvolí.

Blackboard architectures

Why and how do we use blackboard architectures?

Chceme, aby se na svět podívalo vícero expertů. Arbiter vybere experta, ten na tabuli udělá změny a vzdá se kontroly. Vyberou se akce, na kterých se experti shodnou.

What types of actions do you know?

State change — změň nějakou vlastnost na něčem ve hře.
Animations.
Movement.
AI requests — přehoď práci na nižší AI.
Interface commands — zobraz hráči, co se děje.

Discuss interrupting, compound, and scripted actions.

Interrupting — akce trvají nějaký čas, takže je potřeba je umět přerušit, když se objeví důležitější akce.
Compound — koordinace několika akcí dohromady.
Scripted — složité chování, které předpřipravil vývojář.

How is the action specified? How are actions processed by the action manager?

Každá akce má:

expirační dobu,
prioritu,
možnost zkontrolovat, jestli proběhla,
kompatibilitu s jinými akcemi,
schopnost přerušit jiné akce.

Action manager má frontu, kde akce čekají na to, aby byly provedeny.

Tactics

Waypoint tactics

Waypoint uzel v pathfindingu s přidanou taktickou hodnotou.

What is the tactical location?

Waypointy pro taktické situace jako jsou úkryty a pasti.

Discuss primitive and compound tactics.

Primitive properties — krytost, stín, expozice.
Compound tactics — sniper location = cover AND good visibility.

How fuzzy logic is used in continuous tactics?

Taktické vlastnosti jsou spojité, takže se na to fuzzy logika dobře hodí. Nicméně, znamená to vyšší nároky na paměť.

Why is it important to consider the context-sensitivity of tactical locations?

Sniper je k ničemu, když se nepřítel plíží výhradně kanály.

What is the difference between precomputation and raycasting while implementing context-sensitivity?

Precomputation — předpočítáš si třeba, z jakých směrů je úkryt užitečný. Rychlé (za běhu hry).
Raycasting — drahé, děje se za runtimeu hry.

Discuss the importance of particular extensions of tactical locations.

Jednoduché taktické označení.
Context sensitivity.
Spojité taktické hodnoty.
Compound tactics (fuzzy logika).

Why is the simple tactical movement weak?

Používá se decision tree. Postva jen hledá taktický waypoint, až ho potřebuje (protože jí došly náboje). Vůbec nezohledňuje taktické informace při rozhodování. Ten úkryt ani nemusí být dostupný!

Can you show an example of how tactical information can be included in the decision making process?

Viz slide 278.

How can be tactical properties of a waypoint defined?

Manuálně.
Automaticky — uložené v prefabu, předpočítané.

How can be cover points computed?

Střílej (a nebo raycastuj) na bod z mnoha úhlů, výšek postavy, pozic nepřátel. Počítej kolik útoků bylo úspěšných.

How can be visibility points and shadow points computed?

Visibility points — závisí na průměrné délce paprsku vystřeleného z lokace.
Shadow points — bere se světlo z levelu.

How can be waypoints generated automatically?

Pozorováním lidských hráčů.
Zkoušel všechny body, vyřazuj, kodenzuj.

Tactical analyses, tactical pathfinding, coordinated action.

Board games

Game theory
Minimaxing
Transposition tables and memory
Memory-enhanced test algorithms
Monte Carlo tree search