¿Cómo puedo asegurarme de que se pueda llenar una cuadrícula con piezas similares al Tetris?

Estoy pensando en hacer un juego de rompecabezas donde el objective es llenar una cuadrícula con piezas de rompecabezas en forma (por ejemplo, las forms clásicas de Tetris).

¿Cómo puedo generar un set de piezas que se pueda garantizar que se utilizarán para llenar la cuadrícula, sin dejar huecos? ¿Cómo podría adaptar este algorithm para escalar la dificultad del rompecabezas resultante?

Este es un problema difícil conocido, que determina qué rectangularjs se pueden embaldosar con ciertas piezas.

Sin embargo, si estás construyendo rompecabezas y puedes controlar las piezas, es el problema opuesto, constructivo y más fácil …

Construye una solución constructivamente. Tome algunas de las piezas que desee y complete el rompecabezas como lo desee. Luego, agregue suficientes cuadrados únicos para completarlo, y tiene garantizado que hay al less una solución. O más bien, incluye algunas piezas pequeñas en tu set de piezas permitidas.

En cuanto a resolver / diseñar las piezas, un enfoque típico de fuerza bruta es llenarlo de izquierda a derecha, luego de arriba hacia abajo. Encuentre la primera celda abierta (LR numerada, TB) e intente colocar las piezas permitidas en sus orientaciones permitidas (8 orientaciones para una pieza asimétrica si permite el volteo). Tal vez verifique las primeras piezas grandes permitidas, y recurra a las más pequeñas si es necesario. Cuando scopes un estado que no te gusta (callejón sin salida, muchas piezas pequeñas o lo que no), retrocede. Si un set de cuadrícula / pieza determinado no cumple con sus criterios, es decir, ha retrocedido hasta el final sin terminar, intente con un set de piezas y un rectángulo diferente.

Una forma de hacer un rompecabezas "más fácil" podría ser intercambiar piezas más grandes por piezas más pequeñas como monominós y dominós, ya que esto dejará más forms de llenar los últimos agujeros. O, de forma equivalente, crea una solución que favorezca esas piezas más pequeñas.

Algunos policominólogos destacados incluyen:

==> http://ee.usc.edu/faculty_staff/faculty_directory/golomb.htm Golomb originalmente acuñó el término "Polyomino"

==> http://www.eklhad.net/polyomino/ Dahlke ha resuelto bastantes rectangularjs llenos de piezas idénticas (una forma de mosaico particularmente rara)

Esta es una técnica que hemos usado en el pasado para engañar un poco sobre hardware confinado. No es tan puro como las soluciones más complejas, pero tiene la clara ventaja de ser mucho más fácil de implementar y funciona siempre.

En lugar de enfocarse en el rompecabezas completo, divídalo en unidades más pequeñas y uniformes . Cada una de estas unidades se compone de un set de piezas que se unen para formar cuadrados o rectangularjs que son mucho más fáciles de rellenar en un rompecabezas. Elija random de las diferentes configuraciones para llenar el ancho del rompecabezas (ejemplos a continuación, pero hay muchas, muchas configuraciones). A continuación se muestran 4×4, un 5×4 e incluso un ejemplo de 10×4.

Cuadrados y rectángulos

La idea es que "raya" el rompecabezas … elija los anchos random en function de la habitación restante disponible. Una vez que se termina una "raya", comienza una nueva raya.

Lanzas piezas una a la vez random dentro de cada set de "rayas". Si desea boost la dificultad, suelte aleatoriamente dos o más franjas a la vez.

Al utilizar esta técnica, no solo se garantiza que el rompecabezas se puede resolver, sino que también se ha ayudado a "engañar" el order de liberación para que sea más fácil mantenerse con vida. Por supuesto, en la práctica, los jugadores no son capaces de resolver perfectamente cada franja y así se produce el caos.

Sigue generando rayas hasta que el jugador pierda. Por supuesto, mi ejemplo es una banda de 4 bloques de alto, pero puedes elegir algo más grande y más complejo:

enter image description here

Este artículo (página 11-13, descargo de responsabilidad: soy uno de los autores) describe un algorithm que usa progtwigción dinámica para generar uniformemente regiones rectangulares con mosaico de ancho wy altura h , en el time que es lineal en h después de un preprocesamiento que toma aproximadamente 2 (en peso D ) time / espacio ( D es la dimensión más larga de una forma individual, por ejemplo, 4 en el caso de piezas de Tetris).

La idea es similar a la descrita por David arriba, y se enfoca en la tira superior , colocando piezas que no crean agujeros . La key aquí es comenzar por la precomputación de las alternativas permitidas para cada estado de la franja superior, de modo que ya no pague por la explosión combinatoria cuando genere las regiones.

El algorithm funciona para cualquier set de forms (convexas).

Además, un aspecto interesante de una generación aleatoria uniforme es que garantiza la máxima diversidad entre generaciones consecutivas (pero también puede limitar la generación de la forma que desee). Aquí hay algunos resultados típicos:

Algunos tetrises generados al azar de ancho 6

No dude en preguntar si tiene problemas con la implementación (incluso podría tener una implementación rápida y sucia de Python por ahí …)