Block Terrain Generation

[Fu3L]

Hallo,
Edit: Ich habe endlich lesbaren Beispielcode gefunden. Vielleicht löst das mein Problem. Siehe
Terasology | Moving Blocks!


diesmal habe ich ein eher anspruchsvolles Problem, das mich schon länger ärgert. Ich hoffe, dass sich trotzdem jemand findet, der mir helfen kann. Als Belohnung für eine Lösung lobe ich meine ewige Dankbarkeit aus

Ich hatte vor einigen Monaten schonmal versucht per Marching Cubes Terrain prozedural zu generieren und bin kläglich gescheitert... Nicht an Marching Cubes, sondern an einer schönen Dichtefunktion - also der Funktion, die angibt, ob an einer Stelle etwas ist oder eben nicht. (Ein Screen siehe unten.. Gab auch andere, wos einfach nur alles Quaderförmig war, eher so wie im zweiten Screen)

Nun will ich das ganze in einer Minecraft-ähnlicheren Variante angehen und das ganze aus Blöcken aufbauen. Ich weiß, dass Notch für einige Punkte im Raum Perlin-3D-Noise nutzt und zwischen den Werten linear interpoliert. Ich hab auch viele Artikel gesehen, wo andere das ebenso machen:
Sehr zu empfehlender Artikel leider Beispiele in LUA-Skript
Beispiel in JavaScript und der Unity Engine (tut bei mir nicht!)

Meine bisherigen Versuche sehen so aus, wie die beiden letzteren angehängen Screenshots.
Mitlerweile glaube ich, dass ich irgendwo einfach ein Missverständnis drin hab, weils einfach nicht funktionieren will, egal wie viel ich rumprobiere.

Ich versuche das ganze per Fractal Brownian Motion zu lösen (also dem Übereinanderlegen mehrer Perlin-Noise Funktionen mit verschiedenen Frequenzen und Amplituden, so wie es auch bei Marching Cubes genutzt werden sollte (GPU GEMS 3 - Terrain Generation)).
Ich hab keine Ahnung was ich noch versuchen soll^^

Hier mal ein aktuelles (eher hässliches ) Codebeispiel, vor allem die letzten Funktionen vor dem Auskommentierten zum Schluss sind interessant und bilden Code aus den ganz oben genannten Artikeln ab (über bilinear() und lerp()), allerdings eher frustriert hingeschmiert.. Die erste Methode unter dem großen "CREATION" ist eigentlich das, was ich zu funktionieren erwartet hätte und was auch in den GPU GEMS beschrieben wird (Ergebnis ist Screen 2)...

Ein KSKB würde ich auf Anfrage auch wohl bauen, würde nur eben JME3 vorraussetzen.

package logic.world.generation;

import extern.SimplexNoise;
import gnu.trove.list.TIntList;
import gnu.trove.list.array.TIntArrayList;

import java.util.Random;

import logic.GOD;
import logic.world.BlockTerrain;
import logic.world.Offset;
import models.MeshCreator;

import com.jme3.scene.Geometry;

/**
 * May only be called by the BlockTerrain Loading Thread!
 * 
 */
public class WorldManager {

	private final BlockTerrain bt;
	private final int chunkSize = GOD.getChunkSize();

	private static int[] boxes = new int[16 * 16 + 2];

	private Noise[] noise = new Noise[3];

	private final double SCALE_HORIZONTALLY = 8;
	private final double SCALE_VERTICALLY = 4;

	private final int octaves = 1;
	private final double persistence = 0.5;
	private final int terrainHeight = 32;

	private final int terrainSize = 16;
	private final int detailSize = 8;
	private double yTurbulance = 1;

	static {

		Random rnd = new Random(0);

		for(int i = 0; i < 16; i++) {
			for(int n = 0; n < 16; n++) {
				int v = (int) (-0.2 * ((n - 10) * (n - 10)) + 5);
				v = v < 0 ? 0 : v;
				boxes[i * 16 + n] = (i << 12) | (n << 8) | v;
				//boxes[i * 20 + n] = rnd.nextInt(10);
			}
		}
		boxes[256] = (5 | (2 << 8));
	}

	//************
	//CONSTRUCTOR
	//************
	public WorldManager(final BlockTerrain bt) {
		this.bt = bt;
		noise[0] = new Noise(0, 0, 0);
		noise[1] = new Noise(10, 10, 10);
		noise[2] = new Noise(155, 255, 300);
	} //End Contructor

