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

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);

            }
        }
    }
...

Ê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.)

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.

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.

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. :)

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.

@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).

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.

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