Aptikau įdomios medžiagos apie dirbtinį intelektą žaidimuose. Su paprastais pavyzdžiais paaiškinami pagrindiniai AI dalykai, o viduje yra daug naudingų įrankių ir metodų patogiam jo kūrimui ir projektavimui. Čia taip pat nurodyta, kaip, kur ir kada juos naudoti.
Dauguma pavyzdžių parašyti pseudokodu, todėl pažangių programavimo žinių nereikia. Po pjūviu yra 35 lapai teksto su paveikslėliais ir gifais, tad ruoškitės.
UPD. Atsiprašau, bet aš jau išverčiau šį straipsnį apie Habré . Galite perskaityti jo versiją , bet straipsnis man kažkodėl praėjo (naudojau paieška, bet kažkas ne taip). Ir kadangi rašau tinklaraštyje, skirtame žaidimų kūrimui, nusprendžiau savo vertimo versiją palikti prenumeratoriams (kai kurie punktai suformatuoti skirtingai, kai kurie kūrėjų patarimu buvo sąmoningai praleisti).
Kas yra AI?
Žaidimo AI sutelkia dėmesį į tai, kokius veiksmus turi atlikti objektas, atsižvelgiant į sąlygas, kuriomis jis yra. Tai paprastai vadinama „protingo agento“ valdymu, kai agentas yra žaidėjo personažas, transporto priemonė, robotas arba kartais kažkas abstraktesnio: visa subjektų grupė ar net civilizacija. Kiekvienu atveju tai yra dalykas, kuris turi matyti savo aplinką, remdamasis ja priimti sprendimus ir veikti pagal juos. Tai vadinama pojūčio / mąstymo / veikimo ciklu:
- Pojūtis: agentas randa arba gauna informaciją apie savo aplinkoje esančius dalykus, kurie gali turėti įtakos jo elgesiui (greta esančios grėsmės, daiktai, kuriuos reikia rinkti, įdomios vietos, kurias reikia ištirti).
- Pagalvokite: agentas nusprendžia, kaip reaguoti (svarsto, ar pakankamai saugu rinkti daiktus, ar jis turėtų pirmiausia kovoti / pasislėpti).
- Aktas: agentas atlieka veiksmus, kad įgyvendintų ankstesnį sprendimą (pradeda judėti priešo ar objekto link).
- ...dabar situacija pasikeitė dėl veikėjų veiksmų, todėl ciklas kartojasi su naujais duomenimis.
AI linkęs sutelkti dėmesį į kilpos jutimo dalį. Pavyzdžiui, autonominiai automobiliai fotografuoja kelią, sujungia juos su radaro ir lidaro duomenimis ir juos interpretuoja. Paprastai tai atliekama naudojant mašininį mokymąsi, kuris apdoroja gaunamus duomenis ir suteikia jiems prasmę, išgaudamas semantinę informaciją, pvz., „20 jardų priekyje kitas automobilis“. Tai yra vadinamosios klasifikavimo problemos.
Žaidimams nereikia sudėtingos sistemos informacijai išgauti, nes dauguma duomenų jau yra neatsiejama jos dalis. Nereikia paleisti vaizdų atpažinimo algoritmų, kad nustatytų, ar priešas yra priešas – žaidimas jau žino ir pateikia informaciją tiesiai į sprendimų priėmimo procesą. Todėl ciklo dalis jausmas dažnai yra daug paprastesnė nei dalis „Mąstyk ir veik“.
Žaidimo AI apribojimai
AI turi keletą apribojimų, kurių reikia laikytis:
- AI nereikia mokyti iš anksto, tarsi tai būtų mašininio mokymosi algoritmas. Nėra prasmės kurti neuroninį tinklą, kad būtų galima stebėti dešimtis tūkstančių žaidėjų ir išmokti geriausio būdo žaisti prieš juos. Kodėl? Nes žaidimas neišleistas ir žaidėjų nėra.
- Žaidimas turi būti įdomus ir sudėtingas, todėl agentai neturėtų rasti geriausio požiūrio prieš žmones.
- Agentai turi atrodyti realistiški, kad žaidėjai jaustųsi taip, lyg žaistų prieš tikrus žmones. „AlphaGo“ programa pranoko žmones, tačiau pasirinkti žingsniai buvo labai toli nuo tradicinio žaidimo supratimo. Jei žaidime imituojamas žmogaus priešininkas, šio jausmo neturėtų būti. Algoritmą reikia pakeisti taip, kad jis priimtų tikėtinus, o ne idealius sprendimus.
- AI turi veikti realiu laiku. Tai reiškia, kad algoritmas negali monopolizuoti procesoriaus naudojimo ilgą laiką, kad galėtų priimti sprendimus. Net 10 milisekundžių yra per ilgas laikas, nes daugumai žaidimų reikia tik 16–33 milisekundžių, kad būtų atliktas visas apdorojimas ir pereiti prie kito grafikos kadro.
- Idealiu atveju bent dalis sistemos turėtų būti valdoma duomenimis, kad ne koduotojai galėtų atlikti pakeitimus ir koreguoti greičiau.
Pažvelkime į AI metodus, apimančius visą Sense/Think/Act ciklą.
Pagrindinių sprendimų priėmimas
Pradėkime nuo paprasčiausio žaidimo – teniso. Tikslas: judinkite irklą taip, kad kamuolys atsimuštų nuo jo, o ne praskristų pro jį. Tai kaip tenisas, kai tu pralaimi, jei nepataiki kamuolio. Čia AI turi gana lengvą užduotį - nuspręsti, kuria kryptimi perkelti platformą.
Sąlyginiai teiginiai
„Pong“ AI akivaizdžiausias sprendimas yra visada stengtis pastatyti platformą po kamuoliu.
Paprastas algoritmas, parašytas pseudokodu:
kiekvienas kadras / atnaujinimas žaidimui veikiant:
jei kamuolys yra kairėje nuo irklo:
perkelkite irklą į kairę
kitu atveju, jei kamuolys yra dešinėje nuo irklo:
perkelkite irklą į dešinę
Jei platforma juda rutulio greičiu, tai yra idealus AI „Pong“ algoritmas. Nereikia nieko komplikuoti, jei nėra tiek daug duomenų ir galimų agento veiksmų.
Šis metodas yra toks paprastas, kad visas Sense / Think / Act ciklas yra vos pastebimas. Bet ten yra:
- Sense dalis yra dviejų if teiginių. Žaidimas žino, kur yra kamuolys ir kur yra platforma, todėl AI ieško šios informacijos.
- „Tink“ dalis taip pat įtraukta į du „if“ teiginius. Jie įkūnija du sprendimus, kurie šiuo atveju yra vienas kitą paneigiantys. Dėl to pasirenkamas vienas iš trijų veiksmų – perkelkite platformą į kairę, perkelkite ją į dešinę arba nieko nedarykite, jei ji jau yra tinkamai išdėstyta.
- Akto dalis yra Move Paddle Left ir Move Paddle Right teiginiuose. Priklausomai nuo žaidimo dizaino, jie gali perkelti platformą akimirksniu arba tam tikru greičiu.
Tokie metodai vadinami reaktyviais – yra paprastas taisyklių rinkinys (šiuo atveju – teiginiai kode), kurios reaguoja į esamą pasaulio būklę ir imasi veiksmų.
Sprendimų medis
Pong pavyzdys iš tikrųjų atitinka formalią AI koncepciją, vadinamą sprendimų medžiu. Algoritmas eina per jį, kad pasiektų „lapą“ – sprendimą, kokių veiksmų imtis.
Sukurkime mūsų platformos algoritmo sprendimų medžio blokinę schemą:
Kiekviena medžio dalis vadinama mazgu – tokioms struktūroms aprašyti AI naudoja grafų teoriją. Yra dviejų tipų mazgai:
- Sprendimo mazgai: pasirinkimas iš dviejų alternatyvų, pagrįstas tam tikros sąlygos testavimu, kur kiekviena alternatyva vaizduojama kaip atskiras mazgas.
- Pabaigos mazgai: veiksmas, kurį reikia atlikti, atspindi galutinį sprendimą.
Algoritmas prasideda nuo pirmojo mazgo (medžio „šaknies“). Jis arba priima sprendimą, į kurį antrinį mazgą eiti, arba atlieka veiksmą, saugomą mazge, ir išeina.
Kokia nauda, jei sprendimų medis atlieka tą patį darbą, kaip ir ankstesniame skyriuje esantys teiginiai „jei“? Čia yra bendra sistema, kai kiekvienas sprendimas turi tik vieną sąlygą ir du galimus rezultatus. Tai leidžia kūrėjui sukurti AI iš duomenų, atspindinčių sprendimus medyje, nereikalaujant jų koduoti. Pateikiame lentelę:
Kodo pusėje gausite eilučių skaitymo sistemą. Kiekvienam iš jų sukurkite mazgą, prijunkite sprendimų logiką pagal antrąjį stulpelį ir antrinius mazgus pagal trečią ir ketvirtą stulpelius. Vis dar reikia suprogramuoti sąlygas ir veiksmus, tačiau dabar žaidimo struktūra bus sudėtingesnė. Čia galite pridėti papildomų sprendimų ir veiksmų, o tada tinkinti visą AI tiesiog redaguodami medžio apibrėžimo teksto failą. Tada perkeliate failą žaidimo dizaineriui, kuris gali pakeisti elgesį neperkompiliuodamas žaidimo ar nekeisdamas kodo.
Sprendimų medžiai yra labai naudingi, kai jie sukuriami automatiškai iš daugybės pavyzdžių (pavyzdžiui, naudojant ID3 algoritmą). Tai daro juos veiksmingu ir efektyviu įrankiu klasifikuoti situacijas pagal gautus duomenis. Tačiau mes neapsiribojame paprasta agentų veiksmų pasirinkimo sistema.
Scenarijai
Išanalizavome sprendimų medžio sistemą, kuri naudojo iš anksto sukurtas sąlygas ir veiksmus. Asmuo, kuriantis AI, gali sutvarkyti medį taip, kaip nori, bet vis tiek turi pasikliauti programuotoju, kuris visa tai užprogramavo. O kas, jei dizaineriui suteiktume įrankius sukurti savo sąlygas ar veiksmus?
Kad programuotojui nereikėtų rašyti kodo sąlygoms Is Ball Left Of Paddle ir Is Ball Right Of Paddle, jis gali sukurti sistemą, kurioje dizaineris parašys sąlygas šioms reikšmėms patikrinti. Tada sprendimų medžio duomenys atrodys taip:
Tai iš esmės tas pats, kas pirmoje lentelėje, tačiau sprendimai patys turi savo kodą, šiek tiek panašų į sąlyginę if sakinio dalį. Kodo pusėje tai būtų rodoma antrajame sprendimo mazgų stulpelyje, tačiau užuot ieškojusi konkrečios sąlygos, kurią reikia įvykdyti (Is Ball Left Of Paddle), įvertina sąlyginę išraišką ir atitinkamai grąžina true arba false. Tai atliekama naudojant Lua arba Angelscript skriptų kalbą. Naudodamas juos, kūrėjas gali paimti objektus savo žaidime (kamuolys ir irklas) ir sukurti kintamuosius, kurie bus prieinami scenarijuje (ball.position). Be to, scenarijų kalba yra paprastesnė nei C++. Jai nereikia pilno kompiliavimo etapo, todėl idealiai tinka greitai koreguoti žaidimo logiką ir leidžia „nekoduotojams“ patiems susikurti reikiamas funkcijas.
Aukščiau pateiktame pavyzdyje scenarijų kalba naudojama tik sąlyginei išraiškai įvertinti, tačiau ji taip pat gali būti naudojama veiksmams. Pavyzdžiui, duomenys Move Paddle Right gali tapti scenarijaus teiginiu (ball.position.x += 10). Kad veiksmas būtų apibrėžtas ir scenarijuje, nereikia programuoti Move Paddle Right.
Galite eiti dar toliau ir parašyti visą sprendimų medį scenarijų kalba. Tai bus koduotų sąlyginių teiginių kodas, tačiau jie bus išoriniuose scenarijaus failuose, tai yra, juos bus galima pakeisti neperkompiliuojant visos programos. Žaidimo metu dažnai galite redaguoti scenarijaus failą, kad greitai išbandytumėte skirtingus AI atsakymus.
Įvykio atsakymas
Aukščiau pateikti pavyzdžiai puikiai tinka Pong. Jie nuolat vykdo ciklą Sense/Think/Act ir veikia remdamiesi naujausia pasaulio padėtimi. Tačiau sudėtingesniuose žaidimuose reikia reaguoti į atskirus įvykius, o ne viską vertinti iš karto. Pong šiuo atveju jau yra blogas pavyzdys. Pasirinkime kitą.
Įsivaizduokite šaulį, kuriame priešai nejuda, kol aptinka žaidėją, o po to veikia priklausomai nuo savo „specializacijos“: kažkas bėgs „skubėti“, kažkas puls iš toli. Tai vis dar yra pagrindinė reaktyvioji sistema – „jei žaidėjas pastebėtas, ką nors daryk“ – tačiau ją galima logiškai suskirstyti į įvykį „Player Seen“ ir „Reakciją“ (pasirinkite atsakymą ir jį vykdykite).
Tai sugrąžina mus į jausmų / mąstymo / veiksmų ciklą. Galime užkoduoti Sense dalį, kuri kiekvieną kadrą patikrins, ar AI mato grotuvą. Jei ne, nieko neįvyksta, bet jei mato, sukuriamas įvykis Player Seen. Kode bus atskira skiltis, kurioje rašoma „kai įvyksta žaidėjas pastebėtas įvykis, daryk“, kur yra atsakymas, kurio reikia norint išspręsti „Tink ir veik“ dalis. Taigi nustatysite reakcijas į įvykį Player Seen: „skubančiam“ personažui - ChargeAndAttack, o snaiperiui - HideAndSnipe. Šiuos ryšius galima sukurti duomenų faile, kad juos būtų galima greitai redaguoti, nereikia iš naujo kompiliuoti. Čia taip pat galima naudoti scenarijų kalbą.
Priimant sunkius sprendimus
Nors paprastos reakcijos sistemos yra labai galingos, yra daug situacijų, kai jų nepakanka. Kartais reikia priimti skirtingus sprendimus pagal tai, ką šiuo metu veikia agentas, tačiau sunku įsivaizduoti, kad tai yra sąlyga. Kartais yra per daug sąlygų, kad jas būtų galima veiksmingai pateikti sprendimų medyje arba scenarijuje. Kartais prieš apsisprendžiant dėl kito žingsnio reikia iš anksto įvertinti, kaip pasikeis situacija. Norint išspręsti šias problemas, reikia sudėtingesnių metodų.
Baigtinės būsenos mašina
Baigtinės būsenos mašina arba FSM (ribinės būsenos mašina) yra būdas pasakyti, kad mūsų agentas šiuo metu yra vienoje iš kelių galimų būsenų ir kad jis gali pereiti iš vienos būsenos į kitą. Tokių būsenų yra tam tikras skaičius – taigi ir pavadinimas. Geriausias pavyzdys iš gyvenimo – šviesoforas. Skirtingose vietose yra skirtingos šviesų sekos, tačiau principas tas pats – kiekviena būsena kažką reprezentuoja (sustoti, eiti ir pan.). Šviesoforas bet kuriuo metu yra tik vienos būsenos ir juda iš vienos į kitą pagal paprastas taisykles.
Tai panaši istorija su NPC žaidimuose. Pavyzdžiui, paimkime sargybinį su šiomis būsenomis:
- Patruliavimas.
- Puolimas.
- Bėgantis.
Ir šios sąlygos pakeisti būseną:
- Jei sargybinis pamato priešą, jis puola.
- Jei sargybinis puola, bet nebemato priešo, jis grįžta patruliuoti.
- Jei sargybinis puola, bet yra sunkiai sužeistas, jis pabėga.
Taip pat galite rašyti if-teiginius su globėjo būsenos kintamuoju ir įvairiais patikrinimais: ar šalia yra priešas, koks NPC sveikatos lygis ir pan. Pridėkime dar keletą būsenų:
- Tuščiosios eigos – tarp patrulių.
- Ieškoma – kai dingo pastebėtas priešas.
- Pagalbos paieška – kai priešas pastebimas, bet yra per stiprus, kad galėtų kovoti vienas.
Kiekvieno iš jų pasirinkimas yra ribotas - pavyzdžiui, sargybinis nesiims ieškoti paslėpto priešo, jei jo sveikata yra silpna.
Juk yra didžiulis „jeigu“ sąrašas , Tai " gali tapti pernelyg sudėtingas, todėl turime formalizuoti metodą, kuris leistų nepamiršti būsenų ir perėjimų tarp būsenų. Norėdami tai padaryti, atsižvelgiame į visas būsenas ir po kiekviena būsena į sąrašą įrašome visus perėjimus į kitas būsenas kartu su joms būtinomis sąlygomis.
Tai būsenų perėjimo lentelė – išsamus būdas pavaizduoti FMV. Nubraižykime diagramą ir gaukime išsamią apžvalgą, kaip keičiasi NPC elgesys.
Diagrama atspindi šio agento sprendimų priėmimo esmę pagal esamą situaciją. Be to, kiekviena rodyklė rodo perėjimą tarp būsenų, jei šalia jos esanti sąlyga yra teisinga.
Kiekvienas atnaujinimas patikrina esamą agento būseną, peržvelgiame perėjimų sąrašą ir, jei tenkinamos perėjimo sąlygos, jis priima naują būseną. Pavyzdžiui, kiekvienas kadras patikrina, ar 10 sekundžių laikmatis nepasibaigė, o jei taip, tada apsauga pereina iš tuščiosios eigos būsenos į patruliavimą. Lygiai taip pat Atakuojančio būsena tikrina agento sveikatą – jei ji žema, tada pereina į Bėgimo būseną.
Tai yra perėjimų tarp būsenų valdymas, o kaip elgesys, susijęs su pačiomis būsenomis? Kalbant apie tikrosios konkrečios valstybės elgsenos įgyvendinimą, paprastai yra dviejų tipų „kabliukai“, kai FMV priskiriame veiksmus:
- Veiksmai, kuriuos periodiškai atliekame esamai būsenai.
- Veiksmai, kurių atliekame pereidami iš vienos būsenos į kitą.
Pirmojo tipo pavyzdžiai. Patruliavimo būsena perkels agentą patruliavimo maršrutu kiekviename kadre. Atakavimo būsena bandys inicijuoti ataką kiekvieną kadrą arba pereiti į būseną, kurioje tai įmanoma.
Antrojo tipo atveju apsvarstykite perėjimą „jei priešas matomas, o priešas per stiprus, eikite į pagalbos paieškos būseną. Agentas turi pasirinkti, kur kreiptis pagalbos, ir saugoti šią informaciją, kad pagalbos paieškos būsena žinotų, kur kreiptis. Kai pagalba randama, agentas grįžta į puolimo būseną. Šiuo metu jis norės pasakyti sąjungininkui apie grėsmę, todėl gali įvykti veiksmas NotifyFriendOfThreat.
Dar kartą galime pažvelgti į šią sistemą per ciklo Sense/Think/Act objektyvą. Pojūtis įkūnytas perėjimo logikos naudojamuose duomenyse. Pagalvokite – kiekvienoje būsenoje galimi perėjimai. O veiksmas atliekamas veiksmais, periodiškai atliekamais būsenos viduje arba perėjimuose tarp būsenų.
Kartais nuolatinės apklausos perėjimo sąlygos gali būti brangios. Pavyzdžiui, jei kiekvienas agentas atlieka sudėtingus skaičiavimus kiekviename kadre, kad nustatytų, ar gali matyti priešus ir suprasti, ar gali pereiti iš patruliavimo į puolimo būseną, tai užtruks daug procesoriaus laiko.
Svarbūs pasaulio būklės pokyčiai gali būti laikomi įvykiais, kurie bus apdorojami jiems įvykus. Užuot FSM tikrinusi perėjimo sąlygą „ar mano agentas gali matyti grotuvą“, galima sukonfigūruoti atskirą sistemą, kad ji tikrintų rečiau (pvz., 5 kartus per sekundę). Rezultatas yra „Player Seen“, kai patikrinimas praeina.
Tai perduodama FSM, kuri dabar turėtų pereiti į žaidėjo matyto įvykio būseną ir atitinkamai reaguoti. Gautas elgesys yra toks pat, išskyrus beveik nepastebimą delsą prieš atsakant. Tačiau našumas pagerėjo, nes Sense dalis buvo atskirta į atskirą programos dalį.
Hierarchinė baigtinių būsenų mašina
Tačiau dirbti su dideliais FSM ne visada patogu. Jei norime išplėsti atakos būseną ir atskirti MeleeAttacking ir RangedAttacking, turėsime pakeisti visų kitų būsenų perėjimus, vedančius į Attacking būseną (dabartinę ir būsimą).
Tikriausiai pastebėjote, kad mūsų pavyzdyje yra daug pasikartojančių perėjimų. Dauguma tuščiosios eigos būsenos perėjimų yra identiški patruliavimo būsenos perėjimams. Būtų gerai, kad nesikartotų, ypač jei pridėtume daugiau panašių būsenų. Prasminga sugrupuoti tuščią eigą ir patruliavimą pagal bendrą „nekovos“ etiketę, kur yra tik vienas bendras perėjimų į kovines būsenas rinkinys. Jei laikysime šią etiketę kaip būseną, tuščioji eiga ir patruliavimas tampa subbūstėmis. Pavyzdys, kaip naudoti atskirą pereinamojo laikotarpio lentelę naujai ne kovinei subbūvei:
Pagrindinės būsenos:
Iš kovos būsena:
Ir diagramos pavidalu:
Tai ta pati sistema, bet su nauja nekovine būsena, kuri apima tuščiąja eiga ir patruliavimą. Su kiekviena būsena, kurioje yra FSM su subbūsenomis (ir šios subbūsenos, savo ruožtu, turinčios savo FSM – ir taip tiek ilgai, kiek jums reikia), gauname hierarchinę baigtinių būsenų mašiną arba HFSM (hierarchinė baigtinių būsenų mašina). Sugrupuodami nekovinę būseną, iškirtome krūvą perteklinių perėjimų. Tą patį galime padaryti su bet kokiomis naujomis būsenomis su bendrais perėjimais. Pavyzdžiui, jei ateityje išplėsime puolimo būseną į MeleeAttacking ir MissileAttacking būsenas, tai bus subbūsenos, kurios pereina viena nuo kitos pagal atstumą iki priešo ir amunicijos prieinamumą. Dėl to sudėtingas elgesys ir poelgiai gali būti pavaizduoti naudojant minimalų pasikartojančių perėjimų skaičių.
Elgesio medis
Naudojant HFSM, sudėtingi elgesio deriniai sukuriami paprastu būdu. Tačiau yra nedidelių sunkumų, nes sprendimų priėmimas pereinamojo laikotarpio taisyklių forma yra glaudžiai susijęs su dabartine būkle. Ir daugelyje žaidimų tai yra būtent tai, ko reikia. Kruopštus būsenos hierarchijos naudojimas gali sumažinti perėjimo pasikartojimų skaičių. Tačiau kartais jums reikia taisyklių, kurios veiktų, nesvarbu, kurioje būsenoje esate, arba kurios galioja beveik bet kurioje valstybėje. Pavyzdžiui, jei agento sveikata nukris iki 25%, norėsite, kad jis pabėgtų, nepaisant to, ar jis kovojo, nedirbo, ar kalbėjo – šią sąlygą turėsite pridėti prie kiekvienos būsenos. Ir jei vėliau jūsų dizaineris norės pakeisti žemą sveikatos slenkstį nuo 25% iki 10%, tai teks daryti dar kartą.
Idealiu atveju tokia situacija reikalauja sistemos, kurioje sprendimai „kokioje būsenoje būti“ būtų už pačių būsenų ribų, kad pakeitimai būtų atlikti tik vienoje vietoje ir nepaliestų pereinamųjų sąlygų. Čia atsiranda elgesio medžiai.
Yra keletas būdų, kaip juos įgyvendinti, tačiau esmė yra maždaug vienoda visiems ir yra panaši į sprendimų medį: algoritmas prasideda „šakniniu“ mazgu, o medyje yra mazgų, vaizduojančių sprendimus arba veiksmus. Tačiau yra keletas pagrindinių skirtumų:
- Dabar mazgai grąžina vieną iš trijų reikšmių: Pavyko (jei užduotis baigta), Nepavyko (jei jos negalima pradėti) arba Vykdoma (jei ji vis dar veikia ir nėra galutinio rezultato).
- Nebėra sprendimo mazgų, iš kurių būtų galima rinktis iš dviejų alternatyvų. Vietoj to, tai yra dekoratoriaus mazgai, turintys vieną antrinį mazgą. Jei jiems pasiseks, jie įvykdo savo vienintelį vaiko mazgą.
- Mazgai, kurie atlieka veiksmus, grąžina Vykdomas reikšmės, kurios atspindi atliekamus veiksmus.
Šis mažas mazgų rinkinys gali būti sujungtas, kad būtų sukurta daug sudėtingų elgsenų. Įsivaizduokime HFSM apsaugą iš ankstesnio pavyzdžio kaip elgesio medį:
Naudojant šią struktūrą, neturėtų būti akivaizdaus perėjimo iš tuščiosios eigos / patruliavimo būsenų į puolančią ar kitas būsenas. Jei matomas priešas, o veikėjo sveikata silpna, vykdymas sustoja ties Bėgimo mazgu, neatsižvelgiant į tai, kurį mazgą jis anksčiau vykdė – patruliavimo, tuščiosios eigos, puolimo ar bet kurio kito.
Elgsenos medžiai yra sudėtingi – yra daug būdų juos sudaryti, o rasti tinkamą dekoratorių ir sudėtinių mazgų derinį gali būti sudėtinga. Taip pat kyla klausimų, kaip dažnai tikrinti medį – ar norime pereiti kiekvieną jo dalį ar tik pasikeitus vienai iš sąlygų? Kaip išsaugome mazgų būseną – kaip žinoti, kada 10 sekundžių buvome tuščiąja eiga, arba kaip žinoti, kurie mazgai veikė paskutinį kartą, kad galėtume tinkamai apdoroti seką?
Štai kodėl yra daugybė įgyvendinimų. Pavyzdžiui, kai kuriose sistemose dekoratorių mazgai buvo pakeisti įmontuotais dekoratoriais. Jie iš naujo įvertina medį, kai pasikeičia dekoratoriaus sąlygos, padeda sujungti mazgus ir periodiškai atnaujina.
Komunalinėmis paslaugomis pagrįsta sistema
Kai kurie žaidimai turi daug skirtingų mechanikų. Pageidautina, kad jie gautų visus paprastų ir bendrų perėjimo taisyklių privalumus, bet nebūtinai pilno elgesio medžio pavidalu. Užuot turėjus aiškų pasirinkimų rinkinį ar galimų veiksmų medį, lengviau išnagrinėti visus veiksmus ir pasirinkti tinkamiausią šiuo metu.
Komunalinėmis paslaugomis pagrįsta sistema padės būtent tai. Tai sistema, kurioje agentas atlieka įvairius veiksmus ir pasirenka, kuriuos iš jų atlikti, atsižvelgdamas į santykinį kiekvieno naudingumą. Kai naudingumas yra savavališkas matas, nurodantis, kiek svarbu ar pageidautina, kad agentas atliktų šį veiksmą.
Apskaičiuotas veiksmo naudingumas pagal esamą būseną ir aplinką, agentas gali bet kada patikrinti ir pasirinkti tinkamiausią kitą būseną. Tai panašu į FSM, išskyrus atvejus, kai perėjimai nustatomi pagal kiekvienos potencialios būsenos įvertinimą, įskaitant dabartinę. Atkreipkite dėmesį, kad mes pasirenkame naudingiausią veiksmą, kad galėtume tęsti (arba pasilikti, jei jį jau atlikome). Jei norite daugiau įvairovės, tai gali būti subalansuotas, bet atsitiktinis pasirinkimas iš nedidelio sąrašo.
Sistema priskiria savavališką naudingumo reikšmių diapazoną, pavyzdžiui, nuo 0 (visiškai nepageidautina) iki 100 (visiškai pageidautina). Kiekvienas veiksmas turi keletą parametrų, kurie turi įtakos šios vertės apskaičiavimui. Grįžtant prie mūsų globėjo pavyzdžio:
Perėjimai tarp veiksmų yra dviprasmiški – bet kuri būsena gali sekti bet kurią kitą. Veiksmų prioritetai randami grąžintose naudingumo reikšmėse. Jei priešas matomas, o tas priešas stiprus, o veikėjo sveikata silpna, tada tiek „Fleeing“, tiek „FindingHelp“ pateiks dideles, nenulines reikšmes. Šiuo atveju FindingHelp visada bus aukštesnė. Taip pat ne kovinė veikla niekada negrįžta daugiau nei 50, taigi jie visada bus mažesni nei koviniai. Į tai turite atsižvelgti kurdami veiksmus ir apskaičiuodami jų naudingumą.
Mūsų pavyzdyje veiksmai grąžina arba fiksuotą pastovią vertę, arba vieną iš dviejų fiksuotų verčių. Realesnė sistema grąžintų įvertį iš nuolatinio verčių diapazono. Pavyzdžiui, veiksmas „Pabėgimas“ grąžina didesnes naudingumo reikšmes, jei agento sveikata yra žema, o „Attacking“ – žemesnes naudingumo reikšmes, jei priešas yra per stiprus. Dėl šios priežasties Bėgimo veiksmas turi viršenybę prieš Puolimą bet kokioje situacijoje, kai agentas jaučia, kad neturi pakankamai sveikatos nugalėti priešą. Tai leidžia veiksmams teikti pirmenybę pagal bet kokį kriterijų skaičių, todėl šis metodas yra lankstesnis ir kintamesnis nei elgesio medis ar FSM.
Kiekvienas veiksmas turi daug programos skaičiavimo sąlygų. Jie gali būti parašyti scenarijų kalba arba kaip matematinių formulių serija. The Sims, imituojantis veikėjo kasdienybę, prideda papildomą skaičiavimo sluoksnį – agentas gauna eilę „motyvacijų“, kurios daro įtaką naudingumo įvertinimams. Jei veikėjas yra alkanas, laikui bėgant jis dar labiau alkanas, o veiksmo „EatFood“ naudingumo vertė didės tol, kol veikėjas jį atliks, sumažindamas alkio lygį ir grąžindamas „EatFood“ vertę į nulį.
Veiksmų atrankos pagal reitingų sistemą idėja yra gana paprasta, todėl komunalinėmis paslaugomis pagrįsta sistema gali būti naudojama kaip AI sprendimų priėmimo procesų dalis, o ne kaip visiškai juos pakeisti. Sprendimų medis gali paprašyti dviejų antrinių mazgų naudingumo įvertinimo ir pasirinkti aukštesnįjį. Panašiai elgesio medis gali turėti sudėtinį naudingumo mazgą, kad būtų galima įvertinti veiksmų naudingumą ir nuspręsti, kurį vaiką atlikti.
Judėjimas ir navigacija
Ankstesniuose pavyzdžiuose turėjome platformą, kurią judėjome į kairę arba į dešinę, ir sargybinį, kuris patruliavo arba atakavo. Bet kaip tiksliai elgiamės su agento judėjimu per tam tikrą laikotarpį? Kaip nustatyti greitį, kaip išvengti kliūčių ir kaip suplanuoti maršrutą, kai pasiekti tikslą yra sunkiau nei tiesiog judėti tiesia linija? Pažiūrėkime į tai.
Valdymas
Pradiniame etape manysime, kad kiekvienas agentas turi greičio reikšmę, į kurią įeina, kaip greitai jis juda ir kokia kryptimi. Jį galima išmatuoti metrais per sekundę, kilometrais per valandą, pikseliais per sekundę ir t.t. Prisimindami „Sense/Think/Act“ kilpą galime įsivaizduoti, kad „Think“ dalis pasirenka greitį, o „Akto“ dalis taiko tą greitį agentui. Paprastai žaidimuose yra fizikos sistema, kuri atlieka šią užduotį už jus, sužino kiekvieno objekto greičio reikšmę ir ją koreguoja. Todėl galite palikti AI vieną užduotį - nuspręsti, kokį greitį turėtų turėti agentas. Jei žinote, kur turėtų būti agentas, turite jį perkelti reikiama kryptimi nustatytu greičiu. Labai triviali lygtis:
norima_kelionė = paskirties_pozicija – agento_pozicija
Įsivaizduokite 2D pasaulį. Agentas yra taške (-2,-2), tikslas yra kažkur šiaurės rytuose taške (30, 20), o agentui reikalingas kelias ten patekti yra (32, 22). Tarkime, šios pozicijos matuojamos metrais – jei imsime agento greitį 5 metrus per sekundę, tada savo poslinkio vektoriaus mastelį gausime apytiksliai (4.12, 2.83). Su šiais parametrais agentas į paskirties vietą atvyktų per beveik 8 sekundes.
Galite bet kada perskaičiuoti vertes. Jei agentas būtų pusiaukelėje iki tikslo, judėjimas būtų perpus mažesnis, bet kadangi didžiausias agento greitis yra 5 m/s (tai nusprendėme aukščiau), greitis bus toks pat. Tai taip pat veikia judant taikiniams, todėl agentas gali atlikti nedidelius pakeitimus judant.
Tačiau norime daugiau variacijų – pavyzdžiui, lėtai didinant greitį, kad būtų imituojamas veikėjas, judantis iš stovimos į bėgimą. Tą patį galima padaryti pabaigoje prieš sustojimą. Šios savybės yra žinomos kaip vairavimo elgsena, kurių kiekviena turi specifinius pavadinimus: ieškoti, pabėgti, atvykti ir tt. Idėja ta, kad agento greičiui galima pritaikyti pagreičio jėgas, remiantis agento padėties ir dabartinio greičio palyginimu su paskirties vieta. siekiant panaudoti skirtingus metodus siekiant tikslo.
Kiekvienas elgesys turi šiek tiek skirtingą tikslą. „Seek“ ir „Arrival“ yra būdai perkelti agentą į paskirties vietą. Kliūčių išvengimas ir atskyrimas koreguoja agento judėjimą, kad būtų išvengta kliūčių kelyje į tikslą. Lygiavimas ir sanglauda leidžia agentams judėti kartu. Atsižvelgiant į visus veiksnius, galima susumuoti bet kokį skirtingų vairavimo būdų skaičių, kad būtų sukurtas vienas kelio vektorius. Agentas, kuris naudojasi atvykimo, atsiskyrimo ir kliūčių vengimo elgesiu, kad liktų atokiau nuo sienų ir kitų agentų. Šis metodas gerai veikia atvirose vietose be nereikalingų detalių.
Sunkesnėmis sąlygomis skirtingo elgesio papildymas veikia prasčiau – pavyzdžiui, agentas gali įstrigti sienoje dėl konflikto tarp atvykimo ir kliūčių išvengimo. Todėl turite apsvarstyti galimybes, kurios yra sudėtingesnės nei tiesiog pridėti visas vertes. Būdas yra toks: užuot sudėję kiekvieno elgesio rezultatus, galite apsvarstyti judėjimą skirtingomis kryptimis ir pasirinkti geriausią variantą.
Tačiau sudėtingoje aplinkoje su aklavietėmis ir pasirinkimu, kuriuo keliu eiti, mums reikės kažko dar pažangesnio.
Rasti būdą
Vairavimo elgesys puikiai tinka paprastam judėjimui atviroje vietoje (futbolo aikštėje ar arenoje), kur iš A į B yra tiesus kelias su nedideliais apvažiavimais aplink kliūtis. Sudėtingiems maršrutams mums reikia kelio, kuris yra būdas tyrinėti pasaulį ir nuspręsti dėl maršruto per jį.
Paprasčiausia kiekvienam langeliui šalia agento pritaikyti tinklelį ir įvertinti, kuriam iš jų leidžiama judėti. Jei vienas iš jų yra tikslas, sekite maršrutą nuo kiekvieno kvadrato iki ankstesnio, kol pasieksite pradžią. Tai maršrutas. Kitu atveju pakartokite procesą su kitais šalia esančiais kvadratais, kol rasite kelionės tikslą arba pritrūksite laukų (tai reiškia, kad maršruto nėra). Tai yra tai, kas oficialiai žinoma kaip „Breadth-First Search“ arba „BFS“ (paieškos pagal plotį algoritmas). Kiekviename žingsnyje jis žvelgia į visas puses (taigi ir į plotį, „plotį“). Paieškos erdvė yra tarsi bangos frontas, kuris juda tol, kol pasiekia norimą vietą – paieškos erdvė plečiasi kiekviename žingsnyje, kol įtraukiamas galutinis taškas, po kurio galima atsekti pradžią.
Dėl to gausite kvadratų, iš kurių bus sudarytas norimas maršrutas, sąrašą. Tai yra kelias (taigi, pathfinding) – vietų, kurias agentas aplankys sekdamas tikslą, sąrašas.
Atsižvelgiant į tai, kad žinome kiekvieno kvadrato padėtį pasaulyje, galime naudoti vairavimo veiksmus, kad judėtume keliu – nuo 1 mazgo iki 2 mazgo, tada iš 2 mazgo į 3 mazgą ir pan. Paprasčiausias variantas yra eiti link kito kvadrato centro, bet dar geresnis variantas yra sustoti krašto viduryje tarp esamo ir kito kvadrato. Dėl šios priežasties agentas galės nupjauti kampus staigiuose posūkiuose.
BFS algoritmas turi ir trūkumų – „neteisinga“ kryptimi jis ištiria tiek pat kvadratų, kiek „teisinga“. Čia pradeda veikti sudėtingesnis algoritmas, vadinamas A* (A žvaigždute). Jis veikia taip pat, tačiau užuot aklai tyrinėjęs kaimynų kvadratus (tada kaimynų kaimynus, paskui kaimynų kaimynus ir pan.), jis surenka mazgus į sąrašą ir surūšiuoja juos taip, kad kitas tiriamas mazgas visada būtų kuris veda į trumpiausią kelią. Mazgai rūšiuojami pagal euristiką, kurioje atsižvelgiama į du dalykus – hipotetinio maršruto į norimą aikštę „kainą“ (įskaitant visas kelionės išlaidas) ir įvertinimą, kiek toli tas kvadratas yra nuo paskirties vietos (paiešką pakreipus). teisinga kryptis).
Šis pavyzdys rodo, kad agentas vienu metu tyrinėja vieną kvadratą, kiekvieną kartą pasirinkdamas gretimą, kuris yra perspektyviausias. Gautas kelias yra toks pat kaip ir BFS, tačiau procese buvo atsižvelgta į mažiau kvadratų – tai turi didelę įtaką žaidimo našumui.
Judėjimas be tinklelio
Tačiau dauguma žaidimų nėra išdėstyti tinklelyje ir dažnai to padaryti neįmanoma neprarandant realizmo. Reikia kompromisų. Kokio dydžio turėtų būti kvadratai? Per dideli ir jie negalės teisingai pavaizduoti mažų koridorių ar posūkių, per maži ir bus per daug kvadratų ieškoti, o tai galiausiai užtruks daug laiko.
Pirmiausia reikia suprasti, kad tinklelis suteikia mums sujungtų mazgų grafiką. A* ir BFS algoritmai iš tikrųjų veikia su grafikais ir visiškai nesirūpina mūsų tinkleliu. Galėtume dėti mazgus bet kurioje žaidimo pasaulio vietoje: tol, kol bus ryšys tarp bet kurių dviejų sujungtų mazgų, taip pat tarp pradžios ir pabaigos taškų bei bent vieno iš mazgų, algoritmas veiks taip pat gerai, kaip ir anksčiau. Tai dažnai vadinama kelio taškų sistema, nes kiekvienas mazgas reiškia reikšmingą vietą pasaulyje, kuri gali būti bet kokio skaičiaus hipotetinių kelių dalis.
1 pavyzdys: mazgas kiekviename kvadrate. Paieška prasideda nuo mazgo, kuriame yra agentas, ir baigiasi norimo kvadrato mazge.
2 pavyzdys: mažesnis mazgų (kelio taškų) rinkinys. Paieška pradedama nuo agento kvadrato, pereinama per reikiamą skaičių mazgų ir tęsiama iki paskirties vietos.
Tai visiškai lanksti ir galinga sistema. Tačiau reikia šiek tiek atsargumo sprendžiant, kur ir kaip pastatyti tarpinį tašką, kitaip agentai gali tiesiog nematyti artimiausio taško ir negalės pradėti kelio. Būtų lengviau, jei galėtume automatiškai išdėstyti kelio taškus pagal pasaulio geometriją.
Čia pasirodo navigacijos tinklelis arba navimesh (navigacijos tinklelis). Paprastai tai yra 2D trikampių tinklelis, padengtas pasaulio geometrija – visur, kur agentui leidžiama vaikščioti. Kiekvienas tinklelio trikampis tampa grafiko mazgu ir turi iki trijų gretimų trikampių, kurie tampa gretimais grafiko mazgais.
Šis paveikslėlis yra pavyzdys iš Unity variklio – jis išanalizavo pasaulio geometriją ir sukūrė naviko tinklelį (ekrano kopijoje šviesiai mėlyna spalva). Kiekvienas tinklelio daugiakampis yra sritis, kurioje agentas gali stovėti arba pereiti iš vieno daugiakampio į kitą. Šiame pavyzdyje daugiakampiai yra mažesni už aukštus, ant kurių jie yra – tai daroma siekiant atsižvelgti į agento dydį, kuris tęsis už jo vardinės padėties.
Mes galime ieškoti maršruto per šį tinklelį, vėlgi naudodami A* algoritmą. Tai suteiks mums beveik tobulą maršrutą pasaulyje, kuriame atsižvelgiama į visą geometriją ir nereikia nereikalingų mazgų bei tarpinių taškų kūrimo.
Kelio paieška yra per plati tema, kuriai neužtenka vienos straipsnio dalies. Jei norite tai ištirti išsamiau, tai padės .
Planavimas
Su kelio paieška sužinojome, kad kartais neužtenka tik pasirinkti kryptį ir judėti – turime pasirinkti maršrutą ir padaryti kelis posūkius, kad pasiektume norimą tikslą. Šią mintį galime apibendrinti: tikslo pasiekimas yra ne tik kitas žingsnis, o visa seka, kai kartais reikia pažvelgti į kelis žingsnius į priekį, kad išsiaiškintumėte, koks turėtų būti pirmasis. Tai vadinama planavimu. Kelio paieška gali būti laikoma vienu iš kelių planavimo pratęsimų. Kalbant apie mūsų ciklą Sense/Think/Act, čia „Tink“ dalis planuoja kelias veiksmų dalis ateičiai.
Pažiūrėkime į stalo žaidimo Magic: The Gathering pavyzdį. Pirmiausia einame su šiuo kortelių rinkiniu rankose:
- Pelkė – duoda 1 juodą maną (žemės kortelę).
- Miškas – duoda 1 žalią maną (žemės kortelę).
- Fugitive Wizard – norint išsikviesti reikia 1 mėlynos manos.
- Elvish Mystic – norint išsikviesti reikia 1 žalios manos.
Mes ignoruojame likusias tris kortas, kad būtų lengviau. Pagal taisykles, žaidėjui leidžiama žaisti po 1 žemės kortą per savo ėjimą, jis gali „bakstelėti“ šią kortą, kad iš jos ištrauktų maną, o po to burtus (įskaitant būtybės iškvietimą) pagal manos kiekį. Šioje situacijoje žaidėjas žmogus moka žaisti Forest, bakstelėti 1 žalią maną ir tada iškviesti Elvish Mystic. Bet kaip žaidimo AI gali tai išsiaiškinti?
Lengvas planavimas
Trivialus metodas yra išbandyti kiekvieną veiksmą paeiliui, kol neliks tinkamų. Žvelgdamas į kortas, AI mato, ką Swamp gali žaisti. Ir jis tai žaidžia. Ar šiame posūkyje liko kokių nors kitų veiksmų? Jis negali iškviesti nei Elvish Mystic, nei Pabėgusio burtininko, nes jiems iškviesti reikia atitinkamai žalios ir mėlynos manos, o Swamp suteikia tik juodą maną. Ir jis nebegalės vaidinti Miško, nes jau suvaidino Pelkę. Taigi žaidimo AI laikėsi taisyklių, tačiau tai padarė prastai. Galima patobulinti.
Planuojant galima rasti sąrašą veiksmų, kurie perkelia žaidimą į norimą būseną. Kaip ir kiekvienas kvadratas kelyje turėjo kaimynus (kelio ieškant), kiekvienas plano veiksmas taip pat turi kaimynus arba įpėdinius. Šių veiksmų ir vėlesnių veiksmų galime ieškoti tol, kol pasieksime norimą būseną.
Mūsų pavyzdyje norimas rezultatas yra „jei įmanoma, iškviesk padarą“. Posūkio pradžioje matome tik du galimus žaidimo taisyklių leidžiamus veiksmus:
1. Žaiskite „Swamp“ (rezultatas: „Swamp“ žaidime)
2. Žaisk Forest (rezultatas: miškas žaidime)
Kiekvienas atliktas veiksmas gali paskatinti tolesnius veiksmus ir uždaryti kitus, vėlgi priklausomai nuo žaidimo taisyklių. Įsivaizduokite, kad žaidėme Swamp - tai pašalins Swamp kaip kitą žingsnį (jau žaidėme), o tai taip pat pašalins Forest (nes pagal taisykles galite žaisti vieną žemės kortą per ėjimą). Po to AI prideda 1 juodą maną kaip kitą žingsnį, nes nėra kitų galimybių. Jei jis eis į priekį ir pasirinks Tap the Swamp, jis gaus 1 vienetą juodos manos ir negalės su juo nieko daryti.
1. Žaiskite „Swamp“ (rezultatas: „Swamp“ žaidime)
1.1 „Tap“ pelkė (rezultatas: pelkė „tapped“, +1 vienetas juodos manos)
Veiksmų nėra – END
2. Žaisk Forest (rezultatas: miškas žaidime)
Veiksmų sąrašas buvo trumpas, patekome į aklavietę. Mes kartojame procesą kitam žingsniui. Žaidžiame „Forest“, atidarome veiksmą „gauk 1 žalią maną“, kuris savo ruožtu atidarys trečiąjį veiksmą – iškviesk Elvish Mystic.
1. Žaiskite „Swamp“ (rezultatas: „Swamp“ žaidime)
1.1 „Tap“ pelkė (rezultatas: pelkė „tapped“, +1 vienetas juodos manos)
Veiksmų nėra – END
2. Žaisk Forest (rezultatas: miškas žaidime)
2.1 „Tap“ miškas (rezultatas: miškas „išlietas“, +1 vienetas žaliosios manos)
2.1.1 Summon Elvish Mystic (rezultatas: Elvish Mystic žaidime, -1 žalia mana)
Veiksmų nėra – END
Galiausiai ištyrėme visus įmanomus veiksmus ir radome planą, kuris iškviečia būtybę.
Tai labai supaprastintas pavyzdys. Patartina pasirinkti geriausią įmanomą planą, o ne bet kokį planą, atitinkantį kai kuriuos kriterijus. Paprastai galima įvertinti galimus planus pagal jų įgyvendinimo rezultatus arba bendrą naudą. Galite gauti 1 tašką už žaidimą žemės korta ir 3 taškus už būtybės iškvietimą. Žaisti pelkę būtų 1 taško planas. O žaisdamas Forest → Tap the Forest → iškviesk Elvish Mystic iškart duos 4 taškus.
Taip planavimas veikia „Magic: The Gathering“, tačiau ta pati logika galioja ir kitose situacijose. Pavyzdžiui, perkeliant pėstininką, kad vyskupui būtų vietos judėti šachmatuose. Arba prisidenkite už sienos, kad saugiai fotografuotumėte naudojant XCOM. Apskritai, jūs suprantate idėją.
Patobulintas planavimas
Kartais yra per daug galimų veiksmų, kad būtų galima apsvarstyti kiekvieną galimą variantą. Grįžtant prie pavyzdžio su Magic: The Gathering: tarkime, kad žaidime ir tavo rankoje yra kelios žemės ir būtybės kortos – galimų ėjimų kombinacijų skaičius gali siekti keliasdešimt. Yra keletas problemos sprendimų.
Pirmasis metodas yra grandinės sujungimas atgal. Užuot bandę visus derinius, geriau pradėti nuo galutinio rezultato ir pabandyti rasti tiesioginį maršrutą. Užuot eidami nuo medžio šaknies prie konkretaus lapo, judame priešinga kryptimi – nuo lapo iki šaknies. Šis metodas yra lengvesnis ir greitesnis.
Jei priešas turi 1 sveikatą, galite rasti planą „padaryti 1 ar daugiau žalos“. Norint tai pasiekti, turi būti įvykdytos kelios sąlygos:
1. Žalą gali padaryti burtai – jis turi būti rankoje.
2. Norėdami burti, jums reikia manos.
3. Norėdami gauti maną, turite žaisti žemės korta.
4. Norėdami žaisti žemės korta, turite ją turėti rankoje.
Kitas būdas yra geriausia paieška. Užuot išbandę visus kelius, pasirenkame tinkamiausią. Dažniausiai šis metodas suteikia optimalų planą be nereikalingų paieškos išlaidų. A* yra geriausios pirmosios paieškos forma – nuo pat pradžių išnagrinėjęs perspektyviausius maršrutus, jis jau gali rasti geriausią kelią ir nereikia tikrinti kitų variantų.
Įdomi ir vis populiarėjanti geriausio pirmojo paieškos parinktis yra Monte Karlo medžio paieška. Užuot spėliojęs, kurie planai yra geresni už kitus pasirenkant kiekvieną sekantį veiksmą, algoritmas kiekviename žingsnyje pasirenka atsitiktinius įpėdinius, kol pasiekia pabaigą (kai planas lėmė pergalę ar pralaimėjimą). Tada galutinis rezultatas naudojamas padidinti arba sumažinti ankstesnių parinkčių svorį. Kartodamas šį procesą kelis kartus iš eilės, algoritmas gerai įvertina, koks yra geriausias kitas ėjimas, net jei situacija pasikeičia (jei priešas imasi veiksmų, kad trukdytų žaidėjui).
Jokia istorija apie planavimą žaidimuose neapsieitų be į tikslą orientuoto veiksmų planavimo arba GOAP (į tikslą orientuoto veiksmų planavimo). Tai yra plačiai naudojamas ir aptariamas metodas, tačiau, išskyrus kelias išskirtines detales, tai iš esmės yra atgalinio grandinėjimo metodas, apie kurį kalbėjome anksčiau. Jei tikslas buvo „sunaikinti žaidėją“ ir žaidėjas yra už priedangos, planas galėtų būti toks: sunaikinti granata → gauti → mesti.
Paprastai yra keli tikslai, kurių kiekvienas turi savo prioritetą. Jei aukščiausio prioriteto tikslas negali būti įvykdytas (joks veiksmų derinys nesukuria plano „nužudyti žaidėją“, nes žaidėjo nematyti), AI grįš prie žemesnio prioriteto tikslų.
Mokymas ir adaptacija
Jau sakėme, kad žaidimų AI paprastai nenaudoja mašininio mokymosi, nes jis netinka agentams valdyti realiuoju laiku. Bet tai nereiškia, kad negalite ko nors pasiskolinti iš šios srities. Mes norime, kad šaulys būtų priešininkas, iš kurio galėtume ko nors pasimokyti. Pavyzdžiui, sužinokite apie geriausias vietas žemėlapyje. Arba priešininkas koviniame žaidime, kuris blokuotų žaidėjo dažnai naudojamus kombinuotus judesius, motyvuodamas jį panaudoti kitus. Taigi mašininis mokymasis gali būti gana naudingas tokiose situacijose.
Statistika ir tikimybės
Prieš pradėdami eiti į sudėtingus pavyzdžius, pažiūrėkime, kiek toli galime nueiti atlikę kelis paprastus matavimus ir naudodami juos priimdami sprendimus. Pavyzdžiui, realaus laiko strategija – kaip nustatyti, ar žaidėjas gali pradėti ataką pirmosiomis žaidimo minutėmis ir kokiai gynybai prieš tai pasiruošti? Galime ištirti žaidėjo ankstesnę patirtį, kad suprastume, kokios gali būti reakcijos ateityje. Visų pirma, mes neturime tokių neapdorotų duomenų, bet galime juos rinkti – kiekvieną kartą, kai AI žaidžia prieš žmogų, jis gali įrašyti pirmosios atakos laiką. Po kelių sesijų gausime vidutinį laiką, kurio žaidėjas užtruks ateityje.
Taip pat yra problemų dėl vidutinių verčių: jei žaidėjas puolė 20 kartų ir žaidė lėtai 20 kartų, tada reikiamos reikšmės bus kažkur per vidurį, ir tai mums nieko naudingo neduos. Vienas iš sprendimų yra apriboti įvesties duomenis – galima atsižvelgti į paskutinius 20 vienetų.
Panašus metodas naudojamas vertinant tam tikrų veiksmų tikimybę, darant prielaidą, kad žaidėjo ankstesnės nuostatos bus tokios pačios ir ateityje. Jei žaidėjas mus atakuoja penkis kartus ugnies kamuoliu, du kartus žaibu ir vieną kartą artimu kovos kamuoliu, akivaizdu, kad jam labiau patinka ugnies kamuolys. Ekstrapoliuokime ir pamatykime skirtingų ginklų panaudojimo tikimybę: ugnies kamuolys = 62,5%, žaibas = 25% ir artimasis = 12,5%. Mūsų žaidimo AI turi pasiruošti apsisaugoti nuo ugnies.
Kitas įdomus metodas yra naudoti Naive Bayes klasifikatorių, kad būtų galima ištirti didelius įvesties duomenų kiekius ir klasifikuoti situaciją taip, kad AI reaguotų norimu būdu. Bajeso klasifikatoriai geriausiai žinomi dėl jų naudojimo el. pašto šiukšlių filtruose. Ten jie nagrinėja žodžius, lygina juos su tomis vietomis, kuriose tie žodžiai buvo pasirodę anksčiau (spame ar ne), ir daro išvadas apie gaunamus el. Tą patį galime padaryti net su mažiau įvesties. Remiantis visa naudinga informacija, kurią mato dirbtinis intelektas (pvz., kokie priešo vienetai yra sukurti, kokius burtus jie naudoja arba kokias technologijas jie tyrinėjo) ir galutiniu rezultatu (karas ar taika, skubėjimas ar gynyba ir kt.) - pasirinksime norimą AI elgesį.
Visų šių mokymo metodų pakanka, tačiau patartina juos naudoti remiantis testavimo duomenimis. AI išmoks prisitaikyti prie skirtingų strategijų, kurias naudojo jūsų žaidimų testuotojai. AI, kuris prisitaiko prie grotuvo po išleidimo, gali tapti per daug nuspėjamas arba per sunku nugalėti.
Vertė pagrįsta adaptacija
Atsižvelgdami į mūsų žaidimų pasaulio turinį ir taisykles, galime pakeisti verčių, turinčių įtakos sprendimų priėmimui, rinkinį, o ne tiesiog naudoti įvesties duomenis. Mes darome tai:
- Leiskite AI rinkti duomenis apie pasaulio būklę ir pagrindinius įvykius žaidimo metu (kaip nurodyta aukščiau).
- Remdamiesi šiais duomenimis, pakeiskime keletą svarbių reikšmių.
- Savo sprendimus įgyvendiname remdamiesi šių vertybių apdorojimu ar įvertinimu.
Pavyzdžiui, agentas gali pasirinkti iš kelių kambarių pirmojo asmens šaudyklės žemėlapyje. Kiekvienas kambarys turi savo vertę, nuo kurios priklauso, kaip norima apsilankyti. AI atsitiktinai pasirenka, į kurį kambarį eiti pagal vertę. Tada agentas prisimena, kuriame kambaryje buvo nužudytas, ir sumažina jo vertę (tikimybę, kad jis ten grįš). Panašiai ir atvirkštinei situacijai – jei agentas sunaikina daug priešininkų, tada kambario vertė didėja.
Markovo modelis
Ką daryti, jei surinktus duomenis panaudotume prognozėms? Jei prisiminsime kiekvieną kambarį, kuriame matome žaidėją tam tikrą laiką, nuspėsime, į kurį kambarį žaidėjas gali eiti. Stebėdami ir registruodami žaidėjo judesius kambariuose (reikšmes), galime juos numatyti.
Paimkime tris kambarius: raudoną, žalią ir mėlyną. Taip pat pastebėjimai, kuriuos užfiksavome žiūrėdami žaidimo sesiją:
Stebėjimų skaičius kiekviename kambaryje yra beveik vienodas – mes vis dar nežinome, kur padaryti gerą vietą pasaloms. Statistikos rinkimą apsunkina ir žaidėjų atgimimas, kurie visame žemėlapyje atsiranda tolygiai. Bet duomenys apie kitą kambarį, į kurį jie patenka, pasirodžius žemėlapyje, jau praverčia.
Matyti, kad žalias kambarys žaidėjams tinka – iš raudonojo į jį persikelia daugiausia žmonių, kurių 50% lieka ten toliau. Mėlynas kambarys, priešingai, nėra populiarus, o jei ir lankosi, ilgai neužsibūna.
Tačiau duomenys mums sako kai ką svarbesnio – kai žaidėjas yra mėlyname kambaryje, kitas kambarys, kuriame jį matome, bus raudonas, o ne žalias. Nors žalias kambarys yra populiaresnis nei raudonasis kambarys, situacija pasikeičia, jei žaidėjas yra mėlynajame kambaryje. Kita būsena (t. y. kambarys, į kurį žaidėjas eis) priklauso nuo ankstesnės būsenos (t. y. kambario, kuriame žaidėjas šiuo metu yra). Kadangi tyrinėjame priklausomybes, padarysime tikslesnes prognozes nei paprasčiausiai nepriklausomai skaičiuodami stebėjimus.
Būsimos būsenos numatymas remiantis praeities būsenos duomenimis vadinamas Markovo modeliu, o tokie pavyzdžiai (su kambariais) – Markovo grandinėmis. Kadangi modeliai rodo pokyčių tarp nuoseklių būsenų tikimybę, jie vizualiai rodomi kaip FSM su tikimybe aplink kiekvieną perėjimą. Anksčiau mes naudojome FSM, kad parodytume agento elgesio būseną, tačiau ši sąvoka taikoma bet kuriai būsenai, nesvarbu, ar ji susijusi su agentu, ar ne. Šiuo atveju būsenos reiškia patalpą, kurioje agentas užima:
Tai paprastas būdas parodyti santykinę būsenos pokyčių tikimybę, suteikiant AI tam tikrą galimybę numatyti kitą būseną. Galite numatyti kelis žingsnius į priekį.
Jei žaidėjas yra žaliajame kambaryje, yra 50% tikimybė, kad jis liks ten kitą kartą, kai bus stebimas. Bet kokia tikimybė, kad jis vis tiek bus ten net ir po to? Yra ne tik tikimybė, kad žaidėjas po dviejų stebėjimų liko žaliajame kambaryje, bet yra ir tikimybė, kad jis išėjo ir sugrįžo. Štai nauja lentelė, kurioje atsižvelgiama į naujus duomenis:
Tai rodo, kad tikimybė pamatyti žaidėją žaliajame kambaryje po dviejų stebėjimų bus lygi 51% - 21%, kad jis bus iš raudonojo kambario, 5% iš jų, kad žaidėjas apsilankys mėlyname kambaryje tarp jų ir 25%, kurių žaidėjas neišeis, paliks žalią kambarį.
Lentelė yra tiesiog vizualinis įrankis – atliekant procedūrą reikia tik padauginti tikimybes kiekviename žingsnyje. Tai reiškia, kad galite pažvelgti į toli į ateitį su vienu įspėjimu: manome, kad galimybė patekti į kambarį visiškai priklauso nuo esamo kambario. Tai vadinama Markovo nuosavybe – būsima būsena priklauso tik nuo dabarties. Bet tai nėra šimtu procentų tikslus. Žaidėjai gali keisti sprendimus priklausomai nuo kitų faktorių: sveikatos lygio ar amunicijos kiekio. Kadangi šių verčių neįrašome, mūsų prognozės bus ne tokios tikslios.
N-gramai
Ką apie kovinio žaidimo pavyzdį ir žaidėjo kombinuotųjų judesių nuspėjimą? Tas pats! Tačiau vietoj vienos būsenos ar įvykio išnagrinėsime visas sekas, kurios sudaro kombinuotą smūgį.
Vienas iš būdų tai padaryti yra saugoti kiekvieną įvestį (pvz., Kick, Punch arba Block) buferyje ir įrašyti visą buferį kaip įvykį. Taigi žaidėjas pakartotinai spaudžia Kick, Kick, Punch, kad naudotų SuperDeathFist ataką, AI sistema išsaugo visas įvestis buferyje ir prisimena paskutinius tris, naudotus kiekviename žingsnyje.
(Paryškintos eilutės yra tada, kai žaidėjas pradeda „SuperDeathFist“ ataką.)
AI matys visas parinktis, kai žaidėjas pasirinks Kick, po to kitą Kick, ir tada pastebės, kad kita įvestis visada yra Punch. Tai leis agentui numatyti SuperDeathFist kombinuotą judesį ir, jei įmanoma, jį blokuoti.
Šios įvykių sekos vadinamos N-gramais, kur N yra saugomų elementų skaičius. Ankstesniame pavyzdyje tai buvo 3 gramai (trigrama), o tai reiškia: pirmieji du įrašai naudojami nuspėti trečiąjį. Atitinkamai, 5 gramuose pirmieji keturi įrašai numato penktąjį ir pan.
Dizaineris turi atidžiai pasirinkti N-gramų dydį. Mažesniam N reikia mažiau atminties, bet taip pat saugoma mažiau istorijos. Pavyzdžiui, 2 gramai (bigramas) įrašys Kick, Kick arba Kick, Punch, bet negalės išsaugoti Kick, Kick, Punch, todėl AI nereaguos į SuperDeathFist kombinaciją.
Kita vertus, didesni skaičiai reikalauja daugiau atminties ir dirbtinį intelektą bus sunkiau treniruoti, nes bus daug daugiau galimų variantų. Jei turėtumėte tris galimas „Kick“, „Punch“ arba „Block“ įvestis, o mes naudotume 10 gramų, tai būtų apie 60 tūkstančių skirtingų variantų.
Bigramų modelis yra paprasta Markovo grandinė – kiekviena praeities būsenos/dabartinės būsenos pora yra bigrama, ir jūs galite numatyti antrąją būseną pagal pirmąją. 3 gramų ir didesni N gramai taip pat gali būti laikomi Markovo grandinėmis, kur visi elementai (išskyrus paskutinįjį N grame) kartu sudaro pirmąją būseną, o paskutinis elementas – antrąją. Kovinio žaidimo pavyzdys rodo galimybę pereiti iš Kick and Kick būsenos į Kick and Punch būseną. Kelis įvesties istorijos įrašus traktuodami kaip vieną vienetą, iš esmės paverčiame įvesties seką visos būsenos dalimi. Tai suteikia mums Markovo savybę, kuri leidžia mums naudoti Markovo grandines, kad nuspėti kitą įvestį ir atspėti, koks bus kitas kombinuotas veiksmas.
išvada
Kalbėjomės apie dažniausiai naudojamus dirbtinio intelekto kūrimo įrankius ir metodus. Taip pat pažvelgėme į situacijas, kuriose juos reikia naudoti ir kur jie ypač naudingi.
To turėtų pakakti norint suprasti žaidimo AI pagrindus. Bet, žinoma, tai ne visi metodai. Mažiau populiarūs, bet ne mažiau veiksmingi:
- optimizavimo algoritmai, įskaitant kopimą į kalną, nusileidimą nuo gradiento ir genetinius algoritmus
- priešpriešinės paieškos / planavimo algoritmai (minimax ir alfa-beta genėjimas)
- klasifikavimo metodai (perceptronai, neuroniniai tinklai ir paramos vektorinės mašinos)
- agentų suvokimo ir atminties apdorojimo sistemos
- architektūriniai AI metodai (hibridinės sistemos, pogrupių architektūros ir kiti AI sistemų perdengimo būdai)
- animacijos įrankiai (planavimas ir judesių koordinavimas)
- našumo veiksniai (detalumo lygis, bet kuriuo metu ir laiko juostos algoritmai)
Internetiniai šaltiniai šia tema:
1. GameDev.net turi Ir .
2. yra daug pristatymų ir straipsnių įvairiomis temomis, susijusiomis su žaidimų AI kūrimu.
3. apima GDC AI aukščiausiojo lygio susitikimo temas, kurių daugelis yra prieinamos nemokamai.
4. Svetainėje taip pat galima rasti naudingos medžiagos .
5. Tommy Thompson, AI tyrinėtojas ir žaidimų kūrėjas, kuria vaizdo įrašus „YouTube“. su paaiškinimu ir AI tyrimu komerciniuose žaidimuose.
Knygos šia tema:
1. Game AI Pro knygų serija – tai trumpų straipsnių rinkinys, kuriame paaiškinama, kaip įdiegti konkrečias funkcijas arba kaip išspręsti konkrečias problemas.
2. AI Game Programming Wisdom serija yra Game AI Pro serijos pirmtakas. Jame yra senesnių metodų, tačiau beveik visi yra aktualūs ir šiandien.
3. yra vienas pagrindinių tekstų visiems, norintiems suprasti bendrą dirbtinio intelekto sritį. Tai ne knyga apie žaidimų kūrimą – joje mokoma dirbtinio intelekto pagrindų.
Šaltinis: www.habr.com
