El rompecabezas "relleno de patrón con mosaicos"

Question

He encontrado un problema interesante al programar un generador de nivel aleatorio para un juego basado en fichas. Implementé un solucionador de fuerza bruta para él, pero es exponencialmente lento y definitivamente no apto para mi caso de uso. No estoy buscando necesariamente una solución perfecta, estaré satisfecho con una solución "lo suficientemente buena" que funcione bien. Declaración

Problema:

Digamos que tiene todos o un subconjunto de los siguientes azulejos disponibles (esto es la combinación de todos los posibles patrones de 4 bits asignada a la derecha, arriba, izquierda y descendente):

alt text http://img189.imageshack.us/img189/3713/basetileset.png

se le proporciona una cuadrícula donde se marcan algunas células (verdadero) y otros no (falso). Esto podría ser generado por un algoritmo de ruido perlin, por ejemplo. El objetivo es llenar este espacio con mosaicos para que haya tantas fichas complejas como sea posible. Idealmente, todas las fichas deberían estar conectadas. Puede que no haya solución para algunos valores de entrada (mosaicos disponibles + patrón). Siempre hay al menos una solución si el mosaico no conectado superior izquierdo está disponible (es decir, todas las celdas de patrón se pueden llenar con ese mosaico).

Ejemplo:

Imágenes de izquierda a derecha: la disponibilidad de baldosas (azulejos verdes se pueden utilizar, rojo no puede), modelo para llenar y una solución

alt text http://img806.imageshack.us/img806/2391/sampletileset.png + alt text http://img841.imageshack.us/img841/7/samplepattern.png = alt text http://img690.imageshack.us/img690/2585/samplesolution.png

Lo que probé:

Mi implementación de fuerza bruta intenta todas las posibilidades ible azulejo en todas partes y realiza un seguimiento de las soluciones que se encontraron. Finalmente, elige la solución que maximiza el número total de conexiones salientes de cada una de las teselas. El tiempo que toma es exponencial con respecto al número de mosaicos en el patrón. Un patrón de 12 fichas tarda unos segundos en resolverse.

Notas:

Como ya he dicho, el rendimiento es más importante que la perfección. Sin embargo, la solución final debe estar correctamente conectada (no hay mosaico apuntando a una ficha que no apunte a la ficha original). Para dar una idea del alcance, me gustaría manejar un patrón de 100 fichas en menos de 2 segundos.

Answer 1

Como base, eche un vistazo a an earlier answer I gave on searching. Los programas de búsqueda de alpinismo son una herramienta que todo programador debería tener en su arsenal, ya que funcionan mucho mejor que los simples solucionadores de fuerza bruta.

Aquí, incluso un algoritmo de búsqueda relativamente malo tiene como ventaja el hecho de que no generará tableros ilegales, reduciendo en gran medida el tiempo de ejecución esperado.

Answer 2

Para instancias de 100 mosaicos, creo que un programa dinámico basado en una descomposición de tallado del gráfico de entrada podría ajustarse a la factura.

Talla descomposición

En la teoría de grafos, una descomposición talla de un gráfico es una partición binaria recursiva de sus vértices.Por ejemplo, aquí es un gráfico

1--2--3 
| | 
| | 
4--5 

y uno de sus descomposiciones talla

 {1,2,3,4,5} 
    /  \ 
    {1,4}  {2,3,5} 
/ \  / \ 
{1} {4} {2,5}  {3} 
     / \ 
     {2} {5}. 

La anchura de una descomposición talla es el número máximo de bordes dejando una de sus particiones. En este caso, {2,5} tiene bordes salientes 2--1, 2--3, y 5--4, por lo que la anchura es de 3. La anchura de una partición-árbol de estilo kd de una cuadrícula de 10 x 10 es 13.

La talla-anchura de una el gráfico es el ancho mínimo de una descomposición de tallado. Se sabe que los gráficos planar (en particular, subgrafos de grillas) con n vértices tienen ancho de corte O (√n), y la constante de O grande es relativamente pequeña.

dinámica de programa

