Hur man skapar en spel-AI: en guide för nybörjare

Jag kom över en del intressant material om artificiell intelligens i spel. Med en förklaring av grundläggande saker om AI med enkla exempel, och inuti finns det många användbara verktyg och metoder för dess bekväma utveckling och design. Hur, var och när de ska användas finns också där.

De flesta av exemplen är skrivna i pseudokod, så inga avancerade programmeringskunskaper krävs. Under klippet finns 35 textark med bilder och gifs, så gör dig redo.

UPD. Jag ber om ursäkt, men jag har redan gjort min egen översättning av den här artikeln på Habré PatientZero. Du kan läsa hans version här, men av någon anledning gick artikeln mig förbi (jag använde sökningen, men något gick fel). Och eftersom jag skriver på en blogg dedikerad till spelutveckling, bestämde jag mig för att lämna min version av översättningen till prenumeranter (vissa punkter är formaterade på ett annat sätt, några utelämnades medvetet på råd från utvecklarna).

Vad är AI?

Game AI fokuserar på vilka åtgärder ett objekt ska utföra baserat på förhållandena där det befinner sig. Detta kallas vanligtvis för "intelligent agent", där en agent är en spelarkaraktär, ett fordon, en bot eller ibland något mer abstrakt: en hel grupp av enheter eller till och med en civilisation. I varje fall är det en sak som måste se sin omgivning, fatta beslut utifrån den och agera i enlighet med dem. Detta kallas Sense/Think/Act-cykeln:

• Sense: Agenten hittar eller tar emot information om saker i sin omgivning som kan påverka dess beteende (hot i närheten, föremål att samla in, intressanta platser att utforska).
• Tänk: Agenten bestämmer hur han ska reagera (överväger om det är säkert nog att samla föremål eller om han ska slåss/gömma sig först).
• Agera: agenten utför åtgärder för att implementera det tidigare beslutet (börjar röra sig mot fienden eller objektet).
• ...nu har situationen förändrats på grund av karaktärernas handlingar, så cykeln upprepas med nya data.

AI tenderar att fokusera på Sense-delen av loopen. Till exempel tar autonoma bilar bilder av vägen, kombinerar dem med radar- och lidardata och tolkar dem. Detta görs vanligtvis genom maskininlärning, som bearbetar inkommande data och ger den mening, extraherar semantisk information som "det finns en annan bil 20 meter framför dig." Det är de så kallade klassificeringsproblemen.

Spel behöver inte ett komplext system för att extrahera information eftersom det mesta av data redan är en integrerad del av den. Det finns inget behov av att köra bildigenkänningsalgoritmer för att avgöra om det finns en fiende framför sig – spelet känner redan till och matar in informationen direkt i beslutsprocessen. Därför är Sense-delen av cykeln ofta mycket enklare än Think and Act-delen.

Begränsningar för Game AI

AI har ett antal begränsningar som måste observeras:

• AI behöver inte tränas i förväg, som om det vore en maskininlärningsalgoritm. Det är ingen mening att skriva ett neuralt nätverk under utvecklingen för att övervaka tiotusentals spelare och lära sig det bästa sättet att spela mot dem. Varför? Eftersom spelet inte har släppts och det finns inga spelare.
• Spelet ska vara roligt och utmanande, så agenter ska inte hitta den bästa strategin mot människor.
• Agenter måste se realistiska ut så att spelarna känner att de spelar mot riktiga människor. AlphaGo-programmet överträffade människor, men stegen som valdes var mycket långt ifrån den traditionella förståelsen av spelet. Om spelet simulerar en mänsklig motståndare borde denna känsla inte existera. Algoritmen måste ändras så att den fattar rimliga beslut snarare än idealiska.
• AI måste fungera i realtid. Detta innebär att algoritmen inte kan monopolisera CPU-användning under långa tidsperioder för att fatta beslut. Även 10 millisekunder är för långt, eftersom de flesta spel bara behöver 16 till 33 millisekunder för att göra all bearbetning och gå vidare till nästa grafikram.
• Helst bör åtminstone en del av systemet vara datadrivet, så att icke-kodare kan göra ändringar och justeringar kan ske snabbare.

Låt oss titta på AI-metoder som täcker hela Sense/Think/Act-cykeln.

Att fatta grundläggande beslut

Låt oss börja med det enklaste spelet - Pong. Mål: flytta paddeln så att bollen studsar av den istället för att flyga förbi den. Det är som tennis, där man förlorar om man inte slår bollen. Här har AI en relativt enkel uppgift - att bestämma i vilken riktning plattformen ska flyttas.

Villkorliga uttalanden

För AI i Pong är den mest uppenbara lösningen att alltid försöka placera plattformen under bollen.

En enkel algoritm för detta, skriven i pseudokod:

varje bildruta/uppdatering medan spelet körs:
om bollen är till vänster om paddeln:
flytta paddeln åt vänster
annars om bollen är till höger om paddeln:
flytta paddeln åt höger

Om plattformen rör sig med bollens hastighet är detta den idealiska algoritmen för AI i Pong. Det finns ingen anledning att komplicera något om det inte finns så mycket data och möjliga åtgärder för agenten.

Detta tillvägagångssätt är så enkelt att hela Sense/Think/Act-cykeln knappt märks. Men det finns där:

• Sense-delen är i två om-satser. Spelet vet var bollen är och var plattformen är, så AI ser till den för den informationen.
• Tänk-delen ingår också i de två if-påståendena. De förkroppsligar två lösningar, som i detta fall utesluter varandra. Som ett resultat väljs en av tre åtgärder - flytta plattformen till vänster, flytta den till höger eller gör ingenting om den redan är korrekt placerad.
• Akt-delen finns i satserna Move Paddle Left och Move Paddle Right. Beroende på speldesignen kan de flytta plattformen direkt eller med en viss hastighet.

Sådana tillvägagångssätt kallas reaktiva - det finns en enkel uppsättning regler (i det här fallet om uttalanden i koden) som reagerar på det aktuella tillståndet i världen och vidtar åtgärder.

Beslutsträd

Pong-exemplet är faktiskt likvärdigt med ett formellt AI-koncept som kallas ett beslutsträd. Algoritmen går igenom den för att nå ett "blad" - ett beslut om vilken åtgärd som ska vidtas.

Låt oss göra ett blockschema över beslutsträdet för vår plattforms algoritm:

Varje del av trädet kallas en nod - AI använder grafteori för att beskriva sådana strukturer. Det finns två typer av noder:

• Beslutsnoder: att välja mellan två alternativ baserat på att testa något tillstånd, där varje alternativ representeras som en separat nod.
• Slutnoder: Åtgärden som ska utföras som representerar det slutliga beslutet.

Algoritmen startar från den första noden (trädets "rot"). Den fattar antingen ett beslut om vilken underordnad nod den ska gå till, eller så utför den åtgärden som är lagrad i noden och avslutas.

