hagaloustedmismo


Una web de Javier Marco Rubio	FORO	CONTACTO

índice

QUEST 3D:AUTOMATAS CELULARES

Es duro admitirlo, pero uno ya tiene una edad, y más en el tema informático, en el que he vivido sus albores.

Uno de los primeros programas en BASIC que escribí siendo aun niño, fue el autómata celular de Conway:

Consulten la Wikipedia para saber qué es un automata celular

Me gustan los automátas celulares por la complejidad que pueden alcanzar sus diseños a partir de una reglas de evolución muy sencillas. Pero aun me gustan más, porque no hay grupos de investigadores universitarios que pretendan buscar aplicaciones reales a los autómatas celulares, como controlar los semafores de una ciudad, el pilóto automático de un avión, o una cadena de montaje de autómoviles, cosa que sí se pretenden con otros modelos como las redes neuronales, los algoritmos genetícos... Lo bueno de los autómatas celulares es que simplemente son "bonitos"

En concreto, el juego de la vida de Comway es el más conocido, por ser el que reglas más simples aplica, consiguiendo interesantes diseños evolutivos.

Visiten esta web para jugar con un Conway's Game of Life hecho en Java

Y este muy bonito en Flash

En aquellos tiempos remotos, yo saqué el listado del algoritmo de Conway's Game of Life, de un libro incunable, uno de los primeros libros de juegos de ordenador de la historia, que me enorgullezco de conservar:

Basic Computer Games -microcomputer edition- Workman Publishing 1979

Me voy a tomar la atrevida licencia de publicar dos páginas de este libro. Aquellas en las que está la historia, y el listado Basic original del Conway's Game of Life. Pienso que si alguna web la informática se considera un arte, materiales como este serán los primeros en ocupar los museos:

Como ven, las reglas son muy simples:

Se considera vecino de una celda aquellos que la rodean incluso en diagonal.
1-Una celda ocupada muere por soladedad si tiene 0 ó 1 vecinos ocupados, y por saturación si tiene 4 ó más vecinos.
2-Una celda vacia genera una nueva ocupada si tiene exactamente tres vecinos ocupados.
El resto sigue igual.

Si ven el algoritmo original, se implementa mediante un array bidimensional de dimensiones finitas (seria limitación), y hace uso intensivo de los bucles para recorrer las dos dimensiones del array comprobando los vecinos de cada celda.

Recuerdo mi primera implementación del algoritmo, un micro ordenador de 8 bits fabricado por Thomson: MO5. Si hay curiosidad, pueden saber de qué iba este ordenador, y ver los juegos que realicé en aquellos tiempos para este ordenador en esta web.
Comprenderán que la velocidad de calculo de estos ordenadores era poca, y el calculo de las generaciones se podía demorar horas.

¡Qué diferencia ahora!, se generan cientos de generaciones en segundos.

Pero en determinados lenguajes realmente hemos dado un paso atras: los lenguajes interpretados.

Quest 3D, es un lenguaje interpretado, por tanto, el uso intensivo de bucles ralentiza mucho la ejecución.

además carece de la estructura de array bidimensional, por lo que hay que cambiar mucho la estructura del algoritmo orginal de Comway.

Voy a desmenuzar paso a paso la implementación de un algoritmo de Conway en Quest3D. Como ejercicio de lógica en Quest3D a los que esteis aprendiendo puede resultaros interesante:

LIFE en QUEST3D

DESCARGAR EL MATERIAL (fuente y ejecutable)

1-TABLAS

Se necesitan dos tablas, la que contiene el estado evolutivo actual (life), y otra temporal para el calculo de la siguiente iteración (temporal)