Dado un gráfico de entrada n-vértice y una descomposición talla de la anchura w, hay un O (2 ^w n) -Tiempo algoritmo para calcular la elección óptima de baldosas. Este tiempo de ejecución crece rápidamente en w, por lo que debe intentar descomponer algunas entradas de muestra a mano para tener una idea de qué tipo de rendimiento esperar.

El algoritmo funciona en el árbol de descomposición de abajo arriba. Deje que X sea una partición, y que F sea el conjunto de aristas que salen de X. Hacemos una tabla que mapea cada una de 2 ^{| F |} posibilidades de presencia o ausencia de aristas en F a la suma óptima en X bajo las restricciones especificadas (-Infinidad si no hay solución). Por ejemplo, con la partición {1,4}, tenemos entradas

{} -> ?? 
{1--2} -> ?? 
{4--5} -> ?? 
{1--2,4--5} -> ?? 

para las particiones de las hojas con un solo vértice, el subconjunto de F determina completamente la baldosa, así que es fácil de llenar en el número de conexiones (si la baldosa es válido) o -Infinito de lo contrario. Para las otras particiones, al calcular una entrada de la tabla, intente con todos los patrones de conectividad diferentes para los bordes que se encuentran entre los dos elementos secundarios.

Por ejemplo, supongamos que tenemos piezas

     | 
. .- .- -. . 
    |     

La mesa para {1} es

{} -> 0 
{1--2} -> 1 
{1--4} -> -Infinity 
{1--2,1--4} -> 2 

La mesa para {4} es

{} -> 0 
{1--4} -> 1 
{4--5} -> 1 
{1--4,4--5} -> -Infinity 

Ahora vamos a calcular la tabla de {1,4}. Para {}, sin el borde 1--4 tenemos el puntaje 0 para {1} (entrada {}) más el puntaje 0 para {4} (entrada {}). Con el borde 1--4 tenemos la puntuación -Infinity + 1 = -Infinity (entradas {1--4}).

{} -> 0 

Para {1--2}, las puntuaciones son 1 + 0 = 1 sin 1--4 y 2 + 1 = 3 con.

{1--2} -> 3 

Continuando.

{4--5} -> 0 + 1 = 1 (> -Infinity = -Infinity + (-Infinity)) 
{1--2,4--5} -> 1 + 1 = 2 (> -Infinity = 2 + (-Infinity)) 

Al final podemos usar las tablas para determinar una solución óptima.

Encontrar una descomposición talla

Hay algoritmos sofisticados para encontrar buenos descomposiciones de talla, pero no los puedan necesitar. Pruebe un esquema de partición de espacio binario simple.

Answer 3

Creo que puedo tener una idea mejor. No lo probé, pero estoy bastante seguro de que será más rápido que una solución puramente de fuerza bruta para zonas grandes.

Primero, cree un conjunto vacío (un "conjunto" es una colección que solo contiene objetos únicos) de nodos. Esta colección se usará para identificar qué mosaicos tienen conexiones rotas que deben corregirse.

Complete las estructuras de datos para representar el tablero con las piezas que están disponibles, utilizando las que mejor se ajustan según sus criterios personales sin tener en cuenta la exactitud de la solución. Esto seguramente te llevará a un estado inválido, pero está bien por ahora. Itera a través del tablero y encuentra todos los mosaicos que tienen conexiones que conducen a ninguna parte. Agrégalos al conjunto de fichas rotas.

Ahora, itere a través del conjunto. Cambie las fichas a las que hace referencia reduciendo el número de conexiones (de lo contrario, podría entrar en un bucle infinito) para que no tengan una conexión interrumpida, respetando las piezas disponibles actualmente. Comprueba a sus vecinos nuevamente, y si rompiste las conexiones con otras teselas, agrégalas al conjunto de las que están rotas también.

Una vez que el conjunto de conexiones rotas estará vacío, debe tener un patrón fino. Sin embargo, tenga en cuenta que tiene una advertencia importante: podría tender a simplificar en exceso los patrones, ya que la fase de "fijación" siempre intentará reducir el número de conexiones. Puede que tengas la suerte de obtener patrones interesantes ya que esto podría verse muy afectado por la primera pieza que coloques en cada azulejo.