Im Fokus

Alternative Kachelungen für Computerspiele

Die Welt vieler (Computer-)Spiele ist in ebene Raster aus meist quadratischen Kacheln strukturiert. In diesem Artikel werden alternative Kachelungsmöglichkeiten vorgestellt.

Raster in (Computer-)Spielen

Wenn wir Brett-Spiele und Computer-Spiele betrachten, so macht sich eine Gemeinsamkeit bemerkbar: Die Welt dieser Spiele ist oft als Anordnung identischer Felder bzw. Kacheln umgesetzt, die ein regelmäßiges Raster bzw. genauer gesagt eine periodische Kachelung (auch periodische Parkettierung genannt) bilden. Mathematisch besteht die Spielwelt aus einem Ausschnitt bzw. Teilbereich der euklidischen Ebene, der mit geometrischen Figuren lückenlos und ohne Überlappungen periodisch ausgefüllt ist. Periodisch bedeutet hier, dass ein Ausschnitt des Spielfelds, um einen bestimmten Betrag seitlich verschoben, wieder genau in das Spielfeld passt. In Spielen finden wir erfahrungsgemäß überwiegend eine der drei Platonischen Kachelungen aus regulären (gleichseitigen und -winkligen) Dreiecken, Vierecken und Sechsecken.

Eigenschaften der Platonischen Kachelungen

  • Das Parkett besteht aus lauter kongruenten regulären Polygonen
  • Jede Seite eines Polygons ist Seite eines anderen Polygons, d. h. nirgends trifft eine  Ecke auf eine Seite
Abbildung 1: Die drei platonischen Kachelungen.

Abbildung 1: Die drei platonischen Kachelungen.

Unter Brettspielen besonders populär sind quadratische Kacheln (z. B. Schach, Go), seltener sechseckige Kacheln (z. B. das relativ neue Spiel »Siedler von Catan«) oder dreieckige Kacheln (z. B. Stern-Halma).

Schach, Halma, Die Siedler von Catan

Abbildung 2: Schach, Halma, Die Siedler von Catan

Unter Computerspielen sind ebenso quadratische Kacheln besonders häufig vertreten (z. B. Sim City, Civilization I – IV, Command & Conquer, Diablo I-II, Starcraft), wohingegen Strategie-Spiele auch gerne hexagonale (sechseckige) Kacheln verwenden (z. B. Civilization V).

Abbildung 3: Computerspiele Sim City 2000, Diablo II, Civilization 5

Abbildung 3: Computerspiele Sim City 2000, Diablo II, Civilization 5

Eigenschaften von Parkettierungen für Spiele

Solche regelmäßigen Raster bieten sich für Spiele (wie auch für Simulationen) an, da hierdurch Regeln auf kleinen Ausschnitten des Spielfelds definiert werden können, die dann auf allen Kacheln anwendbar sind. Als Beispiel sei hier auf die Zug-Regeln des Schachspiels verwiesen. Der Vorteil von Quadrat-Rastern ist die einfache Abbildbarkeit auf karthesische Koordinaten. Über Umwege lassen sich aber auch Dreiecke und Sechsecke darauf abbilden.

Eine Möglichkeit, den drei platonischen Kachelungen je ein Koordinatensystem zuzuordnen.

Abbildung 4: Eine Möglichkeit, den drei platonischen Kachelungen je ein Koordinatensystem zuzuordnen.

Ein Vorteil sechseckiger Kacheln besteht darin, dass die Entfernungen zwischen sechseckigen Kacheln weniger unausgewogen verteilt sind als zwischen quadratischen, wobei hier wiederum ein Ungleichgewicht zwischen den Richtungen »Nord-Süd« und »Ost-West« unvermeidbar ist, da sich die sechs Hauptrichtungen des hexagonalen Rasters nicht mit den vier Himmelsrichtungen des Quadrat-Rasters in Übereinstimmung bringen lassen.

