Moin Moin,
in meinem heutigen Beitrag geht es um die dynamische Generierung von 2D-Landschaften, wie man sie z. B. aus Spielen wie Age of Emires kennt. Die von mir gezeigten Code-Snippets sind in GML (GameMakerLanguage) programmiert, lassen sich jedoch recht einfach in andere Programmiersprachen übertragen.

Vorweg schon mal ein paar Beispiele, was der Algorithmus am Ende generieren kann:

Grundlage des Algorithmus ist eine Heightmap.

Eine solche Heightmap wird u.a. in der Spielentwicklung beispielsweise für 3D-Karten verwendet. Je heller/weißer ein Bereich ist, desto höher ist das Terrain an dieser Stelle.

Es gibt eine Vielzahl an Algorithmen, die eine solche Heightmap erzeugen können. Meine Variante ist inspiriert vom „Perlin Noise“ Algorithmus, welcher sich sehr einfach implementieren lässt.

Grundlage ist eine zweidimensionale Matrix. Zur Verdeutlichung, nehme ich in meinem Beispiel eine 5×5 Matrix.
Im ersten Schritt geht man alle Zellen durch und füllt diese mit Zufallswerten zwischen 0 und 255.

180	34	82	210	64
42	12	145	188	1
20	68	101	71	99
82	58	19	55	194
48	89	56	138	234

var map;
var mapWidth = room_width/32;
var mapHeight = room_height/32;

for(var h = 0; h < mapHeight; h++)
{
    for(var w = 0; w <; mapWidth; w++)
    {
        map[w,h] = irandom_range(0, 255);
    }
}

Anschließend iteriert man Zelle für Zelle durch und berechnet den durchschnittlichen Wert der benachbarten Zellen (oben links, oben, oben rechts, rechts, unten,….) und setzt diesen Wert in die aktuelle Zelle. Hier das Ergebnis, wenn die Zelle an der Position [0,0] besucht wurde.

29	34	82	210	64
42	12	145	188	1
20	68	101	71	99
82	58	19	55	194
48	89	56	138	234

Es wurde hier also geguckt, welche Werte in den umliegenden Feldern sind (34, 12, 42), diese Werte wurden dann zusammengezählt und durch die Anzahl der vorhandenen Nachbarn (3) geteilt. Als Ergebnis kommt dann die Zahl 29 in die aktuelle Zelle.

Und so arbeitet man sich von Zelle zu Zelle. Durch dieses Vorgehen werden die Bereiche aneinander angeglichen und minimale und maximale Werte relativiert.

for(var h = 0; h < mapHeight; h++)
{
    for(var w = 0; w < mapWidth; w++)
    {
         map[w,h] = scr_neighbor_sum(map, w, h);
    }
 }

Anschließend wird der Durchschnittswert aller Zellen aus der Matrix berechnet. Dieser wird benötigt, um die Gebiete später zuordnen zu können.

var mapAVG = scr_get_map_avg(map);

Nun können wir der Map die Tiles zuweisen, die es in bestimmten Wertebereichen haben soll (Wasser/Sand/Wald/…).

Ich gehe dazu erneut jede Zelle durch und schaue nun, ob der aktuelle Wert kleiner ist als der durchschnittliche Gesamtwert (mapAVG).
Wenn dies der Fall ist, wird an dieser Stelle Wasser platziert. Wenn der aktuelle Wert größer als mapAVG ist, wird Sand zugewiesen.

Je nachdem wie viele Tiles vorhanden sind, kann man natürlich auch Zwischenschritte definieren, um so z.B. noch einen Wald oder ein Gebirge hinzuzufügen.

for(var h = 0; h < mapHeight; h++)
{
    for(var w = 0; w < mapWidth; w++)
    {
        var avg = mapAVG;
        
        if(map[w,h] < avg) { instance_create(w*32,h*32, obj_water); // erzeuge wasser }else { if(map[w,h] > avg + 5 && map[w,h] < avg + 5) { instance_create(w*32,h*32, obj_sand); // erzeuge sand }else if(map[w,h] > avg + 15)
                  {
                      instance_create(w*32,h*32, obj_wood); // erzeuge wald
                  }else
                  {
                      instance_create(w*32,h*32, obj_stone); // erzeuge gebirge
                  }
        }
    }
}

Fertig ist eine rudimentäre Generierungsfunktion. Man kann den Algorithmus an manchen Stellen noch optimieren. Ich kann empfehlen, den Schritt bei dem die Durchschnittswerte für die umliegenden Felder berechnet werden, mehrfach durchlaufen zu lassen. Dadurch erhält man am Ende ein sauberes Ergebnis.

for(var i = 0; i < 4; i++)
{
    for(var h = 0; h < mapHeight; h++)
    {
        for(var w = 0; w < mapWidth; w++)
        {
            map[w,h] = scr_neighbor_sum(map, w, h);
        }
    }
}

Hier der gesamte Quellcode – aufgeteilt nach Funktionen.
main
scr_get_map_avg
scr_get_neighbor_sum
scr_is_cell

Falls ihr Ideen oder Optmimierungsvorschläge habt, dürft ihr sie gern in der Kommentarbox hinterlassen.