Ridisegna la tua lista di visualizzazione con hash spaziali

In qualsiasi gioco 2D, devi sapere in che ordine disegnare i tuoi sprite. Solitamente disegni dal retro della scena in avanti, con gli oggetti precedenti coperti da quelli successivi. Questo è l'Algoritmo standard del pittore usato per rappresentare la profondità su una tela (digitale o altro).

Di Zapyon - Opera personale, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14256921

Il modo più semplice per tenerne traccia consiste nel mettere tutti gli oggetti in un unico grande array, ordinati in base alla loro profondità. Quindi, nella scena sopra, il tuo array sarà simile a qualcosa: [Montagna, Terra, Albero1, Albero2, Albero3, ...]

Il problema con una singola grande matrice

Il problema con una lista di visualizzazione centrale è che non esiste un modo semplice per scoprire quali oggetti sono sullo schermo in un dato momento. Per fare ciò, è necessario scorrere l'intero array e controllare ogni singolo oggetto. Questo diventa per lo più un problema se si dispone di un vasto mondo di giochi in cui molti oggetti esistono al di fuori dello schermo e non devono essere renderizzati o aggiornati.

Un hash spaziale è un modo di memorizzare gli oggetti per evitare questo problema. La cosa bella dell'utilizzo di un hash è che richiede sempre un tempo costante per capire quali oggetti sono sullo schermo, indipendentemente da quanto enorme possa essere il mondo di gioco!

Ora la maggior parte dei motori di gioco non ti lascia effettivamente giocare con il modo in cui strutturano i loro oggetti internamente, ma se stai programmando in un ambiente in cui hai il controllo delle chiamate di estrazione (come il tuo motore OpenGL, un puro JavaScript gioco, o più framework aperti come LÖVE), questo potrebbe essere qualcosa che vale la pena implementare.

L'alternativa: hash spaziali

Un hash spaziale è solo un tabella hash in cui ogni chiave è una coordinata 2D e il valore è un elenco di oggetti di gioco in quell'area.

Immagina che il tuo mondo sia diviso in una griglia in modo tale che ogni oggetto appartenga ad almeno una cella. Ecco come si dovrebbe cercare qualcosa in posizione (420.600) se questo fosse implementato in JavaScript:

var X, Y = 420.600; // Aggancia X e Y alla griglia X = Math.round (X / CELL_SIZE) * CELL_SIZE; Y = Math.round (Y / CELL_SIZE) * CELL_SIZE; // Ora controlla quali elementi sono in quella posizione spatialHash [X + "," + Y] // questa è una lista di oggetti in quella cella

È così facile! Puoi immediatamente sapere cosa c'è in quella posizione. La chiave è una concatenazione di stringhe delle coordinate X e Y, ma non è così avere per essere una stringa, né ha bisogno di una virgola nel mezzo; deve essere unico per ogni coppia di X e Y.

Per capire perché questo è così conveniente, considera come ottenere gli oggetti in questa posizione usando un grande array:

var X = 420; var Y = 600; per (var i = 0; i
Stiamo controllando ogni singolo oggetto, anche se molti di loro sono molto lontani per cominciare! Questo può rovinare enormemente le tue prestazioni se stai facendo molte ricerche come questa e la tua gameObjects la matrice è enorme.
Un esempio concreto
Se non sei ancora convinto di quanto possa essere utile, ecco una demo scritta in puro codice JavaScript dove cerco di rendere un milione di oggetti nel mondo di gioco. In entrambi i casi, solo gli oggetti sullo schermo sono effettivamente renderizzati.
Clicca per vedere la demo live in esecuzione!
E la versione hash spaziale dal vivo.
La versione a singolo array è dolorosamente lenta. Anche se si salvano gli elementi sullo schermo in modo da non dover controllare tutti i fotogrammi, è comunque necessario controllare di nuovo l'intero array quando la telecamera si sposta, causando un forte choppiness.
Cambiare semplicemente il modo in cui immagazziniamo i nostri oggetti di gioco può fare la differenza tra un'esperienza fluida e un gioco ingiocabile.
Implementazione di un hash spaziale
Un hash spaziale dovrebbe essere veramente facile da implementare in qualsiasi lingua (infatti, passando dal primo esempio al secondo in alto sono state necessarie solo 30 righe di codice aggiuntive!)
Ci sono quattro passaggi per implementarlo come sistema di rendering:
 
Imposta la tabella hash.
 
Aggiungi e rimuovi oggetti nell'hash.
 
Raccogli oggetti in una determinata area.
 
Ordina gli oggetti per profondità prima di renderli.
 
Puoi vedere un'implementazione funzionale in JavaScript su GitHub come riferimento.
1. Impostare la tabella hash
La maggior parte delle lingue ha una sorta di tabella hash / mappa incorporata. Il nostro hash spaziale è solo una tabella hash standard. In JavaScript puoi dichiararne uno con:
var spatialHash = ; var CELL_SIZE = 60;
L'unica altra cosa da dire qui è che hai un margine di manovra con la scelta della dimensione della cella. In generale, avere le tue celle due volte più grandi di quanto il tuo oggetto medio sembra funzionare bene. Se le tue celle sono troppo grandi, dovrai inserire troppi oggetti con ogni ricerca. Se sono troppo piccoli, dovrai controllare più celle per coprire l'area che desideri. 
2. Aggiungi e rimuovi oggetti nell'Hash
L'aggiunta di un oggetto all'hash è solo una questione che si collega a una cella, creando l'array di celle, se non esiste, e aggiungendolo a quell'array. Ecco la mia versione JavaScript:
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 key = X + "," + Y; if (spatialHash [key] == undefined) spatialHash [key] = [] spatialHash [key] .push (obj)
C'è un avvertimento, però: cosa succede se il tuo oggetto si estende su più celle o è troppo grande per stare in una cella?
La soluzione è solo per aggiungerla tutti le cellule che tocca. Questo garantisce che se una qualsiasi parte dell'oggetto è in vista, verrà renderizzata. (Naturalmente, devi anche assicurarti di non eseguire il rendering di questi oggetti più volte.)
Nel mio esempio non ho implementato una funzione di rimozione, ma rimuovere un oggetto è solo questione di portarlo fuori dalla (e) matrice (e) di cui fa parte. Per semplificare questo, puoi fare in modo che ogni oggetto mantenga un riferimento a quali celle appartiene.
3. Raccogli oggetti in qualsiasi area
Ora ecco il nocciolo di questa tecnica: data un'area sullo schermo, vuoi essere in grado di ottenere tutti gli oggetti lì dentro.
Tutto quello che devi fare qui è iniziare a esaminare tutte le celle in base a dove la tua videocamera si trova nel mondo di gioco, e raccogliere tutti i sottoliste in un unico array per renderizzare. Ecco lo snippet di codice JavaScript pertinente:
var padding = 100; // Riempimento per afferrare le celle in più attorno ai bordi in modo che il giocatore non veda gli oggetti "pop" nell'esistenza. var startX = -camX - padding; var startY = -camY - padding; var endX = -camX + canvas.width + padding; var endY = -camY + canvas.height + padding; var onScreen = [] per (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. Ordina gli oggetti per profondità prima di renderli
Potresti aver capito ormai che rinunciare alla grande idea della lista di display significa anche rinunciare al comodo ordinamento in profondità. Prendiamo gli oggetti dalla nostra griglia in base alla loro posizione, ma l'array che otteniamo non è ordinato in alcun modo. 
Come passaggio finale prima del rendering, dobbiamo ordinare il nostro array in base a qualche chiave. Ho dato ad ogni oggetto un valore di profondità, e così posso fare:
onScreen.sort (funzione (a, b) return a.depth> b.depth) 
Prima di rendere finalmente tutto:
per (var i = 0; i
Questo è uno degli svantaggi di questo metodo, che devi ordinare cosa c'è sullo schermo ogni fotogramma. Puoi sempre accelerare assicurandoti che tutti i tuoi sotto-elenchi siano ordinati, quindi puoi unirli mentre ti concateni per mantenere l'ordine.
Questo è tutto! Ora dovresti avere un sistema di rendering (si spera molto più veloce) funzionante!
Altri usi e suggerimenti
Questa può essere una tecnica davvero utile, ma come ho detto nell'introduzione, puoi farlo solo in un motore di gioco o in un framework che ti dia il controllo sulle chiamate di estrazione. Tuttavia, ci sono cose che puoi usare gli hash spaziali oltre al rendering. Infatti, sono più comunemente usati per accelerare il rilevamento delle collisioni (puoi saltare qualsiasi controllo di collisione per oggetti che conosci sono lontani o non sono nella stessa cella).
Un'altra tecnica simile agli hash spaziali, ma un po 'più complicata, sta usando un quadrifoglio. Mentre un hash spaziale è solo una griglia piatta, un quadruplo è più di una struttura gerarchica, quindi non devi preoccuparti delle dimensioni della cella, e puoi ottenere più velocemente tutti gli oggetti in una determinata area senza dover controllare ogni piccolo cellula.
In generale, dovresti tenere presente che una struttura spaziale non sarà sempre la soluzione migliore. È l'ideale per un gioco che ha:
 
un grande mondo con molti oggetti
 
relativamente pochi oggetti sullo schermo rispetto alla dimensione del mondo
 
per lo più oggetti statici
 
Se tutti i tuoi oggetti si muovono continuamente, dovrai continuare a rimuoverli e aggiungerli a celle diverse, il che potrebbe comportare una significativa penalizzazione delle prestazioni. Era un sistema di rendering ideale per un gioco come Move or Die (quasi il raddoppio del fps) poiché i livelli erano costituiti da un sacco di oggetti statici, ei personaggi erano le uniche cose che si muovevano.
Speriamo che questo tutorial ti abbia dato un'idea di come strutturare i dati spazialmente può essere un modo semplice per aumentare le prestazioni e come il tuo sistema di rendering non debba sempre essere un singolo elenco lineare!



		
			
	   
	




Sviluppo del gioco