ProHoster > Blogs > interneta ziņas > Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Uzgāju interesantu materiālu par mākslÄ«go intelektu spēlēs. Ar vienkārÅ”u piemēru skaidrojumu par AI pamata lietām, un iekÅ”pusē ir daudz noderÄ«gu rÄ«ku un metožu tā ērtai izstrādei un projektÄ“Å”anai. Tur ir arÄ« norādÄ«ts, kā, kur un kad tās lietot.

Lielākā daļa piemēru ir rakstÄ«ti pseidokodā, tāpēc nav nepiecieÅ”amas progresÄ«vas programmÄ“Å”anas zināŔanas. Zem griezuma ir 35 teksta lapas ar attēliem un gifiem, tāpēc gatavojieties.

UPD. Es atvainojos, bet es jau esmu tulkojis Å”o rakstu par Habrē PatientZero. JÅ«s varat izlasÄ«t viņa versiju Å”eit, bet raksts nez kāpēc pagāja garām (izmantoju meklÄ“Å”anu, bet kaut kas nogāja greizi). Un tā kā es rakstu emuārā, kas veltÄ«ts spēļu izstrādei, es nolēmu atstāt savu tulkojuma versiju abonentiem (daži punkti ir formatēti atŔķirÄ«gi, daži tika apzināti izlaisti pēc izstrādātāju ieteikuma).

Kas ir AI?

Spēles AI koncentrējas uz to, kādas darbības objektam jāveic, pamatojoties uz apstākļiem, kādos tas atrodas. To parasti sauc par "inteliģentā aģenta" vadību, kur aģents ir spēlētāja varonis, transportlīdzeklis, robots vai dažreiz kaut kas abstraktāks: vesela vienību grupa vai pat civilizācija. Katrā gadījumā tā ir lieta, kurai jāredz sava vide, jāpieņem lēmumi, pamatojoties uz to, un jārīkojas saskaņā ar tiem. To sauc par sajūtu/domāt/rīkoties ciklu:

  • SajÅ«ta: aÄ£ents atrod vai saņem informāciju par lietām savā vidē, kas var ietekmēt viņa uzvedÄ«bu (draudi tuvumā, priekÅ”meti, ko savākt, interesantas vietas, ko izpētÄ«t).
  • Padomājiet: aÄ£ents izlemj, kā reaģēt (apsver, vai ir pietiekami droÅ”i savākt priekÅ”metus, vai viņam vispirms ir jācÄ«nās/slēpjas).
  • RÄ«kojieties: aÄ£ents veic darbÄ«bas, lai Ä«stenotu iepriekŔējo lēmumu (sāk virzÄ«ties uz ienaidnieku vai objektu).
  • ...tagad situācija ir mainÄ«jusies varoņu darbÄ«bas dēļ, tāpēc cikls atkārtojas ar jauniem datiem.

AI mēdz koncentrēties uz cilpas Sense daļu. Piemēram, autonomās automaŔīnas fotografē ceļu, apvieno tos ar radara un lidara datiem un interpretē tos. To parasti veic maŔīnmācÄ«Å”anās, kas apstrādā ienākoÅ”os datus un pieŔķir tiem nozÄ«mi, iegÅ«stot semantisko informāciju, piemēram, "20 jardus priekŔā jums ir cita automaŔīna". Tās ir tā sauktās klasifikācijas problēmas.

Spēlēm nav nepiecieÅ”ama sarežģīta sistēma, lai iegÅ«tu informāciju, jo lielākā daļa datu jau ir tās neatņemama sastāvdaļa. Nav nepiecieÅ”ams palaist attēlu atpazÄ«Å”anas algoritmus, lai noteiktu, vai priekŔā ir ienaidnieks ā€” spēle jau zina un ievada informāciju tieÅ”i lēmumu pieņemÅ”anas procesā. Tāpēc cikla SajÅ«tu daļa bieži vien ir daudz vienkārŔāka nekā daļa Domā un rÄ«kojies.

Spēles AI ierobežojumi

AI ir vairāki ierobežojumi, kas jāievēro:

  • AI nav iepriekÅ” jāapmāca, it kā tas bÅ«tu maŔīnmācÄ«Å”anās algoritms. Nav jēgas izstrādes laikā rakstÄ«t neironu tÄ«klu, lai uzraudzÄ«tu desmitiem tÅ«kstoÅ”u spēlētāju un uzzinātu labāko veidu, kā spēlēt pret viņiem. Kāpēc? Jo spēle nav izlaista un spēlētāju nav.
  • Spēlei jābÅ«t jautrai un izaicinoÅ”ai, tāpēc aÄ£entiem nevajadzētu atrast labāko pieeju pret cilvēkiem.
  • AÄ£entiem ir jāizskatās reālistiskiem, lai spēlētāji justos tā, it kā viņi spēlē pret Ä«stiem cilvēkiem. AlphaGo programma pārspēja cilvēkus, taču izvēlētie soļi bija ļoti tālu no tradicionālās spēles izpratnes. Ja spēle simulē cilvēka pretinieku, Å”ai sajÅ«tai nevajadzētu pastāvēt. Algoritms ir jāmaina, lai tas pieņemtu ticamus, nevis ideālus lēmumus.
  • AI jāstrādā reāllaikā. Tas nozÄ«mē, ka algoritms nevar monopolizēt CPU izmantoÅ”anu ilgu laiku, lai pieņemtu lēmumus. Pat 10 milisekundes ir pārāk ilgs laiks, jo lielākajai daļai spēļu ir nepiecieÅ”amas tikai 16 lÄ«dz 33 milisekundes, lai veiktu visu apstrādi un pārietu uz nākamo grafikas kadru.
  • Ideālā gadÄ«jumā vismaz daļai sistēmas vajadzētu bÅ«t balstÄ«tai uz datiem, lai lietotāji, kas nav kodēti, varētu veikt izmaiņas un veikt pielāgojumus ātrāk.

Apskatīsim AI pieejas, kas aptver visu Sense/Think/Act ciklu.

Pamatlēmumu pieņemÅ”ana

Sāksim ar vienkārŔāko spēli - Pong. MērÄ·is: pārvietojiet lāpstiņu tā, lai bumba atlēktu no tās, nevis lidotu tai garām. Tas ir kā tenisā, kur tu zaudē, ja netrāpi pa bumbu. Å eit AI ir salÄ«dzinoÅ”i viegls uzdevums - izlemt, kurā virzienā pārvietot platformu.

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Nosacīti paziņojumi

AI Pong visredzamākais risinājums ir vienmēr mēģināt novietot platformu zem bumbas.

VienkārŔs algoritms tam, rakstīts pseidokodā:

katrs kadrs/atjauninājums spēles darbības laikā:
ja bumba atrodas pa kreisi no lāpstiņas:
pārvietot lāpstiņu pa kreisi
citādi, ja bumba atrodas pa labi no lāpstiņas:
pārvietojiet lāpstiņu pa labi

Ja platforma pārvietojas ar bumbiņas ātrumu, tas ir ideāls Pong algoritms AI. Nevajag neko sarežģīt, ja aģentam nav tik daudz datu un iespējamo darbību.

Šī pieeja ir tik vienkārŔa, ka viss Sense/Think/Act cikls ir tikko pamanāms. Bet tas ir tur:

  • Sense daļa ir divos if paziņojumos. Spēle zina, kur atrodas bumba un kur atrodas platforma, tāpēc AI meklē Å”o informāciju.
  • DomāŔanas daļa ir iekļauta arÄ« divos if paziņojumos. Tie ietver divus risinājumus, kas Å”ajā gadÄ«jumā ir viens otru izslēdzoÅ”i. Rezultātā tiek izvēlēta viena no trim darbÄ«bām - pārvietot platformu pa kreisi, pārvietot to pa labi vai neko nedarÄ«t, ja tā jau ir pareizi novietota.
  • DarbÄ«bas daļa ir atrodama paziņojumos Move Paddle Left un Move Paddle Right. AtkarÄ«bā no spēles dizaina viņi var pārvietot platformu uzreiz vai ar noteiktu ātrumu.

Šādas pieejas sauc par reaktÄ«vām - ir vienkārÅ”s noteikumu kopums (Å”ajā gadÄ«jumā, ja kodā ir paziņojumi), kas reaģē uz paÅ”reizējo pasaules stāvokli un rÄ«kojas.

Lēmumu koks

Pong piemērs faktiski ir lÄ«dzvērtÄ«gs formālai AI koncepcijai, ko sauc par lēmumu koku. Algoritms iziet cauri tam, lai sasniegtu ā€œlapuā€ ā€” lēmumu par to, kā rÄ«koties.

Izveidosim mūsu platformas algoritma lēmumu koka blokshēmu:

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Katru koka daļu sauc par mezglu ā€“ AI izmanto grafu teoriju, lai aprakstÄ«tu Ŕādas struktÅ«ras. Ir divu veidu mezgli:

  • Lēmuma mezgli: izvēle starp divām alternatÄ«vām, pamatojoties uz kāda nosacÄ«juma pārbaudi, kur katra alternatÄ«va tiek attēlota kā atseviŔķs mezgls.
  • Beigu mezgli: veicamā darbÄ«ba, kas atspoguļo galÄ«go lēmumu.

Algoritms sākas no pirmā mezgla (koka ā€œsaknesā€). Tas vai nu pieņem lēmumu par to, uz kuru bērnmezglu pāriet, vai arÄ« izpilda mezglā saglabāto darbÄ«bu un iziet.

Kāds ir labums no lēmumu koka, kas veic to paÅ”u darbu, ko iepriekŔējā sadaļā sniegtie if paziņojumi? Å eit ir vispārēja sistēma, kurā katram lēmumam ir tikai viens nosacÄ«jums un divi iespējamie rezultāti. Tas ļauj izstrādātājam izveidot AI no datiem, kas atspoguļo lēmumus kokā, bez nepiecieÅ”amÄ«bas tos stingri kodēt. Iesniegsim to tabulas veidā:

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Koda pusē jÅ«s iegÅ«sit sistēmu virkņu nolasÄ«Å”anai. Izveidojiet mezglu katram no tiem, savienojiet lēmumu loÄ£iku, pamatojoties uz otro kolonnu, un pakārtotos mezglus, pamatojoties uz treÅ”o un ceturto kolonnu. Jums joprojām ir jāieprogrammē nosacÄ«jumi un darbÄ«bas, taču tagad spēles struktÅ«ra bÅ«s sarežģītāka. Å eit jÅ«s pievienojat papildu lēmumus un darbÄ«bas un pēc tam pielāgojat visu AI, vienkārÅ”i rediģējot koka definÄ«cijas teksta failu. Pēc tam failu pārsÅ«tiet spēles izstrādātājam, kurÅ” var mainÄ«t uzvedÄ«bu, nepārkompilējot spēli vai nemainot kodu.

