Comment ont-ils pu le faire: des millions de tuiles à Terraria

45

J'ai travaillé sur un moteur de jeu similaire à Terraria , principalement sous forme de défi. Bien que j'aie compris l'essentiel, je n'arrive pas vraiment à comprendre comment ils gèrent les millions de tuiles interactives / récupérables. le jeu a à la fois. Créer environ 500 000 tuiles, soit 1 / 20e de ce qui est possible dans Terraria , dans mon moteur, le débit d'images passe de 60 à environ 20, même si je ne fais que restituer les tuiles en vue. Remarquez, je ne fais rien avec les carreaux, je les garde seulement en mémoire.

Mise à jour : code ajouté pour montrer comment je fais les choses.

Cela fait partie d'une classe qui gère les carreaux et les dessine. Je suppose que le coupable est la partie "foreach", qui itère tout, même les index vides.

...
    public void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        foreach (Tile tile in this.Tiles)
        {
            if (tile != null)
            {
                if (tile.Position.X < -this.Offset.X + 32)
                    continue;
                if (tile.Position.X > -this.Offset.X + 1024 - 48)
                    continue;
                if (tile.Position.Y < -this.Offset.Y + 32)
                    continue;
                if (tile.Position.Y > -this.Offset.Y + 768 - 48)
                    continue;
                tile.Draw(spriteBatch, gameTime);
            }
        }
    }
...

Voici également la méthode Tile.Draw, qui pourrait également être mise à jour, chaque mosaïque utilisant quatre appels à la méthode SpriteBatch.Draw. Cela fait partie de mon système de notation automatique, ce qui signifie que chaque coin doit être dessiné en fonction des tuiles voisines. texture_ * sont des rectangles, sont définis une fois à la création du niveau, pas à chaque mise à jour.

...
    public virtual void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        if (this.type == TileType.TileSet)
        {
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position, texture_tl, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(8, 0), texture_tr, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(0, 8), texture_bl, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(8, 8), texture_br, this.BlendColor);
        }
    }
...

Toute critique ou suggestion à mon code est la bienvenue.

Mise à jour : solution ajoutée.

Voici la dernière méthode Level.Draw. La méthode Level.TileAt vérifie simplement les valeurs entrées pour éviter les exceptions OutOfRange.

...
    public void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        Int32 startx = (Int32)Math.Floor((-this.Offset.X - 32) / 16);
        Int32 endx = (Int32)Math.Ceiling((-this.Offset.X + 1024 + 32) / 16);
        Int32 starty = (Int32)Math.Floor((-this.Offset.Y - 32) / 16);
        Int32 endy = (Int32)Math.Ceiling((-this.Offset.Y + 768 + 32) / 16);

        for (Int32 x = startx; x < endx; x += 1)
        {
            for (Int32 y = starty; y < endy; y += 1)
            {
                Tile tile = this.TileAt(x, y);
                if (tile != null)
                    tile.Draw(spriteBatch, gameTime);

            }
        }
    }
...
William Mariager
la source
2
Etes-vous absolument certain de ne rendre que ce que la caméra a en vue, c'est-à-dire le code permettant de déterminer ce qui doit être rendu correctement?
Cooper
5
La fréquence d'image passe de 60 à 20 images par seconde, à cause de la mémoire allouée? C'est très peu probable, il doit y avoir quelque chose qui ne va pas. De quelle plateforme s'agit-il? Le système échange-t-il la mémoire virtuelle sur un disque?
Maik Semder
6
@Drackir Dans ce cas, je dirais que c'est faux s'il existe même une classe de mosaïques, un tableau de nombres entiers de longueur appropriée devrait suffire, et lorsqu'il y a un demi-million d'objets, la surcharge de OO n'est pas une blague. Je suppose qu'il est possible de faire avec des objets, mais quel serait le but? Un tableau entier est extrêmement simple à manipuler.
aaaaaaaaaaaa
3
Aie! Itérer toutes les tuiles et appeler Draw quatre fois sur chacune des vues affichées. Il y a certainement des améliorations possibles ici ....
jeudi
11
Vous n'avez pas besoin de tous les partitionnements sophistiqués décrits ci-dessous pour afficher uniquement ce qui est en vue. C'est un tilemap. Il est déjà partitionné dans une grille régulière. Il suffit de calculer la mosaïque en haut à gauche de l'écran et en bas à droite et de dessiner tout ce qui se trouve dans ce rectangle.
Blecki