	//*******
	//LOADING
	//*******
	public Geometry getChunk(final Offset o) {
		int[] boxes = this.createNewChunk(o.getX(), o.getZ());
		return MeshCreator.createFrom(boxes);

	} //End getChunk();

	//********
	//CREATION
	//********
//Erste Variante mithilfe von 3 3D-Noise-Maps. Ursache für den zweiten Screenshot
	/*private int[] createNewChunk(int xOff, int zOff) {
		TIntList list = new TIntArrayList(300);
		for(int x = 0; x < chunkSize; x++) {
			for(int z = 0; z < chunkSize; z++) {
				for(int y = 63; y >= 0; y--) {
					if(y == 0) {  //Auf jeden Fall Boden einfügen
						list.add((x << 12) | (z << 8) | y);
					} else {
						double d = -y;
						d -= noise[0].get((x + xOff * chunkSize) / 20, y / 20, (z + zOff * chunkSize) / 20) * 15;
						d -= noise[1].get((x + xOff * chunkSize) / 10, y / 10, (z + zOff * chunkSize) / 10) * 5;
						d -= noise[2].get(x + xOff * chunkSize, y, z + zOff * chunkSize);
						if(d + 10 > 0) { //Nur wenn ein gewisser dichtewert erfüllt ist soll ein Block creiert werden
							list.add((x << 12) | (z << 8) | y);
						}
					}
				}
			}
		}
		return list.toArray();
	} //End createNewChunk();*/

//Zweiter Versuch, angelehnt an den Artikel von Gamedev.net
	private int[] createNewChunk(int xOff, int zOff) {
		TIntList list = new TIntArrayList(300);
		for(int x = 0; x < chunkSize; x++) {
			for(int z = 0; z < chunkSize; z++) {
				boolean ground = false;
				for(int y = 0; y <= 20; y++) {
//Betrachte nur jeden achten Block und interpoliere die restlichen Werte "linear" um wegbareres Gelände zu erhalten. Funktioniert auch anders nicht.
					double d = threshold(turbulance(groundGradient(y, 0, 20), shape(x + (xOff * chunkSize) / SCALE_HORIZONTALLY, y, z + (zOff * chunkSize) / SCALE_HORIZONTALLY)));
					//double d = 1 - 2 * (y / terrainHeight) + perlin((x + xOff * terrainSize) / detailSize, y / detailSize, (z + zOff * terrainSize) / detailSize);
					if(d == -1) {
						list.add((x << 12) | (z << 8) | y);
						ground = true;
					}
				}
			}
		}
		return list.toArray();

	}

//Gibt -1 aus, wenn ein Block gesetzt werden soll, sonst +1
	private double threshold(double d) {
		return d > 0 ? +1 : -1;
	}

//Berechnet einen Wert zwischen -1 und 1, der der Position des y-wertes auf der linie zwischen start und end entspricht (siehe GameDev Artikel)
	private double groundGradient(double y, double start, double end) {
		return (y - start) / ((end - start) / 2) - 1;
	}

//Ab hier vermute ich Unzulänglichkeiten meines Codes
	private double turbulance(double d, double yVar) {
		return d + yVar * yTurbulance;
	}

	private double shape(double x, double y, double z) {
		double total = 0;
		for(int i = 0; i < octaves; i++) {
			double freq = Math.pow(1.75, i);
			double amp = Math.pow((1 + persistence), i);
			total += interpolateNoise(x, y, z) * amp;
		}
		return total;
	}

//Hier ein Versuch nur jeden achten Block tatsächlich zu betrachten und den Rest zu interpolieren.
//Ein Block, der interpoliert werden soll
//Alles verzweifelte, eher hingeschmierte Versuche
	private double interpolateNoise(double x, double y, double z) {
if(x == (int) x && y == (int) y && z == (int) z) {
			return SimplexNoise.noise(x, y, z);
		}
		double[] cube = new double[8];
		cube[0] = SimplexNoise.noise((int) x, (int) y, (int) z);
		cube[1] = SimplexNoise.noise((int) x + 1, (int) y, (int) z);
		cube[2] = SimplexNoise.noise((int) x + 1, (int) y + 1, (int) z);
		cube[3] = SimplexNoise.noise((int) x, (int) y + 1, (int) z);
		cube[4] = SimplexNoise.noise((int) x, (int) y, (int) z + 1);
		cube[5] = SimplexNoise.noise((int) x + 1, (int) y, (int) z + 1);
		cube[6] = SimplexNoise.noise((int) x + 1, (int) y + 1, (int) z + 1);
		cube[7] = SimplexNoise.noise((int) x, (int) y + 1, (int) z + 1);
		double[] corners = new double[4];
		corners[0] = lerp(cube[0], cube[3], y - (int) y);
		corners[1] = lerp(cube[1], cube[2], y - (int) y);
		corners[2] = lerp(cube[4], cube[7], y - (int) y);
		corners[3] = lerp(cube[5], cube[6], y - (int) y);

		double v1 = lerp(corners[0], corners[1], x - ((int) x));
		double v2 = lerp(corners[3], corners[2], x - ((int) x));
		return lerp(v1, v2, z - ((int) z));
	}

