Algorithme de mosaïque de carte

La carte

Je crée un RPG basé sur des tuiles avec Javascript, en utilisant des cartes de hauteur de bruit perlin, puis j'attribue un type de tuile en fonction de la hauteur du bruit.

Les cartes finissent par ressembler à quelque chose comme ça (dans la vue minicarte).

J'ai un algorithme assez simple qui extrait la valeur de couleur de chaque pixel de l'image et la convertit en un entier (0-5) en fonction de sa position entre (0-255) qui correspond à une tuile dans le dictionnaire de tuiles. Ce tableau 200x200 est ensuite transmis au client.

Le moteur détermine ensuite les tuiles à partir des valeurs du tableau et les dessine sur le canevas. Donc, je me retrouve avec des mondes intéressants qui ont des caractéristiques réalistes: montagnes, mers, etc.

Maintenant, la prochaine chose que je voulais faire était d'appliquer une sorte d'algorithme de fusion qui ferait fondre les tuiles de manière transparente dans leurs voisins, si le voisin n'est pas du même type. L'exemple de carte ci-dessus est ce que le joueur voit dans sa mini-carte. À l'écran, ils voient une version rendue de la section marquée par le rectangle blanc; où les tuiles sont rendues avec leurs images plutôt que sous forme de pixels de couleur unique.

Ceci est un exemple de ce que l'utilisateur verrait sur la carte mais ce n'est pas le même emplacement que celui indiqué dans la fenêtre ci-dessus!

C'est dans cette optique que je souhaite que la transition se produise.

L'algorithme

J'ai proposé un algorithme simple qui traverserait la carte dans la fenêtre et rendrait une autre image au-dessus de chaque tuile, à condition qu'elle soit à côté d'une tuile de type différent. (Ne change pas la carte! Rend juste quelques images supplémentaires.) L'idée de l'algorithme était de profiler les voisins de la tuile actuelle:

Ceci est un exemple de scénario de ce que le moteur pourrait avoir à rendre, la tuile actuelle étant celle marquée du X.

Un tableau 3x3 est créé et les valeurs qui l'entourent sont lues. Donc, pour cet exemple, le tableau ressemblerait à.

[
    [1,2,2]
    [1,2,2]
    [1,1,2]
];

Mon idée était alors d'élaborer une série de cas pour les configurations de tuiles possibles. À un niveau très simple:

if(profile[0][1] != profile[1][1]){
     //draw a tile which is half sand and half transparent
     //Over the current tile -> profile[1][1]
     ...
}

Ce qui donne ce résultat:

Ce qui fonctionne comme une transition de [0][1]vers [1][1], mais pas de [1][1]vers [2][1], là où un bord dur reste. J'ai donc pensé que dans ce cas, une tuile d'angle devrait être utilisée. J'ai créé deux feuilles de sprite 3x3 qui, selon moi, contiendraient toutes les combinaisons possibles de tuiles qui pourraient être nécessaires. Ensuite, j'ai répliqué cela pour toutes les tuiles qu'il y a dans le jeu (les zones blanches sont transparentes). Cela finit par être 16 tuiles pour chaque type de tuile (les tuiles centrales de chaque feuille de sprites ne sont pas utilisées.)

Le résultat idéal

Donc, avec ces nouvelles tuiles et l'algorithme correct, la section d'exemple ressemblerait à ceci:

Cependant, chaque tentative que j'ai faite a échoué, il y a toujours une faille dans l'algorithme et les modèles finissent par être étranges. Je n'arrive pas à résoudre tous les cas correctement et dans l'ensemble, cela semble être une mauvaise façon de le faire.

Une solution?

Donc, si quelqu'un pouvait fournir une solution alternative quant à la façon dont je pourrais créer cet effet, ou dans quelle direction aller pour écrire l'algorithme de profilage, alors je serais très reconnaissant!

L'idée de base de cet algorithme est d'utiliser une étape de pré-traitement pour trouver toutes les arêtes, puis de sélectionner la tuile de lissage correcte en fonction de la forme de l'arête.