Vad är fördelen med att ett beslutsträd gör samma jobb som if-uttalandena i föregående avsnitt? Här finns ett generellt system där varje beslut endast har ett villkor och två möjliga utfall. Detta gör att utvecklaren kan skapa AI från data som representerar beslut i ett träd utan att behöva hårdkoda det. Låt oss presentera det i form av en tabell:

På kodsidan får du ett system för att läsa strängar. Skapa en nod för var och en av dem, anslut beslutslogik baserat på den andra kolumnen och underordnade noder baserat på den tredje och fjärde kolumnen. Du behöver fortfarande programmera villkoren och åtgärderna, men nu kommer spelets struktur att bli mer komplex. Här lägger du till ytterligare beslut och åtgärder och anpassar sedan hela AI genom att helt enkelt redigera träddefinitionstextfilen. Därefter överför du filen till speldesignern, som kan ändra beteendet utan att kompilera om spelet eller ändra koden.

Beslutsträd är mycket användbara när de byggs automatiskt från en stor uppsättning exempel (till exempel med ID3-algoritmen). Detta gör dem till ett effektivt och högpresterande verktyg för att klassificera situationer baserat på erhållen data. Men vi går längre än ett enkelt system för agenter att välja åtgärder.

scenarier

Vi analyserade ett beslutsträdssystem som använde förskapade förutsättningar och åtgärder. Personen som designar AI kan organisera trädet hur han vill, men han måste fortfarande lita på kodaren som programmerade allt. Tänk om vi kunde ge designern verktygen att skapa sina egna förutsättningar eller handlingar?

För att programmeraren inte ska behöva skriva kod för villkoren Is Ball Left Of Paddle och Is Ball Right Of Paddle, kan han skapa ett system där designern kommer att skriva villkor för att kontrollera dessa värden. Då kommer beslutsträdets data att se ut så här:

Detta är i huvudsak samma som i den första tabellen, men lösningarna inom sig har sin egen kod, lite som den villkorliga delen av en if-sats. På kodsidan skulle detta läsas i den andra kolumnen för beslutsnoderna, men istället för att leta efter ett specifikt villkor att exekvera (Is Ball Left Of Paddle), utvärderar det det villkorliga uttrycket och returnerar sant eller falskt i enlighet med detta. Detta görs med hjälp av skriptspråket Lua eller Angelscript. Med hjälp av dem kan en utvecklare ta objekt i sitt spel (boll och paddla) och skapa variabler som kommer att finnas tillgängliga i skriptet (ball.position). Dessutom är skriptspråket enklare än C++. Det kräver inte ett fullständigt kompileringssteg, så det är idealiskt för att snabbt justera spellogik och låter "icke-kodare" skapa de nödvändiga funktionerna själva.

I exemplet ovan används skriptspråket endast för att utvärdera det villkorliga uttrycket, men det kan också användas för åtgärder. Till exempel kan data Flytta paddel åt höger bli en skriptsats (ball.position.x += 10). Så att åtgärden också definieras i skriptet, utan att behöva programmera Move Paddle Right.

Du kan gå ännu längre och skriva hela beslutsträdet på ett skriptspråk. Detta kommer att vara kod i form av hårdkodade villkorliga uttalanden, men de kommer att finnas i externa skriptfiler, det vill säga de kan ändras utan att kompilera om hela programmet. Du kan ofta redigera skriptfilen under spelandet för att snabbt testa olika AI-svar.

Händelsesvar

Exemplen ovan är perfekta för Pong. De kör kontinuerligt Sense/Think/Act-cykeln och agerar utifrån det senaste tillståndet i världen. Men i mer komplexa spel måste du reagera på enskilda händelser och inte utvärdera allt på en gång. Pong i det här fallet är redan ett dåligt exempel. Låt oss välja en annan.

Föreställ dig en shooter där fienderna är orörliga tills de upptäcker spelaren, varefter de agerar beroende på deras "specialisering": någon kommer att springa för att "rusa", någon kommer att attackera på långt håll. Det är fortfarande ett grundläggande reaktivt system - "om en spelare blir upptäckt, gör något" - men det kan logiskt delas upp i en Player Seen-händelse och en Reaction (välj ett svar och kör det).

Detta för oss tillbaka till Sense/Think/Act-cykeln. Vi kan koda en Sense-del som kommer att kontrollera varje bildruta om AI ser spelaren. Om inte händer ingenting, men om den ser skapas evenemanget Player Seen. Koden kommer att ha ett separat avsnitt som säger "när Player Seen-händelsen inträffar, gör" var är svaret du behöver för att ta itu med Think och Act-delarna. Således kommer du att ställa in reaktioner på Player Seen-händelsen: för den "rusande" karaktären - ChargeAndAttack, och för prickskytten - HideAndSnipe. Dessa relationer kan skapas i datafilen för snabb redigering utan att behöva kompilera om. Skriptspråk kan också användas här.

Att fatta svåra beslut

Även om enkla reaktionssystem är mycket kraftfulla finns det många situationer där de inte räcker till. Ibland behöver du fatta olika beslut baserat på vad agenten gör just nu, men det är svårt att föreställa sig detta som ett villkor. Ibland finns det för många villkor för att effektivt representera dem i ett beslutsträd eller ett manus. Ibland behöver man i förväg bedöma hur situationen kommer att förändras innan man bestämmer sig för nästa steg. Mer sofistikerade tillvägagångssätt behövs för att lösa dessa problem.

Finite state-maskin

Finite state machine eller FSM (finite state machine) är ett sätt att säga att vår agent för närvarande befinner sig i ett av flera möjliga tillstånd, och att den kan övergå från ett tillstånd till ett annat. Det finns ett visst antal sådana stater – därav namnet. Det bästa exemplet från livet är ett trafikljus. Det finns olika sekvenser av ljus på olika platser, men principen är densamma - varje tillstånd representerar något (stopp, gå, etc.). Ett trafikljus är bara i ett tillstånd vid varje given tidpunkt och flyttar sig från ett till ett annat baserat på enkla regler.

Det är en liknande historia med NPC:er i spel. Låt oss till exempel ta en vakt med följande tillstånd:

• Patrullerar.
• Att attackera.
• Flyr.

Och dessa villkor för att ändra dess tillstånd:

• Om vakten ser fienden anfaller han.
• Om vakten attackerar men inte längre ser fienden, återvänder han för att patrullera.
• Om en vakt attackerar men blir svårt sårad, springer han iväg.

Du kan också skriva if-statement med en väktartillståndsvariabel och olika kontroller: finns det en fiende i närheten, vad är hälsonivån för NPC, etc. Låt oss lägga till några fler tillstånd:

• Sysslolöshet - mellan patrullerna.
• Sökande - när den uppmärksammade fienden har försvunnit.
• Hitta hjälp - när en fiende upptäcks, men är för stark för att slåss ensam.

Valet för var och en av dem är begränsat - till exempel kommer vakten inte att leta efter en dold fiende om han har låg hälsa.

Det finns trots allt en enorm lista med "om" , Den där " kan bli för krångligt, så vi måste formalisera en metod som gör att vi kan hålla tillstånd och övergångar mellan stater i åtanke. För att göra detta tar vi hänsyn till alla stater, och under varje stat skriver vi ner i en lista alla övergångar till andra stater, tillsammans med de villkor som är nödvändiga för dem.