	private double bilinear(double w1, double w2, double... a) {
		double v1 = lerp(a[0], a[1], w1);
		double v2 = lerp(a[3], a[2], w1);
		return lerp(v1, v2, w2);
	}

	private double lerp(double a, double b, double w) {
		return a + (b - a) * w;
	}

//1:1 abgeschriebene JavaScript Variante
	/*private double perlin(int x, int y, int z) {
		double total = 0;
		for(int i = 0; i < octaves; i++) {
			double frq = Math.pow(2, i);
			double amp = Math.pow(persistence, i);
			total += interpolatedNoise(x * frq, y * frq, z * frq) * amp;
		}
		return total;
	}

	private double interpolatedNoise(double x, double y, double z) {
		double ix = Math.floor(x);
		double fx = x - ix;
		double iy = Math.floor(y);
		double fy = y - iy;
		double iz = Math.floor(z);
		double fz = z - iz;

		double v1 = sNoise(ix, iy, iz); //          ---
		double v2 = sNoise(ix + 1, iy, iz); //        +--
		double v3 = sNoise(ix, iy + 1, iz);//         -+-
		double v4 = sNoise(ix + 1, iy + 1, iz);//       ++-
		double v5 = sNoise(ix, iy, iz + 1);//         --+
		double v6 = sNoise(ix + 1, iy, iz + 1);//       +-+
		double v7 = sNoise(ix, iy + 1, iz + 1);//       -++
		double v8 = sNoise(ix + 1, iy + 1, iz + 1);//     +++

		double i1 = curve(v1, v2, fx);
		double i2 = curve(v3, v4, fx);
		double i3 = curve(v5, v6, fx);
		double i4 = curve(v7, v8, fx);

		double i5 = curve(i1, i2, fy);
		double i6 = curve(i3, i4, fy);

		return curve(i5, i6, fz);
	}

	private double sNoise(double x, double y, double z) {
		double sides = (noise(x - 1, y, z) + noise(x + 1, y, z) + noise(x, y - 1, z) + noise(x, y + 1, z) + noise(x, y, z - 1) + noise(x, y, z + 1)) / 12.0;
		double center = noise(x, y, z) / 2.0;
		return sides + center;
	}

	private double noise(double x, double y, double z) {
		Random rnd = new Random((int) (x * 657 + y * 111 + z * 11));
		return 2 * (rnd.nextDouble() - 0.5);
	}

	private double curve(double a, double b, double t) {
		return a * (1 - t * t * (3.0 - 2.0 * t)) + b * t * t * (3.0 - 2.0 * t);
	}*/
} //Ende der 1:1 abgeschriebenen JavaScript Variante

Hilfsklasse Noise, die im ersten Versuch Verwendung findet (siehe zweiter Screenshot)

import extern.SimplexNoise;

public class Noise {

	private final int LENGTH = 20;

	double[][][] values = new double[LENGTH][LENGTH][LENGTH];

	//************
	//CONSTRUCTOR
	//************
	public Noise(int xOff, int yOff, int zOff) {
		for(int x = 0; x < values.length; x++) {
			for(int y = 0; y < values.length; y++) {
				for(int z = 0; z < values.length; z++) {
					values[x][y][z] = SimplexNoise.noise(x + xOff, y + yOff, z + zOff);
				}
			}
		}
	} //End Constructor

	public double get(int x, int y, int z) {
		return values[Math.abs(x % LENGTH)][Math.abs(y % LENGTH)][Math.abs(z % LENGTH)];
	}
} //End Noise

 

[Samake03]