La première étape serait de trouver tous les bords. Dans l'exemple ci-dessous, les tuiles de bord marquées d'un X sont toutes des tuiles vertes avec une tuile beige comme une ou plusieurs de leurs huit tuiles voisines. Avec différents types de terrain, cette condition pourrait se traduire par une tuile étant une tuile de bord si elle a des voisins de numéro de terrain inférieur.

Une fois que toutes les tuiles de bord sont détectées, la prochaine chose à faire est de sélectionner la tuile de lissage appropriée pour chaque tuile de bord. Voici ma représentation de vos carreaux de lissage.

Notez qu'il n'y a en fait pas beaucoup de types de carreaux différents. Nous avons besoin des huit carreaux extérieurs de l'un des carrés 3x3, mais seulement des quatre carrés d'angle de l'autre car les carreaux de bord droit se trouvent déjà dans le premier carré. Cela signifie qu'il y a au total 12 cas différents à distinguer.

Maintenant, en regardant une tuile de bord, nous pouvons déterminer dans quel sens la frontière tourne en regardant ses quatre tuiles voisines les plus proches. En marquant une tuile de bord avec X comme ci-dessus, nous avons les six cas différents suivants.

Ces cas sont utilisés pour déterminer la tuile de lissage correspondante et nous pouvons numéroter les tuiles de lissage en conséquence.

Il y a encore un choix de a ou b pour chaque cas. Cela dépend du côté de l'herbe. Une façon de déterminer cela pourrait être de garder une trace de l'orientation de la limite, mais probablement la façon la plus simple de le faire est de choisir une tuile à côté du bord et de voir de quelle couleur elle a. L'image ci-dessous montre les deux cas 5a) et 5b) qui peuvent être distingués en vérifiant par exemple la couleur du carreau supérieur droit.

L'énumération finale de l'exemple d'origine ressemblerait alors à ceci.

Et après avoir sélectionné la tuile de bord correspondante, la bordure ressemblerait à quelque chose comme ça.

En guise de note finale, je pourrais dire que cela fonctionnerait tant que la frontière est quelque peu régulière. Plus précisément, les tuiles de bord qui n'ont pas exactement deux tuiles de bord comme leurs voisines devront être traitées séparément. Cela se produira pour les tuiles de bord sur le bord de la carte qui auront un seul bord voisin et pour des morceaux de terrain très étroits où le nombre de tuiles de bord voisines pourrait être de trois ou même quatre.

Le carré suivant représente une plaque de métal. Il y a un «conduit de chaleur» dans le coin supérieur droit. Nous pouvons voir comment la température de ce point reste constante, la plaque métallique converge vers une température constante en chaque point, étant naturellement plus chaude près du sommet:

Le problème de trouver la température en chaque point peut être résolu comme un "problème de valeur limite". Cependant, le moyen le plus simple de calculer la chaleur à chaque point est de modéliser la plaque sous forme de grille. Nous connaissons les points de la grille à température constante. Nous avons réglé la température de tous les points inconnus sur la température ambiante (comme si l'évent venait juste d'être allumé). Nous laissons ensuite la chaleur se propager à travers la plaque jusqu'à atteindre la convergence. Cela se fait par itération: nous itérons sur chaque point (i, j). On fixe point (i, j) = (point (i + 1, j) + point (i-1, j) + point (i, j + 1) + point (i, j-1)) / 4 [sauf le point (i, j) a un conduit de chaleur à température constante]

Si vous appliquez cela à votre problème, c'est très similaire, juste des couleurs moyennes au lieu des températures. Vous auriez probablement besoin d'environ 5 itérations. Je suggère d'utiliser une grille 400x400. C'est 400x400x5 = moins de 1 million d'itérations qui seront rapides. Si vous n'utilisez que 5 itérations, vous n'aurez probablement pas à vous soucier de maintenir les points de couleur constante, car ils ne changeront pas trop de leur original (en fait, seuls les points situés à une distance de 5 de la couleur peuvent être affectés par la couleur). Pseudo code:

iterations = 5
for iteration in range(iterations):
    for i in range(400):
        for j in range(400):
            try:
                grid[i][j] = average(grid[i+1][j], grid[i-1][j],
                                     grid[i][j+1], grid[i][j+1])
            except IndexError:
                pass

