Share
En * nettbasert opplæring fungerer bra for spill der tegnene kan bevege seg fritt langs både x- og y-aksene. Problemet med å bruke dette på plattformspillere er at bevegelsen på y-aksen er sterkt begrenset på grunn av simulerte tyngdekraften.
I denne opplæringen gir jeg en bred oversikt over hvordan man endrer en standard A * -algoritme til å jobbe for plattformspillere ved å simulere disse gravitasjonsbegrensningene. (I neste del går jeg gjennom å faktisk kode algoritmen.) Den tilpassede algoritmen kan brukes til å lage et AI-tegn som følger spilleren, eller for å vise spilleren en rute til målet deres, for eksempel.
Jeg antar her at du allerede er kjent med A * -opplæring, men hvis du trenger en introduksjon, er Patrick Lesters A * Pathfinding for Beginners utmerket.
Du kan spille Unity-demoen, eller WebGL-versjonen (64MB), for å se det endelige resultatet i handling. Bruk WASD å flytte tegnet, venstre klikk på et sted for å finne en sti du kan følge for å komme dit, og Høyreklikk en celle for å skifte bakken på det punktet.
Ved slutten av denne serien har vi også lagt til enveisplattformer, utvidet koden for å håndtere forskjellige størrelser karakter, og kodet en bot som automatisk kan følge banen! Sjekk ut at Unity demo her (eller 100MB + WebGL-versjonen).
Før vi kan tilpasse treningsalgoritmen, må vi tydelig definere hvilke former banene selv kan ta.
La oss si at vår karakter tar opp en celle, og kan hoppe tre celler høy.
Vi vil ikke tillate at karakteren vår beveger seg diagonalt gjennom celler, fordi vi ikke vil at den skal gå gjennom solid terreng. (Det vil si at vi ikke tillater det å bevege seg gjennom et cellehjørne, bare gjennom toppen, bunnen, venstre eller høyre side.) Hvis du vil flytte til en diagonalt tilstøtende celle, må tegnet flytte en celle opp eller ned , og en celle venstre eller høyre.
Siden karakterens hopphøyde er tre celler, så når den hopper, etter at den har beveget seg tre ganger, bør den ikke være i stand til å bevege seg opp noen flere celler, men det skal fortsatt kunne flytte til side.
Basert på disse reglene er det et eksempel på stien karakteren ville ta under maksimal avstandshopp:
Selvfølgelig kan tegnet hoppe rett opp, eller med en hvilken som helst kombinasjon av venstre og høyre bevegelser, men dette eksemplet viser hva slags tilnærming vi må omfavne når vi beregner banen ved hjelp av rutenettet.
Hver av cellene i banen må holde data om hopphøyden, slik at vår algoritme kan oppdage at spilleren ikke kan hoppe høyere og må begynne å falle ned.
La oss starte med å tilordne hver celle hoppverdien ved å øke den med en, hver celle, så lenge hoppet fortsetter. Selvfølgelig, når tegnet er på bakken, bør hoppverdien være 0.
Her er den regelen som brukes på samme maksimal distansehoppbane fra før:
Cellen som inneholder en 6 markerer det høyeste punktet i banen. Dette er fornuftig, siden det er to ganger verdien av tegnets maksimale hopphøyde, og tegnet veksler mellom å flytte en celle opp og en celle til siden, i dette eksempelet.
Vær oppmerksom på at hvis karakteren hopper rett opp, og vi fortsetter å øke hoppverdien av en hver celle, virker dette ikke lenger, fordi i så fall vil den høyeste cellen ha en hoppeverdi på 3.
La oss endre regelen vår for å øke hoppverdien til neste jevne tall når tegnet beveger seg oppover. Deretter, hvis hoppverdien er jevn, kan tegnet bevege seg enten til venstre, høyre eller ned (eller opp, hvis de ikke har nådd en hoppeverdi på 6 ennå), og hvis hoppverdien er merkelig, flyttes tegnet bare opp eller ned (avhengig av om de har nådd toppen av hoppet ennå).
Her er det som ser ut til et hopp rett opp:
Og her er en mer komplisert sak:
Slik beregnes hoppverdiene:
Som du kan se, med denne typen nummerering vet vi nøyaktig når karakteren når sin maksimale hopphøyde: det er cellen med hoppverdien lik til to ganger Maksimal karakter hopphøyde. Hvis hoppverdien er mindre enn dette, kan tegnet fortsatt bevege seg oppover; Ellers må vi ignorere noden direkte over.
Nå som vi er klar over hva slags bevegelser karakteren kan gjøre på rutenettet, la oss vurdere følgende oppsett:
Den grønne cellen i posisjon (3, 1) er tegnet; den blå cellen i posisjon (2, 5) er målet. La oss tegne en rute som A * -algoritmen kan velge først for å forsøke å nå målet @
Det gule tallet i øverste høyre hjørne av en celle er cellens hoppeverdi. Som du kan se, med et rett oppoverhopp, kan tegnet hoppe over tre fliser, men ikke lenger. Dette er ikke bra.
Vi kan finne lykke med en annen rute, så la oss spole på søket og starte igjen fra node (3, 2).
Som du kan se, hoppet på blokken til høyre for tegnet tillot det å hoppe høyt nok for å komme til målet! Det er imidlertid et stort problem her ...
I all sannsynlighet vil den første ruten algoritmen tar, er den første vi undersøkte. Etter å ha tatt det, vil algoritmen ikke bli veldig langt, og vil ende opp igjen på knutepunktet (3, 2). Det kan da søke gjennom noder (4, 2), (4, 3), (3, 3) (en gang til), (3, 4) (en gang til), (3, 5), og til slutt målcellen, (2, 5).
I en grunnleggende versjon av A * -algoritmen, hvis en knute har blitt besøkt en gang allerede, trenger vi ikke å behandle det noen gang igjen. I denne versjonen gjør vi imidlertid. Dette skyldes at nodene ikke skilles utelukkende av x- og y-koordinater, men også av hoppverdier.
I vårt første forsøk på å finne en bane, hoppe verdien på knutepunktet (3, 3) var 4; i vårt andre forsøk var det 3. Siden i det andre forsøket var hoppverdien på den cellen mindre, betydde det at vi kunne potensielt bli høyere derfra enn vi kunne under det første forsøket.
Dette betyr i utgangspunktet at knutepunktet (3, 3) med en hoppeverdi på 4 er en forskjellig knutepunkt enn node på (3, 3) med en hoppeverdi på 3. Gitteret må i hovedsak bli tredimensjonalt ved noen koordinater for å imøtekomme disse forskjellene, slik som:
Vi kan ikke bare endre hoppverdien til noden på (3, 3) fra 4 til 3, fordi noen baner bruker samme node flere ganger; hvis vi gjorde det, ville vi i utgangspunktet tilsidesette den forrige noden, og det ville selvsagt ødelegge sluttresultatet.
Vi ville ha det samme problemet hvis den første banen ville ha nådd målet til tross for de høyere hoppverdiene; hvis vi hadde overstyrt en av noderne med en mer lovende en, ville vi ikke ha mulighet til å gjenopprette den opprinnelige banen.
Husk, det er det algoritme som bruker en nettbasert tilnærming; i teorien trenger ikke spillet ditt og dets nivåer.
Det er viktig for karakteren å ha i det minste like mye bevegelsesfrihet som algoritmen forventer - og helst litt mer enn det.
Å ha karakterbevegelsen samsvarer nøyaktig algoritmenes begrensninger er ikke en levedyktig tilnærming, på grunn av gridens diskrete natur og gridets cellestørrelse. Det er mulig å kode fysikken på en slik måte at algoritmen vil alltid finn en måte hvis det er en, men det krever at du bygger fysikken for det formålet.
Tilnærmingen jeg tar i denne opplæringen er å passe algoritmen til spillets fysikk, ikke omvendt.
De største problemene oppstår i kantsaker når algoritmens forventede frihetsbevegelsesfrihet ikke samsvarer med den sanne karakteren i bevegelsesfrihetens bevegelsesfrihet.
La oss si at AI muliggjør hopp seks celler lang, men spillets fysikk tillater en syv-cellers hopp. Hvis det er en sti som krever at det lengre hoppet når målet på den raskeste tiden, vil bot ignorere den banen og velge den mer konservative, tenker at det lengre hoppet er umulig.
Hvis det er en sti som krever lengre hopp, og det ikke er noen annen måte å nå målet, vil lederen konkludere med at målet ikke er nås.
Hvis omvendt mener algoritmen at det er mulig å hoppe over syv celler unna, men spillets fysikk tillater bare for et seks-cellers hopp, så kan bot enten følge feil vei og falle inn i et sted som det ikke kan få ut, eller prøv å finne en bane igjen og motta det samme feilresultatet, forårsake en sløyfe.
(Ut av disse to problemene, er det å foretrekke å la spillets fysikk tillate mer bevegelsesfrihet enn algoritmen forventer.)
Den første måten å sikre at algoritmen alltid er riktig, er å ha nivåer som spillere ikke kan endre. I dette tilfellet trenger du bare å sørge for at det terrenget du designer eller genererer, fungerer godt sammen med AI.
Den andre løsningen på disse problemene er å finjustere algoritmen, fysikken eller begge deler for å sikre at de samsvarer. Som jeg nevnte tidligere, betyr dette ikke at de trenger å matche nøyaktig; for eksempel hvis algoritmen mener at tegnet kan hoppe fem celler oppover, er det greit å sette det virkelige maksimale hoppet på 5.5 celler høye. (I motsetning til algoritmen kan spillets fysikk bruke brøkdelte verdier.)
Avhengig av spillet, kan det også være sant at AI bot ikke finner en eksisterende bane, er ikke en stor avtale; det vil ganske enkelt gi opp og gå tilbake til innlegget sitt, eller bare sitte og vent på spilleren.
På dette tidspunktet bør du ha en anstendig konseptuell forståelse av hvordan A * -opplæring kan tilpasses til en plattformspiller. I min neste opplæring, gjør vi denne konkreten ved å faktisk tilpasse en eksisterende A * pathfinding-algoritme for å implementere dette i et spill!
Accentsconagua