Aufgabe 1

In dieser Aufgabe geht es darum, das Spielfeld zufällig in zusammenhänge Regionen der Grösse 4 bis 8 aufzuteilen.

Das soll die Methode randomRegions in der Datei model.js erledigen.

git fetch --all --tags
git checkout tags/a1
git switch -c dev

• Ein Graph besteht aus Knoten und Kanten, die jeweils zwei Knoten miteinander verbinden.
• Zwei verbundene Knoten werden Nachbarn genannt.
• Ein Pfad ist eine Folge Knoten, so dass zwei aufeinanderfolgende Knoten Nachbarn sind (d.h. durch einen Kante verbunden)
• Ein Graph ist zusammenhängend, wenn es zwischen jedem Paar von Knoten einen Pfad gibt.
• Ein Kreis ist geschlossener Pfad, der ausser dem ersten und letzten Knoten keinen Knoten zwei mal enthält.
• Ein Baum ist ein zusammenhängender Graph der keine Kreise enthält.
• In jedem zusammenhängenden Graphen können Kanten enfernt werden, bis ein Baum übrigbleibt. Dabei bleiben bei $n$ Knoten immer genau $n-1$.

Im Cell-Tower Spiel betrachten wir den Graphen $G$, dessen Knoten den Buchstabenfeldern entsprechen, die durch eine Kante verbunden sind, wenn die Felder direkt benachbart sind. Ein Knoten hat also meistens vier Nachbarn.

• Man generiert einen zufälligen Baum $B$ auf dem Spielfeldgraphen $G$.
• Sei $S$ eine Sammlung von Bäumen, initialisiert mit $S=\{B\}$.
• Solange $S$ Bäume enthält, die mehr Knoten haben als die maximale Wortlänge, sei $X$ so ein Baum:
  • Entferne eine zufällige Kante von $X$ so, dass die beiden entstehenden Teilbäume $X_1$ und $X_2$ mindestens so viele Knoten haben wie die minimale Wortlänge.
  • Ersetze $X$ in $S$ durch $X_1$ und $X_2$.
• Die Bäume in $S$ entsprechen einer Zerlegung in zusammenhängende Regionen.

• Start mit einem Graphen mit $n$ Knoten ohne Kanten.
• Jeder Knoten erhält ein Label $l_i$, initialisiert mit $l_i=i$ für eine Nummerierung von 0 bis $n-1$ der Knoten.
• Wiederhole $n-1$ mal:
  • Finde eine zufällige Kante $e = (v_i, v_j)$, die Knoten mit unterschiedlichen Labels verbindet, d.h. $v_i \neq v_j$.
  • Füge $e$ hinzu.
  • Für alle Knoten $u$ mit $l_u=l_j$:
    • $l_u = l_i$

Während der Ausführung haben alle durch Pfade verbundenen Knoten die gleichen Labels. Verbunden werden so nur Teile, die noch nicht verbunden waren. Das garantiert, dass keine Kreise entstehen. Am Schluss entsteht so ein Baum.

• Funktion zählen($a$, $u$):
• Input: aktueller Knoten $a$, Vorgänger-Knoten $u$ (kann auch leer sein).
• anzahl = 1
• For alle Nachbarn $v$ von $a$ mit $v \neq u$:
  • anzahl += zählen($v$, $a)
• Resultat ist anzahl

Aufgerufen wird die Funktion mit zählen($v$, null), wobei $v$ irgendein Knoten vom Baum ist.

Diese Funktion ist korrekt, weil ein Baum keine Kreise enthält. Ansonsten müsste man die Knoten markieren um zu verhindern, dass zwei mal der gleiche Knoten besucht wird.

Ein Graph kann auf verschiedene Arten gespeichert werden, die je nach nötigen Manipulationen und abfragen effizient sind oder nicht.

Die Knoten werden meist einfach mit den Zahlen $0$ bis $n-1$ dargestellt. Daten, die den Knoten zugeordnet sind, werden in Arrays gespeichert, die über diesen Index angesprochen werden.

Für die Kanten gibt es mehrere Möglichkeiten:

• Ein $n \times n$ Array, das true/false enthält, je nachdem ob die Kante [u][v] existiert oder nicht.
• Für jeden Knoten ein Array mit den Nachbarn (Liste von Knoten)
• Eine Liste mit allen Kanten (als Paare von Knoten)

Das Problem mit nicht-aufteilbaren Bäumen kann umgangen werden, wenn mit einem hamiltonischen Pfad (einer der alle Knoten genau einmal besucht) gestartet wird. Ein (genügend) zufälliger solcher Pfad kann z.B. mit folgendem Algorithmus generiert werden: https://stackoverflow.com/questions/7371227/algorithm-to-find-a-random-hamiltonian-path-in-a-grid

Wie gleichverteilt zufällig aus allen möglichen Aufteilungen in Regionen eine generiert werden kann, erschliesst sich mir noch nicht.