Zu deinem Problem kann ich als Anfänger nicht allzu viel sagen, jedoch hat Notch mal seinen TerrainGenerator versucht zu beschreiben. Ich versteh zwar nicht was er schreibt, falls du das noch nicht kennst, kann vielleicht irgendetwas davon helfen.

Fan-Übersetzung von "woiobo" auf Minecraft.de: (Terrain generation, Part 1 [Archiv] - Minecraft.de)

Ich habe versprochen, einen Artikel über technische Aspekte von Minecraft zu schreiben, bin aber nie dazu gekommen.
Jetzt sitze ich in einem kleinen Flugzeug und habe grad nichts zu tun, also los!

Einer der kompliziertesten Teile in Minecraft ist die Terrain-Generation. Als ich das
Spiel so verändert habe, das die Welt von einer begrenzten Zone zur einerunendlichen wurde, 
wurde auch die Terrain-Generation viel komplizierter, weil das Terrain generiert werden musste
während der Spieler erforscht, und jene immer dieselbe sein musste, egal aus welcher Richtung 
dieser kommt.

1) Wie undendlich ist es?

Lasst mich zuerst ein paar Dinge über die "unendlichen" Maps klarstellen: Sie sind nicht unendlich,
aber es gibt auch kein Limit. Es wird bloß immer unrealistischer und verbugter, je weiter du weg
vom Spawn gehst. Terrain wird generiert, geladen, gespeichert und gerendert in Chunks von je
16*16*128 blocks.

Diese Chunks haben die Wertigkeit eines 32-bit Integers, welcher grob genommen zwischen minus
Zweimilliarden und plus Zweimilliarden liegt. Wenn du dich außerhalb dieses Radius' bewegst, 
werden die dort geladenen Chunks die gespeicherten Chunks überschreiben, d.h. ab diesem 
Punkt werden Items, die auf Blöcke angewiesen sind falsch bzw. komisch agieren.

Dies sind die zwei "wirkenden" Limits.

Die meisten anderen Dinge, wie die Generation durch Seed oder Entity-Orte nutzen 64-bit Doubles
für die Ortsbestimmung, aber sie tun auch viele fehlerhafte Sachen; zum Beispiel bewegt sich der
Spielerauf sehr weiten Distanzen öfters langsamer als im Zentrum der jeweiligen Welt - dies passiert
durch Rundungsfehler (im Berechnungsprozess).

Der Terrain-Generator kann auch seltsame Formen generieren, große Blöcke aus Eisen sind möglich,
aber soetwas habe ich in letzter Zeit gesehen weder weiß ich welche Vorraussetzungen erfüllt werden
müssen mit soetwas passiert.

Ein Hauptproblem auf langen Distanzen ist, das die Physik von Bugs heimgesucht wird, so kann der
Spieler z.B. durch normale Blöcke fallen oder bleibt in Wänden hängen.

Viele dieser Probleme können gelöst werden, indem man die bisher mathematisch berechnete Position
des SPielers durch ein lokales Modell, welches den Spieler umgibt, ersetzt sodass alle Nummern
(Koordinaten) den gleichen Wert haben. Für das Rendern benutz Minecraft inzwichen schon lokale,
zum Spieler relative, Koordinaten im Block selbst und außerhalb um den Eindruck der Fortbewegung
zu gewinnen.

Wir werden diese Bugs nicht beheben, solange der gewöhnliche Spieler von diesen beim normalen
Spielablauf nichts merkt - aber ich hab ein gutes Gefühl (dabei), weil dies bisher noch nie
vorgekommen ist - und auch nie wird, denn soweit zu laufen benötigt viel Zeit.
Aber die Bugs geben den "weit entfernen Ländern" ein Charisma und etwas Mysteriöses...

2) Ist diese Form nicht großartig??

In den ersten Versionen von Minecraft habe ich eine "2D Perlin noise heightmap" (2D Höhenkarte)
benutzt um die Form für die Welt festzulegen, oder eher gesagt, ich benutzte mehrere - eine für die
Höhenschichten, eine für die Grobheiten sowie eine für die regionalen Details.
Für jede Kolumne von Blocks betrug die Höhe (elevation + (roughness*detail))*64+64
(also Höhe + ("Grobheiten"*Details))*64+64).
Die Höhe sowie die Grobheiten waren einfache, große gezerrte Ausmaße (der Werte), währen die
Details komplexer waren.
Diese Methode hatte einen großen Vorteil durch ihre Schnelligkeit, da nur 16*16samples pro chunk
generiert wurden - Nachteil war jedoch, das diese (die generierten Landschaften) langweilig waren,
da u.a. keine Vorsprünge (aufgrund der Höhenschichten) generiert wurden.