Detta är en tillståndsövergångstabell - ett heltäckande sätt att representera FSM. Låt oss rita ett diagram och få en fullständig översikt över hur NPC-beteendet förändras.

Diagrammet återspeglar kärnan i beslutsfattandet för denna agent baserat på den aktuella situationen. Dessutom visar varje pil en övergång mellan tillstånd om villkoret bredvid den är sant.

Varje uppdatering kontrollerar vi agentens aktuella tillstånd, tittar igenom listan över övergångar, och om villkoren för övergången är uppfyllda, accepterar den det nya tillståndet. Till exempel kontrollerar varje ram om 10-sekunderstimern har gått ut, och i så fall går vakten från tomgångstillstånd till patrullering. På samma sätt kontrollerar den attackerande staten agentens hälsa - om den är låg går den in i den flyende staten.

Detta är att hantera övergångar mellan stater, men hur är det med beteendet som är förknippat med staterna själva? När det gäller att implementera det faktiska beteendet för ett visst tillstånd, finns det vanligtvis två typer av "krok" där vi tilldelar åtgärder till FSM:

• Åtgärder som vi regelbundet utför för det aktuella tillståndet.
• De åtgärder vi vidtar när vi övergår från ett tillstånd till ett annat.

Exempel för den första typen. Tillståndet Patrullering kommer att flytta agenten längs patrullrutten för varje bildruta. Det attackerande tillståndet kommer att försöka initiera en attack varje bildruta eller övergång till ett tillstånd där detta är möjligt.

För den andra typen, överväga övergången "om fienden är synlig och fienden är för stark, gå sedan till läget Hitta hjälp. Agenten måste välja var den ska vända sig för att få hjälp och lagra denna information så att tillståndet Hitta hjälp vet vart det ska gå. När hjälp har hittats går agenten tillbaka till den attackerande staten. Vid det här laget kommer han att vilja berätta för allierade om hotet, så att NotifyFriendOfThreat-åtgärden kan inträffa.

Återigen kan vi titta på detta system genom linsen av Sense/Think/Act-cykeln. Sense finns i data som används av övergångslogiken. Tänk - övergångar tillgängliga i varje stat. Och Act utförs av åtgärder som utförs periodiskt inom en stat eller vid övergångar mellan stater.

Ibland kan det vara kostsamt att kontinuerligt avläsa övergångsförhållanden. Till exempel, om varje agent utför komplexa beräkningar varje bildruta för att avgöra om den kan se fiender och förstå om den kan övergå från patrullerande till attackerande tillstånd, kommer detta att ta mycket CPU-tid.

Viktiga förändringar i världens tillstånd kan ses som händelser som kommer att bearbetas när de inträffar. Istället för att FSM kontrollerar övergångsvillkoret "kan min agent se spelaren?" varje bildruta, kan ett separat system konfigureras för att kontrollera mindre ofta (t.ex. 5 gånger per sekund). Och resultatet är att utfärda Player Seen när checken passerar.

Detta skickas till FSM, som nu ska gå till läget Player Seen-händelse mottagen och svara därefter. Det resulterande beteendet är detsamma förutom en nästan omärklig fördröjning innan svar. Men prestandan har förbättrats som ett resultat av att Sense-delen delas upp i en separat del av programmet.

Hierarkisk finita tillståndsmaskin

Det är dock inte alltid bekvämt att arbeta med stora FSM. Om vi ​​vill utöka attacktillståndet för att separera MeleeAttacking och RangedAttacking, måste vi ändra övergångarna från alla andra tillstånd som leder till Attacking state (nuvarande och framtida).

Du har säkert märkt att i vårt exempel finns det många dubbla övergångar. De flesta övergångar i tomgångstillstånd är identiska med övergångar i patrullerande tillstånd. Det skulle vara trevligt att inte upprepa oss själva, särskilt om vi lägger till fler liknande tillstånd. Det är vettigt att gruppera tomgång och patrullering under den allmänna etiketten "icke-strid", där det bara finns en gemensam uppsättning övergångar till stridsstater. Om vi ​​tänker på denna etikett som en stat, då blir tomgång och patrullering undertillstånd. Ett exempel på att använda en separat övergångstabell för ett nytt icke-stridsunderläge:

Huvudstater:


Status utanför strid:


Och i diagramform:

Det är samma system, men med ett nytt icke-stridstillstånd som inkluderar tomgång och patrullering. Med varje tillstånd som innehåller en FSM med undertillstånd (och dessa undertillstånd i sin tur innehåller sina egna FSMs - och så vidare så länge du behöver), får vi en Hierarchical Finite State Machine eller HFSM (hierarchical finite state machine). Genom att gruppera den icke-stridande staten klipper vi bort ett gäng redundanta övergångar. Vi kan göra detsamma för alla nya stater med gemensamma övergångar. Till exempel, om vi i framtiden utökar Attacking-staten till MeleeAttacking- och MissileAttacking-staterna, kommer de att vara substater som övergår mellan varandra baserat på avstånd till fienden och ammunition. Som ett resultat kan komplexa beteenden och subbeteenden representeras med ett minimum av dubbla övergångar.

Beteendeträd

Med HFSM skapas komplexa kombinationer av beteenden på ett enkelt sätt. Det finns dock en viss svårighet att beslutsfattande i form av övergångsregler är nära relaterat till det nuvarande tillståndet. Och i många spel är det precis vad som behövs. Och noggrann användning av statlig hierarki kan minska antalet övergångsupprepningar. Men ibland behöver du regler som fungerar oavsett vilket tillstånd du befinner dig i, eller som gäller i nästan alla stater. Till exempel, om en agents hälsa sjunker till 25 %, vill du att han ska springa iväg oavsett om han var i strid, ledig eller pratade - du måste lägga till detta tillstånd till varje stat. Och om din designer senare vill ändra den låga hälsotröskeln från 25 % till 10 %, måste detta göras igen.

Helst kräver denna situation ett system där beslut om "vilket tillstånd man ska vara i" ligger utanför staterna själva, för att göra förändringar endast på ett ställe och inte röra övergångsvillkoren. Beteendeträd visas här.

Det finns flera sätt att implementera dem, men essensen är ungefär densamma för alla och liknar ett beslutsträd: algoritmen börjar med en "rot"-nod och trädet innehåller noder som representerar antingen beslut eller åtgärder. Det finns dock några viktiga skillnader:

• Noder returnerar nu ett av tre värden: Lyckades (om jobbet är slutfört), Misslyckades (om det inte kan startas) eller Körs (om det fortfarande körs och det inte finns något slutresultat).
• Det finns inga fler beslutsnoder att välja mellan två alternativ. Istället är de dekorationsnoder, som har en barnnod. Om de lyckas, kör de sin enda underordnade nod.
• Noder som utför åtgärder returnerar ett körvärde för att representera de åtgärder som utförs.

