Bien que je sois d'accord avec le sentiment: "ne vous inquiétez pas à moins que ce soit un problème avéré", je pense qu'il vaut la peine d'y penser dès le début: le réaménagement d'une solution est beaucoup plus douloureux. Et oui, seule la mise à jour des tuiles «à proximité» est la solution. Mais le stockage et l'adressabilité des éléments dans votre monde de jeu de manière efficace sont très importants pour des raisons de performances.
Ce à quoi vous pensez vraiment ici, c'est un ensemble de données clairsemé: quelque chose où les indices potentiels sont grands (ou illimités), mais seule une petite proportion est réellement utilisée. Le point clé est que vous ne savez pas exactement quelle proportion sera utilisée.
La solution standard à un problème d'ensembles de données clairsemés consiste à séparer l'index / l'adressabilité du stockage de données réel. Donc, si l'objet tuile est cher, stockez-le sous une forme compacte (par exemple un tableau plat). Mais permettez-lui d'être indexé via un objet moins cher. Dans sa forme la plus simple, il peut s'agir d'une matrice 2D (ou 3D) que vous pouvez facilement indexer par coordonnées, mais chaque élément de la matrice est simplement un index. Vous utilisez ensuite cet index pour rechercher le contenu réel des tuiles dans un tableau compact séparé. Si le contenu des tuiles n'existe pas encore, ajoutez-les à la fin du tableau et stockez l'index dans la matrice 3D.
La solution devient plus complexe si vous souhaitez prendre en charge la suppression du contenu (car cela conduit à la fragmentation du tableau de contenu), et si le contenu de votre mosaïque est bon marché, alors le poids supplémentaire de l'index (indices 32 bits ou 64 bits) dépassera probablement les économies de ne pas stocker chaque tuile potentielle unique. C'est également une recherche supplémentaire, qui nuira aux performances de votre cache.
Vous pouvez obtenir encore plus d'efficacité de stockage en introduisant des couches supplémentaires d'indirection. Disons que vous organisez vos tuiles en morceaux, et les morceaux ont une granularité de 64x64x64. Étant donné une tuile à 125, 1, 132, vous savez qu'elle appartient en morceaux (1,0,2). Vous avez donc un monde, qui se compose d'un tableau de blocs compact et d'une matrice d'indices de blocs (-1 si le bloc n'existe pas). Le contenu de chaque bloc (s'il est présent) est une matrice 64x64x64 d'index de tuiles (-1 si la tuile n'existe pas encore), et un tableau compact de tuiles utilisées. De cette façon, vous ne gravez pas une énorme quantité d'index de tuiles pour des morceaux qui ne sont jamais utilisés. En suivant ce type d'approche et en choisissant des nombres raisonnables pour la granularité des morceaux, vous pouvez augmenter massivement votre univers et garder votre utilisation de la mémoire sous contrôle. En fait, si vous faites vos morceaux 32x32x32,
Vous pouvez également faire des astuces sournoises, comme utiliser le bit de poids fort de vos morceaux ou index de tuiles pour signifier quelque chose de spécial. Donc, si une entrée dans la matrice de tuiles a le bit supérieur défini, les 31 bits inférieurs ne signifient pas un index de tuile, ils signifient plutôt un `` index de distorsion '' ou quelque chose de similaire, et vous pouvez le rechercher dans une liste maintenue séparément pour connaître les coordonnées qu'il mène.
Pourquoi ne pouvez-vous pas stocker un million de tuiles en mémoire? Même mon téléphone a 256 Mo de RAM; un million de tuiles vides va être quoi, 4-32 Mo?
la source