Lēmumu koki ir ļoti noderÄ«gi, ja tie tiek veidoti automātiski, izmantojot lielu piemēru kopu (piemēram, izmantojot ID3 algoritmu). Tas padara tos par efektÄ«vu un augstas veiktspējas rÄ«ku situāciju klasificÄ“Å”anai, pamatojoties uz iegÅ«tajiem datiem. Tomēr mēs pārsniedzam vienkārÅ”u sistēmu, lai aÄ£enti varētu atlasÄ«t darbÄ«bas.

Scenāriji

Mēs analizējām lēmumu koka sistēmu, kurā tika izmantoti iepriekÅ” izveidoti nosacÄ«jumi un darbÄ«bas. Persona, kas izstrādā AI, var sakārtot koku, kā vien vēlas, taču viņam joprojām ir jāpaļaujas uz kodētāju, kurÅ” to visu ir ieprogrammējis. Ko darÄ«t, ja mēs varētu dot dizainerim rÄ«kus, lai radÄ«tu savus apstākļus vai darbÄ«bas?

Lai programmētājam nebÅ«tu jāraksta kods nosacÄ«jumiem Is Ball Left Of Paddle un Is Ball Right Of Paddle, viņŔ var izveidot sistēmu, kurā dizaineris ierakstÄ«s nosacÄ«jumus, lai pārbaudÄ«tu Ŕīs vērtÄ«bas. Tad lēmumu koka dati izskatÄ«sies Ŕādi:

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Tas bÅ«tÄ«bā ir tāds pats kā pirmajā tabulā, taču risinājumiem paÅ”iem ir savs kods, nedaudz lÄ«dzÄ«gs if priekÅ”raksta nosacÄ«tajai daļai. Koda pusē tas bÅ«tu lasāms lēmuma mezglu otrajā kolonnā, taču tā vietā, lai meklētu konkrētu izpildāmu nosacÄ«jumu (Is Ball Left Of Paddle), tas novērtē nosacÄ«juma izteiksmi un attiecÄ«gi atgriež patiesu vai nepatiesu. Tas tiek darÄ«ts, izmantojot Lua vai Angelscript skriptu valodu. Izmantojot tos, izstrādātājs var paņemt objektus savā spēlē (bumbu un lāpstiņu) un izveidot mainÄ«gos, kas bÅ«s pieejami skriptā (ball.position). Turklāt skriptu valoda ir vienkārŔāka nekā C++. Tam nav nepiecieÅ”ams pilns kompilācijas posms, tāpēc tas ir ideāli piemērots ātrai spēles loÄ£ikas pielāgoÅ”anai un ļauj ā€œnekodētājiemā€ paÅ”iem izveidot nepiecieÅ”amās funkcijas.

IepriekÅ” minētajā piemērā skriptu valoda tiek izmantota tikai nosacÄ«juma izteiksmes novērtÄ“Å”anai, taču to var izmantot arÄ« darbÄ«bām. Piemēram, dati Move Paddle Right var kļūt par skripta paziņojumu (bumbiņa.pozÄ«cija.x += 10). Lai darbÄ«ba bÅ«tu definēta arÄ« skriptā, bez nepiecieÅ”amÄ«bas ieprogrammēt Move Paddle Right.

Varat iet vēl tālāk un uzrakstīt visu lēmumu koku skriptu valodā. Tas būs kods cietkodētu nosacījumu paziņojumu veidā, taču tie atradīsies ārējos skripta failos, tas ir, tos var mainīt, nepārkompilējot visu programmu. Bieži vien spēles laikā varat rediģēt skripta failu, lai ātri pārbaudītu dažādas AI reakcijas.

Notikuma atbilde

IepriekÅ” minētie piemēri ir lieliski piemēroti Pong. Viņi nepārtraukti vada Sense/Think/Act ciklu un rÄ«kojas, pamatojoties uz jaunāko stāvokli pasaulē. Bet sarežģītākās spēlēs ir jāreaģē uz atseviŔķiem notikumiem, nevis jānovērtē viss uzreiz. Pongs Å”ajā gadÄ«jumā jau ir slikts piemērs. Izvēlēsimies citu.

Iedomājieties Ŕāvēju, kurā ienaidnieki nekustas, lÄ«dz pamana spēlētāju, pēc tam viņi rÄ«kojas atkarÄ«bā no savas ā€œspecializācijasā€: kāds skries ā€œsteigtiesā€, kāds uzbruks no tālienes. Tā joprojām ir pamata reaktÄ«vā sistēma - "ja spēlētājs ir pamanÄ«ts, dariet kaut ko" -, taču to var loÄ£iski sadalÄ«t notikumā Spēlētājs redzēts un reakcijā (atlasiet atbildi un izpildiet to).

Tas mÅ«s atgriež pie SajÅ«tu/Domā/ RÄ«kojies cikla. Mēs varam kodēt Sense daļu, kas pārbaudÄ«s katru kadru, vai AI redz atskaņotāju. Ja nē, nekas nenotiek, bet, ja redz, tad tiek izveidots notikums Player Seen. Kodam bÅ«s atseviŔķa sadaļa, kurā teikts: "Kad notiek notikums Player Seen, dariet", kur ir atbilde, kas jums nepiecieÅ”ama, lai risinātu sadaļas Domā un rÄ«kojies. Tādējādi jÅ«s iestatÄ«sit reakcijas uz notikumu Player Seen: ā€œsteidzÄ«gajamā€ varonim - ChargeAndAttack un snaiperim - HideAndSnipe. Å Ä«s attiecÄ«bas var izveidot datu failā ātrai rediģēŔanai bez nepiecieÅ”amÄ«bas atkārtoti kompilēt. Å eit var izmantot arÄ« skriptu valodu.

Sarežģītu lēmumu pieņemÅ”ana

Lai gan vienkārÅ”as reakcijas sistēmas ir ļoti spēcÄ«gas, ir daudz situāciju, kad ar tām nepietiek. Dažreiz jums ir jāpieņem dažādi lēmumi, pamatojoties uz to, ko aÄ£ents paÅ”laik dara, taču to ir grÅ«ti iedomāties kā nosacÄ«jumu. Dažreiz ir pārāk daudz nosacÄ«jumu, lai tos efektÄ«vi attēlotu lēmumu kokā vai skriptā. Dažreiz jums ir iepriekÅ” jāizvērtē, kā situācija mainÄ«sies, pirms izlemjat par nākamo soli. Lai atrisinātu Ŕīs problēmas, ir vajadzÄ«gas sarežģītākas pieejas.

Galīgā stāvokļa maŔīna

Ierobežotā stāvokļa maŔīna jeb FSM (finite state machine) ir veids, kā pateikt, ka mÅ«su aÄ£ents paÅ”laik atrodas vienā no vairākiem iespējamiem stāvokļiem un ka tas var pāriet no viena stāvokļa uz citu. Ir zināms skaits Ŕādu stāvokļu, tāpēc arÄ« nosaukums. Labākais piemērs no dzÄ«ves ir luksofors. Dažādās vietās ir dažādas gaismu secÄ«bas, bet princips ir viens ā€“ katrs stāvoklis kaut ko attēlo (apstāties, iet utt.). Luksofors jebkurā laikā atrodas tikai vienā stāvoklÄ« un pārvietojas no viena uz otru, pamatojoties uz vienkārÅ”iem noteikumiem.

Tas ir lÄ«dzÄ«gs stāsts ar NPC spēlēs. Piemēram, ņemsim aizsargu ar Ŕādiem stāvokļiem:

  • PatrulÄ“Å”ana.
  • UzbrÅ«k.
  • BēgÅ”ana.

Un Å”ie nosacÄ«jumi tā stāvokļa maiņai:

  • Ja apsargs redz ienaidnieku, viņŔ uzbrÅ«k.
  • Ja apsargs uzbrÅ«k, bet vairs neredz ienaidnieku, viņŔ atgriežas patrulēt.
  • Ja apsargs uzbrÅ«k, bet ir smagi ievainots, viņŔ bēg.

Var rakstīt arī if-izteikumus ar aizbildņa stāvokļa mainīgo un dažādām pārbaudēm: vai tuvumā ir ienaidnieks, kāds ir NPC veselības līmenis utt. Pievienosim vēl dažus stāvokļus:

  • DÄ«kstāve - starp patruļām.
  • MeklÄ“Å”ana ā€“ kad pazudis pamanÄ«tais ienaidnieks.
  • PalÄ«dzÄ«bas atraÅ”ana - kad ienaidnieks ir pamanÄ«ts, bet ir pārāk spēcÄ«gs, lai cÄ«nÄ«tos viens.

Katram no viņiem izvēle ir ierobežota ā€“ piemēram, apsargs nedosies meklēt slēptu ienaidnieku, ja viņam ir slikta veselÄ«ba.

Galu galā ir milzÄ«gs "ja" saraksts , Tas " var kļūt pārāk apgrÅ«tinoÅ”i, tāpēc mums ir jāformalizē metode, kas ļauj mums paturēt prātā stāvokļus un pārejas starp stāvokļiem. Lai to izdarÄ«tu, mēs ņemam vērā visus stāvokļus un zem katra stāvokļa sarakstā ierakstām visas pārejas uz citiem stāvokļiem kopā ar tiem nepiecieÅ”amajiem nosacÄ«jumiem.

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Å Ä« ir stāvokļa pārejas tabula - visaptveroÅ”s veids, kā pārstāvēt MFV. UzzÄ«mēsim diagrammu un iegÅ«sim pilnÄ«gu pārskatu par to, kā mainās NPC uzvedÄ«ba.

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Diagramma atspoguļo Ŕī aÄ£enta lēmumu pieņemÅ”anas bÅ«tÄ«bu, pamatojoties uz paÅ”reizējo situāciju. Turklāt katra bultiņa parāda pāreju starp stāvokļiem, ja blakus esoÅ”ais nosacÄ«jums ir patiess.

