Share
Pathfinding er allestedsnærværende i spill. Så det er viktig å forstå implikasjonene som er tilstede når du bruker algoritmer som A *. I denne opplæringen skal vi dekke en relativt ny metode for å søke i nettbaserte verdener: Jump Point Search, som kan øke hastigheten på A * ved størrelsesorden.
Merk: Selv om denne opplæringen er skrevet med AS3 og Flash, bør du kunne bruke de samme teknikkene og konseptene i nesten hvilket som helst spillutviklingsmiljø.
Denne implementeringen er basert på det originale papiret og artikkelen på JPS funnet her: Jump Point Search. De
Lua-basert implementering, Jumper, ble brukt til hjelp med enkelte deler av implementeringen.
Klikk på SWF for å gi det fokus, flytt deretter musen over ikke-blokkerende områder på kartet for å få NPCene til å prøve å komme seg til det. Trykk på plass for å bytte mellom A *, Jump Point Search, og begge deler.
Ingen Flash? Sjekk ut YouTube-videoen i stedet:
Demo-implementeringen ovenfor bruker AS3 og Flash med Starling Framework for GPU-akselerert rendering og polygonal-ds-biblioteket for datastrukturer.
Pathfinding brukes ofte i videospill, og du er sikker på å støte på den på et eller annet tidspunkt i løpet av spillutviklings karriere. Dens primære bruk er å gi intelligent utseende bevegelsesadferd til kunstige enheter (NPCer) for å unngå at de støter på ting (ofte).
I noen spill er spilleren avatar også utsatt for pathfinding (strategispill, mange tredjeparts RPG og eventyrspill). Så du kan anta at problemet med oppdagelse er løst, men det er dessverre ikke tilfelle. Det er ingen sølvkule som du kan bruke og bare gjøres med den.
Og selv i store AAA-spill, vil du fortsatt finne morsomme ting som dette:
Det kan ikke være en sølvkule, men det er en kule: A * (A-stjerne) -algoritmen. I denne opplæringen skal vi se en kort oversikt over A * og hvordan du kan øke hastigheten med en annen algoritme, Jump Point Search.
Først trenger vi en måte å representere vår spillverden på, slik at en pathfinding-algoritme kan bruke den.
En av de viktigste tingene å vurdere når du tenker på å finne frem til spillet ditt er verdensrepresentasjon. Hvordan er dataene til de tilgjengelige områdene og hindringene organisert med programmeringsstrukturer i minnet?
Den enkleste representasjonen du kan bruke er en nettbasert struktur, der sti noder er organisert i et rutenett og kan representeres av en 2D-array. Vi skal bruke denne representasjonen i denne opplæringen. Spesielt vil det være en åtte-veis grid representasjon: tillater bevegelse i rette og diagonale retninger.
Dine krav kan være forskjellige, så denne strukturen kan ikke passe deg. God ting er at med litt behandling (vanligvis gjort offline) kan du endre pathfinding-representasjoner til andre formater. Alternativer til gridbasert tilnærming vil inkludere ting som polygon (hindringer representert av polygoner) eller navigasjonsmasker (navigasjonsområder representert ved polygoner); Disse kan representere de samme dataene med færre noder.
En annen data som kan lagres i kartrepresentasjon er kostnader: Hvor mye koster det å reise fra en node til en annen. Dette kan brukes for AI til å bestemme stien som for eksempel foretrekker veier over vanlig terreng (noe som gjør kostnaden for veien mindre enn terrenget).
Jump Point Search er spesielt utviklet for åtte-veis gridbasert kartrepresentasjon, så vi vil bruke det. Også, i vaniljeformen støtter den ikke vektede kart. (I siste avsnitt diskuterer jeg en mulig måte å rette opp på dette.)
Nå har vi en verdensrepresentasjon La oss ta en rask titt på implementering av A *. Det er en vektet grafesøkalgoritme som bruker heuristikk (lite "hint") av hvordan man best søker området fra startknutepunktet til sluttknutepunktet.
Jeg anbefaler at du sjekker ut denne visualiseringen av patfinding-algoritmer:
PathFinding.js - visuell. Å spille med det kan øke din intuisjon av hva algoritmen egentlig gjør - pluss det er morsomt!
For pathfinding ved hjelp av A * i rektangulære nett, gjør vi følgende:
1. Finn knutepunkt nærmest posisjonen din og erklære startnoden og sett den på den åpne listen. 2. Mens det er noder i den åpne listen: 3. Velg noden fra den åpne listen som har den minste F-poengsummen. Sett det på den lukkede listen (du vil ikke vurdere det igjen). 4. For hver nabo (tilstøtende celle) som ikke er i den lukkede listen: 5. Sett foreldre til nåværende knutepunkt. 6. Beregn G-poengsum (avstand fra startknutepunkt til denne naboen) og legg den til den åpne listen 7. Beregn F-poeng ved å legge heuristikk til G-verdien.Relaterte innlegg
Heuristikk er i utgangspunktet gjetning ved sjansen for at noden blir evaluert vil føre til målet. Heuristikk kan gjøre en stor forskjell i effektiviteten av patfinding algoritmer som de pleier å begrense antall noder som må besøkes. Vi skal bruke Manhattan avstand for våre formål (som betyr at noder nærmere målet vil få et mindre antall):
privat funksjon manhattanDistance (start: Node, end: Node): int return Math.abs (end.x - start.x) + Math.abs (end.y - start.y);
Dette er mer eller mindre det. Vi stopper algoritmen når vi finner målkoden, og sporer deretter tilbake med foreldringsvariabel for node for å konstruere banen.
Søk algoritmer kan også brukes til andre ting. A * er en generell vektet grafsøkalgoritme, og kan brukes på en slik graf. Dette kan dekke andre felt i AI, for eksempel å finne de optimale trinnene for å oppnå visse mål: Kast en bombe eller løp for ly og prøv å snike seg bak en fiende?
I spillutvikling må vi gjøre ting fort, når vi oppdaterer spillene våre med 60 bilder per sekund hvert millisekund teller. Selv om A * virker rimelig bra for enkelte bruksområder, finnes det behov for å gjøre det raskere eller bruke mindre minne.
Å velge representasjonen er det første som vil påvirke pathfinding-ytelsen og ditt valg av patfinding-algoritme. Størrelsen på grafen som blir søkt vil ha en stor sammenheng med hvordan din opplæring utfører (som er fornuftig, det er lettere å finne veien i rommet ditt enn i en storby).
Da vil du vurdere høyere nivåoptimaliseringer, som vanligvis involverer gruppering av data til mindre regioner, og deretter søker de samtidig som du raffinerer baner i reiste mindre regioner. Hvis du for eksempel vil gå til en restaurant i en nærliggende by, vurderer du først hvordan du kommer fra byen til den ene, og når du er i den byen begrenser du din søking til området der restauranten ligger , ignorerer resten. Dette vil inkludere ting som sump, døduttak og HPA *.
På laveste nivå må du søke. Du valgte datarepresentasjon og mulige abstraksjoner, og deretter plugger du dem i en algoritme som vil plukke ut noder, reise her og der etter å søke etter målet. Disse algoritmene er vanligvis basert på A * søkealgoritmen med mulige modifikasjoner. I enklere tilfeller kan du komme unna med å bruke rett A * som gir deg enkelheten. Jeg har gitt en gridbasert implementering i kildenedlastingen.
Siden denne opplæringen handler om å implementere Jump Point Search, vil veivisjonsgrafen bli representert med et rutenett. Og det må spesifikt være et åtte-veis rutenett siden algoritmen bruker den direkte.
Hva Jump Point Search egentlig gjør er å eliminere mange mellomliggende noder i visse slags nettkombinasjoner. Den hopper over en mengde av disse du vil legge til i åpen liste og lukket liste, samt andre beregninger, til fordel for å gjøre litt mer behandling når du velger neste knutepunkt.
Som med A * velger vi fra den åpne scenen noden med lavest F-poengsum. Men det er her ting begynner å bli interessante. I stedet for å plukke tilstøtende noder vil vi ringe denne funksjonen for å gjøre det for oss:
funksjon identifySuccessors (nåværende: Node, start: Node, end: Node): Vector.var etterfølgere: Vector. = Ny Vector. (); Var naboer: Vector. = nodeNeighbours (nåværende); for hver (var nabo: Node i naboer) // Retning fra nåværende node til nabo: var dX: int = klemme (nabo.x - nåværende.x, -1, 1); var dY: int = klemme (nabo.y - nåværende.y, -1, 1); // Prøv å finne en node for å hoppe til: var jumpPoint: Node = jump (current.x, current.y, dX, dY, start, end); // Hvis funnet, legg det til i listen: hvis (jumpPoint) successors.push (jumpPoint); returnere etterfølgere;
Hva dette gjør er å eliminere noder som ikke er interessante for vår bane. For dette bruker vi retningen fra foreldre som hovedretningslinjene. Her er eksempler på beskjæring av noder som vi vil ignorere for horisontale og vertikale retninger:
Eksempel på en horisontal beskjæringssituasjon.
I kode dette vil ende opp som en serie av hvis uttalelser som kontrollerer disse situasjonene. Du kan se eksemplet her, og beskriver det riktige tilfellet fra bildet:
Hvis (directionY == 0) hvis (! _world.isBlocked (current.x + directionX, current.y)) hvis (_world.isBlocked (current.x, current.y + 1)) // opprett en node med den nye posisjonen neighbours.push (Node.pooledNode (current.x + directionX, current.y + 1));
Etter at vi har valgt naboen, prøver vi å finne et hopppunkt, som er en knutepunkt som kan nås fra nåværende, men ikke nødvendigvis bare på en enkelt måte. For å si det mer formelt, hva JPS gjør er å eliminere symmetri mellom stier - hver har en annen permutasjon av samme trekk:
Så for store åpne områder kan vi få store gevinster. Slik fungerer hoppemetoden:
funksjonshopp (cX: int, cY: int, dX: int, dY: int, start: Node, slutt: Node): Node // cX, cY - Strømnøkkelposisjon, dX, dY - Retning // Posisjon av ny nod vi skal vurdere: var nextX: int = cX + dX; var neste: int = cY + dY; // Hvis det er blokkert, kan vi ikke hoppe her hvis (_world.isBlocked (nextX, nextY)) returneres null; // Hvis node er målet returnerer det hvis (nextX == end.x && nextY == end.y) returnerer ny knutepunkt (nextX, nextY); // Diagonal tilfelle hvis (dX! = 0 && dY! = 0) hvis (/ * ... Diagonal tvunget nabokontroll ... * /) return Node.pooledNode (nextX, nextY); // Kontroller horisontale og vertikale retninger for tvangs naboer // Dette er et spesielt tilfelle for diagonal retning hvis (hoppe (nesteX, neste, dX, 0, start, slutt)! = Null || hoppe (nextX, nextY, 0 , dY, start, slutt)! = null) return Node.pooledNode (nextX, nextY); annet // Horisontalt tilfelle hvis (dX! = 0) hvis (/ * ... Horisontal tvunget nabokontroll ... * /) return Node.pooledNode (nextX, nextY); /// Vertikal sak ellers hvis (/ * ... Vertikal tvunget nabokontroll ... * /) return Node.pooledNode (nextX, nextY); /// Hvis tvungen nabo ikke ble funnet, prøv neste hoppepunkt retur hoppe (nextX, nextY, dX, dY, start, end);
Jeg har fjernet tvunget nabo sjekker fra if-setningene som de er ganske store. De består i utgangspunktet av kontrollene som ligner på når vi først valgte naboer for en ny knute (mange kontroller for å se om cellene er blokkert). De tjener formålet med å oppdage når vi har lov til å ha våre antagelser om symmetri.
Den diagonale saken er spesiell, og vi må ikke bare se på tvungne naboer i diagonale retninger, men også i horisontale og vertikale retninger, og hvis noen av dem feiler, må vi sette en tvungen knutepunkt som et hopppunkt. Vi må også vurdere et spesielt tilfelle av målkoden, der hoppemetoden avsluttes.
Hver gang vi ikke finner en søkekode, kaller vi hoppefunksjonen rekursivt i den angitte retningen. I demonstrasjonen har jeg faktisk rullet opp dette rekursive samtalen siden dette vil bli kalt mye. (I testingen min forbedret denne ytelsen med en faktor på to.)
Dette er hva JPS gjør; Det endelige resultatet er nye noder for A * for å sjekke og vi fortsetter med algoritmen. Når målkoden er funnet, rekonstruerer vi banen og returnerer den.
JPS kan hoppe over mange noder når du søker, noe som kan gi gode hastighetsforbedringer (i prosjektet er det rundt 30x over A *), men det kommer med en kostnad.
Det fungerer best på et ensartet rutenett, men kan gjøres for å jobbe med ikke-uniformer ved hjelp av ekstra justering, markering av naboer som tvunget der det er en overgang til en knutepunkt med forskjellige kostnader (best å bruke diskrete kostnader).
I et spill jeg jobber med, er rutenett uniformer bortsett fra veier, som koster mye mindre enn å gå på vanlig terreng. (Det ser mye bedre ut når karakteren respekterer det.) Til slutt har jeg løst dette ved å forutse noen verdier av veiposisjoner. Når opplæring er initiert, søker algoritmen mulige nærmeste poeng til banen fra start- og målnoder, og søker deretter på en spesiell høytegradsgraf på veier (som er forhåndsdefinert), og deretter bruker den JPS til å søke terrengområder.
Et raskt notat om feilsøking. Feilsøking av slike algoritmer kan være svært vanskelig, og det er nesten sikkert at den første implementeringen vil ha noe vanskelig å finne feil. Du kan gjøre deg selv en tjeneste og bygge en slags visualisering funksjonelt og tegne det som skjer når algoritmen kjører.
Hvis du får en feil, bør du redusere domenet (gridstørrelse) til det minste som lar deg gjengi problemet ditt og testen derfra. Som du sikkert kan gjette, jobbet min første implementering av JPS straks!
Accentsconagua