Ontwerp uw weergavelijst opnieuw met ruimtelijke uitsparingen

In elk 2D-spel moet je weten in welke volgorde je sprites moeten worden getekend. Meestal teken je vanaf de achterkant van de scène naar voren, waarbij de eerdere objecten worden bedekt door de latere. Dit is het standaard Painter's Algorithm dat wordt gebruikt om diepte op een canvas weer te geven (digitaal of anderszins).

Door Zapyon - Eigen werk, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14256921

De meest eenvoudige manier om dit bij te houden, is door al je objecten in één grote array te plaatsen, gesorteerd op hun diepte. Dus in de bovenstaande scène ziet uw array er ongeveer zo uit: [Berg, Grond, Boom 1, Boom 2, Boom 3, ...]

Het probleem met een enkele grote array

Het probleem met een centrale displaylijst is dat er geen eenvoudige manier is om erachter te komen welke objecten op een bepaald moment op het scherm worden weergegeven. Om dat te doen, moet je de hele array doorlopen en elk object controleren. Dit wordt meestal een probleem als je een grote gamewereld hebt waar veel objecten buiten het scherm bestaan ​​en niet mag worden weergegeven of bijgewerkt.

Een ruimtelijke hash is een manier om uw objecten op te slaan om dit probleem te voorkomen. Het aardige aan het gebruik van een hash is dat het altijd een constante tijd kost om erachter te komen welke objecten op het scherm staan, ongeacht hoe groot de spelwereld ook is.!

Nu laten de meeste game-engines je eigenlijk niet echt spelen met hoe ze hun objecten intern structureren, maar als je programmeert in een omgeving waar je controle hebt over de draw-calls (zoals je eigen OpenGL-engine, een pure JavaScript spel, of meer open frameworks zoals LÖVE), dit kan de moeite van het implementeren waard zijn.

Het alternatief: ruimtelijke hashes

Een ruimtelijke hash is slechts een hashtabel waarbij elke sleutel een 2D-coördinaat is en de waarde is een lijst met game-objecten in dat gebied.

Stel je voor dat je wereld is opgesplitst in een raster zodat elk object bij ten minste één cel hoort. Zo zou je iets op positie (420.600) opzoeken als je dit had geïmplementeerd in JavaScript:

var X, Y = 420.600; // Maak X en Y vast aan het raster X = Math.round (X / CELL_SIZE) * CELL_SIZE; Y = Math.round (Y / CELL_SIZE) * CELL_SIZE; // Controleer nu welke elementen in die positie zijn spaceHash [X + "," + Y] // dit is een lijst met objecten in die cel

Het is zo makkelijk! U kunt onmiddellijk weten wat zich in die positie bevindt. De sleutel is een string-aaneenschakeling van de X- en Y-coördinaten, maar dat is niet het geval hebben om een ​​touwtje te zijn, noch heeft het een komma in het midden nodig; het moet gewoon uniek zijn voor elk paar X en Y.

Om te zien waarom dit zo handig is, kunt u overwegen hoe u de objecten op deze positie zou krijgen met behulp van één grote array:

var X = 420; var Y = 600; for (var i = 0; i
We controleren elk afzonderlijk object, zelfs als de meeste van hen om te beginnen erg ver weg zijn! Dit kan je prestaties enorm verlammen als je veel lookups doet zoals deze en jouw gameObjects array is enorm.
Een concreet voorbeeld
Als je nog niet overtuigd bent van hoe nuttig dit kan zijn, is hier een demo geschreven in pure JavaScript waarin ik probeer een miljoen objecten in de gamewereld weer te geven. In beide gevallen worden alleen de objecten op het scherm daadwerkelijk weergegeven.
Klik om de live demo te zien lopen!
En de live ruimtelijke hash-versie.
De single array-versie is pijnlijk langzaam. Zelfs als u opslaat welke elementen op het scherm staan, zodat u niet elk frame hoeft te controleren, moet u de hele array opnieuw controleren wanneer de camera beweegt, wat leidt tot ernstige haperingen.
Alleen al het veranderen van de manier waarop we onze game-objecten opslaan, kan het verschil maken tussen een vloeiende ervaring en een onbespeelbaar spel.
Een ruimtelijke hash implementeren
Een ruimtelijke hash moet in elke taal heel gemakkelijk te implementeren zijn (in feite ging het van het eerste voorbeeld naar het tweede hierboven alleen om extra 30 regels code!)
Er zijn vier stappen om dit als uw weergavesysteem te implementeren:
 
Stel de hashtabel in.
 
Objecten toevoegen en verwijderen in de hash.
 
Verzamel objecten in een bepaald gebied.
 
Sorteer objecten op diepte voordat u ze rendert.
 
U kunt een functionele implementatie in JavaScript op GitHub zien als een referentie.
1. Stel de hashtabel in
De meeste talen hebben een soort ingebouwde hash-tabel / kaart. Onze ruimtelijke hasj is slechts een standaard hash-tabel. In JavaScript kunt u er gewoon een declareren met:
var spatialHash = ; var CELL_SIZE = 60;
Het enige andere ding om hier te vermelden is dat je wat speelruimte hebt met het kiezen van de celgrootte. Over het algemeen lijkt het erop dat je cellen twee keer zo groot zijn als je gemiddelde object goed lijkt te werken. Als je cellen te groot zijn, dan zul je bij elke opzoeking te veel objecten binnenhalen. Als ze te klein zijn, moet je meer cellen controleren om het gewenste gebied te bedekken. 
2. Objecten toevoegen en verwijderen in de hash
Het toevoegen van een object aan de hash is gewoon een kwestie van knippen naar een cel, het maken van de celarray als deze niet bestaat, en deze aan die array toevoegen. Hier is mijn JavaScript-versie:
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-toets = X + "," + Y; if (spatialHash [key] == undefined) spatialHash [key] = [] spatialHash [key] .push (obj)
Er is echter een voorbehoud: wat als uw object meerdere cellen beslaat of te groot is om in één cel te passen??
De oplossing is gewoon om het toe te voegen allemaal de cellen die het aanraakt. Dit garandeert dat als een deel van het object in zicht is, het zal worden gerenderd. (Natuurlijk moet u er ook voor zorgen dat u deze objecten niet meerdere keren rendert.)
Ik heb in mijn voorbeeld geen verwijderfunctie geïmplementeerd, maar het verwijderen van een object is gewoon een kwestie van het uit de array (s) halen waarvan het deel uitmaakt. Om dit eenvoudiger te maken, kunt u elk object een verwijzing laten houden naar de cellen waartoe het behoort.
3. Verzamel objecten in een bepaald gebied
Nu is hier de kern van deze techniek: gezien een gebied op het scherm, wil je alle objecten daarin kunnen krijgen.
Het enige dat u hier hoeft te doen, is om alle cellen te doorlopen op basis van waar uw camera zich in de gamewereld bevindt en verzamel alle sublijsten samen in één array om weer te geven. Hier is het relevante JavaScript-fragment:
var padding = 100; // Opvulling om extra cellen rond de randen te grijpen zodat de speler objecten niet "pop" ziet ontstaan. var startX = -camX - opvulling; var startY = -camY - opvulling; var endX = -camX + canvas.width + padding; var endY = -camY + canvas.hoogte + opvulling; var onScreen = [] voor (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. Sorteer objecten op diepte voordat ze worden weergegeven
Je hebt je misschien al gerealiseerd dat het opgeven van het grote displaylijst-idee ook betekent dat je de handige dieptesortering opgaf. We pakken objecten uit ons raster op basis van hun locatie, maar de array die we krijgen, is op geen enkele manier gesorteerd. 
Als laatste stap voor het renderen moeten we onze array sorteren op basis van een sleutel. Ik heb elk object een dieptewaarde gegeven, en dus kan ik het volgende doen:
onScreen.sort (functie (a, b) retourneer a.depth> b.depth) 
Voordat je eindelijk alles hebt weergegeven:
for (var i = 0; i
Dit is een van de nadelen van deze methode, dat je elk frame op het scherm moet sorteren. U kunt dit altijd versnellen door ervoor te zorgen dat al uw sublijsten zijn gesorteerd, zodat u ze kunt samenvoegen terwijl u aaneenschakelt om de bestelling te onderhouden.
Dat is het! Je zou nu een (hopelijk veel sneller) werkend weergavesysteem moeten hebben!
Ander gebruik en tips
Dit kan een heel nuttige techniek zijn, maar zoals ik al zei in de inleiding, kun je dit alleen doen in een game-engine of een framework dat je controle geeft over de draw-calls. Toch zijn er dingen die u ruimtelijke hashes kunt gebruiken voor het weergeven. In feite worden ze vaker gebruikt om botsingsdetectie te versnellen (je kunt botsingscontroles overslaan voor objecten waarvan je weet dat ze ver weg zijn of zich niet in dezelfde cel bevinden).
Een andere techniek die vergelijkbaar is met ruimtelijke hashes, maar een beetje ingewikkelder, is het gebruik van een kwadratuur. Terwijl een ruimtelijke hash slechts een plat raster is, is een kwadrant eerder een hiërarchische structuur, dus je hoeft je geen zorgen te maken over de celgrootte, en je kunt sneller alle objecten in een bepaald gebied krijgen zonder dat je elk klein beetje hoeft te controleren cel.
Over het algemeen moet je in gedachten houden dat een ruimtelijke structuur niet altijd de beste oplossing is. Het is ideaal voor een game met:
 
een grote wereld met veel objecten
 
relatief weinig objecten op het scherm in vergelijking met de wereldgrootte
 
voornamelijk statische objecten
 
Als al je objecten de hele tijd in beweging zijn, moet je ze blijven verwijderen en toevoegen aan verschillende cellen, wat een aanzienlijke prestatievergoeding kan opleveren. Het was een ideaal weergavesysteem voor een spel als Move of Die (bijna een verdubbeling van de fps) omdat levels bestonden uit een groot aantal statische objecten en de personages de enige dingen waren die bewogen.
Hopelijk heeft deze tutorial u een idee gegeven van hoe het structureren van gegevens ruimtelijk een eenvoudige manier kan zijn om de prestaties te verbeteren en hoe uw weergavesysteem niet altijd een enkele lineaire lijst hoeft te zijn!



		
			
	   
	




Game ontwikkeling