In einem Hexagon-Raster hat eine Kachel nur über Kanten angrenzende Nachbarn. Dagegen sind in einem Quadrat-Raster die Hälfte der Kacheln nur über eine Ecke benachbart. Das Auszählen der Hexagon-Kacheln der kürzesten Route zwischen zwei beliebigen Punkten liefert eine gute Näherung der wahren Entfernung. Bei quadratischen Parkettierungen haben dagegen zwei Kacheln die sich nur an den Ecken berühren den √2-fachen Abstand zweier sich über eine Kante berührender Kacheln, was beim Abzählen im schlimmsten Fall zu einem Fehler von gut 40% führt.

Quadratische Kacheln lassen sich leicht zu größeren Rechtecken zusammenfassen, etwa um ein Gebäude zu platzieren, das nicht in ein einzelnes Feld passt. Vielleicht wirken sie wegen dieser sehr gleichmäßigen Struktur eher künstlich (man denke etwa an das Raster der Straßenzüge von Manhattan). Hexagonale Kacheln zu größeren Sechsecken zusammenzufassen ist nicht exakt möglich, denn die daraus zusammengesetzten Formen weisen immer einen gezackten Rand auf. Dies könnte ein Grund dafür sein, dass hexagonale Raster abwechslungsreicher und eher organisch wirken (und somit gerne für Landschaften in Strategie-Spielen Verwendung finden).

Eine Kachelung aus Dreiecken weist einerseits ähnliche Eigenschaften auf wie eine aus Sechsecken (man stelle sich vor, jedes Sechseck der hexagonalen Kachelung in sechs gleiche Dreiecke zu zerlegen). Allersdings berühren sich hier noch mehr Kacheln nur über eine Ecke. Im Gegensatz zu Sechsecken lassen sich andererseits die Dreiecke auch zu größeren Dreiecken gruppieren. Eine Unannehmlichkeit bei der Verwendung von Dreiecks-Kacheln liegt darin, dass die Hälfte dieser (bezüglich einer Translation d. h. Verschiebung) »auf dem Kopf« steht und daher z. B. in einem Computerprogramm gesondert behandelt werden muss.

Raster pro und contra

Es gibt natürlich auch viele (Computer-)Spiele, die ohne ein zugrundeliegendes Raster auskommen (z. B. verschiedene Adventures, Flugsimulatoren, Autorennspiele…), was mehr Freiheit in der Spielgestaltung zulässt, auf der Schattenseite jedoch auch zu völliger Beliebigkeit des Leveldesigns führen kann.

Doch brauchen nicht all Spiele diese völlige Freiheit. Die Verwendung eines Spielrasters erlaubt in vielen Fällen, die Spielregeln einfacher zu formulieren (Gedankenexperiment: Man stelle sich vor, Schach-Figuren dürften sich völlig frei bewegen. Wie sähen wohl die Regeln für so ein Schachspiel aus?). Ein Raster schränkt einerseits das Level-Design durch die etwas zwanghafte Wiederholung ein, gibt allerdings andererseits auch durch seine »kristalline« Anordnung der Elemente eine stützende Struktur vor.

Hilfreich wirken sich Raster zur Erzeugung zufälliger Levels aus (z. B. Diablo II). Im einfachsten Fall reicht es schon pro Kachel den Inhalt aus einer vorgegebenen Sammlung auszuwürfeln. Komplexere Verfahren sollten bei der Platzierung auch die Nachbarschaften berücksichtigen (etwa eine Wüsten-Kachel nicht direkt an eine Gletscher-Kachel angrenzen lassen).

Die interne Repräsentation eines rasterbasierten Levels gestaltet sich besonders einfach: Im Prinzip ist sie nichts als eine Tabelle, in deren Zellen die Eigenschaften der Kachel eingetragen sind. Solche Tabellen lassen sich Programm-intern sehr einfach verwalten (speichern/laden).

Erweiterungen

