Diseño de mosaico aleatorio

Question

Necesito colocar mosaicos en una grilla grande que irradia desde un punto central de una manera que se ve orgánica y aleatoria. Las fichas nuevas necesitarán encontrar un espacio abierto en la cuadrícula que toque al menos otra ficha.

¿Alguien puede indicarme el derecho de dirigir a cualquier cosa que pueda ayudar con esto? ¿O algunos conceptos básicos que puedo leer que están en esta línea?

Por ejemplo, en esta imagen, hay una forma ya creada (amarillo) y puedo recibir una nueva ficha, que puede ser 1x1, 2x2 o 3x3. Tratando de encontrar una buena manera de averiguar dónde puedo colocar la nueva ficha para que toque la cantidad máxima de fichas actuales.

foto: alt text http://osomer.com/grid.JPG

Answer 1

Como alternativa, puede acercarse a este problema, ya que las baldosas amarillas "erosionar" lejos en el azul/fondo. Para hacer esto, en cada paso, haga que un mosaico amarillo agregue un número fijo a la "suma de erosión" E de todas las fichas de fondo que lo rodean en una dirección cardinal (y tal vez una fracción de eso a las fichas de fondo vecinas diagonalmente).

Luego, cuando llega el momento de colocar un nuevo mosaico, puede, para cada mosaico de fondo, elegir un número aleatorio de 0 a E; el más grande es "erosionado". Alternativamente, podría hacer una elección aleatoria simple ponderada, con E siendo sus ponderaciones.

Para baldosas de 2x2 o 3x3, puede elegir solo baldosas que convenientemente "encajen" en un cuadrado de 2x2 o 3x3 (es decir, un azulejo 2x2 o 3x3 en su borde, para que no cause superposición con fichas ya colocadas). Pero, en realidad, nunca obtendrás algo que parezca tan natural como la colocación de baldosas/erosión uno a uno.

Puede ahorrar tiempo recalculando las sumas de erosión haciendo que persistan en cada iteración, solo cuando agrega una nueva loseta, aumente las sumas de erosión de las que la rodean (un simple +=). En este punto, es esencialmente lo mismo que se sugirió otra respuesta, aunque con una perspectiva/filosofía diferente.

Una cuadrícula muestra de Erosión Así resume E, con los vecinos directos cardinales siendo 4, y los vecinos diagonales siendo 1:

Erosion Sums http://img199.imageshack.us/img199/4766/erosion.png

Los que tienen un mayor E tienen más probabilidades de ser "erosionado" de distancia; por ejemplo, en este caso, las dos entradas pequeñas en las caras oeste y sur son más propensas a ser erosionadas por el amarillo, seguidas por las bahías más pequeñas en las caras norte y este. Lo más probable es que sean los que apenas tocan el amarillo en una esquina. Puede decidir cuál de ellas asignando un número aleatorio de 0 a E para cada azulejo y erosionando el que tiene el número aleatorio más alto, o haciendo una selección aleatoria ponderada simple, o mediante cualquier método de decisión de su elección.

Answer 2

Por puramente aleatoria, se empieza con una cuadrícula vacía y una lista de "candidato" (también vacío).

Coloque la primera ficha en el centro de la cuadrícula, luego agregue cada ficha adyacente a la que acaba de colocar en la lista de "candidatos". Luego, en cada turno, elige una entrada aleatoria en la lista "candidato" y coloca una ficha allí. Mire cada ubicación adjunta de la grilla al lado de donde acaba de colocar el mosaico, y para cada uno que también esté vacío, póngalo en la lista de "candidatos" para la próxima vez (si no está ya allí).

Para evitar crear agujeros en la cuadrícula de mosaico, aumente la probabilidad de seleccionar una ubicación de cuadrícula según el número de mosaicos adyacentes que ya estén llenos (de modo que si solo una casilla adyacente ya está llena, probablemente sea baja). está todo lleno, tendrá una probabilidad muy alta).

En pseudocódigo:

grid = new array[width,height]; 
candidates = new list(); 

function place_tile(x,y) { 
    // place the tile at the given location 
    grid[x,y] = 1; 

    // loop through all the adjacent grid locations around the one 
    // we just placed 
    for(y1 = y - 1; y1 < y + 1; y1++) { 
     for(x1 = x - 1; x1 < x + 1; x1++) { 
      // if this location doesn't have a tile and isn't already in 
      // the candidate list, add it 
      if (grid[x,y] != 1 && !candidates.contains(x1,y1)) { 
       candidates.add(x1,y1); 
      } 
     } 
    } 
} 

// place the first tile in the centre 
place_tile(width/2, height/2); 

while (!finished) { 
    // choose a random tile from the candidate list 
    int index = rand(0, candidates.length - 1); 

    // place a tile at that location (remove the entry from 
    // the candidate list) 
    x, y = candidates[index]; 
    candidates.remove(index); 
    place_tile(x, y); 
} 

Answer 3

El problema con su pregunta es que 'orgánico y aleatorio' puede ser muchas cosas diferentes. Te voy a enseñar dos enlaces

• generar random fractal terrain (busque en la sección de 'cielos despejados' e imagina que usted le da vuelta a B/W, o en su caso amarillo/fondo).
• simulando erosion (mira la imagen bajo 'erosionar')

Las dos muestras anteriores son 'orgánico y al azar' para mí, pero es posible que no estar satisfecho con ellos. Por lo tanto, creo que tendrá que definir mejor qué es "orgánico y aleatorio".

Por ahora, me quedo con su definición de la regla de guía para la adición de nuevos azulejos (pero no creo que sea necesariamente el mismo problema), que leí como:

Dadas dos formas (mapas de bits suponiendo) encuentra la posición relativa de los formas tales que el número de lados tocar es máxima

I también asumirá

• superposición no se permite
• puede dejar agujeros dentro de la resultante, fusionado forma
• puede no girar formas

Bajo tales condiciones que necesita para poner a prueba a menos de x Y soluciones y en cada uno lo que necesita - descartarla si hay una superposición - descartarla si no se toquen - si tocan comienzan a contar el número de aristas que son comunes los tres de las pruebas anteriores se puede hacer de constante de tiempo b y escaneando todos los mosaicos amarillos (cuyo número es konst x * y)

Entonces, lo anterior se puede hacer fácilmente en O (n^4), ¿es eso suficiente para usted?

Answer 4

Calcule un árbol de expansión aleatorio para el gráfico dual, es decir, la cuadrícula cuyos vértices son los centros de sus celdas. Para eso, comience en el centro de la cuadrícula y realice una búsqueda aleatoria en profundidad. Luego grafica las celdas para aumentar la distancia del árbol desde el centro.