Tiefenkarte mit Diamond Square

    • VB.NET
    • .NET (FX) 3.0–3.5

    Es gibt 5 Antworten in diesem Thema. Der letzte Beitrag () ist von Thorstian.

      Tiefenkarte mit Diamond Square

      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

      VB.NET-Quellcode

      1. Partial Class Map
      3. Public Shared Function DiamondSquare(power As Integer, depth As Double, random As Random) As Map
      4. If power >= 30 Then Throw New ArgumentOutOfRangeException("power", "Unsupported buffer size.")
      5. If random Is Nothing Then random = New Random()
      6. Dim nextRandom As Func(Of Double) = Function() MapRandom(random.NextDouble()) * depth
      8. Dim w As Integer = (1 << power) + 1
      10. Dim buffer(w * w - 1) As Double
      11. DiamondSquareHelper(New Context(buffer, w, w), w - 1, nextRandom)
      13. Return New Map(buffer, w, w)
      14. End Function
      16. Private Shared Sub DiamondSquareHelper(context As Context, a As Integer, nextRandom As Func(Of Double))
      17. Dim v As Integer = a
      18. Dim d As Integer = 1
      20. context.SetValue(0, 0, nextRandom())
      21. context.SetValue(v, 0, nextRandom())
      22. context.SetValue(0, v, nextRandom())
      23. context.SetValue(v, v, nextRandom())
      25. 'v is the edge length of the divided square
      26. While v > 0
      27. For i As Integer = 0 To d - 1
      28. For j As Integer = 0 To d - 1
      29. Dim x = i * v
      30. Dim y = j * v
      31. Dim ul = context.GetValue(x, y)
      32. Dim ur = context.GetValue((x + v), y)
      33. Dim ll = context.GetValue(x, (y + v))
      34. Dim lr = context.GetValue((x + v), (y + v))
      36. 'set diamond
      38. '->top center
      39. context.SetValue(x + v \ 2, y, (ul + ur) / 2 + nextRandom() / d)
      40. '->left center
      41. context.SetValue(x, y + v \ 2, (ul + ll) / 2 + nextRandom() / d)
      42. 'right center
      43. context.SetValue(x + v, y + v \ 2, (ur + lr) / 2 + nextRandom() / d)
      44. 'bottom center
      45. context.SetValue(x + v \ 2, y + v, (ll + lr) / 2 + nextRandom() / d)
      47. 'set center point
      48. context.SetValue(x + v \ 2, y + v \ 2, (ul + ur + ll + lr) / 4 + nextRandom() / d)
      49. Next
      50. Next
      51. v \= 2
      52. d *= 2
      53. End While
      54. End Sub
      56. Private Shared Function MapRandom(random As Double) As Double
      57. Return 2 * random - 1
      58. End Function
      60. Private Structure Context
      61. Public Width, Height As Integer
      62. Public Buffer As Double()
      64. Public Sub SetValue(x As Integer, y As Integer, value As Double)
      65. Buffer(x + y * Width) = value
      66. End Sub
      68. Public Function GetValue(x As Integer, y As Integer) As Double
      69. Return Buffer(x + y * Width)
      70. End Function
      72. Public Sub New(buffer As Double(), width As Integer, height As Integer)
      73. Me.Buffer = buffer
      74. Me.Width = width
      75. Me.Height = height
      76. End Sub
      77. End Structure
      78. End Class
      79. Partial Public Class Map
      81. Private Shared ReadOnly Empty As New Map(New Double() {}, 0, 0)
      83. Private ReadOnly _array As Double()
      84. Private ReadOnly _width, _height As Integer
      86. Public ReadOnly Property Width As Integer
      87. Get
      88. Return _width
      89. End Get
      90. End Property
      92. Public ReadOnly Property Height As Integer
      93. Get
      94. Return _height
      95. End Get
      96. End Property
      98. Private Sub New(array As Double(), width As Integer, height As Integer)
      99. _array = array
      100. _width = width
      101. _height = height
      102. End Sub
      104. Public Sub New(width As Integer, height As Integer)
      105. _array = New Double(width * height - 1) {}
      106. End Sub
      108. Default Public Property Value(x As Integer, y As Integer) As Double
      109. Get
      110. If x < 0 OrElse x >= _width OrElse y < 0 OrElse y >= _height Then
      111. Throw New ArgumentException("The specified point is not within bounds.")
      112. End If
      114. Return _array(x + y * _height)
      115. End Get
      116. Set(value As Double)
      117. If x < 0 OrElse x >= _width OrElse y < 0 OrElse y >= _height Then
      118. Throw New ArgumentException("The specified point is not within bounds.")
      119. End If
      120. _array(x + y * _height) = value
      121. End Set
      122. End Property
      123. 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~“ ()

      Also ich generiere damit ganz komische Grafiken (siehe Anhang). Solche "harten" Übergänge sollten doch nicht generiert werden, oder?
      Aufruf:

      C#-Quellcode

      1. ​ int p = 9;
      2. int s = 1 << p;
      4. Map m = Map.DiamondSquare(p, 0.8, null);
      6. Bitmap b = new Bitmap(s, s);
      7. for (int x = 0; x < s; x++)
      8. {
      9. for (int y = 0; y < s; y++)
      10. {
      11. byte c = (byte)(m[x, y] * 256);
      12. b.SetPixel(x, y, Color.FromArgb(c, c, c));
      13. }
      14. }
      Bilder

      • image.png

        217,2 kB, 512×512, 166 mal angesehen
      Mit freundlichen Grüßen,
      Thunderbolt

      Ahja. Ich wusste gar nicht mal, dass es checked/unchecked gibt ^^
      Also habe ich schnell ein ​checked darumgeschrieben und es fliegt eine OverflowException, weil ein Wert in m -1.8​ beträgt.
      So funktioniert es:

      C#-Quellcode

      1. ​ int power = 9;
      2. double depth = 1;
      4. Map m = Map.DiamondSquare(power, depth, null);
      6. Bitmap b = new Bitmap(m.Width, m.Height);
      7. checked
      8. {
      9. for (int x = 0; x < m.Width; x++)
      10. {
      11. for (int y = 0; y < m.Height; y++)
      12. {
      13. byte c = (byte)Math.Max(Math.Min((m[x, y] + depth) / (2 * depth) * 255, 255), 0);
      14. b.SetPixel(x, y, Color.FromArgb(c, c, c));
      15. }
      16. }
      17. }
      Mit freundlichen Grüßen,
      Thunderbolt

    Facebook
    Telefonspende