Reconcevoir votre liste d'affichage avec des hachages spatiaux

Dans tout jeu en 2D, vous devez savoir dans quel ordre dessiner vos sprites. Vous dessinez généralement du fond de la scène vers l'avant, les objets les plus anciens étant recouverts par les objets les plus récents. C'est l'algorithme standard de Painter utilisé pour représenter la profondeur sur une toile (numérique ou autre).

Par Zapyon - Propre travail, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14256921

Le moyen le plus simple de garder une trace de cela est de mettre tous vos objets dans un grand tableau, triés par leur profondeur. Ainsi, dans la scène ci-dessus, votre tableau ressemblerait à quelque chose comme: [Montagne, Terre, Tree1, Tree2, Tree3,…]

Le problème avec un seul grand tableau

Le problème avec une liste d’affichage centrale est qu’il n’ya pas de moyen facile de savoir quels objets sont à l’écran à un moment donné. Pour ce faire, vous devez parcourir tout le tableau et vérifier chaque objet. Cela devient généralement un problème si vous avez un grand monde de jeux où de nombreux objets existent en dehors de l'écran et ne doivent pas être rendus ou mis à jour..

Un hachage spatial est un moyen de stocker vos objets pour éviter ce problème. La bonne chose à propos de l’utilisation d’un hachage est qu’il faut toujours un temps constant pour déterminer quels objets sont à l’écran, quelle que soit l’ampleur du monde du jeu.!

Maintenant, la plupart des moteurs de jeu ne vous laisseront pas jouer avec la structure interne de leurs objets, mais si vous programmez dans un environnement où vous contrôlez les appels de tirages (tels que votre propre moteur OpenGL, un code JavaScript pur). jeu, ou des cadres plus ouverts tels que LÖVE), cela pourrait être quelque chose de intéressant à mettre en œuvre.

L'alternative: hachages spatiaux

Un hachage spatial est juste un table de hachage où chaque clé est une coordonnée 2D et la valeur est une liste d'objets de jeu dans cette zone.

Imaginez que votre monde soit divisé en une grille telle que chaque objet appartient à au moins une cellule. Voici comment vous chercheriez quelque chose à la position (420 600) si cela avait été implémenté en JavaScript:

var X, Y = 420 600; // Accrochez X et Y à la grille X = Math.round (X / CELL_SIZE) * CELL_SIZE; Y = Math.round (Y / CELL_SIZE) * CELL_SIZE; // Vérifie maintenant quels éléments se trouvent à cette position. SpatialHash [X + "," + Y] // Voici une liste d'objets dans cette cellule.

C'est si facile! Vous pouvez immédiatement savoir ce qui se passe dans cette position. La clé est une concaténation de chaîne des coordonnées X et Y, mais elle ne le fait pas. avoir pour être une chaîne, il n'a pas besoin d'une virgule au milieu; il doit juste être unique pour chaque paire de X et Y.

Pour voir pourquoi cela est si pratique, réfléchissez à la façon dont vous obtiendriez les objets à cette position en utilisant un grand tableau:

var X = 420; var Y = 600; pour (var i = 0; i
Nous vérifions chaque objet, même si la plupart d'entre eux sont très éloignés! Cela peut grandement nuire à votre performance si vous effectuez de nombreuses recherches comme celle-ci et votre gameObjects le tableau est énorme.
Un exemple concret
Si vous n'êtes pas encore convaincu de l'utilité de cette fonctionnalité, voici une démo écrite en JavaScript pur où j'essaie de restituer un million d'objets dans le monde du jeu. Dans les deux cas, seuls les objets à l'écran sont réellement rendus..
Cliquez pour voir la démo en cours!
Et la version de hachage spatiale en direct.
La version à tableau unique est extrêmement lente. Même si vous enregistrez les éléments à l'écran pour ne pas avoir à vérifier chaque image, vous devez quand même vérifier à nouveau l'ensemble de la matrice lorsque la caméra bouge, ce qui entraîne de fortes hausses..
Changer simplement la façon dont nous stockons nos objets de jeu peut faire toute la différence entre une expérience fluide et un jeu injouable.
Implémentation d'un hachage spatial
Un hachage spatial devrait être vraiment facile à implémenter dans n'importe quelle langue (en fait, passer du premier exemple au deuxième ci-dessus n'a pris que 30 lignes de code supplémentaires!)
Il existe quatre étapes pour implémenter cela en tant que système de rendu:
 
Mettre en place la table de hachage.
 
Ajouter et supprimer des objets dans le hachage.
 
Recueillir des objets dans une zone donnée.
 
Trier les objets par profondeur avant de les rendre.
 
Vous pouvez voir une implémentation fonctionnelle en JavaScript sur GitHub comme référence.
1. Configurer la table de hachage
La plupart des langues ont une sorte de table de hachage / carte intégrée. Notre hachage spatial est juste une table de hachage standard. En JavaScript, vous pouvez simplement en déclarer un avec:
var spatialHash = ; var CELL_SIZE = 60;
La seule autre chose à mentionner ici est que vous avez une marge de manœuvre pour choisir la taille de la cellule. En général, si vos cellules sont deux fois plus grandes que votre objet moyen semble bien fonctionner. Si vos cellules sont trop grandes, vous attirerez trop d'objets à chaque recherche. Si elles sont trop petites, vous devrez vérifier plus de cellules pour couvrir la zone souhaitée.. 
2. Ajouter et supprimer des objets dans le hachage
L'ajout d'un objet au hachage est un problème qui consiste à le capturer dans une cellule, à créer le tableau de cellules s'il n'existe pas et à l'ajouter à ce tableau. Voici ma version JavaScript:
spatialHash.add = fonction (obj) var X = Math.round (obj.x / CELL_SIZE) * CELL_SIZE; var Y = Math.round (obj.y / CELL_SIZE) * CELL_SIZE; touche var = X + "," + Y; if (spatialHash [clé] == non défini) spatialHash [clé] = [] spatialHash [clé] .push (obj)
Cependant, il y a une mise en garde: que se passe-t-il si votre objet s'étend sur plusieurs cellules ou est trop grand pour tenir dans une cellule??
La solution consiste simplement à l'ajouter à tout les cellules qu'il touche. Cela garantit que si une partie de l'objet est en vue, il sera rendu. (Bien entendu, vous devez également vous assurer de ne pas restituer ces objets plusieurs fois.)
Je n'ai pas implémenté de fonction remove dans mon exemple, mais supprimer un objet consiste simplement à le retirer du (des) tableau (s) dont il fait partie. Pour simplifier les choses, vous pouvez faire en sorte que chaque objet garde une référence à quelles cellules il appartient..
3. Collecter des objets dans une zone donnée
Voici maintenant le cœur de cette technique: dans une zone de l'écran, vous voulez pouvoir y insérer tous les objets..
Tout ce que vous avez à faire ici est de commencer à parcourir toutes les cellules en fonction de la position de votre caméra dans le monde du jeu et à rassembler toutes les sous-listes dans un seul tableau à restituer. Voici l'extrait de code JavaScript approprié:
var padding = 100; // Remplissage pour attraper des cellules supplémentaires sur les bords afin que le joueur ne voie pas les objets "apparaître" dans l'existence. var startX = -camX - remplissage; var startY = -camY - remplissage; var endX = -camX + canvas.width + padding; var endY = -camY + canvas.height + padding; var onScreen = [] pour (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. Trier les objets par profondeur avant de les rendre
Vous vous êtes peut-être déjà rendu compte qu'abandonner l'idée d'une liste volumineuse signifiait aussi que vous abandonniez le tri en profondeur très pratique. Nous récupérons des objets dans notre grille en fonction de leur emplacement, mais le tableau que nous obtenons n'est pas trié. 
Comme dernière étape avant le rendu, nous devons trier notre tableau en fonction de certaines clés. J'ai donné à chaque objet une valeur de profondeur et je peux donc faire:
onScreen.sort (fonction (a, b) return a.depth> b.depth) 
Avant de tout rendre finalement:
pour (var i = 0; i
C’est l’un des inconvénients de cette méthode: vous devez trier ce qui est affiché à l’écran à chaque image. Vous pouvez toujours accélérer le processus en vous assurant que toutes vos sous-listes sont triées afin de pouvoir les fusionner pendant la concaténation afin de maintenir l'ordre..
C'est tout! Vous devriez maintenant avoir un système de rendu fonctionnel (j'espère beaucoup plus rapide)!
Autres utilisations et astuces
Cela peut être une technique très utile, mais comme je l’ai dit dans l’introduction, vous ne pouvez le faire que dans un moteur de jeu ou une structure qui vous permet de contrôler les appels de tirage. Néanmoins, il y a des choses pour lesquelles vous pouvez utiliser des hachages spatiaux en plus du rendu. En fait, ils sont plus couramment utilisés pour accélérer la détection des collisions (vous pouvez ignorer toutes les vérifications de collisions pour les objets que vous savez éloignés ou qui ne sont pas dans la même cellule)..
Une autre technique similaire au hachage spatial, mais un peu plus compliquée, consiste à utiliser un quadtree. Alors qu'un hachage spatial est juste une grille plate, un quadtree est plus une structure hiérarchique, vous n'avez donc pas à vous soucier de la taille de la cellule, et vous pouvez obtenir plus rapidement tous les objets d'une zone donnée sans avoir à vérifier chaque petit cellule.
En général, gardez à l'esprit qu'une structure spatiale ne sera pas toujours la meilleure solution. C'est idéal pour un jeu qui a:
 
un grand monde avec de nombreux objets
 
relativement peu d'objets à l'écran par rapport à la taille du monde
 
principalement des objets statiques
 
Si tous vos objets bougent tout le temps, vous devrez continuer à les supprimer et à les ajouter à différentes cellules, ce qui pourrait entraîner une baisse importante des performances. C'était un système de rendu idéal pour un jeu comme Move or Die (doublant presque le nombre de fps), car les niveaux étaient composés d'objets statiques, et les personnages étaient les seuls éléments qui bougeaient..
Espérons que ce tutoriel vous ait montré comment la structuration spatiale des données peut être un moyen simple d'améliorer les performances et que votre système de rendu ne doit pas toujours être une seule liste linéaire.!



		
			
	   
	




Développement de jeu