Zufällige 2DMap-Generierung

[BeRsErKeR]

Hallo zusammen,

ich bastele gerade an einem kleinen 2D-Spiel. Für die Welt nutze ich eine tilebasierte 2D-Karte, die aus 32x32 großen Tiles besteht und 32x24 bis 2048x2048 Tiles groß sein kann. Ich möchte nun einen Algorithmus einbauen mit dem Zufallskarten erstellt werden. Ich habe einige Regeln (bestimmte Terraintypen dürfen nur an bestimmte andere grenzen usw). Außerdem soll das ganze einen Inselstil haben, sprich Wasser ist meist außen und Landmassen im Zentrum bzw. bei mehreren Inseln dann halt Landmassen. Auch auf den Inseln möchte ich eine gewisse Clusterung erzeugen (Berge, Grasflächen, Süßwasserseen, vielleicht sogar Flüsse).

Mir geht es hier nicht darum einen fertigen Algorithmus zu bekommen, sondern eher um prinzipielle Ideen wie man da ran gehen kann. Oder vielleicht gibt es ja auch schon Algorithmen um zum Beispiel effektiv eine Clusterung zu bewirken.

Für die Generierung kann man über bestimmte Parameter die prozentuale Anzahl der Terraintypen vorgeben (z.B. ein Parameter "Inseln" der steuert wieviel Landmasse es gibt usw).

Mein erster Versuch hat in einem großen Switch-Block die möglichen Terraintypen für alle 4 Nachbartiles eines Tiles bestimmt und zufällig einen ausgewählt. Das ganze dann rekursiv bis die ganze Map befüllt ist. Da Berge und Wasser sehr strenge Regeln haben (Wasser kann nur an anderes Wasser oder Strand grenzen, Berge können nur an andere Berge und Grasland grenzen) bzw. nur wenige Möglichkeiten für Alternativen bieten, sind diese Teile schon recht ansehnlich. Beim Rest ist noch alles ziemlich kunterbunt. Außerdem kann ich durch die Rekursion nicht immer ausschließen, dass ungültige Terrain-Kombinationen entstehen. Wenn das letzte zu füllende Tile an 4 Tiles angrenzt, die kein Terrain ermöglichen (z.B. eine Seite Wasser und eine Seite Berg) dann hab ich auch ein Problem.

Prinzipiell müsste ich also weiter vorausschauen und die Clusterung könnte man eventuell durch eine Gewichtung erreichen. Aber ich wollte erstmal hier fragen. Vielleicht habt ihr ja ein paar gute ideen.

Hier mal ein Ausschnitt wie es zur Zeit aussieht:



Bitte nicht an der Optik stören. Das Ganze steckt noch in einer sehr frühen Prototyp-Phase. ;) Mir geht es erstmal um die Funktionalität.

Was man im Bild auch noch gut sieht sind die Bereiche rechts wo Strand und Meerwasser zusammen mitten in der Insel vorkommen, da Strand natürlich neben Grasland liegen kann usw. Ich muss hier also irgendwie besser Aussagen treffen können wo sich ein Tile befindet (bezogen auf eine Insel zum Beispiel).

[RazorX]

Vielleicht hilft dir das schonmal weiter: http://www-cs-students.stanford.edu/~am ... eneration/
Die Aussehen des Voronoi-Diagramms bzw. der Thiessen-Polygone kann man durch die Metrik anpassen, sodass man letztlich auch einen Block-Look haben könnte.

Außerdem fand ich die Arbeit von ArtificialMind bezüglich CyberDive sehr interessant. Konkret, dass er sich bei der Landmassengenerierung an der Natur orientiert hat und eine Plattentektonik und Klimasimulation nachgebaut hat. http://zfx.info/viewtopic.php?t=1830

[BeRsErKeR]

Danke erstmal für die Antwort. Die beiden Sachen bringen mich auf eine gute Idee.

Ich werde erstmal grob Insel-Shapes je nach Mapgröße und Inselanzahl generieren (also einfach erstmal geometrisch ohne Rücksicht auf Tile-Grenzen) und daraus dann vereinfacht die Formen der Landmassen in Tiles erzeugen. Den Rest kann ich dann mit Wasser füllen. So kann ich auch besser die Küstenzüge (Strandtiles und Tiles mit seichtem Wasser) generieren. Die Mechanismen könnte ich dann auch für Bereiche auf der Insel nutzen (quasi "Inseln" aus Grasland, "Inseln" aus Süßwasser und "Inseln" aus Bergen). Die Formen der Shapes können dann je nach Typ variieren (z.B. Flüsse, Bergketten, Seen, Ebenen). Das klingt schonmal vielversprechend.