Katrā atjauninājumā mēs pārbaudām aÄ£enta paÅ”reizējo stāvokli, apskatām pāreju sarakstu un, ja ir izpildÄ«ti pārejas nosacÄ«jumi, tas pieņem jauno stāvokli. Piemēram, katrs kadrs pārbauda, ā€‹ā€‹vai 10 sekunžu taimeris nav beidzies, un, ja tā, tad apsargs pāriet no tukÅ”gaitas stāvokļa uz PatrulÄ“Å”anu. Tādā paŔā veidā UzbrÅ«koÅ”ais stāvoklis pārbauda aÄ£enta veselÄ«bu ā€“ ja tas ir zems, tad tas pāriet BēgÅ”anas stāvoklÄ«.

Tas attiecas uz pāreju starp stāvokļiem, bet kā ar uzvedÄ«bu, kas saistÄ«ta ar paÅ”iem stāvokļiem? Runājot par faktiskās uzvedÄ«bas ievieÅ”anu konkrētam stāvoklim, parasti ir divu veidu "āķis", kurā mēs pieŔķiram darbÄ«bas MFV:

  • DarbÄ«bas, kuras mēs periodiski veicam paÅ”reizējam stāvoklim.
  • DarbÄ«bas, ko veicam, pārejot no viena stāvokļa uz otru.

Piemēri pirmajam tipam. PatrulÄ“Å”anas stāvoklis pārvietos aÄ£entu pa patruļas marÅ”rutu katrā kadrā. Uzbrukuma stāvoklis mēģinās uzsākt uzbrukumu katrā kadrā vai pāriet uz stāvokli, kurā tas ir iespējams.

Otrajam veidam apsveriet pāreju ā€œja ienaidnieks ir redzams un ienaidnieks ir pārāk spēcÄ«gs, pārejiet uz MeklÄ“Å”anas palÄ«dzÄ«bas stāvokli. AÄ£entam ir jāizvēlas, kur vērsties pēc palÄ«dzÄ«bas, un jāsaglabā Ŕī informācija, lai palÄ«dzÄ«bas meklÄ“Å”anas stāvoklis zinātu, kur vērsties. Kad palÄ«dzÄ«ba tiek atrasta, aÄ£ents atgriežas uzbrucēja stāvoklÄ«. Å ajā brÄ«dÄ« viņŔ vēlēsies pastāstÄ«t sabiedrotajam par draudiem, tāpēc var notikt NotifyFriendOfThreat darbÄ«ba.

Vēlreiz mēs varam aplÅ«kot Å”o sistēmu caur cikla Sense/Think/Act objektÄ«vu. Jēga ir ietverta datos, ko izmanto pārejas loÄ£ika. Padomā ā€“ pārejas pieejamas katrā stāvoklÄ«. Un aktu veic darbÄ«bas, kas periodiski tiek veiktas stāvoklÄ« vai pārejās starp stāvokļiem.

Dažreiz nepārtrauktas aptaujas pārejas nosacÄ«jumi var bÅ«t dārgi. Piemēram, ja katrs aÄ£ents veic sarežģītus aprēķinus katrā kadrā, lai noteiktu, vai tas var redzēt ienaidniekus un saprast, vai tas var pāriet no patrulÄ“Å”anas stāvokļa uz uzbrukumu, tas prasÄ«s daudz CPU laika.

SvarÄ«gas izmaiņas pasaules stāvoklÄ« var uzskatÄ«t par notikumiem, kas tiks apstrādāti, tiklÄ«dz tie notiek. Tā vietā, lai FSM pārbaudÄ«tu pārejas nosacÄ«jumu "vai mans aÄ£ents var redzēt atskaņotāju?" katrā kadrā, atseviŔķu sistēmu var konfigurēt, lai tā pārbaudÄ«tu retāk (piemēram, 5 reizes sekundē). Rezultātā tiek izdots Player Seen, kad čeks ir izturēts.

Tas tiek nodots MFV, kurai tagad jāiet uz nosacÄ«jumu, ka notikums ir redzēts, un attiecÄ«gi jāreaģē. Rezultātā uzvedÄ«ba ir tāda pati, izņemot gandrÄ«z nemanāmu kavÄ“Å”anos pirms atbildes. Taču veiktspēja ir uzlabojusies, atdalot Sense daļu atseviŔķā programmas daļā.

Hierarhiska galīgo stāvokļu maŔīna

Tomēr darbs ar lieliem FSM ne vienmēr ir ērti. Ja mēs vēlamies paplaÅ”ināt uzbrukuma stāvokli, lai atdalÄ«tu MeleeAttacking un RangedAttacking, mums bÅ«s jāmaina pārejas no visiem pārējiem stāvokļiem, kas noved pie Attacking stāvokļa (paÅ”reizējais un nākotnes).

JÅ«s droÅ”i vien pamanÄ«jāt, ka mÅ«su piemērā ir daudz pāreju dublikātu. Lielākā daļa pāreju tukÅ”gaitas stāvoklÄ« ir identiskas pārejām patrulÄ“Å”anas stāvoklÄ«. BÅ«tu jauki neatkārtoties, it Ä«paÅ”i, ja pievienojam vēl lÄ«dzÄ«gus stāvokļus. Ir jēga grupēt tukÅ”gaitu un patrulÄ“Å”anu zem vispārējā apzÄ«mējuma "bez kaujas", kur ir tikai viens kopÄ«gs pāreju kopums uz kaujas stāvokļiem. Ja mēs domājam par Å”o etiÄ·eti kā stāvokli, tad tukÅ”gaita un patrulÄ“Å”ana kļūst par apakÅ”stāvokļiem. AtseviŔķas pārejas tabulas izmantoÅ”anas piemērs jaunai ar kauju nesaistÄ«tai apakÅ”stāvoklim:

Galvenie stāvokļi:
Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Ārpus kaujas statuss:
Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Un diagrammas formā:

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Tā ir tā pati sistēma, bet ar jaunu bezkaujas stāvokli, kas ietver tukÅ”gaitu un patrulÄ“Å”anu. Katram stāvoklim, kurā ir FSM ar apakÅ”stāvokļiem (un Å”ie apakÅ”stāvokļi, savukārt, satur savus FSM ā€” un tā tālāk tik ilgi, cik jums nepiecieÅ”ams), mēs iegÅ«stam hierarhisko galÄ«go stāvokļu maŔīnu vai HFSM (hierarhisko galÄ«go stāvokļu maŔīnu). Grupējot bezkaujas stāvokli, mēs izgriezām virkni lieku pāreju. Mēs varam darÄ«t to paÅ”u jebkuriem jauniem stāvokļiem ar kopÄ«gām pārejām. Piemēram, ja nākotnē mēs paplaÅ”ināsim Attacking stāvokli uz Tuvcīņas uzbrukuma un MissileAttacking stāvokļiem, tie bÅ«s apakÅ”stāvokļi, kas pāriet savā starpā, pamatojoties uz attālumu lÄ«dz ienaidniekam un munÄ«cijas pieejamÄ«bu. Rezultātā sarežģītas uzvedÄ«bas un apakÅ”uzvedÄ«bas var attēlot ar minimālu dublikātu pāreju skaitu.

Uzvedības koks

Izmantojot HFSM, vienkārŔā veidā tiek izveidotas sarežģītas uzvedÄ«bas kombinācijas. Tomēr ir nelielas grÅ«tÄ«bas, ka lēmumu pieņemÅ”ana pārejas noteikumu veidā ir cieÅ”i saistÄ«ta ar paÅ”reizējo stāvokli. Un daudzās spēlēs tas ir tieÅ”i tas, kas nepiecieÅ”ams. Un rÅ«pÄ«ga stāvokļa hierarhijas izmantoÅ”ana var samazināt pārejas atkārtojumu skaitu. Bet dažreiz jums ir nepiecieÅ”ami noteikumi, kas darbojas neatkarÄ«gi no jÅ«su atraÅ”anās vietas vai ir spēkā gandrÄ«z jebkurā Å”tatā. Piemēram, ja aÄ£enta veselÄ«bas stāvoklis pasliktinās lÄ«dz 25%, jÅ«s vēlaties, lai viņŔ aizbēgtu neatkarÄ«gi no tā, vai viņŔ bija kaujā, dÄ«kstāvē vai runāja ā€” jums Å”is nosacÄ«jums bÅ«s jāpievieno katram stāvoklim. Un, ja jÅ«su dizainers vēlāk vēlas mainÄ«t zemo veselÄ«bas slieksni no 25% uz 10%, tad tas bÅ«s jādara vēlreiz.

Ideālā gadÄ«jumā Ŕī situācija prasa sistēmu, kurā lēmumi par to, ā€œkādā stāvoklÄ« atrastiesā€, ir ārpus paÅ”iem stāvokļiem, lai veiktu izmaiņas tikai vienā vietā un neskartu pārejas nosacÄ«jumus. Å eit parādās uzvedÄ«bas koki.

Ir vairāki veidi, kā tos ieviest, taču bÅ«tÄ«ba ir aptuveni vienāda visiem un ir lÄ«dzÄ«ga lēmumu kokam: algoritms sākas ar ā€œsaknesā€ mezglu, un kokā ir mezgli, kas atspoguļo lēmumus vai darbÄ«bas. Tomēr ir dažas galvenās atŔķirÄ«bas:

  • Mezgli tagad atgriež vienu no trim vērtÄ«bām: Succeeded (ja darbs ir pabeigts), Failed (ja to nevar sākt) vai Running (ja tas joprojām darbojas un nav gala rezultāta).
  • Vairs nav lēmumu pieņemÅ”anas mezglu, no kuriem izvēlēties starp divām alternatÄ«vām. Tā vietā tie ir dekoratora mezgli, kuriem ir viens pakārtots mezgls. Ja viņiem izdodas, viņi izpilda savu vienÄ«go bērnu mezglu.
  • Mezgli, kas veic darbÄ«bas, atgriež Running vērtÄ«bu, lai attēlotu veicamās darbÄ«bas.

