Reproiectați lista dvs. de afișări cu spații hașă

În orice joc 2D, trebuie să știți ce ordine să vă atrageți spritele. De obicei, trageți din spatele scenei spre față, obiectele anterioare fiind acoperite de cele ulterioare. Acesta este algoritmul standard al pictorului folosit pentru a reprezenta adâncimea pe o pânză (digitală sau altfel).

De Zapyon - Muncă proprie, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14256921

Cea mai simplă modalitate de a urmări acest lucru este punerea tuturor obiectelor într-o gamă largă, sortată după adâncimea lor. Deci, în scena de mai sus, array ar arata cam ca: [Mountain, Ground, Tree1, Tree2, Tree3, ...]

Problema cu o singură matrice mare

Problema cu o listă centrală de afișare este că nu există nicio modalitate ușoară de a afla care obiecte sunt pe ecran în orice moment dat. Pentru a face acest lucru, trebuie să bifați întreaga matrice și să verificați fiecare obiect. Acest lucru devine o problemă mai ales dacă aveți o lume a jocurilor mari unde multe obiecte există în afara ecranului și nu ar trebui să fie redate sau actualizate.

Un hash spațial este o modalitate de stocare a obiectelor dvs. pentru a evita această problemă. Lucrul obișnuit cu privire la utilizarea unui hash este întotdeauna un timp constant pentru a afla care obiecte sunt pe ecran, indiferent de cât de mare ar putea fi lumea jocurilor!

Acum majoritatea motoarelor de joc nu vă vor lăsa să vă jucați cu modul în care își structurează obiectele pe plan intern, dar dacă programați într-un mediu în care vă aflați în controlul apelurilor de remiză (cum ar fi propriul motor OpenGL, un JavaScript pur joc, sau mai multe cadre deschise, cum ar fi LÖVE), acest lucru ar putea fi un lucru care merită implementat.

Alternativa: Hashes-ul spațial

Un hash spațial este doar a tabelul hash unde fiecare cheie este o coordonată 2D iar valoarea este o listă de obiecte de joc din acea zonă.

Imaginați-vă că lumea voastră este împărțită într-o rețea astfel încât fiecare obiect să aparțină cel puțin unei celule. Iată cum ați căuta ceva în poziție (420.600) dacă ați implementat acest lucru în JavaScript:

var X, Y = 420,600; // Snap X și Y în grila X = Math.round (X / CELL_SIZE) * CELL_SIZE; Y = Matematică (Y / CELL_SIZE) * CELL_SIZE; // Acum verificați ce elemente sunt în această poziție spatialHash [X + "," + Y] // aceasta este o listă de obiecte din acea celulă

Este atât de ușor! Puteți ști imediat ce este în această poziție. Cheia este o concatenare string a coordonatelor X și Y, dar nu este avea a fi un șir și nu are nevoie de o virgulă în mijloc; trebuie doar să fie unic pentru fiecare pereche de X și Y.

Pentru a vedea de ce este atât de convenabil, gândiți-vă cum veți obține obiectele de la această poziție folosind o gamă largă:

var X = 420; var Y = 600; pentru (var i = 0; i
Verificăm fiecare obiect, chiar dacă majoritatea sunt foarte departe pentru a începe! Acest lucru vă poate afecta foarte mult performanța dacă efectuați multe căutări ca acesta și dvs. gameObjects matricea este imensă.
Un exemplu de beton
Dacă nu sunteți încă convins de cât de util poate fi acest lucru, iată un demo scris în limbajul JavaScript, unde încerc să fac un milion de obiecte în lumea jocurilor. În ambele cazuri, numai obiectele de pe ecran sunt efectiv redate.
Faceți clic pentru a vedea demo-ul live care rulează!
Și versiunea hash spațială spațială.
Versiunea cu o singură matrice este dureros de lentă. Chiar dacă salvați elementele care sunt pe ecran, astfel încât nu trebuie să verificați fiecare cadru, tot trebuie să verificați din nou întreaga matrice atunci când camera se mișcă, ceea ce duce la o mișcare severă.
Modificarea modului în care stocăm obiectele jocului poate face diferența între o experiență lină și un joc care nu poate fi jucat.
Implementarea unui hash spațial
Un hash spațial ar trebui să fie foarte ușor de implementat în orice limbă (de fapt, trecerea de la primul exemplu la al doilea de mai sus a făcut doar 30 de linii de cod suplimentare!)
Există patru pași pentru a implementa acest lucru ca sistem de randare:
 
Configurați tabelul hash.
 
Adăugați și eliminați obiecte din hash.
 
Colectați obiecte în orice zonă dată.
 
Sortați obiectele în funcție de adâncime înainte de a le preda.
 
Puteți vedea o implementare funcțională în JavaScript pe GitHub ca referință.
1. Configurați tabelul Hash
Cele mai multe limbi au un fel de tabel / hartă built-in. Hash-ul nostru spațial este doar o tabelă hash standard. În JavaScript poți să declare unul cu:
var spatialHash = ; var CELL_SIZE = 60;
Singurul lucru pe care trebuie să-l menționăm este că aveți o anumită libertate în alegerea mărimii celulelor. În general, având celulele dvs. de două ori mai mari decât obiectul dvs. obișnuit, pare să funcționeze bine. Dacă celulele tale sunt prea mari, atunci vei trage prea multe obiecte cu fiecare căutare. Dacă sunt prea mici, va trebui să verificați mai multe celule pentru a acoperi zona pe care o doriți. 
2. Adăugați și eliminați obiecte în Hash
Adăugarea unui obiect la hash este doar o chestiune care o creează într-o celulă, creând matricea celulelor dacă nu există și adăugând-o la acea matrice. Iată versiunea JavaScript:
spațialHash.add = funcție (obj) var X = Math.round (obj.x / CELL_SIZE) * CELL_SIZE; var Y = Math.round (volum / CELL_SIZE) * CELL_SIZE; var cheie = X + "," + Y; dacă [spatialHash [key] == undefined) spatialHash [key] = [] spatialHash [cheie] .push (obj)
Există însă o avertizare: Ce se întâmplă dacă obiectul dvs. cuprinde mai multe celule sau este prea mare pentru a se potrivi într-o singură celulă?
Soluția este doar să o adăugăm toate celulele pe care le atinge. Acest lucru garantează că dacă o parte a obiectului este în vedere, atunci el va fi redat. (Desigur, atunci trebuie să vă asigurați că nu redați aceste obiecte de mai multe ori.)
Nu am implementat o funcție de eliminare în exemplul meu, dar eliminarea unui obiect este doar o chestiune de scoatere din matricea (elementele) din care face parte. Pentru a face acest lucru mai simplu, puteți avea fiecare obiect să păstreze o referință la care celule aparține.
3. Colectați obiecte în orice zonă dată
Acum, aici este nucleul acestei tehnici: datând o zonă pe ecran, doriți să puteți obține toate obiectele de acolo.
Tot ce trebuie să faceți aici este să începeți să treceți prin toate celulele în funcție de locul în care aparatul dvs. foto este în lumea jocurilor și să colectați toate sub-listele împreună într-o singură matrice pentru a face. Iată fragmentul JavaScript relevant:
var padding = 100; // Cusătură pentru a prinde celule suplimentare în jurul marginilor, astfel încât jucătorul să nu vadă obiecte "pop" în existență. var startX = -camX-padding; var startY = -camY-padding; var endX = -camX + canvas.width + padding; var endY = -camY + canvas.height + padding; var onScreen = [] pentru (var X = startX; < 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. Sortați obiectele în funcție de adâncime înainte de a le executa
S-ar fi putut realiza până acum că renunțarea la ideea listei mari de afișare înseamnă, de asemenea, că renunțați la sortarea convenabilă a adâncilor. Obținem obiecte din grila noastră pe baza locației lor, dar matricea pe care o primim nu este sortată în nici un fel. 
Ca un pas final înainte de redare, trebuie să sortați matricea pe baza unor chei. Am dat fiecărui obiect o valoare de adâncime și așa pot să fac:
onScreen.sort (funcția (a, b) returnează a.depth> b.depth) 
Înainte de a face totul în cele din urmă:
pentru (var i = 0; i
Acesta este unul din dezavantajele acestei metode, că trebuie să sortați ceea ce este pe ecran în fiecare cadru. Puteți accelera întotdeauna acest lucru, asigurându-vă că toate sub-listele dvs. sunt sortate, astfel încât să le puteți îmbina în timp ce vă conectați pentru a menține comanda.
Asta e! Ar trebui să aveți acum un sistem de randare (sperăm mult mai rapid)!
Alte utilizări și sfaturi
Aceasta poate fi o tehnică foarte utilă, dar așa cum am spus în introducere, puteți face acest lucru doar într-un motor de joc sau un cadru care vă oferă controlul asupra apelurilor de remiză. Totuși, există lucruri pe care le puteți utiliza pentru hashes spațial, pe lângă rendering. De fapt, acestea sunt folosite mai frecvent pentru a accelera detectarea coliziunilor (puteți sări peste orice verificări de coliziune pentru obiectele pe care le cunoașteți sunt departe sau nu se află în aceeași celulă).
O altă tehnică asemănătoare cu hashes-urile spațiale, dar puțin mai complicată, utilizează un quadtree. Întrucât un hash spațial este doar o rețea plană, un quadtree este mai mult o structură ierarhică, deci nu trebuie să vă faceți griji cu privire la dimensiunea celulei și puteți obține mai repede toate obiectele dintr-o anumită zonă fără a fi nevoie să verificați fiecare mic celulă.
În general, trebuie să rețineți că o structură spațială nu va fi întotdeauna cea mai bună soluție. Este ideal pentru un joc care are:
 
o lume mare cu multe obiecte
 
relativ puține obiecte pe ecran comparativ cu dimensiunea mondială
 
cele mai multe obiecte statice
 
Dacă toate obiectele dvs. se mișcă în permanență, va trebui să le eliminați și să le adăugați în diferite celule, ceea ce ar putea genera o penalizare semnificativă a performanței. A fost un sistem ideal de redare pentru un joc precum Move or Die (aproape dublând fps-urile), deoarece nivelele erau alcătuite dintr-o mulțime de obiecte statice, iar personajele erau singurele lucruri care s-au mutat.
Sperăm că acest tutorial ți-a dat o idee despre modul în care structurarea datelor din spațiu poate fi o modalitate ușoară de a crește performanța și cum nu trebuie întotdeauna sistemul dvs. de randare să fie o singură listă liniară!



		
			
	   
	




Dezvoltarea jocurilor