Danke nochmal. Ich werd es heute abend mal ausprobieren. ;)

[FlorianB82]

Danke für den Link (http://www-cs-students.stanford.edu/~am ... eneration/), RazorX. Hat Spaß gemacht, zu lesen. Zumal ich mich vor Jahr und Tag auch mit so etwas herumgeschlagen habe, und so eine Anleitung wirklich gut hätte brauchen können ;)

[kristof]

Ein einfacher Ansatz wäre vielleicht auch noch, dass du eine art Höhenkarte erzeugst und dann Grenzwerte definierst die bestimmen welche Höhen zu welchen Tiles führen. Wenn das nicht reicht und du auch noch so etwas wie Biome definieren willst, könntest du auch mehrere solcher Höhenkarten kombinieren, wobei dann eine der Karten z.B. die Temperatur an dieser Stelle angibt. Das ließe sich dann beliebig erweitern.
Die Höhenkarten könntest du erzeugen, indem du eine sehr niedrig aufgelöste Textur mit Zufälligen Grauwerten füllst und dann mit entsprechender Interpolation auf die Grösse deine Spielwelt ziehst. Das ergibt dann eine recht "weiche" Hügellandschaft.

[BeRsErKeR]

Danke. Theoretisch ein guter Ansatz. Die Frage ist dann aber wie ich z.B. ein Atoll abbilde. Also mehrere Inseln. Das ist so ziemlich das Wichtigste weil das Spiel auf Inseln spielen soll. Man kann sich das vom Aussehen etwa wie Anno 1602 vorstellen von den Maps (halt ohne Iso).

[kristof]

Du musst die Texturen ja nicht mit rein zufälligen Werten füllen. Du kannst ja auch eine 2D Funktion finden, die grob deiner gewünschten Form entspricht. Bei einem kreisförmig angeordneten Atoll also vielleicht eine Kombination aus Sinus und Kosinus. Das ganze dann noch etwas verzerren und ein Rauschen drüber legen, sodass es nicht mehr so klinisch aussieht.
Wenn du eine bestimmte Anzahl von Inseln brauchst könntest du das Verfahren auch pro Insel anwenden (Wieder eine geeignete Funktion finden pro Insel) und dann die so generierten Inseln in ein separat generierten Meer einbetten.
Aber sind auch nur Ideen. Viel Spass beim rum probieren :)

[BeRsErKeR]

Jo danke. Ich guck mal was ich hinkriege. Ich muss erstmal eine Funktion hinkriegen, die möglichst interessante Inselformen generiert. Soll ja nicht zu eckig oder zu rund werden. ;) Ich glaub bei Anno hatten sie sich das einfach gemacht und eine Hand voll statischer Inseln fest vorgegeben. Und die dann kombiniert. Ich wills aber schon sehr zufällig halten aber wie gesagt mit bestimmten Regeln.

[joeydee]

Den Ansatz von Kristof halte ich für geeignet und relativ leicht umsetzbar.
Ich würde da Perlin Noise als Basis nehmen (das wäre optisch in etwa wie die genannte skalierte Zufallstextur, nur mehrere in verschiedener Skalierung übereinander).
Unter einem bestimmten Wert ist Wasser. Für Inseln einen kreis- oder kastenförmigen Verlauf aus der Mitte heraus darübermultiplizieren, so dass Pixel an den Rändern auf alle Fälle unter Meereshöhe liegen.
Perlin-Höhendaten multipliziere ich gerne mit sich selbst (Meereshöhe als Nullwert, Meer ist negativ), das gibt ggf. natürlichere Geländeformen.
Fels existiert eher an steilen Stellen, Bewuchs eher an flachen, die nicht zu hoch (niedrige Temperatur) und nicht zu tief (Strand/Wasser) sind. Aber natürlich nicht überall, dafür die potenziellen Stellen mit einer weiteren Noise-Textur maskieren.

[ponx]

