Hügel Algorithmen

Hügel Algorithmen sind spezielle Algorithmen zur Landschaftsgenerierung. Es werden dabei zufällig (kreisförmige) Hügel auf der Landschaft plaziert - sie unterscheiden sich in ihrem Radius, ihrem Ort und der Stelle der Plazierung.

Hügel mithilfe von Parabeln

Einfache Hügel lassen sich mithilfe von Parabeln erzeugen. Er soll durch eine Funktion H(x,y) beschrieben werden. H(x,y) gibt die Höhe des Hügels zurück, die er am Punkt (x,y) In der Landschaft beschreibt. Charakterisiert soll er durch seinen Mittelpunkt M=(x',y'), seine Höhe h und seinen Radius R werden. Die Form des Hügels soll einer nach unten geöffneten Parabel parabel entsprechen.

Wir benötigen einige Funktionen, um H leichter bestimmen zu können: dx := x' - x, dy := y' - y. (dx,dy) beschreibt dann den Vektor, der den Mittelpunkt mit einem Punkt (x,y) verbindet. Die Länge von (dx,dy) ist dann die Entfernung vom Mittelpunkt zu (x,y). Ist diese Länge also größer als R, so setze H(x,y) = 0.

Ist der Abstand dagegen kleiner, können wir einfach die Länge des Verbindungsvektors von H(x,y) quadrieren (wir wollen ja eine Parabel) und ziehen diesen Wert von h mit einem Vorfaktor ab:

H(x,y) = h - l*||(dx,dy)||^2

Nun gilt am Mittelpunkt M: H(M) = h. Ist aber ||(dx,dy)|| = R, so soll die Parabel den Wert 0 erreichen, was wir durch eine geeignete Wahl von

l := h/R^2

erreichen:

       /// <summary>
       /// Hügelfunktion
       /// </summary>
       /// <param name="x"></param>
       /// <param name="y"></param>
       /// <param name="mx">x-Koordinate des Mittelpunks</param>
       /// <param name="my">y-Koordinate des Mittelpunks</param>
       /// <param name="h">Höhe des Hügels</param>
       /// <param name="R">Radius der Hügels</param>
       /// <returns></returns>
       private double H(double x, double y, double mx, double my, double h, double R)
       {
           double dx = mx - x;
           double dy = my - y;
           double r_2 = dx * dx + dy * dy; // Abstand vom Mittelpunkt im Quadrat
           double R_2 = R * R;
           if (r_2 > R_2)
           {
               return 0;
           }
           else
           {
               return h * (1 - r_2 / R_2);
           }
       }

Man kann sich natürlich jede andere Hügelform konstruieren und im Hügelalgorithmus einsetzen.

Hügel zusammenbringen

Man kann nun auf einer Karte eine größere Menge Hügel zufällig plazieren und aufeinanderadieren und bekommt so eine schöne Karte. Diese normiert man affin auf Werte zwischen 0 und 1. Wenn man will kann man nun alle Werte auch noch quadrieren - Täler werden so ein bisschen breiter, Berg-Spitzen wachsen steiler an. Es ist auch ein guter Moment um Erosion zu simulieren. Karte speichern nicht vergessen.

Variation Inselalgorithmus: Den Algorithmus kann man leicht verändern, um Inseln zu erzeugen. Statt die Hügel wild auf der Karte zu plazieren, setzt man die höheren näher zur Mitte. Nach aussen hin fügt man kleinere Hügel hinzu. Ausserhalb einer bestimmten Entfernung zum Mittelpunkt dürfen keine oder nur sehr kleine Hügel hinzugefügt werden.

Dies kann man gut durch eine "Wahrscheinlichkeitskarte" erreichen. Wird ein Berg an einer bestimmten Stelle erzeugt, erhöht sich die Wahrscheinlichkeit in der Wahrscheinlichkeitskarte an dieser Stelle. So werden neue Erhebungen mit größerer Wahrscheinlichkeit neben bereits bestehenden Bergen erzeugt. Man kann den Wert um den die Felder der Wahrscheinlichkeitskarte erhöht werden abhängig von der Höhe des erzeugten Hügels machen. Dadurch ziehen höhere Berge neue Berge stärker an, als kleinere Hügel.