Modelamiento del “Juego de la Vida de Conway” mediante Pseudolenguaje

Para comprender lo que realmente es el “juego de la vida”, debemos entender primero lo que es un autómata celular simple, entender las reglas del juego, conocer algunas aplicaciones de este y cómo funciona, para finalmente modelarlo.. en este mismo órden:

¿Qué es un Autómata Celular?

No existe una definición formal de autómata celular (A.C.), sin embargo, la definición que utilizaremos es bastante general y se ajusta al problema que abordamos. Un autómata celular es un modelo matemático para un sistema dinámico que evoluciona en pasos discretos. Es adecuado para modelar sistemas naturales que puedan ser descritos como una colección masiva de objetos simples que interactúen localmente unos con otros mediante reglas que definen el comportamiento del autómata.

Introducción al Juego de la Vida

El juego de la vida (or the Game of Life) es básicamente un autómata celular que describe una idealización matemática de la naturaleza. Tal juego fue inventado por el matemático John Conway -docente de la Universidad de Cambridge- y lo publicó en un artículo en la revista Scientífic American en 1970. La cantidad de aplicaciones de este inocente juego fueron insospechadas, por ejemplo, permite modelar leyes de comportamiento climático para una determinada zona, representar una simulación de la propia vida o su evolución, sistemas termodinámicos, etc. Para los interesados en la parte más matemática del juego, éste puede considerarse como una idealización discreta de las ecuaciones diferenciales (esto de forma gráfica, ya que la discretización de la teoría de ecuaciones diferenciales se conoce como ecuaciones en diferencias), y en segunda instancia, sus bases se asemejan a la de los computadores de procesamiento paralelo.

…pero, ¿qué reglas definen el juego?

Consideremos una matriz de dimensión n\times n (puede verse como un tablero con n^2 casillas), diremos que una casilla tiene una “célula” si ésta se encuentra ocupada y nos referiremos a “vecinos” de un casillero (con o sin célula) para hablar de las células que se encuentran en las 8 casillas que lo rodean (si el casillero se encuentra en la frontera del tablero lo rodean menos casillas). Bajo este contexto definimos las siguientes reglas:

  • Cada “célula” con 1 o ningún vecino “muere”, es decir, es retirada del tablero en el siguiente estado o en la siguiente actualización;
  • Cada célula con 4 o más vecinos “muere” por superpoblación;
  • Una célula con 2 o 3 vecinos sobrevive;
  • Un casillero vacío rodeado de exactamente 3 vecinos “engendra” una nueva célula, es decir, hay que poner una célula en ese casillero en la siguiente actualización;

Despues de toda esta introducción, deberíamos entender como es que se genera la siguiente animación:

Ejemplo de A.C. generado por el Juego de la Vida

En este ejemplo podemos notar que la población de células inicial inevitablemente se extingue. Esto no siempre ocurre, de hecho, existen ocasiones donde se llega a un estado muerto (donde la distribución de células deja de cambiar, un ejemplo particular es cuando la población se extingue), se llega a una cantidad finita de estados que se repiten ciclicamente o a regularidades que van cambiando y evolucionando… ¿qué ocurriría si pudieramos ver estos cambios -a partir de una configuración inicial dada- sobre un tablero lo suficientemente grande como para no distinguir las casillas, sino figuras? La respuesta a esta pregunta es sorprendente y les recomiendo que vean el siguiente video:

Modelamiento del Juego de la Vida

La gracia de escribir un programa en pseudocódigo es que el traspaso de éste a un lenguaje de programación como Java o Python es natural. A continuación dejo el pseudocódigo para generar un tablero de dimensión modificable y poder hacer un programa con las reglas del juego de la vida, muy parecido al que se encuentra en el video anterior:

Proceso Conway
   Escribir "Ingrese dimensión del cuadriculado: ";
   Leer dim;
   Borrar Pantalla;
	
   Dimension Cuad[dim,dim];
   Dimension Cuad2[dim,dim];
   Dimension Cuad3[dim,dim];
	
   Para i<-1 Hasta dim Con Paso 1 Hacer
      Para j<-1 Hasta dim Con Paso 1 Hacer
	Cuad[i,j]<-0;
      FinPara 
   FinPara
	
   Para i<-1 Hasta dim Con Paso 1 Hacer
      Para j<-1 Hasta dim Con Paso 1 Hacer
	 Si Cuad[i,j]=1 Entonces
	   Cuad3[i,j]<-"O";
	 Sino
	   Cuad3[i,j]<-".";
	 FinSi
      FinPara
   FinPara	
	
   Para i<-1 Hasta dim Con Paso 1 Hacer
      Para j<-1 Hasta dim Con Paso 1 Hacer
	Escribir SIN SALTAR Cuad3[i,j];
	Escribir SIN SALTAR " ";
      FinPara
      Escribir "";
   FinPara	
	
   Escribir "";
   g<-1;
	
   Mientras g=1 Hacer
      Escribir "Ingrese una de las siguientes opciones: ";
      Escribir "";
      Escribir "1) Definir configuración inicial / llenar (o vaciar)
      una celda;";
      Escribir "2) Comenzar simulación;";
      Leer op1;

      Segun op1 Hacer
	 1:
	    Escribir "Número de FILA: ";
	    Leer fila;
	    Escribir "Número de COLUMNA: ";
            Leer columna;
	    p<-Cuad[fila,columna];
	    
            Si p=0 Entonces
	      Cuad[fila,columna]<-1;
  	    Sino
	      Cuad[fila,columna]<-0;
  	    FinSi
	
 	    Borrar Pantalla;
				
 	    Para i<-1 Hasta dim Con Paso 1 Hacer
	       Para j<-1 Hasta dim Con Paso 1 Hacer
		 Si Cuad[i,j]=1 Entonces
		   Cuad3[i,j]<-"O";
		 Sino
		   Cuad3[i,j]<-".";
		 FinSi
	       FinPara
	    FinPara	
				
	   Para i<-1 Hasta dim Con Paso 1 Hacer
  	      Para j<-1 Hasta dim Con Paso 1 Hacer
		 Escribir SIN SALTAR Cuad3[i,j];
		 Escribir SIN SALTAR " ";
	      FinPara
	      Escribir "";
  	   FinPara	
	   Escribir "";

	2:
	   g<-2;

	De Otro Modo:
  	   Borrar Pantalla;
	   Escribir "Por favor, ingrese una opción válida! ";
	   Escribir "";
	   Para i<-1 Hasta dim Con Paso 1 Hacer
	      Para j<-1 Hasta dim Con Paso 1 Hacer
	         Escribir SIN SALTAR Cuad3[i,j];
		 Escribir SIN SALTAR " ";
	      FinPara
	      Escribir "";
   	   FinPara	
	   Escribir "";
      FinSegun
   FinMientras
	
   Para i<-1 Hasta dim Con Paso 1 Hacer
      Para j<-1 Hasta dim Con Paso 1 Hacer
	 Cuad2[i,j]<-Cuad[i,j];
      FinPara
   FinPara
	
   counter<-0;
   salir<-0;
	
   Mientras salir=0 Hacer		
      Para i<-1 Hasta dim Con Paso 1 Hacer
	 Para j<-1 Hasta dim Con Paso 1 Hacer

 	    Si i=1 y j=1 Entonces //esquina 1
	      Si Cuad[1,1]=1 Entonces
		 Si Cuad[1,2]+Cuad[2,1]+Cuad[2,2]<=1 Entonces
		   Cuad2[1,1]<-0;
		 FinSi
	      Sino
	         Si Cuad[1,2]+Cuad[2,1]+Cuad[2,2]=3 Entonces
		   Cuad2[1,1]<-1;
		 FinSi
	      FinSi
 	   FinSi

	   Si i=1 y j=dim Entonces //esquina 2
              Si Cuad[1,dim]=1 Entonces
                 Si Cuad[1,dim-1]+Cuad[2,dim-1]+Cuad[2,dim]<=1 
                 Entonces
		   Cuad2[1,dim]<-0;
		 FinSi
              Sino
                 Si Cuad[1,dim-1]+Cuad[2,dim-1]+Cuad[2,dim]=3 
                 Entonces
		   Cuad2[1,dim]<-1;
		 FinSi
	      FinSi	
 	   FinSi

	   Si i=dim y j=1 Entonces //esquina 3
	      Si Cuad[dim,1]=1 Entonces
		 Si Cuad[dim-1,1]+Cuad[dim-1,2]+Cuad[dim,2]<=1 
                 Entonces
		   Cuad2[dim,1]<-0;
		 FinSi
	      Sino
		 Si Cuad[dim-1,1]+Cuad[dim-1,2]+Cuad[dim,2]=3 
                 Entonces
		   Cuad2[dim,1]<-1;
		 FinSi
	      FinSi
	   FinSi

	   Si i=dim y j=dim Entonces //esquina 4
	      Si Cuad[dim,dim]=1 Entonces
		 Si Cuad[dim-1,dim]+Cuad[dim,dim-1]+
                 Cuad[dim-1,dim-1]<=1 Entonces
		   Cuad2[dim,dim]<-0;
		 FinSi
	      Sino
		 Si Cuad[dim-1,dim]+Cuad[dim,dim-1]+
                 Cuad[dim-1,dim-1]=3 Entonces
		   Cuad2[dim,dim]<-1;
		 FinSi
	      FinSi
	   FinSi

           //interior cuadriculado sin borde
 	   Si i>1 y j>1 y i<dim y j<dim Entonces 
	      Si Cuad[i,j]=1 Entonces
		 Si Cuad[i-1,j-1]+Cuad[i-1,j]+Cuad[i-1,j+1]+
                 Cuad[i,j+1]+Cuad[i+1,j+1]+Cuad[i+1,j]+
                 Cuad[i+1,j-1]+Cuad[i,j-1]<=1 o Cuad[i-1,j-1]
                 +Cuad[i-1,j]+Cuad[i-1,j+1]+Cuad[i,j+1]+
                 Cuad[i+1,j+1]+Cuad[i+1,j]+Cuad[i+1,j-1]
                 +Cuad[i,j-1]>=4 Entonces
		   Cuad2[i,j]<-0;
		 FinSi
	      Sino
		 Si Cuad[i-1,j-1]+Cuad[i-1,j]+Cuad[i-1,j+1]+
                 Cuad[i,j+1]+Cuad[i+1,j+1]+Cuad[i+1,j]+
                 Cuad[i+1,j-1]+Cuad[i,j-1]=3 Entonces
		    Cuad2[i,j]<-1;
		 FinSi
	      FinSi
	   FinSi

 	   Si i=1 y j>1 y j<dim Entonces //borde 1 sin esquinas
	      Si Cuad[1,j]=1 Entonces
		 Si Cuad[1,j-1]+Cuad[2,j-1]+Cuad[2,j]+Cuad[2,j+1]+
                 Cuad[1,j+1]<=1 o Cuad[1,j-1]+Cuad[2,j-1]+Cuad[2,j]
                 +Cuad[2,j+1]+Cuad[1,j+1]>=4 Entonces
		   Cuad2[1,j]<-0;
		 FinSi
	      Sino
	         Si Cuad[1,j-1]+Cuad[2,j-1]+Cuad[2,j]+Cuad[2,j+1]+
                 Cuad[1,j+1]=3 Entonces
		   Cuad2[1,j]<-1;
		 FinSi
	      FinSi
	   FinSi

	   Si i>1 y i<dim y j=1 Entonces //borde 2 sin esquinas
	      Si Cuad[i,1]=1 Entonces
		 Si Cuad[i+1,1]+Cuad[i+1,2]+Cuad[i,2]+Cuad[i-1,2]+
                 Cuad[i-1,1]<=1 o Cuad[i+1,1]+Cuad[i+1,2]+Cuad[i,2]
                 +Cuad[i-1,2]+Cuad[i-1,1]>=4 Entonces
		   Cuad2[i,1]<-0;
		 FinSi
	      Sino
		 Si Cuad[i+1,1]+Cuad[i+1,2]+Cuad[i,2]+Cuad[i-1,2]+
                 Cuad[i-1,1]=3 Entonces
		   Cuad2[i,1]<-1;
		 FinSi
	      FinSi
	   FinSi

	   Si i=dim y j>1 y j<dim Entonces //borde 3 sin esquinas
	      Si Cuad[dim,j]=1 Entonces
		 Si Cuad[dim,j-1]+Cuad[dim-1,j-1]+Cuad[dim-1,j]+
                 Cuad[dim-1,j+1]+Cuad[dim,j+1]<=1 o Cuad[dim,j-1]
                 +Cuad[dim-1,j-1]+Cuad[dim-1,j]+Cuad[dim-1,j+1]
                 +Cuad[dim,j+1]>=4 Entonces
		   Cuad2[dim,j]<-0;
		 FinSi
	      Sino
		 Si Cuad[dim,j-1]+Cuad[dim-1,j-1]+Cuad[dim-1,j]+
                 Cuad[dim-1,j+1]+Cuad[dim,j+1]=3 Entonces
		   Cuad2[dim,j]<-1;
		 FinSi
	      FinSi
	   FinSi

	   Si i>1 y i<dim y j=dim Entonces //borde 4 sin esquinas
	      Si Cuad[i,dim]=1 Entonces
		 Si Cuad[i-1,dim]+Cuad[i-1,dim-1]+Cuad[i,dim-1]+
                 Cuad[i+1,dim-1]+Cuad[i+1,dim]<=1 o Cuad[i-1,dim]
                 +Cuad[i-1,dim-1]+Cuad[i,dim-1]+Cuad[i+1,dim-1]+
                 Cuad[i+1,dim]>=4 Entonces
		   Cuad2[i,dim]<-0;
		 FinSi
	      Sino
		 Si Cuad[i-1,dim]+Cuad[i-1,dim-1]+Cuad[i,dim-1]+
                 Cuad[i+1,dim-1]+Cuad[i+1,dim]=3 Entonces
		   Cuad2[i,dim]<-1;
		 FinSi
	      FinSi
	   FinSi
        FinPara
     FinPara
		
     Para i<-1 Hasta dim Con Paso 1 Hacer
	Para j<-1 Hasta dim Con Paso 1 Hacer
	   Cuad[i,j]<-Cuad2[i,j];
	FinPara
     FinPara
		
     counter<-counter+1;
     Borrar Pantalla;
     Escribir Sin Saltar "Estado N°";
     Escribir Sin Saltar counter;
     Escribir "";
		
     Para i<-1 Hasta dim Con Paso 1 Hacer
	Para j<-1 Hasta dim Con Paso 1 Hacer
	   Si Cuad[i,j]=1 Entonces
	     Cuad3[i,j]<-"O";
  	   Sino
	     Cuad3[i,j]<-".";
	   FinSi
	FinPara
     FinPara	
				
     Para i<-1 Hasta dim Con Paso 1 Hacer
	Para j<-1 Hasta dim Con Paso 1 Hacer
	   Escribir SIN SALTAR Cuad3[i,j];
	   Escribir SIN SALTAR " ";
	FinPara
	Escribir "";
     FinPara	
		
     Esperar 1 Segundos;		
   
   FinMientras

FinProceso

El pseudocódigo anterior esta escrito para ser interpretado por “PSeint” (que aún se encuentra en versión beta), cualquier duda sobre la acción de los comandos anteriores puede verse en el tutorial de este programa.

Anuncios

Si te gustó el post, por favor dejanos tu comentario!!

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s