Denna lilla uppsättning noder kan kombineras för att skapa ett stort antal komplexa beteenden. Låt oss föreställa oss HFSM-vakten från föregående exempel som ett beteendeträd:

Med denna struktur bör det inte finnas någon uppenbar övergång från tomgångs-/patrullerande tillstånd till attackerande eller någon annan stat. Om en fiende är synlig och karaktärens hälsa är låg, kommer avrättningen att stanna vid den flyende noden, oavsett vilken nod den tidigare utförde - patrullerande, tomgång, attackerande eller någon annan.

Beteendeträd är komplexa – det finns många sätt att komponera dem, och att hitta rätt kombination av dekoratörer och sammansatta noder kan vara utmanande. Det finns också frågor om hur ofta man ska kontrollera trädet - vill vi gå igenom varje del av det eller bara när ett av förutsättningarna har ändrats? Hur lagrar vi tillstånd för noder - hur vet vi när vi har varit vilande i 10 sekunder, eller hur vet vi vilka noder som kördes förra gången så att vi kan bearbeta sekvensen korrekt?

Det är därför det finns många implementeringar. Till exempel har vissa system ersatt dekoratornoder med inlinedekoratorer. De omvärderar trädet när dekorationsförhållandena ändras, hjälper till att ansluta noder och tillhandahåller regelbundna uppdateringar.

Verktygsbaserat system

Vissa spel har många olika mekaniker. Det är önskvärt att de får alla fördelar med enkla och allmänna övergångsregler, men inte nödvändigtvis i form av ett komplett beteendeträd. Istället för att ha en tydlig uppsättning val eller ett träd med möjliga åtgärder är det lättare att undersöka alla åtgärder och välja den mest lämpliga för tillfället.

Det Utility-baserade systemet hjälper till med just detta. Detta är ett system där agenten har en mängd olika åtgärder och väljer vilka som ska utföras baserat på den relativa nyttan av var och en. Där nyttan är ett godtyckligt mått på hur viktigt eller önskvärt det är för agenten att utföra denna åtgärd.

Den beräknade nyttan av en åtgärd baserat på det aktuella tillståndet och miljön, agenten kan kontrollera och välja det mest lämpliga andra tillståndet när som helst. Detta liknar FSM, förutom där övergångar bestäms av en uppskattning för varje potentiellt tillstånd, inklusive det nuvarande. Observera att vi väljer den mest användbara åtgärden för att gå vidare (eller stanna om vi redan har slutfört den). För mer variation kan detta vara ett balanserat men slumpmässigt urval från en liten lista.

Systemet tilldelar ett godtyckligt intervall av nyttovärden, till exempel från 0 (helt oönskat) till 100 (helt önskvärt). Varje åtgärd har ett antal parametrar som påverkar beräkningen av detta värde. För att återgå till vårt exempel på vår vårdnadshavare:

Övergångar mellan handlingar är tvetydiga - vilket tillstånd som helst kan följa vilket som helst annat. Åtgärdsprioriteringar finns i de returnerade nyttovärdena. Om en fiende är synlig, och den fienden är stark, och karaktärens hälsa är låg, kommer både Fly och FindingHelp att returnera höga värden som inte är noll. I det här fallet kommer FindingHelp alltid att vara högre. På samma sätt ger icke-stridsaktiviteter aldrig mer än 50, så de kommer alltid att vara lägre än stridsaktiviteter. Du måste ta hänsyn till detta när du skapar åtgärder och beräknar deras nytta.

I vårt exempel returnerar åtgärderna antingen ett fast konstant värde eller ett av två fasta värden. Ett mer realistiskt system skulle returnera en uppskattning från ett kontinuerligt värdeintervall. Till exempel, Flyt-åtgärden returnerar högre nyttovärden om agentens hälsa är låg, och Attack-åtgärden returnerar lägre nyttovärden om fienden är för stark. På grund av detta har Flytåtgärden företräde framför Attack i alla situationer där agenten känner att han inte har tillräckligt med hälsa för att besegra fienden. Detta gör att åtgärder kan prioriteras baserat på ett valfritt antal kriterier, vilket gör detta tillvägagångssätt mer flexibelt och variabelt än ett beteendeträd eller FSM.

Varje åtgärd har många villkor för programberäkning. De kan skrivas i skriptspråk eller som en serie matematiska formler. The Sims, som simulerar en karaktärs dagliga rutin, lägger till ett extra lager av beräkningar - agenten får en serie "motivationer" som påverkar nyttobetyg. Om en karaktär är hungrig kommer de att bli ännu hungrigare med tiden, och nyttovärdet för EatFood-åtgärden kommer att öka tills karaktären utför det, vilket minskar hungernivån och återställer EatFood-värdet till noll.

Idén med att välja åtgärder baserat på ett klassificeringssystem är ganska enkel, så ett Utility-baserat system kan användas som en del av AI-beslutsprocesser, snarare än som en komplett ersättning för dem. Beslutsträdet kan begära en nyttoklassificering av två underordnade noder och välja den högre. På liknande sätt kan ett beteendeträd ha en sammansatt Utility-nod för att utvärdera nyttan av åtgärder för att bestämma vilket barn som ska utföras.

Rörelse och navigering

I de tidigare exemplen hade vi en plattform som vi flyttade till vänster eller höger, och en vakt som patrullerade eller attackerade. Men exakt hur hanterar vi agentrörelser över en tidsperiod? Hur ställer vi in ​​hastighet, hur undviker vi hinder och hur planerar vi en rutt när det är svårare att ta sig till en destination än att bara röra oss i en rak linje? Låt oss titta på det här.

Управление

I det inledande skedet kommer vi att anta att varje agent har ett hastighetsvärde, som inkluderar hur snabbt den rör sig och i vilken riktning. Det kan mätas i meter per sekund, kilometer per timme, pixlar per sekund, etc. När vi återkallar Sense/Think/Act-loopen kan vi föreställa oss att Think-delen väljer en hastighet och Act-delen tillämpar den hastigheten på agenten. Vanligtvis har spel ett fysiksystem som gör denna uppgift åt dig, lär dig hastighetsvärdet för varje objekt och justerar det. Därför kan du lämna AI med en uppgift - att bestämma vilken hastighet agenten ska ha. Om du vet var agenten ska vara måste du flytta den i rätt riktning med en inställd hastighet. En mycket trivial ekvation:

önskad_resa = destination_position – agent_position

Föreställ dig en 2D-värld. Agenten är vid punkt (-2,-2), destinationen är någonstans i nordost vid punkt (30, 20), och den erforderliga vägen för agenten att ta sig dit är (32, 22). Låt oss säga att dessa positioner mäts i meter - om vi tar agentens hastighet till 5 meter per sekund, så kommer vi att skala vår förskjutningsvektor och få en hastighet på ungefär (4.12, 2.83). Med dessa parametrar skulle agenten anlända till sin destination på nästan 8 sekunder.

Du kan när som helst räkna om värdena. Om agenten var halvvägs till målet skulle rörelsen vara halva längden, men eftersom agentens maxhastighet är 5 m/s (vi bestämde detta ovan) blir hastigheten densamma. Detta fungerar även för rörliga mål, vilket gör att agenten kan göra små ändringar när de rör sig.

Men vi vill ha mer variation – till exempel att långsamt öka hastigheten för att simulera en karaktär som går från stående till löpande. Samma sak kan göras i slutet innan du stoppar. Dessa funktioner är kända som styrbeteenden, som var och en har specifika namn: Sök, Fly, Ankomst, etc. Tanken är att accelerationskrafter kan appliceras på agentens hastighet, baserat på att jämföra agentens position och aktuella hastighet med destinationen i för att använda olika metoder för att förflytta sig till målet.

Varje beteende har ett lite olika syfte. Sök och ankomst är sätt att flytta en agent till en destination. Hinderundvikande och -separation justerar agentens rörelse för att undvika hinder på vägen mot målet. Anpassning och sammanhållning håller agenter i rörelse. Valfritt antal olika styrbeteenden kan summeras för att producera en enda vägvektor med hänsyn till alla faktorer. En agent som använder beteendena Ankomst, Separation och Hinderundvikande för att hålla sig borta från väggar och andra agenter. Detta tillvägagångssätt fungerar bra på öppna platser utan onödiga detaljer.

Under svårare förhållanden fungerar tillägg av olika beteenden sämre – till exempel kan en agent fastna i en vägg på grund av en konflikt mellan Ankomst och Hinderundvikande. Därför måste du överväga alternativ som är mer komplexa än att bara lägga till alla värden. Sättet är detta: istället för att lägga ihop resultaten av varje beteende kan du överväga rörelse i olika riktningar och välja det bästa alternativet.

Men i en komplex miljö med återvändsgränder och val om vilken väg vi ska gå, kommer vi att behöva något ännu mer avancerat.

Att hitta ett sätt

Styrbeteenden är bra för enkel rörelse på ett öppet område (fotbollsplan eller arena) där att ta sig från A till B är en rak väg med endast mindre omvägar runt hinder. För komplexa rutter behöver vi pathfinding, vilket är ett sätt att utforska världen och bestämma en rutt genom den.

Det enklaste är att applicera ett rutnät på varje ruta bredvid agenten och utvärdera vilka av dem som får flytta. Om en av dem är en destination, följ sedan rutten från varje ruta till den föregående tills du når början. Det här är rutten. Annars upprepar du processen med andra rutor i närheten tills du hittar din destination eller tills du får slut på rutor (vilket betyder att det inte finns någon möjlig väg). Detta är vad som formellt kallas Breadth-First Search eller BFS (breadth-first search algorithm). Vid varje steg tittar han åt alla håll (därav bredd, "bredd"). Sökutrymmet är som en vågfront som rör sig tills den når önskad plats - sökutrymmet expanderar vid varje steg tills slutpunkten ingår, varefter den kan spåras tillbaka till början.

Som ett resultat kommer du att få en lista med rutor längs vilka den önskade rutten sammanställs. Detta är sökvägen (därav sökväg) - en lista över platser som agenten kommer att besöka när han följer destinationen.

Med tanke på att vi känner till positionen för varje ruta i världen kan vi använda styrbeteenden för att förflytta oss längs banan - från nod 1 till nod 2, sedan från nod 2 till nod 3, och så vidare. Det enklaste alternativet är att gå mot mitten av nästa ruta, men ett ännu bättre alternativ är att stanna i mitten av kanten mellan nuvarande ruta och nästa. På grund av detta kommer agenten att kunna skära hörn vid skarpa svängar.

BFS-algoritmen har också nackdelar - den utforskar lika många rutor i "fel" riktning som i "rätt" riktning. Det är här en mer komplex algoritm som kallas A* (A star) kommer in i bilden. Det fungerar på samma sätt, men istället för att blint undersöka grannruta (sedan grannar till grannar, sedan grannar till grannar till grannar och så vidare), samlar den noderna till en lista och sorterar dem så att nästa nod som undersöks alltid är den en som leder till den kortaste vägen. Noder sorteras baserat på en heuristik som tar hänsyn till två saker – "kostnaden" för en hypotetisk rutt till det önskade torget (inklusive eventuella resekostnader) och en uppskattning av hur långt torget är från destinationen (som förargar sökningen i rätt riktning).

Det här exemplet visar att agenten utforskar en ruta i taget och varje gång väljer den intilliggande som är mest lovande. Den resulterande vägen är densamma som BFS, men färre rutor övervägdes i processen - vilket har en stor inverkan på spelets prestanda.

Rörelse utan rutnät

Men de flesta spel är inte upplagda på ett rutnät, och det är ofta omöjligt att göra det utan att offra realism. Kompromisser behövs. Vilken storlek ska rutorna ha? För stora och de kommer inte att kunna representera små korridorer eller svängar korrekt, för små och det kommer att finnas för många rutor att söka efter, vilket i slutändan kommer att ta mycket tid.

Det första att förstå är att ett nät ger oss en graf över anslutna noder. A*- och BFS-algoritmerna fungerar faktiskt på grafer och bryr sig inte om vårt mesh alls. Vi skulle kunna placera noder var som helst i spelvärlden: så länge det finns en koppling mellan två anslutna noder, såväl som mellan start- och slutpunkterna och åtminstone en av noderna, kommer algoritmen att fungera lika bra som tidigare. Detta kallas ofta ett waypointsystem, eftersom varje nod representerar en betydande position i världen som kan vara en del av ett valfritt antal hypotetiska banor.

Exempel 1: en knut i varje ruta. Sökningen startar från noden där agenten finns och slutar vid noden för den önskade kvadraten.

Exempel 2: En mindre uppsättning noder (waypoints). Sökningen startar vid agentens ruta, går igenom det antal noder som krävs och fortsätter sedan till destinationen.

Detta är ett helt flexibelt och kraftfullt system. Men viss försiktighet behövs för att bestämma var och hur en waypoint ska placeras, annars kanske agenter helt enkelt inte ser den närmaste punkten och kommer inte att kunna starta vägen. Det skulle vara lättare om vi automatiskt kunde placera waypoints baserat på världens geometri.

Det är här navigeringsnätet eller navmesh (navigationsnät) visas. Detta är vanligtvis ett 2D-nät av trianglar som är överlagrat på världens geometri - varhelst agenten tillåts gå. Var och en av trianglarna i nätet blir en nod i grafen och har upp till tre intilliggande trianglar som blir intilliggande noder i grafen.

Den här bilden är ett exempel från Unity-motorn - den analyserade geometrin i världen och skapade ett navmesh (i skärmdumpen i ljusblått). Varje polygon i ett navmesh är ett område där en agent kan stå eller flytta från en polygon till en annan polygon. I det här exemplet är polygonerna mindre än våningarna de är placerade på - detta görs för att ta hänsyn till storleken på agenten, som kommer att sträcka sig bortom dess nominella position.