mein Kommilitone Nick Pruehs hat seine Masterarbeit über prozedurale Maps geschrieben und vor ein paar Wochen online gestellt, bestimmt auch eine gute Inspirationsquelle: http://www.levelsbychance.com/

[joeydee]

Ich konnte natürlich die Finger nicht davon lassen...
Falls du ein Flash-Plugin hast, hier eine kleine Demo (ich hoffe es macht niemandem etwas aus, hat nur 8k):

Gradient.swf

code=actionscript

(7.37 KiB) 8926-mal heruntergeladen

Hier der relevante Teil der Berechnung, die Parameter der Perlin-Methode sind hier dokumentiert. Beispiele für Perlin Noise solltest du leicht im Netz finden.
Flash kann das nur für Bitmaps, und ich war zu faul Perlin und Pseudorandom jetzt auf die Schnelle neu zu implementieren. Deshalb der Umweg über das Auslesen in den uint-Vektor und das Casting in float. Da sollte man natürlich besser von vornherein bei float bleiben.
ActionScript ist ein JavaScript-Dialekt, der Code müsste also auch für Flash-Fremde zu lesen sein.
Prinzipiell werden wie vorgeschlagen 2 unterschiedliche Perlin-Muster verrechnet, sowie ein Kreisverlauf für eine optionale Insel in der Mitte der Map.
Natürlich könnte man die Insel (oder gleich mehrere) auf dieselbe Weise auch frei platzieren und skalieren. Oder man nimmt bei größeren Maps ein drittes Muster mit größerer Wellenlänge für viele automatische Inseln als Grundlage (mach mal centerIsland auf 0 und waterLevel ca. auf 0.7).

Code: Alles auswählen

//Ausgangswerte
var seed1:Number=123;
var seed2:Number=456;
var waterLevel:Number=1;
var centerIsland:Number=1;
var fractality:Number=10;
var wavelength:Number=20;
generateMap();

function generateMap():void{
	bmp.perlinNoise(wavelength,wavelength,fractality,seed1,false,true,4,false);
	var hbytes:Vector.<uint>=bmp.getVector(bmp.rect);
	bmp.perlinNoise(wavelength*2,wavelength*2,fractality/2,seed2,false,true,4,false);
	var vbytes:Vector.<uint>=bmp.getVector(bmp.rect);
	
	var resH:Number=res*0.5;
	var rq:Number=resH*resH;
	for(var px:int=0;px<res;px++){
		for(var py:int=0;py<res;py++){
			var id:int=py*res+px;
			//island mask
			var dq:Number=Math.pow(px-resH,2)+Math.pow(py-resH,2);
			var islandMask:Number=0;
			if(dq<rq)islandMask=Math.pow(1-dq/rq,2);
			//perlin noise data access
			var h:Number=Number(hbytes[id] & 255)/255;//(uint to number 0 to 1)
			var v:Number=Number(vbytes[id] & 255)/255;//(uint to number 0 to 1)
			h=h+islandMask*centerIsland*waterLevel-waterLevel;//apply island mask and water level
			//some "rules":
			if(h<0)h=0;//ocean level
			h=Math.pow(h,2);//sharpen mountains, flatten beach
			var fin:uint=0x0000FF;//ocean
			if(h>0 && h<0.05)fin=0xFFFF00;//beach
			if(h>0.05 && h<0.3){
				fin=0xFF8020;//earth;
				if(v>0.6)fin=0x008000;//woods
				if(v<0.5){
					fin=0xFFFF00;//beach
					if(h>0.1 && h<0.7 && v<0.3)fin=0x80CCFF;//water
				}
			}
			if(h>0.3)fin=0xCCCCCC;//stone;
			bmp.setPixel(px,py,fin);//show 
		}
	}
}

[Schrompf]

Schönes Ding, und auch noch zum Live-Rumspielen! Danke!

[gdsWizard]

@joeydee

Der Mapgenerator liefert wirklich gute Ergebnisse. Vielleicht kann ich das mal gebrauchen. :)

[BeRsErKeR]

Cool danke. Das sieht wirklich vielversprechend aus. :) Werde gerade leider noch von meinem Map-Shader aufgehalten. Danach guck ichs mir mal genauer an.

[BeRsErKeR]

