2017 veröffentlichten zwei Wissenschaftler, der Kanadier John Aycock und die Britin Tara Copplestone, eine Analyse des Klassikers Entombed für die Videospielkonsole Atari 2600 . Die Mechanik dieses 1982 veröffentlichten Spiels ist äußerst einfach: Der vom Spieler kontrollierte Archäologe muss sich von unten nach oben durch die rollenden Katakomben bewegen und Zombies ausweichen.
Der Atari 2600 hatte nur 128 Byte RAM; Trotzdem war das scheinbar endlose Labyrinth bei jedem Start neu. im Speicher generiert. Wie haben die Programmierer das geschafft? Hier ist ein Kommentar von Stephen Sidley, dem Programmierer, der dieses Spiel vor 38 Jahren erstellt hat:
- . , , . , , , , , .
Wikipedia listet ein Dutzend verschiedener Algorithmen zur Erzeugung von Labyrinthen auf. Von größtem Interesse für Spielekonsolen ist der " Eller-Algorithmus ", der 1982 von Martin Eller von Microsoft entwickelt wurde. Mit dem Eller-Algorithmus können Sie Zeile für Zeile ohne Zyklen verbundene Labyrinthe erstellen. Um ein Labyrinth mit unbegrenzter Höhe zu erstellen, müssen nur die letzten Zeilen im Speicher gespeichert werden. Es scheint, dass dies genau das ist, was Entombed braucht! Leider ist Ellers Algorithmus nicht mit der Spielmechanik eines vertikalen Scrollers kompatibel, da Sie im resultierenden Labyrinth regelmäßig Hindernisse von oben umgehen müssen. Um dies zu demonstrieren, habe ich Ellers Algorithmus leicht modifiziert, sodass das Labyrinth in einer Matrix aus "Wänden" und "Passagen" erstellt wird, wie in Entombed:
Anspruchsvollere Algorithmen, die Rekursion und dergleichen verwenden, würden nicht in 128 Bytes RAM passen. Die Anforderungen für den Algorithmus für Entombed sind also:
- Zeile für Zeile Erzeugung von Labyrinthen unbegrenzter Höhe;
- Die erstellten Labyrinthe sollten so wenig getrennte Abschnitte wie möglich haben. (Der Spieler hat eine begrenzte Fähigkeit, "Wände zu durchbrechen", so dass seltene Inkohärenz kein Problem darstellt.)
- Erstellte Labyrinthe sollten hauptsächlich aus verzweigten und verbindenden vertikalen Passagen bestehen - damit der Passage des Labyrinths keine Aufwärtsbewegung erfordert;
- Nur die letzten generierten Linien sollten verwendet werden, um neue Linien des Labyrinths zu erzeugen. (Da der Atari 2600 keinen Videopuffer hat, müssen alle auf dem Bildschirm sichtbaren Zeilen des Labyrinths in irgendeiner Form in 128 Bytes Hauptspeicher gespeichert werden.)
Wer und wie hat dieser Algorithmus erstellt?
Zwei Wissenschaftler, die sich "Videospiel-Archäologen" nennen, beschlossen, ihre Forschung mit Entombed zu beginnen - einem Spiel über einen Archäologen in einem Labyrinth. Während ihrer Recherchen haben sie Stephen Sidley aufgespürt und ihn gefragt, mit welchem Algorithmus er das Labyrinth erzeugt hat. Wie bereits erwähnt, sagte Sidley ihnen, dass selbst der Autor des Algorithmus sich nicht erinnern könne, was sein Algorithmus sei, und Sidley selbst noch mehr. Dann versuchten die Forscher, den "Junkie" zu finden, der diesen Algorithmus erstellt hatte. Die zweite Hälfte der Geschichte wurde in einem 2008 veröffentlichten Interview gefunden :
Entombed [Duncan Muirhead] [Paul Allen Newell]. - , , , . , . , VCS [Atari 2600], . , . , , . , Towering InfernoVerwenden Sie dort einen Teil unseres Algorithmus und beenden Sie das Programm. Nachdem ich gegangen war, stellte die Firma Stephen Sidley ein und übergab ihm den Labyrinthgenerator. Er musste einen wesentlichen Teil meines Codes löschen, um Platz für Spielmechaniken zu schaffen. [Beim Atari 2600 ist es zusätzlich zu den strengen Einschränkungen bei der Größe von RAM und ROM erforderlich, dass die Erzeugung jeder Pixelreihe genau 76 Anmerkungen des Autors enthält ].
Sidley erwähnte, dass der Labyrinthgeneratorcode in der 6502-Assembly ohne Kommentare geschrieben wurde. Das an sich sieht nach einer Leistung aus: wie bereits erwähnt khimdort "ist der Befehlssatz so begrenzt und krumm, dass beim Schreiben von Programmen die Hauptfrage auftaucht:" Wie kann ich etwas über dieses Wunder schreiben? " Trotzdem haben die Forscher den Spielcode untersucht und festgestellt, dass das Labyrinth wie folgt generiert wird: Für jede der acht Zellen der generierten Zeile werden fünf bereits generierte Zellen berücksichtigt (drei oben und zwei links), und gemäß der "magischen Tabelle" wird der Status der neuen Zelle ausgewählt (Durchgang, Wand oder zufällige Wahl). Die beiden Zellen ganz links sind immer voll und werden nicht gespeichert. Die rechte Hälfte des Labyrinths ist nur ein Spiegelbild der linken.
Ein mysteriöser Tisch im Herzen eines ungelösten Algorithmus
Die Eigenschaften des erzeugten Labyrinths hängen vom Zustand des neuen Zellensatzes für jeweils fünf zuvor erzeugte Zellen ab. In Entombed eingenähte Tabelle, viele verwirrte Forscher: "Wir haben keine Gesetze bemerkt, auch wenn wir verschiedene Möglichkeiten haben, sie in Form einer Karnaugh-Karte darzustellen ." Sidley sagte in der gleichen Weise: "Für mich bleibt es ein Rätsel: Ich konnte es nicht entwirren und benutzte es als Black Box." Das Fehlen von Regelmäßigkeiten in der Tabelle ist jedoch etwas übertrieben: Auf der Karnot-Karte können Sie beispielsweise sehen, dass bei c = 1 (der Wand oben links in der aktuellen Zelle) X = 1 (die Wand in der aktuellen Zelle) nicht generiert wird .
BBC in ihrem BerichtÜber die „digitale Archäologie“ griff sie auf noch dramatischere Übertreibungen zurück: „Der Tisch ist wirklich genial: Jedes Mal, wenn Sie das Spiel starten, wird ein neues Labyrinth erstellt, durch das Sie von Anfang bis Ende gehen können. Wenn die Werte in dieser Tabelle sogar geringfügig abweichen würden, würde sich das Labyrinth höchstwahrscheinlich als unpassierbar herausstellen. Es ist einfach unerklärlich. " Der Repost auf hackaday.com ist noch sicherer formuliert: "Ein mysteriöser Tisch erzeugt immer passable Labyrinthe, aber wenn Sie Teile daran ändern, wird das Rätsel unlösbar." Tatsächlich war das Labyrinth nicht immer kohärent, wie im Video des Spiels zu sehen ist . und kleine Änderungen in der Tabelle haben keine spürbaren Auswirkungen auf die resultierenden Labyrinthe: Ich habe eine JavaScript-Version erstellt, in dem Sie selbst mit dem "mysteriösen Tisch" spielen können - ändern Sie ihn direkt "unterwegs" und beobachten Sie, wie sich das Labyrinth dadurch verändert. Wahrscheinlich ging die Garantie für die Labyrinth-Konnektivität, die Paul Newell in seinem Interview erwähnte, zusammen mit dem gelöschten Teil des Codes verloren.
Archäologie von Videospielen
John Aycock kommentierte, wie Entombed zum Gegenstand seiner Forschung wurde: Er bereitete eine Reverse Engineering-Aufgabe für seine Schüler vor und entschied sich für ein relativ wenig bekanntes Spiel, da die Schüler für beliebte Spiele bereits analysierten Code im Internet finden konnten. Wenn solch ein herausragender Fund in einem zufällig ausgewählten Spiel gefunden wurde, bedeutet das, dass es in fast jedem Spiel dieser Zeit brillante Programmierlösungen gibt, müssen Sie nur tiefer graben? Stephen Sidley verglich das Design für den Atari 2600 mit seinem mageren Befehlssatz, 128 Byte RAM und 76 Takten pro Pixelzeile mit dem "Besteigen des Mount Everest ohne Sauerstofftanks" : Die Einschränkungen der Plattform zwangen Programmierer, ausgeklügelte Algorithmen zu erfinden.
Tiefer graben ist nicht nur eine Metapher. Die Erforschung klassischer Videospiele wird sowohl durch die Fragilität der Medien, auf denen sie aufgezeichnet wurden, als auch durch die Behandlung alter Spiele als uninteressanten Müll erschwert. 1983 hat Atari 47 Tonnen Atari 2600-Patronen auf einer Mülldeponie abgeladen - nicht weniger als ein Dutzend volle Lastwagen! Diese von einer Asphaltwalze zerkleinerten und mit Beton übergossenen Patronen lagen 30 Jahre lang, bis 2014 "digitale Archäologen" die Erlaubnis erhielten, die erhaltenen Patronen auszuheben und wiederzugewinnen. Keine der gegrabenen Patronen funktionierte, aber mindestens eine von ihnen wurde durch Löten der Komponenten wiederhergestellt .
Das Verhalten von Atari, der Beton in Patronen gegossen hat, um sie vor "Dieben" zu schützen, ist sehr typisch für Inhaber von Urheberrechten, die ihre Arbeit leichter in ewige Vergessenheit versetzen würden, als "entgangenen Gewinn" durch die Tatsache zu erleiden, dass ihr geistiges Eigentum jemandem kostenlos zur Verfügung gestellt wird. Aber vielleicht ist es nicht zu spät, die "virtuelle Kulturschicht" des 20. Jahrhunderts durch das kostenlose Kopieren von Programmen zu schützen, die längst ihren kommerziellen Wert verloren haben?
