Computerspiele-Kombinatorik

Kombinatorik ist leider erfahrungsgemäß eher unbeliebt. Grade in der Spiele-Entwicklung tauchen aber immer wieder kombinatorische Fragen auf. Der folgende Artikel gibt ein Beispiel dafür, wie eine solche Fragestellung in Spielen aussehen kann und soll Spieleentwickler motivieren, sich mit dem Thema auseinanderzusetzen.

Wie im Folgenden zu lesen ist, sind bei der Entwicklung von (Computer-) Spielen (mindestens) Grundkenntnisse der Kombinatorik ziemlich nützlich. Stellen wir uns ein Computerspiel vor, in dem jeder Spieler ein Team aus drei Figuren spielt, das bei Spielbeginn zusammengestellt wird. Jede dieser drei Figuren steht in sechs unterschiedlichen Varianten 0, 1, 2, 3, 4, 5 zur Verfügung, denen zur einfacheren Visualisierung Farben zugeordnet sind: magenta, rot, gelb, grün, cyan, blau. Auch wenn die Regeln eines Spiels normalerweise weit komplexer sind, lässt sich bereits anhand dieses Grundsystems eine wichtige Frage untersuchen:

Wieviele unterschiedliche Team-Kombinationen sind hier möglich?

Von der Antwort hängt unter anderem ab, ob für jede Kombination ein eigenes 3d-Modell erstellt werden kann (zu viele Möglichkeiten werden das Budget und/oder die Deadline sprengen), ob sich die Kombinationen ohne Rest in eine bestimmten Anzahl gleich großer „Fraktionen“ einteilen lassen (zwei wie in WoW, drei wie in StarCraft oder auch mal fünf wie in Morrowind...). Geschicktes Variieren der Rahmenbedingungen erlaubt weiterhin (in vielen Spielen mit jedem neuen „Level“), die Anzahl der dem Spieler zur Verfügung stehenden Kombinationen systematisch zu erweitern.

Welche Bedingungen steuern die Anzahl der möglichen Kombinationen?

Um die Anzahl der Möglichkeiten zu berechnen bilden wir die Frage auf das klassische „Bälle-aus-Urne-ziehen“ Modell ab. Zwar ist das ein kleiner Umweg, dieser lohnt sich erfahrungsgemäß jedoch: Die Idee dabei ist, statt für jede Situation ad hoc Berechnungen anzustellen, ein Standard-Beispiel zu verwenden, um die Formeln nicht in jeder Situation neu herleiten zu müssen und um auf den ersten Blick verschiedene Systeme vergleichbar zu machen.

Stellen wir uns also einen Behälter vor, in dem sechs Bälle der obengenannten Farben liegen. Für jede der drei Figuren wird der Reihe nach ein Ball gezogen und die Farbe notiert (in einem „Pen-and-Paper“ Rollenspiel würde an dieser Stelle stattdessen gewürfelt, im Computerspiel die gewünschte Farbe angeklickt).

Die Anzahl der möglichen Team-Kombinationen hängt von zwei Faktoren ab. Ziehen wir

• mit Zurücklegen, d.h. darf eine Farbe mehrfach vorkommen (ist z.B. rot, rot, grün erlaubt)?
• geordnet, d.h. spielt die Reihenfolge eine Rolle (ist z.B. rot, blau, grün dasselbe wie grün, blau, rot)?

Die Anzahl der Bälle bezeichnen wir mit n, die Anzahl der Ziehungen mit k. In unserem Beispiel gibt es sechs Farben (also n = 6 Bälle) zur Auswahl, aus denen für jeden Typ einmal (also k = 3 mal) gezogen wird.

Mit Zurücklegen, geordnet

Bedingungen: Hier darf dieselbe Farbe mehrfach vorkommen: wir wählen („ziehen“) pro Figur eine Farbe und „legen“ sie dann „zurück“, so dass sie auch für eine weiterer Figur zur Verfügung steht. Weiter spielt die Reihenfolge eine Rolle, es bedeutet also etwas anderes, ob wir die Kombination rot, grün, blau oder blau, grün, rot wählen.

