Publicado el 2020-04-24
En este post voy a (presumir) explicar mi implementación del juego de la vida de John Conway dentro de SHENZHEN I/O[1]. Este[2] video lo muestra en acción con un "oscilador"[3].
El juego está implementado en una matriz de 29x34 siguiendo este enfoque de Wikipedia en inglés[4].
If it is desired to save memory, the storage can be reduced to one array plus two line buffers. One line buffer is used to calculate the successor state for a line, then the second line buffer is used to calculate the successor state for the next line. The first buffer is then written to its line and freed to hold the successor state for the third line.
[4] Algoritmos para implementar el juego de la vida
Traducido al español diría más o menos lo siguiente:
Si se desea ahorrar memoria, el almacenamiento se puede reducir a un arreglo más dos buffers de línea. Un buffer se usa para calcular el estado siguiente para una línea, luego el segundo buffer se usa para calcular el estado siguiente para la línea siguiente. El primer buffer se escribe a su línea correspondiente y se libera para almacenar el estado siguiente de la tercer línea.
Dado que voy a necesitar almacenar el estado de dos líneas completas de 29 celdas cada una, estoy usando dos módulos de RAM 100P-33. El módulo de ROM 200P-33 se usa para saber cómo calcular el número de vecinos vivos para cada celda, pero más sobre eso luego. El resto de la placa es la pantalla, un botón, y 8 módulos MC6000. No creo que hubiese podido meter un solo elemento más a la placa, y tengo un total de 8 líneas de código libres, así que diría que estoy bastante en el límite. Sin contar que, prácticamente, tuve que hacer magia para poder cablear todo. Pero sigamos...
Primero que nada veamos cómo está diseñado el circuito y qué rol tiene cada pieza en todo el proceso.
Esta es la parte fácil. Antes de apretar el botón de arriba, este MC6000 es el único controlador ejecutando código (los demás duermen), y su única responsabilidad es apagar y prender los píxeles de la pantalla de acuerdo a lo que el usuario toca. No es muy complejo así que voy a obviar su explicación.
Una vez que apretás el botón, el control es cedido al MC6000 en #2. Si esto fuera un programa escrito en un lenguaje de alto nivel, este sería el bucle exterior.
Este controlador ejecuta una iteración por fila de la matriz. Por cada fila le pedirá a #3 que calcule el estado de esa fila en la siguiente generación. Luego le pedirá a #4 que dibuje la fila anterior. Finalmente le sumará 29 (el largo de una fila) a su contador y repetirá el bucle.
También hay un caso especial para la primera fila donde se salta el dibujado de la fila previa, puesto que no existe. Además, cada vez que cede el control a otro módulo, espera por una respuesta del mismo para evitar cualquier problema relacionado con concurrencia.
El primer módulo en #3, #3.1, recibe la fila en la que trabajar de #2. Va a iterar sobre cada celda de la fila y le pedirá a #3.2 que calcule el estado de las mismas para la próxima generación. Cuando completa la fila, le responde de vuelta a #2 para hacerle saber que terminó. También se encarga de saltarse el bucle si el offset es 986, pues intentaría trabajar sobre una fila inexistente.
El módulo #3.2 se encarga de calcular el estado siguiente de una celda basándose en el número de vecinos vivos, y #3.3 ejecuta el conteo en sí. #3.3 hace uso del extraño módulo ROM. Ese módulo tiene dos propósitos:
1. Saber la distancia de la celda actual hasta su primer (izquierda-arriba) vecino, y las distancias de cada vecino al próximo.
2. Saber cuáles celdas especiales no tienen vecinos. Por ejemplo, deberíamos recordar que una celda en el borde izquierdo de la matriz no tendrá los 3 vecinos a su izquierda.
Entonces, para cada celda, #3.3 necesita chequear el estado de sus 8 vecinos, y saltarse los vecinos que no existan. Revisemos el flujo para una celda en particular:
1. Primer leemos el índice especial de la ROM. El primer índice especial es 1.
1.1. Si estamos en la celda 1, deberíamos saltarnos la siguiente distancia porque está destinada a obtener el estado del vecino de arriba a la izquierda. La celda 1 no tiene vecinos a su izquierda.
1.2. Si no estamos en la celda 1, entonces nos movemos -30 celdas (es decir, hacia atrás) para ir al vecino de arriba a la izquierda.
2. Si no estábamos en un índice especial, chequeamos el estado de ese píxel en la pantalla y lo comunicamos de vuelta a #3.2.
El bucle luego se repite para el vecino de arriba, el de arriba a la derecha, el de la izquierda, y así. Si el índice especial es 0 significa que ese vecino en particular siempre existe y no necesitamos saltarlo.
Mientras tanto, #3.2 está contando todos los vecinos vivos en acc. Bueno, en realidad estamos contando vecinos y la celda actual, pues es más fácil de esa manera. Cuando #3.3 devuelve -999 significa que ha finalizado y que podemos escribir el estado siguiente de esta celda en la RAM. Si la cantidad es 3 escribimos 1 (nace), si es 4 escribimos -1 (se mantiene), y sino escribimos 0 (muere). Notarás que no escribimos directamente a la RAM sino que en su lugar usamos #5.1. Más sobre ese tema en la sección 5: Controlador de RAM.
La última parte consiste en leer el estado siguiente de una fila dada y dibujarlo en la pantalla. El estado, como lo guardamos, no es "absoluto", o sea que no podemos simplemente tomarlo y escribirlo tal cual está en la pantalla. Debemos considerar el valor especial -1 que significa "dejá el píxel en su estado actual". #4.1 se encarga de ciclar sobre la fila y pasarle el índice de la celda a #4.2 junto con su estado actual. #4.2 toma el índice y el estado actual, lee el estado siguiente de la celda desde la RAM (de nuevo, no directamente sino a través del Controlador de RAM), y aplica las transformaciones necesarias para obtener el estado final y dibujarlo en pantalla.
Los módulos de RAM no se escriben o leen de forma directa, sino que en su lugar puse dos MC6000 que actúan como controladores. Si prestás atención a la cita de Wikipedia, necesitamos guardar el estado siguiente de una fila n a nuestra RAM 1, luego la fila n+1 a RAM 2, luego la fila n+2 a la RAM 1 de nuevo, y así sigue... De forma similar, cuando leemos los estados futuros para dibujarlos en pantalla, lo hacemos primero de la RAM 1, luego de la 2, luego de la 1...
El módulo #5.1 se encarga de esa alternancia cuando escribimos a los módulos de RAM. Se asegura que escribamos exactamente 29 valores a un módulo y luego cambiemos al otro. #5.2 hace lo mismo pero para las lecturas. Puesto que no podemos dormir hasta que un puerto está siendo leído, #5.2 le pide a #4.2 que escriba algo en x1 para despertarlo. Quitando eso, el código de los dos módulos es bastante similar.
Este pequeño truco funciona de maravilla. Ni siquiera necesitamos reiniciar las direcciones de memoria ya que los punteros ciclan automáticamente cuando llegan al final.
El juego de la vida puede escribirse en un lenguaje moderno en cuestión de minutos. Ahora, con un poco de imaginación y voluntad, podés hacer que esa tarea te lleve días si lo escribís en el entorno apropiado (¿o menos apropiado?).
Espero que esto te inspire a también buscar formas extremadamente complicadas de escribir software que de otra manera es bastante básico. Suena tonto, pero (ahora sí en serio) es una buena forma de aprender o practicar los fundamentos de la arquitectura de computadoras. El código completo está acá[5] en su formato original así podés tirarlo en tu carpeta del SHENZHEN y enloquecerte. También vas a precisar la imágen para la pantalla táctil[6].
Por último, si el tamaño de la placa te resulta demasiado limitante, probá el ShenzhenMod de gtw123[7].
![[6] Pantalla táctil](29x34-matrix.png){kind=link}