So endlich hatte ich mal ein bisschen Zeit und hab versucht deinen Code in C++ zu gießen inklusive PerlinNoise-Implementierung. Hab leider auf die schnelle keine gefunden, die so schön konfigurierbar war, wie die in deinem Beispiel. Aber ein seed war natürlich dabei. Nach ein bisschen Gefummel und Anpassung an meinen Code und mein Mapformat habe ich nun alles ans Laufen gebracht und die erste kleine Testinsel kam zum Vorschein. :)



Kann sich auf jeden Fall schonmal sehen lassen. Ich muss nun gucken wie es aussieht wenn ich ein bisschen mit den Werten rumspiele. Vielen Dank auf jeden Fall nochmal. Das hilft mir sehr weiter.

[joeydee]

Freut mich :-)
Die Konfigurationsmöglichkeit müsste aber jede Implementierung mit sich bringen. Fractality sind einfach die Anzahl Generatoren (oder Layer), meist fängt man ja mit hoch vergrößertem interpoliertem Noise an (große Wellenlänge), halbiert diese mit jedem Durchgang und verrechnet sie mit verminderter Stärke auf das bisherige Ergebnis. Wavelength ist dann letzten Endes nur der Skalierungsfaktor, mit welchem man anfängt.
Alle anderen Parameter in der Flash-Implementierung sollten dann eigentlich keine Rolle spielen. Falls du noch was vermisst, frag einfach.

[BeRsErKeR]

Hatte leider nicht viel Zeit und hab daher die erste halbwegs vernünftig aussehende Implementierung verwendet. Die besteht nur aus 5 überschaubaren Funktionen und nutzt C++11-Features. Es ist eine Klasse, die man mit einem seed-Wert initialisiert und dann gibt es eine Methode, die dir den noise-Wert für eine 3-dimensionale Koordinate liefert. Intern wird mit einem Cube berechnet. Ich hab mich noch nicht allzu intensiv mit Perlin-Noise beschäftigt, daher weiß ich nicht genau wo ich da die Faktoren integrieren muss.

Im Moment iteriere ich einfach über all meine Tiles in x- und y-Richtung und lasse mir den noise-Wert bei (x = XInTiles / MapWidth, y = YInTiles / MapHeight, 0.0) liefern. Die Werte sind bereits normiert.

Ich habe ein paar Tests gemacht. Größtenteils sehen die Maps gut aus. Manchmal ist aber gar keine Insel vorhanden oder sie sieht ziemlich komisch aus. Da muss ich eventuell noch etwas mit den Schranken rumfummeln, damit das in 99% der Fälle was realistisches ausspuckt.

Mein Problem ist jetzt noch, dass ich sicherstellen muss, dass bestimmte Ressourcen immer vorhanden sind (mit einem Minimalmaß). Zum Beispiel geht es nicht ganz ohne Berge, Seen oder Wälder. Bei den Testgenerierungen waren aber in weniger als 25% der Fälle Berge vorhanden usw. Es gibt also noch einiges zu tun.

Aber du hast mich definitiv in die richtige Richtung gestoßen.

[joeydee]

Im Moment iteriere ich einfach über all meine Tiles in x- und y-Richtung und lasse mir den noise-Wert bei (x = XInTiles / MapWidth, y = YInTiles / MapHeight, 0.0) liefern. Die Werte sind bereits normiert.

Ah ich sehe wo noch was fehlt. Der Pseudorandom-Wert ist erst die halbe Miete. Nun kannst du damit z.B. ein 64x64-Raster nur sagen wir an jedem 8. Punkt füllen und die Werte dazwischen interpolieren, statt jedes Pixel völlig zufällig zu beschreiben. Das gibt ein recht weiches, unscharfes Muster. Und dann ein weiteres Muster mit anderem Seed, diesmal aber an jedem 4. Punkt (doppelte Frequenz), dafür nur mit halber Intensität zum ersten addiert (ausgehend von einer ursprünglichen Normierung von -1 bis 1). Dann eins mit 2 Pixel und 1/4 Intensität, am Ende noch eins mit jedem Pixel und 1/8 Itensität.
Heraus kommt eine Art Wolkenmuster, wenn du da alle Pixel testweise unter einem bestimmten Wert schwarz und den Rest weiß machst, sollte eine ziemlich unregelmäßige Küstenlinie herauskommen.
"Wellenlänge" in meinem Beispiel war dann einfach der Abstand der Samples im ersten Muster (hier wäre das 8), und "Fraktalität" die Anzahl der Generatoren (hier wären das 4), d.h. Letzteres bestimmt indirekt die Detailgröße des letzen Musters.
Es gäbe da noch die "Persistenz" als wesentlichen Faktor, die bestimmt, mit welcher Intensität der Einfluss jeden Musters abnimmt.
Auf DelphiGList das Handwerkszeug für alle Schritte ink. Code-Beispielen von Null auf sehr ausführlich erklärt. Den Random-Generator kannst du natürlich überspringen und deinen nehmen.

