javascript - google - Algoritmo de mosaico de mapas

google maps html5

Question

El mapa

Estoy haciendo un RPG basado en mosaico con Javascript, usando mapas de altura de ruido perlin, y luego asignando un tipo de mosaico basado en la altura del ruido.

Los mapas terminan pareciéndose a algo así (en la vista de minimapa).

Tengo un algoritmo bastante simple que extrae el valor de color de cada píxel en la imagen y lo convierte en un número entero (0-5) dependiendo de su posición entre (0-255) que corresponde a un mosaico en el diccionario de mosaico. Esta matriz de 200x200 se pasa luego al cliente.

El motor luego determina las fichas de los valores en la matriz y las dibuja en el lienzo. Por lo tanto, termino con mundos interesantes que tienen características de aspecto realista: montañas, mares, etc.

Ahora, lo siguiente que quería hacer era aplicar algún tipo de algoritmo de fusión que hiciera que las teselas se mezclaran perfectamente con las de sus vecinos, si el vecino no es del mismo tipo. El mapa de ejemplo de arriba es lo que el jugador ve en su minimapa. En pantalla, ven una versión representada de la sección marcada por el rectángulo blanco; donde las teselas se representan con sus imágenes en lugar de píxeles de un solo color.

Este es un ejemplo de lo que el usuario vería en el mapa, pero no es la misma ubicación que muestra la ventana gráfica anterior.

Es en esta vista que quiero que ocurra la transición.

El algoritmo

Se me ocurrió un algoritmo simple que atravesaría el mapa dentro de la ventana gráfica y mostraría otra imagen en la parte superior de cada mosaico, siempre que estuviera al lado de una ficha de diferente tipo. (¡No se cambia el mapa! Simplemente se renderizan algunas imágenes adicionales.) La idea del algoritmo era hacer un perfil de los vecinos del mosaico actual:

Este es un escenario de ejemplo de lo que el motor podría tener que representar, con el mosaico actual marcado con la X.

Se crea una matriz de 3x3 y se leen los valores que la rodean. Por lo tanto, para este ejemplo, la matriz se vería.

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

Mi idea fue resolver una serie de casos para las posibles configuraciones de mosaicos. En un nivel muy 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]
     ...
}

Lo que le da este resultado:

Que funciona como una transición de [0][1] a [1][1] , pero no de [1][1] a [2][1] , donde queda un borde duro. Así que pensé que en ese caso tendría que usarse un azulejo de esquina. Creé dos hojas de sprite de 3x3 que pensé que contendrían todas las combinaciones posibles de fichas que pudieran ser necesarias. Luego repliqué esto para todas las fichas que hay en el juego (las áreas blancas son transparentes). Esto termina siendo 16 teselas para cada tipo de mosaico (no se utilizan las teselas centrales de cada lámina de sprites).

El resultado ideal

Entonces, con estos nuevos mosaicos y el algoritmo correcto, la sección de ejemplo se vería así:

Sin embargo, cada intento que he hecho ha fallado, siempre hay algún defecto en el algoritmo y los patrones terminan siendo extraños. Parece que no puedo solucionar todos los casos y, en general, parece una forma pobre de hacerlo.

¿Una solución?

Entonces, si alguien pudiera proporcionar una solución alternativa sobre cómo podría crear este efecto, o qué dirección tomar para escribir el algoritmo de creación de perfiles, ¡entonces estaría muy agradecido!

Answer 1

El siguiente cuadrado representa una placa de metal. Hay un "respiradero de calor" en la esquina superior derecha. Podemos ver cómo a medida que la temperatura de este punto permanece constante, la placa de metal converge a una temperatura constante en cada punto, siendo naturalmente más caliente cerca de la parte superior:

El problema de encontrar la temperatura en cada punto se puede resolver como un "problema de valor límite". Sin embargo, la forma más sencilla de calcular el calor en cada punto es modelar la placa como una cuadrícula. Conocemos los puntos en la grilla a temperatura constante. Configuramos la temperatura de todos los puntos desconocidos para que sea la temperatura ambiente (como si la ventilación hubiera sido recién encendida). Luego dejamos que el calor se extienda a través del plato hasta que lleguemos a la convergencia. Esto se hace por iteración: iteramos a través de cada punto (i, j). Establecemos el punto (i, j) = (punto (i + 1, j) + punto (i-1, j) + punto (i, j + 1) + punto (i, j-1)) / 4 [a menos el punto (i, j) tiene un respiradero de temperatura constante]

Si aplica esto a su problema, es muy similar, solo colores promedio en lugar de temperaturas. Probablemente necesitarías alrededor de 5 iteraciones. Sugiero usar una grilla de 400x400. Eso es 400x400x5 = menos de 1 millón de iteraciones que serán rápidas. Si solo usa 5 iteraciones, probablemente no tendrá que preocuparse por mantener los puntos de color constante, ya que no cambiarán demasiado de su original (de hecho, solo los puntos dentro de la distancia 5 del color pueden verse afectados por el color). Pseudo código:

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

Answer 2

Estaba jugando con algo similar a esto, no fue terminado por una serie de razones; pero básicamente tomaría una matriz de 0 y 1, 0 siendo el suelo y 1 una pared para una aplicación de generador de laberinto en Flash. Como AS3 es similar a JavaScript, no sería difícil reescribir 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;
}

Básicamente, esto verifica cada mosaico a su alrededor yendo de izquierda a derecha, de arriba a abajo y asume que las fichas de borde son siempre 1. También me he tomado la libertad de exportar las imágenes como un archivo para usar como clave:

Esto es incompleto y probablemente sea una forma estrafalaria de lograr esto, pero pensé que podría ser de algún beneficio.

Editar: captura de pantalla del resultado de ese código.

Answer 3

La idea básica de este algoritmo es utilizar un paso de preproceso para encontrar todos los bordes y luego seleccionar el mosaico correcto de acuerdo con la forma del borde.

El primer paso sería encontrar todos los bordes. En el siguiente ejemplo, las fichas de borde marcadas con una X son todas las fichas verdes con una ficha de color tostado como una o más de las ocho fichas adyacentes. Con diferentes tipos de terreno, esta condición podría traducirse en que una loseta sea una loseta de borde si tiene vecinos de menor número de terreno.

Una vez que se detectan todas las fichas de borde, lo siguiente que hay que hacer es seleccionar la ficha de suavizado correcta para cada ficha de borde. Aquí está mi representación de tus alisados.

Tenga en cuenta que en realidad no hay tantos tipos diferentes de mosaicos. Necesitamos las ocho fichas externas de uno de los cuadros de 3x3, pero solo los cuatro cuadrados de esquina del otro ya que las fichas de borde recto ya se encuentran en el primer cuadro. Esto significa que hay en total 12 casos diferentes que debemos distinguir.

Ahora, mirando a un azulejo de borde, podemos determinar en qué dirección gira el límite mirando sus cuatro fichas vecinas más cercanas. Al marcar una losa de borde con X justo arriba, tenemos los siguientes seis casos diferentes.

Estos casos se usan para determinar la loseta de alisado correspondiente y podemos numerar las losetas de alisado en consecuencia.

Todavía hay una opción de aob para cada caso. Esto depende de qué lado esté la hierba. Una forma de determinar esto podría ser realizar un seguimiento de la orientación del límite, pero probablemente la forma más sencilla de hacerlo es elegir una ficha al lado del borde y ver qué color tiene. La imagen a continuación muestra los dos casos 5a) y 5b) que se pueden distinguir entre, por ejemplo, verificar el color de la ficha superior derecha.

La enumeración final para el ejemplo original se vería así.

Y después de seleccionar el azulejo de borde correspondiente, el borde se vería así.

Como nota final, podría decir que esto funcionaría siempre que el límite sea algo regular. Más precisamente, las fichas de borde que no tienen exactamente dos fichas de borde como sus vecinos tendrán que tratarse por separado. Esto ocurrirá para las fichas de borde en el borde del mapa que tendrá un solo borde vecino y para las partes del terreno muy estrechas donde el número de fichas de borde vecinas podría ser de tres o incluso cuatro.

Answer 4

Ok, las primeras ideas son que la automatización de una solución perfecta para el problema requiere algunas matemáticas de interpolación bastante carnosas. Basado en el hecho de que menciona imágenes de mosaicos pretratados, supongo que la solución de interpolación completa no está garantizada aquí.

Por otro lado, como dijiste, terminar el mapa a mano conducirá a un buen resultado ... pero también asumo que ningún proceso manual para arreglar fallas tampoco es una opción.

Aquí hay un algoritmo simple que no da un resultado perfecto, pero que es muy gratificante en función del bajo esfuerzo que requiere.

En lugar de intentar mezclar TODAS las fichas de borde, (lo que significa que primero debes saber el resultado de mezclar las fichas adyacentes - interpolación, o necesitas refinar todo el mapa varias veces y no puedes confiar en las fichas pregeneradas) ¿por qué no mezclar los mosaicos en un patrón de tablero de ajedrez alternante?

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

Es solo mezclar los azulejos que aparecen en la matriz de arriba?

Suponiendo que los únicos pasos permitidos en el valor son uno a la vez, solo tiene unas pocas fichas para diseñar ...

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]           

Habrá 16 patrones en total. Si aprovecha la simetría de rotación y reflexión, habrá aún menos.

''A'' sería una ficha de estilo simple [1]. ''D'' sería una diagonal.

Habrá pequeñas discontinuidades en las esquinas de las teselas, pero estas serán menores en comparación con el ejemplo que proporcionó.

Si puedo, actualizaré esta publicación con imágenes más adelante.

Answer 5

Sugeriría algunas cosas:

• no importa cuál sea el mosaico "central", ¿verdad? podría ser 2, pero si todos los demás son 1, mostraría 1?

• solo importa lo que son las esquinas, cuando hay una diferencia en los vecinos inmediatos a la parte superior o lateral. Si todos los vecinos inmediatos son 1, y una esquina es 2, mostraría 1.

• Probablemente precalcularé todas las combinaciones posibles de vecinos, creando una matriz de índices de 8 con los primeros cuatro indicando los valores de los vecinos superiores e inferiores, y el segundo indicando las diagonales:

bordes [N] [E] [S] [W] [NE] [SE] [SW] [NW] = cualquier desplazamiento en sprite

entonces en tu caso, [2] [2] [1] [1] [2] [2] [1] [1] = 4 (el quinto sprite).

en este caso, [1] [1] [1] [1] sería 1, [2] [2] [2] [2] sería 2 y el resto tendría que resolverse. Pero la búsqueda de un mosaico en particular sería trivial.