Integration in die Spielmechanik:
Dieses Szenario bietet sich an, wenn die Figuren im Team unterscheidbar sind, z.B. ein Team immer aus Ritter, Magier, Reittier besteht und die Typen so ausbalanciert sind, dass jede Kombination sinnvoll ist. Die Farben könnten hier für jede Figur etwas anderes bedeuten: für den Ritters verschiedene Kampftechniken (z.B. Schwert, Lanze, Axt...), für den Magier verschiedene Zauber (z.B. Feuer, Eis, Blitze...), für das Reitier verschiedene Typen (z.B. Adler, Drache, Löwe... das Übliche eben).

Für jede Figur stehen hier alle sechs Farben zur Verfügung, die jeweils miteinander kombiniert werden dürfen. Es ergeben sich hier 6 · 6 · 6 = 6³ = 216 Möglichkeiten (siehe Abb. 1 und Abb. 2), bzw. allgemein n^k Möglichkeiten.

Ohne Zurücklegen, geordnet

Bedingungen: Anders als im vorigen Fall darf hier keine Farbe mehr als einmal gewählt werden, z.B. wäre rot, rot, gelb verboten.

Integration in die Spielmechanik:
So eine Einschränkung kann sinnvoll sein, um die Auswahl auszubalancieren, etwa wenn die Farben mit Attributen wie Stärke, Geschicklichkeit, Reichweite o.ä. assoziiert wären, und vermieden werden soll, dass z.B. ein Team aus nur „starken“ Typen gewählt werden kann. Durch die Bedingung, keine Farbe zu wiederholen, müsste sich ein Spieler dann entscheiden, ob eher der Ritter stark und der Magier geschickt sein soll (rot, blau) oder ob eher der Ritter geschickt und der Magier stark sein soll (blau, rot).

Wieviele Möglichkeiten gibt es in diesem Fall? Für die erste Figur stehen dem Spieler sechs Farben zur Verfügung, für die zweite Figur noch fünf Farben und für die dritte nur noch vier. Es gibt hier also 6 · 5 · 4 = 120 Möglichkeiten (siehe Abb. 3, links). Allgemein ist die Anzahl der Möglichkeiten

bzw. noch etwas kompakter notiert:

Ohne Zurücklegen, ungeordnet

Bedingungen: Wie zuvor darf keine Farbe im Team mehrfach vorkommen. Anders als in den beiden vorigen Abschnitten wird aber auch die Reihenfolge nicht mehr berücksichtigt. Ob wir rot, grün, blau oder blau, grün, rot wählen ist nun gleich. Integration in die Spielmechanik: Anstatt dreier unterschiedlicher Figuren besteht ein Team nun aus drei gleichen Figuren.

Die Anzahl der Möglichkeiten schrumpft durch diese Einschränkung nochmal: Aus der im vorigen Abschnitt berechneten Anzahl muss die Anzahl möglicher Vertauschungen (Permutationen) des Ergebnisses herausgerechnet werden. Im vorigen Fall gab es 120 Möglichkeiten. In jedem Team gab es 3 · 2 · 1 = 6 Möglichkeiten, drei verschiedene Farben drei verschiedenen Figuren zuzuordnen. Da die Figuren jetzt aber ununterscheidbar sind, fallen diese Möglichkeiten raus und es bleiben 120 / 6 = 20 Möglichkeiten (siehe Abb. 3, rechts). Im allgemeinen besteht jedes Ergebnis aus k Elementen, die auf k! = k · (k-1) · (k-2) · ... · 1 Arten angeordnet werden können. Letztendlich bleiben also nur

Möglichkeiten, kompakter notiert gesprochen: „k aus n“. Diese Formel beschreibt auch die Anzahl der Möglichkeiten k Kreuze in n Kästchen zu setzen, wie beim einem Lotto-Schein (entsprechend könnte auch das User-Interface für das Spiel in diesem Fall so gestaltet werden, dass der Spieler genau drei von sechs Farben anklicken muss).