Å o nelielo mezglu kopu var apvienot, lai izveidotu lielu skaitu sarežģītu darbÄ«bu. Iedomāsimies HFSM aizsargu no iepriekŔējā piemēra kā uzvedÄ«bas koku:

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Izmantojot Å”o struktÅ«ru, nevajadzētu bÅ«t acÄ«mredzamai pārejai no tukÅ”gaitas/patrulÄ“Å”anas stāvokļiem uz uzbrukuma vai citiem stāvokļiem. Ja ir redzams ienaidnieks un varoņa veselÄ«ba ir zema, izpilde tiks pārtraukta BēgÅ”anas mezglā neatkarÄ«gi no tā, kuru mezglu tas iepriekÅ” izpildÄ«ja ā€“ PatrulÄ“Å”ana, TukÅ”gaita, UzbrÅ«kÅ”ana vai jebkura cita.

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

UzvedÄ«bas koki ir sarežģīti ā€” ir daudz veidu, kā tos izveidot, un atrast pareizo dekoratoru un salikto mezglu kombināciju var bÅ«t izaicinājums. Rodas arÄ« jautājumi par to, cik bieži koku pārbaudÄ«t ā€“ vai gribam iziet cauri katrai tā daļai vai tikai tad, kad ir mainÄ«jies kāds no apstākļiem? Kā mēs saglabājam mezglu stāvokli ā€” kā mēs zinām, kad esam dÄ«kstāvē 10 sekundes, vai kā mēs zinām, kuri mezgli darbojās pēdējo reizi, lai mēs varētu pareizi apstrādāt secÄ«bu?

Tāpēc ir daudz ievieÅ”anu. Piemēram, dažās sistēmās dekoratoru mezgli ir aizstāti ar iebÅ«vētiem dekoratoriem. Viņi atkārtoti novērtē koku, kad mainās dekoratora apstākļi, palÄ«dz pievienoties mezgliem un nodroÅ”ina periodiskus atjauninājumus.

Uz komunālajiem pakalpojumiem balstīta sistēma

Dažām spēlēm ir daudz dažādu mehāniku. Vēlams, lai viņi saņemtu visas vienkārÅ”o un vispārÄ«go pārejas noteikumu priekÅ”rocÄ«bas, bet ne vienmēr pilnÄ«ga uzvedÄ«bas koka veidā. Tā vietā, lai bÅ«tu skaidrs izvēļu kopums vai iespējamo darbÄ«bu koks, ir vieglāk izskatÄ«t visas darbÄ«bas un izvēlēties konkrētajā brÄ«dÄ« piemērotāko.

Uz utilÄ«tprogrammām balstÄ«tā sistēma palÄ«dzēs tieÅ”i Å”ajā jautājumā. Å Ä« ir sistēma, kurā aÄ£entam ir dažādas darbÄ«bas un viņŔ izvēlas, kuras no tām veikt, pamatojoties uz katras darbÄ«bas relatÄ«vo lietderÄ«bu. Ja lietderÄ«ba ir patvaļīgs mērs tam, cik svarÄ«gi vai vēlams aÄ£entam ir veikt Å”o darbÄ«bu.

Aprēķinātā darbÄ«bas lietderÄ«ba, pamatojoties uz paÅ”reizējo stāvokli un vidi, aÄ£ents jebkurā laikā var pārbaudÄ«t un atlasÄ«t vispiemērotāko citu stāvokli. Tas ir lÄ«dzÄ«gi MFV, izņemot gadÄ«jumus, kad pārejas nosaka katra potenciālā stāvokļa novērtējums, ieskaitot paÅ”reizējo. LÅ«dzu, ņemiet vērā, ka mēs izvēlamies visnoderÄ«gāko darbÄ«bu, lai turpinātu (vai paliekam, ja esam to jau pabeiguÅ”i). Lai iegÅ«tu lielāku dažādÄ«bu, Ŕī varētu bÅ«t lÄ«dzsvarota, bet nejauÅ”a atlase no neliela saraksta.

Sistēma pieŔķir patvaļīgu lietderÄ«bas vērtÄ«bu diapazonu, piemēram, no 0 (pilnÄ«gi nevēlams) lÄ«dz 100 (pilnÄ«gi vēlams). Katrai darbÄ«bai ir vairāki parametri, kas ietekmē Ŕīs vērtÄ«bas aprēķināŔanu. Atgriežoties pie mÅ«su aizbildņa piemēra:

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Pārejas starp darbÄ«bām ir neskaidras ā€” jebkura valsts var sekot jebkurai citai. DarbÄ«bas prioritātes ir atrodamas atgrieztajās lietderÄ«bas vērtÄ«bās. Ja ir redzams ienaidnieks un Å”is ienaidnieks ir spēcÄ«gs un varoņa veselÄ«ba ir zema, gan Fleeing, gan FindingHelp atgriezÄ«s augstas vērtÄ«bas, kas nav nulles. Å ajā gadÄ«jumā FindingHelp vienmēr bÅ«s augstāks. Tāpat arÄ« ar kauju nesaistÄ«tās aktivitātes nekad neatmaksā vairāk par 50, tāpēc tās vienmēr bÅ«s zemākas par kaujas aktivitātēm. Tas jāņem vērā, veidojot darbÄ«bas un aprēķinot to lietderÄ«bu.

MÅ«su piemērā darbÄ«bas atgriež vai nu fiksētu konstantu vērtÄ«bu, vai vienu no divām fiksētām vērtÄ«bām. Reālistiskāka sistēma atgrieztu aplēsi no nepārtraukta vērtÄ«bu diapazona. Piemēram, darbÄ«ba BēgÅ”ana atgriež augstākas lietderÄ«bas vērtÄ«bas, ja aÄ£enta veselÄ«bas stāvoklis ir zems, un darbÄ«ba Attacking atgriež zemākas lietderÄ«bas vērtÄ«bas, ja ienaidnieks ir pārāk spēcÄ«gs. Å Ä« iemesla dēļ darbÄ«bai BēgÅ”ana ir augstāka par Uzbrukumu jebkurā situācijā, kad aÄ£entam Ŕķiet, ka viņam nav pietiekami daudz veselÄ«bas, lai uzvarētu ienaidnieku. Tas ļauj noteikt darbÄ«bām prioritāti, pamatojoties uz jebkuru kritēriju skaitu, padarot Å”o pieeju elastÄ«gāku un mainÄ«gāku nekā uzvedÄ«bas koks vai MFV.

Katrai darbÄ«bai ir daudz nosacÄ«jumu programmas aprēķināŔanai. Tos var rakstÄ«t skriptu valodā vai kā matemātisko formulu sēriju. Sims, kas simulē varoņa ikdienas rutÄ«nu, pievieno papildu aprēķinu slāni - aÄ£ents saņem virkni "motivācijas", kas ietekmē lietderÄ«bas vērtējumus. Ja varonis ir izsalcis, tas laika gaitā kļūs vēl izsalkuÅ”i, un EatFood darbÄ«bas lietderÄ«bas vērtÄ«ba palielināsies, lÄ«dz varonis to izpildÄ«s, samazinot izsalkuma lÄ«meni un atgriežot EatFood vērtÄ«bu uz nulli.

Ideja par darbÄ«bu atlasi, pamatojoties uz vērtÄ“Å”anas sistēmu, ir diezgan vienkārÅ”a, tāpēc uz utilÄ«tu balstÄ«tu sistēmu var izmantot kā daļu no AI lēmumu pieņemÅ”anas procesiem, nevis kā pilnÄ«gu to aizstājēju. Lēmumu koks var pieprasÄ«t divu pakārtoto mezglu lietderÄ«bas novērtējumu un atlasÄ«t augstāko. LÄ«dzÄ«gi uzvedÄ«bas kokam var bÅ«t salikts lietderÄ«bas mezgls, lai novērtētu darbÄ«bu lietderÄ«bu, lai izlemtu, kuru bērnu izpildÄ«t.

Kustība un navigācija

IepriekŔējos piemēros mums bija platforma, kuru mēs pārvietojām pa kreisi vai pa labi, un apsargs, kas patrulēja vai uzbruka. Bet kā tieÅ”i mēs rÄ«kojamies ar aÄ£entu kustÄ«bu noteiktā laika periodā? Kā mēs uzstādām ātrumu, kā izvairāmies no ŔķērŔļiem un kā mēs plānojam marÅ”rutu, kad nokļūt galamērÄ·Ä« ir grÅ«tāk, nekā braukt pa taisnu lÄ«niju? ApskatÄ«sim Å”o.

Vadība

Sākotnējā posmā mēs pieņemsim, ka katram aÄ£entam ir ātruma vērtÄ«ba, kas ietver to, cik ātri tas pārvietojas un kādā virzienā. To var izmērÄ«t metros sekundē, kilometros stundā, pikseļos sekundē utt. Atsaucot atmiņā Sense/Think/Act cilpu, mēs varam iedomāties, ka daļa Think izvēlas ātrumu, bet daļa DarbÄ«ba piemēro Å”o ātrumu aÄ£entam. Parasti spēlēm ir fizikas sistēma, kas veic Å”o uzdevumu jÅ«su vietā, apgÅ«stot katra objekta ātruma vērtÄ«bu un pielāgojot to. Tāpēc jÅ«s varat atstāt AI ar vienu uzdevumu - izlemt, kādam ātrumam vajadzētu bÅ«t aÄ£entam. Ja zināt, kur aÄ£entam jāatrodas, tad tas jāpārvieto pareizajā virzienā ar noteiktu ātrumu. Ä»oti triviāls vienādojums:

wish_travel = galamērÄ·a_pozÄ«cija ā€” aÄ£enta_pozÄ«cija

Iedomājieties 2D pasauli. AÄ£ents atrodas punktā (-2,-2), galamērÄ·is atrodas kaut kur ziemeļaustrumos punktā (30, 20), un nepiecieÅ”amais ceļŔ, lai aÄ£ents tur nokļūtu, ir (32, 22). Pieņemsim, ka Ŕīs pozÄ«cijas mēra metros ā€“ ja pieņemsim, ka aÄ£enta ātrums ir 5 metri sekundē, tad mēs mērogosim savu nobÄ«des vektoru un iegÅ«sim ātrumu aptuveni (4.12, 2.83). Izmantojot Å”os parametrus, aÄ£ents galamērÄ·Ä« nonāktu gandrÄ«z 8 sekundēs.

