Juego de la Vida de Conway en C# con interfaz gráfica
20/01/2018
Hoy os traigo un proyecto que realizamos Daniel Bazaco y yo. Se trata del clásico de juego de la vida, esta vez hecho en C# con .NET Core y Avalonia como librería gráfica. Funciona tanto en Windows como en GNU/Linux. El programa tiene la peculiaridad de que tiene implementados dos algoritmos totalmente distintos para el juego de la vida:
La velocidad de este segundo algoritmo es muy superior a la del primero, aunque he de confesar que este segundo algoritmo no resulta evidente y tiene una desventaja en el modo gráfico. Este segundo algoritmo avanza a trompicones, por lo que no es posible realizar una animación gráfica idónea, a no ser que lo modifiquemos ligeramente. Este tercer algoritmo que es una modificación del segundo, es más lento, pero permite ser mostrado por la pantalla.
El programa admite ficheros tanto en formato estándar RLE como un formato propio, que hemos llamado Vaca. Puedes pasarte por la wiki del juego de la vida y probar los ficheros RLE que encuentres. No obstante, hay que tener cuidado, pues algunos ficheros RLE no son del juego de la vida, sino de otros juegos con normas ligeramente modificadas.
El juego de la vida es un autómata celular de dos dimensiones. También se le ha categorizado como juego para cero jugadores.
El juego tiene unas normas sencillas. Cada celda puede estar viva o muerta. En la siguiente evolución, las celdas pueden pasar a vivas o muertas siguiendo este esquema:
Unas condiciones de partida determinadas podrán desencaminar comportamientos complejos y emergentes muy interesantes como las pistolas de gliders.
[video width="1364" height="704" mp4="https://files.adrianistan.eu/GosperGliderGun.mp4" webm="https://files.adrianistan.eu/GosperGliderGun.webm"][/video]
Pantalla de inicio de Conway
Desde aquí podemos dar a Nuevo patrón o Cargar patrón. Si le damos a Nuevo Patrón tendremos una matriz vacía y limpia. Podemos hacer click con el ratón para ir activando/desactivando las casillas. Puedes usar las teclas W, A, S y D o las flechas en pantalla para moverte por el universo infinito de Conway.
Una vez lo tengamos podemos guardarlo para no tener que volver a dibujarlo. Otra opción es cargar un patrón de la lista. Este programa admite formato RLE y Vaca, pero solo guarda archivos en formato Vaca.
Para ejecutar el juego de la vida hay tres botones importantes. El primero es Ejecutar, que ejecuta el juego de la vida indefinidamente. Se para cuando pulsamos Parar (el mismo botón).
El otro es Siguiente, que nos permite avanzar de iteración en iteración manualmente, muy interesante para observar al detalle ciertos patrones. Por otro lado tenemos Iterar N veces, que permite iterar N veces y que sirve para pruebas de rendimiento. Hay que tener en cuenta que tanto Siguiente como Iterar N veces funcionan un poco distinto con el algoritmo Quadtree (el activado por defecto), ya que este algoritmo hace varias evoluciones de golpe, para ser todavía más rápido. La parte mala es que no es posible ver en detalle cada algoritmo.
[video width="1008" height="486" mp4="https://files.adrianistan.eu/AlgoritmoMatriz.mp4" webm="https://files.adrianistan.eu/AlgoritmoMatriz.webm"][/video]
[video width="1008" height="486" mp4="https://files.adrianistan.eu/AlgoritmoQuadtree.mp4" webm="https://files.adrianistan.eu/AlgoritmoQuadtree.webm"][/video]
Es posible ejecutar el juego de la vida en línea de comandos. Este modo permite cargar un archivo Vaca o RLE y ejecutarlo N iteraciones. Al finalizar se muestran estadísticas y se permite guardar el resultado o mostrarlo por pantalla con caracteres ASCII.
Hay dos parámetros, -i para indicar el fichero de entrada y -n para indicar las iteraciones a calcular.
¿Cómo funciona el algoritmo quadtree que tanto mejora el rendimiento del juego de la vida? Siendo sinceros, no es algoritmo sencillo o evidente. Su nombre más correcto es algoritmo Hashlife y fue descrito por Bill Gosper en los laboratorios de investigación de Xerox Palo Alto.
La idea básica es que muchas veces en el juego de la vida nos encontramos con patrones que se van repitiendo periódicamente y grandes zonas vacías.
Para ello recurre a un almacén de cuadrantes. Y es que ahora el universo ya no es una matriz infinita, sino un cuadrante. Y cada cuadrante tiene cuatro cuadrantes hijos (noroeste, noreste, suroeste y sureste), así hasta llegar al cuadrante mínimo ya no tiene hijos sino que es una celda viva o muerta. Esto evidentemente pone limitaciones al tamaño del universo, que será siempre potencia de dos.
El almacén es una tabla hash, pero no una corriente tipo HashMap de Java o Dictionary de C# sino que toma 4 elementos como índice, cuatro subcuadrantes. Si existe un elemento cuyos cuatro subcuadrantes son iguales (no se comprueba la igualdad exactamente, sería muy lento), se devuelve la siguiente iteración del cuadrante del almacén que cumple esos requisitos. De este modo no hace falta calcular los cuadrantes nada más que la primera vez que el programa se encontró con ellos.
Este sistema consume más memoria, pero mejora de forma sustancial la velocidad de ejecución. El algoritmo luego tiene bastantes más detalles (el diablo está en los detalles), pero esa es la idea principal, no calcular los cuadrantes más que una sola vez.
Podéis descargar Conway desde GitHub y compilarlo en Windows y GNU/Linux (Mac no está probado pero en principio funcionaría), con .NET Core 2.0 instalado.
- El clásico algoritmo de la matriz infinita.
- Un algoritmo usando Quadtrees y tablas de dispersión optimizadas, que permite tener patrones precalculados.
La velocidad de este segundo algoritmo es muy superior a la del primero, aunque he de confesar que este segundo algoritmo no resulta evidente y tiene una desventaja en el modo gráfico. Este segundo algoritmo avanza a trompicones, por lo que no es posible realizar una animación gráfica idónea, a no ser que lo modifiquemos ligeramente. Este tercer algoritmo que es una modificación del segundo, es más lento, pero permite ser mostrado por la pantalla.
El programa admite ficheros tanto en formato estándar RLE como un formato propio, que hemos llamado Vaca. Puedes pasarte por la wiki del juego de la vida y probar los ficheros RLE que encuentres. No obstante, hay que tener cuidado, pues algunos ficheros RLE no son del juego de la vida, sino de otros juegos con normas ligeramente modificadas.
¿En qué consiste el Juego de la Vida?
El juego de la vida es un autómata celular de dos dimensiones. También se le ha categorizado como juego para cero jugadores.
El juego tiene unas normas sencillas. Cada celda puede estar viva o muerta. En la siguiente evolución, las celdas pueden pasar a vivas o muertas siguiendo este esquema:
- Una célula muerta con exactamente 3 células vecinas vivas "nace" (es decir, al turno siguiente estará viva).
- Una célula viva con 2 o 3 células vecinas vivas sigue viva, en otro caso muere o permanece muerta (por "soledad" o "superpoblación").
Unas condiciones de partida determinadas podrán desencaminar comportamientos complejos y emergentes muy interesantes como las pistolas de gliders.
[video width="1364" height="704" mp4="https://files.adrianistan.eu/GosperGliderGun.mp4" webm="https://files.adrianistan.eu/GosperGliderGun.webm"][/video]
Uso
Pantalla de inicio de ConwayDesde aquí podemos dar a Nuevo patrón o Cargar patrón. Si le damos a Nuevo Patrón tendremos una matriz vacía y limpia. Podemos hacer click con el ratón para ir activando/desactivando las casillas. Puedes usar las teclas W, A, S y D o las flechas en pantalla para moverte por el universo infinito de Conway.
Una vez lo tengamos podemos guardarlo para no tener que volver a dibujarlo. Otra opción es cargar un patrón de la lista. Este programa admite formato RLE y Vaca, pero solo guarda archivos en formato Vaca.Para ejecutar el juego de la vida hay tres botones importantes. El primero es Ejecutar, que ejecuta el juego de la vida indefinidamente. Se para cuando pulsamos Parar (el mismo botón).
El otro es Siguiente, que nos permite avanzar de iteración en iteración manualmente, muy interesante para observar al detalle ciertos patrones. Por otro lado tenemos Iterar N veces, que permite iterar N veces y que sirve para pruebas de rendimiento. Hay que tener en cuenta que tanto Siguiente como Iterar N veces funcionan un poco distinto con el algoritmo Quadtree (el activado por defecto), ya que este algoritmo hace varias evoluciones de golpe, para ser todavía más rápido. La parte mala es que no es posible ver en detalle cada algoritmo.
Algoritmo Matriz
[video width="1008" height="486" mp4="https://files.adrianistan.eu/AlgoritmoMatriz.mp4" webm="https://files.adrianistan.eu/AlgoritmoMatriz.webm"][/video]
Algoritmo Quadtree
[video width="1008" height="486" mp4="https://files.adrianistan.eu/AlgoritmoQuadtree.mp4" webm="https://files.adrianistan.eu/AlgoritmoQuadtree.webm"][/video]
Línea de comandos
Es posible ejecutar el juego de la vida en línea de comandos. Este modo permite cargar un archivo Vaca o RLE y ejecutarlo N iteraciones. Al finalizar se muestran estadísticas y se permite guardar el resultado o mostrarlo por pantalla con caracteres ASCII.
Hay dos parámetros, -i para indicar el fichero de entrada y -n para indicar las iteraciones a calcular.
Algoritmo Quadtree
¿Cómo funciona el algoritmo quadtree que tanto mejora el rendimiento del juego de la vida? Siendo sinceros, no es algoritmo sencillo o evidente. Su nombre más correcto es algoritmo Hashlife y fue descrito por Bill Gosper en los laboratorios de investigación de Xerox Palo Alto.
La idea básica es que muchas veces en el juego de la vida nos encontramos con patrones que se van repitiendo periódicamente y grandes zonas vacías.
Para ello recurre a un almacén de cuadrantes. Y es que ahora el universo ya no es una matriz infinita, sino un cuadrante. Y cada cuadrante tiene cuatro cuadrantes hijos (noroeste, noreste, suroeste y sureste), así hasta llegar al cuadrante mínimo ya no tiene hijos sino que es una celda viva o muerta. Esto evidentemente pone limitaciones al tamaño del universo, que será siempre potencia de dos.
El almacén es una tabla hash, pero no una corriente tipo HashMap de Java o Dictionary de C# sino que toma 4 elementos como índice, cuatro subcuadrantes. Si existe un elemento cuyos cuatro subcuadrantes son iguales (no se comprueba la igualdad exactamente, sería muy lento), se devuelve la siguiente iteración del cuadrante del almacén que cumple esos requisitos. De este modo no hace falta calcular los cuadrantes nada más que la primera vez que el programa se encontró con ellos.
Este sistema consume más memoria, pero mejora de forma sustancial la velocidad de ejecución. El algoritmo luego tiene bastantes más detalles (el diablo está en los detalles), pero esa es la idea principal, no calcular los cuadrantes más que una sola vez.
Descargar Conway
Podéis descargar Conway desde GitHub y compilarlo en Windows y GNU/Linux (Mac no está probado pero en principio funcionaría), con .NET Core 2.0 instalado.