Réponses:

56

Êtes-vous en train de parcourir les 500 000 tuiles lorsque vous effectuez un rendu? Si c'est le cas, cela va probablement causer une partie de vos problèmes. Si vous parcourez un demi-million de carreaux lors du rendu, et un demi-million de carreaux lors de l'exécution des graduations de «mise à jour», alors vous bouclez un million de carreaux par image.

De toute évidence, il existe des moyens autour de cela. Vous pouvez effectuer vos ticks de mise à jour tout en effectuant un rendu, vous évitant ainsi la moitié du temps passé en boucle sur toutes ces tuiles. Mais cela lie votre code de rendu et votre code de mise à jour en une seule fonction et est généralement une mauvaise idée .

Vous pouvez garder une trace des tuiles qui sont à l'écran et ne les parcourir qu'en boucle (et les restituer). En fonction de facteurs tels que la taille de vos mosaïques et la taille de l'écran, cela pourrait facilement réduire la quantité de mosaïques à boucler, ce qui économiserait beaucoup de temps de traitement.

Enfin, et peut-être la meilleure option (la plupart des grands jeux mondiaux le font), consiste à diviser votre terrain en régions. Divisez le monde en morceaux de, disons, 512x512, et chargez / déchargez les régions au fur et à mesure que le joueur se rapproche ou s'éloigne d'une région. Cela vous évite également de devoir parcourir des vignettes lointaines pour effectuer tout type de "mise à jour".