JÅ«s jebkurā laikā varat pārrēķināt vērtÄ«bas. Ja aÄ£ents bÅ«tu pusceļā lÄ«dz mērÄ·im, kustÄ«ba bÅ«tu uz pusi mazāka, bet tā kā aÄ£enta maksimālais ātrums ir 5 m/s (mēs to nolēmām iepriekÅ”), ātrums bÅ«s tāds pats. Tas darbojas arÄ« kustÄ«giem mērÄ·iem, ļaujot aÄ£entam veikt nelielas izmaiņas, kad tie pārvietojas.

Taču mēs vēlamies vairāk variāciju ā€“ piemēram, lēnām palielinot ātrumu, lai modelētu tēlu, kas pāriet no stāvÄ“Å”anas uz skrieÅ”anu. To paÅ”u var izdarÄ«t beigās pirms apstāŔanās. Å Ä«s funkcijas ir pazÄ«stamas kā stÅ«rÄ“Å”anas darbÄ«bas, un katrai no tām ir specifiski nosaukumi: MeklÄ“Å”ana, BēgÅ”ana, IeraÅ”anās utt. Ideja ir tāda, ka paātrinājuma spēkus var pielietot aÄ£enta ātrumam, pamatojoties uz aÄ£enta pozÄ«cijas un paÅ”reizējā ātruma salÄ«dzināŔanu ar galamērÄ·i. lai izmantotu dažādas metodes virzÄ«bai uz mērÄ·i.

Katrai uzvedÄ«bai ir nedaudz atŔķirÄ«gs mērÄ·is. MeklÄ“Å”ana un ieraÅ”anās ir veidi, kā pārvietot aÄ£entu uz galamērÄ·i. ŠķērŔļu novērÅ”ana un atdalÄ«Å”ana pielāgo aÄ£enta kustÄ«bu, lai izvairÄ«tos no ŔķērŔļiem ceļā uz mērÄ·i. IzlÄ«dzināŔana un kohēzija nodroÅ”ina aÄ£entu kustÄ«bu kopā. Jebkuru skaitu dažādu stÅ«rÄ“Å”anas darbÄ«bu var summēt, lai iegÅ«tu vienu ceļa vektoru, ņemot vērā visus faktorus. AÄ£ents, kas izmanto ieraÅ”anās, atdalÄ«Å”anas un ŔķērŔļu novērÅ”anas darbÄ«bas, lai izvairÄ«tos no sienām un citiem aÄ£entiem. Å Ä« pieeja labi darbojas atklātās vietās bez nevajadzÄ«gām detaļām.

Sarežģītākos apstākļos dažādu uzvedÄ«bu pievienoÅ”ana darbojas sliktāk - piemēram, aÄ£ents var iestrēgt sienā konflikta starp IeraÅ”anos un ŔķērŔļu novērÅ”anu dēļ. Tāpēc jums ir jāapsver iespējas, kas ir sarežģītākas nekā vienkārÅ”i visu vērtÄ«bu pievienoÅ”ana. Veids ir Ŕāds: tā vietā, lai saskaitÄ«tu katras uzvedÄ«bas rezultātus, varat apsvērt kustÄ«bu dažādos virzienos un izvēlēties labāko variantu.

Tomēr sarežģītā vidē ar strupceļiem un izvēli, kuru ceļu iet, mums bÅ«s nepiecieÅ”ams kaut kas vēl progresÄ«vāks.

CeļŔ

StÅ«rÄ“Å”anas izturÄ“Å”anās ir lieliski piemērota vienkārÅ”ai kustÄ«bai atklātā vietā (futbola laukumā vai arēnā), kur nokļūŔana no A lÄ«dz B ir taisna taka ar tikai nelieliem apvedceļiem ap ŔķērŔļiem. Sarežģītiem marÅ”rutiem mums ir nepiecieÅ”ama ceļa atraÅ”ana, kas ir veids, kā izpētÄ«t pasauli un izlemt par marÅ”rutu caur to.

VisvienkārŔākais ir uzlikt režģi katram laukumam blakus aÄ£entam un novērtēt, kurÅ” no tiem drÄ«kst pārvietoties. Ja kāds no tiem ir galamērÄ·is, tad sekojiet marÅ”rutam no katra laukuma uz iepriekŔējo, lÄ«dz sasniedzat sākumu. Å is ir marÅ”ruts. Pretējā gadÄ«jumā atkārtojiet Å”o procesu ar citiem blakus esoÅ”ajiem laukumiem, lÄ«dz atrodat galamērÄ·i vai izbeidzas laukums (tas nozÄ«mē, ka nav iespējama marÅ”ruta). Tas ir tas, kas formāli tiek saukts par meklÄ“Å”anas platumu vai BFS (meklÄ“Å”anas algoritms pēc platuma). Ik uz soļa viņŔ skatās uz visām pusēm (tātad platums, "platums"). MeklÄ“Å”anas telpa ir kā viļņu fronte, kas kustas, lÄ«dz sasniedz vēlamo vietu ā€“ meklÄ“Å”anas telpa katrā solÄ« paplaÅ”inās, lÄ«dz tiek iekļauts beigu punkts, pēc kura to var izsekot lÄ«dz sākumam.

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Rezultātā jÅ«s saņemsiet sarakstu ar laukumiem, pa kuriem tiek sastādÄ«ts vēlamais marÅ”ruts. Å is ir ceļŔ (tātad, ceļa atraÅ”ana) ā€” to vietu saraksts, kuras aÄ£ents apmeklēs, sekojot galamērÄ·im.

Ņemot vērā to, ka mēs zinām katra kvadrāta atraÅ”anās vietu pasaulē, mēs varam izmantot stÅ«rÄ“Å”anas uzvedÄ«bu, lai pārvietotos pa ceļu - no 1. mezgla uz 2. mezglu, tad no 2. mezgla uz 3. mezglu un tā tālāk. VienkārŔākais variants ir virzÄ«ties uz nākamā laukuma centru, bet vēl labāks variants ir apstāties malas vidÅ« starp paÅ”reizējo un nākamo laukumu. Pateicoties tam, aÄ£ents varēs nogriezt stÅ«rus asos pagriezienos.

BFS algoritmam ir arÄ« trÅ«kumi - tas pēta tikpat daudz kvadrātu ā€œnepareizajāā€ virzienā, cik ā€œpareizajāā€ virzienā. Å eit tiek izmantots sarežģītāks algoritms, ko sauc par A* (zvaigzne). Tas darbojas tāpat, bet tā vietā, lai akli pārbaudÄ«tu kaimiņu kvadrātus (pēc tam kaimiņu kaimiņus, pēc tam kaimiņu kaimiņus un tā tālāk), tas apkopo mezglus sarakstā un sakārto tos tā, lai nākamais pārbaudÄ«tais mezgls vienmēr bÅ«tu tāds, kas ved uz Ä«sāko ceļu. Mezgli tiek kārtoti, pamatojoties uz heiristisku metodi, kurā tiek ņemtas vērā divas lietas ā€” hipotētiskā marÅ”ruta ā€œizmaksasā€ uz vēlamo laukumu (ieskaitot visas ceļa izmaksas) un aplēses par to, cik tālu Å”is laukums atrodas no galamērÄ·a (novirzot meklÄ“Å”anu pareizais virziens).

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Å is piemērs parāda, ka aÄ£ents vienlaikus izpēta vienu kvadrātu, katru reizi izvēloties blakus esoÅ”o, kas ir visdaudzsoloŔākais. Rezultātā iegÅ«tais ceļŔ ir tāds pats kā BFS, taču Å”ajā procesā tika ņemts vērā mazāk laukumu, kas bÅ«tiski ietekmē spēles veiktspēju.

Kustība bez režģa

Taču lielākā daļa spēļu nav izkārtotas režģī, un bieži vien to nav iespējams izdarīt, neupurējot reālismu. Ir vajadzīgi kompromisi. Kādam izmēram jābūt kvadrātiem? Pārāk lieli, un tie nespēs pareizi attēlot mazus koridorus vai pagriezienus, pārāk mazi, un būs pārāk daudz laukumu, ko meklēt, kas galu galā prasīs daudz laika.

Vispirms ir jāsaprot, ka tÄ«kls sniedz mums savienoto mezglu grafiku. Algoritmi A* un BFS faktiski darbojas uz grafikiem, un tiem vispār nerÅ«p mÅ«su tÄ«kls. Mēs varētu novietot mezglus jebkurā spēles pasaulē: kamēr pastāv savienojums starp jebkuriem diviem savienotiem mezgliem, kā arÄ« starp sākuma un beigu punktiem un vismaz vienu no mezgliem, algoritms darbosies tikpat labi kā iepriekÅ”. To bieži sauc par marÅ”ruta punktu sistēmu, jo katrs mezgls pārstāv nozÄ«mÄ«gu vietu pasaulē, kas var bÅ«t daļa no jebkura skaita hipotētisku ceļu.

Kā izveidot spēļu AI: rokasgrāmata iesācējiem
1. piemērs: mezgls katrā kvadrātā. MeklÄ“Å”ana sākas no mezgla, kurā atrodas aÄ£ents, un beidzas vajadzÄ«gā kvadrāta mezglā.

Kā izveidot spēļu AI: rokasgrāmata iesācējiem
2. piemērs: mazāka mezglu (ceļa punktu) kopa. MeklÄ“Å”ana sākas aÄ£enta laukumā, iziet cauri vajadzÄ«gajam mezglu skaitam un pēc tam turpinās lÄ«dz galamērÄ·im.

Å Ä« ir pilnÄ«gi elastÄ«ga un jaudÄ«ga sistēma. Taču ir nepiecieÅ”ama piesardzÄ«ba, izlemjot, kur un kā novietot pieturas punktu, pretējā gadÄ«jumā aÄ£enti var vienkārÅ”i neredzēt tuvāko punktu un nevarēs sākt ceļu. BÅ«tu vieglāk, ja mēs varētu automātiski izvietot pieturas punktus, pamatojoties uz pasaules Ä£eometriju.

Å eit parādās navigācijas siets vai navmesh (navigācijas tÄ«kls). Parasti tas ir trijstÅ«ru 2D tÄ«kls, kas tiek pārklāts ar pasaules Ä£eometriju ā€” visur, kur aÄ£entam ir atļauts staigāt. Katrs acs trijstÅ«ris kļūst par mezglu diagrammā, un tam ir ne vairāk kā trÄ«s blakus esoÅ”ie trÄ«sstÅ«ri, kas kļūst par diagrammas blakus mezgliem.

