Game AI Flashcards
Was ist ein Steering Behaviour? Welche Steering Behaviours gibt es?
Ein Steering Behaviour sagt aus, wie sich z.B. ein Agent / eine AI mit verhält und physikalisch fortbewegt
Seek, Arrive, Flee, FollowPath, ObstacleAvoidance…
Wie kann AI grundsätzlich Entscheidungen treffen? Über welche Algorithmen oder Datenstrukturen läuft dies?
Decision Trees
State Machines
Behaviour Tree
Goal Orientated Behaviour
Was sind und wie funktionieren Decision Trees?
Eine simple if / else Abfolge, bei der bestimmt wird, welche Aktionen die AI als Nächstes vor hat
Dabei muss beachtet werden, dass der Decision Tree balanciert ist und teure Entscheidungen erst später getroffen werden müssen
Wie funktionieren State Machines im Zusammenhang mit AI Decision Making?
Jeder einzelne Status der AI ist ein eigener State und zwischen den States gibt es Verbindungen - wenn eine AI also von einem State in den anderen geht, muss dies über eine aktive Verbindung geschehen - wenn der Agent in einem State ist, wird das Behaviour dieses States so lange ausgeführt, bis der State verlassen wird
Was ist A*?
A* ist ein Algorithmus zur Ermittlung des potentiell kürzesten Pfads beginnend von einem Startknoten bis hin zu einem Endknoten, ähnlich wie Dijkstra, nur ungenauer und mehr performance-basierter.
Wie funktioniert der A* Algorithmus?
Man beginnt damit, den Anfangsknoten zur “offenen” Liste hinzuzufügen und die ungefähren Manhattan Distanzkosten zum Ziel zu berechnen.
Dann wählt man den Knoten mit den niedrigsten ungefähren Kosten zum Ziel von der “offenen Liste” und fügt alle Nachbarknoten der “offenen Liste” hinzu - wobei von jedem Knoten die ungefähren Kosten zum Ziel berechnet werden. Hierbei muss beachtet werden, im Gegensatz zu Dijkstra können Knoten auf der “geschlossenen” Liste wieder geöffnet werden, wenn die neuen Kosten kleiner als die alten sind.
Alle besuchten Knoten werden von der “offenen Liste” in die “geschlossene Liste” verschoben und dies wird solange gemacht, bis das Ziel gefunden worden ist.
Wieso verwendet man bei A* die Manhattan Distanz anstatt der Euklidischen Distanz?
Um das Rechnen mit Wurzeln zu vermeiden
Der A* Algorithmus findet oft nicht den optimalen Pfad - was sollte man in diesem Fall machen?
Bevor man den Algorithmus beendet, diesen etwas länger laufen lassen, in der Hoffnung, dass ein besserer Pfad noch gefunden wird
Ebenso: im echten Leben wird mit G-Cost (Kosten zum Startknoten) und H-Cost (Kosten zum Endknoten) gerechnet, um dieses Szenario zu umgehen (mit präziseren Berechnungen)
Was ist ein Navigationsgraph? Welche Arten von Navigation Graphen gibt es in Spielen?
Ein Navigation Graph beinhaltet Knoten, die die Navigation in einem Level widerspiegeln
Es gibt…
Tile-basierte Navigationsgraphen
Point of Visibility Navigationsgraphen
Polygonale Mesh Navigationsgraphen
Wie funktioniert der Tile-basierte Navigationsgraph?
Der Tile-basierte Navigationsgraph ist am einfachsten zu implementieren und man kann sich diesen wie das Bucket Tool in Paint vorstellen - es wird via Flood Fill auf der gesamten Map Blöcke definiert, die dann der Navigation dienen
Nachteile davon sind, dass es sehr viele Nodes gibt (je nach Graphdichte) und der Pfad sehr blockig aussieht
Wie funktioniert der Point of Visibility Navigationsgraph?
Der Navigationsgraph besteht aus Sichtbarkeitspunkten im Level, die miteinander verknüpft sind - jeder verbundene Punkt hat freie Sicht auf andere verbundenen Punkte - diese Art von Graph muss per Hand von Level Designern festgelegt werden, wobei die automatische Generation auch möglich wäre
Wie funktioniert der polygonale Mesh Navigationsgraph?
Dieser besteht aus einem Netzwerk von konvexen Polygonen (oft auch mit Dreiecken erstellt) und ist der “standard” in der Gaming Industrie derzeit - dabei muss die Geometrie im Level von einem Level Designer markiert werden (alle begehbaren Bereiche) und eigene Navigationsgeometrie erstellt werden
Warum muss Path Smoothing betrieben werden?
Ein Pfad kann manchmal sehr eckig und kantig wirken, weswegen der ermittelte Pfad immer gesmoothed werden sollte und unnötige Knotenpunkte entfernt werden sollten - smoothing wird auch teilweise schon über Steering Behaviours geregelt
Was sind die Bedingungen für Game AI?
Believable (intelligent, human-like sein)
Challenging (AI sollte den Spieler nicht besiegen, aber diesen herausfordern)
Efficient (AI bekommt typischerweise 5 - 20 % CPU Budget)
Wie ist eine Game AI typischerweise aufgebaut? Welche Komponenten enthält diese?
Typischerweise besteht Game AI aus zwei großen Komponenten - Group AI und Character AI.
Group AI: Strategy
Character AI: Perception, Decision Making, Movement
Was ist mit “Cheating” gemeint bei Game AI?
Game AI, die weiter weg vom Spieler ist, muss nicht das Verhalten 1:1 ausführen, wie sie es tun müsste, wenn nahe beim Spieler - sie kann sozusagen also “cheaten” und muss nicht ihr ganzes Verhalten simulieren (performance sparend)
Was ist Locomotion?
Locomotion definiert, wie ein Objekt sich bewegt –> position += velocity * time;
Locomotion hat Einschränkungen, ist von Kräften beeinflusst und kann sich auf Animationen auswirken
Was ist ein Steering Command?
Die Geschwindigkeit und Bewegung eines Objekts sollte nicht direkt gesetzt werden, sondern durch Kräfte (steering commands) beeinflusst und somit gelenkt werden
Steering Behaviour: Was ist Seek?
Bei Seek folgt der Agent einem Ziel und geht auf dieses direkt zu -> für eine geschmeidigere (smoothere) Bewegung wird der Impulse über eine Zeit lang angewendet, damit der Agent nicht sofort in Richtung des Spielers schaut und sich bewegt, womit ein Arc entsteht
Steering Behaviour: Was ist Arrive?
Bei Arrive bewegt sich der Agent nahe zum Ziel, aber geht nie direkt zum Ziel (hört ab einem gewissen Threshold auf und wird davor schon langsamer)
Steering Behaviour: Was ist Pursue?
Beim Verfolgen eines Ziels wird die Bewegung des Ziels vorhergesehen anhand einer “look ahead time” - die look ahead time wird angepasst je nach Distanz zum Ziel, wenn der Agent nahe beim Evader ist, wird einfach auf das Seek Behaviour zurückgewechselt
Steering Behaviour: Was ist Path Following? Welche Variante gibt es?
Der Agent folgt den im Pfad definierten Punkten und seekt auf diese einfach zu
Wenn nur ein Pfad ohne Punkte definiert ist, kann sich der Agent selbst einen nahegelegenen Punkt am Pfad finden und auf diesen zuseeken - oft wird dies kombiniert mit “weiter nach vorne” sehen am Pfad, damit man nicht direkt auf den Pfad zugeht sondern sich an diesen annähert
Steering Behaviour: Was ist Separation?
Wenn Charaktere zu nahe beieinander stehen, werden Kräfte berechnet, damit sich die Charaktere voneinander entfernen (Stärke der Separation ist abhängig vom Abstand zu anderen Charakteren)
Steering Behaviour: Was ist Obstacle Avoidance?
Der Agent versucht den Objekten vor sich (in einer Cone) auszuweichen - dabei werden Kräfte berechnet, die den Agenten am Objekt vorbeiführen sollten
Steering Behaviour: Was ist Wall Avoidance? Welche Raycasting Verfahren gibt es?
Der Agent casted ständig Rays vor sich, um nicht gegen Wände zu laufen -> wenn eine Wand vom Raycast getroffen wird, wird an Hand der Kollisionsnormale ein neues Ziel berechnet, auf welches sich der Agent zubewegt
Beim Raycasting gibt es verschiedene Ansätze für präzisere Wall Avoidance:
Single Ray Richtung Forward Vektor
Parallel Side Rays um größere Bereiche abzudecken
Whisker Rays (Katzen)
Shape Cast (man verwendet eine Shape für die Kollisionserkennung - sehr teuer)
Steering Behaviour: Was ist Wander?
Der Agent bewegt sich “zufällig” zu Punkten vor sich hin (in einem Kreis), um menschliches Fortbewegen zu simulieren