Ich wechselte das System in eine ähnliche, auf 3D Perlin basierende, Methode.
Anstatt die "Grundhöhe" zu generieren, wechselte ich den Wert in eine "Dichte", wo alles unter 0 Luft
und alles über 0 "der Rest", also Grund, wurde.
Um sicherzugehen dass die letzte Ebene (Bedrock) solid, also unzerstörbar ist, habe ich einfach diese
Höhe zur berechneten Gesamtsumme addiert.

Leider kam ich sofort in Performance, sowie Spielschwierigkeiten (im Sinne von Spielbarkeit).
Performanceprobleme aufgrund des hohen Samplings (bei der ersten Methode waren es nur 16*16),
und Spielschwierigkeiten weil keine ebenen Flächen oder "sanfte" Berge generiert wurden.
Die Lösung beider Probleme enstand dadurch, das horizon sowie vertikale sampling auf eine niedrigere
Auflösung zu bringen und eine lineare Interpolation zu machen.
Plötzlich hatte das Spiel flache, ebene Flächen, sanfte (abgerundete) Hügel und die meisten, allein in
der Luft schwebenden Blöcke, verschwanden.

Exakt diesen Vorgang, ein bisschen abgeändert und durch die Zeit, die ich mit dem Spiel verbracht
habe weiterentwickelt, nutze ich für die Generierung von Landschaften - jedoch werden die 2D-Karten
von mir immernoch genutzt.

Was noch zum Thema Terrain-Generierung kommt:

* Biome!
* Höhlen sowie große Features
* Bäume, Seen und kleine Features
* der Nether!

Aber nun mache ich mich zum landen bereit um in den nächsten Flieger zu wechseln!

Original Post:

Terrain generation, Part 1 : The Word of Notch

 

[Fu3L]

Danke für deine Mühe.

Der Blogpost ist mir als Vollblutminecraftspieler durchaus bekannt, siehe mein erster Post

Ich weiß, dass Notch für einige Punkte im Raum Perlin-3D-Noise nutzt und zwischen den Werten linear interpoliert.

Entspricht quasie dem vorletzten Absatz seines Eintrags, welcher der spannenste ist

Ich hab noch nicht weiter reingesehen, aber habe oben ganz oben einen Link reineditiert, wo man tatsächlich funktionierenden Java Quelltext sehen kann.. Mit dem sollte ich es schaffen, meine Fehler zu beseitigen.

 

[Helgon]

Ich wollt dich grad nach verständlichem Beispielcode fragen.

Und da editierst du das rein, großartig

 

[Kr0e]

Interessant, ich arbeite grad auch einem Algorithmus, allerdings mit einem ganz anderen Ansatz. Anstatt auf Techniken wie Voxel etc. zu setzen, hatte ich mir zum Ziel gesetzt, das Terrain durch die Simulation von sich verschiebenden und verformenden Terrainplatten zu realisieren mit noch ein paar anderen Ideen, die vlt unkonventionell erscheinen aber dennoch meine Neugier erweckt haben. Unser Prof. hielt es für einen gewagten Ansatz Aber mal sehen ...

 

[Samake03]

Hab hier noch was interessantes. Ist ein OpenSource Project welches sich zum Ziel setzt die Optik von Minecraft mit anderen Spielelementen zu vereinen. Vielleicht gibts da im Code noch Gute Ansätze für dich? Die Bilder sehen zumindest vielversprechend aus, für meinen Geschmack sogar besser als das Terrain von Minecraft seitdem Notch den Generator verändert hatte.

Terasology | Moving Blocks!

 

[Kr0e]

Hallo,
Edit: Ich habe endlich lesbaren Beispielcode gefunden. Vielleicht löst das mein Problem. Siehe
Terasology | Moving Blocks!

 

[Fu3L]

Wir scheinen aneinander vorbeizureden^^

Aber ums zu bestätigen, es funktioniert tatsächlich^^ Ich war wohl nur etwas unfähig^^

Mal einen Screen gemacht (ist etwas hell, weil ich die Farbe testweise nach der Höhe vergebe und bei den Tests vorher die Strukturen kleiner waren^^)

@Kr0e: Das klingt interessant, auch wenn ich mir so noch wenig darunter vorstellen kann

 

[Helgon]

Sieht doch schon ganz nett aus