Las columnas celda son de tipo vector, se inicializa a mano la de la tabla life rellenando las X e Y de las casillas ocupadas en el patrón inicial. (la Z a cero para implementar en el futuro un life en tres dimensiones.

La columna vecinos de life se calculará en el algoritmo, no hace falta rellenarlo. contendrá en todo momento cuantos vecinos tiene cada celda ocupada.

Como ven, al no implementarlo mediante array, no hay dimensiones finitas. El patrón puede crecer (teoricamente) hasta el infinito.

2-INICIALIZACIÓN DE TABLAS

Al comienzo del algoritmo, con un "one-time" se inicializan las tablas, y se rellena la tabla life, con las celdas ocupadas del patrón inicial que se desea evolucione. Finalmente se rellena una variable TOTAL, que contendrá en todo momento el numero de celdas ocupadas del patrón evolutivo.

3-CALCULO DE VECINOS

Este es el primer paso de la iteración, necesario para saber quien muere de soledad o saturación.

El algoritmo en lenguaje fácil sería:

		  Repite de celdaactual=0 a TOTAL

             Vecinos=0

             repite de celdacomprueba=0 a TOTAL

                 if celda(celdaactual)<>celda(celdacomprueba)

                      and

                    ABS(celda(celdaactual).X-celda(celdacomprueba).X)<2

                      and

                    ABS(celda(celdaactual).Y-celda(celdacomprueba).Y)<2

                    entonces vecinos=vecinos+1

             finrepite

             meter vecinos en tabla life indice celdaactual

         finrepite

con esto, la columna vecinos queda rellenada con el numero de vecinos de cada celda ocupada.

4-CALCULO DE SUPERVIVIENTES

Una vez que tenemos los vecinos, podemos saber quién sobrevive a la siguiente iteración. Estos los psaremos a la tabla temporal.

         cont=0
		  Repite de celdaactual=0 a TOTAL
            si vecinos(celdaactual)=2 ó 3 entonces
                temporal(cont)=celda(celdaactual)
                cont=cont+1
            fin si

         finrepite

5- NACIMIENTOS

La fase más compleja y que más calculo absorve. Primero encuadramos el patrón, sacando sus coordenadas máximas y minimas. Ampliando en uno este cuadrado, comprobaremos todas las celdas vacias, contando sus vecinos ocupados. Aquellos que tengan tres vecinos, pasaran a la tabla temporal como nueva celda ocupada.

         maximax=-10000; maximay=-10000; minimax=10000; minimay=10000

         Repite de celdaactual=0 a TOTAL

            si celda(celdaactual).X>maximaX entonces maximaX=celda(celdaactual).X

            si celda(celdaactual).X<minimaX entonces minimaX=celda(celdaactual).X
            si celda(celdaactual).Y>maximaY entonces maximaY=celda(celdaactual).Y
            si celda(celdaactual).Y<minimaY entonces minimaY=celda(celdaactual).Y

         finrepite
         minimaX=minimaX-1
         minimaY=minimay-1
         maximaX=maximaX+1
         maximaY=maximaY+1
         repite celdaactualX=minimaX a maximaX
         repite celdaactualY=minimaY a maximaY
         //comprobar si es vacia
             vacia=1
             repite de celdacomprueba=0 a TOTAL
              if celda(celdacomprueba).X = celdaactualX 
                              and
                 celda(celdacomprueba).Y = celdaactualY
                              entonces vacia=0
             finrepite

          if vacia=1 entonces
               vecinos=0
               esta1=0; esta2=0; esta3=0; esta4=0; esta5=0; esta6=0; esta7=0; esta8=0
               repite de celdacomprueba=0 a TOTAL
               si celda(celdacomprueba).X = celdaactualX-1
                                   and
                  celda(celdacomprueba).Y = celdaactualY-1
                                             entonces esta1=1
               si celda(celdacomprueba).X = celdaactualX
                                   and
                  celda(celdacomprueba).Y = celdaactualY-1
                                             entonces esta2=1
               .
               .
               .
               finrepite
               vecinos=esta1+esta2+esta3+esta4+esta5+esta6+esta7+esta8
               if vecinos=3 entonces añadir (celdaactualX, celdaactualY,0) a temporal
           end if
           fin repite
           finrepite

En Quest la imagen es un poco grande: