Share
Een finite-state machine is een model dat wordt gebruikt om de uitvoeringsstroom weer te geven en te regelen. Het is perfect voor het implementeren van AI in games en levert geweldige resultaten op zonder een complexe code. Deze tutorial beschrijft de theorie, implementatie en gebruik van eenvoudige en stack-gebaseerde eindige-toestandsmachines.
Alle pictogrammen gemaakt door Lorc en beschikbaar op http://game-icons.net.
Notitie: Hoewel deze tutorial geschreven is met behulp van AS3 en Flash, zou je in bijna elke game-ontwikkelomgeving dezelfde technieken en concepten moeten kunnen gebruiken.
Een finite-state machine, kortweg FSM, is een berekeningsmodel gebaseerd op een hypothetische machine gemaakt van een of meer toestanden. Alleen een enkele status kan tegelijkertijd actief zijn, dus moet de machine van de ene naar de andere status overschakelen om verschillende acties uit te voeren.
FSM's worden vaak gebruikt om een uitvoeringsstroom te organiseren en te representeren, wat handig is om AI in games te implementeren. Het "brein" van een vijand kan bijvoorbeeld worden geïmplementeerd met behulp van een FSM: elke toestand vertegenwoordigt een actie, zoals aanval of ontwijken:
FSM vertegenwoordigt het brein van een vijand.Een FSM kan worden weergegeven door een grafiek, waarbij de knooppunten de statussen zijn en de randen de overgangen. Elke rand heeft een label dat aangeeft wanneer de transitie moet plaatsvinden, zoals de speler is in de buurt label in de bovenstaande afbeelding, wat aangeeft dat de machine zal overstappen van dwalen naar aanval als de speler in de buurt is.
De implementatie van een FSM begint met de toestanden en overgangen die het zal hebben. Stel je de volgende FSM voor, die de hersenen vertegenwoordigt van een mier met bladeren naar huis:
FSM vertegenwoordigt de hersenen van een mier.Het startpunt is de vind blad toestand, die actief blijft totdat de mier het blad vindt. Wanneer dat gebeurt, wordt de huidige status overgezet naar ga naar huis, die actief blijft tot de mier thuiskomt. Wanneer de mier uiteindelijk thuiskomt, wordt de actieve toestand vind blad nogmaals, dus de mier herhaalt zijn reis.
Als de actieve status is vind blad en de muiscursor nadert de mier, er is een overgang naar de Weglopen staat. Terwijl die status actief is, zal de mier weglopen van de muiscursor. Wanneer de cursor geen bedreiging meer is, is er een overgang terug naar de vind blad staat.
Omdat er overgangen zijn die verbinden vind blad en Weglopen, de mier zal altijd weglopen van de muiscursor wanneer deze dichterbij komt zolang de mier het blad vindt. Dat zal niet gebeuren als de actieve status is ga naar huis (bekijk de figuur hieronder). In dat geval zal de mier onverschrokken naar huis lopen, alleen overgaand naar de vind blad aangeven wanneer het thuiskomt.
FSM vertegenwoordigt de hersenen van een mier. Let op het ontbreken van een overgang tussen 
Accentsconagua
Weglopen en ga naar huis. Een FSM kan worden geïmplementeerd en ingekapseld in een enkele klasse, genaamd FSM bijvoorbeeld. Het idee is om elke status te implementeren als een functie of methode, met behulp van een eigenschap genaamd ActiveState in de klas om te bepalen welke status actief is:
public class FSM private var activeState: Function; // verwijst naar de momenteel actieve statusfunctie public function FSM () public function setState (state: Function): void activeState = state; public function update (): void if (activeState! = null) activeState ();
Omdat elke status een functie is, wordt een specifieke status actief, maar de functie die die staat vertegenwoordigt, wordt elke game-update aangeroepen. De ActiveState eigenschap is een verwijzing naar een functie, dus deze wijst naar de functie van de actieve status.
De bijwerken() methode van de FSM klasse moet elk gameframe worden aangeroepen, zodat het de functie kan oproepen die wordt aangegeven door de ActiveState eigendom. Die oproep zal de acties van de huidige actieve status bijwerken.
De setstate () methode zal de FSM naar een nieuwe staat overbrengen door de ActiveState eigenschap naar een nieuwe toestandsfunctie. De staatsfunctie hoeft geen lid te zijn van FSM; het kan tot een andere klasse behoren, wat het FSM klasse meer generiek en herbruikbaar.
De ... gebruiken FSM klasse al beschreven, is het tijd om het "brein" van een personage te implementeren. De eerder toegelichte mier zal worden gebruikt en bestuurd door een FSM. Het volgende is een weergave van toestanden en overgangen, met de nadruk op de code:
FSM van mierenhersenen met focus op de code.De mier wordt vertegenwoordigd door de Mier klasse, die een eigenschap met de naam heeft hersenen en een methode voor elke staat. De hersenen eigenschap is een instantie van de FSM klasse:
public class Ant public var position: Vector3D; public var velocity: Vector3D; public var brain: FSM; publieke functie Ant (posX: Number, posY: Number) position = new Vector3D (posX, posY); velocity = new Vector3D (-1, -1); brein = nieuwe FSM (); // Vertel de hersenen om op zoek te gaan naar het blad. brain.setState (findLeaf); / ** * De "findLeaf" -status. * Het zorgt ervoor dat de mier naar het blad toe beweegt. * / public function findLeaf (): void / ** * De staat "goHome". * Het maakt de mier naar zijn huis toe. * / public function goHome (): void / ** * De status "runAway". * Het zorgt ervoor dat de mier wegloopt van de muiscursor. * / public function runAway (): void update openbare functie (): void // Update de FSM die het "brein" beheert. Het zal de huidige // active state-functie aanroepen: findLeaf (), goHome () of runAway (). brain.update (); // Pas de snelheidsvector toe op de positie, waardoor de mier beweegt. moveBasedOnVelocity (); (...)
De Mier klasse heeft ook een snelheid en een positie eigenschap, beide gebruikt om de beweging te berekenen met behulp van Euler-integratie. De bijwerken() methode wordt elk gameframe genoemd, dus het werkt de FSM bij.
Om dingen eenvoudig te houden, wordt de code gebruikt om de mier te verplaatsen, zoals moveBasedOnVelocity (), zal worden weggelaten. Meer informatie hierover is te vinden in de Understanding Steering Behaviors-serie.
Hieronder is de implementatie van elke staat, te beginnen met findLeaf (), de staat die verantwoordelijk is voor het geleiden van de mier naar de bladpositie:
public function findLeaf (): void // Verplaats de mier naar het blad. velocity = new Vector3D (Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (afstand (Game.instance.leaf, this) <= 10) // The ant is extremelly close to the leaf, it's time // to go home. brain.setState(goHome); if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) // Mouse cursor is threatening us. Let's run away! // It will make the brain start calling runAway() from // now on. brain.setState(runAway);
De ga naar huis() staat, gebruikt om de mierenwoning te leiden:
publieke functie goHome (): void // Verplaats de mier naar home velocity = new Vector3D (Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (afstand (Game.instance.home, this) <= 10) // The ant is home, let's find the leaf again. brain.setState(findLeaf);
eindelijk, de Weglopen() staat, gebruikt om de mier de muiscursor te laten ontvluchten:
public function runAway (): void // Verplaats de mier weg van de muiscursor velocity = new Vector3D (position.x - Game.mouse.x, position.y - Game.mouse.y); // Is de muiscursor nog steeds in de buurt? if (afstand (Game.mouse, this)> MOUSE_THREAT_RADIUS) // Nee, de muiscursor is verdwenen. Laten we terug gaan om naar het blad te zoeken. brain.setState (findLeaf);
Het resultaat is een mier die wordt bestuurd door de "hersenen" van een FSM:
Mier gecontroleerd door een FSM. Verplaats de muiscursor om de mier te bedreigen.Stel je voor dat de mier ook weg moet rennen van de muiscursor wanneer deze naar huis gaat. De FSM kan worden bijgewerkt naar het volgende:
Ant FSM bijgewerkt met nieuwe overgangen.Het lijkt een triviale wijziging, de toevoeging van een nieuwe overgang, maar het creëert een probleem: als de huidige status is Weglopen en de muiscursor is niet meer in de buurt, welke staat moet de ant-overgang naar: ga naar huis of vind blad?
De oplossing voor dat probleem is een stack-gebaseerde FSM. In tegenstelling tot onze bestaande FSM gebruikt een stack-gebaseerde FSM een stack om staten te beheren. De bovenkant van de stapel bevat de actieve status; overgangen worden afgehandeld door staten uit de stapel te duwen of te laten knallen:
Stack-gebaseerde FSMDe huidige actieve status kan beslissen wat te doen tijdens een overgang:
Overgangen in een stack-gebaseerde FSM: pop zichzelf + push nieuw; pop zelf; duw nieuw.Het kan zichzelf van de stapel verwijderen en een andere staat pushen, wat een volledige overgang betekent (net zoals het simpele FSM deed). Het kan zichzelf uit de stapel verwijderen, wat betekent dat de huidige status voltooid is en de volgende status in de stapel actief moet worden. Ten slotte kan het gewoon een nieuwe status pushen, wat betekent dat de huidige actieve status een tijdje zal veranderen, maar wanneer het zichzelf uit de stapel springt, zal de eerder actieve toestand het opnieuw overnemen.
Een stack-gebaseerde FSM kan worden geïmplementeerd met dezelfde aanpak als voorheen, maar deze keer met behulp van een reeks functie-aanwijzers om de stapel te besturen. De ActiveState eigenschap is niet langer nodig, omdat de bovenkant van de stapel al naar de huidige actieve staat verwijst:
public class StackFSM private var stack: Array; public function StackFSM () this.stack = new Array (); public function update (): void var currentStateFunction: Function = getCurrentState (); if (currentStateFunction! = null) currentStateFunction (); openbare functie popState (): Functie return stack.pop (); openbare functie pushState (status: Functie): void if (getCurrentState ()! = state) stack.push (state); openbare functie getCurrentState (): Functie return stack.length> 0? stack [stack.length - 1]: null;
De setstate () methode is vervangen door twee nieuwe methoden: pushState () en popstate (); pushState () voegt een nieuwe status toe aan de bovenkant van de stapel, terwijl popstate () verwijdert de status boven aan de stapel. Beide methoden schakelen de machine automatisch over naar een nieuwe status, omdat deze de bovenkant van de stapel wijzigen.
Bij het gebruik van een stack-gebaseerde FSM, is het belangrijk om op te merken dat elke staat verantwoordelijk is om zichzelf uit de stapel te verwijderen. Gewoonlijk verwijdert een status zichzelf van de stapel wanneer deze niet langer nodig is, zoals wanneer aanval() is actief, maar het doelwit is net overleden.
In het voorbeeld van de ant zijn slechts een paar wijzigingen nodig om de code aan te passen om een stack-gebaseerde FSM te gebruiken. Het probleem van het niet kennen van de staat om over te stappen, is nu naadloos opgelost dankzij de aard van stack-gebaseerde FSM:
public class Ant (...) public var brain: StackFSM; publieke functie Ant (posX: Number, posY: Number) (...) brain = new StackFSM (); // Vertel de hersenen om op zoek te gaan naar het blad. brain.pushState (findLeaf); (...) / ** * De "findLeaf" -status. * Het zorgt ervoor dat de mier naar het blad toe beweegt. * / public function findLeaf (): void // Verplaats de mier naar het blad. velocity = new Vector3D (Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (afstand (Game.instance.leaf, this) <= 10) // The ant is extremelly close to the leaf, it's time // to go home. brain.popState(); // removes "findLeaf" from the stack. brain.pushState(goHome); // push "goHome" state, making it the active state. if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) // Mouse cursor is threatening us. Let's run away! // The "runAway" state is pushed on top of "findLeaf", which means // the "findLeaf" state will be active again when "runAway" ends. brain.pushState(runAway); /** * The "goHome" state. * It makes the ant move towards its home. */ public function goHome() :void // Move the ant towards home velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) // The ant is home, let's find the leaf again. brain.popState(); // removes "goHome" from the stack. brain.pushState(findLeaf); // push "findLeaf" state, making it the active state if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) // Mouse cursor is threatening us. Let's run away! // The "runAway" state is pushed on top of "goHome", which means // the "goHome" state will be active again when "runAway" ends. brain.pushState(runAway); /** * The "runAway" state. * It makes the ant run away from the mouse cursor. */ public function runAway() :void // Move the ant away from the mouse cursor velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Is the mouse cursor still close? if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) // Nee, de muiscursor is verdwenen. Laten we teruggaan naar de eerdere // actieve status. brain.popState (); (...)
Het resultaat is een mier die in staat is om weg te rennen van de muiscursor, terug te keren naar de eerder actieve status vóór de dreiging:
Mier bestuurd door een stack-gebaseerde FSM. Verplaats de muiscursor om de mier te bedreigen.Finite-state machines zijn handig om AI-logica in games te implementeren. Ze kunnen eenvoudig worden weergegeven met behulp van een grafiek, waardoor een ontwikkelaar het grote geheel kan zien, kan tweaken en het uiteindelijke resultaat kan optimaliseren.
De implementatie van een FSM met functies of methoden om staten te representeren is eenvoudig maar krachtig. Nog complexere resultaten kunnen worden behaald met een stack-gebaseerde FSM, die zorgt voor een beheersbare en beknopte uitvoeringsstroom zonder de code negatief te beïnvloeden. Het is tijd om al je gamevijanden slimmer te maken met behulp van een FSM!