Welche Möglichkeiten gibt es, die Kachelungen zu erweitern, um so den strukturierenden Einfluss beizubehalten und gleichzeitig mehr Abwechslung zu gewinnen?

Lockern wir die Einschränkung nur gleiche Polygone als Kacheln zu verwenden, so erhalten wir die acht archimedischen Parkettierungen.

  • Es enthält mehr als eine Sorte regulärer Polygone
  • Es trifft nie eine Ecke auf eine Seite (insbesondere sind alle Seiten gleich lang)
  • Alle Ecken sind vom gleichen Typ
Die acht archimedischen Kachelungen

Abbildung 5: Die acht archimedischen Kachelungen

Auf den ersten Blick erhalten wir so acht völlig neue Spielfeld-Typen. Genau betrachtet ist die so erzielte Abwechslung dann doch nicht so überwältigend: Alle periodischen Kachelungen lassen sich letztendlich auf eine Kachelung aus Rechtecken abbilden!

Nicht-periodische Kachelungen

Was lässt sich noch verändern, um eine abwechslungsreichere Kachelung zu erreichen? Kachelungen müssen nicht zwangsläufig periodisch sein! Nicht-periodische Kachelungen zeichnen sich dadurch aus, dass sie sich eben nicht durch Vervielfachung und Verschiebung eines Ausschnitts erzeugen lassen. Frühe Beispiele solcher Muster finden sich in orientalischen Ornamenten.

Stattdessen wird ein Teilbereich sukzessive in immer kleinere, selbstähnliche Bereiche unterteilt, ein Vorgang, der auch als »Deflation« bezeichnet wird und fraktale (d. h. selbst ähnliche), nicht-periodische Kachelungen erzeugt. Als Beispiele seien hier die Pinwheel-, Penrose- und Danzer-Parkettierung genannt.

Die Pinwheel-Kachelung wird erzeugt, indem ein rechtwinkliges Dreieck der Seitenlängen 1, 2, √5 mit fünf Kopien seiner selbst ausgefüllt wird.

Nicht-periodische Pinwheel Kachelung

Abbildung 7: Nicht-periodische Pinwheel Kachelung

Die Penrose-Kachelung setzt sich aus zwei Formen zusammen, die sich in zwei (spiegelsymmetrische) so genannte Robinson-Dreiecke unterteilen.

Der Drachen, engl. Kite, Winkel: 36°, 72°, 72° und der Pfeil, engl. Dart, Winkel: 108°, 36° 36°.

Nicht-periodische Penrose Kachelung

Abbildung 8: Nicht-periodische Penrose Kachelung

Die Winkel der Teildreiecke der Danzer-Parkettierung sind 1 π/7, 2 π/7, 3 π/7, 4 π/7 .

Nicht-periodische Danzer-Kachelung

Abbildung 9: Nicht-periodische Danzer-Kachelung

Es existieren keine platonischen Kachelungen mit Fünfecken oder Siebenecken, da deren Winkel keine Teiler von 360° sind. Am nächsten kommen diesen die Penrose-Parkettierung und die Danzer-Parkettierung.

Nicht-periodische Parkettierungen im Leveldesign einzusetzen würde Spielwelten ermöglichen, die immer noch eine sehr geordnete Struktur aufweisen, aber weit abwechslungsreicher als periodische Welten sind.

Die Datenstruktur für Zugriff und Verwaltung dieser Kachelung wäre nun kein einfaches Raster mehr. Stattdessen käme, analog zum »Deflation«-Algorithmus, ein Baum zum Einsatz.

pinwheel pattern

Abbildung 10: Ausschnitt der Pinwheel-Kachelung

pinwhee pattern

Abbildung 11: Ausschnitt der Penrose-Kachelung

pinwheel pattern

Abbildung 12: Ausschnitt der Danzer-Kachelung

Ausblick

Dem Autor sind zur Zeit leider keine Computerspiele bekannt, die nicht-periodische Raster einsetzen. Vermutlich erzwingen Zeitdruck und Gewohnheit in der Computerspiel-Entwicklung in Kombination mit nicht verfügbarer geometrischer Kenntnis solcher Strukturen auf Bewährtes zurückzugreifen: Entweder technisch leicht beherrschbare periodische Raster oder von den meisten 3d-Modellierungs-Programmen und 3d-Engines unterstützte »freie« Geometrien. Engines und Entwicklungs-Tools für nicht-periodische Parkettierungen würden es Spiele-Entwicklern sicherlich enorm erleichtern, dieses Gebiet stärker zu erkunden.

An der Grenze zwischen vollkommen geregelten und völlig freien Spielwelten angesiedelt wären nicht-periodische Kachelungen/Parkettierungen zur Erzeugung prozeduraler Level eine Bereicherung. Auch wirken die so entstehenden Strukturen schon für sich sehr ästhetisch und könnten so manchen Spiele-Designer zu neuen Ideen inspirieren.

Literatur

[1] Grünbaum, Branko, Sheppard: Tilings and Patterns, New York W.H. Freeman, 1986
[2] Olaf Delgado-Friedrichs: Gep asterte Materie, Spektrum der Wissenschaft 22.07.2008
[3] Stefan Maier: Moderne Mathematik in islamischen Ornamenten, Spektrum der Wissenschaft 24.08.2007
[4] Quasikristalline islamische Muster, Spektrum der Wissenschaft 20.04.2007
[5] Michael Baake, Uwe Grimm, Robert V. Moody: Die verborgene Ordnung der Quasikristalle, Spektrum der Wissenschaft 01.02.2002
[6] Doris Schattschneider : Eschers Metaphern, Spektrum der Wissenschaft 01.01.1995
[7] P. Bourke: Non-Periodic Tiling of the Plane, http://local.wasp. uwa.edu.au/~pbourke/texture_colour/nonperiodic
[8] Wikipedia: Aperiodic Tiling, http://http://en.wikipedia.org/ wiki/Aperiodic_tiling
[9] Eric Weisstein: Mathworld, Tesselation, http://mathworld. wolfram.com/Tessellation.html
[10] Wikipedia: Regular Tiling, http://en.wikipedia.org/wiki/Tiling_ by_regular_polygons
[11] Eric Weisstein: Mathworld, Penrose Tiles, http://mathworld. wolfram.com/PenroseTiles.html
[12] Wikipedia: Penrose Tiles, http://en.wikipedia.org/wiki/Penrose_ tiles
[13] Eric Weisstein: Mathworld, Topology, http://mathworld.wolfram. com/Topology.html
[14] Eric Weisstein: Mathworld, Platonic Solid, http://mathworld. wolfram.com/PlatonicSolid.html
[15] Wikipedia: Aperiodic Tiling, http://en.wikipedia.org/wiki/ Platonic_solid
[16] Wikipedia: Non-Euclidean Geometry, http://en.wikipedia.org/ wiki/Non-Euclidean_geometry
[17] Eric Weisstein: Mathworld, Hyperbolic Tiling, http://mathworld. wolfram.com/HyperbolicTiling.html
[18] Wikipedia: Hyperbolic Tiling, http://en.wikipedia.org/wiki/ Hyperbolic_tiling
[19] Eric Weisstein: Mathworld, Space-lling Polyhedron, http://mathworld.wolfram.com/Space-FillingPolyhedron.html
[20] Wikipedia: Space-lling Polyhedra/Honeycomb, http://en. wikipedia.org/wiki/Honeycomb_(geometry)
[21] Sid Meier: Civilization 5, http://www.civilization.com/
[22] Maxis: SimCity2000
[23] Blizzard: Diablo II, http://us.blizzard.com/en-us/games/d2/
[24] Blizzard: Star Craft, http://us.blizzard.com/en-us/games/sc/
[25] Westwood: Command and Conquer, http://www. commandandconquer.com/classic/