Los poliominós son figuras geométricas bidimensionales que resultan de “pegar” varios cuadrados por sus lados. Que yo sepa, el primer juego de computadora que los usó fue el legendario Tetris, donde había que ir acomodando tetrominós, o sea, poliominós de orden 4.
En el juego Ntris —mi humilde versión del Tetris—, las piezas van aumentando su tamaño a medida que avanza el juego. Por lo tanto, el programa no contiene una biblioteca de piezas predefinidas sino que las va generando dinámicamente.
Si Ud. desea generar poliominós a la manera del Ntris, elija una cantidad de cuadrados y proceda así. Al comienzo, coloque un cuadrado en la «mesa». Luego entre en este pequeño bucle:
- Elija un cuadrado al azar de la mesa.
- Elija un lugar adyacente al cuadrado elegido.
- Si el lugar elegido aún no está ocupado, coloque un cuadrado allí.
- Si quedan cuadrados por poner, vuelva al paso 1. Si no, ha terminado.
Es un método simple pero claramente injusto: no todos los poliominós de un orden dado tienen la misma probabilidad de ser generados.
¿Habrá un método simple y elegante de generar poliominós dinámicamente que evite ese problema?
Si a alguien se le ocurre, tendré el placer de incorporarlo al programa, y por supuesto dar el crédito correspondiente.
Marzo 10, 2008 a las 11:46 am |
mmmmh, estoy pensando algo con un hashing, después te lo mando….
Marzo 13, 2008 a las 10:46 am |
EL método no óptimo que se me ocurre es generar un grilla de nxn casillas y generar todas las posibles combinaciones con n casillas coloreadas, luego recorrer esa lista e ir descartando aquellas configuraciones que tengan alguna casilla que no tenga vecinos ortogonalmente. Eso te daría todas las versiones de poliominós con todas sus rotaciones.
Luego habría que pasarlos por un filtro para eliminar los rotados, et voilá.
Marzo 13, 2008 a las 11:05 am |
Bueno, ese método funcionaría sin duda, pero llevaría demasiado tiempo cada vez que quiera generar una pieza, o bien demasiada memoria para almacenar las piezas de cada tamaño…
Marzo 13, 2008 a las 11:42 am |
manualmente, sin dudas, estoy haciendo el algoritmo bruto en Python, una vez que lo tenga veo si lo podemos optimizar, seguro se puede
Marzo 13, 2008 a las 11:46 am |
a ver, hagamos brainstorming, la grilla es el tablero, sin duda necesario para armar cualquier poliomino de orden n, tenemos que encontrar una manera de generarle un código hash a cada poliomino para incluírlo en un diccionario e ir descartando los que se generen iguales, se te ocurre alguna forma?
Marzo 13, 2008 a las 11:57 am |
A ver!! se me acaba de ocurrir esto (tambien te da todos los rotados, pero es menor el numero de iteraciones ya que se detiene al final de un poliominó cosntruído).
Tomemos el caso de poliominos de orden n:
ponemos un cuadrado.
X
empezamos con una dirección, (arriba A, abajo B, derecha D, izquierda C
supongamos A,
nos queda un poliomino XA
seguimos con el tercer cuadrado, nos quedan direcciones posibles
ADC
elegimos A nos queda un poliomino XAA y direcciones posibles ADC
elegimos A nos queda XAAA. Guardamos este resultado XAAA
Tomamos el ultimo poliomino y deshacemos un paso
XAA vemos los dos caminos posibles que nos quedaban, DC
elegimos D, nos queda XAAD
repetimos los 2 pasos anteriores paso anterior nos queda XAAC
repetimos los pasos anteriores, no nos quedan caminos así que deshacemos un paso más XA
elegimos entre DC, nos queda XAD
ahora tenemos ADC, elegimos XADA..
y así..
Marzo 13, 2008 a las 12:02 pm |
Creo que debo explicitar los requerimientos que busco: el algoritmo debe ser de tiempo y memoria lineal en el tamaño de la pieza.
O sea, debería funcionar sin tener que armar estructuras de datos complejas. Además, no tendría que depender de ir armando una lista de piezas de cada tamaño; eso lo haría ocupar demasiada memoria.
Por ejemplo, el algoritmo actual construye, sobre la marcha, una simple lista de coordenadas de las casillas que forman la pieza; va agregando una por una las casillas.
Marzo 13, 2008 a las 12:08 pm |
El único algoritmo que se me ocurre sobre la marcha y justo es el de tener la grilla de n*n y depositar sobre la marcha n cuadrados y verificar que todos tengan una pieza adyacente, si no volver a repetir. El tema que cuanto mayor el orden más baja es la probabilidad que randonómicamente se conecten todos los cuadrados
Marzo 13, 2008 a las 12:16 pm |
Es cierto, tardaría mucho… Pero ¿estás seguro de que todos los poliominós aparecerían con la misma probabilidad?
Yo creo que no; aunque no lo podría demostrar. Habrá que recurrir a algún matemático o estadístico…
Marzo 13, 2008 a las 12:20 pm |
Debería, a no ser que una pieza pueda entrar más veces que otra (rotada en todas sus formas) dentro del tablero, pero sospecho que no pasa. Mientras mantenemos esta charla estoy programando todo esto (estoy medio al pedo en el laburo hoy
)
Marzo 15, 2008 a las 3:25 am |
Una variacion para no repetir simetrias sin necesidad de guardar una lista podria ser la siguiente. A cada poliomino se le asigna un numero cuya representacion binaria tiene a lo sumo nxn digitos con 1s en donde hay piezas (llamale codigo hash si queres). Entonces cuando generas un poliomino podes chequear que ninguna de las rotaciones o traslaciones que entran en el cuadradito tenga un numero asignado menor. Si hubiere alguna, descartamos el poliomino este, y probamos con otro.
Aun asi no estoy seguro de como general el poliomino para empezar. El algoritmo que usa tu programa todavia generaria algunos poliominos con mas probabilidad que otros dependiendo de la libertad que tenemos en el orden de elegir los cuadraditos.
Abril 10, 2008 a las 1:42 am |
Ups, llego tarde y medio perdido, pero me dio curiosidad el asunto.
¿Cómo es exactamente esto de que con tu versión actual algunos polinomiós tienen más probabilidad de ser generados que otros?
Abril 25, 2008 a las 10:01 pm |
Hola, he descubierto ahora mismo tu blog y estoy recorriendo las entradas antiguas. No sé si ya habrás resuelto este problema, pero me ha parecido interesante y he pensado en una solución que quizás te vendría bien.
Consiste simplemente en utilizar dos listas de coordenadas. Cada lista contiene las coordenadas de los cuadrados colocados y de los espacios circundantes donde se pueden colocar cuadrados.
El caso es recorrer la lista de los cuadrados situados analizando las posiciones superior (+y), derecha (+x), inferior (-y) e izquierda (-x) de cada uno de ellos: si las coordenadas están en alguna de las dos listas no se hace nada, y si no aparecen, se guardan en la de posibles.
Entonces se hace una tirada aleatoria con el mismo índice de probabilidad para todas las coordenadas de posibles; al que le toque se elimina de esa lista y se añade a la de colocados.
Así a primeras, si el poliomino es muy grande parece que será muy costoso; sin embargo, no es necesario recalcular cada vez ambas listas. El espacio de posibles sólo se ve modificado al incluir un nuevo cuadrado, de modo que sólo será éste el que hay que estudiar, añadiendo las coordenadas circundantes del último que no estén en ninguna de las dos listas.
Creo que es un algoritmo bastante sencillo y que te permite tener la misma probabilidad para todas las posiciones.
Un saludo.