Å is attēls ir piemērs no Unity dzinēja - tas analizēja Ä£eometriju pasaulē un izveidoja navsietu (ekrānuzņēmumā gaiÅ”i zilā krāsā). Katrs navigācijas tÄ«kla daudzstÅ«ris ir apgabals, kurā aÄ£ents var stāvēt vai pārvietoties no viena daudzstÅ«ra uz citu daudzstÅ«ri. Å ajā piemērā daudzstÅ«ri ir mazāki par stāviem, uz kuriem tie atrodas - tas tiek darÄ«ts, lai ņemtu vērā aÄ£enta izmēru, kas pārsniedz tā nominālo pozÄ«ciju.

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Mēs varam meklēt marÅ”rutu caur Å”o tÄ«klu, atkal izmantojot A* algoritmu. Tas mums iegÅ«s gandrÄ«z ideālu marÅ”rutu pasaulē, kas ņem vērā visu Ä£eometriju un neprasa liekus mezglus un ceļa punktu izveidi.

Ceļa meklÄ“Å”ana ir pārāk plaÅ”a tēma, kurai nepietiek ar vienu raksta sadaļu. Ja vēlaties to izpētÄ«t sÄ«kāk, tad tas palÄ«dzēs Amit Patel vietne.

plānoŔana

Ar ceļa atraÅ”anu esam iemācÄ«juÅ”ies, ka dažreiz nepietiek tikai izvēlēties virzienu un pārvietoties ā€“ mums ir jāizvēlas marÅ”ruts un jāveic daži pagriezieni, lai nokļūtu vēlamajā galamērÄ·Ä«. Mēs varam vispārināt Å”o ideju: mērÄ·a sasniegÅ”ana nav tikai nākamais solis, bet gan vesela secÄ«ba, kurā dažreiz jums ir jāskatās uz priekÅ”u vairākus soļus, lai noskaidrotu, kam vajadzētu bÅ«t pirmajam. To sauc par plānoÅ”anu. Ceļa atraÅ”anu var uzskatÄ«t par vienu no vairākiem plānoÅ”anas paplaÅ”inājumiem. Runājot par mÅ«su ciklu Sense/Think/Act, Å”ajā daļā DomāŔanas daļa plāno vairākas darbÄ«bas daļas nākotnei.

ApskatÄ«sim galda spēles Magic: The Gathering piemēru. Vispirms mēs ejam ar Ŕādu kārÅ”u komplektu rokās:

  • Purvs - dod 1 melno manu (zemes karti).
  • Mežs - dod 1 zaļo manu (zemes karti).
  • Fugitive Wizard ā€” lai izsauktu 1 zilo manu.
  • Elvish Mystic ā€” lai izsauktu 1 zaļo manu.

Mēs ignorējam atlikuŔās trÄ«s kārtis, lai bÅ«tu vieglāk. Saskaņā ar noteikumiem spēlētājam ir atļauts izspēlēt 1 zemes karti vienā gājienā, viņŔ var ā€œpiesitā€ Å”ai kārtei, lai no tās izvilktu manu, un pēc tam mest burvestÄ«bas (tostarp izsaukt radÄ«jumu) atbilstoÅ”i manas daudzumam. Šādā situācijā spēlētājs zina, ka jāspēlē Forest, jāpiesit 1 zaļajam manam un pēc tam jāizsauc Elvish Mystic. Bet kā spēle AI to var izdomāt?

Viegla plānoŔana

Triviālā pieeja ir izmēģināt katru darbÄ«bu pēc kārtas, lÄ«dz vairs nav piemērotas. AplÅ«kojot kārtis, AI redz, ko Swamp var spēlēt. Un viņŔ to spēlē. Vai Å”ajā pagriezienā ir vēl kādas darbÄ«bas? Tas nevar izsaukt Elvish Mystic vai Fugitive Wizard, jo tiem ir nepiecieÅ”ama attiecÄ«gi zaļā un zilā mana, lai tos izsauktu, savukārt Swamp nodroÅ”ina tikai melno manu. Un viņŔ vairs nevarēs spēlēt Forestu, jo viņŔ jau ir spēlējis Purvu. Tādējādi spēle AI ievēroja noteikumus, taču darÄ«ja to slikti. Var uzlabot.

Plānojot var atrast sarakstu ar darbÄ«bām, kas noved spēli vēlamajā stāvoklÄ«. Tāpat kā katram ceļa laukumam bija kaimiņi (ceļa atraÅ”anā), katrai plāna darbÄ«bai ir arÄ« kaimiņi vai pēcteči. Mēs varam meklēt Ŕīs darbÄ«bas un turpmākās darbÄ«bas, lÄ«dz sasniedzam vēlamo stāvokli.

MÅ«su piemērā vēlamais rezultāts ir ā€œizsauc radÄ«jumu, ja iespējamsā€. Pagrieziena sākumā redzam tikai divas iespējamās darbÄ«bas, ko pieļauj spēles noteikumi:

1. Spēlējiet Swamp (rezultāts: Swamp spēlē)
2. Spēlēt Forest (rezultāts: Mežs spēlē)

Katra veiktā darbÄ«ba var izraisÄ«t turpmākas darbÄ«bas un slēgt citas, atkal atkarÄ«bā no spēles noteikumiem. Iedomājieties, ka mēs spēlējām Swamp - tas noņems Swamp kā nākamo soli (mēs to jau spēlējām), un tas noņems arÄ« Forest (jo saskaņā ar noteikumiem jÅ«s varat izspēlēt vienu zemes karti katrā gājienā). Pēc tam AI kā nākamo soli pievieno 1 melnās manas iegÅ«Å”anu, jo nav citu iespēju. Ja viņŔ iet uz priekÅ”u un izvēlēsies Tap the Swamp, viņŔ saņems 1 vienÄ«bu melnā mana un nevarēs ar to neko darÄ«t.

1. Spēlējiet Swamp (rezultāts: Swamp spēlē)
1.1 ā€œTapā€ purvs (rezultāts: purvs ā€œpiesistsā€, +1 vienÄ«ba melnā mana)
Nav pieejama neviena darbÄ«ba ā€” END
2. Spēlēt Forest (rezultāts: Mežs spēlē)

DarbÄ«bu saraksts bija Ä«ss, nonācām strupceļā. Mēs atkārtojam procesu nākamajam solim. Mēs spēlējam Forest, atveram darbÄ«bu ā€œdabÅ« 1 zaļo manuā€, kas savukārt atklās treÅ”o darbÄ«bu - izsauc Elvish Mystic.

1. Spēlējiet Swamp (rezultāts: Swamp spēlē)
1.1 ā€œTapā€ purvs (rezultāts: purvs ā€œpiesistsā€, +1 vienÄ«ba melnā mana)
Nav pieejama neviena darbÄ«ba ā€” END
2. Spēlēt Forest (rezultāts: Mežs spēlē)
2.1. ā€œTapā€ mežs (rezultāts: mežs ir ā€œpiesistsā€, +1 vienÄ«ba zaļās manas)
2.1.1. Izsaukt Elvish Mystic (rezultāts: Elvish Mystic spēlē, -1 zaļā mana)
Nav pieejama neviena darbÄ«ba ā€” END

Visbeidzot, mēs izpētījām visas iespējamās darbības un atradām plānu, kas izsauc radījumu.

Å is ir ļoti vienkārÅ”ots piemērs. Ieteicams izvēlēties labāko iespējamo plānu, nevis tikai jebkuru plānu, kas atbilst dažiem kritērijiem. Parasti ir iespējams novērtēt potenciālos plānus, pamatojoties uz to Ä«stenoÅ”anas rezultātu vai kopējo ieguvumu. JÅ«s varat iegÅ«t sev 1 punktu par zemes kartes izspēlÄ“Å”anu un 3 punktus par radÄ«juma izsaukÅ”anu. Spēlēt Purvu bÅ«tu 1 punkta plāns. Un spēlējot Forest ā†’ Tap the Forest ā†’ izsauc Elvish Mystic uzreiz iedos 4 punktus.

Šādi plānoÅ”ana darbojas programmā Magic: The Gathering, taču tā pati loÄ£ika attiecas arÄ« uz citām situācijām. Piemēram, bandinieka pārvietoÅ”ana, lai atbrÄ«votu vietu bÄ«skapam, lai pārvietotos Å”ahā. Vai arÄ« paslēpieties aiz sienas, lai droÅ”i fotografētu Ŕādā formātā XCOM. Kopumā jÅ«s saprotat domu.

Uzlabota plānoŔana

Dažreiz ir pārāk daudz iespējamo darbību, lai apsvērtu visas iespējamās iespējas. Atgriežoties pie piemēra ar Magic: The Gathering: pieņemsim, ka spēlē un jūsu rokā ir vairākas zemes un radījumu kārtis - iespējamo gājienu kombināciju skaits var būt desmitiem. Problēmai ir vairāki risinājumi.

Pirmā metode ir atpakaļgaitas ķēde. Tā vietā, lai izmēģinātu visas kombinācijas, labāk ir sākt ar gala rezultātu un mēģināt atrast tieÅ”o marÅ”rutu. Tā vietā, lai dotos no koka saknes uz konkrētu lapu, mēs virzāmies pretējā virzienā ā€“ no lapas uz sakni. Å Ä« metode ir vienkārŔāka un ātrāka.

Ja ienaidniekam ir 1 veselība, jūs varat atrast plānu "nodarīt 1 vai vairāk bojājumu". Lai to panāktu, ir jāievēro vairāki nosacījumi:

1. Bojājumus var radÄ«t burvestÄ«ba ā€“ tai jābÅ«t rokā.
2. Lai veiktu burvestību, jums ir nepiecieŔams mana.
3. Lai iegūtu manu, jāizspēlē zemes kārts.
4. Lai izspēlētu zemes karti, tai ir jābūt rokā.