Vi kan söka efter en rutt genom detta mesh, återigen med hjälp av A*-algoritmen. Detta kommer att ge oss en nästan perfekt rutt i världen, som tar hänsyn till all geometri och inte kräver onödiga noder och skapande av waypoints.

Pathfinding är ett för brett ämne för vilket ett avsnitt i en artikel inte räcker. Om du vill studera det mer i detalj, kommer detta att hjälpa Amit Patels hemsida.

planering

Vi har lärt oss med pathfinding att ibland räcker det inte att bara välja en riktning och flytta – vi måste välja en rutt och göra några svängar för att komma till vår önskade destination. Vi kan generalisera denna idé: att uppnå ett mål är inte bara nästa steg, utan en hel sekvens där du ibland behöver se framåt flera steg för att ta reda på vad det första ska vara. Detta kallas planering. Pathfinding kan ses som en av flera förlängningar av planering. När det gäller vår Sense/Think/Act-cykel är det här som Think-delen planerar flera Act-delar för framtiden.

Låt oss titta på exemplet med brädspelet Magic: The Gathering. Vi går först med följande uppsättning kort i våra händer:

• Swamp - Ger 1 svart mana (landkort).
• Skog - ger 1 grön mana (landkort).
• Fugitive Wizard - Kräver 1 blå mana för att kalla.
• Elvish Mystic - Kräver 1 grön mana för att kalla.

Vi ignorerar de återstående tre korten för att göra det lättare. Enligt reglerna får en spelare spela 1 landkort per tur, han kan "knacka" på detta kort för att extrahera mana från det, och sedan kasta trollformler (inklusive kalla en varelse) enligt mängden mana. I den här situationen vet den mänskliga spelaren att han ska spela Forest, trycka på 1 grön mana och sedan kalla på Elvish Mystic. Men hur kan spelets AI ta reda på detta?

Enkel planering

Det triviala tillvägagångssättet är att prova varje åtgärd i tur och ordning tills det inte finns några lämpliga kvar. Genom att titta på korten ser AI:n vad Swamp kan spela. Och han spelar det. Finns det några andra åtgärder kvar denna sväng? Den kan inte tillkalla vare sig Elvish Mystic eller Fugitive Wizard, eftersom de kräver grön respektive blå mana för att tillkalla dem, medan Swamp bara tillhandahåller svart mana. Och han kommer inte längre att kunna spela Forest, eftersom han redan har spelat Swamp. Således följde spelet AI reglerna, men gjorde det dåligt. Kan förbättras.

Planering kan hitta en lista över åtgärder som för spelet till önskat tillstånd. Precis som varje ruta på en stig hade grannar (vid vägsökning), har varje åtgärd i en plan också grannar eller efterföljare. Vi kan leta efter dessa åtgärder och efterföljande åtgärder tills vi når önskat tillstånd.

I vårt exempel är det önskade resultatet "kalla en varelse om möjligt." I början av omgången ser vi bara två möjliga handlingar tillåtna enligt spelets regler:

1. Spela Swamp (resultat: Swamp i spelet)
2. Spela Skog (resultat: Skog i spelet)

Varje åtgärd som vidtas kan leda till ytterligare handlingar och stänga andra, igen beroende på spelets regler. Föreställ dig att vi spelade Swamp - detta tar bort Swamp som nästa steg (vi har redan spelat det), och detta tar också bort Forest (eftersom du enligt reglerna kan spela ett landkort per tur). Efter detta lägger AI till att få 1 svart mana som nästa steg eftersom det inte finns några andra alternativ. Om han går vidare och väljer Tap the Swamp, kommer han att få 1 enhet svart mana och kommer inte att kunna göra något med den.

1. Spela Swamp (resultat: Swamp i spelet)
1.1 "Tap" Swamp (resultat: Swamp "tapped", +1 enhet svart mana)
Inga åtgärder tillgängliga - END
2. Spela Skog (resultat: Skog i spelet)

Listan över åtgärder var kort, vi kom till en återvändsgränd. Vi upprepar processen för nästa steg. Vi spelar Forest, öppnar åtgärden "få 1 grön mana", som i sin tur kommer att öppna den tredje åtgärden - kalla på Elvish Mystic.

1. Spela Swamp (resultat: Swamp i spelet)
1.1 "Tap" Swamp (resultat: Swamp "tapped", +1 enhet svart mana)
Inga åtgärder tillgängliga - END
2. Spela Skog (resultat: Skog i spelet)
2.1 "Tapp" Forest (resultat: Skogen "tappas", +1 enhet grön mana)
2.1.1 Summon Elvish Mystic (resultat: Elvish Mystic i spel, -1 grön mana)
Inga åtgärder tillgängliga - END

Slutligen undersökte vi alla möjliga åtgärder och hittade en plan som kallar fram en varelse.

Detta är ett mycket förenklat exempel. Det är tillrådligt att välja den bästa möjliga planen, snarare än bara vilken plan som helst som uppfyller vissa kriterier. Det är i allmänhet möjligt att utvärdera potentiella planer baserat på resultatet eller den totala nyttan av deras genomförande. Du kan få dig själv 1 poäng för att spela ett landkort och 3 poäng för att kalla fram en varelse. Att spela Swamp skulle vara en 1 poäng plan. Och att spela Skog → Tryck på Skogen → kalla på Elvish Mystic ger omedelbart 4 poäng.

Så fungerar planering i Magic: The Gathering, men samma logik gäller i andra situationer. Till exempel att flytta en bonde för att göra plats för biskopen att röra sig i schack. Eller ta skydd bakom en vägg för att säkert fotografera i XCOM så här. I allmänhet förstår du idén.

Förbättrad planering

Ibland finns det för många potentiella åtgärder för att överväga alla möjliga alternativ. För att återgå till exemplet med Magic: The Gathering: låt oss säga att i spelet och i din hand finns det flera land- och varelsekort - antalet möjliga kombinationer av drag kan vara i dussintals. Det finns flera lösningar på problemet.

Den första metoden är kedja bakåt. Istället för att prova alla kombinationer är det bättre att börja med det slutliga resultatet och försöka hitta en direkt väg. Istället för att gå från trädets rot till ett specifikt blad, rör vi oss i motsatt riktning - från bladet till roten. Denna metod är enklare och snabbare.

Om fienden har 1 hälsa kan du hitta planen "deal 1 or more damage". För att uppnå detta måste ett antal villkor vara uppfyllda:

1. Skador kan orsakas av en besvärjelse - den måste vara i handen.
2. För att besvärja behöver du mana.
3. För att få mana måste du spela ett landkort.
4. För att spela ett landkort måste du ha det på handen.

Ett annat sätt är bäst-först-sökning. Istället för att prova alla vägar väljer vi den lämpligaste. Oftast ger denna metod den optimala planen utan onödiga sökkostnader. A* är en form av bästa första sökning - genom att undersöka de mest lovande rutterna från början kan den redan hitta den bästa vägen utan att behöva kontrollera andra alternativ.

