152 votes

Carte de carrelage algorithme

HTML5 & Javascript RPG

  • 200 x 200 carte
  • Carte générée à partir de heightmap
  • 6 types de tuiles
  • 24x24 px tuiles
  • Exemple De Carte

enter image description here

Ok, donc je suis en train d'écrire un jeu en JavaScript HTML5, dans lequel un 200x200 carte est générée à partir d'un créés de manière aléatoire heightmap. J'ai un algorithme assez simple qui extrait la valeur de la couleur de chaque pixel de l'image et le convertit en un nombre entier (de 0 à 5) en fonction de sa position entre (0 à 255), ce qui correspond à une tuile en tuile dictionnaire. Cette 200x200 tableau est ensuite transmis au client.

Le moteur détermine ensuite les tuiles à partir des valeurs du tableau et dessine sur la toile. Donc, je termine avec des mondes qui ont des caractéristiques réalistes recherche: des montagnes, des mers, etc.

Maintenant, la prochaine chose que je voulais faire était d'appliquer une tuile blender algorithme de sorte que si une tuile est à côté d'une tuile qui n'est pas du même type, il semble taché. L'exemple de la carte ci-dessus est ce que le joueur voit dans leur minimap, qu'ils voient à l'écran le rendu de la section marquée par le rectangle blanc; la fenêtre d'affichage. Lorsque les tuiles sont rendus avec leurs images plutôt que comme de simples pixels de la couleur.

Ceci est un exemple de ce que l'utilisateur voit dans la carte (pas le même emplacement que la fenêtre ci-dessus montre!)

enter image description here

Il est de ce point de vue que je veux la transition de se produire sur, aucune modification ne doit être faite à la mini-carte.

L'Algorithme

J'ai donc formulé un, ce qui semblait simple algorithme qui permettrait de parcourir l'ensemble de la carte qui était disponible dans la fenêtre d'affichage et de rendu d'une autre image sur le dessus de la tuile, si il était à côté d'une tuile de type différent. (Sans modification de la carte! Juste rendu quelques images supplémentaires.) L'idée de l'algorithme a été pour le profil de la tuile courante pays voisins:

An example of a tile profile

C'est un scénario d'exemple de ce que le moteur pourrait avoir à rendre, avec la tuile courante étant celle marquée avec le X. Un 3x3 tableau est créé et les valeurs sont lues dans. Donc, pour cet exemple, le tableau devrait ressembler.

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

Mon idée était alors de travailler sur une série de cas possibles configurations de tuiles. Sur un très simple niveau:

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

Ce qui donne ce résultat:

Result

Qui fonctionne comme une transition de [0][1] [1][1], mais pas à partir de [1][1] [2][1], où un bord dur reste. J'ai donc pensé que, dans ce cas un coin de la tuile devra être utilisé. J'ai créé deux 3x3 feuilles sprite que j'ai pensé serait de détenir toutes les combinaisons possibles de tuiles qui pourraient être nécessaires. Puis-je répliqué ce pour toutes les tuiles qu'il y a dans le jeu (Les zones blanches sont transparentes). Ce qui nous donne 16 tuiles pour chaque type de tuile (Le centre de la dalle sur chaque spritesheet ne sont pas utilisés.)

SandSand2

Le Résultat Idéal

Ainsi, avec ces nouvelles tuiles et l'algorithme correct, l'exemple de l'article devrait ressembler à ceci:

Correct

Chaque tentative que j'ai faite a échoué si, il y a toujours une faille dans l'algorithme, et les patrons finissent étrange. Je n'arrive pas à obtenir tous les cas et à l'aide de cas semble être une mauvaise façon de le faire. En raison des circonstances étranges qui peuvent se produire avec des mélanges d'avoir à être utilisés ensemble pour créer une ligne régulière.

Une fois, j'ai développé un jeu avec un semblable carrelage technique à ce, à l'exception de tout ce qui a été fait dans un éditeur de carte, donc j'ai lissé manuellement les tuiles en ajoutant les images sur le dessus, de sorte que la technique d'imagerie fonctionne, il faut juste l'algorithme de le faire.

