Big Data Origins: Wie Super Mario bunt wurde

In meinem Beitrag „Big Data Origins: Super Mario hat‘s vorgemacht“ habe ich Super Mario zur Big-Data-Applikation der ersten Stunde erkoren. Doch beinahe hätte diese niemals das Licht der Welt erblickt, denn die Entwickler von Nintendo hatten einiges um die Ohren. Gemessen an den heutigen Ressourcen und Möglichkeiten scheinen sie zwar lächerlich gering, aber damals waren die Hardware-Anforderungen fast nicht zu stemmen. Heute könnte jedes Smartphone ganz nebenbei hunderte Figuren über den Bildschirm hüpfen lassen, in den 1980er Jahren ging das aber noch nicht so locker.

Heute hat jeder Video-Chip einen eigenen Arbeitsspeicher (RAM), den er zur Bildausgabe nutzen kann. Je nach Auflösung und Anzahl der angeschlossenen Ausgabegeräte kann da schon eine ziemliche Datenmenge zusammenkommen. Der Arbeitsspeicher des Systems wird dadurch aber nicht belastet, Programme, Datenbanken und Betriebssystem werden also nicht in ihrer Leistung eingeschränkt.

Für das System Nintendo NES sah die Architektur seinerzeit aber etwas anders aus:

Der Video-Chip hatte noch kein eigenes RAM und musste das RAM des Systems mitverwenden. Der Arbeitsspeicher musste also nicht nur für die Applikation und das Betriebssystem zur Verfügung stehen, sondern gleichzeitig zu jedem Zeitpunkt alle Bildschirmdaten bereit halten. Keine leichte Aufgabe, wenn man bedenkt, dass die NES nur ganze zwei KB (tatsächlich: KILObyte) RAM hatte. Manche Spiele, wie auch Super Mario, hatten deshalb noch zusätzlichen RAM (~6KB) in der Cartridge verbaut.

So kommen wir zu folgender Ausgangslage:

8 KB RAM verfügbar
Bildschirmauflösung 256×240 Pixel = 61.440 Pixel

61.440 Pixel entsprechen bei einem Bit Farbtiefe (schwarz/weiß) bereits knapp acht KB, das heißt, allein die Bildschirmausgabe konsumiert bereits so gut wie alles des zur Verfügung stehenden RAM. Bei größerer Farbtiefe wird die Entwicklung fast dramatisch:

1 Bit (2 Farben) ~8KB
4 Bit (16 Farben) ~32KB
8 Bit (256 Farben) ~64KB

Mit den vorhandenen Ressourcen erreichen wir somit gerade noch eine zweifarbige Ausgabe, also schwarz/weiß. Ein schwerer Schlag, doch wie kommt es dann dazu:

Es muss also einen Weg geben, denn Nintendo erreichte damals tatsächlich eine Farbtiefe von 8 Bit, also 256 Farben.

Wie brachte man aber 64 KB Information in weniger als acht KB RAM unter?

Es musste ein Weg gefunden werden, die Information effizienter darzustellen. Und die Lösung lag damals – wie auch bei den meisten Aufgabenstellungen heute – in der Anwendung von Analytik.

Versuchen wir uns also, wie die Nintendo-Entwickler vor 30 Jahren, der Herausforderung analytisch zu nähern. Das nächste Bild zeigt die Hauptfigur von „Super Mario“:

Sie setzt sich aus 252 Bildpunkten zusammen und benötigt bei acht Bit Farbtiefe insgesamt 2.016 Bit Speicherplatz. Diese 252 Bildpunkte zu je acht Bit sind der gesamte Datenraum, den es möglichst effizient zu beschreiben gilt. Dazu benötigen wir allerdings zunächst möglichst viele beschreibende Informationen über das Objekt, um ein geeignetes Modell ableiten zu können.

Im Falle einer herkömmlichen Datentabelle würden wir im ersten Schritt durch Exploration beziehungsweise Profiling versuchen, erste Korrelationen zu finden. Moderne Big-Data-Lösungen erledigen diese Aufgabe im Handumdrehen per Drag & Drop – auch auf sehr großen Datenmengen. Im Falle von Super Mario mussten die Entwickler diesen Schritt selbst erledigen und haben das Bild einfach in mehrere gleich große Segmente unterteilt:

Sie legten also einfach ein quadratisches Raster über das Bild und erhielten so viele kleine, gleich große Segmente.
Die nächste Aufgabe ist nun, Merkmale zu identifizieren, die auf möglichst viele Segmente zutreffen, diese also möglichst gut beschreiben. Also so etwas wie: „Jedes Segment hat vier Pixel.“

Bei Super Mario findet sich so ein global gültiges Merkmal zum Glück ebenfalls, auf den zweiten Blick sogar recht offensichtlich. Jedes der Segmente besteht nämlich aus nur zwei Farben. Die Farbkombination kann natürlich unterschiedlich sein, aber insgesamt gibt es nie mehr als zwei Farben in einem Segment – mit Sicherheit nicht ganz zufällig...

Wenn wir nun die einzelnen Segmente nach ihren Merkmalsausprägungen (Vordergrundfarbe, Hintergrundfarbe) gruppieren, kommen wir auf insgesamt 13 mögliche Farbkombinationen, viele davon treten mehrfach auf (siehe Abbildung).

Diese Erkenntnis ist entscheidend, denn die komplette Farbtiefe (1x8bit Vordergrundfarbe, 1x8bit Hintergrundfarbe) muss nur noch einmal pro Segmentgruppe gespeichert werden, und nicht länger für jedes einzelne Pixel. Die Einsparungen sind speziell bei der Darstellung von großen Flächen wie Wiesen oder Wolken signifikant und führen dazu, dass Nintendo seinen Helden in eine farbenfrohe Spielewelt schicken konnte.

Anmerkung:
Diese Technik nennt sich „Color Cells“ und war eine der ersten Bildkomprimierungsmethoden. Für Super Mario selbst kam darüber hinaus noch eine Methode namens „Sprites“ zum Einsatz.

Analytik hat also den Entwicklern damals geholfen, ein nicht unerhebliches Problem elegant zu lösen. Hätte ich damals aber gewusst, dass ich beim Spielen von „Super Mario“ technisch gesehen nur auf viele ineinander verschachtelte Schwarzweißaufnahmen blicke, hätte mich das vermutlich wenig begeistert...

Heute freue ich mich aber umso mehr, dass ich schon als Kind mit einem der ersten Data Scientists zusammengearbeitet habe 😀