A pesar de su nombre, El Juego de la Vida (en inglés Game of Life, abreviado GOL) no se trata de un “juego” en el sentido popular de la expresión. Se trata del autómata celular por excelencia, inventado por el matemático inglés John H. Conway a finales de la década de los 60. En el tutorial de hoy verás como implementarlo fácilmente con un programa en lenguaje C++.
El Juego de la vida de Conway
Como la mayoría de autómatas celulares, el Juego de la Vida se “juega” en un tablero de dos dimensiones (finito o infinito) compuesto por celdas. Cada celda puede tener uno de dos estados: viva o muerta.
El juego transcurre en unidades discretas de tiempo (que podemos llamar turnos). El estado de las celdas evoluciona en cada turno a partir de su propio estado y el de las otras celdas vecinas en el turno anterior, siguiendo estas normas:
- Por cada celda muerta:
-Si tiene exactamente tres vecinas vivas, en el turno siguiente estará viva (nacimiento). - Por cada celda viva:
-Si tiene menos de dos vecinas vivas, en el turno siguiente morirá (aislamiento).
-Si tiene cuatro o más vecinas vivas, en el turno siguiente morirá (sobrepoblación).
-Si tiene dos o tres vecinas vivas, se mantendrá viva en el siguiente turno (supervivencia).
Como puedes ver, se trata de un juego de cero jugadores. El usuario sólo tiene control sobre las condiciones iniciales del tablero, y una vez iniciado el juego este evoluciona sin intervención. Lo más fascinante es que a partir de estas reglas tan sencillas surgen comportamientos insospechadamente complejos.
Estas son sólo algunas de las formas de vida complejas que pueden crearse en GoL. (imagen de wikipedia)
Además, puede demostrarse matemáticamente que el Juego de la Vida es Turing-Completo, es decir, uno podría implementar una Máquina de Turing dentro de GOL y hacer cualquier cálculo numérico. Aunque no es recomendable.
También es interesante modificar los parámetros y las condiciones de las reglas. Por ejemplo, en el diseño de videojuegos se utiliza una versión modificada de GOL para generar mapas aleatorios en forma de cuevas.
Implementación básica en C++
Para implementar el juego de la vida esencialmente se necesitan tres funciones:
- Función para calcular el número de vecinos de una celda (calcular_vecinos)
- Función para aplicar las reglas a una celda (aplicar_regla)
- Función para calcular una sola iteración del juego (calcular_iteracion)
También habrá que añadir el main y una función para dibujar el tablero.
/* IMPLEMENTACIÓN BÁSICA DEL JUEGO DE LA VIDA
*
* Autor: Transductor
* www.robologs.net
*/
#include<iostream>
#include<vector>
using namespace std;
int calcular_vecinos(vector< vector<int> > tablero, int fila, int col)
{
//Inicializar el numero de vecinos a cero
int vecinos = 0;
//Recorrer todos los vecinos de la celda
for(int i = fila-1; i < fila+2; i++)
{
for(int j = col-1; j < col+2; j++)
{
//Ignorar la casilla central
if(i != fila || j != col)
{
//Ignorar las casillas fuera del rango del tablero
if(!(i < 0 || i >= tablero.size() || j < 0 || j >= tablero[0].size()))
{
//Sumar el valor de la casilla vecina (+1 si esta viva, 0 si está muerta)
vecinos = vecinos + tablero[i][j];
}
}
}
}
//Devolver el numero de vecinos
return vecinos;
}
int aplicar_regla(vector< vector<int> > tablero, int fila, int col)
{
//Variable para el nuevo estado de la celda
int nuevo_estado;
//Calcular el numero de vecinos que tiene la celda
int num_vecinos = calcular_vecinos(tablero, fila, col);
//Aplicar las reglas para calcular el nuevo estado
if(tablero[fila][col] == 1)
{
if(num_vecinos <= 1)
nuevo_estado = 0;
else if(num_vecinos >= 4)
nuevo_estado = 0;
else
nuevo_estado = 1;
}
else
{
if(num_vecinos == 3)
nuevo_estado = 1;
else
nuevo_estado = 0;
}
//Devolver el nuevo estado
return nuevo_estado;
}
vector< vector<int> > calcular_iteracion(vector< vector<int> > tablero)
{
//Tablero dónde se guardarán los estados para el nuevo turno
vector< vector<int> > nuevo_tablero(tablero);
//Variable auxiliar
int nuevo_valor;
//Recorre todas las casillas del tablero y aplica las reglas
for(int i = 0; i < tablero.size(); i++)
{
for(int j = 0; j < tablero[0].size(); j++)
{
nuevo_tablero[i][j] = aplicar_regla(tablero, i, j);
}
}
return nuevo_tablero;
}
void dibujarTablero(vector< vector<int> > tablero)
{
//Recorrer la matriz y pintar cada elemento
for(int i = 0; i < tablero.size(); i++)
{
for(int j = 0; j < tablero[0].size(); j++)
{
if(tablero[i][j])
cout << "# "; //Celda viva
else
cout << ". "; //Celda muerta
}
cout << endl;
}
}
int main()
{
//Inicializar tablero (puedes modificarlo como prefieras)
vector< vector<int> > tablero = {
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,1,0,0,0,0},
{0,0,0,1,0,1,0,0,0,0},
{0,0,0,0,1,1,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{1,1,1,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0}
};
//Dibujar el tablero inicial
cout << "\nConfiguración inicial " << endl;
dibujarTablero(tablero);
cout << endl;
//Calcular nuevas iteraciones y pintar tablero
for(int iter = 0; iter < 5; iter++)
{
//Calcular iteración
tablero = calcular_iteracion(tablero);
//Dibujar la matriz del tablero
cout << "Iteración " << iter << endl;
dibujarTablero(tablero);
cout << endl;
}
return 0;
}
Y ya está, humano. Acabas de implementar tu propio Juego de la Vida funcional. En los siguientes apartados vamos a pulir un poco este programa para mejorar su presentación y uso.
Input a través de un fichero de texto
Tal y como está escrito el código ahora mismo, para poder variar las condiciones iniciales del juego (dimensiones, casillas vivas y máximo de iteraciones) se requiere modificar el código y volver a compilar todo el programa. No es demasiado elegante.
En este segundo código, he modificado el main() para que lea un fichero de texto con el nombre “input.txt” y genere el tablero inicial a partir de su contenido. Este fichero tendrá que empezar por dos números enteros (las dimensiones del tablero), seguido de un número máximo de iteraciones y después las coordenadas de todas las celdas que empezarán estando vivas.
/* IMPLEMENTACIÓN DEL JUEGO DE LA VIDA
*
* Autor: Transductor
* www.robologs.net
*/
#include<iostream>
#include <fstream>
#include<vector>
#include <string>
using namespace std;
int calcular_vecinos(vector< vector<int> > tablero, int fila, int col)
{
//Inicializar el numero de vecinos a cero
int vecinos = 0;
//Recorrer todos los vecinos de la celda
for(int i = fila-1; i < fila+2; i++)
{
for(int j = col-1; j < col+2; j++)
{
//Ignorar la casilla central
if(i != fila || j != col)
{
//Ignorar las casillas fuera del rango del tablero
if(!(i < 0 || i >= tablero.size() || j < 0 || j >= tablero[0].size()))
{
//Sumar el valor de la casilla vecina (+1 si esta viva, 0 si está muerta)
vecinos = vecinos + tablero[i][j];
}
}
}
}
//Devolver el numero de vecinos
return vecinos;
}
int aplicar_regla(vector< vector<int> > tablero, int fila, int col)
{
//Variable para el nuevo estado de la celda
int nuevo_estado;
//Calcular el numero de vecinos que tiene la celda
int num_vecinos = calcular_vecinos(tablero, fila, col);
//Aplicar las reglas para calcular el nuevo estado
if(tablero[fila][col] == 1)
{
if(num_vecinos <= 1)
nuevo_estado = 0;
else if(num_vecinos >= 4)
nuevo_estado = 0;
else
nuevo_estado = 1;
}
else
{
if(num_vecinos == 3)
nuevo_estado = 1;
else
nuevo_estado = 0;
}
//Devolver el nuevo estado
return nuevo_estado;
}
vector< vector<int> > calcular_iteracion(vector< vector<int> > tablero)
{
//Tablero dónde se guardarán los estados para el nuevo turno
vector< vector<int> > nuevo_tablero(tablero);
//Variable auxiliar
int nuevo_valor;
//Recorre todas las casillas del tablero y aplica las reglas
for(int i = 0; i < tablero.size(); i++)
{
for(int j = 0; j < tablero[0].size(); j++)
{
nuevo_tablero[i][j] = aplicar_regla(tablero, i, j);
}
}
return nuevo_tablero;
}
void dibujarTablero(vector< vector<int> > tablero)
{
//Recorrer la matriz y pintar cada elemento
for(int i = 0; i < tablero.size(); i++)
{
for(int j = 0; j < tablero[0].size(); j++)
{
if(tablero[i][j])
cout << "# "; //Celda viva
else
cout << ". "; //Celda muerta
}
cout << endl;
}
}
void extraerNumeros(string linia, int &n1, int &n2)
{
// Dado un string de la forma "A B", con A y B numeros de una
// o más cifras, extrae estos dos numeros y los guarda en
// las variables n1 y n2
//Variable para almacenar provisionalmente el entero
int num = 0;
//Recorrer todo el string
for(int i = 0; i < linia.size(); i++)
{
//Si se lee un espacio, guardar el primer entero
if(linia[i] == ' ')
{
n1 = num;
num = 0;
i++;
}
//Leer una nueva cifra
num = num*10;
num = num + (linia[i] - '0');
}
//Guardar el segundo entero
n2 = num;
}
int main()
{
//Variables para poder inicializar el tablero
int alto, ancho, fila, columna;
//Maximo de iteraciones que el programa calculará
int max_iteraciones;
//Fichero de input
ifstream fichero;
//Variable para guardar lineas del fichero
string linia;
//Tablero de juego
vector < vector <int> > tablero;
//Abrir el fichero de input y generar el tablero inicial
fichero.open("input.txt");
if(fichero.is_open())
{
//La primera linea es especial; debe procesarse por separado
if(getline(fichero,linia))
{
//Convertir los carácteres a enteros
extraerNumeros(linia, alto, ancho);
cout << "Dimensiones: " << alto << " x " << ancho << endl;
}
//Una vez conocidas las dimensiones, se puede inicializar el tablero
tablero.resize(alto, vector<int>(ancho, 0));
for(int i = 0; i < alto; i++)
for(int j = 0; j < ancho; j++)
tablero[i][j] = 0;
//La segunda linea también es especial: se corresponde al num de iteraciones
if(getline(fichero, linia))
{
//Como solo hay un numero, podemos utilizar atoi()
max_iteraciones = stoi(linia);
}
//Hay que ir leyendo cada linea del fichero
while(getline(fichero,linia))
{
extraerNumeros(linia, fila, columna);
if(fila >= 0 and fila < alto and columna >= 0 and columna < ancho)
tablero[fila][columna] = 1;
}
}
else
{
cout << "ERROR: no se ha encontrado el fichero 'input.txt'" << endl;
return 0;
}
//Cerrar el fichero
fichero.close();
//Dibujar el tablero inicial
cout << "\nConfiguración inicial " << endl;
dibujarTablero(tablero);
cout << endl;
//Calcular nuevas iteraciones y pintar tablero
for(int iter = 0; iter < max_iteraciones; iter++)
{
//Calcular iteración
tablero = calcular_iteracion(tablero);
//Dibujar la matriz del tablero
cout << "Iteración " << iter << endl;
dibujarTablero(tablero);
cout << endl;
}
return 0;
}
Para probarlo puedes utilizar este fichero. Guárdalo como “input.txt” en la misma carpeta donde tengas el ejecutable del programa:
20 20 30 1 1 2 1 3 1 7 7 8 8 8 9 7 9 6 9
(Este fichero inicializará un tablero de 20×20 con un Glider y un Blinker y calculará 30 iteraciones)
Animación
Por último, estaría bien poder ver una animación de como evoluciona el autómata celular. Hay un truco fácil para hacerlo, si bien no es muy elegante: limpiar la pantalla de la consola cada vez que se vaya a dibujar el tablero, y después pausar el programa durante algunos milisegundos.
/* IMPLEMENTACIÓN DEL JUEGO DE LA VIDA
* (Ahora con animaciones)
*
* Autor: Transductor
* www.robologs.net
*/
#include<iostream>
#include <fstream>
#include<vector>
#include <string>
#include <cstdlib>
#include <chrono>
#include <thread>
using namespace std;
using namespace std::this_thread;
using namespace std::chrono;
int calcular_vecinos(vector< vector<int> > tablero, int fila, int col)
{
//Inicializar el numero de vecinos a cero
int vecinos = 0;
//Recorrer todos los vecinos de la celda
for(int i = fila-1; i < fila+2; i++)
{
for(int j = col-1; j < col+2; j++)
{
//Ignorar la casilla central
if(i != fila || j != col)
{
//Ignorar las casillas fuera del rango del tablero
if(!(i < 0 || i >= tablero.size() || j < 0 || j >= tablero[0].size()))
{
//Sumar el valor de la casilla vecina (+1 si esta viva, 0 si está muerta)
vecinos = vecinos + tablero[i][j];
}
}
}
}
//Devolver el numero de vecinos
return vecinos;
}
int aplicar_regla(vector< vector<int> > tablero, int fila, int col)
{
//Variable para el nuevo estado de la celda
int nuevo_estado;
//Calcular el numero de vecinos que tiene la celda
int num_vecinos = calcular_vecinos(tablero, fila, col);
//Aplicar las reglas para calcular el nuevo estado
if(tablero[fila][col] == 1)
{
if(num_vecinos <= 1)
nuevo_estado = 0;
else if(num_vecinos >= 4)
nuevo_estado = 0;
else
nuevo_estado = 1;
}
else
{
if(num_vecinos == 3)
nuevo_estado = 1;
else
nuevo_estado = 0;
}
//Devolver el nuevo estado
return nuevo_estado;
}
vector< vector<int> > calcular_iteracion(vector< vector<int> > tablero)
{
//Tablero dónde se guardarán los estados para el nuevo turno
vector< vector<int> > nuevo_tablero(tablero);
//Variable auxiliar
int nuevo_valor;
//Recorre todas las casillas del tablero y aplica las reglas
for(int i = 0; i < tablero.size(); i++)
{
for(int j = 0; j < tablero[0].size(); j++)
{
nuevo_tablero[i][j] = aplicar_regla(tablero, i, j);
}
}
return nuevo_tablero;
}
void dibujarTablero(vector< vector<int> > tablero)
{
//Recorrer la matriz y pintar cada elemento
for(int i = 0; i < tablero.size(); i++)
{
for(int j = 0; j < tablero[0].size(); j++)
{
if(tablero[i][j])
cout << "# "; //Celda viva
else
cout << ". "; //Celda muerta
}
cout << endl;
}
}
void extraerNumeros(string linia, int &n1, int &n2)
{
// Dado un string de la forma "A B", con A y B numeros de una
// o más cifras, extrae estos dos numeros y los guarda en
// las variables n1 y n2
//Variable para almacenar provisionalmente el entero
int num = 0;
//Recorrer todo el string
for(int i = 0; i < linia.size(); i++)
{
//Si se lee un espacio, guardar el primer entero
if(linia[i] == ' ')
{
n1 = num;
num = 0;
i++;
}
//Leer una nueva cifra
num = num*10;
num = num + (linia[i] - '0');
}
//Guardar el segundo entero
n2 = num;
}
int main()
{
//Variables para poder inicializar el tablero
int alto, ancho, fila, columna;
//Maximo de iteraciones que el programa calculará
int max_iteraciones;
//Fichero de input
ifstream fichero;
//Variable para guardar lineas del fichero
string linia;
//Tablero de juego
vector < vector <int> > tablero;
//Abrir el fichero de input y generar el tablero inicial
fichero.open("input.txt");
if(fichero.is_open())
{
//La primera linea es especial; debe procesarse por separado
if(getline(fichero,linia))
{
//Convertir los carácteres a enteros
extraerNumeros(linia, alto, ancho);
cout << "Dimensiones: " << alto << " x " << ancho << endl;
}
//Una vez conocidas las dimensiones, se puede inicializar el tablero
tablero.resize(alto, vector<int>(ancho, 0));
for(int i = 0; i < alto; i++)
for(int j = 0; j < ancho; j++)
tablero[i][j] = 0;
//La segunda linea también es especial: se corresponde al num de iteraciones
if(getline(fichero, linia))
{
//Como solo hay un numero, podemos utilizar atoi()
max_iteraciones = stoi(linia);
}
//Hay que ir leyendo cada linea del fichero
while(getline(fichero,linia))
{
extraerNumeros(linia, fila, columna);
if(fila >= 0 and fila < alto and columna >= 0 and columna < ancho)
tablero[fila][columna] = 1;
}
}
else
{
cout << "ERROR: no se ha encontrado el fichero 'input.txt'" << endl;
return 0;
}
//Cerrar el fichero
fichero.close();
//Dibujar el tablero inicial
cout << "\nConfiguración inicial " << endl;
dibujarTablero(tablero);
cout << endl;
//Calcular nuevas iteraciones y pintar tablero
for(int iter = 0; iter < max_iteraciones; iter++)
{
//Calcular iteración
tablero = calcular_iteracion(tablero);
//Limpiar la pantalla del terminal
if (system("CLS")) system("clear");
//Dibujar la matriz del tablero
cout << "Iteración " << iter << endl;
dibujarTablero(tablero);
cout << endl;
//Esperar 0.35 segundos antes de continuar
sleep_for(milliseconds(350));
}
return 0;
}
NOTA: No estoy seguro de que este último programa funcione con todos los sistemas operativos. Si utilizas Windows puede que tengas que buscar alternativas a cstdlib, chrono y/o thread.
Final de línea.
Actualización 15/04/2020 – Compilación
He recibido algunos mensajes de lectores que se han encontrado con problemas para compilar estos códigos. Todos deberían funcionar correctamente con C++11 y el compilador g++ o gpp.
Esta es la instrucción que he utilizado para compilar los ejemplos directamente desde la Terminal de Linux:
g++ micodigo.cpp -o micodigo -std=c++11
(cambiando “micodigo.cpp” por el path a tu programa)
Para que sirve los corchetes tablero[i][j];
Aquí sirven para acceder a la fila ‘i’ y la columna ‘j’ de la matriz ‘tablero’.
Amigo para que sirven los corchetes [] ejemplo tablero[i][j];