(Évidemment, si votre moteur n'effectue aucune sorte de mise à jour sur les tuiles, vous pouvez ignorer la partie de cette réponse qui mentionne celles-ci.)

thédien
la source
5
La partie région semble intéressante, si je me souviens bien, c'est ce que fait Minecraft. Cependant, cela ne fonctionne pas avec l'évolution du terrain dans Terraria, même si vous êtes loin de là, comme l'épandage d'herbe, la croissance de cactus, etc. Éditer : à moins que, bien sûr, ils appliquent le temps écoulé depuis la dernière fois que la région était active, puis effectuent tous les changements qui seraient survenus au cours de cette période. Cela pourrait effectivement fonctionner.
William Mariager
2
Minecraft utilise certainement des régions (tout comme les derniers jeux Ultima, et je suis sûr que beaucoup de jeux Bethesda le font). Je suis moins sûr de la façon dont Terraria gère le terrain, mais ils appliquent probablement le temps écoulé à une "nouvelle" région ou stockent la carte entière en mémoire. Ce dernier exigerait une utilisation importante de la RAM, mais la plupart des ordinateurs modernes pourraient le gérer. Il se peut également que d'autres options n'aient pas été mentionnées.
Thedaian
2
@MindWorX: Faire toutes les mises à jour quand le rechargement ne fonctionne pas toujours - supposez que vous avez tout un tas de zones stériles puis d'herbe. Vous partez pendant des siècles et marchez ensuite vers l'herbe. Lorsque le bloc avec les charges d'herbe, il rattrape et se propage dans ce bloc, mais ne se propage pas dans les blocs plus proches déjà chargés. Cependant, ces choses progressent BEAUCOUP plus lentement que le jeu - vérifiez seulement un petit sous-ensemble de tuiles au cours d'un cycle de mise à jour et vous pourrez mettre en direct des terrains lointains sans charger le système.
Loren Pechtel
1
Comme alternative (ou complément) au "rattrapage" lorsqu'une région se rapproche du joueur, vous pouvez utiliser une simulation distincte pour effectuer une itération sur chaque région distante et la mettre à jour plus lentement. Vous pouvez réserver du temps pour chaque image ou l'exécuter sur un thread séparé. Ainsi, par exemple, vous pouvez mettre à jour la région dans laquelle se trouve le lecteur, ainsi que les 6 régions adjacentes à chaque image, mais également mettre à jour 1 ou 2 régions supplémentaires.
Lewis Wakeford
1
Pour tous ceux qui s’interrogent, Terraria stocke la totalité de ses données de mosaïque dans un tableau 2D (taille maximale de 8400x2400). Et utilise ensuite des calculs simples pour décider quelle section de carreaux rendre.
FrenchyNZ
4

Je vois une énorme erreur ici non traitée par aucune des réponses. Bien sûr, vous ne devriez jamais dessiner et parcourir plus de tuiles que nécessaire. Ce qui est moins évidemment, c’est la façon dont vous définissez les carreaux. Comme je peux voir que vous avez fait une classe de tuiles, je le faisais toujours aussi mais c'est une grave erreur. Vous avez probablement toutes sortes de fonctions dans cette classe et cela crée beaucoup de traitements inutiles.

Vous ne devriez qu'itérer sur ce qui est vraiment nécessaire de traiter. Alors réfléchissez à ce dont vous avez réellement besoin pour les carreaux. Pour dessiner, vous n'avez besoin que d'une texture, mais vous ne voulez pas parcourir une image réelle, car celles-ci sont volumineuses à traiter. Vous pouvez simplement créer un int [,] ou même un octet non signé [,] (si vous ne vous attendez pas à plus de 255 textures de mosaïque). Tout ce que vous avez à faire est de parcourir ces petits tableaux et d’utiliser un commutateur ou une instruction if pour dessiner la texture.

Alors, que devez-vous mettre à jour? Le type, la santé et les dégâts semblent suffisants. Tous ces éléments peuvent être stockés en octets. Alors pourquoi ne pas créer une structure comme celle-ci pour la boucle de mise à jour:

struct TileUpdate
{
public byte health;
public byte type;
public byte damage;
}

Vous pouvez réellement utiliser le type pour dessiner la tuile. Vous pouvez donc détacher celui-ci (en faire un tableau) de la structure afin de ne pas parcourir les champs inutiles de santé et de dommages dans la boucle de dessin. Pour la mise à jour, vous devez considérer une zone plus large que votre écran afin que le monde du jeu se sente plus vivant (les entités changent de position en dehors de l'écran), mais pour dessiner des éléments, vous avez simplement besoin des vignettes visibles.

Si vous conservez la structure ci-dessus, cela ne prend que 3 octets par tuile. Donc, pour l’épargne et la mémoire, c’est l’idéal. Pour la vitesse de traitement, peu importe que vous utilisiez int ou byte, ni même long int si vous avez un système 64 bits.

Madmenyo
la source
1
Oui, les itérations ultérieures de mon moteur ont évolué pour l'utiliser. Principalement pour réduire la consommation de mémoire et augmenter la vitesse. Les types ByRef sont lents par rapport à un tableau rempli de structures ByVal. Néanmoins, il est bon que vous ayez ajouté ceci à la réponse.
William Mariager
1
Ouais, nous sommes tombés dessus en cherchant des algorithmes aléatoires. Vous avez immédiatement remarqué que vous utilisiez votre propre classe de tuiles dans votre code. C'est une erreur très commune lorsque vous êtes nouveau. Heureux de voir que vous êtes toujours actif depuis que vous avez posté ceci il y a 2 ans.
Madmenyo
3
Vous n'avez besoin ni de l'un healthni de l' autre damage. Vous pouvez conserver un petit tampon des emplacements de mosaïque récemment choisis et des dommages qu'ils subissent. Si une nouvelle tuile est sélectionnée et que la mémoire tampon est pleine, éliminez l'emplacement le plus ancien avant d'en ajouter une nouvelle. Cela limite le nombre de tuiles que vous pouvez exploiter à la fois, mais il y a quand même une limite intrinsèque (approximativement #players * pick_tile_size). Vous pouvez conserver cette liste par joueur si cela vous facilite la tâche. Taille ne importe pour la vitesse; une taille plus petite signifie plus de tuiles dans chaque cacheline de la CPU
Sean Middleditch
@SeanMiddleditch Vous avez raison, mais ce n'était pas le but. Le but était de vous arrêter et de penser à ce dont vous avez réellement besoin pour dessiner les carreaux à l’écran et faire vos calculs. Comme le PO utilisait toute une classe, j’en ai fait un exemple simple, simple qui contribue grandement à la progression de l’apprentissage. Maintenant, ouvrez mon sujet sur la densité de pixels s'il vous plaît, vous êtes évidemment un programmeur qui essaie de regarder cette question avec le regard d'un artiste en images de synthèse. Depuis ce site est également pour CG pour les jeux autant que je sache.
Madmenyo
2

Il existe différentes techniques de codage que vous pouvez utiliser.

RLE: Vous commencez donc par une coordonnée (x, y), puis vous comptez combien de la même tuile existe côte à côte (longueur) le long de l’un des axies. Exemple: (1,1,10,5) signifierait que, à partir de la coordonnée 1,1, il y a 10 carreaux côte à côte du type de carreau 5.

Le tableau massif (bitmap): chaque élément du tableau conserve le type de tuile qui réside dans cette zone.

EDIT: Je viens de rencontrer cette excellente question ici: Fonction de graine aléatoire pour la génération de cartes?

Le générateur de bruit Perlin semble être une bonne réponse.

Sam Ax
la source
Je ne suis pas vraiment sûr que vous répondiez à la question qui vous est posée car vous parlez d'encodage (et de bruit perlin) et que cette question semble traiter de problèmes de performances.
Thedaian
1
En utilisant le bon encodage (tel que le bruit perlin), vous ne pouvez plus vous inquiéter de garder toutes ces tuiles en mémoire en même temps .. vous demandez simplement à votre encodeur (générateur de bruit) de vous dire ce qui est censé apparaître à une coordonnée donnée. Il existe un équilibre entre les cycles du processeur et l'utilisation de la mémoire, et un générateur de bruit peut aider à cet équilibre.
Sam Axe
2
Le problème ici est que si vous créez un jeu qui permet aux utilisateurs de modifier le terrain d’une manière ou d’une autre, il ne suffit pas d’utiliser un générateur de bruit pour "stocker" ces informations. De plus, la génération de bruit est assez coûteuse, de même que la plupart des techniques de codage. Vous feriez mieux d'économiser des cycles de processeur pour des éléments de jeu réels (physique, collisions, éclairage, etc.) Le bruit Perlin est excellent pour la génération de terrain et l'encodage est bon pour l'enregistrement sur disque, mais il existe de meilleures façons de gérer la mémoire dans ce cas.
Thedaian
Très bonne idée cependant, comme dans le cas américain, le terrain est en interaction avec l'utilisateur, ce qui signifie que je ne peux pas extraire mathématiquement d'informations. Je regarderai quand même le bruit perlin, pour générer le terrain de base.
William Mariager
1

Vous devriez probablement partitionner le tilemap comme déjà suggéré. Par exemple, avec la structure Quadtree, vous débarrasserez de tout traitement potentiel (par exemple, même simplement en boucle) des tuiles inutiles (et non visiles). De cette façon, vous ne traitez que ce qui pourrait nécessiter un traitement et l'augmentation de la taille du jeu de données (mappage de tuiles) ne provoque aucune pénalité de performance pratique. Bien sûr, en supposant que l'arbre est bien équilibré.

Je ne veux pas avoir l'air ennuyeux ou quoi que ce soit en répétant le "vieux", mais lors de l'optimisation, n'oubliez jamais d'utiliser les optimisations supportées par votre chaîne d'outils / compilateur, vous devriez les expérimenter un peu. Et oui, l'optimisation prématurée est la racine de tous les maux. Faites confiance à votre compilateur, il sait mieux que vous dans la plupart des cas, mais toujours, toujoursmesurer deux fois et ne jamais compter sur des estimations approximatives. Il ne s'agit pas d'implémenter rapidement l'algorithme le plus rapide tant que vous ne savez pas où se trouve le goulot d'étranglement. C'est pourquoi vous devez utiliser un profileur pour rechercher les chemins les plus lents (chaud) du code et vous concentrer sur leur élimination (ou leur optimisation). Une connaissance de bas niveau de l'architecture cible est souvent essentielle pour exploiter tout ce que le matériel a à offrir. Par conséquent, étudiez ces caches de processeur et découvrez ce qu'est un prédicteur de branche. Voyez ce que votre profileur vous dit sur les correspondances et les ratés de cache / branche. Et comme le montre l'utilisation d'une forme de structure de données arborescente, il est préférable de disposer de structures de données intelligentes et d'algorithmes muets, plutôt que l'inverse. Les données sont primordiales pour la performance. :)

zxcdw
la source
+1 pour "optimisation prématurée est la racine de tout le mal" Je suis coupable de ceci :(
thedaian
16
-1 un quadtree? Trop cher un peu? Quand toutes les tuiles ont la même taille dans un jeu 2D comme celui-ci (ce qui est le cas pour les terrariums), il est extrêmement facile de déterminer la plage de tuiles affichées à l'écran. tuiles en bas à droite.
BlueRaja - Danny Pflughoeft
1

N'est-ce pas trop de nombreux appels de tirage? Si vous mettez toutes les textures de mosaïque de vos cartes dans un même atlas d'image, il n'y aura aucune permutation de texture lors du rendu. Et si vous regroupez toutes vos tuiles dans un seul Mesh, celui-ci sera dessiné en un seul appel.

À propos de la dynamique aditing ... Peut-être que quad tree n'est pas une si mauvaise idée. En supposant que les tuiles soient placées dans les nœuds feuilles et non-feuilles ne sont que des maillages groupés de ses enfants, la racine doit contenir toutes les tuiles groupées dans un seul maillage. Supprimer une tuile nécessite des mises à jour des nœuds (rebatching du maillage) jusqu'à la racine. Mais à chaque niveau d’arbre, il n’ya qu’un quart du maillage rebatché qui ne devrait pas être trop, un maillage 4 * tree_height se joint?

Oh, et si vous utilisez cet arbre dans l’algorithme de découpage, vous ne rendrez pas toujours le nœud racine, mais certains de ses enfants, de sorte que vous n’aurez même pas à mettre à jour / réassembler tous les nœuds jusqu’à la racine, mais jusqu’au nœud (non-feuille) que vous êtes. rendu au moment.

Juste mes pensées, pas de code, peut-être que c'est un non-sens.

arrivée
la source
0

@arrival a raison. Le problème est le code de tirage. Vous construisez un tableau de 4 * 3000 + commandes quadruples (plus de 24000 commandes polygonales ) par image. Ensuite, ces commandes sont traitées et transmises au GPU. C'est plutôt mauvais.

Il y a des solutions.

  • Rendez de gros blocs (par exemple, la taille de l'écran) de mosaïques en une texture statique et dessinez-la en un seul appel.
  • Utilisez des shaders pour dessiner les mosaïques sans envoyer la géométrie au GPU à chaque image (c'est-à-dire stocker la mappe de mosaïques sur le GPU).
Ark-kun
la source
0

Ce que vous devez faire, c'est diviser le monde en régions. La génération de terrain de bruit Perlin peut utiliser une graine commune, de sorte que même si le monde n’est pas prégénéré, la graine fera partie de l’algo de bruit, qui raccorde joliment le nouveau terrain aux parties existantes. De cette façon, vous n'avez pas besoin de calculer plus qu'un petit tampon avant la vue des joueurs à la fois (quelques écrans autour de celui en cours).

En ce qui concerne le traitement de choses telles que les plantes poussant dans des zones éloignées de l'écran actuel du lecteur, vous pouvez avoir des minuteries par exemple. Ces minuteries parcourent des fichiers contenant des informations sur les plantes, leur position, etc. Il vous suffit de lire / mettre à jour / enregistrer les fichiers dans les minuteries. Lorsque le lecteur revient dans ces régions du monde, le moteur lit les fichiers normalement et présente les nouvelles données de l'installation à l'écran.

J'ai utilisé cette technique dans un jeu similaire à celui que j'avais créé l'année dernière, pour la récolte et l'agriculture. Le joueur pouvait marcher loin des champs et, à son retour, les objets avaient été mis à jour.

Jason Coombes
la source
-2

J'ai réfléchi à la façon de gérer autant de zillions de blocs et la seule chose qui me vienne à l'esprit est le modèle de conception Flyweight. Si vous ne le savez pas, je vous conseille vivement de lire ceci: cela pourrait beaucoup aider à économiser de la mémoire et du traitement: http://en.wikipedia.org/wiki/Flyweight_pattern

Tiago Frossard
la source
3
-1 Cette réponse est trop générale pour être utile, et le lien que vous fournissez ne résout pas directement ce problème particulier. Le modèle Flyweight est l’un des nombreux moyens de gérer efficacement de grands ensembles de données; Pourriez-vous préciser comment appliquer ce modèle dans le contexte spécifique du stockage de tuiles dans un jeu ressemblant à Terraria?
postgoodism