Une Solution?

Donc, si quelqu'un pouvait fournir une solution de rechange à la façon dont j'ai pu créer cet effet, ou dans quelle direction aller pour l'écriture de l'algorithme de profilage, j'en serais très reconnaissante!

117voto

user1884905 Points 2733

L'idée de base de cet algorithme est d'utiliser une étape de prétraitement pour trouver tous bords et de sélectionner le bon lissage de la tuile en fonction de la forme de l'arête.

La première étape serait de trouver tous les bords. Dans l'exemple ci-dessous le bord des tuiles marquées d'un X sont toutes les tuiles vertes avec un bronzage de tuile, de l'un ou plusieurs de leurs huit tuiles voisines. Avec différents types de terrains, cette condition pourrait se traduire par un carreau d'être d'un bord de la tuile, si il a des voisins du bas-relief-nombre.

Edge tiles.

Une fois toutes les tuiles de rives sont détectés, la prochaine chose à faire est de choisir le bon lissage de la dalle pour chaque bord de la tuile. Voici ma représentation de votre lissage des tuiles.

Smoothing tiles.

Notez qu'il y a en fait pas beaucoup de différents types de carreaux. Nous avons besoin de huit extérieur carreaux d'un de 3x3 cases, mais seulement les quatre coins du carré de l'autre depuis le straight-edge tuiles sont déjà présents dans la première place. Cela signifie qu'il y a au total 12 différents cas, nous devons faire la distinction entre les deux.

Maintenant, en regardant d'un bord de la tuile, nous pouvons déterminer de quelle manière la frontière devient par la recherche à ses quatre plus proche voisin de tuiles. En marquant le bord de la tuile avec X comme ci-dessus, nous avons six cas différents.

Six cases.

Ces cas sont utilisés pour déterminer le correspondant de lissage de la tuile et nous pouvons nombre le lissage des tuiles en conséquence.

Smoothed tiles with numbers.

Il y a toujours un choix a ou b pour chaque cas. Cela dépend de quel côté l'herbe est sur. Une façon de déterminer ce qui pourrait être de garder une trace de l'orientation de la frontière, mais sans doute la façon la plus simple de le faire est de choisir une tuile à côté du bord et voir de quelle couleur il est. L'image ci-dessous montre les deux cas, 5a) et 5b) et qui peut être distingué entre, par exemple, la vérification de la couleur de la partie supérieure droite de la tuile.

Choosing 5a or 5b.

La dernière énumération de l'exemple original ressemblerait alors à ceci.

Final enumeration.

Et après avoir sélectionné le bord correspondant de la tuile de la frontière ressemblerait à quelque chose comme ça.

Final result.

Comme note finale, je pourrais dire que ce serait de travailler aussi longtemps que la frontière est peu régulière. Plus précisément, le bord des tuiles qui n'ont pas exactement deux tuiles de rives de leurs voisins devront être traités séparément. Ce sera le cas pour des tuiles de rives sur le bord de la carte, ce qui aura un avantage unique voisin et très étroites morceaux de terrain où le nombre de voisins des tuiles de rives pourrait être trois ou même quatre.

12voto

robert king Points 5369

La suite de carré représente une plaque de métal. Il y a une "évacuation de chaleur" par le coin en haut à droite. Nous pouvons voir comment la température de ce point reste constante, la plaque de métal qui converge vers une constante de la température en chaque point, étant naturellement plus chaud près du sommet:

heatplate

Le problème de trouver la température en chaque point peut être résolu en tant que "valeur Limite de problème". Toutefois, la façon la plus simple de travailler de la chaleur à chaque point est le modèle de la plaque de grille. Nous savons que les points sur la grille à température constante. Nous avons fixé la température de tous les inconnus points à la température de la pièce (comme si l'évent, qui venait d'être allumé). Nous avons ensuite laisser la chaleur se propager à travers la plaque jusqu'à ce que nous atteindre la convergence. Cela se fait par itération: nous itérer sur chaque (i,j) point. Nous avons mis le point(i,j) = ((i+1, j)+(i-1,j)+(i, j+1)+point(i,j-1))/4 [, à moins que le point(i,j) a une évacuation de chaleur de température constante]

Si vous appliquez cela à votre problème, il est très similaire, juste dans la moyenne des couleurs au lieu de températures. Vous auriez probablement besoin d'environ 5 itérations. Je vous suggère d'utiliser un 400x400 de la grille. C'est 400x400x5 = moins de 1 million d'itérations qui sera rapide. Si vous utilisez uniquement les 5 itérations vous n'aurez probablement pas besoin de s'inquiéter à propos de la tenue de tout les points de couleur constante, comme ils l'habitude de maj trop de leur origine (en fait, seuls les points à l'intérieur distance de 5 à partir de la couleur peut être effectuée par la couleur). Le 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

5voto

perfectionist Points 1608

Ok, donc tout d'abord les pensées sont que l'automatisation d'une solution parfaite à ce problème exige une certaine plutôt charnue interpolation de mathématiques. Basé sur le fait que vous mentionnez pré-rendus mosaïque d'images, je suppose que la totalité de l'interpolation de la solution n'est pas justifié ici.

D'autre part, comme vous l'avez dit, en finir avec la carte à la main aboutir à un bon résultat... mais j'ai aussi supposer que tout le processus manuel pour corriger les bugs est pas non plus une option.

Voici un algorithme simple qui ne donne pas un résultat parfait, mais c'est très gratifiant, basé sur le faible effort qu'il faut.

Au lieu d'essayer de mélanger TOUS les bord de la tuile, (ce qui signifie que vous besoin de connaître le résultat du mélange de l'tuiles adjacentes de la première interpolation, ou vous avez besoin pour affiner l'ensemble de la carte plusieurs fois et ne peut pas compter sur la pré-généré tuiles), pourquoi ne pas mélanger les carreaux dans une alternance de checker-conseil de modèle?

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

I. e. seule mélanger les tuiles joué dans la matrice ci-dessus?

En supposant que les seules autorisées les étapes de valeur sont l'un-à-un-temps, vous n'avez que quelques tuiles à la conception...

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 profitez de la rotation et de reflectional symétrie, il y aura encore moins.

"A" serait une plaine [1] le style de la tuile. "D" serait une diagonale.

Il y aura de petites discontinuités dans les coins des carreaux, mais de façon mineure par rapport à l'exemple que vous avez donné.

Si je peux, je mettrai à jour ce post avec les images plus tard.

2voto

Ben Points 4012

J'ai été jouer avec quelque chose de semblable à cela, ce n'était pas fini pour un certain nombre de raisons; mais, fondamentalement, il faudrait une matrice de 0 et de 1, 0 étant le terrain et 1 étant un mur pour un générateur de labyrinthe application dans Flash. Depuis AS3 est similaire à JavaScript, il ne serait pas difficile de le 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;
}

En gros, cela vérifie chaque tuile autour d'elle allant de gauche à droite, de haut en bas et suppose que des tuiles de rives sont toujours de 1. J'ai aussi pris la liberté d'exporter les images dans un fichier à utiliser comme une clé:

Wall tiles

C'est incomplète et probablement un hacky façon d'atteindre cet objectif, mais j'ai pensé qu'il pourrait être d'une certaine utilité.

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

Generated Result

1voto

elijah Points 2329

Je voudrais suggérer quelques petites choses:

  • il n'a pas d'importance ce que le "centre" de la tuile est, droite? il pourrait être 2, mais si tous les autres sont à 1, ce serait montrer 1?

  • il importe seulement que les coins sont, lorsqu'il existe une différence dans le les voisins immédiats vers le haut ou le côté. Si tous les voisins immédiats sont 1, et l'angle est de 2, ce serait montrer 1.

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

bords[N][E][S][W][NE][SE][SW][NW] = quelle que soit la position dans le sprite

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

dans ce cas, [1][1][1][1] serait 1, [2][2][2][2] serait 2, et le reste devra être travaillé. Mais la recherche pour une tuile particulière serait trivial.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X