\section{Simulieren} \subsection{Die Entstehung von Galaxien} \par ``Eine Galaxie ist eine durch Gravitation gebundene große Ansammlung von Sternen, Planetensystemen, Gasnebeln und sonstigen Stellaren Objekten.`` \footnote{\url{https://de.wikipedia.org/wiki/Galaxie}} \par Demnach ist es relativ Einfach eine Galaxie zu generieren: es werden einfach ganz viele Objekte in einen Raum geworfen. Das reicht jedoch nicht um die Objekte als Galaxie definieren zu können, da sie nicht ``durch Gravitation gebunden`` sind. \par Um dies zu tun muss die Kraft zwischen allen Objekten in der Galaxie berechnet werden um damit die Position der jeweiligen Objekte nach einer bestimmten Zeit bestimmen zu können. \par Tut man dies indem man zwischen allen Objekten die Kräfte berechnet kommt es zu Problemen: die Anzahl der Kraft Berechnungen die durchgeführt werden müssen steigen exponentiell: Die Anzahl der Kräfte die auf \(n\) Sterne wirken lassen sich mit der Formel \( n \cdot (n-1) \) berechnen. Für \( n=3 \) müssen demnach \( 6 \) Kräfte berechnet werden, für \( 100 \) Sterne dagegen \( 9900 \) und für \( 1.000.000 \) Sterne \( \approx 9.99999 \cdot 10^{11} \). Die Anzahl der Kraft Berechnungen die durchgeführt werden müssen beim simulieren einer ''echten'' Galaxie mit \( >200 \cdot 10^6 \) Sternen ist demnach so groß, dass die Anzahl der Kräfte die berechnet werden müssen minimiert werden müssen um in einer sinnvollen Zeit an ein Ergebnis zu kommen. \par Dies reicht jedoch auch nicht um eine ``stabile`` Galaxie zu generieren: berechnet man nur die Kräfte die auf ruhende Objekte in einem Reibungsfreiem Raum wirken, würden alle Objekte zum Massen Mittelpunkt gezogen werden und die Galaxie würde somit implodieren. Es ist also nötig auf die Sterne in der Galaxie Anfangs Kräfte zu wirken. Diese Kräfte sind durch die Rotation der Galaxie um den Massen Mittelpunkt der Galaxie definiert, man rotiert also die Galaxie und gleicht durch die Zentripetalkraft die Kraft die Alle Sterne Richtung Massen Mittelpunkt zieht aus. Rotiert man die Galaxie jedoch zu schnell, explodiert sie förmlich, da die Sterne nicht mehr zusammengehalten werden und die Fliehkraft sie einfach auseinanderzieht. \subsubsection{Die Kraft als Vektor} Um die Kraft als Vektor zu berechnen, welcher ein Stern B auf einen Stern A ausübt, wird die folgende Formel verwendet: \begin{equation} \vec{F}_{AB} = \underbrace{-G \frac{m_A m_B}{|r_{AB}|^2}}_{Scalar} \cdot \underbrace{\frac{r_B - r_A}{|r_B - r_A|}}_{Vector} \end{equation} Die Summe der Kräfte die auf einen Stern wirken ist somit die Summe aller Kräfte die zwischen dem jeweiligen Stern \( a \) und allen anderen Sternen wirken: \begin{equation} F_{a} = \sum_{\substack{i=0 \\ i\neq a}}^{n-1} F_{ai} \end{equation} \subsection{Konzepte} %Die Software ist komplett in Golang geschrieben was die Nutzung von mehreren %Threads mithilfe von Go-Methoden stark vereinfacht. Um den Barnes-Hut %Algorithmus anzuwenden muss die Galaxie in einen Octree unterteilt werden. %Dabei wird eine Zelle definiert die alle Sterne beinhaltet welche anschließen %solange unterteilt, bis eine der drei end- Bedingungen eintrifft. \subsubsection{Zu lösende Probleme} Wie bereits beschrieben ist eines der Probleme das Auftritt die Anzahl der nötigen Kraft Berechnungen wodurch der Rechenaufwand Quadratisch in Relation zu der Anzahl der Sterne steigt und somit in \( O(n \cdot (n - 1)) \in O(n^2) \) liegt. \par Es kommt zu Problemen, wenn der mittlere Fehler, der bei der Berechnung der Kraft entsteht größer als die wirkende Kraft wird. Dies passiert unter anderem dann, wenn der Abstand zwischen den Sternen so groß wird, das die wirkende Kraft so gering ist das sie mithilfe von Computern nicht mehr sinnvoll dargestellt werden kann. Statt nun mit Rundungsfehlern zu rechnen, können diese Sterne, die sehr weit entfernt vom Stern dessen Kräfte berechnet werden sollen, einfach nicht mehr beachtet werden, da sie nicht sinnvoll beitragen. Um diese Sterne jedoch nicht komplett aus der Berechnung auszunehmen, können kleine Cluster an Sternen welche weit genug vom Stern auf den die Kräfte berechnet werden sollen weg sind und klein genug sind zu einem Pseudo- Stern zusammengefasst werden welcher durch den Masse Mittelpunkt der Sterne die er repräsentiert definiert ist. Das Konzept wurde 1986 von Josch Barnes und Piet Hut veröffentlicht und erlaubt es die Anzahl an Kräften die berechnet werden müssen von \( O(n^2) \) auf \( O(n log(n)) \) zu reduzieren. \subsubsection{Generierung von Quadtrees und entsprechende Bäume} Um Sterne clustern zu können muss die Galaxie in der sich die Sterne befinden in Zellen unterteilt werden. Dazu wird ein Quadtree bzw. Octree (ein k-närer Baum mit 4 bzw. 8 Kindern) aufgebaut indem die Sterne eingefügt werden. Damit die Stern-cluster gebildet werden können müssen die Sterne sich in den Blättern des Baumes befinden. Die Knoten des Baumes indem sich die Sterne befinden dürfen somit keine weiteren Kinder besitzen. \par Ein Galaxie wie in Abbildung \ref{fig:cells} dargestellt wird demnach Stern für Stern in einen anfangs leeren Baum eingefügt. Die Größe der ersten Zelle die nach dem einfügen aller Sterne alle Sterne beinhaltet kann falls bekannt ist in was für einem Intervall die Koordinaten der Sterne sich befinden direkt genutzt werden um die Größe der Zelle zu definieren, andernfalls muss diese erst ermittelt werden indem die minimal und maximal Koordinaten in der liste an Sternen gesucht werden. Beim einfügen kann es jedoch wie in Abbildung \ref{fig:insertwithexisting} zu sehen zu Problemen kommen. Im falle das der Knoten indem ein Stern eingefügt werden soll bereits durch einen anderen Stern belegt ist müssen für den jeweiligen Knoten Kinder-Knoten erzeugt werden in den die beiden Sterne eingefügt werden müssen. Dies wird so lange fortgeführt bis sich alle Knoten in den Blättern des Baums befinden. \par Eine Zelle ist durch ihren Mittelpunkt und ihrer Breite definiert, daher verschiebt sich eine Zelle welche sich eine Ebene ''tiefer'' befinden um ein viertel ihre Breite und die Breite der neuen Zelle ist im Relation zu der Ursprünglichen Zelle gesehen halbiert. \par Nachdem alle Sterne in einen Baum eingefügt wurden und sich in den Blättern des Baumes befinden, wird der Baum rekursiv durchlaufen und es wird für jeden inneren Knoten (Knoten welche keine Blätter sind) die gesamt Masse ihrer Kinder berechnet und der Massen Mittelpunkt. \subsubsection{Funktion des Barnes-Hut Algorithmus} Um nun zu definierten welche Cluster zusammengefasst werden und welche nicht wird der Barnes-Hut Algorithmus (\ref{eq:barnes_hut}) verwendet. Dieser berechnet einen Wert \( \theta \) welcher als Referenz dafür genommen werden kann, wie die Relation zwischen der Entfernung zu einem Cluster und der Größe des Clusters ist. Um nun Cluster welche weit genug von einem Stern weg sind und gleichzeitig klein genug sind zu erkennen und herauszufiltern kann der Algorithmus in Kombination mit einem vordefinierten Grenzwert genutzt werden. \begin{figure}[!h] \centering \subfloat[Ein Cluster auf mehreren Sternen]{ \centering \begin{tikzpicture} \tikzstyle{circlestyle}=[shape=circle,thick,fill,draw, inner sep=0cm] \node at (0, 0) {}; \node at (9, 0) {}; % Random seed for RNG \pgfmathsetseed{7}; \foreach \x in {1,...,40} { % Find random numbers \pgfmathrandominteger{\a}{10}{390} \pgfmathrandominteger{\b}{10}{390} % Scale numbers nicely \pgfmathparse{0.005*\a}\let\a\pgfmathresult; \pgfmathparse{0.005*\b}\let\b\pgfmathresult; % draw the circle \fill (\a, \b) circle (0.03); }; % draw a box around the star cluster \draw[] (0,0) rectangle (2, 2); \node[] at (1, 1) (A1) {}; \draw[arrows=<->] (0,-0.2) -- node[midway, align=center, below] {\(d\)} (2,-0.2); % draw a star in the far right of the image \node[circlestyle, minimum size=2pt, label=above:\(s_1\)] at (8, 1) (A2) {}; % draw a line in between the box and the far right of the image \draw[dashed, arrows=<->] (A1) -- node[midway, align=center, above] {\(r\)} (A2); \end{tikzpicture} \label{subfig:ungrouped} } \hfill \subfloat[Die abstraction des obigen Clusters]{ \centering \begin{tikzpicture} \tikzstyle{circlestyle}=[shape=circle,thick,fill,draw, inner sep=0cm] \node at (0, 0) {}; \node at (9, 0) {}; % draw a big star in the far left of the image \node[circlestyle, minimum size=2pt, label=above:\(q_1\)] at (1, 0) (B1) {}; % draw the right star \node[circlestyle, minimum size=2pt, label=above:\(s_1\)] at (8, 0) (B2) {}; % draw a line in between the far left star and the right star \draw[dashed, arrows=<->] (B1) -- node[midway, align=center, above] {\(r\)} (B2); \end{tikzpicture} \label{subfig:grouped} } \caption{Visuelle Darstellung der Funktionsweise des Barnes-Hut Algorithmuses. Das Stern Cluster aus \ref{subfig:ungrouped} wird in \ref{subfig:grouped} zu einem Stern abstrahiert.} \end{figure} \begin{equation} \label{eq:barnes_hut} \theta = \frac{d}{r} \end{equation} Ist das Verhältnis zwischen Entfernung \( r \) und Breite \( b \) des Clusters kleiner als der vorher definierte Grenzwert, kann das Cluster zu einem Pseudostern zusammengefasst werden. \subsection{Kraft-Berechnungen} \subsubsection{Berechnung der auf einen Stern wirkenden Kraft} \par Um die Kraft, welche auf einen bestimmten Stern wirkt, zu berechnen, wird der Baum von der Wurzel aus rekursiv durchlaufen. Es wird für jeden Knoten das jeweilige \( \theta \) berechnet und mit dem vorher definierten Grenzwert verglichen. Ist das berechnete \( \theta \) kleiner als der vorher definierte Grenzwert wird die Rekursion nicht weiter in den Baum gehen sondern den jeweiligen Teilbaum zusammenfassen. \par Es ist somit durch den Grenzwert somit eine end-Bedingung gegeben, welche verhindert das zu weit in den Baum vorgedrungen wird und somit auch verhindert, dass Sterne die in einer zu großen Entfernung zu dem Ursprungs Stern liegen und dicht genug gruppiert sind in die Berechnung miteinbezogen werden. \par Möchte man die Kraft auf den Stern \( F \) in Abbildung \ref{fig:cells} berechnen berechnet man das \( \theta \) zwischen \( F \) und dem Wurzel-Knoten. Ist das berechnete \( \theta \) größer als der vorher definierte Grenzwert kann statt weiter in den Baum hineinzugehen und weitere Kräfte zu berechnen die Kraft zwischen \( F \) und dem Pseudostern der durch den Wurzel-knoten dargestellt wird direkt berechnet werden. Andernfalls wird weiter in den Baum hineingegangen und auf der nächsten Baum-Ebene das Entsprechende \( \theta \) zwischen den Sternen berechnet werden. \par Betrachtet man Abbildung \ref{fig:cells} fällt auf das die Zelle in der sich die Sterne \( C \) und \( D \) befinden sehr klein ist und die Entfernung zu dem Stern \( F \) vergleichsweise hoch ist. Es kann also angenommen werden, dass das Theta zwischen \( F \) und der Zelle in der sich \( C \) und \( B \) befinden sehr klein ist. Die Sterne können demnach zusammengefasst werden. \bigskip \begin{figure} \hspace{1.5cm} \begin{minipage}{0.45\textwidth} \begin{tikzpicture}[level 1/.style={level distance=1.5cm}] % First Layer \draw [line width=0.5mm] (0, 0) rectangle (6, 6); % Second Layer \draw [line width=0.25mm] (0, 0) rectangle (3, 3); \draw [line width=0.25mm] (3, 0) rectangle (6, 3); \draw [line width=0.25mm] (0, 3) rectangle (3, 6); \draw [line width=0.25mm] (3, 3) rectangle (6, 6); % Third Layer (South West) \draw [line width=0.125mm] (0, 0) rectangle (1.5, 1.5); \draw [line width=0.125mm] (1.5, 1.5) rectangle (3, 3); % Third Layer (North East) \draw [line width=0.125mm] (3, 3) rectangle (4.5, 4.5); \draw [line width=0.125mm] (4.5, 4.5) rectangle (6, 6); % Forth Layer (North West) \draw [line width=0.125mm] (3, 4.5) rectangle (3.75, 5.25); \draw [line width=0.125mm] (3.75, 5.25) rectangle (4.5, 6); % Draw the nodes \node at (1, 4.5) {$A$}; \node at (4, 5.5) {$B$}; \node at (3.5, 5) {$C$}; \node at (5, 4) {$D$}; \node at (2.75, 2.75) {$E$}; \node at (0.75, 0.75) {$F$}; \node at (2, 0.75) {$G$}; \node at (3.5, 0.75) {$H$}; \end{tikzpicture} \end{minipage} \caption{Unterteilung einer Galaxie in verschiedene Zellen} \label{fig:cells} \end{figure} \begin{figure} \centering \begin{forest} for tree={circle,draw, s sep+=0.25em} [ [A] [ [ [] [B] [C] [] ] [] [] [D] ] [ [] [E] [F] [G] ] [H] ] \end{forest} \caption{Die in Abbildung \ref{fig:cells} dargestellte Galaxie als Baum dargestellt} \end{figure} \begin{figure} \subfloat[Anfangszustand. Der Stern B soll in den Baum, indem sich bereits A befindet, eingefügt werden.]{ \begin{forest} for tree={circle,draw, s sep+=0.25em} [,phantom [B] [ A ] ] \end{forest} } \; \subfloat[Stern B kann nicht eingefügt werden, da der Slot durch A belegt ist, also wird A weiter in den Baum versickert.]{ \begin{forest} for tree={circle,draw, s sep+=0.25em} [,phantom [B] [ [A] [] [] [] ] ] \end{forest} } \; \subfloat[B wird nun eingefügt, da sich B jedoch nicht in einem Blatt befinden, muss B weiter versickert werden.]{ \begin{forest} for tree={circle,draw, s sep+=0.25em} [,phantom [B [A] [] [] [] ] ] \end{forest}\quad\\[2ex] } \; \subfloat[Damit B versickert werden kann, wird der Platz der durch A besetzt wird freigemacht, indem A weiter versickert wird.]{ \begin{forest} for tree={circle,draw, s sep+=0.25em} [B [ [A] [] [] [] ] [] [] [] ] \end{forest}\quad } \; \subfloat[B kann jetzt in den Baum versickert werden und ist nun ein Blatt.]{ \begin{forest} for tree={circle,draw, s sep+=0.25em} [ [ [A] [] [B] [] ] [] [] [] ] \end{forest}\quad } \caption{Schrittweises einfügen des Sternes B in einen Baum, indem sich bereits ein Stern (A) befindet.} \label{fig:insertwithexisting} \end{figure} \subsection{Datenbanken} \subsubsection{Speichern der Sterne} Die Sterne werden in einer Tabelle in Datenbank \mbox{PostgreSQL} gespeichert. Die Tabelle ist folgendermaßen aufgebaut: \begin{figure}[h!] \centering \begin{tabular} {l | l | l | l | l | l} star\_id & \(x\) & \(y\) & \(vx\) & \(vy\) & \(m\) \\ \hline\hline 1 & -300 & 300 & 0 & 0 & 1000 \\ \hline 2 & -200 & -200 & 0 & 0 & 1000 \\ \hline \dots & \dots & \dots & \dots & \dots & \dots \\ \hline n & \(x_n\) & \(y_n\) & \(vx_n\)& \(vy_n\) & \(m_n\) \\ \hline \end{tabular} \caption{Darstellung der Tabelle in der die Sterne gespeichert werden. Die star\_id spalte beinhaltet eine global einmalige ID wodurch jeder Stern identifiziert werden kann.} \end{figure} Dadurch das jeder Stern eine einmalige ID besitzt kann diese verwendet werden um einfach auf Sterne zu verweisen. Dies ist im Kontext des Einfügens sehr hilfreich da die Verschiebung eines Sternes durch ändern der Stern-ID vollzogen werden kann. \subsubsection{Speichern von Bäumen} Um die Bäume in einer Datenbank zu speichern muss eine einheitliche Struktur definiert werden um Probleme in der Zukunft zu verhindern. Die Nutzung von speziellen Graphen Datenbanken bietet sich natürlich an, jedoch wird diese starke Spezialisierung schnell zu einem Hindernis. Um nach dem KISS Prinzip\footnote{"Das KISS-Prinzip (englisch Keep it simple, stupid) fordert, zu einem Problem eine möglichst einfache Lösung anzustreben." \url{https://de.wikipedia.org/wiki/KISS-Prinzip}} eine möglichst einfache Lösung zu nutzen werden die Bäume in einer Relationalen Datenbank gespeichert. Jeder Knoten wird dabei in einer Zeile der Datenbank gespeichert und erhält eine global einzigartige ID. Die Kinder in andrem Knoten hängen werden anhand ihrer ID in der Zeile gespeichert sodass es einfach möglich ist einfach auf diese zuzugreifen und beim rekursiven durchsuchen des Baumes auf diese zuzugreifen. \begin{figure*}[ht] \begin{tabular} {l | l | l | l | l | l | l | l | l | l} node\_id & box\_width & total\_mass & depth & star\_id & root\_id & isleaf & box\_center & center\_of\_mass & subnodes \\ bigint & numeric & numeric & numeric & bigint & bigint & boolean & numeric[] & numeric[] & numeric[] \\ \hline\hline 2921847 & 1000 & 2000 & 0 & 0 & 1 & False & \{0, 0\} & \{0, 0\} & \{ \(\dots\) \} \\ \hline 2921848 & 500 & 1000 & 1 & 1 & 1 & True & \{-500, 500\} & \{-300, 300\} & \{ \(\dots\) \} \\ \hline 2921849 & 500 & 0 & 1 & 0 & 1 & True & \{500, 500\} & \{0, 0\} & \{ \(\dots\) \} \\ \hline 2921850 & 500 & 1000 & 1 & 2 & 1 & True & \{-500, -500\} & \{-200, -200\} & \{ \(\dots\) \} \\ \hline 2921851 & 500 & 0 & 1 & 0 & 1 & True & \{500, -500\} & \{0, 0\} & \{ \(\dots\) \} \\ \hline \end{tabular} \caption{Darstellung der Tabelle in der ein Baum definiert ist } \end{figure*}