Ok, donc les premières pensées sont que l'automatisation d'une solution parfaite au problème nécessite des mathématiques d'interpolation plutôt charnues. Sur la base du fait que vous mentionnez des images de tuiles pré-rendues, je suppose que la solution d'interpolation complète n'est pas garantie ici.

D'un autre côté, comme vous l'avez dit, terminer la carte à la main conduira à un bon résultat ... mais je suppose également que tout processus manuel pour corriger les problèmes n'est pas non plus une option.

Voici un algorithme simple qui ne donne pas un résultat parfait, mais qui est très gratifiant compte tenu du faible effort nécessaire.

Au lieu d'essayer de mélanger CHAQUE tuile de bord, (ce qui signifie que vous devez d'abord connaître le résultat du mélange des tuiles adjacentes - interpolation, ou vous devez affiner la carte entière plusieurs fois et ne pouvez pas compter sur des tuiles pré-générées) pourquoi ne pas mélanger les carreaux dans un motif en damier alterné?

[1] [*] [2]
[*] [1] [*]
[1] [*] [2]

C'est-à-dire mélanger uniquement les tuiles marquées dans la matrice ci-dessus?

En supposant que les seules étapes de valeur autorisées soient une à la fois, vous n'avez que quelques tuiles à concevoir ...

A    [1]      B    [2]      C    [1]      D    [2]      E    [1]           
 [1] [*] [1]   [1] [*] [1]   [1] [*] [2]   [1] [*] [2]   [1] [*] [1]   etc.
     [1]           [1]           [1]           [1]           [2]           

Il y aura 16 modèles au total. Si vous tirez parti de la symétrie de rotation et de réflexion, il y en aura encore moins.

«A» serait une tuile de style simple [1]. «D» serait une diagonale.

Il y aura de petites discontinuités aux coins des tuiles, mais celles-ci seront mineures par rapport à l'exemple que vous avez donné.

Si je peux, je mettrai à jour ce message avec des images plus tard.

Je jouais avec quelque chose de similaire, ce n'était pas fini pour un certain nombre de raisons; mais fondamentalement, il faudrait une matrice de 0 et 1, 0 étant le sol et 1 étant un mur pour une application de générateur de labyrinthe dans Flash. Comme AS3 est similaire à JavaScript, il ne serait pas difficile de réécrire en JS.

var tileDimension:int = 20;
var levelNum:Array = new Array();

levelNum[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1];
levelNum[1] = [1, 0, 0, 0, 0, 0, 0, 0, 1];
levelNum[2] = [1, 0, 1, 1, 1, 0, 1, 0, 1];
levelNum[3] = [1, 0, 1, 0, 1, 0, 1, 0, 1];
levelNum[4] = [1, 0, 1, 0, 0, 0, 1, 0, 1];
levelNum[5] = [1, 0, 0, 0, 0, 0, 0, 0, 1];
levelNum[6] = [1, 0, 1, 1, 1, 1, 0, 0, 1];
levelNum[7] = [1, 0, 0, 0, 0, 0, 0, 0, 1];
levelNum[8] = [1, 1, 1, 1, 1, 1, 1, 1, 1];