Wo hast du deinen her? Würde mich interessieren wie der aussieht, denn mit 3D-Noise will ich demnächst auch wieder experimentieren. Hast du einen Link?

[BeRsErKeR]

Wo hast du deinen her? Würde mich interessieren wie der aussieht, denn mit 3D-Noise will ich demnächst auch wieder experimentieren. Hast du einen Link?

Ich habe eine C++-Portierung des Ursprungsalgorithmus von Ken Perlin. Du findest ihn hier: http://solarianprogrammer.com/2012/07/1 ... se-cpp-11/. Die Generatoren stammen direkt aus C++11. Hatte wie gesagt bislang wenig Zeit mir da selbst was auszudenken.

[joeydee]

Hatte wie gesagt bislang wenig Zeit mir da selbst was auszudenken.

Nur nochmal bevor ein Missverständnis auftritt: Sollst du ja auch nicht, Hauptsache du hast reproduzierbare Pseudo-Zufallszahlen. Da gibts keinen der gleich fertige Landschaften produziert, die reinen Noise-Muster sehen alle prinzipiell so verpixelt aus.
Die Landschaft bzw. Clusterung und Fraktalität entsteht dann erst durch die Interpolation verteilter Noise-Samples und Verrechnung über mehrere Layer. Das ist nicht mehr Teil der Noise-Funktion. Flash bietet zwar beide Schritte innerhalb einer einzigen Bitmap-Methode, du musst zweiteres dann aber selbst machen.

[BeRsErKeR]

Ja ich hab mich jetzt noch etwas zu dem Thema belesen. Gerade auch in Hinblick auf Cluster. Habe nun noch einen Wrapper drumrum gebaut, der Angaben zur Anzahl der Oktaven und der persistence (Frequenz/Amplitude) entgegennimmt. Ich hab auch schon Ansätze gefunden, wie ich bestimmte Anforderungen (z.B. mindestens 10% Wald) umsetzen kann. Leider fehlt mir wie gesagt gerade etwas die Zeit. Erste Tests haben aber sehr ähnliche Ergebnisse geliefert, die ich vorher bereits hatte. Ich muss vielleicht erstmal eine genauere Analyse der erzeugten Daten durchführen, damit ich besser abschätzen kann wie ich die Schranken für die einzelnen Terrainarten setzen muss, damit es mit meinen Vorgaben korreliert. Und um das "mehrere Inseln"-Problem habe ich mich bislang auch noch nicht gekümmert, auch wenn die Ansätze dafür da sind.

[Horus]

Hi,

ich habe eine Methode die dich vielleicht interessiert.
Die Map hier wurde so erstellt:
https://www.youtube.com/watch?feature=p ... AFwiQ5D1tg

Die Map besteht nur als Blockiert- und- Frei Tiles. Das ist beliebig erweiterbar!
Die Formen sind flüssig und vorab beeinflussbar.
Ich habs für meine KI-Simulation oben so gemacht, weil es nach einer Stunde fertig implementiert ist.

1. Tiles zufällig generieren, vom Verhältnis so, wie es später sein soll.
Man kann auch Formen vorgeben, welche später verschwimmen werden.

2. eine Schleife mit Tileanzahl * 10 oder mehr Durchläufen.
In dieser immer eine Zufallszahl generieren, auf eine zufällige Tile zugreifen.
Alle umliegenden Tiles prüfen und die Tile in den häufigsten angrenzenden Typ ändern.
Wenns keinen häufigsten gibt einen Zuffallstyp.

Das Ergebnis kann sich sehen lassen, falls meine Erklärung gut ist sollte es schnell umsetzbar sein.

LG