Vēl viens veids ir vislabākā pirmā meklÄ“Å”ana. Tā vietā, lai izmēģinātu visus ceļus, mēs izvēlamies piemērotāko. Visbiežāk Ŕī metode nodroÅ”ina optimālu plānu bez liekām meklÄ“Å”anas izmaksām. A* ir labākās pirmās meklÄ“Å”anas veids ā€” no sākuma pārbaudot daudzsoloŔākos marÅ”rutus, tas jau var atrast labāko ceļu, nepārbaudot citas iespējas.

Interesanta un arvien populārāka labākā pirmā meklÄ“Å”anas iespēja ir Monte Carlo Tree Search. Tā vietā, lai uzminētu, kuri plāni ir labāki par citiem, izvēloties katru nākamo darbÄ«bu, algoritms katrā solÄ« izvēlas nejauÅ”us pēctečus, lÄ«dz tas sasniedz beigas (kad plāns izraisÄ«ja uzvaru vai sakāvi). Pēc tam gala rezultāts tiek izmantots, lai palielinātu vai samazinātu iepriekŔējo opciju svaru. Atkārtojot Å”o procesu vairākas reizes pēc kārtas, algoritms sniedz labu novērtējumu tam, kāds ir labākais nākamais gājiens, pat ja situācija mainās (ja ienaidnieks rÄ«kojas, lai traucētu spēlētājam).

Neviens stāsts par plānoÅ”anu spēlēs nebÅ«tu pilnÄ«gs bez uz mērÄ·i orientētas rÄ«cÄ«bas plānoÅ”anas vai GOAP (mērÄ·tiecÄ«gas rÄ«cÄ«bas plānoÅ”anas). Å Ä« ir plaÅ”i izmantota un apspriesta metode, taču, izņemot dažas atŔķirÄ«gas detaļas, tā bÅ«tÄ«bā ir atgriezeniskā ķēdes metode, par kuru mēs runājām iepriekÅ”. Ja mērÄ·is bija "iznÄ«cināt spēlētāju" un spēlētājs atrodas aiz aizsega, plāns varētu bÅ«t Ŕāds: iznÄ«cināt ar granātu ā†’ iegÅ«t ā†’ mest.

Parasti ir vairāki mērķi, katram ir sava prioritāte. Ja augstākās prioritātes mērķi nevar izpildīt (neviena darbību kombinācija nerada plānu "nogalināt spēlētāju", jo spēlētājs nav redzams), AI atgriezīsies pie zemākas prioritātes mērķiem.

Apmācība un adaptācija

Mēs jau teicām, ka spēļu AI parasti neizmanto maŔīnmācÄ«Å”anos, jo tā nav piemērota aÄ£entu pārvaldÄ«bai reāllaikā. Bet tas nenozÄ«mē, ka jÅ«s nevarat kaut ko aizņemties no Ŕīs jomas. Strēlniekā gribam pretinieku, no kura varam kaut ko mācÄ«ties. Piemēram, uzziniet par labākajām pozÄ«cijām kartē. Vai arÄ« pretinieks kaujas spēlē, kurÅ” bloķētu spēlētāja bieži izmantotās kombinētās kustÄ«bas, motivējot viņu izmantot citus. Tātad maŔīnmācÄ«ba Ŕādās situācijās var bÅ«t diezgan noderÄ«ga.

Statistika un varbūtības

Pirms iedziļināmies sarežģītos piemēros, redzēsim, cik tālu mēs varam iet, veicot dažus vienkārÅ”us mērÄ«jumus un izmantojot tos lēmumu pieņemÅ”anai. Piemēram, reāllaika stratēģija ā€“ kā noteikt, vai spēlētājs var uzsākt uzbrukumu pirmajās spēles minÅ«tēs un kādu aizsardzÄ«bu pret to sagatavot? Mēs varam izpētÄ«t spēlētāja pagātnes pieredzi, lai saprastu, kādas varētu bÅ«t turpmākās reakcijas. Sākumā mums nav Ŕādu neapstrādātu datu, bet mēs varam tos savākt - katru reizi, kad AI spēlē pret cilvēku, tas var reÄ£istrēt pirmā uzbrukuma laiku. Pēc dažām sesijām mēs iegÅ«sim vidējo laiku, kas bÅ«s nepiecieÅ”ams, lai spēlētājs nākotnē varētu uzbrukt.

Problēma ir arÄ« ar vidējām vērtÄ«bām: ja spēlētājs 20 reizes steidzās un 20 reizes spēlēja lēni, tad nepiecieÅ”amās vērtÄ«bas bÅ«s kaut kur pa vidu, un tas mums neko noderÄ«gu nedos. Viens no risinājumiem ir ierobežot ievades datus - var ņemt vērā pēdējos 20 gabalus.

LÄ«dzÄ«ga pieeja tiek izmantota, novērtējot noteiktu darbÄ«bu iespējamÄ«bu, pieņemot, ka spēlētāja pagātnes preferences bÅ«s tādas paÅ”as arÄ« nākotnē. Ja spēlētājs mums uzbrÅ«k piecas reizes ar ugunsbumbu, divas reizes ar zibeni un vienreiz ar tuvcīņu, ir skaidrs, ka viņŔ dod priekÅ”roku ugunsbumbai. Ekstrapolēsim un redzēsim dažādu ieroču izmantoÅ”anas varbÅ«tÄ«bu: ugunsbumba=62,5%, zibens=25% un tuvcīņa=12,5%. MÅ«su spēlei AI ir jāsagatavojas, lai pasargātu sevi no uguns.

Vēl viena interesanta metode ir izmantot Naive Bayes klasifikatoru, lai izpētÄ«tu lielus ievades datu apjomus un klasificētu situāciju tā, lai AI reaģētu vēlamajā veidā. Bajesa klasifikatori ir vislabāk pazÄ«stami ar to izmantoÅ”anu e-pasta surogātpasta filtros. Tur viņi pārbauda vārdus, salÄ«dzina tos ar to, kur Å”ie vārdi ir parādÄ«juÅ”ies iepriekÅ” (surogātpasta vai nē), un izdara secinājumus par ienākoÅ”ajiem e-pastiem. Mēs varam darÄ«t to paÅ”u pat ar mazāku ievadi. Pamatojoties uz visu noderÄ«go informāciju, ko redz AI (piemēram, kādas ienaidnieka vienÄ«bas ir izveidotas vai kādas burvestÄ«bas tās izmanto, vai kādas tehnoloÄ£ijas viņi pētÄ«ja), un gala rezultātu (karÅ” vai miers, steiga vai aizstāvÄ«ba utt.) - mēs izvēlēsimies vēlamo AI uzvedÄ«bu.

Visas Ŕīs apmācÄ«bas metodes ir pietiekamas, taču ir vēlams tās izmantot, pamatojoties uz testÄ“Å”anas datiem. AI iemācÄ«sies pielāgoties dažādām stratēģijām, kuras ir izmantojuÅ”i jÅ«su spēļu pārbaudÄ«tāji. AI, kas pielāgojas atskaņotājam pēc izlaiÅ”anas, var kļūt pārāk paredzams vai pārāk grÅ«ti uzveicams.

Vērtībās balstīta adaptācija

Ņemot vērā mÅ«su spēļu pasaules saturu un noteikumus, mēs varam mainÄ«t vērtÄ«bu kopu, kas ietekmē lēmumu pieņemÅ”anu, nevis vienkārÅ”i izmantot ievades datus. Mēs to darām:

  • Ä»aujiet AI savākt datus par pasaules stāvokli un galvenajiem notikumiem spēles laikā (kā iepriekÅ”).
  • MainÄ«sim dažas svarÄ«gas vērtÄ«bas, pamatojoties uz Å”iem datiem.
  • Mēs Ä«stenojam savus lēmumus, pamatojoties uz Å”o vērtÄ«bu apstrādi vai novērtÄ“Å”anu.

Piemēram, aÄ£entam ir vairākas telpas, no kurām izvēlēties pirmās personas Ŕāvēja kartē. Katrai telpai ir sava vērtÄ«ba, kas nosaka, cik vēlams to apmeklēt. AI nejauÅ”i izvēlas, uz kuru telpu doties, pamatojoties uz vērtÄ«bu. Pēc tam aÄ£ents atceras, kurā telpā viņŔ tika nogalināts, un samazina tās vērtÄ«bu (iespējamÄ«bu, ka viņŔ tur atgriezÄ«sies). LÄ«dzÄ«gi arÄ« pretējai situācijai ā€“ ja aÄ£ents iznÄ«cina daudzus pretiniekus, tad telpas vērtÄ«ba pieaug.

Markova modelis

Ko darīt, ja mēs izmantotu apkopotos datus, lai veiktu prognozes? Ja mēs noteiktu laiku atcerēsimies katru istabu, kurā redzam spēlētāju, mēs prognozēsim, uz kuru istabu spēlētājs varētu doties. Izsekojot un reģistrējot spēlētāja kustības telpās (vērtības), mēs varam tās paredzēt.

Ņemsim trīs istabas: sarkanu, zaļu un zilu. Un arī novērojumi, ko fiksējām, skatoties spēles sesiju:

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Novērojumu skaits katrā telpā ir gandrÄ«z vienāds - mēs joprojām nezinām, kur izveidot labu vietu slazdam. Statistikas apkopoÅ”anu apgrÅ«tina arÄ« spēlētāju atdzimÅ”ana, kas vienmērÄ«gi parādās visā kartē. Bet dati par nākamo telpu, kurā viņi ienāk pēc parādÄ«Å”anās kartē, jau ir noderÄ«gi.

Redzams, ka zaļā istaba spēlētājiem piestāv - no sarkanās istabas uz to pārceļas lielākā daļa cilvēku, no kuriem 50% paliek tur tālāk. Gluži pretēji, zilā istaba nav populāra, uz to gandrīz neviens neiet, un, ja iet, tad ilgi neuzturas.

Taču dati stāsta par kaut ko svarÄ«gāku ā€“ kad spēlētājs atrodas zilā istabā, nākamā telpa, kurā mēs viņu redzam, bÅ«s sarkana, nevis zaļa. Lai gan zaļā istaba ir populārāka par sarkano istabu, situācija mainās, ja spēlētājs atrodas zilajā istabā. Nākamais stāvoklis (t.i., telpa, uz kuru spēlētājs dosies) ir atkarÄ«gs no iepriekŔējā stāvokļa (t.i., telpas, kurā spēlētājs paÅ”laik atrodas). Tā kā mēs pētām atkarÄ«bas, mēs veiksim precÄ«zākas prognozes nekā tad, ja mēs vienkārÅ”i skaitÄ«tu novērojumus neatkarÄ«gi.

