\section{Simulieren} \subsection{Die Entstehung von Galaxien} ``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}} 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. 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. 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 Massenmittelpunkt 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 Massenmittelpunkt der Galaxie definiert, man rotiert also die Galaxie und gleicht durch die Zentripetalkraft, die Kraft die Alle Sterne Richtung Massenmittelpunkt 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. \subsection{Berechnung der Beschleunigungen} Um die Beschleunigung die auf einen Stern wirkt zu berechnen wird folgendes berechnet: \begin{equation} \label{eq:beschleunigung} a = G \cdot \frac{\Delta{M_2}}{\Delta{r}^2} \end{equation} \( G \) steht hier für die Universelle Gravitationskraft, \( \Delta M \) für die Masse des Objektes das Umkreist wird und \( \Delta r \) für die Entfernung zum Mittelpunkt des Objektes das umkreist wird. Problem ist, dass kein Objekt umkreist wird sondern eine große Anzahl an Sternen. Es ist also nicht möglich mithilfe von herkömmlichen Methoden die Beschleunigung die auf einen Stern wirkt zu berechnen. TODO: und jetzt? \subsubsection{Die Kraft als Vektor} Um die Kraft als Vektor darzustellen, muss die Formel \ref{eq:beschleunigung} mithilfe von Vektoren wiefolgt neu aufgestellt werden: \begin{equation} \vec{F}_{12} = \underbrace{-G \frac{m_1 m_2}{|r_{12}|^2}}_{Scalar} \cdot \underbrace{\frac{r_2 - r_1}{|r_2 - r_1|}}_{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_{i=0}^{n-1} F_{ai} \end{equation} \subsubsection{Berechnung der Umlaufgeschwindigkeit} Die Umlaufgeschwindigkeit kann berechnet werden, indem die Kraft die die Sterne in die Mitte der Galaxie zieht \( \left( F = G \cdot \frac{m \cdot M}{r^2} \right) \) mit der Zentripetalkraft \( \left( F_z = \frac{m \cdot v^2}{r} \right)\) gleichgesetzt wird: \begin{equation} v = \sqrt{\frac{G \cdot M_E}{r}} \end{equation} \( M_E \) steht dabei für die Masse der Erde, \( G \) für die Gravitationskonstante und \( r \) für den Bahn Radius. Da wir jedoch nicht in der Erdumlaufbahn, sondern in einer Galaxien Umlaufbahn hantieren, können wir nicht die Masse der Erde nutzen. Wir müssen daher eine andere Möglichkeit nutzen, die Größe der Masse, die den Stern in Richtung Massenmittelpunkt zieht zu berechnen. \subsubsection{Ellipsen und die Geschwindigkeit der Sterne} Da die Sterne nicht auf perfekten Kreisbahnen um den Mittelpunkt der Galaxie fliegen muss in betracht gezogen werden wie die Sterne auf Elliptischen Bahnen orbitieren. Wichtigt ist dabei die Geschwindigkeit, diese muss zwischen der ersten Kosmischen Geschwindigkeit \( v_k \) und der zweiten Kosmischen Geschwindigkeit \( v_P \) liegen. Die beiden Kosmischen Geschwindigkeiten sind folgendermaßen definiert: \begin{equation} v_{k1} = \sqrt{\frac{GM}{r}} \end{equation} \begin{equation} v_{k2} = \sqrt{\frac{2GM}{r}} \end{equation} Die Tatsache das die Sterne auf Elliptischen Bahnen unterwegs sind ist für die Berechnung irrelevant, da eh für jeden Zeitschritt \( t \) eine neue Kraft berechnet wird aus der eine Beschleunigung berechnet wird die wiederum die neue Position des Sternes ergibt. Hält man die Geschwindigkeit der Sterne somit im interval \( (v_{k1} ; v_{k2}) \), dann ergibt sich (in der Therorie) von alleine eine elliptische Bahn. \subsection{Entwicklung der nötigen Software} 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 Endbedingungen eintrifft. \subsubsection{Zu lösende Probleme} Ein Problem das auftritt wenn die Kräfte zwischen allen Sternen berechnet werden ist, dass der Rechenaufwand \( O(n \cdot n-1) \approx O(n^2) \) beträgt. Es kommt zu Problemen, wen nder mittlere Fehler, der bei der Berchnung 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 nichtmehr sinvoll dargestellt wird. Statt nun mit Rundungsfehlen zu rechnen, können diese Sterne, die sehr weit enfrent vom Stern dessen kräfte berechnet werden sollen, einfach nicht mehr beachtet werden, da sie nicht sinvoll beitragen. Um dieses Problem zu lösen wird der Barnes-Hut Algorithmus verwenden. Dieser Algorithmus unterteil einen Bereich in variabel große Zellen und mindert die Laufzeit von \( O(n^2) \) auf \( O(n \log(n) \). \subsubsection{Generierung von Quadtrees und die nutzung des Barnes-Hut Algorithmus\footnote{http://arborjs.org/docs/barnes-hut}} \begin{equation} NW = \left( m \pm \frac{b}{2}, m \pm \frac{b}{2} \right) \end{equation} \bigskip \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} \begin{forest} for tree={circle,draw, s sep+=0.25em} [ [A] [ [ [] [B] [C] [] ] [] [] [D] ] [ [] [E] [F] [G] ] [H] ] \end{forest} Um die Kraft die auf einen bestimmten Stern wirkt zu berechnen, wird der Baum von der Wurzel aus nach unten durchlaufen. Beispiel: Berechnung der Kraft die auf den Stern A wirkt. Der 'Quadtree' wird von oben nach unten durchgegangen, also wird das Verhältnis zwischen der Entfernung des Massemittelpunktes zu dem Stern A (\(\approx 42\)) und der Breite der jeweiligen Zelle (100) berechnet (Formel \ref{eq:barnes_hut}): \( \frac{100}{43} \not> \theta = 0.5\). \begin{equation} \label{eq:barnes_hut} \theta = \frac{d}{r} \end{equation} Ist das Verhältnis größer als ein im vorhinein definierter Grenzwert \( \theta \), dann wird weiter in den Quadtree ineingegangen und eine Ebene tiefer rekursiv weitergeprüft. Die Koordinate des Massemittelpunktes \( \varsigma \) des jeweiligen Knotens kann wie in Formel (\ref{eq:mean_mass}) beschrieben berechnet werden: \begin{equation} \label{eq:mean_mass} \varsigma = \left( \dfrac{ \displaystyle \sum_{i=0}^{n} x_i \cdot m_i }{ \displaystyle \sum_{i=0}^{n} m_i } , \frac{ \displaystyle \sum_{i=0}^{n} y_i \cdot m_i }{ \displaystyle \sum_{i=0}^{n} m_i } \right) \end{equation} Es ist somit durch \( \theta \) eine Endbedingung 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 ursprungssten liegen und dicht genug grupiert sind zusammengefasst werden. \subsubsection{Implementierung des Quadtrees} Um generell irgendwas zu tun muss in fast allen fällen etwas definiert werden. Zur Simulation von Galaxien brauchen wir vor allem eine Methode, Sterne einheitlich zu definieren. Der unten definierte Vec2-typ kann einen Vektor oder eine Koordinate darstellen was ihn in der Anwendung zu einem praktischen Hilfsmittel macht. Er speichert die X und Y Komponente der jeweiligen Struktur die er darstellen soll als float64-typ. \begin{lstlisting} type Vec struct { X float64 Y float64 Z float64 } method (Vec2) insert() {...} method (Vec2) insideOf() bool {...} func newVec2() Vec2 {...} \end{lstlisting} Mithilfe des Vec2-typens kann ein Kompletter Stern definiert werden. Dabei wird ein Stern mithilfe seine Position \( C \), seiner Geschwindigkeit \( V \), und seiner Masse \( M \) beschrieben. \begin{lstlisting} type Star struct { C Vec V Vec Mass float64 } method (Vec2) insideOf() bool {...} \end{lstlisting} Um einen sogennanten quadtree bzw. octree aufzubauen wird erstmal eine Räumliche Begrenzung benötigt, die einem Raum beschriebt indem die Sterne enthalten sind oder nicht. Diese grenze ist als `Boundary` definiert, es wird dabei der Mittelpunkt der Begrenzung und die kürzeste Entfernung zwischen mittelpunkt und äußerer Begrenzung genutzt um den Raum zu definieren. \begin{lstlisting} type Boundary struct { Center Vec HalfDimension float64 } function newBoundary() {...} \end{lstlisting} Der eigentliche QuadTree bzw. Octree beinhaltet einige Informationen: Die Anzahl in ihm enthaltene Sterne, die Räumliche ausbreitung, die eigentlichen Sterne als Star2D definiert und die RecursionTiefe als integer. Die Definition des QuadTrees der Unten zu sehen ist enthält Zeiger zu den Kindern des Quadtrees und ist somit rekusriv definiert was es einfach macht neue Kinder zu erstellen, da diese eine Kopie ihere Eltern mit einer anderen Begrenzung darstellen wodurch die in ihnen enthaltenen Sterne weniger werden. \begin{lstlisting} type QuadTree struct { StarCount int Boundary Boundary Star []Vec2 NorthWest *QuadTree NorthEast *QuadTree SouthWest *QuadTree SouthEast *QuadTree ReccursionDepth int } method (QuadTree) insert(Star) bool {...} method (QuadTree) subdivide() {...} \end{lstlisting} \subsubsection{Benchmarking} Um den Geschwindigkeitsvorteil darzustellen, kann die Kraft zwischen \(n\) homogen verteilten Sternen berechnet werden. Einmal mit der Brute-Force Methode und einmal mit der im Barnes-Hut Algorithmus beschriebenen Methode. %\begin{figure*}[ht!] %\centering %\begin{tabular*} {l | l | l | l || l} % left bound & right bound & step & amount of stars & time \\ % -5e5 & 5e5 & 5e3 & 40003 & 1m25 \\ %\end{tabular*} %\end{figure*} \subsubsection{Runge-Kutta methods} Die Runge-Kutta Methode wird genutzt, um die Position eines objektes nach einer Beliebigen Zeit zu approximieren. Dabei kann, bei nutzung eines mglich kleinen Zeitschrittes, ein sehr genaues Ergebniss erzielt werden. In unserem Fall haben wir einen Stern auf den eine Kraft wirkt. Wir wollen die Position des Sternens nach einem Zeitschritt berechnen, jedoch auch eine andere Kraft miteinbringen um die Sterne auf eine Ellipische Bahn um die Mitte der Galaxie zu bringen. Die Geschwindigkeit die der Stern dabei annnimmt kann mit der fogenden Formel berechnet werden: \begin{equation} v = \sqrt{ar} \end{equation} \subsubsection{Goroutines} Die Nutzung von mehreren sogennanten Go-Methoden ist unglaublich effektiv, da es die Zeit die gebraucht wird das Programm auszuführen drastisch verringert. Die implementation ist ebenfalls unglaublich einfach, es recht \subsection{Netwerkfoo} Damit das Projekt so gut wie möglich skalliert, wird die Anwendung in mehrere kleine Dienste aufgeteilt die jeweils eine funktion übernehmen und untereinander kommunizieren. Dabei läuft jede Anwendung in einem eigenen Kontainer (siehe \ref{subsubsec:Docker}) und kann somit in falle eines nadelöhrs mehrfach gestartet werden und über einen reverse-http-proxy (siehe \ref{subsubsec:Traefik}) mit daten versorgt werden. \subsubsection{Die verschiedenen Dienste} Um die Generierung der Punktwolken und die anschließende Simulation der Wolke in einzelne Microservices aufzuspalten muss erstmal definiert werden für welche Dienste es überhaupt sinn macht sie in einzelne instanzen abhängig bzw. unabhängig von einander agieren. \subsubsection{Docker} \label{subsubsec:Docker} \subsubsection{Docker-compose} \subsubsection{Traefik} \label{subsubsec:Traefik} \subsubsection{Kubernetes / Docker swarm} \subsubsection{grafana}