Hi
ich habe mich im Rahmen eines Benutzerwunsches dazu bereiterklärt, den Diamond-Square-Algorithmus zu implementieren. Hierbei verwende ich ein iteratives Vorgehen. Es wird ein Raster mit 2^n x 2^n Punkten in festem Abstand verwendet, denen jeweils ein Höhenwert zugeordnet wird, wobei n die Länge einer Seite angibt. tiefe sei hierbei der maximale Ausschlag der Tiefe. Alle Höhenwerte liegen zwischen -tiefe und tiefe.
Das Verfahren ermöglicht bspw. das Generieren von Terrain auf Basis von Zufallszahlen, ohne hierbei hochgradige Abweichungen zwischen zwei einzelnen Punkten zur Folge zu haben.
Die Vorgehensweise ist besonders anschaulich durch die rekursive Vorgehensweise ersichtlich:
Man möchte ein Quadrat mit zufälligen, aber "glatten" Höhenwerten effizient befüllen. Das Quadrat soll eine Seitenlänge, die eine Potenz von 2 darstellt, besitzen, wodurch der Algorithmus weiter vereinfacht wird.
Jedem Paar (x, y) wird hierbei ein Höhenwert zugeordnet, wobei gilt, dass x und y je zwischen 0 und 2^n-1 liegen (jew. inklusive).
Es wird ein Quadrat mit zufällig gesetzten Höhenwerten der Eckpunkte genommen und anschließend folgender Algorithmus ausgeführt:
Das Quadrat wird, sofern die Seitenlänge größer als 0 ist, in 4 gleichgroße Quadrate zerteilt, für die der Algorithmus ebenfalls aufgerufen wird. Nun werden jeweils die ungesetzten fünf Punkte (jeweils die Seitenhalbierenden aller Seiten und der Mittelpunkt des ursprünglichen Quadrats) mit zufälligen Werten befüllt. Die zufälligen Werte sollen nicht zu weit von den Höhenwerten des ursprünglichen Quadrats abweichen, da es sonst zu einer hohen Höhendifferenz zwischen zwei Nachbarn kommen kann. Hierdurch erklärt sich auch das rekursive Vorgehen, denn es bietet sich an, die Tiefenunterschiede durch tiefe/2^i zu beschränken, wodurch solch ein glatter Übergang zwischen zwei Nachbarn möglich ist. Der neu generierte Wert wird daher auf den Mittelwert der Höhenwerte der jeweiligen Quadrateckpunkte aufaddiert und anschließend gespeichert.
Spoiler anzeigen
Das Ergebnis kann bspw. wie folgt sein:
Für die Verwendung einfach Map.DiamondSquare aufrufen, wobei power n entspricht und depth der Tiefe. Der Parameter Random ermöglicht es, einen eigenen Zufallszahlengenerator zu übergeben. Hierbei wird lediglich NextDouble aufgerufen. Wird Nothing übergeben, so wird einfach eine neue Instanz von System.Random verwendet.
Viel Spaß damit!
Viele Grüße
~blaze~
ich habe mich im Rahmen eines Benutzerwunsches dazu bereiterklärt, den Diamond-Square-Algorithmus zu implementieren. Hierbei verwende ich ein iteratives Vorgehen. Es wird ein Raster mit 2^n x 2^n Punkten in festem Abstand verwendet, denen jeweils ein Höhenwert zugeordnet wird, wobei n die Länge einer Seite angibt. tiefe sei hierbei der maximale Ausschlag der Tiefe. Alle Höhenwerte liegen zwischen -tiefe und tiefe.
Das Verfahren ermöglicht bspw. das Generieren von Terrain auf Basis von Zufallszahlen, ohne hierbei hochgradige Abweichungen zwischen zwei einzelnen Punkten zur Folge zu haben.
Die Vorgehensweise ist besonders anschaulich durch die rekursive Vorgehensweise ersichtlich:
Man möchte ein Quadrat mit zufälligen, aber "glatten" Höhenwerten effizient befüllen. Das Quadrat soll eine Seitenlänge, die eine Potenz von 2 darstellt, besitzen, wodurch der Algorithmus weiter vereinfacht wird.
Jedem Paar (x, y) wird hierbei ein Höhenwert zugeordnet, wobei gilt, dass x und y je zwischen 0 und 2^n-1 liegen (jew. inklusive).
Es wird ein Quadrat mit zufällig gesetzten Höhenwerten der Eckpunkte genommen und anschließend folgender Algorithmus ausgeführt:
Das Quadrat wird, sofern die Seitenlänge größer als 0 ist, in 4 gleichgroße Quadrate zerteilt, für die der Algorithmus ebenfalls aufgerufen wird. Nun werden jeweils die ungesetzten fünf Punkte (jeweils die Seitenhalbierenden aller Seiten und der Mittelpunkt des ursprünglichen Quadrats) mit zufälligen Werten befüllt. Die zufälligen Werte sollen nicht zu weit von den Höhenwerten des ursprünglichen Quadrats abweichen, da es sonst zu einer hohen Höhendifferenz zwischen zwei Nachbarn kommen kann. Hierdurch erklärt sich auch das rekursive Vorgehen, denn es bietet sich an, die Tiefenunterschiede durch tiefe/2^i zu beschränken, wodurch solch ein glatter Übergang zwischen zwei Nachbarn möglich ist. Der neu generierte Wert wird daher auf den Mittelwert der Höhenwerte der jeweiligen Quadrateckpunkte aufaddiert und anschließend gespeichert.
VB.NET-Quellcode
- Partial Class Map
- Public Shared Function DiamondSquare(power As Integer, depth As Double, random As Random) As Map
- If power >= 30 Then Throw New ArgumentOutOfRangeException("power", "Unsupported buffer size.")
- If random Is Nothing Then random = New Random()
- Dim nextRandom As Func(Of Double) = Function() MapRandom(random.NextDouble()) * depth
- Dim w As Integer = (1 << power) + 1
- Dim buffer(w * w - 1) As Double
- DiamondSquareHelper(New Context(buffer, w, w), w - 1, nextRandom)
- Return New Map(buffer, w, w)
- End Function
- Private Shared Sub DiamondSquareHelper(context As Context, a As Integer, nextRandom As Func(Of Double))
- Dim v As Integer = a
- Dim d As Integer = 1
- context.SetValue(0, 0, nextRandom())
- context.SetValue(v, 0, nextRandom())
- context.SetValue(0, v, nextRandom())
- context.SetValue(v, v, nextRandom())
- 'v is the edge length of the divided square
- While v > 0
- For i As Integer = 0 To d - 1
- For j As Integer = 0 To d - 1
- Dim x = i * v
- Dim y = j * v
- Dim ul = context.GetValue(x, y)
- Dim ur = context.GetValue((x + v), y)
- Dim ll = context.GetValue(x, (y + v))
- Dim lr = context.GetValue((x + v), (y + v))
- 'set diamond
- '->top center
- context.SetValue(x + v \ 2, y, (ul + ur) / 2 + nextRandom() / d)
- '->left center
- context.SetValue(x, y + v \ 2, (ul + ll) / 2 + nextRandom() / d)
- 'right center
- context.SetValue(x + v, y + v \ 2, (ur + lr) / 2 + nextRandom() / d)
- 'bottom center
- context.SetValue(x + v \ 2, y + v, (ll + lr) / 2 + nextRandom() / d)
- 'set center point
- context.SetValue(x + v \ 2, y + v \ 2, (ul + ur + ll + lr) / 4 + nextRandom() / d)
- Next
- Next
- v \= 2
- d *= 2
- End While
- End Sub
- Private Shared Function MapRandom(random As Double) As Double
- Return 2 * random - 1
- End Function
- Private Structure Context
- Public Width, Height As Integer
- Public Buffer As Double()
- Public Sub SetValue(x As Integer, y As Integer, value As Double)
- Buffer(x + y * Width) = value
- End Sub
- Public Function GetValue(x As Integer, y As Integer) As Double
- Return Buffer(x + y * Width)
- End Function
- Public Sub New(buffer As Double(), width As Integer, height As Integer)
- Me.Buffer = buffer
- Me.Width = width
- Me.Height = height
- End Sub
- End Structure
- End Class
- Partial Public Class Map
- Private Shared ReadOnly Empty As New Map(New Double() {}, 0, 0)
- Private ReadOnly _array As Double()
- Private ReadOnly _width, _height As Integer
- Public ReadOnly Property Width As Integer
- Get
- Return _width
- End Get
- End Property
- Public ReadOnly Property Height As Integer
- Get
- Return _height
- End Get
- End Property
- Private Sub New(array As Double(), width As Integer, height As Integer)
- _array = array
- _width = width
- _height = height
- End Sub
- Public Sub New(width As Integer, height As Integer)
- _array = New Double(width * height - 1) {}
- End Sub
- Default Public Property Value(x As Integer, y As Integer) As Double
- Get
- If x < 0 OrElse x >= _width OrElse y < 0 OrElse y >= _height Then
- Throw New ArgumentException("The specified point is not within bounds.")
- End If
- Return _array(x + y * _height)
- End Get
- Set(value As Double)
- If x < 0 OrElse x >= _width OrElse y < 0 OrElse y >= _height Then
- Throw New ArgumentException("The specified point is not within bounds.")
- End If
- _array(x + y * _height) = value
- End Set
- End Property
- End Class
Das Ergebnis kann bspw. wie folgt sein:
Für die Verwendung einfach Map.DiamondSquare aufrufen, wobei power n entspricht und depth der Tiefe. Der Parameter Random ermöglicht es, einen eigenen Zufallszahlengenerator zu übergeben. Hierbei wird lediglich NextDouble aufgerufen. Wird Nothing übergeben, so wird einfach eine neue Instanz von System.Random verwendet.
Viel Spaß damit!
Viele Grüße
~blaze~
Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „~blaze~“ ()