for (var rows:int = 0; rows < levelNum.length; rows++)
{
    for (var cols:int = 0; cols < levelNum[rows].length; cols++)
    {
        // set up neighbours
        var toprow:int = rows - 1;
        var bottomrow:int = rows + 1;

        var westN:int = cols - 1;
        var eastN:int = cols + 1;

        var rightMax =  levelNum[rows].length;
        var bottomMax = levelNum.length;

        var northwestTile =     (toprow != -1 && westN != -1) ? levelNum[toprow][westN] : 1;
        var northTile =         (toprow != -1) ? levelNum[toprow][cols] : 1;
        var northeastTile =     (toprow != -1 && eastN < rightMax) ? levelNum[toprow][eastN] : 1;

        var westTile =          (cols != 0) ? levelNum[rows][westN] : 1;
        var thistile =          levelNum[rows][cols];
        var eastTile =          (eastN == rightMax) ? 1 : levelNum[rows][eastN];

        var southwestTile =     (bottomrow != bottomMax && westN != -1) ? levelNum[bottomrow][westN] : 1;
        var southTile =         (bottomrow != bottomMax) ? levelNum[bottomrow][cols] : 1;
        var southeastTile =     (bottomrow != bottomMax && eastN < rightMax) ? levelNum[bottomrow][eastN] : 1;

        if (thistile == 1)
        {
            var w7:Wall7 = new Wall7();
            addChild(w7);
            pushTile(w7, cols, rows, 0);

            // wall 2 corners

            if      (northTile === 0 && northeastTile === 0 && eastTile === 1 && southeastTile === 1 && southTile === 1 && southwestTile === 0 && westTile === 0 && northwestTile === 0)
            {
                var w21:Wall2 = new Wall2();
                addChild(w21);
                pushTile(w21, cols, rows, 270);
            }

            else if (northTile === 0 && northeastTile === 0 && eastTile === 0 && southeastTile === 0 && southTile === 1 && southwestTile === 1 && westTile === 1 && northwestTile === 0)
            {
                var w22:Wall2 = new Wall2();
                addChild(w22);
                pushTile(w22, cols, rows, 0);
            }

            else if (northTile === 1 && northeastTile === 0 && eastTile === 0 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 1 && northwestTile === 1)
            {
                var w23:Wall2 = new Wall2();
                addChild(w23);
                pushTile(w23, cols, rows, 90);
            }

            else if (northTile === 1 && northeastTile === 1 && eastTile === 1 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 0 && northwestTile === 0)
            {
                var w24:Wall2 = new Wall2();
                addChild(w24);
                pushTile(w24, cols, rows, 180);
            }           

            //  wall 6 corners

            else if (northTile === 1 && northeastTile === 1 && eastTile === 1 && southeastTile === 0 && southTile === 1 && southwestTile === 1 && westTile === 1 && northwestTile === 1)
            {
                var w61:Wall6 = new Wall6();
                addChild(w61);
                pushTile(w61, cols, rows, 0); 
            }

            else if (northTile === 1 && northeastTile === 1 && eastTile === 1 && southeastTile === 1 && southTile === 1 && southwestTile === 0 && westTile === 1 && northwestTile === 1)
            {
                var w62:Wall6 = new Wall6();
                addChild(w62);
                pushTile(w62, cols, rows, 90); 
            }

            else if (northTile === 1 && northeastTile === 1 && eastTile === 1 && southeastTile === 1 && southTile === 1 && southwestTile === 1 && westTile === 1 && northwestTile === 0)
            {
                var w63:Wall6 = new Wall6();
                addChild(w63);
                pushTile(w63, cols, rows, 180);
            }

            else if (northTile === 1 && northeastTile === 0 && eastTile === 1 && southeastTile === 1 && southTile === 1 && southwestTile === 1 && westTile === 1 && northwestTile === 1)
            {
                var w64:Wall6 = new Wall6();
                addChild(w64);
                pushTile(w64, cols, rows, 270);
            }

            //  single wall tile

            else if (northTile === 0 && northeastTile === 0 && eastTile === 0 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 0 && northwestTile === 0)
            {
                var w5:Wall5 = new Wall5();
                addChild(w5);
                pushTile(w5, cols, rows, 0);
            }

            //  wall 3 walls

            else if (northTile === 0 && eastTile === 1 && southTile === 0 && westTile === 1)
            {
                var w3:Wall3 = new Wall3();
                addChild(w3);
                pushTile(w3, cols, rows, 0);
            }

            else if (northTile === 1 && eastTile === 0 && southTile === 1 && westTile === 0)
            {
                var w31:Wall3 = new Wall3();
                addChild(w31);
                pushTile(w31, cols, rows, 90);
            }

            //  wall 4 walls

            else if (northTile === 0 && eastTile === 0 && southTile === 1 && westTile === 0)
            {
                var w41:Wall4 = new Wall4();
                addChild(w41);
                pushTile(w41, cols, rows, 0);
            }

            else if (northTile === 1 && eastTile === 0 && southTile === 0 && westTile === 0)
            {
                var w42:Wall4 = new Wall4();
                addChild(w42);
                pushTile(w42, cols, rows, 180);
            }

            else if (northTile === 0 && northeastTile === 0 && eastTile === 1 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 0 && northwestTile === 0)
            {
                var w43:Wall4 = new Wall4();
                addChild(w43);
                pushTile(w43, cols, rows, 270);
            }

            else if (northTile === 0 && northeastTile === 0 && eastTile === 0 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 1 && northwestTile === 0)
            {
                var w44:Wall4 = new Wall4();
                addChild(w44);
                pushTile(w44, cols, rows, 90);
            }

            //  regular wall blocks

            else if (northTile === 1 && eastTile === 0 && southTile === 1 && westTile === 1)
            {
                var w11:Wall1 = new Wall1();
                addChild(w11);
                pushTile(w11, cols, rows, 90);
            }

            else if (northTile === 1 && eastTile === 1 && southTile === 1 && westTile === 0)
            {
                var w12:Wall1 = new Wall1();
                addChild(w12);
                pushTile(w12, cols, rows, 270);
            }

            else if (northTile === 0 && eastTile === 1 && southTile === 1 && westTile === 1)
            {
                var w13:Wall1 = new Wall1();
                addChild(w13);
                pushTile(w13, cols, rows, 0);
            }

            else if (northTile === 1 && eastTile === 1 && southTile === 0 && westTile === 1)
            {
                var w14:Wall1 = new Wall1();
                addChild(w14);
                pushTile(w14, cols, rows, 180);
            }

        }
        // debug === // trace('Top Left: ' + northwestTile + ' Top Middle: ' + northTile + ' Top Right: ' + northeastTile + ' Middle Left: ' + westTile + ' This: ' + levelNum[rows][cols] + ' Middle Right: ' + eastTile + ' Bottom Left: ' + southwestTile + ' Bottom Middle: ' + southTile + ' Bottom Right: ' + southeastTile);
    }
}

