I et hvilket som helst 2D-spill må du vite hvilken rekkefølge du skal tegne dine sprites inn. Du trekker vanligvis fra baksiden av scenen til forsiden, med de tidligere objektene dekket av de senere. Dette er standardmalerens algoritme som brukes til å representere dybde på et lerret (digitalt eller annet).
Av Zapyon - eget arbeid, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14256921
Den enkleste måten å holde styr på dette er å sette alle objektene dine inn i et stort utvalg, sortert etter deres dybde. Så i den ovennevnte scenen, ville ditt utvalg se ut som: [Mountain, Ground, Tree1, Tree2, Tree3, ...]
Problemet med en enkelt stor array
Problemet med en sentral visningsliste er at det ikke er noen enkel måte å finne ut hvilke objekter som er på skjermen når som helst. For å gjøre det, må du gå gjennom hele oppsettet og sjekke hvert enkelt objekt. Dette blir for det meste et problem hvis du har en stor spillverden der mange objekter eksisterer utenfor skjermen og ikke skal gjengis eller oppdateres.
En romlig hash er en måte å lagre dine gjenstander for å unngå dette problemet. Den ryddige tingen om å bruke en hash, det tar alltid en konstant tid å finne ut hvilke objekter som er på skjermen, uansett hvor stor spillverdenen kan være!
Nå vil de fleste spillmotorer ikke la deg spille rundt med hvordan de strukturerer sine objekter internt, men hvis du programmerer i et miljø der du har kontroll over tegneanropene (for eksempel din egen OpenGL-motor, er det et rent JavaScript spill, eller flere åpne rammer som LØVE), kan dette være noe verdt å implementere.
Alternativet: Romlige Hashes
En romlig hash er bare en hashbord hvor hver nøkkel er en 2D-koordinat og verdien er en liste over spillobjekter i dette området.
Tenk deg at verden er delt inn i et rutenett slik at hvert objekt tilhører minst en celle. Slik ser du noe på plass (420 600) hvis du hadde implementert dette i JavaScript:
var X, Y = 420.600; // Snap X og Y til rutenettet X = Math.round (X / CELL_SIZE) * CELL_SIZE; Y = Math.round (Y / CELL_SIZE) * CELL_SIZE; // Nå kontroller hvilke elementer som er i denne posisjonen spatialHash [X + "," + Y] // dette er en liste over objekter i den cellen
Det er så enkelt! Du kan umiddelbart vite hva som er i den posisjonen. Nøkkelen er en strengkonsentrasjon av X- og Y-koordinatene, men det gjør det ikke ha å være en streng, og trenger heller ikke et komma i midten; det må bare være unikt for hvert par av X og Y.
For å se hvorfor dette er så praktisk, bør du vurdere hvordan du vil få objektene i denne posisjonen ved hjelp av ett stort utvalg:
var X = 420; var Y = 600; for (var i = 0; i
Vi sjekker hvert enkelt objekt, selv om de fleste er veldig langt unna til å begynne med! Dette kan i stor grad kreme ytelsen din hvis du gjør mange oppslag som dette og ditt gameObjects array er stor.
Et konkret eksempel
Hvis du ennå ikke er overbevist om hvor nyttig dette kan være, er det en demonstrasjon skrevet i ren JavaScript, der jeg prøver å gjengi en million objekter i spillverdenen. I begge tilfeller er bare gjenstandene på skjermen faktisk gjengitt.
Klikk for å se live-demoen som kjører!
Og den levende romlige hashversjonen.
Enkelt array-versjonen er smertelig sakte. Selv om du lagrer hvilke elementer som er på skjermen, slik at du ikke trenger å sjekke hver ramme, må du fortsatt sjekke hele arrayet igjen når kameraet beveger seg, noe som fører til alvorlig choppiness.
Bare å endre måten vi lagrer våre spillobjekter på, kan gjøre hele forskjellen mellom en jevn opplevelse og et spill som ikke kan spilles av.
Implementere et romlig Hash
En romlig hash burde være veldig enkel å implementere på hvilket som helst språk (faktisk fra det første eksemplet til det andre over tok bare en ekstra 30 linjer med kode!)
Det er fire trinn for å implementere dette som gjengisystemet ditt:
Sett opp hashbordet.
Legg til og fjern objekter i hash.
Samle gjenstander i et gitt område.
Sorter objekter etter dybde før du gjengir dem.
Du kan se en funksjonell implementering i JavaScript på GitHub som referanse.
1. Sett opp Hash-tabellen
De fleste språk har en slags innebygd hashbord / kart. Vår romlige hash er bare et standard hashbord. I JavaScript kan du bare erklære en med:
var spatialHash = ; var CELL_SIZE = 60;
Den eneste andre tingen å nevne her er at du har litt spillerom med å plukke cellestørrelsen. Generelt har cellene dine dobbelt så stor som det gjennomsnittlige objektet ditt som virker bra. Hvis cellene dine er for store, vil du trekke inn for mange gjenstander med hvert oppslag. Hvis de er for små, må du sjekke flere celler for å dekke området du vil ha.
2. Legg til og fjern objekter i Hash
Hvis du legger til et objekt på hash, er det bare å snakke det til en celle, og opprette celleoppsettet hvis det ikke eksisterer, og legge til det i det aktuelle feltet. Her er min JavaScript-versjon:
spatialHash.add = funksjon (obj) var X = Math.round (obj.x / CELL_SIZE) * CELL_SIZE; var Y = Math.round (obj.y / CELL_SIZE) * CELL_SIZE; var nøkkel = X + "," + Y; hvis (spatialHash [nøkkel] == undefined) spatialHash [key] = [] spatialHash [nøkkel] .push (obj)
Det er en advarsel, men: Hva om objektet ditt spenner over flere celler, eller er for stort til å passe i en celle?
Løsningen er bare å legge den til alle cellene som det berører. Dette garanterer at hvis noe av objektet er i sikte, blir det gjengitt. (Selvfølgelig må du også sørge for at du ikke gjengir disse objektene flere ganger.)
Jeg har ikke implementert en fjernfunksjon i mitt eksempel, men å fjerne et objekt er bare et spørsmål om å ta det ut av arrayet (ene) det er en del av. For å gjøre dette enklere kan du få hvert objekt til å referere til hvilke celler den tilhører.
3. Samle objekter i et gitt område
Nå er kjernen i denne teknikken: gitt et område på skjermen, vil du kunne få alle gjenstandene der inne.
Alt du trenger å gjøre her, er å begynne å gå gjennom alle cellene basert på hvor kameraet ditt er i spillverdenen, og samle alle underlister sammen til en rekke for å gjengi. Her er den relevante JavaScript-koden:
var padding = 100; // Padding å hente ekstra celler rundt kantene, slik at spilleren ikke ser objekter "pop" til eksistens. var startX = -camX - polstring; var startY = -camY - polstring; var endX = -camX + canvas.width + polstring; var endy = -camY + canvas.height + padding; var onScreen = [] for (var X = startX; X < endX; X += CELL_SIZE) for(var Y = startY; Y < endY; Y += CELL_SIZE) var sublist = spatialHash.getList(X,Y) if(sublist != undefined) onScreen = onScreen.concat(sublist)
4. Sorter objekter etter dybde før du gjengir dem
Du har kanskje innsett nå at det å gi opp på den store displaylisten ideen, betyr også at du gir opp den praktiske dybdsorteringen. Vi tar tak i gjenstander fra vårt rutenett basert på deres plassering, men arrayet vi får er ikke sortert på noen måte.
Som et siste skritt før gjengivelse må vi sortere vårt utvalg basert på noen nøkkel. Jeg ga hvert objekt en dybdeverdi, og så kan jeg gjøre det:
onScreen.sort (funksjon (a, b) return a.depth> b.depth)
Før du endelig gjengir alt:
for (var i = 0; i
Dette er en av ulempene ved denne metoden, at du må sortere hva som er på skjermen hver ramme. Du kan alltid fremskynde dette ved å sørge for at alle underlister er sortert, slik at du kan fusjonere dem mens du samtykker i å opprettholde bestillingen.
Det er det! Du bør nå ha et (forhåpentligvis mye raskere) arbeidende gjengisystem!
Andre bruksområder og tips
Dette kan være en veldig nyttig teknikk, men som jeg sa i innledningen, kan du bare gjøre dette i en spillmotor eller et rammeverk som gir deg kontroll over tegneanropene. Likevel er det ting du kan bruke romlig hash for i tillegg til gjengivelse. Faktisk er de mer vant til å øke hastigheten på kollisjonsdeteksjon (du kan hoppe over eventuelle kollisjonskontroller for objekter du kjenner langt unna eller ikke er i samme celle).
En annen teknikk som ligner romlig hash, men litt mer komplisert, bruker en quadtree. Mens en romlig hash bare er et flatt grid, er en quadtree mer av en hierarkisk struktur, så du trenger ikke å bekymre deg for cellestørrelse, og du kan raskere få alle objektene i et gitt område uten å måtte sjekke hver eneste liten celle.
Generelt bør du huske på at en romlig struktur ikke alltid vil være den beste løsningen. Det er ideelt for et spill som har:
en stor verden med mange gjenstander
relativt få gjenstander på skjermen i forhold til verdensstørrelsen
for det meste statiske gjenstander
Hvis alle objektene dine beveger seg hele tiden, må du fortsette å fjerne og legge dem til forskjellige celler, noe som kan medføre en betydelig ytelsesstraff. Det var et ideelt gjengisystem for et spill som Move or Die (nesten dobling av fps) siden nivåene besto av mange statiske objekter, og tegnene var de eneste tingene som flyttet.
Forhåpentligvis har denne opplæringen gitt deg en ide om hvordan strukturering av data romlig kan være en enkel måte å øke ytelsen på, og hvordan gjengisystemet ditt ikke alltid må være en enkelt lineær liste!
Share
Av Zapyon - eget arbeid, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14256921
Accentsconagua
