En 2017, dos científicos, el canadiense John Aycock y la británica Tara Copplestone, publicaron un análisis del clásico juego Entombed para la consola de videojuegos Atari 2600 . La mecánica de este juego, lanzado en 1982, es extremadamente simple: el arqueólogo, controlado por el jugador, debe abrirse paso a través de las catacumbas de desplazamiento de abajo hacia arriba, esquivando zombis.
El Atari 2600 solo tenía 128 bytes de RAM; sin embargo, el laberinto aparentemente interminable era nuevo con cada lanzamiento; generado en la memoria. ¿Cómo lo gestionaron los programadores? Aquí hay un comentario de Stephen Sidley, el programador que creó este juego hace 38 años:
- . , , . , , , , , .
Wikipedia enumera una docena de algoritmos diferentes para generar laberintos. De gran interés para las consolas de juegos es el " algoritmo Eller ", creado en el mismo 1982 por Martin Eller de Microsoft. El algoritmo de Eller le permite crear laberintos conectados línea por línea sin ciclos, y generar un laberinto de altura ilimitada, es suficiente para almacenar solo el último par de líneas en la memoria. ¡Parece que esto es exactamente lo que Entombed necesita! Pero, por desgracia, el algoritmo de Eller es incompatible con la mecánica del juego de un desplazador vertical, porque en el laberinto resultante regularmente tienes que sortear obstáculos desde arriba. Para demostrar esto, modifiqué ligeramente el algoritmo de Eller para que el laberinto se cree en una matriz de "paredes" y "pasajes", como en Entombed:
Algoritmos más sofisticados que usan recursividad y similares no encajarían en 128 bytes de RAM. Entonces, los requisitos para el algoritmo de Entombed son:
- Generación línea por línea de laberintos de altura ilimitada;
- Los laberintos creados deben tener la menor cantidad posible de secciones desconectadas; (el jugador tiene una capacidad limitada para "romper paredes", por lo que la incoherencia rara no es un problema)
- Los laberintos creados deben consistir principalmente en ramificar y conectar pasajes verticales, de modo que el paso del laberinto no requiera movimiento hacia arriba;
- Solo las últimas líneas generadas deben usarse para generar nuevas líneas del laberinto. (Dado que el Atari 2600 no tiene un búfer de video, todas las líneas del laberinto visibles en la pantalla deben almacenarse de alguna forma en 128 bytes de memoria principal).
¿Quién y cómo creó este algoritmo?
Dos científicos que se autodenominan "arqueólogos de videojuegos" decidieron comenzar su investigación con Entombed, un juego sobre un arqueólogo en un laberinto. Durante su investigación, rastrearon a Stephen Sidley y le preguntaron qué algoritmo utilizó para generar el laberinto. Como ya se mencionó, Sidley les dijo que incluso el autor del algoritmo no podía recordar cuál era su algoritmo, y el propio Sidley, aún más. Luego, los investigadores trataron de encontrar al "adicto" que creó este algoritmo; La segunda mitad de la historia se encontró en una entrevista publicada en 2008:
Entombed [Duncan Muirhead] [Paul Allen Newell]. - , , , . , . , VCS [Atari 2600], . , . , , . , Towering Inferno, usando parte de nuestro algoritmo allí, y salga. Después de que me fui, la empresa contrató a Stephen Sidley y le entregó el generador del laberinto. Tuvo que eliminar una parte importante de mi código para dejar espacio a la mecánica del juego. [En el Atari 2600, además de las severas restricciones en la cantidad de RAM y ROM, también es un requisito que la generación de cada fila de píxeles tome exactamente 76 ciclos de nota del autor ].
Sidley mencionó que el código del generador de laberinto fue escrito en el ensamblaje 6502 sin ningún comentario. Esto en sí mismo parece una hazaña: como se señaló khim, allí "el conjunto de comandos es tan limitado y torcido que al escribir programas, surge la pregunta principal," ¿cómo puedo escribir algo sobre este milagro? " Sin embargo, los investigadores profundizaron en el código del juego y descubrieron que el laberinto se genera de la siguiente manera: para cada una de las ocho celdas de la fila generada, se consideran cinco celdas ya generadas (tres en la parte superior y dos en la izquierda), y de acuerdo con la "tabla mágica" se selecciona el estado de la nueva celda (pasaje, muro o elección aleatoria). Las dos celdas más a la izquierda están siempre llenas y no se almacenan en la memoria. La mitad derecha del laberinto es solo una imagen especular de la izquierda.
Una mesa misteriosa en el corazón de un algoritmo sin resolver
Las propiedades del laberinto generado dependen del estado del nuevo conjunto de celdas para cada cinco generadas previamente. Tabla cosida en Entombed, muchos investigadores desconcertados: "No notamos ninguna ley, incluso cuando tenemos varias formas de presentarla en forma de un mapa de Karnaugh ". Sidley dijo en la misma línea: "Para mí, ella sigue siendo un misterio: no pude desentrañarla y la usé como una caja negra". Sin embargo, la ausencia de regularidades en la tabla es un poco exagerada: por ejemplo, en el mapa de Karnot, puede ver que cuando c = 1 (el muro en la parte superior izquierda de la celda actual), X = 1 (el muro en la celda actual) no se generará .
BBC en su informesobre "arqueología digital" recurrió a exageraciones aún más dramáticas: "La mesa es realmente ingeniosa: cada vez que comienzas el juego, se crea un nuevo laberinto, a través del cual puedes ir de principio a fin. Si los valores de esta tabla fueran incluso ligeramente diferentes, lo más probable es que el laberinto resulte intransitable. Es simplemente inexplicable ". La nueva publicación en hackaday.com está formulada con más confianza: "Una mesa misteriosa siempre crea laberintos pasables, pero si cambias algo, el rompecabezas se volverá insoluble". De hecho, el laberinto no siempre fue coherente, como se puede ver en el video del juego ; y pequeños cambios en la tabla no tienen un efecto notable en los laberintos resultantes: hice una versión de JavaScript, en el que puedes jugar tú mismo con la "mesa misteriosa": cámbiala "sobre la marcha" y observa cómo cambia el laberinto como resultado. Probablemente, la garantía de conectividad del laberinto, que Paul Newell mencionó en su entrevista, se perdió junto con la parte eliminada del código.
Arqueología de videojuegos
John Aycock comentó cómo Entombed se convirtió en el objeto de su investigación: preparó una tarea de ingeniería inversa para sus estudiantes y eligió un juego relativamente poco conocido, porque para los juegos populares los estudiantes podían encontrar código ya analizado en la red. Si se encontró un hallazgo tan sobresaliente en un juego elegido al azar, ¿significa que en casi cualquier juego de ese tiempo habrá soluciones de programación brillantes, solo tienes que profundizar? Stephen Sidley comparó el diseño para el Atari 2600, con su escaso conjunto de instrucciones, 128 bytes de RAM y 76 relojes por línea de píxeles, con "escalar el Monte Everest sin tanques de oxígeno" : las limitaciones de la plataforma obligaron a los programadores a inventar algoritmos ingeniosos.
Cavar más profundo no es solo una metáfora. La investigación de los videojuegos clásicos es complicada tanto por la fragilidad de los medios en los que fueron grabados como por el tratamiento de los juegos antiguos como basura sin interés. En 1983, Atari arrojó 47 toneladas de cartuchos Atari 2600 en un vertedero , ¡nada menos que una docena de camiones completos! Aplastados por un rodillo de asfalto y vertidos con concreto, estos cartuchos permanecieron durante treinta años hasta que, en 2014, los "arqueólogos digitales" recibieron permiso para excavar y recuperar los cartuchos sobrevivientes. Ninguno de los cartuchos excavados funcionó, pero al menos uno de ellos se restauró soldando los componentes.
El comportamiento de Atari, que vertió hormigón en cartuchos para protegerlos de los "ladrones", es muy típico de los titulares de derechos de autor que con mayor facilidad consignarían su trabajo al olvido eterno que sufrirían "ganancias perdidas" por el hecho de que su propiedad intelectual llegaría a alguien de forma gratuita. ¿Pero tal vez no sea demasiado tarde para proteger la "capa cultural virtual" del siglo XX al permitir la copia gratuita de programas que han perdido su valor comercial durante mucho tiempo?