Mit Zurücklegen, ungeordnet

Bedingungen: Wie zuvor gibt es nur gleiche Figuren im Team, dafür erlauben wir aber wieder, Farben mehrfach zu verwenden. Integration in die Spielmechanik: Sind die Typen im Spiel ausbalanciert spricht nichts dagegen, Farben mehrfach zuzulassen. Wie zuvor besteht das Team aus drei gleichen Figuren.

In den vorhergehenden Fällen wurde die Anzahl der Möglichkeiten immer weiter reduziert -- jetzt erweitern wir sie wieder etwas. Um die Anzahl der Möglichkeiten zu bestimmen (nach [1]), wechseln wir vorübergehend die Notation. Da die Reihenfolge der Farben egal ist, dürfen wir sie beliebig vertauschen. Wir wählen eine Anordnung, in der die Farben nach ihrer Reihenfolge im Regenbogen sortiert sind (magenta, rot, gelb, grün, cyan, blau), als Repräsentanten für alle ihre Permutationen. So werden sowohl rot, blau, grün als auch grün, blau, rot etc. durch die sortierte Folge rot, grün, blau repräsentiert. Nun können wir jede Möglichkeit mit nur zwei Symbolen darstellen: mit einem vollen Kästchen markieren wir den Wechsel der Farbe, für jedes Vorkommen derselben Farbe schreiben wir ein leeres Kästchen.

Es gibt genau soviele leere Kästchen wie Figuren (bzw. Ziehungen), also k (hier: 3). Es gibt ein volles Kästchen weniger als Farben in unserem Spiel, also n - 1 (hier: 6 - 1 = 5). Insgesammt gibt es immer k + n - 1 Kästchen (hier: 3 + 6 - 1 = 8). Vergleichen wir das mit dem Lotto-Schein von vorhin: Es gibt k + n - 1 Kästchen, von denen n - 1 „angekreuzt“ werden.

Also Möglichkeiten.

Übrigens liefert dasselbe Ergebnis,
es wäre einfach so als würde man in einem vollständig angekreuzten Lotto-Schein die zuviel angekreuzten Felder wieder ausradieren. In unserem Spiel ergeben sich damit

Möglichkeiten (siehe Abb. 4).

Ausblick

Die unterschiedliche Anzahl möglicher Teams in Abhängigkeit der jeweiligen Beschränkungen lässt sich nutzen, um im Verlauf des Spiels neue Möglichkeiten freizuschalten. So könnte das Spiel mit drei gleichen Figuren und ohne Wiederholung von Farben beginnen („Level 1“). In der Mitte des Spiels würde entweder erlaubt, Farben mehrfach zu verwenden („Level2a“) oder die drei gleichen Figuren des Teams würden durch drei unterschiedliche ersetzt („Level2b“). Am Ende des Spiels wären schliefllich alle Kombinationen zugänglich, mehrfache Farben erlaubt und die Figuren des Teams unterscheidbar. Zwar wäre die Freischaltung neuer Möglichkeiten auch mit einem ad hoc System möglich. Ein Blick durch die „kombinatorische Brille“ erlaubt uns aber diese Aufgabe sehr elegant durch Änderung nur zweier Parameter (mit/ohne Zurücklegen, (un)geordnet) zu lösen, die sich gut in die Spielmechanik integrieren lassen (mehr-/einfache Farben, (un)unterscheidbare Figuren).

Für einen Einstieg ins Thema Kombinatorik siehe auch [2], [3].

Literatur

[1] Angelika Steger:mDiskrete Strukturen I: Kombinatorik, Graphentheorie, Algebra (Springer 2007)
[2] Wikipedia: Diskrete Mathematik, http://de.wikipedia.org/wiki/Diskrete_Mathematik
[3] Wikipedia: Abzählende Kombinatorik, http://de.wikipedia.org/wiki/Abzählende_Kombinatorik

#im fokus #game design #media design #münchen