Redesign din bildlista med rymdhashes

I vilket som helst 2D-spel måste du veta vilken ordning som ska rita dina sprites. Du brukar rita från baksidan av scenen till framsidan, med de föregående objekten täckta av de senare. Detta är standardmålarens algoritm som används för att representera djup på en duk (digital eller på annat sätt).

Av Zapyon - eget arbete, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14256921

Det enklaste sättet att hålla reda på det här är att sätta alla dina föremål i ett stort sortiment, sorterat efter deras djup. Så i ovanstående scen skulle din array se ut som: [Mountain, Ground, Tree1, Tree2, Tree3, ...]

Problemet med en enda stor array

Problemet med en central visningslista är att det inte finns någon enkel väg att ta reda på vilka föremål som finns på skärmen vid något tillfälle. För att göra det måste du slinga igenom hela matrisen och kontrollera varje enskilt objekt. Det här blir oftast ett problem om du har en stor spelvärld där många objekt existerar utanför skärmen och inte ska göras eller uppdateras.

En rumslig hash är ett sätt att lagra dina föremål för att undvika detta problem. Det snygga med att använda en hash är att det alltid tar en ständig tid att ta reda på vilka föremål som finns på skärmen, oavsett hur stor spelvärlden kan vara!

Nu kommer de flesta spelmotorerna inte att låta dig leka med hur de strukturerar sina föremål internt, men om du programmerar i en miljö där du har kontroll över dragningsanropen (som din egen OpenGL-motor, en ren JavaScript spel, eller fler öppna ramar som LÖVE), kan detta vara något värt att genomföra.

Alternativet: Spatial Hashes

En rumslig hash är bara en hashbord där varje nyckel är en 2D-koordinat och värdet är en lista över spelobjekt i det området.

Tänk dig att din värld är uppdelad i ett galler så att varje objekt tillhör minst en cell. Så här ser du något på plats (420.600) om du hade implementerat det i JavaScript:

var X, Y = 420,600; // Snap X och Y till rutnätet X = Math.round (X / CELL_SIZE) * CELL_SIZE; Y = Math.round (Y / CELL_SIZE) * CELL_SIZE; // Nu kolla vilka element som är i den positionen spatialHash [X + "," + Y] // det här är en lista över objekt i den cellen

Det är så enkelt! Du kan genast veta vad som är i den positionen. Nyckeln är en strängkonstruktion av X- och Y-koordinaterna, men det gör det inte ha att vara en sträng, och behöver inte komma i mitten; det måste bara vara unikt för varje par av X och Y.

För att se varför detta är så bekvämt, överväga hur du skulle få objekten i denna position med en stor grupp:

var X = 420; var Y = 600; för (var i = 0; i
Vi kontrollerar varje enskilt objekt, även om de flesta är mycket långt borta till att börja med! Detta kan väldigt förkrota din prestation om du gör många sökningar som denna och din gameObjects array är enorm.
Ett konkret exempel
Om du inte är övertygad om hur användbar det här är kan det vara, här är en demo skrivet i ren JavaScript där jag försöker göra miljon objekt i spelvärlden. I båda fallen är endast objekten på skärmen faktiskt gjorda.
Klicka för att se live demo körning!
Och den levande rumsliga hashversionen.
Singel array-versionen är smärtsamt långsam. Även om du sparar vilka element som finns på skärmen så att du inte behöver kontrollera varje bildruta, måste du fortfarande kontrollera hela matrisen när kameran rör sig, vilket leder till allvarlig choppiness.
Att bara ändra hur vi lagrar våra spelobjekt kan göra skillnaden mellan en jämn upplevelse och ett ospelbart spel.
Genomföra en rymdhash
En rumslig hash borde vara väldigt lätt att implementera på något språk (i själva verket gick det från det första exemplet till det andra ovanför endast 30 extra kod!)
Det finns fyra steg att implementera detta som ditt reningssystem:
 
Ställ in hashbordet.
 
Lägg till och ta bort objekt i hash.
 
Samla föremål i ett visst område.
 
Sortera objekt efter djup innan du gör dem.
 
Du kan se en funktionell implementering i JavaScript på GitHub som referens.
1. Ställ in Hash-tabellen
De flesta språk har någon form av inbyggd hashbord / karta. Vår rumsliga hash är bara ett vanligt hashbord. I JavaScript kan du bara deklarera en med:
var spatialHash = ; var CELL_SIZE = 60;
Den enda andra sak att nämna här är att du har lite utrymme med att välja cellstorleken. I allmänhet verkar dina celler dubbelt så stora som ditt genomsnittliga föremål fungerar bra. Om dina celler är för stora kommer du att dra in för många föremål med varje uppslag. Om de är för små måste du kolla fler celler för att täcka det område du vill ha. 
2. Lägg till och ta bort objekt i huvudet
Att lägga till ett objekt i hasen är bara en sak som knyter den till en cell, skapar cellmatrisen om den inte existerar och lägger till den i den uppsättningen. Här är min JavaScript-version:
spatialHash.add = function (obj) var X = Math.round (obj.x / CELL_SIZE) * CELL_SIZE; var Y = Math.round (obj.y / CELL_SIZE) * CELL_SIZE; var nyckel = X + "," + Y; om (spatialHash [key] == undefined) spatialHash [key] = [] spatialHash [tangent] .push (obj)
Det finns dock en försiktighet, men om ditt objekt sträcker sig över flera celler, eller är för stort för att passa i en cell?
Lösningen är bara att lägga till den Allt de celler som det rör vid. Detta garanterar att om någon del av objektet är synlig så kommer den att göras. (Naturligtvis måste du också se till att du inte gör dessa objekt flera gånger.)
Jag har inte implementerat en borttagningsfunktion i mitt exempel, men att ta bort ett objekt handlar bara om att ta bort den ur den eller de arrayer som den ingår i. För att göra detta enklare kan du få varje objekt att hålla en hänvisning till vilka celler den tillhör.
3. Samla objekt i något visst område
Nu är här kärnan i den här tekniken: Ge ett område på skärmen, du vill kunna få alla föremål in där.
Allt du behöver göra här börjar med att gå igenom alla celler baserat på var din kamera befinner sig i spelvärlden och samla alla underlistor tillsammans i en array för att göra. Här är relevant JavaScript-kod:
var padding = 100; // Padding för att ta tag i extra celler runt kanterna så att spelaren inte ser objekt "pop" till existens. var startX = -camX - vadderar; var startY = -camY - vadderar; var endX = -camX + canvas.width + padding; var ände = -camY + canvas.height + padding; var onScreen = [] för (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. Sortera objekt efter djup innan du gör dem
Du kanske har insett det nu att att ge upp på den stora bildskärmens lista innebär också att du ger upp den bekväma djupsorteringen. Vi tar tag i objekt från vårt nät baserat på deras plats, men den matris vi får sorteras inte på något sätt. 
Som ett sista steg före rendering måste vi sortera vår array baserat på en nyckel. Jag gav varje objekt ett djupvärde, och så kan jag göra:
onScreen.sort (funktion (a, b) return a.depth> b.depth) 
Innan du äntligen gör allt:
för (var i = 0; i
Detta är en av nackdelarna med denna metod, att du måste sortera vad som finns på skärmen varje ram. Du kan alltid påskynda detta genom att se till att alla dina underlistor är sorterade så att du kan sammanfoga dem medan du sammanfattar för att behålla ordern.
Det är allt! Du borde nu ha ett (förhoppningsvis mycket snabbare) fungerande reningssystem!
Andra användningar och tips
Det här kan vara en väldigt användbar teknik, men som sagt i introduktionen kan du bara göra det i en spelmotor eller ett ramverk som ger dig kontroll över röstsamtal. Fortfarande finns det saker du kan använda rumsliga hash för förutom att göra. Faktum är att de vanligtvis används för att påskynda kollisionsdetektering (du kan hoppa över alla kollisionskontroller för objekt du känner till är långt borta eller inte i samma cell).
En annan teknik som liknar spatial hashes, men lite mer komplicerad, använder en quadtree. Medan en rumslig hash bara är ett plattnät, är en quadtree mer en hierarkisk struktur, så du behöver inte oroa sig för cellstorleken och du kan snabbare få alla föremål i ett visst område utan att behöva kolla varje lilla cell.
I allmänhet bör du komma ihåg att en rumslig struktur inte alltid kommer att vara den bästa lösningen. Det är idealiskt för ett spel som har:
 
en stor värld med många föremål
 
relativt få objekt på skärmen jämfört med världsstorleken
 
mestadels statiska föremål
 
Om alla dina föremål rör sig hela tiden måste du fortsätta att ta bort och lägga till dem i olika celler, vilket kan medföra en betydande prestationsstraff. Det var ett idealiskt reningssystem för ett spel som Flytta eller Dö (nästan dubbla fps) eftersom nivåerna bestod av många statiska objekt och tecknen var de enda sakerna som rörde sig.
Förhoppningsvis har denna handledning gett dig en uppfattning om hur strukturering av data spatalt kan vara ett enkelt sätt att öka prestanda och hur ditt reningssystem inte alltid behöver vara en enda linjär lista!



		
			
	   
	




Spelutveckling