Nākotnes stāvokļa prognozÄ“Å”anu, pamatojoties uz datiem no pagātnes stāvokļa, sauc par Markova modeli, un Ŕādus piemērus (ar telpām) sauc par Markova ķēdēm. Tā kā modeļi atspoguļo izmaiņu iespējamÄ«bu starp secÄ«giem stāvokļiem, tie tiek vizuāli parādÄ«ti kā FSM ar varbÅ«tÄ«bu ap katru pāreju. IepriekÅ” mēs izmantojām MFV, lai attēlotu aÄ£enta uzvedÄ«bas stāvokli, taču Å”is jēdziens attiecas uz jebkuru stāvokli neatkarÄ«gi no tā, vai tas ir saistÄ«ts ar aÄ£entu vai nē. Å ajā gadÄ«jumā stāvokļi apzÄ«mē telpu, kuru aÄ£ents aizņem:

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Tas ir vienkārÅ”s veids, kā attēlot relatÄ«vo stāvokļa izmaiņu iespējamÄ«bu, dodot AI zināmu iespēju paredzēt nākamo stāvokli. Varat paredzēt vairākus soļus uz priekÅ”u.

Ja spēlētājs atrodas zaļajā zālē, pastāv 50% iespēja, ka viņŔ tur paliks nākamreiz, kad tiks novērots. Bet kāda ir iespēja, ka viņŔ joprojām bÅ«s tur pat pēc tam? Pastāv ne tikai iespēja, ka spēlētājs palika zaļajā istabā pēc diviem novērojumiem, bet arÄ« iespēja, ka viņŔ aizgāja un atgriezās. Å eit ir jaunā tabula, kurā ņemti vērā jaunie dati:

Kā izveidot spēļu AI: rokasgrāmata iesācējiem

Tas parāda, ka iespēja redzēt spēlētāju zaļajā istabā pēc diviem novērojumiem bÅ«s vienāda ar 51% - 21%, ka viņŔ bÅ«s no sarkanās istabas, 5% no tiem, ka spēlētājs apmeklēs zilo istabu starp viņiem, un 25%, ka spēlētājs neatstās zaļo istabu.

Tabula ir vienkārÅ”i vizuāls rÄ«ks - procedÅ«rai ir nepiecieÅ”ams tikai reizināt varbÅ«tÄ«bas katrā solÄ«. Tas nozÄ«mē, ka varat ieskatÄ«ties tālā nākotnē ar vienu piebildi: mēs pieņemam, ka iespēja iekļūt telpā ir pilnÄ«bā atkarÄ«ga no paÅ”reizējās telpas. To sauc par Markova Ä«paÅ”umu ā€“ nākotnes stāvoklis ir atkarÄ«gs tikai no tagadnes. Bet tas nav simtprocentÄ«gi precÄ«zs. Spēlētāji var mainÄ«t lēmumus atkarÄ«bā no citiem faktoriem: veselÄ«bas lÄ«meņa vai munÄ«cijas daudzuma. Tā kā mēs Ŕīs vērtÄ«bas nereÄ£istrējam, mÅ«su prognozes bÅ«s mazāk precÄ«zas.

N-grami

Kā ir ar kaujas spēles piemēru un spēlētāja kombinēto gājienu prognozÄ“Å”anu? Tas pats! Taču viena stāvokļa vai notikuma vietā mēs pārbaudÄ«sim visas secÄ«bas, kas veido kombinēto triecienu.

Viens veids, kā to izdarīt, ir saglabāt katru ievadi (piemēram, Kick, Punch vai Block) buferī un ierakstīt visu buferi kā notikumu. Tātad spēlētājs atkārtoti nospiež Kick, Kick, Punch, lai izmantotu SuperDeathFist uzbrukumu, AI sistēma saglabā visus ievades datus buferī un atceras pēdējās trīs, kas izmantotas katrā solī.

Kā izveidot spēļu AI: rokasgrāmata iesācējiem
(Treknrakstā norādītās līnijas ir tad, kad spēlētājs uzsāk SuperDeathFist uzbrukumu.)

AI redzēs visas opcijas, kad spēlētājs izvēlēsies Kick, kam sekos vēl viens Kick, un pēc tam ievēros, ka nākamā ievade vienmēr ir Punch. Tas ļaus aģentam paredzēt SuperDeathFist kombinēto kustību un, ja iespējams, to bloķēt.

Å Ä«s notikumu secÄ«bas sauc par N-gramiem, kur N ir saglabāto elementu skaits. IepriekŔējā piemērā tas bija 3 grami (trigrams), kas nozÄ«mē: pirmie divi ieraksti tiek izmantoti, lai paredzētu treÅ”o. AttiecÄ«gi 5 gramos pirmie četri ieraksti paredz piekto un tā tālāk.

Dizaineram rÅ«pÄ«gi jāizvēlas N-gramu izmērs. Mazākam N ir nepiecieÅ”ams mazāk atmiņas, taču tajā ir arÄ« mazāk vēstures. Piemēram, 2 grami (bigrami) ierakstÄ«s Kick, Kick vai Kick, Punch, bet nevarēs saglabāt Kick, Kick, Punch, tāpēc AI nereaģēs uz SuperDeathFist kombināciju.

No otras puses, lielākam skaitam ir nepiecieÅ”ams vairāk atmiņas, un AI bÅ«s grÅ«tāk apmācÄ«t, jo bÅ«s daudz vairāk iespēju. Ja jums bÅ«tu trÄ«s iespējamie Kick, Punch vai Block ievades veidi, un mēs izmantotu 10 gramus, tas bÅ«tu aptuveni 60 tÅ«kstoÅ”i dažādu iespēju.

Bigramu modelis ir vienkārÅ”a Markova ķēde ā€” katrs pagātnes stāvokļa/paÅ”reizējā stāvokļa pāris ir bigrams, un jÅ«s varat paredzēt otro stāvokli, pamatojoties uz pirmo. 3 gramus un lielākus N gramus var uzskatÄ«t arÄ« par Markova ķēdēm, kur visi elementi (izņemot pēdējo N gramā) kopā veido pirmo stāvokli, bet pēdējais elements ā€“ otro. Cīņas spēles piemērs parāda iespēju pāriet no Kick and Kick stāvokļa uz Kick and Punch stāvokli. Apstrādājot vairākus ievades vēstures ierakstus kā vienu vienÄ«bu, mēs bÅ«tÄ«bā pārveidojam ievades secÄ«bu par daļu no visa stāvokļa. Tas dod mums Markova Ä«paŔību, kas ļauj mums izmantot Markova ķēdes, lai paredzētu nākamo ievadi un uzminētu, kāda bÅ«s nākamā kombinācija.

Secinājums

Mēs runājām par izplatÄ«tākajiem instrumentiem un pieejām mākslÄ«gā intelekta attÄ«stÄ«bā. ApskatÄ«jām arÄ« situācijas, kurās tās jāizmanto un kur tās ir Ä«paÅ”i noderÄ«gas.

Ar to vajadzētu pietikt, lai saprastu spēles AI pamatus. Bet, protams, Ŕīs nav visas metodes. Mazāk populāri, bet ne mazāk efektÄ«vi ietver:

  • optimizācijas algoritmi, tostarp kāpÅ”ana kalnos, nolaiÅ”anās no slÄ«puma un Ä£enētiskie algoritmi
  • pretrunÄ«gie meklÄ“Å”anas/plānoÅ”anas algoritmi (minimax un alfa-beta atzaroÅ”ana)
  • klasifikācijas metodes (perceptrons, neironu tÄ«kli un atbalsta vektora maŔīnas)
  • sistēmas aÄ£entu uztveres un atmiņas apstrādei
  • arhitektÅ«ras pieejas AI (hibrÄ«dsistēmas, apakÅ”kopu arhitektÅ«ras un citi veidi, kā AI sistēmas pārklāt)
  • animācijas rÄ«ki (plānoÅ”ana un kustÄ«bu koordinācija)
  • veiktspējas faktori (detalizācijas lÄ«menis, jebkurā laikā un laika sadalÄ«juma algoritmi)

TieÅ”saistes resursi par Å”o tēmu:

1. GameDev.net ir sadaļa ar rakstiem un pamācībām par AIun forums.
2. AiGameDev.com satur daudzas prezentācijas un rakstus par dažādām tēmām, kas saistītas ar spēļu AI izstrādi.
3. GDC Vault ietver tēmas no GDC AI samita, no kurām daudzas ir pieejamas bez maksas.
4. Mājaslapā var atrast arī noderīgus materiālus AI spēļu programmētāju ģilde.
5. Tomijs Tompsons, mākslīgā intelekta pētnieks un spēļu izstrādātājs, veido videoklipus vietnē YouTube AI un spēles ar skaidrojumu un AI izpēti komerciālajās spēlēs.

Grāmatas par Å”o tēmu:

1. Game AI Pro grāmatu sērija ir īsu rakstu krājums, kurā ir paskaidrots, kā ieviest konkrētas funkcijas vai kā atrisināt konkrētas problēmas.

Game AI Pro: Game AI profesionāļu apkopotā gudrība
Game AI Pro 2: Game AI profesionāļu apkopotā gudrība
Game AI Pro 3: Game AI profesionāļu apkopotā gudrība

2. AI Game Programming Wisdom sērija ir Game AI Pro sērijas priekÅ”tecis. Tajā ir senākas metodes, taču gandrÄ«z visas ir aktuālas arÄ« mÅ«sdienās.

AI spēļu programmÄ“Å”anas gudrÄ«ba 1
AI spēļu programmÄ“Å”anas gudrÄ«ba 2
AI spēļu programmÄ“Å”anas gudrÄ«ba 3
AI spēļu programmÄ“Å”anas gudrÄ«ba 4

3. MākslÄ«gais intelekts: mÅ«sdienÄ«ga pieeja ir viens no pamattekstiem ikvienam, kurÅ” vēlas izprast vispārējo mākslÄ«gā intelekta jomu. Å Ä« nav grāmata par spēļu izstrādi ā€“ tā māca AI pamatus.

Avots: www.habr.com

Pievieno komentāru