Ett intressant och allt mer populärt bästa-första-sökalternativ är Monte Carlo Tree Search. Istället för att gissa vilka planer som är bättre än andra när man väljer varje efterföljande åtgärd, väljer algoritmen slumpmässiga efterföljare vid varje steg tills den når slutet (när planen resulterade i seger eller nederlag). Det slutliga resultatet används sedan för att öka eller minska vikten av tidigare alternativ. Genom att upprepa denna process flera gånger i rad ger algoritmen en bra uppskattning av vad det bästa nästa draget är, även om situationen förändras (om fienden vidtar åtgärder för att störa spelaren).

Ingen berättelse om planering i spel skulle vara komplett utan målorienterad handlingsplanering eller GOAP (målorienterad handlingsplanering). Detta är en mycket använd och diskuterad metod, men förutom några få utmärkande detaljer är det i huvudsak den bakåtkedjemetoden vi pratade om tidigare. Om målet var att "förstöra spelaren" och spelaren är bakom skydd, kan planen vara: förstöra med en granat → hämta den → kasta den.

Det finns vanligtvis flera mål, var och en med sin egen prioritet. Om det högsta prioriterade målet inte kan fullföljas (ingen kombination av åtgärder skapar en "döda spelaren"-plan eftersom spelaren inte är synlig), kommer AI:n att falla tillbaka till lägre prioriterade mål.

Träning och anpassning

Vi har redan sagt att spel AI vanligtvis inte använder maskininlärning eftersom det inte är lämpligt för att hantera agenter i realtid. Men det betyder inte att du inte kan låna något från detta område. Vi vill ha en motståndare i en skytt som vi kan lära oss något av. Ta till exempel reda på de bästa positionerna på kartan. Eller en motståndare i ett fightingspel som skulle blockera spelarens ofta använda kombinationsrörelser och motivera honom att använda andra. Så maskininlärning kan vara ganska användbar i sådana situationer.

Statistik och sannolikheter

Innan vi går in på komplexa exempel, låt oss se hur långt vi kan gå genom att ta några enkla mätningar och använda dem för att fatta beslut. Till exempel realtidsstrategi - hur avgör vi om en spelare kan starta en attack under de första minuterna av spelet och vilket försvar för att förbereda sig mot detta? Vi kan studera en spelares tidigare erfarenheter för att förstå vilka framtida reaktioner kan vara. Till att börja med har vi inte sådana rådata, men vi kan samla in dem - varje gång AI:n spelar mot en människa kan den registrera tiden för den första attacken. Efter några sessioner kommer vi att få ett snitt av den tid det tar för spelaren att anfalla i framtiden.

Det finns också ett problem med genomsnittliga värden: om en spelare rusade 20 gånger och spelade långsamt 20 gånger, kommer de nödvändiga värdena att vara någonstans i mitten, och detta kommer inte att ge oss något användbart. En lösning är att begränsa indata - de sista 20 bitarna kan tas med i beräkningen.

Ett liknande tillvägagångssätt används när man uppskattar sannolikheten för vissa handlingar genom att anta att spelarens tidigare preferenser kommer att vara desamma i framtiden. Om en spelare attackerar oss fem gånger med eldboll, två gånger med blixt och en gång med närstrid, är det uppenbart att han föredrar eldboll. Låt oss extrapolera och se sannolikheten att använda olika vapen: eldklot=62,5%, blixt=25% och närstrid=12,5%. Vårt spel-AI måste förbereda sig för att skydda sig mot eld.

En annan intressant metod är att använda Naive Bayes Classifier för att studera stora mängder indata och klassificera situationen så att AI:n reagerar på önskat sätt. Bayesianska klassificerare är mest kända för sin användning i spamfilter för e-post. Där undersöker de orden, jämför dem med var de orden har förekommit tidigare (i skräppost eller inte), och drar slutsatser om inkommande e-postmeddelanden. Vi kan göra samma sak även med färre input. Baserat på all användbar information som AI ser (som vilka fiendeenheter som skapas, eller vilka trollformler de använder, eller vilka tekniker de undersökte), och det slutliga resultatet (krig eller fred, rusa eller försvara, etc.) - vi kommer att välja önskat AI-beteende.

Alla dessa träningsmetoder är tillräckliga, men det är tillrådligt att använda dem baserat på testdata. AI:n kommer att lära sig att anpassa sig till de olika strategier som dina speltestare har använt. AI som anpassar sig till spelaren efter release kan bli för förutsägbar eller för svår att besegra.

Värdebaserad anpassning

Med tanke på innehållet i vår spelvärld och reglerna kan vi ändra uppsättningen av värden som påverkar beslutsfattande, snarare än att bara använda indata. Vi gör så här:

• Låt AI:n samla in data om världens tillstånd och viktiga händelser under spelet (enligt ovan).
• Låt oss ändra några viktiga värden baserat på dessa data.
• Vi implementerar våra beslut baserat på att bearbeta eller utvärdera dessa värderingar.

En agent har till exempel flera rum att välja mellan på en förstapersonsskjutarkarta. Varje rum har sitt eget värde, som avgör hur önskvärt det är att besöka. AI:n väljer slumpmässigt vilket rum den ska gå till baserat på värdet. Agenten kommer då ihåg vilket rum han dödades i och minskar dess värde (sannolikheten att han kommer tillbaka dit). På samma sätt för den omvända situationen - om agenten förstör många motståndare, ökar rummets värde.

Markov modell

Vad händer om vi använde den insamlade informationen för att göra förutsägelser? Om vi ​​kommer ihåg varje rum vi ser en spelare i under en viss tid, kommer vi att förutsäga vilket rum spelaren kan gå till. Genom att spåra och registrera spelarens rörelser över rum (värden) kan vi förutsäga dem.

Låt oss ta tre rum: röd, grön och blå. Och även observationerna som vi spelade in när vi tittade på spelsessionen:

Antalet observationer i varje rum är nästan lika stort - vi vet fortfarande inte var vi ska göra en bra plats för ett bakhåll. Att samla in statistik kompliceras också av återuppbyggnaden av spelare, som visas jämnt över hela kartan. Men uppgifterna om nästa rum de kommer in efter att ha dykt upp på kartan är redan användbara.

Det kan ses att det gröna rummet passar spelarna – de flesta flyttar från det röda rummet till det, varav 50 % är kvar där längre. Det blå rummet, tvärtom, är inte populärt; nästan ingen går till det, och om de gör det stannar de inte länge.

Men uppgifterna säger oss något viktigare - när en spelare är i ett blått rum kommer nästa rum vi ser honom i att vara rött, inte grönt. Även om det gröna rummet är mer populärt än det röda rummet förändras situationen om spelaren är i det blå rummet. Nästa tillstånd (dvs rummet spelaren kommer att gå till) beror på det tidigare tillståndet (dvs rummet spelaren befinner sig i). Eftersom vi utforskar beroenden kommer vi att göra mer exakta förutsägelser än om vi helt enkelt räknade observationer oberoende av varandra.

