- Decision Trees
- Behavior Networks
- AI Scripting
- Movement Pattern
- Waypoint Movement, Flocking (Tutorial 13)
Decision Trees
Mithilfe von Decision Trees (CDecisionTree) lässt sich der Prozess der Planung und Entscheidungsfindung strukturieren. Ausgehend vom Root-Knoten (der Baumwurzel) repräsentieren alle weiteren Knoten (die sogenannten Leaf-Knoten) die notwendigen
Schritte zur Entscheidungsfindung. Betrachten wir ein Beispiel, bei dem zur Entscheidungsfindung (Angriff, Rückzug oder Mission fortsetzen) drei Entscheidungsschritte notwendig sind:
- Gegner in Reichweite?
- Wenn nicht, dann die Mission fortsetzen / Wenn ja, dann überprüfen, ob das Schiff für einen Angriff gerüstet ist (voll bewaffnet, Schutzschilde auf 100%)
- Wenn ja, dann Angriff einleiten / Wenn nicht, dann Rückzug antreten
// Decision Tree initialisieren:
DecisionTree_Boid_GREEN = new CDecisionTree;
// 3 Knoten: Root, Attack, Retreat
DecisionTree_Boid_GREEN->Init_DecisionNodes(3);
// Decision Tree aufbauen - Verbinden der einzelnen Knoten:
DecisionTree_Boid_GREEN->Set_RootNode(DECISION_NODE_ROOT);
// Jeder Leaf-Knoten repräsentiert eine mögliche Entscheidung:
DecisionTree_Boid_GREEN->Add_LeafNode_To_SelectedNode(
DECISION_NODE_ROOT, DECISION_NODE_ATTACK);
DecisionTree_Boid_GREEN->Add_LeafNode_To_SelectedNode(
DECISION_NODE_ROOT, DECISION_NODE_RETREAT);
[...]
// Verwendung eines Decision Trees:
// Entscheidungen zurücksetzen:
DecisionTree_Boid_RED->Reset_Decision();
DecisionTree_Boid_GREEN->Reset_Decision();
DiffVector = Boid_GREEN->WorldSpacePosition-Boid_RED->WorldSpacePosition;
float distanceSq = D3DXVec3LengthSq(&DiffVector);
if(distanceSq < frnd(25.0f, 40.0))
DecisionTree_Boid_RED->Set_NextDecisionStep(DECISION_NODE_RETREAT);
else
{
// Boid_GREEN fliegt vor Boid_RED
if(D3DXVec3Dot(&DiffVector, &Boid_RED->MovementDirection) > 0.0f)
DecisionTree_Boid_RED->Set_NextDecisionStep(DECISION_NODE_ATTACK);
}
[...]
DecisionTree_Boid_GREEN = new CDecisionTree;
// 3 Knoten: Root, Attack, Retreat
DecisionTree_Boid_GREEN->Init_DecisionNodes(3);
// Decision Tree aufbauen - Verbinden der einzelnen Knoten:
DecisionTree_Boid_GREEN->Set_RootNode(DECISION_NODE_ROOT);
// Jeder Leaf-Knoten repräsentiert eine mögliche Entscheidung:
DecisionTree_Boid_GREEN->Add_LeafNode_To_SelectedNode(
DECISION_NODE_ROOT, DECISION_NODE_ATTACK);
DecisionTree_Boid_GREEN->Add_LeafNode_To_SelectedNode(
DECISION_NODE_ROOT, DECISION_NODE_RETREAT);
[...]
// Verwendung eines Decision Trees:
// Entscheidungen zurücksetzen:
DecisionTree_Boid_RED->Reset_Decision();
DecisionTree_Boid_GREEN->Reset_Decision();
DiffVector = Boid_GREEN->WorldSpacePosition-Boid_RED->WorldSpacePosition;
float distanceSq = D3DXVec3LengthSq(&DiffVector);
if(distanceSq < frnd(25.0f, 40.0))
DecisionTree_Boid_RED->Set_NextDecisionStep(DECISION_NODE_RETREAT);
else
{
// Boid_GREEN fliegt vor Boid_RED
if(D3DXVec3Dot(&DiffVector, &Boid_RED->MovementDirection) > 0.0f)
DecisionTree_Boid_RED->Set_NextDecisionStep(DECISION_NODE_ATTACK);
}
[...]
Behavior Network
Ein Behavior Network CBehaviorNetwork dient zur Simulation der einzelnen Verhaltensweisen eines KI-Objekts. Es besteht aus miteinander verbundenen Netzwerkknoten CBehaviorNode, welche die einzelnen Verhaltensweisen repräsentieren. Die Überganswahrscheinlichkeiten (TransitionProbability) zwischen den einzelnen Knoten repräsentieren das Persönlichkeitsprofil.
// Behavior Network initialisieren:
BehaviorNetwork_Boid_GREEN = new CBehaviorNetwork;
// 3 Zustände: Pattern Movement (geskripteter Bewegungsablauf), Attack,
// Retreat
// Häufige zufällige Verhaltensänderungen sollen vermieden werden, daher
// legen wir möglichst kleine Übergangswahrscheinlichkeiten
// (0.001:1 bis 0.002:1) zwischen den Zuständen fest
BehaviorNetwork_Boid_GREEN->Init_BehaviorNetwork(3, 0.001f, 0.002f);
// Persönlichkeit festlegen:
// Nach einem Rückzug möglichst schnell wieder angreifen:
BehaviorNetwork_Boid_GREEN->Set_BehaviorProbability_From_Node1_To_Node2(
BEHAVIOR_NODE_RETREAT, BEHAVIOR_NODE_ATTACK, 0.025f);
// Angriff einem geskripteten Bewegungsablauf vorziehen:
BehaviorNetwork_Boid_GREEN->Set_BehaviorProbability_From_Node1_To_Node2(
BEHAVIOR_NODE_PATTERN_MOVEMENT, BEHAVIOR_NODE_ATTACK, 0.02f);
// geringe Wahrscheinlichkeit für einen nicht erzwungenen Rückzug:
BehaviorNetwork_Boid_GREEN->Set_BehaviorProbability(
BEHAVIOR_NODE_RETREAT, 0.0001f);
[...]
// Verwendung eines Behavior Networks:
// zufällige Verhaltensänderungen entsprechend des
// Persönlichkeitsprofils ermöglichen:
BehaviorNetwork_Boid_RED->Random_Update_BehaviorNetwork();
BehaviorNetwork_Boid_GREEN->Random_Update_BehaviorNetwork();
[...]
BehaviorNetwork_Boid_GREEN = new CBehaviorNetwork;
// 3 Zustände: Pattern Movement (geskripteter Bewegungsablauf), Attack,
// Retreat
// Häufige zufällige Verhaltensänderungen sollen vermieden werden, daher
// legen wir möglichst kleine Übergangswahrscheinlichkeiten
// (0.001:1 bis 0.002:1) zwischen den Zuständen fest
BehaviorNetwork_Boid_GREEN->Init_BehaviorNetwork(3, 0.001f, 0.002f);
// Persönlichkeit festlegen:
// Nach einem Rückzug möglichst schnell wieder angreifen:
BehaviorNetwork_Boid_GREEN->Set_BehaviorProbability_From_Node1_To_Node2(
BEHAVIOR_NODE_RETREAT, BEHAVIOR_NODE_ATTACK, 0.025f);
// Angriff einem geskripteten Bewegungsablauf vorziehen:
BehaviorNetwork_Boid_GREEN->Set_BehaviorProbability_From_Node1_To_Node2(
BEHAVIOR_NODE_PATTERN_MOVEMENT, BEHAVIOR_NODE_ATTACK, 0.02f);
// geringe Wahrscheinlichkeit für einen nicht erzwungenen Rückzug:
BehaviorNetwork_Boid_GREEN->Set_BehaviorProbability(
BEHAVIOR_NODE_RETREAT, 0.0001f);
[...]
// Verwendung eines Behavior Networks:
// zufällige Verhaltensänderungen entsprechend des
// Persönlichkeitsprofils ermöglichen:
BehaviorNetwork_Boid_RED->Random_Update_BehaviorNetwork();
BehaviorNetwork_Boid_GREEN->Random_Update_BehaviorNetwork();
[...]
if(DecisionTree_Boid_GREEN->Get_Decision() == DECISION_NODE_ATTACK)
BehaviorNetwork_Boid_GREEN->Set_ActualBehaviorNode(
BEHAVIOR_NODE_ATTACK, true/*spätere Verhaltensänderung erlauben*/, true);
else if(DecisionTree_Boid_GREEN->Get_Decision() == DECISION_NODE_RETREAT)
BehaviorNetwork_Boid_GREEN->Set_ActualBehaviorNode(
BEHAVIOR_NODE_RETREAT, true, false/*sofort ausweichen*/);
BehaviorNetwork_Boid_GREEN->Set_ActualBehaviorNode(
BEHAVIOR_NODE_ATTACK, true/*spätere Verhaltensänderung erlauben*/, true);
else if(DecisionTree_Boid_GREEN->Get_Decision() == DECISION_NODE_RETREAT)
BehaviorNetwork_Boid_GREEN->Set_ActualBehaviorNode(
BEHAVIOR_NODE_RETREAT, true, false/*sofort ausweichen*/);
AI Scripting
Handlungsabläufe (Storytelling) werden mithilfe von zeitgesteuerten und getriggerten KI-Skripten realisiert. Während sich die Handlung mithilfe von zeitgesteuerten Ereignissen unabhängig vom Verhalten des Spielers vorantreiben lässt, berücksichtigen getriggerte Ereignisse das augenblickliche Spielgeschehen (Spieler betritt einen bestimmten Bereich, hat eine Aufgabe erfolgreich beendet, usw.).
Verantwortlich für das Einlesen und die Verarbeitung eines KI-Skripts ist die CAIScriptManager-Klasse des Graphics And Physics Frameworks. Mithilfe der vom Skriptmanager unterstützten Funktionen lassen sich die folgenden zeitgesteuerten bzw. Getriggerten Ereignisse realisieren (die konkrete Ausführung muss zuvor im Hauptprogramm implementiert worden sein).
- Spieleobjekt initialisieren und falls gewünscht Positionieren
- Spieleobjekt löschen
- Globales (nicht an ein bestimmtes Objekt gebundenes) Ereignis starten
- Objekt-gebundenes Ereignis starten
- Globale (nicht an ein bestimmtes Objekt gebundene) Nachrichtenausgabe (Sprache, Textnachrichten)
- Objekt-gebundene Nachrichtenausgabe (Bsp. ein Gespräch)
// Skript laden:
AIScriptManager = new CAIScriptManager;
AIScriptManager->Load_Script("../SimpleKIScript.txt");
// Trigger (Auslöser für ein geskriptetes Ereignis) initialisieren:
AIScriptManager->Init_Trigger(4);
// zeitabhängiges Skript starten:;
AIScriptManager = new CAIScriptManager;
AIScriptManager->Load_Script("../SimpleKIScript.txt");
// Trigger (Auslöser für ein geskriptetes Ereignis) initialisieren:
AIScriptManager->Init_Trigger(4);
// zeitabhängiges Skript starten:;
AIScriptManager->Activate_AIScriptedTimeBasedActions(GetTickCount());
[...]
// zeitabhängigen Skriptverlauf updaten:
AIScriptManager->Update_AIScriptedTimeBasedActions();
// zeitabhängige Ereignisse abfragen:
// konkretes Beispiel: überprüfen, ob die Textfarbe geändert werden soll
pAIScript_OutputTimeBased = AIScriptManager->
GetNext_AIScript_OutputTimeBased();
if(pAIScript_OutputTimeBased != NULL) // Textfarbe ändern
DisplayBehaviorStateData = pAIScript_OutputTimeBased->OutputType;
[...]
// triggerbasierten Skriptverlauf updaten:
AIScriptManager->Deactivate_Trigger(TRIGGER_BOID_RED_MOVEMENTPATTERN_0);
AIScriptManager->Deactivate_Trigger(TRIGGER_BOID_RED_MOVEMENTPATTERN_1);
long random = lrnd(0, 2000);
if(random == 5)
{
if(Boid_RED->IDOfUsedMovementPattern == 1)
AIScriptManager->Activate_Trigger(TRIGGER_BOID_RED_MOVEMENTPATTERN_0);
}
else if(random == 6)
{
if(Boid_RED->IDOfUsedMovementPattern == 0)
AIScriptManager->Activate_Trigger(TRIGGER_BOID_RED_MOVEMENTPATTERN_1);
}
[...]
// nacheinander alle geskripteten Ereignisse abarbeiten, die durch die
// einzelnen Trigger gesteuert (aktiviert) werden:
[...]
// zeitabhängigen Skriptverlauf updaten:
AIScriptManager->Update_AIScriptedTimeBasedActions();
// zeitabhängige Ereignisse abfragen:
// konkretes Beispiel: überprüfen, ob die Textfarbe geändert werden soll
pAIScript_OutputTimeBased = AIScriptManager->
GetNext_AIScript_OutputTimeBased();
if(pAIScript_OutputTimeBased != NULL) // Textfarbe ändern
DisplayBehaviorStateData = pAIScript_OutputTimeBased->OutputType;
[...]
// triggerbasierten Skriptverlauf updaten:
AIScriptManager->Deactivate_Trigger(TRIGGER_BOID_RED_MOVEMENTPATTERN_0);
AIScriptManager->Deactivate_Trigger(TRIGGER_BOID_RED_MOVEMENTPATTERN_1);
long random = lrnd(0, 2000);
if(random == 5)
{
if(Boid_RED->IDOfUsedMovementPattern == 1)
AIScriptManager->Activate_Trigger(TRIGGER_BOID_RED_MOVEMENTPATTERN_0);
}
else if(random == 6)
{
if(Boid_RED->IDOfUsedMovementPattern == 0)
AIScriptManager->Activate_Trigger(TRIGGER_BOID_RED_MOVEMENTPATTERN_1);
}
[...]
// nacheinander alle geskripteten Ereignisse abarbeiten, die durch die
// einzelnen Trigger gesteuert (aktiviert) werden:
long i, j;
long NumEvents = AIScriptManager->
AIScriptTrigger[TRIGGER_BOID_RED_MOVEMENTPATTERN_0].
NumObjectEventsTriggered;
for(i = 0; i < NumEvents; i++)
{
// j := Index des getriggerten Ereignisses:
j = AIScriptManager->AIScriptTrigger[
TRIGGER_BOID_RED_MOVEMENTPATTERN_0].
ListOfAIScriptEntries_ObjectEventTriggered[i];
pAIScript_ObjectEventTriggered = AIScriptManager->
Get_AIScript_ObjectEventTriggered(j);
if(pAIScript_ObjectEventTriggered != NULL)
Boid_RED->Select_ActualMovementPattern(0);
}
[...]
Movement Pattern
Bereits in den allerersten Arcade-Games wie Space Invaders wurden die Flugmanöver der Computergegner mithilfe von Movement Pattern (geskriptete Bewegungsabläufe) realisiert. Wie das nachfolgende Beispiel zeigt, lassen sich geskriptete Bewegungsabläufe auch in heutigen Spielen noch sinnvoll einsetzen:
- Treibstoff und Fracht aufnehmen (Wait)
- Raumstation im Mondorbit anfliegen (Move To Position)
- Fracht entladen, Treibstoff und neu Fracht aufnehmen (Wait)
- Raumstation im Erdorbit anfliegen (Move To Position)
// Movement Pattern (geskriptete Bewegungsabläufe) laden:
MovementPatternScript = new CMovementPatternScript;
MovementPatternScript->Load_Script("../MovementPattern0.txt");
Boid_RED->Set_MovementPattern(0, MovementPatternScript);
Boid_GREEN->Set_MovementPattern(0, MovementPatternScript);
MovementPatternScript->Load_Script("../MovementPattern1.txt");
Boid_RED->Set_MovementPattern(1, MovementPatternScript);
Boid_GREEN->Set_MovementPattern(1, MovementPatternScript);
Boid_RED->Select_ActualMovementPattern(0);
Boid_GREEN->Select_ActualMovementPattern(1);
[...]
// Movement Pattern ausführen:
MovementPatternScript = new CMovementPatternScript;
MovementPatternScript->Load_Script("../MovementPattern0.txt");
Boid_RED->Set_MovementPattern(0, MovementPatternScript);
Boid_GREEN->Set_MovementPattern(0, MovementPatternScript);
MovementPatternScript->Load_Script("../MovementPattern1.txt");
Boid_RED->Set_MovementPattern(1, MovementPatternScript);
Boid_GREEN->Set_MovementPattern(1, MovementPatternScript);
Boid_RED->Select_ActualMovementPattern(0);
Boid_GREEN->Select_ActualMovementPattern(1);
[...]
// Movement Pattern ausführen:
CMovementPattern* pPattern = &MovementPattern[IDOfUsedMovementPattern];
long MOVEMENT_PATTERN_ACTION = MovementPatternReader->
Read_Actual_Element(pPattern);
long ActualPatternElement = MovementPatternReader->ActualElement;
if(MOVEMENT_PATTERN_ACTION == MOVEMENT_PATTERN_ACTION_END)
{
MovementPatternReader->Activate_Pattern(pPattern, GetTickCount());
}
else if(MOVEMENT_PATTERN_ACTION ==
MOVEMENT_PATTERN_ACTION_MOVE_IN_DIRECTION ||
MOVEMENT_PATTERN_ACTION ==
MOVEMENT_PATTERN_ACTION_MOVE_IN_RANDOM_DIRECTION)
{
MovementDirectionDesired = pPattern->
MovementPatternStep[ActualPatternElement].MovementDirection;
Update_MovementDirection(precisionOfMovementDirection);
WorldSpacePosition += MovementDirection*
pPattern->MovementPatternStep[ActualPatternElement].MovementVelocity*
g_FrameTime;
}
long MOVEMENT_PATTERN_ACTION = MovementPatternReader->
Read_Actual_Element(pPattern);
long ActualPatternElement = MovementPatternReader->ActualElement;
if(MOVEMENT_PATTERN_ACTION == MOVEMENT_PATTERN_ACTION_END)
{
MovementPatternReader->Activate_Pattern(pPattern, GetTickCount());
}
else if(MOVEMENT_PATTERN_ACTION ==
MOVEMENT_PATTERN_ACTION_MOVE_IN_DIRECTION ||
MOVEMENT_PATTERN_ACTION ==
MOVEMENT_PATTERN_ACTION_MOVE_IN_RANDOM_DIRECTION)
{
MovementDirectionDesired = pPattern->
MovementPatternStep[ActualPatternElement].MovementDirection;
Update_MovementDirection(precisionOfMovementDirection);
WorldSpacePosition += MovementDirection*
pPattern->MovementPatternStep[ActualPatternElement].MovementVelocity*
g_FrameTime;
}
[...]
Hinweise zum Erstellen eines neuen Projekts:
- Kopieren Sie den Ordner GraphicsAndPhysicsFrameworkImports ins Projektverzeichnis
- Kopieren sie alle dll-Dateien sowie die Konfigurationsdatei ResolutionAndRendering.txt aus besagtem Ordner ins gleiche Verzeichnis, in dem sich auch die exe-Datei befindet (in unseren Programmbeispielen ist dies das Bin-Verzeichnis)
- Binden Sie die folgenden Dateien in Ihr Projekt ein: GraphicsAndPhysics_Framework_Imports.h, GraphicsAndPhysics_Framework_Imports.lib, glew32.lib, glew32s.lib, glut32.lib. Die Glew- und Glut-Bibliotheken ermöglichen die Nutzung der aktuellen OpenGL-Spezifikationen unabhängig vom Framework.
GraphicsAndPhysicsFrameworkDemo18.zip