En 2017, deux scientifiques, le canadien John Aycock et la britannique Tara Copplestone, ont publié une analyse du jeu classique Entombed pour la console de jeu vidéo Atari 2600 . La mécanique de ce jeu, sorti en 1982, est extrêmement simple: l'archéologue, contrôlé par le joueur, doit se frayer un chemin à travers les catacombes défilantes de bas en haut, en esquivant les zombies.
L'Atari 2600 n'avait que 128 octets de RAM; néanmoins, le labyrinthe apparemment sans fin était nouveau à chaque lancement; généré en mémoire. Comment les programmeurs l'ont-ils géré? Voici un commentaire de Stephen Sidley, le programmeur qui a créé ce jeu il y a 38 ans:
- . , , . , , , , , .
Wikipédia répertorie une douzaine d'algorithmes différents pour générer des labyrinthes. Le plus grand intérêt pour les consoles de jeux est l '« algorithme Eller », créé en 1982 par Martin Eller de Microsoft. L'algorithme d'Eller vous permet de créer des labyrinthes connectés ligne par ligne sans boucles, et de générer un labyrinthe de hauteur illimitée, il suffit de ne stocker que les deux dernières lignes en mémoire. Il semblerait que c'est exactement ce dont Entombed a besoin! Mais hélas, l'algorithme d'Eller est incompatible avec la mécanique de jeu d'un scroller vertical, car dans le labyrinthe qui en résulte, vous devez régulièrement contourner les obstacles d'en haut. Pour le démontrer, j'ai légèrement modifié l'algorithme d'Eller afin que le labyrinthe soit créé dans une matrice de «murs» et de «passages», comme dans Entombed:
Des algorithmes plus sophistiqués utilisant la récursivité et autres ne rentrent pas dans 128 octets de RAM. Ainsi, les exigences de l'algorithme pour Entombed sont:
- Génération ligne par ligne de labyrinthes de hauteur illimitée;
- Les labyrinthes créés doivent avoir le moins de sections déconnectées possible; (le joueur a une capacité limitée à "percer les murs", donc une incohérence rare n'est pas un problème)
- Les labyrinthes créés devraient consister principalement en des passages verticaux de branchement et de connexion - de sorte que le passage du labyrinthe ne nécessite pas de mouvement ascendant;
- Seules les dernières lignes générées doivent être utilisées pour générer de nouvelles lignes du labyrinthe. (Comme l'Atari 2600 n'a pas de tampon vidéo, toutes les lignes du labyrinthe visibles à l'écran doivent être stockées sous une forme quelconque dans 128 octets de mémoire principale).
Qui et comment a créé cet algorithme?
Deux scientifiques qui se disent «archéologues du jeu vidéo» ont décidé de commencer leurs recherches avec Entombed - un jeu sur un archéologue dans un labyrinthe. Au cours de leurs recherches, ils ont retrouvé Stephen Sidley et lui ont demandé quel algorithme il utilisait pour générer le labyrinthe. Comme déjà mentionné, Sidley leur a dit que même l'auteur de l'algorithme ne pouvait pas se souvenir de ce qu'était son algorithme, et Sidley lui-même, encore plus. Ensuite, les chercheurs ont essayé de trouver le "junkie" qui a créé cet algorithme; la seconde moitié de l'histoire a été retrouvée dans une interview publiée en 2008:
Entombed [Duncan Muirhead] [Paul Allen Newell]. - , , , . , . , VCS [Atari 2600], . , . , , . , Towering Inferno, en utilisant une partie de notre algorithme là-bas, et quittez. Après mon départ, l'entreprise a embauché Stephen Sidley et lui a remis le générateur de labyrinthe. Il a dû supprimer une partie importante de mon code pour faire de la place aux mécanismes de jeu. [Sur l'Atari 2600, en plus des restrictions sévères sur la quantité de RAM et de ROM, il est également nécessaire que la génération de chaque rangée de pixels prenne exactement 76 cycles note de l'auteur ].
Sidley a mentionné que le code du générateur de labyrinthe a été écrit dans l'assemblage 6502 sans aucun commentaire. Cela en soi ressemble à un exploit: comme indiqué khim, là "l'ensemble des commandes est si limité et tordu que lors de l'écriture de programmes, la question principale se pose," comment puis-je écrire quoi que ce soit sur ce miracle? " Néanmoins, les chercheurs ont creusé dans le code du jeu et ont découvert que le labyrinthe est généré comme suit: pour chacune des huit cellules de la ligne générée, cinq cellules déjà générées sont considérées (trois en haut et deux à gauche), et conformément à la "table magique", l'état de la nouvelle cellule est sélectionné (passage, mur ou choix aléatoire). Les deux cellules les plus à gauche sont toujours pleines et ne sont pas stockées en mémoire. La moitié droite du labyrinthe est juste une image miroir de la gauche.
Une table mystérieuse au cœur d'un algorithme non résolu
Les propriétés du labyrinthe généré dépendent de l'état du nouvel ensemble de cellules pour chaque cinq générés précédemment. Tableau cousu dans Entombed, de nombreux chercheurs perplexes: "Nous n'avons pas remarqué de lois, même lorsque nous avons plusieurs façons de le présenter sous la forme d'une carte de Karnaugh ." Sidley a déclaré dans la même veine: "Pour moi, cela reste un mystère: je n'ai pas pu le démêler, et je l'ai utilisé comme une boîte noire." Cependant, l'absence de régularités dans le tableau est un peu exagérée: par exemple, sur la carte de Karnot, vous pouvez voir que lorsque c = 1 (le mur en haut à gauche de la cellule courante), X = 1 (le mur dans la cellule courante) ne sera pas généré .
BBC dans son rapportà propos de «l'archéologie numérique», elle a eu recours à des exagérations encore plus dramatiques: «Le tableau est vraiment ingénieux: à chaque fois que vous démarrez le jeu, un nouveau labyrinthe se crée, à travers lequel vous pouvez passer du début à la fin. Si les valeurs de ce tableau étaient même légèrement différentes, le labyrinthe s'avérerait probablement infranchissable. C'est juste inexplicable. " Le republication sur hackaday.com est formulé avec encore plus de confiance: "Une table mystérieuse crée toujours des labyrinthes passables, mais si vous en changez des morceaux, le puzzle deviendra insoluble." En fait, le labyrinthe n'était pas toujours cohérent, comme on peut le voir dans la vidéo du jeu ; et les petits changements dans le tableau n'ont pas d'effet notable sur les labyrinthes résultants: j'ai fait une version JavaScript, dans lequel vous pouvez jouer vous-même avec la «table mystérieuse» - changez-la correctement «sur le pouce» et regardez comment le labyrinthe change en conséquence. Probablement, la garantie de la connectivité du labyrinthe, dont Paul Newell a parlé dans son interview, a été perdue avec la partie supprimée du code.
Archéologie des jeux vidéo
John Aycock a commenté comment Entombed est devenu le sujet de ses recherches: il préparait une tâche d'ingénierie inverse pour ses étudiants, et il a choisi un jeu relativement peu connu, car pour les jeux populaires, les étudiants pouvaient trouver du code déjà analysé sur le net. Si une découverte aussi exceptionnelle a été trouvée dans un jeu choisi au hasard, cela signifie-t-il que dans presque tous les jeux de cette époque, il y aura des solutions de programmation brillantes, il vous suffit de creuser plus profondément? Stephen Sidley a comparé la conception de l'Atari 2600, avec son maigre jeu d'instructions, 128 octets de RAM et 76 horloges par ligne de pixels, à «escalader le mont Everest sans réservoir d'oxygène» : les limites mêmes de la plate-forme ont obligé les programmeurs à inventer des algorithmes ingénieux.
Creuser plus profondément n'est pas qu'une métaphore. La recherche sur les jeux vidéo classiques est compliquée à la fois par la fragilité des médias sur lesquels ils ont été enregistrés et par le traitement des vieux jeux comme des déchets sans intérêt. En 1983, Atari a jeté 47 tonnes de cartouches Atari 2600 dans une décharge - pas moins d'une douzaine de camions pleins! Écrasées par un rouleau d'asphalte et recouvertes de béton, ces cartouches sont restées trente ans jusqu'à ce qu'en 2014, les «archéologues numériques» aient reçu l'autorisation de fouiller et de récupérer les cartouches survivantes. Aucune des cartouches creusées n'a fonctionné, mais au moins une d'entre elles a été restaurée en soudant les composants.
Le comportement d'Atari, qui a coulé du béton dans des cartouches pour les protéger des «voleurs», est très typique des détenteurs de droits d'auteur qui abandonneraient plus facilement leur travail à un oubli éternel que subiraient des «pertes de profits» du fait que leur propriété intellectuelle serait donnée à quelqu'un gratuitement. Mais il n'est peut-être pas trop tard pour protéger la «couche culturelle virtuelle» du XXe siècle en permettant la copie gratuite de programmes qui ont depuis longtemps perdu leur valeur commerciale?
