Löysin mielenkiintoista materiaalia tekoälystä peleissä. Tekoälyn perusasiat selitetään yksinkertaisilla esimerkeillä, ja sisällä on monia hyödyllisiä työkaluja ja menetelmiä sen kätevään kehittämiseen ja suunnitteluun. Siellä on myös kuinka, missä ja milloin niitä käytetään.
Suurin osa esimerkeistä on kirjoitettu pseudokoodilla, joten edistyneitä ohjelmointitietoja ei tarvita. Leikkauksen alla on 35 arkkia tekstiä kuvilla ja gifillä, joten valmistaudu.
UPD. Pyydän anteeksi, mutta olen jo tehnyt oman käännökseni tästä Habrén artikkelista . Voit lukea hänen versionsa , mutta jostain syystä artikkeli meni minulta ohi (käytin hakua, mutta jokin meni pieleen). Ja koska kirjoitan pelien kehittämiseen omistettuun blogiin, päätin jättää oman versioni käännöksestä tilaajille (jotkut kohdat on muotoiltu eri tavalla, jotkut jätettiin tarkoituksella pois kehittäjien neuvojen perusteella).
Mikä on AI?
Pelin tekoäly keskittyy siihen, mitä toimintoja kohteen tulee suorittaa sen sijaintiolosuhteiden perusteella. Tätä kutsutaan yleisesti "älykkään agentin" johtamiseksi, jossa agentti on pelaajahahmo, ajoneuvo, botti tai joskus jotain abstraktimpaa: kokonaista kokonaisuutta tai jopa sivilisaatiota. Se on joka tapauksessa asia, jonka täytyy nähdä ympäristönsä, tehdä sen perusteella päätöksiä ja toimia niiden mukaisesti. Tätä kutsutaan Sense/Think/Act sykliksi:
- Aisti: Agentti löytää tai vastaanottaa tietoa ympäristöstään asioista, jotka voivat vaikuttaa sen käyttäytymiseen (lähellä olevat uhkat, kerättävät esineet, mielenkiintoiset paikat tutkittavaksi).
- Ajattele: Agentti päättää, miten reagoi (pohtii, onko tarpeeksi turvallista kerätä esineitä vai pitäisikö hänen taistella/piiloutua ensin).
- Toimi: agentti suorittaa toimia edellisen päätöksen toteuttamiseksi (alkaa liikkua vihollista tai kohdetta kohti).
- ...nyt tilanne on muuttunut hahmojen toiminnan takia, joten sykli toistuu uusilla tiedoilla.
AI pyrkii keskittymään silmukan Sense-osaan. Esimerkiksi autonomiset autot ottavat kuvia tiestä, yhdistävät ne tutka- ja lidartietoihin ja tulkitsevat niitä. Tämä tapahtuu yleensä koneoppimisen avulla, joka käsittelee saapuvat tiedot ja antaa sille merkityksen poimimalla semanttista tietoa, kuten "20 jaardia edelläsi on toinen auto". Nämä ovat niin sanottuja luokitteluongelmia.
Pelit eivät tarvitse monimutkaista järjestelmää tiedon poimimiseen, koska suurin osa tiedoista on jo olennainen osa sitä. Ei tarvitse ajaa kuvantunnistusalgoritmeja sen määrittämiseksi, onko edessä vihollinen – peli tietää jo ja syöttää tiedot suoraan päätöksentekoprosessiin. Siksi syklin Sense-osa on usein paljon yksinkertaisempi kuin Ajattele ja toimi -osa.
Game AI:n rajoitukset
Tekoälyllä on useita rajoituksia, jotka on otettava huomioon:
- Tekoälyä ei tarvitse kouluttaa etukäteen, ikään kuin se olisi koneoppimisalgoritmi. Ei ole mitään järkeä kirjoittaa hermoverkkoa kehityksen aikana, jotta voidaan seurata kymmeniä tuhansia pelaajia ja oppia paras tapa pelata heitä vastaan. Miksi? Koska peliä ei ole julkaistu eikä pelaajia ole.
- Pelin tulee olla hauskaa ja haastavaa, joten agenttien ei pitäisi löytää parasta lähestymistapaa ihmisiä vastaan.
- Agenttien tulee näyttää realistisilta, jotta pelaajat tuntevat pelaavansa oikeita ihmisiä vastaan. AlphaGo-ohjelma menestyi paremmin kuin ihmiset, mutta valitut vaiheet olivat hyvin kaukana perinteisestä pelin ymmärtämisestä. Jos peli simuloi ihmisvastustajaa, tätä tunnetta ei pitäisi olla olemassa. Algoritmia on muutettava niin, että se tekee mieluummin uskottavia päätöksiä kuin ihanteellisia.
- AI:n on toimittava reaaliajassa. Tämä tarkoittaa, että algoritmi ei voi monopolisoida suorittimen käyttöä pitkiksi ajoiksi päätösten tekemiseksi. Jopa 10 millisekuntia on liian pitkä aika, koska useimmat pelit tarvitsevat vain 16–33 millisekuntia suorittaakseen kaiken käsittelyn ja siirtyäkseen seuraavaan grafiikkakehykseen.
- Ihannetapauksessa ainakin osa järjestelmästä tulisi olla dataohjattua, jotta ei-koodaajat voivat tehdä muutoksia ja säädöt tapahtuvat nopeammin.
Katsotaanpa tekoälyn lähestymistapoja, jotka kattavat koko Sense/Think/Act -syklin.
Peruspäätösten tekeminen
Aloitetaan yksinkertaisimmasta pelistä - Pongista. Tavoite: liikuta melaa niin, että pallo pomppii siitä sen sijaan, että se lennäisi sen ohi. Se on kuin tennis, jossa häviät, jos et lyö palloa. Täällä tekoälyllä on suhteellisen helppo tehtävä - päättää, mihin suuntaan alustaa siirretään.
Ehdolliset lausunnot
Pongin tekoälylle ilmeisin ratkaisu on yrittää aina sijoittaa alusta pallon alle.
Yksinkertainen algoritmi tälle, kirjoitettu pseudokoodilla:
jokainen kehys/päivitys pelin ollessa käynnissä:
jos pallo on melan vasemmalla puolella:
siirrä melaa vasemmalle
muuten, jos pallo on melan oikealla puolella:
siirrä mela oikealle
Jos alusta liikkuu pallon nopeudella, tämä on ihanteellinen algoritmi Pongin tekoälylle. Mitään ei tarvitse monimutkaista, jos agentille ei ole niin paljon tietoa ja mahdollisia toimia.
Tämä lähestymistapa on niin yksinkertainen, että koko Sense/Think/Act-sykli on tuskin havaittavissa. Mutta se on siellä:
- Sense-osa on kahdessa if-lauseessa. Peli tietää missä pallo on ja missä alusta on, joten tekoäly etsii sitä tietoa.
- Ajattele-osa sisältyy myös kahteen if-lauseeseen. Ne sisältävät kaksi ratkaisua, jotka tässä tapauksessa ovat toisensa poissulkevia. Tämän seurauksena valitaan yksi kolmesta toiminnosta - siirrä alustaa vasemmalle, siirrä sitä oikealle tai tee mitään, jos se on jo asetettu oikein.
- Toimi-osa löytyy Move Paddle Left- ja Move Paddle Right -lausekkeista. Pelin suunnittelusta riippuen ne voivat siirtää alustaa välittömästi tai tietyllä nopeudella.
Tällaisia lähestymistapoja kutsutaan reaktiivisiksi - on olemassa yksinkertainen sääntöjoukko (tässä tapauksessa lauseet koodissa), jotka reagoivat maailman nykyiseen tilaan ja toimivat.
Päätöspuu
Pong-esimerkki vastaa itse asiassa muodollista tekoälykonseptia, jota kutsutaan päätöspuuksi. Algoritmi käy sen läpi saavuttaakseen "lehden" - päätöksen siitä, mitä toimia tehdä.
Tehdään lohkokaavio alustamme algoritmin päätöspuusta:
Puun jokaista osaa kutsutaan solmuksi - AI käyttää graafiteoriaa tällaisten rakenteiden kuvaamiseen. Solmuja on kahden tyyppisiä:
- Päätössolmut: valinta kahdesta vaihtoehdosta jonkin ehdon testauksen perusteella, jossa kukin vaihtoehto esitetään erillisenä solmuna.
- Loppusolmut: suoritettava toiminto, joka edustaa lopullista päätöstä.
Algoritmi alkaa ensimmäisestä solmusta (puun "juuresta"). Se joko päättää, mihin lapsisolmuun mennään, tai se suorittaa solmuun tallennetun toiminnon ja poistuu.
Mitä hyötyä on siitä, että päätöspuu tekee saman työn kuin edellisen osan if-lauseet? Tässä on yleinen järjestelmä, jossa jokaisella päätöksellä on vain yksi ehto ja kaksi mahdollista lopputulosta. Näin kehittäjä voi luoda tekoälyä puussa olevia päätöksiä edustavista tiedoista ilman, että sitä tarvitsee koodata. Esitetään se taulukon muodossa:
Koodipuolella saat järjestelmän merkkijonojen lukemiseen. Luo jokaiselle solmu, yhdistä päätöslogiikka toisen sarakkeen perusteella ja lapsisolmut kolmanteen ja neljänteen sarakkeeseen. Sinun on vielä ohjelmoitava ehdot ja toimet, mutta nyt pelin rakenne on monimutkaisempi. Täällä voit lisätä ylimääräisiä päätöksiä ja toimia ja muokata sitten koko tekoälyä yksinkertaisesti muokkaamalla puun määritelmän tekstitiedostoa. Seuraavaksi siirrät tiedoston pelisuunnittelijalle, joka voi muuttaa toimintaa kääntämättä peliä uudelleen tai vaihtamatta koodia.
Päätöspuut ovat erittäin hyödyllisiä, kun ne rakennetaan automaattisesti suuresta määrästä esimerkkejä (esimerkiksi ID3-algoritmia käyttämällä). Tämä tekee niistä tehokkaan ja tehokkaan työkalun tilanteiden luokitteluun saatujen tietojen perusteella. Menemme kuitenkin pidemmälle kuin yksinkertainen järjestelmä, jossa agentit voivat valita toimintoja.
skenaariot
Analysoimme päätöspuujärjestelmää, joka käytti valmiiksi luotuja ehtoja ja toimia. Tekoälyä suunnitteleva henkilö voi järjestää puun haluamallaan tavalla, mutta hänen on silti luotettava kooderiin, joka ohjelmoi kaiken. Mitä jos voisimme antaa suunnittelijalle työkalut luoda omia ehtojaan tai tekojaan?
Jotta ohjelmoijan ei tarvitse kirjoittaa koodia ehtoille Is Ball Left Of Paddle ja Is Ball Right Of Paddle, hän voi luoda järjestelmän, jossa suunnittelija kirjoittaa ehdot näiden arvojen tarkistamiseksi. Sitten päätöspuun tiedot näyttävät tältä:
Tämä on olennaisesti sama kuin ensimmäisessä taulukossa, mutta ratkaisuilla itsessään on oma koodinsa, vähän kuin if-lauseen ehdollinen osa. Koodipuolella tämä lukee päätössolmujen toisessa sarakkeessa, mutta sen sijaan, että etsittäisiin tiettyä suoritettavaa ehtoa (On Ball Left Of Paddle), se arvioi ehdollisen lausekkeen ja palauttaa sen mukaisesti tosi tai epätosi. Tämä tehdään Lua- tai Angelscript-skriptikielellä. Niiden avulla kehittäjä voi ottaa pelissään esineitä (pallo ja mela) ja luoda muuttujia, jotka ovat käytettävissä käsikirjoituksessa (ball.position). Lisäksi komentosarjakieli on yksinkertaisempi kuin C++. Se ei vaadi täyttä käännösvaihetta, joten se on ihanteellinen pelilogiikan nopeaan säätämiseen ja antaa "ei-koodaajille" luoda tarvittavat toiminnot itse.
Yllä olevassa esimerkissä komentosarjakieltä käytetään vain ehdollisen lausekkeen arvioimiseen, mutta sitä voidaan käyttää myös toimiin. Esimerkiksi Move Paddle Right -tiedoista voi tulla komentosarjalause (pallo.sijainti.x += 10). Jotta toiminto määritellään myös skriptissä ilman, että sinun tarvitsee ohjelmoida Move Paddle Right.
Voit mennä vielä pidemmälle ja kirjoittaa koko päätöspuun komentosarjakielellä. Tämä on koodi kovakoodattujen ehdollisten lausekkeiden muodossa, mutta ne sijaitsevat ulkoisissa komentosarjatiedostoissa, eli niitä voidaan muuttaa kääntämättä koko ohjelmaa uudelleen. Voit usein muokata käsikirjoitustiedostoa pelin aikana testataksesi nopeasti erilaisia tekoälyreaktioita.
Tapahtumavastaus
Yllä olevat esimerkit sopivat täydellisesti Pongille. He ajavat jatkuvasti Sense/Think/Act-sykliä ja toimivat maailman viimeisimmän tilan perusteella. Mutta monimutkaisemmissa peleissä sinun on reagoitava yksittäisiin tapahtumiin eikä arvioitava kaikkea kerralla. Pong tässä tapauksessa on jo huono esimerkki. Valitaan toinen.
Kuvittele ampuja, jossa viholliset ovat liikkumattomia, kunnes he havaitsevat pelaajan, minkä jälkeen he toimivat "erikoistumisensa" mukaan: joku juoksee "kiireilemään", joku hyökkää kaukaa. Se on edelleen perusreaktiivinen järjestelmä - "jos pelaaja havaitaan, tee jotain" - mutta se voidaan loogisesti jakaa Player Seen -tapahtumaan ja reaktioon (valitse vastaus ja suorita se).
Tämä tuo meidät takaisin Sense/Think/Act -kiertoon. Voimme koodata Sense-osan, joka tarkistaa jokaisen ruudun, näkeekö tekoäly soittimen. Jos ei, mitään ei tapahdu, mutta jos se näkee, Player Seen -tapahtuma luodaan. Koodissa on erillinen osio, jossa lukee "kun Player Seen -tapahtuma tapahtuu, tee", jossa on vastaus, jota tarvitset Think and Act -osien käsittelemiseen. Siten määrität reaktioita Player Seen -tapahtumaan: "kiireilevälle" hahmolle - ChargeAndAttack ja tarkka-ampujalle - HideAndSnipe. Nämä suhteet voidaan luoda datatiedostoon nopeaa muokkausta varten ilman uudelleenkääntämistä. Skriptikieltä voidaan käyttää myös tässä.
Vaikeiden päätösten tekeminen
Vaikka yksinkertaiset reaktiojärjestelmät ovat erittäin tehokkaita, on monia tilanteita, joissa ne eivät riitä. Joskus sinun on tehtävä erilaisia päätöksiä sen perusteella, mitä agentti tällä hetkellä tekee, mutta on vaikea kuvitella tätä ehtona. Joskus on liian monia ehtoja, jotta ne voidaan esittää tehokkaasti päätöspuussa tai komentosarjassa. Joskus sinun on arvioitava etukäteen, miten tilanne muuttuu, ennen kuin päätät seuraavasta askeleesta. Näiden ongelmien ratkaisemiseksi tarvitaan kehittyneempiä lähestymistapoja.
Äärimmäisen tilan kone
Finite state machine eli FSM (finite state machine) on tapa sanoa, että agenttimme on tällä hetkellä yhdessä useista mahdollisista tiloista ja että se voi siirtyä tilasta toiseen. Tällaisia tiloja on tietty määrä – tästä syystä nimi. Paras esimerkki elämästä on liikennevalo. Eri paikoissa on erilaisia valosarjoja, mutta periaate on sama - jokainen tila edustaa jotain (pysähdy, kävele jne.). Liikennevalo on kulloinkin vain yhdessä tilassa ja liikkuu yhdestä toiseen yksinkertaisten sääntöjen perusteella.
Samanlainen tarina on pelien NPC:iden kanssa. Otetaan esimerkiksi vartija, jolla on seuraavat tilat:
- Partioiminen.
- Hyökkäys.
- Pakenemassa.
Ja nämä ehdot sen tilan muuttamiseen:
- Jos vartija näkee vihollisen, hän hyökkää.
- Jos vartija hyökkää, mutta ei enää näe vihollista, hän palaa partioimaan.
- Jos vartija hyökkää, mutta haavoittuu vakavasti, hän pakenee.
Voit myös kirjoittaa if-lauseita, joissa on huoltajan tilamuuttuja ja erilaisia tarkistuksia: onko lähistöllä vihollinen, mikä on NPC:n terveystaso jne. Lisätään vielä muutama tila:
- Joutilaisuus - partioiden välillä.
- Etsiminen - kun havaittu vihollinen on kadonnut.
- Avun löytäminen - kun vihollinen havaitaan, mutta on liian vahva taistelemaan yksin.
Jokaisen valinnanvara on rajoitettu - esimerkiksi vartija ei mene etsimään piilotettua vihollista, jos hänellä on heikko terveys.
Loppujen lopuksi siellä on valtava luettelo "jos" , Tuo " voi tulla liian hankalaksi, joten meidän on muotoiltava menetelmä, jonka avulla voimme pitää tilat ja tilojen väliset siirtymät mielessä. Tätä varten otamme huomioon kaikki tilat ja jokaisen tilan alle kirjoitamme luetteloon kaikki siirtymät muihin tiloihin sekä niille tarvittavat ehdot.
Tämä on tilasiirtymätaulukko - kattava tapa edustaa FSM:ää. Piirretään kaavio ja saamme täydellisen yleiskuvan siitä, kuinka NPC-käyttäytyminen muuttuu.
Kaavio heijastaa tämän agentin päätöksenteon ydintä nykytilanteen perusteella. Lisäksi jokainen nuoli näyttää siirtymän tilojen välillä, jos sen vieressä oleva ehto on tosi.
Tarkistamme jokaisen päivityksen agentin nykyisen tilan, katsomme siirtymäluettelon läpi ja jos siirtymän ehdot täyttyvät, se hyväksyy uuden tilan. Jokainen kehys esimerkiksi tarkistaa, onko 10 sekunnin ajastin umpeutunut, ja jos on, niin vartija siirtyy tyhjäkäyntitilasta partiointiin. Samalla tavalla hyökkäävä tila tarkistaa agentin terveyden - jos se on alhainen, se siirtyy pakenevaan tilaan.
Tämä käsittelee siirtymiä tilojen välillä, mutta entä itse tiloihin liittyvä käyttäytyminen? Mitä tulee tietyn tilan todellisen käyttäytymisen toteuttamiseen, on tyypillisesti kahdenlaisia "koukkuja", joissa kohdistamme toimintoja Mikronesille:
- Toiminnot, jotka suoritamme säännöllisesti nykyiselle tilalle.
- Toimet, joita teemme siirtyessämme tilasta toiseen.
Esimerkkejä ensimmäisestä tyypistä. Partiointitila siirtää agenttia partioreittiä pitkin jokaisessa kehyksessä. Hyökkäävä tila yrittää käynnistää hyökkäyksen jokaisessa kehyksessä tai siirtyä tilaan, jossa tämä on mahdollista.
Toisessa tyypissä harkitse siirtymistä "jos vihollinen on näkyvissä ja vihollinen on liian vahva, siirry Finding Help -tilaan. Edustajan on valittava, minne hakea apua, ja tallennettava nämä tiedot, jotta Finding Help -tila tietää, minne mennä. Kun apu löytyy, agentti palaa hyökkäävään tilaan. Tässä vaiheessa hän haluaa kertoa liittolaiselle uhasta, joten NotifyFriendOfThreat-toiminto saattaa tapahtua.
Jälleen kerran voimme tarkastella tätä järjestelmää Sense/Think/Act -syklin linssin läpi. Sense sisältyy siirtymälogiikan käyttämiin tietoihin. Think - siirtymät ovat saatavilla jokaisessa tilassa. Ja Act suoritetaan toimilla, jotka suoritetaan määräajoin tilan sisällä tai tilojen välisissä siirtymissä.
Joskus jatkuvan kyselyn siirtymäolosuhteet voivat olla kalliita. Jos esimerkiksi jokainen agentti suorittaa monimutkaisia laskelmia jokaisessa kehyksessä selvittääkseen, näkeekö se vihollisia ja voiko se siirtyä partiotilasta hyökkääväksi, tämä vie paljon suorittimen aikaa.
Tärkeitä muutoksia maailman tilassa voidaan ajatella tapahtumina, joita käsitellään niiden tapahtuessa. Sen sijaan, että FSM tarkistaisi siirtymäehdon "näkeekö agenttini soittimen?" joka kehys, erillinen järjestelmä voidaan määrittää tarkistamaan harvemmin (esim. 5 kertaa sekunnissa). Ja tuloksena on, että pelaaja nähdään, kun sekki läpäisee.
Tämä välitetään FSM:lle, jonka pitäisi nyt siirtyä Player Seen -tapahtuman vastaanotettuihin ehtoihin ja vastata vastaavasti. Tuloksena oleva käyttäytyminen on sama paitsi melkein huomaamaton viive ennen vastaamista. Mutta suorituskyky on parantunut, kun Sense-osa on erotettu erilliseksi ohjelman osaksi.
Hierarkkinen äärellinen kone
Kuitenkin työskentely suurten FSM:ien kanssa ei ole aina kätevää. Jos haluamme laajentaa hyökkäystilan erottamaan MeleeAttackingin ja RangedAttackingin, meidän on muutettava siirtymät kaikista muista hyökkäystilaan johtavista tiloista (nykyinen ja tuleva).
Olet todennäköisesti huomannut, että esimerkissämme on paljon päällekkäisiä siirtymiä. Useimmat siirtymät joutokäyntitilassa ovat identtisiä partiointitilan siirtymien kanssa. Olisi mukavaa olla toistamatta itseämme, varsinkin jos lisäämme samanlaisia tiloja. On järkevää ryhmitellä tyhjäkäynti ja partio "ei-taistelu" -nimikkeen alle, jossa on vain yksi yhteinen siirtymäsarja taistelutiloihin. Jos ajattelemme tätä etikettiä tilana, joutokäynnistä ja partioinnista tulee alitiloja. Esimerkki erillisen siirtymätaulukon käyttämisestä uudelle ei-taistelualatilalle:
Päätilat:
Taistelun ulkopuolinen tila:
Ja kaaviomuodossa:
Se on sama järjestelmä, mutta uudella ei-taistelutilassa, joka sisältää tyhjäkäynnin ja partioinnin. Kun jokainen tila sisältää FSM:n alitiloilla (ja nämä puolestaan sisältävät omat FSM:nsä - ja niin edelleen niin kauan kuin tarvitset), saamme hierarkkisen äärellisen tilakoneen tai HFSM:n (hierarkkinen äärellinen kone). Ryhmittelemällä ei-taistelutilan leikkaamme pois joukon tarpeettomia siirtymiä. Voimme tehdä saman kaikille uusille tiloille, joissa on yhteisiä siirtymiä. Esimerkiksi, jos tulevaisuudessa laajennamme Hyökkäävä-tilan lähihyökkäys- ja MissileAttacking-tiloihin, ne ovat alitiloja, jotka siirtyvät toistensa välillä vihollisen etäisyyden ja ammusten saatavuuden perusteella. Tämän seurauksena monimutkaiset käyttäytymiset ja osakäyttäytymiset voidaan esittää minimimäärällä päällekkäisiä siirtymiä.
Käyttäytymispuu
HFSM:llä luodaan monimutkaisia käyttäytymisyhdistelmiä yksinkertaisella tavalla. Pientä vaikeutta on kuitenkin se, että siirtymäsääntöjen muodossa tapahtuva päätöksenteko liittyy läheisesti nykytilaan. Ja monissa peleissä tämä on juuri sitä, mitä tarvitaan. Ja tilahierarkian huolellinen käyttö voi vähentää siirtymätoistojen määrää. Mutta joskus tarvitset sääntöjä, jotka toimivat riippumatta siitä, missä osavaltiossa olet, tai joita sovelletaan melkein mihin tahansa osavaltioon. Jos esimerkiksi agentin terveys putoaa 25 prosenttiin, haluat hänen pakenevan riippumatta siitä, oliko hän taistelussa, toimettomana tai puhumassa – sinun on lisättävä tämä ehto jokaiseen tilaan. Ja jos suunnittelijasi haluaa myöhemmin muuttaa matalan terveyskynnyksen 25 prosentista 10 prosenttiin, tämä on tehtävä uudelleen.
Ihannetapauksessa tämä tilanne vaatii järjestelmän, jossa päätökset "missä tilassa olla" ovat itse tilojen ulkopuolella, jotta muutoksia voidaan tehdä vain yhdessä paikassa eikä kosketa siirtymäolosuhteita. Käyttäytymispuut näkyvät täällä.
Niiden toteuttamiseen on useita tapoja, mutta olemus on suunnilleen sama kaikille ja on samanlainen kuin päätöspuu: algoritmi alkaa "juurisolmulla" ja puu sisältää solmuja, jotka edustavat joko päätöksiä tai toimia. On kuitenkin muutamia keskeisiä eroja:
- Solmut palauttavat nyt yhden kolmesta arvosta: Onnistui (jos työ on valmis), Failed (jos sitä ei voida käynnistää) tai Running (jos se on edelleen käynnissä eikä lopputulosta ole).
- Ei ole enää päätössolmuja, joista valita kahden vaihtoehdon välillä. Sen sijaan ne ovat Decorator-solmuja, joissa on yksi lapsisolmu. Jos he onnistuvat, he suorittavat ainoan lapsisolmunsa.
- Toimintoja suorittavat solmut palauttavat suoritettavia toimintoja kuvaavan Running-arvon.
Tämä pieni joukko solmuja voidaan yhdistää luomaan suuri määrä monimutkaisia käyttäytymismalleja. Kuvitellaan edellisen esimerkin HFSM-suojaa käyttäytymispuuksi:
Tällä rakenteella ei pitäisi olla ilmeistä siirtymistä tyhjäkäynti-/partiointitiloista hyökkäävään tai mihinkään muuhun tilaan. Jos vihollinen on näkyvissä ja hahmon kunto on heikko, teloitus pysähtyy pakenevaan solmuun riippumatta siitä, mitä solmua se aiemmin suoritti - partiointi, tyhjäkäynti, hyökkääminen tai mikä tahansa muu.
Käyttäytymispuut ovat monimutkaisia – niitä on monia tapoja muodostaa, ja oikean sisustajien ja yhdistelmäsolmujen yhdistelmän löytäminen voi olla haastavaa. Kysymyksiä on myös siitä, kuinka usein puu tarkistetaan - haluammeko käydä läpi sen jokaisen osan vai vasta kun jokin ehdoista on muuttunut? Kuinka tallennamme solmuihin liittyvät tilat - mistä tiedämme, milloin olemme olleet joutokäynnillä 10 sekuntia, tai mistä tiedämme, mitkä solmut suorittivat viimeksi, jotta voimme käsitellä sekvenssin oikein?
Tästä syystä toteutuksia on monia. Esimerkiksi joissakin järjestelmissä sisustuselementit on korvattu sisäisillä sisustajilla. He arvioivat puun uudelleen sisustajan olosuhteiden muuttuessa, auttavat liittymään solmuihin ja tarjoavat säännöllisiä päivityksiä.
Apuohjelmapohjainen järjestelmä
Joissakin peleissä on monia erilaisia mekaniikkoja. On toivottavaa, että he saavat kaikki yksinkertaisten ja yleisten siirtymäsääntöjen edut, mutta eivät välttämättä täydellisen käyttäytymispuun muodossa. Selkeiden valintojen tai mahdollisten toimien puun sijaan on helpompi tarkastella kaikkia toimia ja valita tällä hetkellä sopivin.
Utility-pohjainen järjestelmä auttaa juuri tässä. Tämä on järjestelmä, jossa agentilla on erilaisia toimintoja ja hän valitsee, mitkä niistä suorittaa kunkin suhteellisen hyödyn perusteella. Kun hyödyllisyys on mielivaltainen mitta siitä, kuinka tärkeää tai toivottavaa agentin on suorittaa tämä toimenpide.
Toiminnon laskettu hyödyllisyys nykyisen tilan ja ympäristön perusteella, agentti voi tarkistaa ja valita sopivimman muun tilan milloin tahansa. Tämä on samanlainen kuin FSM, paitsi jos siirtymät määräytyvät kunkin potentiaalisen tilan arvion perusteella, mukaan lukien nykyinen. Huomaa, että valitsemme hyödyllisimmän toimenpiteen jatkaaksemme (tai pysyäksemme, jos olemme jo suorittaneet sen). Lisää vaihtelua varten tämä voisi olla tasapainoinen mutta satunnainen valinta pienestä luettelosta.
Järjestelmä määrittää mielivaltaisen alueen hyödyllisyysarvoja, esimerkiksi 0 (täysin ei-toivottu) 100 (täysin toivottava). Jokaisella toiminnolla on useita parametreja, jotka vaikuttavat tämän arvon laskemiseen. Palataksemme huoltajaesimerkkiimme:
Toimien väliset siirtymät ovat epäselviä – mikä tahansa tila voi seurata mitä tahansa muuta. Toimintojen prioriteetit löytyvät palautetuista hyödyllisyysarvoista. Jos vihollinen on näkyvissä ja se on vahva ja hahmon terveys on heikko, sekä Fleeing että FindingHelp palauttavat korkeat nollasta poikkeavat arvot. Tässä tapauksessa FindingHelp on aina korkeampi. Samoin ei-taistelutoiminnat eivät koskaan palaa enempää kuin 50, joten ne ovat aina pienempiä kuin taisteluaktiviteetit. Sinun on otettava tämä huomioon, kun luot toimintoja ja lasket niiden hyödyllisyyttä.
Esimerkissämme toiminnot palauttavat joko kiinteän vakioarvon tai toisen kahdesta kiinteästä arvosta. Realistisempi järjestelmä palauttaisi arvion jatkuvasta arvoalueesta. Esimerkiksi Pako-toiminto palauttaa korkeammat hyödyllisyysarvot, jos agentin kunto on heikko, ja Attacking-toiminto palauttaa alhaisemmat hyödyllisyysarvot, jos vihollinen on liian vahva. Tästä johtuen Pako-toiminto menee hyökkäämisen edelle kaikissa tilanteissa, joissa agentti kokee, ettei hänellä ole tarpeeksi terveyttä vihollisen voittamiseksi. Tämä mahdollistaa toimintojen priorisoinnin useiden kriteerien perusteella, mikä tekee tästä lähestymistavasta joustavamman ja vaihtelevamman kuin käyttäytymispuu tai FSM.
Jokaisella toiminnolla on useita ehtoja ohjelman laskennassa. Ne voidaan kirjoittaa skriptikielellä tai sarjana matemaattisia kaavoja. The Sims, joka simuloi hahmon päivittäistä rutiinia, lisää ylimääräisen laskentakerroksen - agentti saa sarjan "motivaatioita", jotka vaikuttavat hyödyllisyysluokitukseen. Jos hahmolla on nälkä, hänestä tulee ajan myötä entistä nälkäisempi, ja SyöRuoka-toiminnon hyödyllisyysarvo kasvaa, kunnes hahmo suorittaa sen, mikä vähentää nälkätasoa ja palauttaa EatFood-arvon nollaan.
Ajatus toimintojen valitsemisesta luokitusjärjestelmän perusteella on varsin yksinkertainen, joten apuohjelmapohjaista järjestelmää voidaan käyttää osana tekoälyn päätöksentekoprosesseja sen sijaan, että ne korvattaisiin kokonaan. Päätöspuu voi pyytää kahden lapsisolmun hyödyllisyysluokitusta ja valita korkeamman. Vastaavasti käyttäytymispuussa voi olla yhdistetty apuohjelmasolmu, joka arvioi toimintojen hyödyllisyyden sen päättämiseksi, mikä lapsi suoritetaan.
Liikkuminen ja navigointi
Aiemmissa esimerkeissä meillä oli lava, jota siirrettiin vasemmalle tai oikealle, ja vartija, joka partioi tai hyökkäsi. Mutta miten tarkalleen käsittelemme agenttien liikkumista tietyn ajanjakson aikana? Miten säädämme nopeutta, miten vältämme esteitä ja miten suunnittelemme reitin, kun määränpäähän on vaikeampaa kuin suorassa liikkeessä? Katsotaanpa tätä.
Управление
Alkuvaiheessa oletetaan, että jokaisella agentilla on nopeusarvo, joka sisältää sen, kuinka nopeasti se liikkuu ja mihin suuntaan. Se voidaan mitata metreinä sekunnissa, kilometreinä tunnissa, pikseleinä sekunnissa jne. Muistettaessa Sense/Think/Act-silmukkaa, voimme kuvitella, että Think-osa valitsee nopeuden ja Act-osa soveltaa tätä nopeutta agenttiin. Tyypillisesti peleissä on fysiikkajärjestelmä, joka tekee tämän tehtävän puolestasi, oppii kunkin kohteen nopeusarvon ja säätää sitä. Siksi voit jättää tekoälyn yhteen tehtävään - päättää, mikä nopeus agentilla tulisi olla. Jos tiedät missä agentin pitäisi olla, sinun on siirrettävä sitä oikeaan suuntaan määritetyllä nopeudella. Hyvin triviaali yhtälö:
haluttu_matka = määränpään_sijainti – agentin_sijainti
Kuvittele 2D-maailma. Agentti on pisteessä (-2,-2), määränpää on jossain koillisessa pisteessä (30, 20), ja agentin vaadittu polku sinne on (32, 22). Oletetaan, että nämä paikat mitataan metreinä - jos otamme agentin nopeudeksi 5 metriä sekunnissa, skaalaamme siirtymävektorimme ja saamme nopeudeksi suunnilleen (4.12, 2.83). Näillä parametreilla agentti saapuisi määränpäähänsä lähes 8 sekunnissa.
Voit laskea arvot uudelleen milloin tahansa. Jos agentti olisi puolessavälissä kohdetta, liike olisi puolet pituudesta, mutta koska agentin maksiminopeus on 5 m/s (päätimme tämän edellä), nopeus on sama. Tämä toimii myös liikkuville kohteille, jolloin agentti voi tehdä pieniä muutoksia niiden liikkuessa.
Mutta haluamme enemmän vaihtelua - esimerkiksi lisäämällä hitaasti nopeutta simuloidaksemme hahmon siirtymistä seisomisesta juoksemiseen. Sama voidaan tehdä lopussa ennen pysähtymistä. Nämä ominaisuudet tunnetaan ohjauskäyttäytymisinä, joilla jokaisella on omat nimensä: Haku, Pako, Saapuminen jne. Ajatuksena on, että agentin nopeuteen voidaan soveltaa kiihtyvyysvoimia vertaamalla agentin sijaintia ja nykyistä nopeutta määränpäähän. käyttää erilaisia menetelmiä tavoitteeseen siirtymiseksi.
Jokaisella käytöksellä on hieman erilainen tarkoitus. Seek ja Arrival ovat tapoja siirtää agentti määränpäähän. Esteiden välttäminen ja erottelu säätävät agentin liikettä välttääkseen esteitä matkalla maaliin. Kohdistus ja koheesio pitävät agentit liikkumassa yhdessä. Mikä tahansa määrä erilaisia ohjauskäyttäytymistä voidaan laskea yhteen, jolloin saadaan yksi polkuvektori kaikki tekijät huomioon ottaen. Agentti, joka käyttää saapumis-, erottelu- ja esteen välttämiskäyttäytymistä pysyäkseen poissa seinistä ja muista tekijöistä. Tämä lähestymistapa toimii hyvin avoimissa paikoissa ilman tarpeettomia yksityiskohtia.
Vaikeammissa olosuhteissa erilaisten käyttäytymismallien lisääminen toimii huonommin – agentti voi esimerkiksi juuttua seinään Saapumisen ja Esteiden välttämisen välisen ristiriidan vuoksi. Siksi sinun on harkittava vaihtoehtoja, jotka ovat monimutkaisempia kuin pelkkä kaikkien arvojen lisääminen. Tapa on tämä: kunkin käyttäytymisen tulosten laskemisen sijaan voit harkita liikettä eri suuntiin ja valita parhaan vaihtoehdon.
Kuitenkin monimutkaisessa ympäristössä, jossa on umpikujia ja valintoja siitä, mihin suuntaan mennä, tarvitsemme jotain vielä edistyneempää.
Tapa löytää
Ohjauskäyttäytyminen sopii erinomaisesti yksinkertaiseen liikkumiseen avoimella alueella (jalkapallokenttä tai areena), jossa paikasta A paikkaan B pääseminen on suoraa polkua, jossa on vain pieniä kiertoteitä esteiden ympäri. Monimutkaisia reittejä varten tarvitsemme polunhakua, joka on tapa tutkia maailmaa ja päättää reitti sen läpi.
Yksinkertaisinta on lisätä ruudukko jokaiseen agentin vieressä olevaan ruutuun ja arvioida, mitkä niistä saavat liikkua. Jos jokin niistä on määränpää, seuraa reittiä jokaisesta ruudusta edelliseen, kunnes tulet alkuun. Tämä on reitti. Muussa tapauksessa toista prosessi lähellä olevien muiden ruutujen kanssa, kunnes löydät määränpääsi tai ruudut loppuvat (eli mahdollista reittiä ei ole). Tätä kutsutaan muodollisesti Breadth-First Searchiksi tai BFS:ksi (leveys ensin hakualgoritmi). Jokaisella askeleella hän katsoo kaikkiin suuntiin (siis leveys, "leveys"). Hakuavaruus on kuin aaltorintama, joka liikkuu, kunnes se saavuttaa halutun kohdan - hakuavaruus laajenee joka vaiheessa, kunnes loppupiste on mukana, minkä jälkeen se voidaan jäljittää takaisin alkuun.
Tämän seurauksena saat luettelon ruuduista, joita pitkin haluttu reitti kootaan. Tämä on polku (siis polkuhaku) - luettelo paikoista, joissa agentti vierailee seuraaessaan määränpäätä.
Koska tiedämme maailman jokaisen neliön sijainnin, voimme käyttää ohjauskäyttäytymistä liikkuaksemme polkua pitkin - solmusta 1 solmuun 2, sitten solmusta 2 solmuun 3 ja niin edelleen. Yksinkertaisin vaihtoehto on suunnata kohti seuraavan neliön keskustaa, mutta vielä parempi vaihtoehto on pysähtyä nykyisen ja seuraavan ruudun välisen reunan keskelle. Tämän ansiosta agentti pystyy leikkaamaan kulmia jyrkissä käännöksissä.
BFS-algoritmilla on myös haittoja - se tutkii yhtä monta neliötä "väärään" suuntaan kuin "oikeaan" suuntaan. Tässä tulee käyttöön monimutkaisempi algoritmi nimeltä A* (A tähti). Se toimii samalla tavalla, mutta sen sijaan, että tutkisi sokeasti naapurineliöitä (sitten naapurien naapurit, sitten naapurien naapurit ja niin edelleen), se kerää solmut listaksi ja lajittelee ne siten, että seuraava tutkittu solmu on aina joka johtaa lyhimmälle tielle. Solmut lajitellaan heuristiikan perusteella, joka ottaa huomioon kaksi asiaa: hypoteettisen reitin "kustannus" haluttuun neliöön (mukaan lukien mahdolliset matkakulut) ja arvio siitä, kuinka kaukana tämä neliö on määränpäästä (painottamalla hakua oikea suunta).
Tämä esimerkki osoittaa, että agentti tutkii yhtä ruutua kerrallaan ja valitsee joka kerta viereisen lupaavimman. Tuloksena oleva polku on sama kuin BFS, mutta vähemmän ruutuja otettiin huomioon prosessissa - millä on suuri vaikutus pelin suorituskykyyn.
Liikettä ilman verkkoa
Mutta useimpia pelejä ei ole asetettu ruudukolle, ja se on usein mahdotonta tehdä realismista tinkimättä. Kompromisseja tarvitaan. Minkä kokoisia neliöiden tulisi olla? Liian suuria, eivätkä ne pysty esittämään oikein pieniä käytäviä tai käännöksiä, liian pieniä ja etsittäväksi tulee liian monta neliötä, mikä vie lopulta paljon aikaa.
Ensimmäinen asia, joka on ymmärrettävä, on, että verkko antaa meille kaavion yhdistetyistä solmuista. A*- ja BFS-algoritmit toimivat itse asiassa kaavioissa eivätkä välitä verkkostamme ollenkaan. Voisimme sijoittaa solmuja mihin tahansa pelimaailmaan: niin kauan kuin kahden yhdistetyn solmun välillä sekä alku- ja loppupisteiden ja ainakin yhden solmun välillä on yhteys, algoritmi toimii yhtä hyvin kuin ennenkin. Tätä kutsutaan usein reittipistejärjestelmäksi, koska jokainen solmu edustaa merkittävää asemaa maailmassa, joka voi olla osa mitä tahansa hypoteettista polkua.
Esimerkki 1: solmu jokaisessa ruudussa. Haku alkaa solmusta, jossa agentti sijaitsee, ja päättyy halutun neliön solmuun.
Esimerkki 2: Pienempi joukko solmuja (reittipisteitä). Haku alkaa agentin neliöstä, käy läpi vaaditun määrän solmuja ja jatkuu sitten määränpäähän.
Tämä on täysin joustava ja tehokas järjestelmä. Mutta on huolellinen päätettäessä, mihin ja miten reittipiste sijoitetaan, muuten agentit eivät yksinkertaisesti näe lähintä pistettä eivätkä pysty aloittamaan polkua. Olisi helpompaa, jos voisimme asettaa reittipisteitä automaattisesti maailman geometrian perusteella.
Tässä näkyy navigointiverkko tai navmesh (navigointiverkko). Tämä on yleensä kolmioiden 2D-verkko, joka on peitetty maailman geometrian päällä - missä tahansa agentin sallitaan kävellä. Jokaisesta verkon kolmiosta tulee kaavion solmu, ja siinä on enintään kolme vierekkäistä kolmiota, joista tulee kaavion vierekkäisiä solmuja.
Tämä kuva on esimerkki Unity-moottorista - se analysoi maailman geometrian ja loi navmesh-verkon (kuvakaappauksessa vaaleansininen). Jokainen monikulmio navmeshissä on alue, jolla agentti voi seistä tai siirtyä polygonista toiseen. Tässä esimerkissä polygonit ovat pienempiä kuin kerrokset, joilla ne sijaitsevat - tämä tehdään, jotta voidaan ottaa huomioon agentin koko, joka ulottuu sen nimellisaseman ulkopuolelle.
Voimme etsiä reittiä tämän verkon läpi käyttämällä jälleen A*-algoritmia. Tämä antaa meille lähes täydellisen reitin maailmassa, joka ottaa huomioon kaiken geometrian ja ei vaadi tarpeettomia solmuja ja reittipisteiden luomista.
Pathfinding on liian laaja aihe, johon yksi artikkelin osa ei riitä. Jos haluat tutkia sitä tarkemmin, tämä auttaa .
Планирование
Olemme oppineet polunhaussa, että joskus ei riitä, että valitsemme suunnan ja siirrymme - meidän on valittava reitti ja tehtävä muutama käännös päästäksemme haluttuun määränpäähämme. Voimme yleistää tämän ajatuksen: tavoitteen saavuttaminen ei ole vain seuraava askel, vaan koko sarja, jossa joskus sinun on katsottava useita vaiheita eteenpäin saadaksesi selville, mikä ensimmäisen pitäisi olla. Tätä kutsutaan suunnitteluksi. Pathfinding voidaan ajatella yhtenä useista suunnittelun laajennuksista. Sense/Think/Act-syklissämme Think-osa suunnittelee useita Act-osia tulevaisuutta varten.
Katsotaanpa esimerkkiä lautapelistä Magic: The Gathering. Menemme ensin seuraavilla korttisarjoilla käsissämme:
- Suo - Antaa 1 mustan manan (maakortti).
- Metsä - antaa 1 vihreä mana (maakortti).
- Fugitive Wizard - Vaatii 1 sinisen manan kutsuakseen.
- Elvish Mystic - Vaatii 1 vihreän manan kutsumiseen.
Jäljelle jääneet kolme korttia jätämme huomioimatta sen helpottamiseksi. Sääntöjen mukaan pelaaja saa pelata 1 maakortti per vuoro, hän voi "napauttaa" tätä korttia poimiakseen siitä manaa ja sitten loitsua (mukaan lukien olennon kutsuminen) manan määrän mukaan. Tässä tilanteessa ihmispelaaja osaa pelata Forestia, napauttaa 1 vihreää manaa ja kutsua sitten Elvish Mysticin. Mutta miten pelin tekoäly voi selvittää tämän?
Helppoa suunnittelua
Triviaali lähestymistapa on kokeilla jokaista toimintaa vuorotellen, kunnes sopivia ei ole enää jäljellä. Kortteja katsomalla tekoäly näkee, mitä Swamp voi pelata. Ja hän pelaa sitä. Onko muita toimintoja jäljellä tällä vuorolla? Se ei voi kutsua Elvish Mysticiä tai Fugitive Wizardia, koska ne vaativat vihreää ja sinistä manaa kutsuakseen heidät, kun taas Swamp tarjoaa vain mustaa manaa. Ja hän ei voi enää pelata Forestia, koska hän on jo pelannut Swampia. Siten pelin tekoäly noudatti sääntöjä, mutta teki sen huonosti. Voidaan parantaa.
Suunnittelu voi löytää luettelon toiminnoista, jotka tuovat pelin haluttuun tilaan. Aivan kuten jokaisella polun ruudulla oli naapureita (polun etsinnässä), jokaisella suunnitelman toiminnolla on myös naapureita tai seuraajia. Voimme etsiä näitä toimia ja myöhempiä toimia, kunnes saavutamme halutun tilan.
Esimerkissämme haluttu tulos on "kutsu olento, jos mahdollista". Vuoron alussa näemme vain kaksi mahdollista pelisääntöjen sallimaa toimintaa:
1. Pelaa Swampia (tulos: Swamp pelissä)
2. Pelaa Metsää (tulos: Metsä pelissä)
Jokainen suoritettu toiminta voi johtaa uusiin toimiin ja sulkea muita, jälleen pelin säännöistä riippuen. Kuvittele, että pelasimme Swampin - tämä poistaa Swampin seuraavana vaiheena (olemme jo pelanneet sen), ja tämä poistaa myös Forestin (koska sääntöjen mukaan voit pelata yhden maakortin per vuoro). Tämän jälkeen tekoäly lisää 1 mustan manan saamisen seuraavaksi askeleeksi, koska muita vaihtoehtoja ei ole. Jos hän menee eteenpäin ja valitsee Tap the Swamp, hän saa 1 yksikön mustaa manaa eikä voi tehdä sillä mitään.
1. Pelaa Swampia (tulos: Swamp pelissä)
1.1 "Tap" Suo (tulos: Suo "tapped", +1 yksikkö mustaa manaa)
Toimintoja ei ole käytettävissä - END
2. Pelaa Metsää (tulos: Metsä pelissä)
Toimenpiteiden luettelo oli lyhyt, saavuimme umpikujaan. Toistamme prosessin seuraavaa vaihetta varten. Pelaamme Forestia, avaa toiminnon "hanki 1 vihreä mana", joka puolestaan avaa kolmannen toiminnon - kutsu Elvish Mystic.
1. Pelaa Swampia (tulos: Swamp pelissä)
1.1 "Tap" Suo (tulos: Suo "tapped", +1 yksikkö mustaa manaa)
Toimintoja ei ole käytettävissä - END
2. Pelaa Metsää (tulos: Metsä pelissä)
2.1 "Tap" -metsä (tulos: metsä on "kierretty", +1 yksikkö vihreää manaa)
2.1.1 Kutsu Elvish Mystic (tulos: Elvish Mystic pelissä, -1 vihreä mana)
Toimintoja ei ole käytettävissä - END
Lopuksi tutkimme kaikkia mahdollisia toimia ja löysimme suunnitelman, joka kutsuu olennon.
Tämä on hyvin yksinkertaistettu esimerkki. On suositeltavaa valita paras mahdollinen suunnitelma mieluummin kuin mikä tahansa suunnitelma, joka täyttää tietyt kriteerit. Mahdollisia suunnitelmia on yleensä mahdollista arvioida niiden toteuttamisen tuloksen tai kokonaishyödyn perusteella. Voit saada itsellesi 1 pisteen maakortin pelaamisesta ja 3 pistettä olennon kutsumisesta. Swampin pelaaminen olisi yhden pisteen suunnitelma. Ja pelaamalla Metsää → Napauta metsää → kutsu Elvish Mystic antaa heti 1 pistettä.
Näin suunnittelu toimii Magic: The Gatheringissa, mutta sama logiikka pätee muissakin tilanteissa. Esimerkiksi pelinappulan siirtäminen, jotta piispa voi liikkua shakissa. Tai suojaudu seinän takana ampuaksesi turvallisesti XCOMissa tällä tavalla. Yleisesti ottaen ymmärrät idean.
Parempi suunnittelu
Joskus on liian monia mahdollisia toimia, jotta kaikki mahdolliset vaihtoehdot voitaisiin harkita. Palataksemme Magic: The Gatheringin esimerkkiin: oletetaan, että pelissä ja kädessäsi on useita maa- ja olentokortteja – mahdollisten siirtoyhdistelmien määrä voi olla kymmeniä. Ongelmaan on useita ratkaisuja.
Ensimmäinen menetelmä on taaksepäin ketjuttaminen. Sen sijaan, että kokeilisit kaikkia yhdistelmiä, on parempi aloittaa lopputuloksesta ja yrittää löytää suora reitti. Sen sijaan, että siirtyisimme puun juuresta tiettyyn lehteen, siirrymme päinvastaiseen suuntaan - lehdestä juureen. Tämä menetelmä on helpompi ja nopeampi.
Jos vihollisella on 1 terveys, voit löytää "jaa 1 tai useampi vahinko" -suunnitelman. Tämän saavuttamiseksi on täytyttävä useita ehtoja:
1. Vahinko voi johtua loitsusta - sen on oltava kädessä.
2. Loitsun tekemiseen tarvitaan manaa.
3. Saadaksesi manan, sinun on pelattava maakortti.
4. Jotta voit pelata maakorttia, sinulla on oltava se kädessäsi.
Toinen tapa on paras ensin -haku. Sen sijaan, että kokeilemme kaikkia polkuja, valitsemme sopivimman. Useimmiten tämä menetelmä antaa optimaalisen suunnitelman ilman tarpeettomia hakukustannuksia. A* on parhaan ensimmäisen haun muoto - tutkimalla lupaavimpia reittejä alusta alkaen, se löytää jo parhaan polun ilman, että tarvitsee tarkistaa muita vaihtoehtoja.
Mielenkiintoinen ja yhä suositumpi paras ensin -hakuvaihtoehto on Monte Carlo Tree Search. Sen sijaan, että arvaisi, mitkä suunnitelmat ovat muita parempia valitessaan jokaista seuraavaa toimintaa, algoritmi valitsee satunnaisia seuraajia jokaisessa vaiheessa, kunnes se saavuttaa loppuun (kun suunnitelma johti voittoon tai tappioon). Lopullista tulosta käytetään sitten aiempien vaihtoehtojen painon lisäämiseen tai vähentämiseen. Toistamalla tätä prosessia useita kertoja peräkkäin, algoritmi antaa hyvän arvion siitä, mikä on paras seuraava siirto, vaikka tilanne muuttuisi (jos vihollinen häiritsee pelaajaa).
Mikään tarina pelien suunnittelusta ei olisi täydellinen ilman tavoiteorientoitua toimintasuunnittelua tai GOAP-ohjelmaa (tavoitteellinen toimintasuunnittelu). Tämä on laajalti käytetty ja keskusteltu menetelmä, mutta muutamien erottavien yksityiskohtien lisäksi se on olennaisesti taaksepäin ketjutusmenetelmä, josta puhuimme aiemmin. Jos tavoitteena oli "tuhota pelaaja" ja pelaaja on suojan takana, suunnitelma voisi olla: tuhoa kranaatilla → hanki → heitä.
Tavoitteita on yleensä useita, jokaisella on oma prioriteettinsa. Jos korkeimman prioriteetin tavoitetta ei voida saavuttaa (mikään toimien yhdistelmä ei luo "tappaa pelaaja" -suunnitelmaa, koska pelaaja ei ole näkyvissä), tekoäly palaa alemman prioriteetin tavoitteisiin.
Koulutus ja sopeutuminen
Olemme jo sanoneet, että pelin tekoäly ei yleensä käytä koneoppimista, koska se ei sovellu agenttien hallintaan reaaliajassa. Mutta tämä ei tarkoita, että et voisi lainata jotain tältä alueelta. Haluamme ampujaan vastustajan, jolta voimme oppia jotain. Ota esimerkiksi selvää parhaista paikoista kartalla. Tai vastustaja taistelupelissä, joka estäisi pelaajan usein käytetyt yhdistelmäliikkeet ja motivoi häntä käyttämään muita. Joten koneoppimisesta voi olla varsin hyödyllistä tällaisissa tilanteissa.
Tilastot ja todennäköisyydet
Ennen kuin menemme monimutkaisiin esimerkkeihin, katsotaanpa, kuinka pitkälle voimme mennä tekemällä muutama yksinkertainen mittaus ja käyttämällä niitä päätöksenteossa. Esimerkiksi reaaliaikainen strategia - miten määritämme, voiko pelaaja aloittaa hyökkäyksen pelin ensimmäisten minuuttien aikana ja mikä puolustus on valmistauduttava tätä vastaan? Voimme tutkia pelaajan menneitä kokemuksia ymmärtääksemme, mitä tulevat reaktiot voivat olla. Aluksi meillä ei ole tällaista raakadataa, mutta voimme kerätä ne - joka kerta kun tekoäly pelaa ihmistä vastaan, se voi tallentaa ensimmäisen hyökkäyksen ajan. Muutaman istunnon jälkeen saamme keskimäärin ajan, joka pelaajalta kestää hyökätä tulevaisuudessa.
Keskiarvoissa on myös ongelma: jos pelaaja ryntäsi 20 kertaa ja pelasi hitaasti 20 kertaa, vaaditut arvot ovat jossain puolivälissä, eikä tästä ole meille mitään hyötyä. Yksi ratkaisu on syöttötietojen rajoittaminen - viimeiset 20 kappaletta voidaan ottaa huomioon.
Samanlaista lähestymistapaa käytetään arvioitaessa tiettyjen toimien todennäköisyyttä olettaen, että pelaajan aiemmat mieltymykset ovat samat myös tulevaisuudessa. Jos pelaaja hyökkää meihin viisi kertaa tulipallolla, kaksi kertaa salamalla ja kerran lähitaistelulla, on selvää, että hän pitää tulipallosta parempana. Ekstrapoloidaan ja katsotaan eri aseiden käyttötodennäköisyys: tulipallo=62,5%, salama=25% ja lähitaistelu=12,5%. Pelimme tekoälyn on valmistauduttava suojautumaan tulelta.
Toinen mielenkiintoinen tapa on käyttää Naive Bayes Classifier -luokittajaa suurten syöttötietomäärien tutkimiseen ja tilanteen luokitteluun niin, että tekoäly reagoi halutulla tavalla. Bayesin luokittelijat tunnetaan parhaiten käytöstä sähköpostin roskapostisuodattimissa. Siellä he tutkivat sanoja, vertaavat niitä siihen, missä sanat ovat esiintyneet aiemmin (roskapostissa tai ei) ja tekevät johtopäätöksiä saapuvista sähköposteista. Voimme tehdä saman jopa pienemmällä syöttömäärällä. Perustuu kaikkiin tekoälyn näkemiin hyödyllisiin tietoihin (kuten mitä vihollisen yksiköitä luodaan, mitä loitsuja ne käyttävät tai mitä tekniikoita he tutkivat) ja lopputulokseen (sota tai rauha, kiire tai puolustaminen jne.) - Valitsemme halutun tekoälykäyttäytymisen.
Kaikki nämä koulutusmenetelmät ovat riittäviä, mutta niitä kannattaa käyttää testaustietojen perusteella. Tekoäly oppii mukautumaan pelitestaajien käyttämiin erilaisiin strategioihin. Tekoäly, joka mukautuu soittimeen julkaisun jälkeen, voi muuttua liian ennustettavaksi tai liian vaikeaksi voittaa.
Arvopohjainen sopeutuminen
Pelimaailmamme sisällön ja sääntöjen perusteella voimme muuttaa päätöksentekoon vaikuttavia arvoja sen sijaan, että käytämme vain syötetietoja. Teemme näin:
- Anna tekoälyn kerätä tietoja maailman tilasta ja tärkeimmistä tapahtumista pelin aikana (kuten yllä).
- Muutetaan muutamia tärkeitä arvoja näiden tietojen perusteella.
- Toteutamme päätöksemme näiden arvojen käsittelyn tai arvioinnin perusteella.
Esimerkiksi agentilla on useita huoneita, joista valita ensimmäisen persoonan ammuntakartalla. Jokaisella huoneella on oma arvonsa, joka määrittää, kuinka toivottavaa siellä on vierailla. Tekoäly valitsee satunnaisesti, mihin huoneeseen mennään arvon perusteella. Agentti muistaa sitten missä huoneessa hänet tapettiin ja vähentää sen arvoa (todennäköisyyttä, että hän palaa sinne). Samoin päinvastaisessa tilanteessa - jos agentti tuhoaa monta vastustajaa, huoneen arvo nousee.
Markovin malli
Entä jos käyttäisimme kerättyä tietoa ennusteiden tekemiseen? Jos muistamme jokaisen huoneen, jossa näemme pelaajan tietyn ajan, ennustamme mihin huoneeseen pelaaja saattaa mennä. Seuraamalla ja tallentamalla pelaajan liikkeitä huoneiden välillä (arvot), voimme ennustaa ne.
Otetaan kolme huonetta: punainen, vihreä ja sininen. Ja myös havainnot, jotka kirjasimme katsoessamme pelisession:
Havaintoja on jokaisessa huoneessa lähes yhtä paljon - emme vielä tiedä, mistä tehdä hyvä väijytyspaikka. Tilastojen keräämistä vaikeuttaa myös pelaajien uudelleensyntyminen, jotka näkyvät tasaisesti koko kartalla. Mutta tiedot seuraavasta huoneesta, joihin he tulevat kartalle ilmestymisen jälkeen, ovat jo hyödyllisiä.
Näkyy, että green room sopii pelaajille - suurin osa ihmisistä muuttaa punaisesta huoneesta sinne, joista 50% jää sinne pidemmälle. Sininen huone sitä vastoin ei ole suosittu, sinne ei mene melkein kukaan, ja jos käy, ei viihdy pitkään.
Mutta tiedot kertovat meille jotain tärkeämpää - kun pelaaja on sinisessä huoneessa, seuraava huone, jossa näemme hänet, on punainen, ei vihreä. Vaikka vihreä huone on suositumpi kuin punainen huone, tilanne muuttuu, jos pelaaja on sinisessä huoneessa. Seuraava tila (eli huone, johon pelaaja menee) riippuu edellisestä tilasta (eli huoneesta, jossa pelaaja tällä hetkellä on). Koska tutkimme riippuvuuksia, teemme tarkempia ennusteita kuin jos laskemme havainnot itsenäisesti.
Tulevan tilan ennustamista menneen tilan datan perusteella kutsutaan Markovin malliksi ja tällaisia esimerkkejä (huoneiden kanssa) kutsutaan Markov-ketjuiksi. Koska kuviot edustavat muutosten todennäköisyyttä peräkkäisten tilojen välillä, ne näytetään visuaalisesti FSM:inä todennäköisyydellä jokaisen siirtymän ympärillä. Aiemmin käytimme FSM:ää edustamaan käyttäytymistilaa, jossa agentti oli, mutta tämä käsite ulottuu kaikkiin tiloihin riippumatta siitä, liittyykö se agenttiin vai ei. Tässä tapauksessa tilat edustavat tilaa, jossa agentti asuu:
Tämä on yksinkertainen tapa esittää tilanmuutosten suhteellinen todennäköisyys, mikä antaa tekoälylle jonkin verran kykyä ennustaa seuraava tila. Voit ennakoida useita vaiheita eteenpäin.
Jos pelaaja on green roomissa, on 50 % todennäköisyys, että hän pysyy siellä seuraavan kerran, kun häntä tarkkaillaan. Mutta mitkä ovat todennäköisyydet, että hän on siellä vielä sen jälkeenkin? Ei ole vain mahdollista, että pelaaja jäi green roomiin kahden havainnon jälkeen, vaan on myös mahdollista, että hän lähti ja palasi. Tässä on uusi taulukko, jossa otetaan huomioon uudet tiedot:
Se osoittaa, että mahdollisuus nähdä pelaaja vihreässä huoneessa kahden havainnon jälkeen on 51 % - 21 %, että hän tulee punaisesta huoneesta, 5 %, että pelaaja vierailee heidän välisessä sinisessä huoneessa, ja 25 %, jota pelaaja ei poistu vihreästä huoneesta.
Taulukko on yksinkertaisesti visuaalinen työkalu - menettely vaatii vain kertomalla todennäköisyydet jokaisessa vaiheessa. Tämä tarkoittaa, että voit katsoa pitkälle tulevaisuuteen yhdellä varoituksella: oletamme, että huoneeseen pääsy riippuu täysin nykyisestä huoneesta. Tätä kutsutaan Markovin omaisuudeksi - tulevaisuuden tila riippuu vain nykyhetkestä. Mutta tämä ei ole sataprosenttisen tarkka. Pelaajat voivat muuttaa päätöksiä muista tekijöistä riippuen: terveystasosta tai ammusten määrästä. Koska emme tallenna näitä arvoja, ennusteemme ovat vähemmän tarkkoja.
N-grammaa
Entä esimerkki taistelupelistä ja pelaajan yhdistelmäliikkeiden ennustamisesta? Sama! Mutta yhden tilan tai tapahtuman sijasta tarkastelemme kokonaisia sekvenssejä, jotka muodostavat yhdistelmäiskun.
Yksi tapa tehdä tämä on tallentaa jokainen syöte (kuten Kick, Punch tai Block) puskuriin ja kirjoittaa koko puskuri tapahtumaksi. Joten pelaaja painaa toistuvasti Kick, Kick, Punch käyttääkseen SuperDeathFist-hyökkäystä, tekoälyjärjestelmä tallentaa kaikki syötteet puskuriin ja muistaa kolme viimeistä jokaisessa vaiheessa käytettyä.
(Lihavoidut rivit ovat silloin, kun pelaaja käynnistää SuperDeathFist-hyökkäyksen.)
Tekoäly näkee kaikki vaihtoehdot, kun pelaaja valitsee Kick, jota seuraa toinen Kick, ja huomaa sitten, että seuraava syöte on aina Punch. Näin agentti voi ennustaa SuperDeathFistin yhdistelmäliikkeen ja estää sen, jos mahdollista.
Näitä tapahtumasarjoja kutsutaan N-grammeiksi, missä N on tallennettujen elementtien lukumäärä. Edellisessä esimerkissä se oli 3 grammaa (trigrammi), mikä tarkoittaa: kahta ensimmäistä merkintää käytetään kolmannen ennustamiseen. Näin ollen 5-grammassa neljä ensimmäistä merkintää ennustavat viidennen ja niin edelleen.
Suunnittelijan on valittava N-grammien koko huolellisesti. Pienempi N vaatii vähemmän muistia, mutta myös tallentaa vähemmän historiaa. Esimerkiksi 2-grammainen (bigrammi) tallentaa Kick, Kick tai Kick, Punch, mutta ei voi tallentaa Kick, Kick, Punch, joten tekoäly ei reagoi SuperDeathFist-yhdistelmään.
Toisaalta suuremmat luvut vaativat enemmän muistia ja tekoälyä on vaikeampi harjoitella, koska mahdollisia vaihtoehtoja on paljon enemmän. Jos sinulla olisi kolme mahdollista tuloa Kick, Punch tai Block, ja käyttäisimme 10 grammaa, se olisi noin 60 tuhatta eri vaihtoehtoa.
Bigrammimalli on yksinkertainen Markov-ketju - jokainen mennyt tila/nykyinen tila -pari on bigrammi, ja voit ennustaa toisen tilan ensimmäisen perusteella. 3-grammat ja sitä suuremmat N-grammat voidaan ajatella myös Markovin ketjuina, joissa kaikki elementit (paitsi viimeinen N-grammassa) yhdessä muodostavat ensimmäisen tilan ja viimeinen elementti toisen. Taistelupeliesimerkki näyttää mahdollisuuden siirtyä Kick and Kick -tilasta Kick and Punch -tilaan. Käsittelemällä useita syöttöhistorian merkintöjä yhtenä yksikkönä muunnamme syöttösekvenssin olennaisesti osaksi koko tilaa. Tämä antaa meille Markov-ominaisuuden, jonka avulla voimme käyttää Markov-ketjuja ennustamaan seuraavaa syötettä ja arvaamaan, mikä yhdistelmäliike on seuraava.
Johtopäätös
Keskustelimme yleisimmistä työkaluista ja lähestymistavoista tekoälyn kehittämisessä. Pohdimme myös tilanteita, joissa niitä pitää käyttää ja missä niistä on erityisen hyötyä.
Tämän pitäisi riittää ymmärtämään pelin tekoälyn perusteet. Mutta tietenkään nämä eivät ole kaikki menetelmiä. Vähemmän suosittuja, mutta yhtä tehokkaita ovat:
- optimointialgoritmit, mukaan lukien mäkikiipeily, kaltevuus laskeutuminen ja geneettiset algoritmit
- kontradiktoriset haku-/aikataulutusalgoritmit (minimax ja alfa-beta karsiminen)
- luokittelumenetelmät (perceptronit, hermoverkot ja tukivektorikoneet)
- järjestelmät agenttien havainnon ja muistin käsittelemiseksi
- arkkitehtoniset lähestymistavat tekoälyyn (hybridijärjestelmät, osajoukkoarkkitehtuurit ja muut tavat peittää tekoälyjärjestelmiä)
- animaatiotyökalut (suunnittelu ja liikkeen koordinointi)
- suorituskykytekijät (yksityiskohtien taso, milloin tahansa ja aikaviipalointialgoritmit)
Internet-resurssit aiheesta:
1. GameDev.net on Ja .
2. sisältää monia esityksiä ja artikkeleita useista pelien tekoälyn kehittämiseen liittyvistä aiheista.
3. sisältää aiheita GDC AI Summitista, joista monet ovat saatavilla ilmaiseksi.
4. Verkkosivustolta löytyy myös hyödyllistä materiaalia .
5. Tommy Thompson, tekoälytutkija ja pelien kehittäjä, tekee videoita YouTubessa kaupallisten pelien tekoälyn selityksen ja tutkimuksen kanssa.
Aiheeseen liittyviä kirjoja:
1. Game AI Pro -kirjasarja on kokoelma lyhyitä artikkeleita, jotka selittävät, miten tiettyjä ominaisuuksia voidaan ottaa käyttöön tai miten ratkaista tiettyjä ongelmia.
2. AI Game Programming Wisdom -sarja on Game AI Pro -sarjan edeltäjä. Se sisältää vanhoja menetelmiä, mutta lähes kaikki ovat relevantteja vielä tänäkin päivänä.
3. on yksi perusteksteistä kaikille, jotka haluavat ymmärtää tekoälyn yleistä alaa. Tämä kirja ei ole pelinkehityksestä - se opettaa tekoälyn perusteita.
Lähde: will.com