Att förutsäga ett framtida tillstånd baserat på data från ett tidigare tillstånd kallas en Markov-modell, och sådana exempel (med rum) kallas Markov-kedjor. Eftersom mönstren representerar sannolikheten för förändringar mellan på varandra följande tillstånd, visas de visuellt som FSM med en sannolikhet runt varje övergång. Tidigare använde vi FSM för att representera beteendetillståndet som en agent var i, men detta koncept sträcker sig till alla tillstånd, oavsett om det är associerat med agenten eller inte. I det här fallet representerar staterna rummet som agenten upptar:

Detta är ett enkelt sätt att representera den relativa sannolikheten för tillståndsförändringar, vilket ger AI:n en viss förmåga att förutsäga nästa tillstånd. Du kan förutse flera steg framåt.

Om en spelare är i green room är det 50 % chans att han stannar där nästa gång han observeras. Men vad är chansen att han fortfarande kommer att vara där även efter? Det finns inte bara en chans att spelaren stannade kvar i green room efter två observationer, utan det finns också en chans att han lämnade och återvände. Här är den nya tabellen som tar hänsyn till de nya uppgifterna:

Den visar att chansen att se spelaren i det gröna rummet efter två observationer kommer att vara lika med 51 % - 21 % att han kommer från det röda rummet, 5 % av dem att spelaren kommer att besöka det blå rummet mellan dem, och 25% som spelaren inte kommer att lämna green room.

Tabellen är helt enkelt ett visuellt verktyg - proceduren kräver bara att man multiplicerar sannolikheterna vid varje steg. Det betyder att du kan se långt in i framtiden med en varning: vi antar att chansen att komma in i ett rum helt beror på det aktuella rummet. Detta kallas Markov Property - det framtida tillståndet beror bara på nuet. Men detta är inte hundra procent korrekt. Spelare kan ändra beslut beroende på andra faktorer: hälsonivå eller mängd ammunition. Eftersom vi inte registrerar dessa värden blir våra prognoser mindre exakta.

N-gram

Hur är det med exemplet med ett fightingspel och att förutsäga spelarens kombinationsrörelser? Det samma! Men istället för ett tillstånd eller en händelse kommer vi att undersöka hela sekvensen som utgör en kombinationsstrik.

Ett sätt att göra detta är att lagra varje ingång (som Kick, Punch eller Block) i en buffert och skriva hela bufferten som en händelse. Så spelaren trycker upprepade gånger på Kick, Kick, Punch för att använda SuperDeathFist-attacken, AI-systemet lagrar alla ingångar i en buffert och kommer ihåg de tre senaste som användes i varje steg.

(Raderna i fet stil är när spelaren startar SuperDeathFist-attacken.)

AI:n kommer att se alla alternativ när spelaren väljer Kick, följt av en annan Kick, och lägger sedan märke till att nästa ingång alltid är Punch. Detta gör att agenten kan förutsäga SuperDeathFists kombinationsrörelse och blockera den om möjligt.

Dessa händelsesekvenser kallas N-gram, där N är antalet lagrade element. I det föregående exemplet var det ett 3-gram (trigram), vilket betyder: de två första posterna används för att förutsäga den tredje. Följaktligen, i en 5-grams, förutsäger de första fyra posterna den femte och så vidare.

Designern måste välja storleken på N-gram noggrant. Ett mindre N kräver mindre minne men lagrar också mindre historik. Till exempel kommer en 2-grams (bigram) att spela in Kick, Kick eller Kick, Punch, men kommer inte att kunna lagra Kick, Kick, Punch, så AI:n kommer inte att svara på SuperDeathFist-kombon.

Å andra sidan kräver större antal mer minne och AI kommer att bli svårare att träna eftersom det kommer att finnas många fler möjliga alternativ. Om du hade tre möjliga ingångar av Kick, Punch eller Block, och vi använde en 10-grams, skulle det vara cirka 60 tusen olika alternativ.

Bigrammodellen är en enkel Markov-kedja - varje tidigare tillstånd/nuvarande tillståndspar är ett bigram, och du kan förutsäga det andra tillståndet baserat på det första. De 3-grams och större N-grammen kan också ses som Markov-kedjor, där alla element (utom det sista i N-grammet) tillsammans bildar det första tillståndet och det sista elementet det andra. Fightingspelexemplet visar chansen att övergå från Kick and Kick-tillståndet till Kick and Punch-tillståndet. Genom att behandla flera inmatningshistorikposter som en enda enhet omvandlar vi i huvudsak inmatningssekvensen till en del av hela tillståndet. Detta ger oss Markov-egenskapen, som gör att vi kan använda Markov-kedjor för att förutsäga nästa ingång och gissa vilket kombinationsdrag som kommer att bli nästa.

Slutsats

Vi pratade om de vanligaste verktygen och tillvägagångssätten i utvecklingen av artificiell intelligens. Vi tittade också på i vilka situationer de behöver användas och där de är särskilt användbara.

Detta borde vara tillräckligt för att förstå grunderna i spel AI. Men det är naturligtvis inte alla metoder. Mindre populära, men inte mindre effektiva inkluderar:

• optimeringsalgoritmer inklusive bergsklättring, lutning och genetiska algoritmer
• motstridiga sök-/schemaläggningsalgoritmer (minimax och alfa-beta beskärning)
• klassificeringsmetoder (perceptroner, neurala nätverk och stödvektormaskiner)
• system för bearbetningsagenters perception och minne
• arkitektoniska tillvägagångssätt för AI (hybridsystem, delmängdsarkitekturer och andra sätt att överlappa AI-system)
• animationsverktyg (planering och rörelsekoordinering)
• prestandafaktorer (detaljnivå, när som helst och tidsdelningsalgoritmer)

Internetresurser om ämnet:

1. GameDev.net har avsnitt med artiklar och handledning om AIOch forumet.
2. AiGameDev.com innehåller många presentationer och artiklar om ett brett spektrum av ämnen relaterade till spel AI-utveckling.
3. GDC-valvet innehåller ämnen från GDC AI Summit, av vilka många är tillgängliga gratis.
4. Användbart material finns också på hemsidan AI Game Programmers Guild.
5. Tommy Thompson, AI-forskare och spelutvecklare, gör videor på YouTube AI och spel med en förklaring och studie av AI i kommersiella spel.

Böcker om ämnet:

1. Bokserien Game AI Pro är en samling korta artiklar som förklarar hur man implementerar specifika funktioner eller hur man löser specifika problem.

Game AI Pro: Collected Wisdom of Game AI Professionals
Game AI Pro 2: Collected Wisdom of Game AI Professionals
Game AI Pro 3: Collected Wisdom of Game AI Professionals

2. AI Game Programming Wisdom-serien är föregångaren till Game AI Pro-serien. Den innehåller äldre metoder, men nästan alla är aktuella även idag.

AI Game Programming Wisdom 1
AI Game Programming Wisdom 2
AI Game Programming Wisdom 3
AI Game Programming Wisdom 4

3. Artificiell intelligens: ett modernt tillvägagångssätt är en av grundtexterna för alla som vill förstå det allmänna området artificiell intelligens. Det här är inte en bok om spelutveckling – den lär ut grunderna i AI.

Källa: will.com