function pushTile(til:Object, tx:uint, ty:uint, degrees:uint):void
{
    til.x = tx * tileDimension;
    til.y = ty * tileDimension;
    if (degrees != 0) tileRotate(til, degrees);
}

function tileRotate(tile:Object, degrees:uint):void
{
    // http://www.flash-db.com/Board/index.php?topic=18625.0
    var midPoint:int = tileDimension/2;
    var point:Point=new Point(tile.x+midPoint, tile.y+midPoint);
    var m:Matrix=tile.transform.matrix;
    m.tx -= point.x;
    m.ty -= point.y;
    m.rotate (degrees*(Math.PI/180));
    m.tx += point.x;
    m.ty += point.y;
    tile.transform.matrix=m;
}

Fondamentalement, cela vérifie chaque tuile autour d'elle de gauche à droite, de haut en bas et suppose que les tuiles de bord sont toujours 1. J'ai également pris la liberté d'exporter les images sous forme de fichier à utiliser comme clé:

Ceci est incomplet et probablement une manière piratée d'y parvenir, mais j'ai pensé que cela pourrait être un avantage.

Edit: Capture d'écran du résultat de ce code.

Je suggérerais quelques choses:

• peu importe ce qu'est la tuile «centrale», non? il pourrait être 2, mais si tous les autres sont 1, il afficherait 1?

• il importe seulement quels sont les coins, quand il y a une différence dans les voisins immédiats du haut ou du côté. Si tous les voisins immédiats sont 1 et un coin est 2, il affichera 1.

• Je précalculerais probablement toutes les combinaisons possibles de voisins, créant un tableau d'index 8 avec les quatre premiers indiquant les valeurs des voisins haut / bas, et le second indiquant les diagonales:

arêtes [N] [E] [S] [W] [NE] [SE] [SW] [NW] = quel que soit le décalage dans le sprite

donc dans votre cas, [2] [2] [1] [1] [2] [2] [1] [1] = 4 (le 5ème sprite).

dans ce cas, [1] [1] [1] [1] serait 1, [2] [2] [2] [2] serait 2, et le reste devrait être calculé. Mais la recherche d'une tuile particulière serait triviale.