Brauche hilfe bei Perlin Noise :(

Übersicht BlitzMax, BlitzMax NG Allgemein

Neue Antwort erstellen

 

PhillipK

Betreff: Brauche hilfe bei Perlin Noise :(

 BeitragDo, Sep 15, 2011 13:48
Antworten mit Zitat
Benutzer-Profile anzeigen
Heyho Community Smile

Ich bastel mir grade eine Minecraft ähnliche map und möchte gerne Perlin noise zur erstellung nutzen.

Da ich mich noch nie damit befasst habe, hab ich mir gestern die ganze zeit Hilfe dazu durchgelesen und Tutorials durchgeschaut.
Leider bin ich ein wenig auf dem Holzweg, mein Code klappt nur teilweise.

Die Codesnippets habe ich hieraus übersetzt: How to Use Perlin Noise in your games
Ich glaube, ich habe irgendwo ein-zwei fehler bei der Int-rundung gemacht Sad Eigentlich sollte der Code 1zu1 übertragen werden, allerdings kenne ich mich in den Feinheiten von C++ nicht aus, so zb das hier:
Zitat:
int sample_i0 = (i / samplePeriod) * samplePeriod;


Dazu die bemerkung der Seite:
Zitat:
Note that the line:

Zitat:
int sample_i0 = (i / samplePeriod) * samplePeriod;


is not the same as
Zitat:

int sample_i0 = i;


because the division automatically floors the result to give an integer, so that sample_i0 is the largest multiple of the samplePeriod dmaller than i. For example, if i is 7 and samplePeriod is 3, then sample_i0 is 6.


Den fehler *vermute* ich in der Funktion 'Generate Smooth Noise' - es scheint, als würde das Vertikale Smoothing nicht funktionieren (das Ergebnis sieht schon ein wenig nach Perlin noise aus, aber man erkennt ganz klar Vertikale linien, die vielleicht nicht gesmoothed wurden.. Sad )

BlitzMax: [AUSKLAPPEN] 
SuperStrict

Extern "win32"
   Function QueryPerformanceCounter:Int(out:Long Ptr)
   Function QueryPerformanceFrequency:Int(out:Long Ptr)
End Extern

Type TPerformanceCounter
   Global _supported:Int = False
   Global _freq:Long = 0
   Global _last:Long = 0
   
   Function IsSupported:Int()
      Return _supported
   End Function
   
   Function Init()
      _supported = QueryPerformanceFrequency(Varptr(_freq))
      If _supported Then
         QueryPerformanceCounter(Varptr(_last))
      Else
         _last = MilliSecs()
      EndIf
   End Function
   
   Function GetDelta:Double()
      Local now:Long = 0
      Local delta:Double = 0

      If _supported Then
         QueryPerformanceCounter(Varptr(now))
         delta = (now - _last) / Double(_freq)
      Else
         now = MilliSecs()
         delta = (now - _last) / 1000.0
      EndIf

      _last = now
      Return delta
   End Function
End Type

TPerformanceCounter.Init()

'First step: Ein random array mit breite/höhe erstellen und ihn mit 0 bis 1 füllen.
Function GenerateWhiteNoise:Float[][] (width:Int, Height:Int)
	SeedRnd(0) 'Seed auf 0 zum testen.
	
	Local ret:Float[][]
	ret = ret[..width]

	
	
	For Local x:Int = 0 Until width
		ret[x] = New Float[Height]
		
		For Local y:Int = 0 Until Height
			ret[x][y] = RndFloat()
		'	If RndFloat() < 0.1 And x Mod 10 < 2 And y Mod 10 < 3 Then ret[x][y] = RndFloat()
		Next
	Next
	Return ret
End Function
Function GenerateSmootheNoise:Float[][] (baseNoise:Float[][], octave:Int)
	Local width:Int = Len(baseNoise)
	Local Height:Int = Len(baseNoise[0])
	
	Local smootheNoise:Float[][]
	smootheNoise = smootheNoise[..width]
	
	Local samplePeriod:Int = 1 Shl octave 'calc 2^octave
	Local sampleFrequency:Float = 1.0 / samplePeriod
	
	Local x:Int = 0, y:Int = 0
	Local sample_x0:Int, sample_x1:Int, horizontal_blend:Int
	Local sample_y0:Int, sample_y1:Int, vertical_blend:Float
	
	Local top:Float, bottom:Float
	
	For x = 0 Until width Step 1
		smootheNoise[x] = New Float[Height]
		
		'calc the horizontal sampling idices
		sample_x0 = Int(x / samplePeriod) * samplePeriod
		sample_x1 = Int(sample_x0 + samplePeriod) Mod width 'wrap around
		horizontal_blend = (x - sample_x0) * sampleFrequency
				
		For y = 0 Until Height Step 1
			'calc the vertical sampling indices
			sample_y0 = Int(y / samplePeriod) * samplePeriod
			sample_y1 = Int(sample_y0 + samplePeriod) Mod Height 'wrap around
			vertical_blend = (y - sample_y0) * sampleFrequency
			
			'blend the top two corners
			top = interpolate(baseNoise[sample_x0][sample_y0], baseNoise[sample_x1][sample_y0], horizontal_blend)
			
			'blend the bottom two corners
			bottom = interpolate(baseNoise[sample_x0][sample_y1], baseNoise[sample_x1][sample_y1], horizontal_blend)
			
			'final blend
			
			smootheNoise[x][y] = interpolate(top, bottom, vertical_blend)
			
		Next
	Next
	
	Return smootheNoise
End Function
Function Interpolate1:Float(x0:Float, x1:Float, alpha:Float)
	Return x0 * (1 - alpha) + alpha * x1
End Function
Function Interpolate2:Float(x0:Float, x1:Float, alpha:Float)
	Local a2:Float
	a2 = (1.0 - Cos(alpha * 180)) / 2.0
	Return (x0 * (1.0 - a2) + x1 * a2)
End Function
Function interpolate:Float(x0:Float, x1:Float, alpha:Float)
	Select interMethod
		Case 0 Return Interpolate1(x0, x1, alpha)
		Case 1 Return Interpolate2(x0, x1, alpha)
	End Select
End Function
Function GeneratePerlinNoise:Float[][] (baseNoise:Float[][], octaveCount:Int)
	Local width:Int = Len(baseNoise)
	Local Height:Int = Len(baseNoise[0])
	
	Local smoothnoise:Float[][][]
	smoothNoise = smoothNoise[..octaveCount]
	
	Local persistance:Float = 0.7
	
	'generate smooth noise
	For Local i:Int = 0 Until octaveCount
		smoothNoise[i] = GenerateSmootheNoise(baseNoise, i)
	Next
	
	Local perlinNoise:Float[][]
	perlinNoise = perlinNoise[..width]
	For Local a:Int = 0 Until Height
		perlinNoise[a] = New Float[Height]
	Next
	
	Local amplitude:Float = 1.0
	Local totalAmplitude:Float = 0.0
		
	'blend noise together
	Local x:Int, y:Int, octave:Int
	
	For octave = octaveCount - 1 To 0 Step - 1
		amplitude:*persistance
		totalAmplitude:+amplitude
		
		For x = 0 Until width
		For y = 0 Until Height
			perlinNoise[x][y]:+SmoothNoise[octave][x][y] * amplitude
		Next
		Next
	Next
	
	'normalisation
	For x = 0 Until width
	For y = 0 Until Height
		perlinNoise[x][y]:/totalAmplitude
	Next
	Next
	
	Return perlinNoise
End Function

Graphics(1024, 768)

Global width:Int = 512, Height:Int = 512
Global img:TImage = CreateImage(width, Height)
Global ok:Int = 1
Global last_time:Double = TPerformanceCounter.getDelta()
Global interMethod:Int = 0

MakeNoise()

Function MakeNoise()
	img = CreateImage(width, Height)
	
	Local pix:TPixmap = LockImage(img, 0)
	
	last_time:Double = TPerformanceCounter.getDelta()
	Local noise:Float[][]
	noise = GeneratePerlinNoise(GenerateWhiteNoise(width, Height), ok)

	
	For Local i:Int = 0 Until width
	For Local j:Int = 0 Until Height
		Local col:Int = 255 * noise[i][j]
		'Print col
		pix.WritePixel(i, j, (255 Shl 24) | (col Shl 16) | (col Shl 8) | (col))
	Next
	Next
	
	last_time:Double = TPerformanceCounter.getDelta()
	
	UnlockImage(img, 0)
	
End Function

While Not KeyHit(KEY_ESCAPE)

Cls
SetColor(255, 255, 255)
'DrawRect(0, 0, width + 4, Height + 4)
DrawImage(img, 1, 1)

If KeyHit(KEY_UP) Then
	width = width Shl 1
	Height = Height Shl 1
End If
If KeyHit(KEY_DOWN) Then
	width = width Shr 1
	Height = Height Shr 1
	If width < 32 Then width = 32
	If Height < 32 Then Height = 32
End If
If KeyHit(KEY_ENTER) Then
	interMethod = 1 - interMethod
	MakeNoise()
End If
Local mz:Int = MouseZSpeed()
If mz <> 0 Then
	ok:+mz
	If ok < 0 Then ok = 0
	MakeNoise()
End If
DrawText("interpolate Methode: " + interMethod, 5, GraphicsHeight() - 80)
DrawText("Width: " + width + " - Height: " + Height, 5, GraphicsHeight() - 60)
DrawText("Oktave: " + ok, 5, GraphicsHeight() - 20)
DrawText("Rendertime: " + last_time, 5, GraphicsHeight() - 40)
Flip 1

Wend


Anmerkung:
Ich nutze ein Codesnippet aus dem Code Archiv um mir die Mikro-sekundenzeit anzeigen zu lassen.
Das Type ist win-only :3

Generiert wird ein Perlin-Noise array der dann mit seinen werten als Pixels in eine Pixmap eingetragen wird.
Diese pixmap wird angezeigt.

Größe ist per PFEIL HOCH und PFEIL RUNTER wählbar (exponent von 2 -> standartmäßig ist die höhe/breite auf 512x512)

Interpolationsmethode wechseln geschieht auf ENTER. Interpolate Methode 1 ist Linear, Methode 2 *sollte* Cosine_Interpolate sein.
MausRad stellt die Oktave'n zahl hoch/runter mit der GeneratePerlinNoise() aufgerufen wird.

Das ganze ist nur ein Test, deshalb etwas unsortiert Sad

Sieht jemand meinen Denkfehler?
Ich habe das Thema leider noch nicht genug verstanden, um selbst an den Werten rumzuspielen. Aber solangsam dreh ich durch, nach mehrmaligen durchgehen scheint alles 1zu1 auf Blitzmax übertragen worden zu sein :3

Bitte um hilfe :3

Gruß, PhillipK

Xeres

Moderator

BeitragDo, Sep 15, 2011 14:20
Antworten mit Zitat
Benutzer-Profile anzeigen
Code: [AUSKLAPPEN]
int sample_i0 = (i / samplePeriod) * samplePeriod;

Das funktioniert so auch in BlitzMax, gesetzt dem Fall, samplePeriod ist Float:
BlitzMax: [AUSKLAPPEN] 
SuperStrict

Local i:Int = 7, Period:Float = 3
Local sample:Int = (i / Period) * Period
Print(sample)

Local j:Int = 7, Period2:Int = 3
Local sample2:Int = (j / Period2) * Period2
Print(sample2)

Doku - Type balancing hat Folgendes geschrieben:
BlitzMax decides the result type by balancing the argument types. Both arguments are then converted to the result type before the operator is applied.

The rules governing type balancing are:

  • If either argument is Double, then result is Double
  • else if either argument is Float, then result is Float
  • else if either argument is Long, then result is Long
  • else result is Int


Lange Rede, kurzer Sinn: Du musst dir sicher sein, die richtigen Datentypen zu verwenden, um die richtigen Rundungen zu erreichen.
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Noobody

 BeitragDo, Sep 15, 2011 14:51
Antworten mit Zitat
Benutzer-Profile anzeigen
@Xeres: Eigentlich ist es andersrum - das funktioniert nur, wenn i und samplePeriod beides Integer sind Wink Nur dann wird nämlich bei einer Division abgerundet. Bei Floats würde am Ende wieder i herauskommen.

@PhillipK: Die Abrundungsrechnung ist korrekt, das Problem liegt woanders. vertical_blend und horizontal_blend sind als Integer deklariert (bzw. sind sie gar nicht deklariert und werden deshalb vom Compiler als Integer behandelt), dabei müssten es beides Floats sein. Wenn man diese zwei abändert, funktioniert der Code.

Allerdings müsste man anmerken, dass die von dir verlinkte Seite ein wenig... unkonventionell vorgeht. Perlin Noise beginnt normalerweise mit der Oktave mit der grössten Wellenlänge und addiert mit steigender Oktavenzahl Rauschen mit höherer Frequenz und tieferer Amplitude. Der verlinkte Artikel aber beginnt mit der Oktave mit der kleinsten Wellenlänge und addiert mit steigender Oktavenzahl tiefere Frequenzen obenauf. Auch sonst scheint der Code ein paar seltsame Dinge zu machen (zumindest anders, als ich das bisher kannte); ich würde daher diesen Artikel empfehlen. Ich glaube, so ziemlich jeder, der mal mit Perlin Noise zu tun hatte, ist irgendwann mal auf diese Seite gestossen Razz
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun
 

PhillipK

 BeitragDo, Sep 15, 2011 15:57
Antworten mit Zitat
Benutzer-Profile anzeigen
@Noobody:

Aaah die Seite Very Happy
Gestern habe ich mich bereits an diese Seite rangewagt.
Allerdings hatte ich ohne grobes wissen über Perlin noise echte schwierigkeiten, da durchzusteigen. Zumal mein englisch auch zu wünschen übrig lässt.
Allerdings wollte ich grade (nachdem ich ein bisschen frisch luft schnappen war) nochmal genau diese Seite zur hilfe nehmen *g*

Garnicht deklariert? Bin ich nun bescheuert? :O

Ich habe mir angewöhnt, für codesnippets wo es auf die geschwindigkeit ankommt, jede Variable vor den For schleifen zu deklarieren. Grade wenn es 2 For's verschachtelt sind, gibt es teilweise enorme variablen-initialisierungen. Ich weiß zwar nicht, ob das in Blitzmax nicht evtl vorher unterbunden wird oder ob tatsächlich ständig neuer speicher belegt wird, aber so finde ich persönlich es schöner.

BlitzMax: [AUSKLAPPEN] 
	Local sample_x0:Int, sample_x1:Int, horizontal_blend:Int
	Local sample_y0:Int, sample_y1:Int, vertical_blend:Float


Aber hier habe ich tatsächlich geschlampt. Vertical_blend ist float, horizontal_blend ist int.

Mal schauen, ob ich es auch als "funktionierenden" code hinbekomme, um, falls meine weitere Exkursion ins Thema Perlin Noise heute fehlschlägt, wenigstens ein kleines erfolgserlebnis zu haben Smile

-----------

Mal ne oberflächlichere Frage:

Ich plane grade eine Welt mit etwa 256x256x256 blöcken zu erstellen. (Minecraft Style)
Pro ebene wollte ich den 'kontrast' der 2d Map erhöhen, aber den selben Random-seed verwenden. Sodass ich mir kleinere Berge und täler rendern lassen kann und der Rest ein Solider block ist.

Ist da perlin noise zu empfehlen? Wenn ich es richtig verstanden habe, kann man durch die schicken parameter auch generelle Strukturen nachempfinden, so zb ein eher Hügeligeres Land, oder aber ein flaches tal was zb nur 3-4 Blöcke hoch ist.


Danke schonmal an euch beiden fürs drübergucken Smile
 

PhillipK

 BeitragFr, Sep 16, 2011 12:10
Antworten mit Zitat
Benutzer-Profile anzeigen
Okay mittlerweile Tag 3 des Verzweifelns.

Ich habe nocheinmal den artikel den Noobody vorgeschlagen hat vorgenommen und durchgearbeitet.

Solangsam verstehe ich, was genau bei dem Perlin noise algorythmus funktioniert. Problem an der ganzen geschichte ist nun der Random generator.
Ich habe schon viele ideen durchgeprobiert, um einen eigenen Random-generator zu schreiben. Letzten endes hat nichts funktioniert.

Auf der seite steht folgende funktion:
Code: [AUSKLAPPEN]
  function PerlinNoise_2D(float x, float y)

      total = 0
      p = persistence
      n = Number_Of_Octaves - 1

      loop i from 0 to n

          frequency = 2i
          amplitude = pi

          total = total + InterpolatedNoise_i(x * frequency, y * frequency) * amplitude

      end of i loop

      return total

  end function


wobei
Code: [AUSKLAPPEN]
total = total + InterpolatedNoise_i(x * frequency, y * frequency) * amplitude

je eine eigene funktion pro Oktave aufrufen soll.


Hier ein part den ich nicht ganz verstehe:

Zitat:
Since all the noise functions are essentially the same, except for the values of those three big prime numbers, you can keep the same code, but simply use a different set of prime numbers for each

Der random-generator nimmt 2 werte (x/y) bzw n werte, für n dimensionen und gibt eine nummer zurück.
Diese nummer wird am ende so interpoliert und berechnet, das der Perlin-noise effekt entsteht.

Das erste was mir kopfzerbrechen bereitet: Da die n parameter am ende wie ein Random-seed fungieren, bräuchte ich unendlich viele Prim-zahlen um auch nur ansatzweise Zufällig generierte Noise-arrays zu erhalten.
Meine bisher einzige idee um dem entgegen zu wirken, ist von anfang an einen n dimensionen-array für jede Oktave anzulegen.
Diesen fülle ich mit RndFloat() oder auch mit Rnd(-1,1) - je nachdem was ich benötige.
und die "Rand" funktion gibt mir am ende Array[oktave][x][y]..[n] des arrays zurück.

Da die X-Y-N parameter mit x*frequenzy übergeben werden, und frequenzy immer ein exponent von 2 ist (bzw 1,2,4,8,16,...) und ich, der geschwindigkeit wegen, keine 4048x4048 array-einträge mit randomzahlen füllen will, dachte ich daran, das ich am ende vor der auswertung des parameters einfach wieder DURCH Frequenzy rechne.
Das gibt aber, milde gesagt, bullshit. Oder ich habe es einfach nur falsch durchgerechnet und somit am ende den Randomeffekt ausgehebelt Sad

2te idee wäre, mit den n parametern ein Random-seed zu errechnen und den an blitz zu übergeben. Aber auch das würde nicht ganz sauber funktionieren.
Das einfachste wäre zb, RndSeed( (x shl 16) | (y) ) zu machen, was bei integerzahlen aber direkt wieder zu schwierigkeiten führt Sad

Hat jemand irgendwelche ideen, wie ich einen solchen Random-generator simulieren kann? Oder hat jemand bereits eine solche Perlin Noise funktion geschrieben und einen fix für diese Problem gefunden? :3
-----------

Bevor ich hier aber viel von der Theorie schwafel, werde ich nocheinmal von null anfangen und mir den komplettne Code übersetzen und meine idee einbringen. Ich weiß, es ist nicht gerne gesehen, wenn man nur nach hilfe fragt, ohne eigeninitiative zu zeigen Smile Leider hab ich in einem kleinen Missmutsanfall allen code wieder verworfen.
Dieser folgt also etwa in einer stunde Very Happy

Xeres

Moderator

BeitragFr, Sep 16, 2011 12:45
Antworten mit Zitat
Benutzer-Profile anzeigen
Nunja, ich hab's mal probiert - das Ergebnis hat mich aber auch noch nicht wirklich überzeugt gehabt... Hier mal die 1D Version:
BlitzMax: [AUSKLAPPEN] 
SuperStrict
Rem
	http://freespace.virgin.net/hugo.elias/models/m_perlin.htm

endrem


Global gfx_w:Int = 512, gfx_h:Int = 128
Graphics(gfx_w, gfx_h)
SetClsColor(255, 255, 255)
Cls

SetColor(0, 0, 255)
DrawPerlinNoise_1D(64,, 32) ;Flip;Cls;WaitKey
DrawPerlinNoise_1D(64,, 64) ;Flip;Cls;WaitKey
DrawPerlinNoise_1D(64,, 128) ;Flip;Cls;WaitKey
DrawPerlinNoise_1D(64,, 256)

SetColor(0, 0, 0)
DrawText("DONE", 256, 110)
Flip
WaitKey
End

Function Noise_1D:Float(x:Int, Seed:Int)
	'SeedRnd(x)
	'Return Rnd(-1.0, 1.0)
	'x = x Mod 6
	Seed = Int(Left(String(Seed), 3))
	x = ((Seed + x) * x) / Seed
	x = Int(Left(String(x), 8))
	Return (1.0 - ((x * (x * x * 15731 + 789221) + 1376312589) & $7fffffff) / 1073741824.0)
	'Return ((x * (x * x * 15731 + 789221) + 1376312589) & $7fffffff) / 1073741824.0
End Function

Function SmoothNoise_1D:Float(x:Int, Seed:Int)

	Return Noise_1D(x, Seed) / 2 + Noise_1D(x - 1, Seed) / 4 + Noise_1D(x + 1, Seed) / 4

End Function


Function Cosine_Interpolate_1D:Float(a:Float, b:Float, x:Float)
	Local ft:Float = x * 3.1415927
	Local f:Float = (1 - Cos(ft)) *.5
	
	Return  a*(1-f) + b*f
End Function

Function InterpolatedNoise_1D:Float(x:Int, Seed:Int)
	Local ix:Int = Int(x)
	Local fractional_X:Float = x - ix
	
	Local v1:Float = SmoothNoise_1D(ix, Seed:Int)
	Local v2:Float = SmoothNoise_1D(ix + 1, Seed:Int)
	
	Return Cosine_Interpolate_1D(v1, v2, fractional_X)

End Function


Function PerlinNoise_1D:Float(x:Int, persistence:Float = 0.5, Octaves:Int = 1, Seed:Int = 123456789)
	
	Local total:Float = 0
	For Local i:Int = 0 Until Octaves
		Local frequency:Float = 2.0 ^ i
		Local amplitude:Float = persistence ^ i
		
		total = total + InterpolatedNoise_1D(x * frequency, Seed) * amplitude
	Next
	
	Return total

End Function

Function DrawPerlinNoise_1D:Float(y:Int, persistence:Float = 0.5, Octaves:Int = 1, Seed:Int = 123456789)
	Local width:Int = gfx_w / Octaves
	For Local i:Int = 0 To gfx_w / width

		DrawLine(i * width, MinMax(y + PerlinNoise_1D(i * width) * y, 0, gfx_h - 1), (i + 1) * width, MinMax(y + PerlinNoise_1D((i + 1) * width) * y, 0, 127))

	Next
End Function

Function MinMax:Float(_value:Float, _Min:Float, _Max:Float)
	If _value < _Min Then
		Return _Min
	ElseIf _value > _Max Then
		Return _max
	Else
		Return _value
	EndIf
End Function
Ich glaube, der Zufallssamen in Noise_1D wird etwas eigenwillig behandelt, aber ich hatte bestimmt gute Gründe.

Edit: Mh, ein LookUpTable...
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)
  • Zuletzt bearbeitet von Xeres am Fr, Sep 16, 2011 13:02, insgesamt einmal bearbeitet

Midimaster

 BeitragFr, Sep 16, 2011 12:47
Antworten mit Zitat
Benutzer-Profile anzeigen
stand das nicht auch in dem Artikel, auf den Noobody Dich verwiesen hat?

Die Grundlage neuer zufälliger Generierung sind zufällig ausgewählte Primzahlen:

Zitat:
...Now, you'll want several different random number generators, so I suggest making several copies of the above code, but use slightly different numbers. Those big scarey looking numbers are all prime numbers, so you could just use some other prime numbers of a similar size. So, to make it easy for you to find random numbers, I have written a little program to list prime numbers for you. You can give it a start number and an end number, and it will find all the primes between the two. Source code is also included, so you can easily include it into your own programs to produce a random prime number. Primes.zip...
Gewinner des BCC #53 mit "Gitarrist vs Fussballer" http://www.midimaster.de/downl...ssball.exe
 

PhillipK

 BeitragFr, Sep 16, 2011 13:03
Antworten mit Zitat
Benutzer-Profile anzeigen
@Midimaster: Jap, stand drin.

Die gute seite kann ich mittlerweile fast auswendig ^^

Aber die primzahlen sind das problem. Er/Sie schreibt dort munter fröhlig, das man _nur_ einen andere Primzahl gleicher länge einsetzen muss und man neue werte bekommt.
Ich mein, uäh?

Dieser Generator macht in meinen augen nichts weiter, wie eine Zufallszahl aus X/Y/n parametern zu bestimmen.
Das gleiche kann blitz von haus aus - wenn auch etwas langsamer. Hierfür ist der RndSeed gut - der "samen" aus dem die neue zufallszahl 'wächst'.

Ich glaube nicht umbedingt, das es wirklich sinnvoll ist, pro Oktave ein eigenes Primzahlen-set zusammenzustellen.

1) Hab ich gestern, trotz ausschluss verfahren (allerdings ohne Netz des Irgendwas), einen primzahlen-finder geschrieben, der zahlen zwischen start und ende auf ihre primzahligkeit überprüft und via ausschlussverfahren die rechenzeit vermindert.
als er versucht hat, zwischen 1mrd und 3mrd eine neue primzahl zu finden, hab ich irgendwann nach 10minuten ohne ergebnis das programm gekillt. Primzahlen bei laufzeit finden ist also nicht - nicht ohne tausende integer im ram zu verschwenden um die suche einzugrenzen (stichwort - dieses Netz des Irgendwas zum primzahlen finden Very Happy )

2) Andere Noise-algorythmen verwenden ebenfalls die technik, einen array mit zufallszahlen zu füllen um eben diese zufallszahlengeneratoren zu umgehen. Das ist mit einem Simplen Seedrnd(millisecs()) relativ willkürlich (wie es sein sollte). Allerdings weiß ich nicht, wie ich den array bei mehr oktaven füllen soll - ein 3d Array( [oktave][x][y] würde es tuen, aber da ich die zufallszahlengeneratoren nicht verstehe, weiß ich nicht, ob es eine gewisse abhängigkeit zwischen der zufallszahl aus x und x*frequenzy gibt Sad


Hier mal mein jetziger versuch für einen 1d Perlin noise:
BlitzMax: [AUSKLAPPEN] 
rem
	Ansatz nummer 3, eine Perlin Noise funktion umzusetzen.
	
	Quelle des ansatzes: http://freespace.virgin.net/hugo.elias/models/m_perlin.htm

end rem

Type TPerlin1D
	Field out:Float[]

	Field persistence:Float = 0.5
	Field octaves:Int = 4
		
	Field amplitudeArray:Float[]
	
	Function Create:TPerlin1D(sizeX:Int, octaves:Int, persistence:Float)
		Local perlin:TPerlin1D = New TPerlin1d
		
		'Output anpassen.
		perlin.out = New Float[sizeX]
		perlin.octaves = octaves
		perlin.persistence = persistence
				
		'Amplituden vor-berechnen.
		perlin.amplitudeArray = New Float[perlin.octaves]
		For Local i:Int = 0 Until perlin.octaves
			perlin.amplitudeArray[i] = perlin.persistence ^ i
		Next
		
		'output füllen!
		For i = 0 Until sizeX
			perlin.out[i] = perlin.PerlinNoise(i)
		Next
		
		'rückgabe!
		Return perlin
	End Function
	
	Method PerlinNoise:Float(x:Float)
		Local total:Float = 0.0
		Local freq:Int = 0
		
		
		For Local i:Int = 0 Until Self.octaves
			freq = 1 Shl i 'frequenz ist 2^i !
		
			total = total + Self.interpolatedNoise(x * freq) * Self.amplitudeArray[i]
		Next
		
		Return total
	End Method
	
	Method interpolatedNoise:Float(x:Float)
		Local intX:Int = Int(x)
		
		Local fracX:Float = x - intX 'nachkommastellen von X extrahieren! Möglich aufgrund der int-abrundung.
			
		Return Self.interpolate(Self.SmoothNoise(intX), Self.SmoothNoise(intX + 1), fracX) 'warum nur X+1 ? warum nicht auch X-1 ? 	
		
	End Method
	
	Method SmoothNoise:Float(x:Float)
		Return Self.Noise(x) / 2 + Self.Noise(x - 1) / 4 + Noise(x + 1) / 4
	End Method
	
	Method Noise:Float(seed:Int)
		SeedRnd(CoreSeed + seed)
		Return RndFloat()
	End Method
	
	Method interpolate:Float(x:Float, y:Float, alpha:Float)
		Return Self.Cosine_Interpolate(x, y:Float, alpha)
	End Method
	Method Cosine_Interpolate:Float(x:Float, y:Float, alpha:Float)
		Local f:Float = (1 - Cos(x * 180)) * 0.5
		Return x * (1 - f) + y * f
	End Method
End Type

Global p:Float = 0.7 'persistence!
Global o:Int = 4 'octaves!

Global CoreSeed:Int = MilliSecs() 'wird zusammen mit X als SeedRnd angegeben -> SeedRnd(CoreSeed+x) ! 

Global perlin:TPerlin1D = TPerlin1d.Create(256, o, p)
'perlin.out hat nun meine gewünschten Perlin-höhen.


Graphics(1024, 768)

Global distPerX:Float = 1024.0 / 256.0

While Not KeyHit(KEY_ESCAPE) And Not AppTerminate()
	Cls
	
	'Testen, einstellungen ändern.
	Local rebuild:Int = 0
	If KeyHit(KEY_ENTER) Then
		CoreSeed:Int = MilliSecs() 'neues zufallszahlenset bestimmen :)
	End If
	If KeyDown(KEY_LEFT) Then
		p:-0.001
		rebuild = 1
	ElseIf KeyDown(KEY_RIGHT) Then
		p:+0.001
		rebuild = 1
	EndIf
	If KeyHit(KEY_UP) Then
		o:+1
		rebuild = 1
	ElseIf KeyHit(KEY_DOWN) Then
		o:-1
		rebuild = 1
	End If
	If rebuild = 1 Then
		If p < 0.001 Then p = 0.001
		If o < 1 Then o = 1
		perlin = TPerlin1D.Create(256, o, p)
	End If
	'Visualisieren!
	Local lastY:Float = (perlin.out[0] * 50.0) + 100.0 '100 als standart-offset höhe.
	Local newY:Float
	For Local i:Int = 1 Until Len(perlin.out)
		If perlin.out[i] < - 1 Or perlin.out[i] > 1 Then
			SetColor(255, 0, 0)
		Else
			SetColor(255, 255, 255)
		EndIf
		newY = (perlin.out[i] * 50.0) + 100.0
		DrawLine((i - 1) * distPerX, lastY, i * distPerX, newY)
		lastY = newY
		
		'kleiner test.. 
		
	Next
	
	'Debug ausgabe der einstellungen.
	DrawText("CoreSeed (Drücke ENTER um ihn zu wechseln!): " + CoreSeed, 5, GraphicsHeight() - 51)
	DrawText("Persistence: " + p, 5, GraphicsHeight() - 17)
	DrawText("Octaves: " + o, 5, GraphicsHeight() - 34)
	
	Flip 1
Wend


Da ich allerdings keine ahnung habe, wie ein 1D perlin noise genau aussehen könnte, weiß ich nicht, ob das nun funktioniert hat ^^

Steuerung: Links/rechts um persistence zu ändern
Hoch/Runter um Octaves zu ändern
Enter um einen neuen 'Coreseed' festzulegen (Coreseed= Millisecs())

-----------

@Xeres:

Danke für den Code.

Deins sieht tatsächlich mehr wie ein Perlin Noise aus. Meins hingegen wiederholt sich sichtlich zu oft.

Ich werde mich nun dransetzen und deinen Code analysieren, vielleicht fällt mir der Springende punkt zwischen unseren beiden umsetzungen auf. Wenn ich den gefunden habe, finde ich vielleicht auch den fehler, warum meine 2d umsetzung einfach nur WhiteNoise im willkürlichen rahmen produziert hat Smile

---------

2 Fragen hätte ich allerdings noch:

Wie kann ich meine werte 'normalisieren' ? In meiner 2d umsetzung habe ich eine rot-färbung eingebaut, sobald der Höhen-wert < -1 oder > 1 ist (dh wenn er nichtmehr als 'normal' gilt Very Happy) - dh welchen wert muss ich berechnen um die tatsächliche maximalhöhe zu bestimmen, die am ende rauskommen kann, um meine werte zu normalisieren?

2tens - auf der seite wird geschrieben, das man 'am ende' nurnoch alle Oktaven zusammen 'blenden' muss- wie genau sieht dieses blenden aus?

In meinen augen ist es diese Zeile:
Code: [AUSKLAPPEN]
total = total + InterpolatedNoisei(x * frequency) * amplitude

was auch bedeutet, das ich meine werte normalisieren kann, indem ich am ende
Code: [AUSKLAPPEN]
Return total / octaves_anzahl

zurückgebe. richtig?

Midimaster

 BeitragFr, Sep 16, 2011 13:39
Antworten mit Zitat
Benutzer-Profile anzeigen
ich hab deinen Code nur so überflogen, aber festgestellt, dass die Methode NOISE() den RndSeed immer wieder auf den einmal mit MilliSecs() gefüllten CoreSeed% stellt. Das würde ja heißen, dass die genau gleiche Zufallsreihe wieder von vorne beginnt. Hast Du das bewußt so gewählt, oder liegt hier ein Denkfehler?
Gewinner des BCC #53 mit "Gitarrist vs Fussballer" http://www.midimaster.de/downl...ssball.exe
 

PhillipK

 BeitragFr, Sep 16, 2011 13:49
Antworten mit Zitat
Benutzer-Profile anzeigen
@Midimaster:

Das ist bewusst so.

Später soll das Perlin Noise zeugs mal als "landschaftsgenerierung" diehnen und auch zum festlegen von Ressourcen vorkommen herhalten.

Das ich immer wieder die selbe zufallsreihe nutze hat den sinn, die auswirkungen von Oktaves/Amplitude/Frequenzy zu beobachten. Durch die visualisierung und leichtem verändern fällt das gut auf Smile


Was mir immernoch zu schaffen macht, ist das man bei meiner umsetzung ziemlich eindeutig fraktale erkennen kann. Es sind wiederkehrende muster in der Höhenbildung zu erkennen. Bei xeres' umsetzung ist dem nicht so. Ich erkunde immernoch seinen code (und hab sicherheitshalber direkt mal seine Random-generierung + den seed übernommen, um den code nachzuahmen und den unterschied festzustellen.)
Bis jetzt ist der einzige unterschied den ich erkennen kann, seine MinMax() funktion, die anscheinend das normalisieren (und anpassen an den screen) übernimmt :3

------------

Ich hab grade einmal die Zufallszahlen-generatoren miteinander verglichen.
Hier habe ich auf jedenfall verbesserungsbedarf, denn:

(1) Mit xeres' seinem siehts schon sehr viel besser aus.
(2) Spuckt xeres' seiner zahlen zwischen -1.0 und 1.0 aus, meiner hingegen spuckt werte zwischen 0.0 und 1.0 aus.

Ausserdem wird in xeres' umsetzung die X koordinate durch Octaves bestimmt.
Nachdem ich das mit meiner version verglichen hab, ist mir ein dicker fehler aufgefallen.
Wenn man meinen kram beobachtet, und langsam "octaves" erhöht, sieht es so aus, als würde sich die linie rechts aus dem fenster rausschieben und einfach nur reinzoomen.

Das bedeutet, ich muss das füllen des Höhen array überprüfen und Oktaves kann max. == Länge des arrays sein.
Je höher die Octave, desto höher die frequenz, desto detailreicher ist das ganze.

Wenn ich das nun richtig interpretiere, muss ich für oktave = 1 nur perlin.out[0] und perlin.out[sizeX-1]bestimmen, den rest interpolieren.
für oktave=2 benötige ich.. 3 punkte? die ich bestimme und interpoliere. oder sinds schon 4?
Also entweder bei 0%, 50%,100% vom output oder aber 0%, 33%, 66%, 100% - mhpf, mal schauen <.<

Aber immerhin... dank des codes von Xeres' kann ich nun viel besser analysieren! dankeschön =)
  • Zuletzt bearbeitet von PhillipK am Fr, Sep 16, 2011 14:05, insgesamt einmal bearbeitet

Xeres

Moderator

BeitragFr, Sep 16, 2011 14:01
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich habe grade noch einen relativ neuen Code gefunden: Perlin Noise Type by Bladum
Funktioniert ohne besondere Random-Funktion, aber mit einem Vorberechneten Array. Mal ausprobieren, ob ich damit was intelligenteres hin bekomme.
@PhillipK: Meine Umsetzung ist sehr Fehlerhaft: Wenn du dir die Oktaven ansiehst, wirst du bemerken, das sich die Funktion nur zusammen staucht, aber keine zusätzlichen Verfeinerungen der größeren Funktion entstehen. Insofern bist du näher dran.
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)
 

PhillipK

 BeitragFr, Sep 16, 2011 14:08
Antworten mit Zitat
Benutzer-Profile anzeigen
ugh.

Dein post kam ein wenig zu spät, ich hatte grade die vermutung angestellt, das es genau dieses zusammenstauchen ist, was mir fehlt.
Dreck =)

Okay, vorberechneter array ist schon ne tolle sache - so hatte ich das auch schon 2-3 x gesehen. In dem ersten wurde es als "white noise" bezeichnet - tatsächlich war dies aber nur ein Float[SizeX,SizeY]array mit werten zwischen 0.0 und 1.0, woher die noise-funktion am ende ihre Zufallszahlen erhalten hat.
Allerdings weiß ich noch nicht, ob bei dem random-zahlen generator eine gewisse abhängigkeit zwischen x und x+1 besteht, oder ob das tatsächlich nur randomzahlen sind.

---------------------

Soooo Smile Ich habe nun auch einmal den Noise-array übernommen.
Ein besonderheit ist mir hier aufgefallen:

Da x*frequency übergeben wird, ist der wert immer ein vielfaches von der ursprünglichen größe. Bei einem array mit N oktaven geht es natürlich nicht, das man 4086x4086 felder reserviert, auch wenn man nur ein bruchteil davon nutzt.
In meinem ersten versuch mit einem solchen array hatte ich einfach am ende die aktuelle frequenz wieder dividiert. In dem Code, dessen link Xeres' gepostet hat, wird allerdings eine mod-division vorgenommen um das tatsächliche X zu erhalten.

hier mal der code:

BlitzMax: [AUSKLAPPEN] 
rem
	Ansatz nummer 3, eine Perlin Noise funktion umzusetzen.
	
	Quelle des ansatzes: http://freespace.virgin.net/hugo.elias/models/m_perlin.htm

end rem

Type TPerlin1D
	Field out:Float[]

	Field persistence:Float = 0.5
	Field octaves:Int = 4
		
	Field amplitudeArray:Float[]
	
	Field seed:Int = 123456789
	
	Field tmp:Float[]
	
	Function Create:TPerlin1D(sizeX:Int, octaves:Int, persistence:Float)
		Local perlin:TPerlin1D = New TPerlin1d
		
		SeedRnd(CoreSeed)
		
		'Output anpassen.
		perlin.out = New Float[sizeX]
		perlin.tmp = New Float[sizeX]
		perlin.octaves = octaves
		perlin.persistence = persistence
		
		'tmp Random array füllen! quelle: http://www.blitzbasic.com/codearcs/codearcs.php?code=2852
		For Local i:Int = 0 Until sizeX
			perlin.tmp[i] = (RndFloat() - 0.5) * 2.0 'auf werte zwischen -1.0 und 1.0 bringen! allerdings nur mit halb so hoher genaugkeit - dafür schnell!
		Next
		
		'Amplituden vor-berechnen.
		perlin.amplitudeArray = New Float[perlin.octaves]
		For i = 0 Until perlin.octaves
			perlin.amplitudeArray[i] = perlin.persistence ^ i
		Next
		
		'output füllen!
		For i = 0 Until sizeX
			perlin.out[i] = perlin.PerlinNoise((i*2.0)/perlin.octaves*0.5)
		Next
		
		'tmp array löschen -> speicherplatz sparen!
		perlin.tmp = Null
		
		'rückgabe!
		Return perlin
	End Function
	
	Method PerlinNoise:Float(x:Float)
		Local total:Float = 0.0
		Local freq:Int = 0
		

		For Local i:Int = 0 Until Self.octaves
			freq = 1 Shl i 'frequenz ist 2^i !
		
			total = total + Self.interpolatedNoise(x * freq) * Self.amplitudeArray[i]
		Next

		If total < - 1.0 Then total = -1.0
		If total > 1.0 Then total = 1.0
		
		total = total * 0.5 + 0.5
			
		Return total
	End Method
	
	Method interpolatedNoise:Float(x:Float)
		Local intX:Int = Int(x)
		
		Local fracX:Float = x - intX 'nachkommastellen von X extrahieren! Möglich aufgrund der int-abrundung.
			
		Return Self.interpolate(Self.SmoothNoise(intX), Self.SmoothNoise(intX + 1), fracX) 'warum nur X+1 ? warum nicht auch X-1 ? 	
		
	End Method
	
	Method SmoothNoise:Float(x:Float)
		Local sizeX:Int = Len(Self.tmp)
		Local x1:Int = x Mod sizeX
		Local x2:Int = (x - 1) Mod sizeX
		Local x3:Int = (x + 1) Mod sizex
		
		
		If x1 < 0 Then x1:+sizeX
		If x2 < 0 Then x2:+sizeX
		If x3 < 0 Then x3:+sizeX
	'	If x3 >= sizeX Then x3:-sizeX
		Return Self.Noise(x1) / 2 + Self.Noise(x2) / 4 + Noise(x3) / 4
	End Method
	
	Method Noise:Float(x:Int)
		Return Self.tmp[x]
	End Method
'	Method Noise:Float(seed:Int)
'		SeedRnd(CoreSeed + seed)
'	'	Local ret:Float = RndFloat()
'	'	Print ret
'		Return Rnd(-.99, .99)'ret'RndFloat()
'	End Method
'	Method Noise:Float(x:Int)
'		'SeedRnd(x)
'		'Return Rnd(-1.0, 1.0)
'		'x = x Mod 6
'		'Print "X: " + x
'		Local Seed:Int = Int(Left(String(Self.Seed), 3))
'		x = ((Seed + x) * x) / Seed
'		x = Int(Left(String(x), 8))
'		
'		'Print (1.0 - ((x * (x * x * 15731 + 789221) + 1376312589) & $7fffffff) / 1073741824.0)
'		Return (1.0 - ((x * (x * x * 15731 + 789221) + 1376312589) & $7fffffff) / 1073741824.0)
'		'Return ((x * (x * x * 15731 + 789221) + 1376312589) & $7fffffff) / 1073741824.0
'	End Method

	Method interpolate:Float(x:Float, y:Float, alpha:Float)
	'	Return Self.Cosine_Interpolate(x, y:Float, alpha)
		Return Self.Linear_Interpolate(x, y, alpha)
	End Method
	Method Cosine_Interpolate:Float(x:Float, y:Float, alpha:Float)
		Local f:Float = (1 - Cos(x * 180)) * 0.5
		Return x * (1 - f) + y * f
	End Method
	Method Linear_Interpolate:Float(x:Float, y:Float, alpha:Float)
		Return x * (1 - x) + b * x
	End Method
End Type

Global p:Float = 0.5 'persistence!
Global o:Int = 1 Shl 6 'octaves!

Global CoreSeed:Int = MilliSecs() 'wird zusammen mit X als SeedRnd angegeben -> SeedRnd(CoreSeed+x) ! 

Global perlin:TPerlin1D = TPerlin1d.Create(256, o, p)
'perlin.out hat nun meine gewünschten Perlin-höhen.


Graphics(1024, 768)

Global distPerX:Float = 1024.0 / 256.0

While Not KeyHit(KEY_ESCAPE) And Not AppTerminate()
	Cls
	
	'Testen, einstellungen ändern.
	Local rebuild:Int = 0
	If KeyHit(KEY_ENTER) Then
		CoreSeed:Int = MilliSecs() 'neues zufallszahlenset bestimmen :)
	End If
	If KeyDown(KEY_LEFT) Then
		p:-0.001
		rebuild = 1
	ElseIf KeyDown(KEY_RIGHT) Then
		p:+0.001
		rebuild = 1
	EndIf
	If KeyHit(KEY_UP) Then
		o:+1
		rebuild = 1
	ElseIf KeyHit(KEY_DOWN) Then
		o:-1
		rebuild = 1
	End If
	If rebuild = 1 Then
		If p < 0.001 Then p = 0.001
		If o < 1 Then o = 1
		perlin = TPerlin1D.Create(512, o, p)
	End If
	'Visualisieren!
	Local lastY:Float = (perlin.out[0] * 50.0) + 300.0 '300 als standart-offset höhe.
	Local newY:Float
	For Local i:Int = 1 Until Len(perlin.out)
		If perlin.out[i] < - 1 Or perlin.out[i] > 1 Then
			SetColor(255, 0, 0)
		Else
			SetColor(255, 255, 255)
		EndIf
		newY = (perlin.out[i] * 50.0) + 300.0
		DrawLine((i - 1) * distPerX, lastY, i * distPerX, newY)
		lastY = newY
		
		'kleiner test.. 
		
	Next
	
	'Debug ausgabe der einstellungen.
	DrawText("CoreSeed (Drücke ENTER um ihn zu wechseln!): " + CoreSeed, 5, GraphicsHeight() - 51)
	DrawText("Persistence: " + p, 5, GraphicsHeight() - 17)
	DrawText("Octaves: " + o, 5, GraphicsHeight() - 34)
	
	Flip 1
Wend


Das sieht schon sehr viel besser aus Very Happy
Hier habe ich allerdings die LineareInterpolation angeschaltet. Weiß immer noch nicht recht, ob Cosinus-Interpolation funktioniert, da blitzmax nicht mit dem Bogenmaß arbeitet.

Ich werde nun ersteinmal eine weitere idee einbringen, die ich mal gelesen hab: ein gewisses set an Cosinus-werten für Alpha-werte (für die interpolation) bereitstellen und diese in einem array halten. Grade bei zeitkritischen noise-aufrufen, die teils ne millionen mal interpolieren, könnte das nen ziemlichen speedboost (relativ gesehen^^) geben.

wenn ich das habe, gucke ich mal, wie das ganze in 2d aussieht Very Happy

Noobody

 BeitragFr, Sep 16, 2011 17:07
Antworten mit Zitat
Benutzer-Profile anzeigen
PhillipK hat Folgendes geschrieben:
Da die n parameter am ende wie ein Random-seed fungieren, bräuchte ich unendlich viele Prim-zahlen um auch nur ansatzweise Zufällig generierte Noise-arrays zu erhalten.

Hm was? Du brauchst pro Oktave nur einen Satz Primzahlen. Im Prinzip geht es einfach darum, einen separaten Zufallsgenerator pro Oktave zu nehmen - das muss nicht unbedingt der sein, der dort im Artikel vorgeschlagen wird; man könnte ja auch den BMax-internen nehmen.

So oder so, hier einmal meine Implementation von damals, als ich auf den Artikel zum ersten mal stiess, vielleicht hilft sie dir weiter BlitzMax: [AUSKLAPPEN] 
SuperStrict

Const NOISE_SIZE:Int = 512

Graphics NOISE_SIZE, NOISE_SIZE

Local Pixmap:TPixmap = CreatePixmap(NOISE_SIZE, NOISE_SIZE, PF_RGBA8888)

For Local Y:Int = 0 Until NOISE_SIZE
	For Local X:Int = 0 Until NOISE_SIZE
		Pixmap.WritePixel(X, Y, Int(TNoise2D.PerlinNoise(X, Y, 8, 0.7)*128.0 + 127.0)*$010101)
	Next
Next

DrawPixmap Pixmap, 0, 0

Flip 0
WaitKey
End

Type TNoise1D
	Global PrimeNumbers:Int[][] = [ ..
	[ 15731, 789221, 1376312589, 1073741824 ], ..
	[ 15733, 789227, 1376312657, 1073741827 ], ..
	[ 15737, 789251, 1376312687, 1073741831 ], ..
	[ 15739, 789311, 1376312689, 1073741833 ], ..
	[ 15749, 789323, 1376312753, 1073741839 ], ..
	[ 15761, 789331, 1376312783, 1073741843 ], ..
	[ 15767, 789343, 1376312789, 1073741857 ], ..
	[ 15773, 789367, 1376312629, 1073741891 ] ]
	
	Function PerlinNoise:Float( X:Float, OctaveCount:Int, Persistence:Float )
		Local Result:Float, Frequency:Float = 0.01, Amplitude:Float = 1.0
		
		Local TotalAmplitude:Float
		
		For Local I:Int = 0 Until OctaveCount
			Result :+ InterpolatedNoise( X*Frequency, I )*Amplitude
			
			TotalAmplitude :+ Amplitude
			
			Amplitude :* Persistence
			Frequency :* 2.0
		Next
		
		Return Result/TotalAmplitude
	End Function
	
	Function InterpolatedNoise:Float( X:Float, Octave:Int )
		Local IntX:Int = Int( X )
		
		Return Interpolate( SmoothedNoise( IntX, Octave ), SmoothedNoise( IntX + 1, Octave ), X - IntX )
	End Function
	
	Function SmoothedNoise:Float( X:Int, Octave:Int )
		Return Noise( X, Octave )*0.5 + ( Noise( X - 1, Octave ) + Noise( X + 1, Octave ) )*0.25
	End Function
	
	Function Interpolate:Float( Y1:Float, Y2:Float, Blend:Float )
		Local Cosine:Float = ( 1.0 - Cos( Blend*180.0 ) )*0.5
		
		Return Y1*( 1.0 - Cosine ) + Y2*Cosine
	End Function
	
	Function Noise:Float( Seed:Int, Octave:Int )
		Seed = ( Seed Shl 13 ) ~ Seed
		
		Local Prime:Int[] = PrimeNumbers[ Octave ]
		
		Return 1.0 - ( ( ( Seed*Seed*Prime[ 0 ] + Prime[ 1 ] )*Seed + Prime[ 2 ] ) & $7FFFFFFF )/Float( Prime[ 3 ] )
	End Function
End Type

Type TNoise2D
	Global PrimeNumbers:Int[][] = [ ..
	[ 15731, 789221, 1376312589, 1073741824 ], ..
	[ 15733, 789227, 1376312657, 1073741827 ], ..
	[ 15737, 789251, 1376312687, 1073741831 ], ..
	[ 15739, 789311, 1376312689, 1073741833 ], ..
	[ 15749, 789323, 1376312753, 1073741839 ], ..
	[ 15761, 789331, 1376312783, 1073741843 ], ..
	[ 15767, 789343, 1376312789, 1073741857 ], ..
	[ 15773, 789367, 1376312629, 1073741891 ] ]
	
	Function PerlinNoise:Float( X:Float, Y:Float, OctaveCount:Int, Persistence:Float, Frequency:Float = 0.01 )
		Local Result:Float, Amplitude:Float = 1.0
		
		Local TotalAmplitude:Float
		
		For Local I:Int = 0 Until OctaveCount
			Result :+ InterpolatedNoise( X*Frequency, Y*Frequency, I )*Amplitude
			
			TotalAmplitude :+ Amplitude
			
			Amplitude :* Persistence
			Frequency :* 2.0
		Next
		
		Return Result/TotalAmplitude
	End Function
	
	Function InterpolatedNoise:Float( X:Float, Y:Float, Octave:Int )
		Local IntX:Int = Int( X )
		Local IntY:Int = Int( Y )
		
		Local X1:Float = Interpolate( Noise( IntX, IntY,     Octave ), Noise( IntX + 1, IntY,     Octave ), X - IntX )
		Local X2:Float = Interpolate( Noise( IntX, IntY + 1, Octave ), Noise( IntX + 1, IntY + 1, Octave ), X - IntX )
		
		Return Interpolate( X1, X2, Y - IntY )
	End Function
	
	Function CubicInterpolatedNoise:Float( X:Float, Y:Float, Octave:Int )
		Local IntX:Int = Int( X )
		Local IntY:Int = Int( Y )
		
		Local X0:Float = CubicInterpolate( Noise( IntX - 1, IntY - 1, Octave ), Noise( IntX, IntY - 1, Octave ), Noise( IntX + 1, IntY - 1, Octave ), Noise( IntX + 2, IntY - 1, Octave ), X - IntX )
		Local X1:Float = CubicInterpolate( Noise( IntX - 1, IntY,     Octave ), Noise( IntX, IntY,     Octave ), Noise( IntX + 1, IntY,     Octave ), Noise( IntX + 2, IntY,     Octave ), X - IntX )
		Local X2:Float = CubicInterpolate( Noise( IntX - 1, IntY + 1, Octave ), Noise( IntX, IntY + 1, Octave ), Noise( IntX + 1, IntY + 1, Octave ), Noise( IntX + 2, IntY + 1, Octave ), X - IntX )
		Local X3:Float = CubicInterpolate( Noise( IntX - 1, IntY + 2, Octave ), Noise( IntX, IntY + 2, Octave ), Noise( IntX + 1, IntY + 2, Octave ), Noise( IntX + 2, IntY + 2, Octave ), X - IntX )
		
		Return CubicInterpolate( X0, X1, X2, X3, Y - IntY )
	End Function
	
	Function SmoothedNoise:Float( X:Int, Y:Int, Octave:Int )
		Return Noise( X, Y, Octave )*0.25 + ..
			( Noise( X - 1, Y, Octave ) + Noise( X + 1, Y, Octave ) + Noise( X, Y - 1, Octave ) + Noise( X, Y + 1, Octave ) )*0.125 + ..
			( Noise( X - 1, Y - 1, Octave ) + Noise( X + 1, Y + 1, Octave ) + Noise( X + 1, Y - 1, Octave ) + Noise( X - 1, Y + 1, Octave ) )*0.0625
	End Function
	
	Function Interpolate:Float( Y1:Float, Y2:Float, Blend:Float )
		Local Cosine:Float = ( 1.0 - Cos( Blend*180.0 ) )*0.5
		
		Return Y1*( 1.0 - Cosine ) + Y2*Cosine
	End Function
	
	Function CubicInterpolate:Float( Y0:Float, Y1:Float, Y2:Float, Y3:Float, Blend:Float )
		Local BlendSq:Float = Blend*Blend
		
		Local A0:Float = Y3 - Y2 - Y0 + Y1
		Local A1:Float = Y0 - Y1 - A0
		Local A2:Float = Y2 - Y0
		Local A3:Float = Y1
		
		Return A0*Blend*BlendSq + A1*BlendSq + A2*Blend + A3
	End Function
	
	Function Noise:Float( X:Int, Y:Int, Octave:Int )
		Local Seed:Int = X + Y*57
		Seed = ( Seed Shl 13 ) ~ Seed
		
		Local Prime:Int[] = PrimeNumbers[ Octave ]
		
		Return 1.0 - ( ( ( Seed*Seed*Prime[ 0 ] + Prime[ 1 ] )*Seed + Prime[ 2 ] ) & $7FFFFFFF )/Float( Prime[ 3 ] )
	End Function
End Type

Type TNoise3D
	Global PrimeNumbers:Int[][] = [ ..
	[ 15731, 789221, 1376312589, 1073741824 ], ..
	[ 15733, 789227, 1376312657, 1073741827 ], ..
	[ 15737, 789251, 1376312687, 1073741831 ], ..
	[ 15739, 789311, 1376312689, 1073741833 ], ..
	[ 15749, 789323, 1376312753, 1073741839 ], ..
	[ 15761, 789331, 1376312783, 1073741843 ], ..
	[ 15767, 789343, 1376312789, 1073741857 ], ..
	[ 15773, 789367, 1376312629, 1073741891 ] ]
	
	Global AdditionalSeed:Int
	
	Function PerlinNoise:Float( X:Float, Y:Float, Z:Float, OctaveCount:Int, Persistence:Float, Frequency:Float = 0.01, Seed:Int = 0 )
		AdditionalSeed = Seed
		
		Local Result:Float, Amplitude:Float = 1.0
		
		Local TotalAmplitude:Float
		
		For Local I:Int = 0 Until OctaveCount
			Result :+ CubicInterpolatedNoise( X*Frequency, Y*Frequency, Z*Frequency, I )*Amplitude
			
			TotalAmplitude :+ Amplitude
			
			Amplitude :* Persistence
			Frequency :* 2.0
		Next
		
		Return Result/TotalAmplitude
	End Function
	
	Function CubicInterpolatedNoise:Float( X:Float, Y:Float, Z:Float, Octave:Int )
		Local IntX:Int = Int( X )
		Local IntY:Int = Int( Y )
		Local IntZ:Int = Int( Z )
		
		Local X0 :Float = CubicInterpolate( Noise( IntX - 1, IntY - 1, IntZ - 1, Octave ), Noise( IntX, IntY - 1, IntZ - 1, Octave ), Noise( IntX + 1, IntY - 1, IntZ - 1, Octave ), Noise( IntX + 2, IntY - 1, IntZ - 1, Octave ), X - IntX )
		Local X1 :Float = CubicInterpolate( Noise( IntX - 1, IntY,     IntZ - 1, Octave ), Noise( IntX, IntY,     IntZ - 1, Octave ), Noise( IntX + 1, IntY,     IntZ - 1, Octave ), Noise( IntX + 2, IntY,     IntZ - 1, Octave ), X - IntX )
		Local X2 :Float = CubicInterpolate( Noise( IntX - 1, IntY + 1, IntZ - 1, Octave ), Noise( IntX, IntY + 1, IntZ - 1, Octave ), Noise( IntX + 1, IntY + 1, IntZ - 1, Octave ), Noise( IntX + 2, IntY + 1, IntZ - 1, Octave ), X - IntX )
		Local X3 :Float = CubicInterpolate( Noise( IntX - 1, IntY + 2, IntZ - 1, Octave ), Noise( IntX, IntY + 2, IntZ - 1, Octave ), Noise( IntX + 1, IntY + 2, IntZ - 1, Octave ), Noise( IntX + 2, IntY + 2, IntZ - 1, Octave ), X - IntX )
		
		Local X4 :Float = CubicInterpolate( Noise( IntX - 1, IntY - 1, IntZ    , Octave ), Noise( IntX, IntY - 1, IntZ    , Octave ), Noise( IntX + 1, IntY - 1, IntZ    , Octave ), Noise( IntX + 2, IntY - 1, IntZ    , Octave ), X - IntX )
		Local X5 :Float = CubicInterpolate( Noise( IntX - 1, IntY,     IntZ    , Octave ), Noise( IntX, IntY,     IntZ    , Octave ), Noise( IntX + 1, IntY,     IntZ    , Octave ), Noise( IntX + 2, IntY,     IntZ    , Octave ), X - IntX )
		Local X6 :Float = CubicInterpolate( Noise( IntX - 1, IntY + 1, IntZ    , Octave ), Noise( IntX, IntY + 1, IntZ    , Octave ), Noise( IntX + 1, IntY + 1, IntZ    , Octave ), Noise( IntX + 2, IntY + 1, IntZ    , Octave ), X - IntX )
		Local X7 :Float = CubicInterpolate( Noise( IntX - 1, IntY + 2, IntZ    , Octave ), Noise( IntX, IntY + 2, IntZ    , Octave ), Noise( IntX + 1, IntY + 2, IntZ    , Octave ), Noise( IntX + 2, IntY + 2, IntZ    , Octave ), X - IntX )
		
		Local X8 :Float = CubicInterpolate( Noise( IntX - 1, IntY - 1, IntZ + 1, Octave ), Noise( IntX, IntY - 1, IntZ + 1, Octave ), Noise( IntX + 1, IntY - 1, IntZ + 1, Octave ), Noise( IntX + 2, IntY - 1, IntZ + 1, Octave ), X - IntX )
		Local X9 :Float = CubicInterpolate( Noise( IntX - 1, IntY,     IntZ + 1, Octave ), Noise( IntX, IntY,     IntZ + 1, Octave ), Noise( IntX + 1, IntY,     IntZ + 1, Octave ), Noise( IntX + 2, IntY,     IntZ + 1, Octave ), X - IntX )
		Local X10:Float = CubicInterpolate( Noise( IntX - 1, IntY + 1, IntZ + 1, Octave ), Noise( IntX, IntY + 1, IntZ + 1, Octave ), Noise( IntX + 1, IntY + 1, IntZ + 1, Octave ), Noise( IntX + 2, IntY + 1, IntZ + 1, Octave ), X - IntX )
		Local X11:Float = CubicInterpolate( Noise( IntX - 1, IntY + 2, IntZ + 1, Octave ), Noise( IntX, IntY + 2, IntZ + 1, Octave ), Noise( IntX + 1, IntY + 2, IntZ + 1, Octave ), Noise( IntX + 2, IntY + 2, IntZ + 1, Octave ), X - IntX )
		
		Local X12:Float = CubicInterpolate( Noise( IntX - 1, IntY - 1, IntZ + 2, Octave ), Noise( IntX, IntY - 1, IntZ + 2, Octave ), Noise( IntX + 1, IntY - 1, IntZ + 2, Octave ), Noise( IntX + 2, IntY - 1, IntZ + 2, Octave ), X - IntX )
		Local X13:Float = CubicInterpolate( Noise( IntX - 1, IntY,     IntZ + 2, Octave ), Noise( IntX, IntY,     IntZ + 2, Octave ), Noise( IntX + 1, IntY,     IntZ + 2, Octave ), Noise( IntX + 2, IntY,     IntZ + 2, Octave ), X - IntX )
		Local X14:Float = CubicInterpolate( Noise( IntX - 1, IntY + 1, IntZ + 2, Octave ), Noise( IntX, IntY + 1, IntZ + 2, Octave ), Noise( IntX + 1, IntY + 1, IntZ + 2, Octave ), Noise( IntX + 2, IntY + 1, IntZ + 2, Octave ), X - IntX )
		Local X15:Float = CubicInterpolate( Noise( IntX - 1, IntY + 2, IntZ + 2, Octave ), Noise( IntX, IntY + 2, IntZ + 2, Octave ), Noise( IntX + 1, IntY + 2, IntZ + 2, Octave ), Noise( IntX + 2, IntY + 2, IntZ + 2, Octave ), X - IntX )
		
		Local Y0:Float = CubicInterpolate( X0 , X1 , X2 , X3 , Y - IntY )
		Local Y1:Float = CubicInterpolate( X4 , X5 , X6 , X7 , Y - IntY )
		Local Y2:Float = CubicInterpolate( X8 , X9 , X10, X11, Y - IntY )
		Local Y3:Float = CubicInterpolate( X12, X13, X14, X15, Y - IntY )
		
		Return CubicInterpolate( Y0, Y1, Y2, Y3, Z - IntZ )
	End Function
	
	Function CubicInterpolate:Float( Y0:Float, Y1:Float, Y2:Float, Y3:Float, Blend:Float )
		Local BlendSq:Float = Blend*Blend
		
		Local A0:Float = Y3 - Y2 - Y0 + Y1
		Local A1:Float = Y0 - Y1 - A0
		Local A2:Float = Y2 - Y0
		Local A3:Float = Y1
		
		Return A0*Blend*BlendSq + A1*BlendSq + A2*Blend + A3
	End Function
	
	Function Noise:Float( X:Int, Y:Int, Z:Int, Octave:Int )
		Local Seed:Int = X + Y*57 + Z*3251 + AdditionalSeed
		Seed = ( Seed Shl 13 ) ~ Seed
		
		Local Prime:Int[] = PrimeNumbers[ Octave ]
		
		Return 1.0 - ( ( ( Seed*Seed*Prime[ 0 ] + Prime[ 1 ] )*Seed + Prime[ 2 ] ) & $7FFFFFFF )/Float( Prime[ 3 ] )
	End Function
End Type


Ich verstehe nicht genau, warum du unbedingt auf einem Array mit Zufallszahlen beharrst - auf so eines greift man an sich erst zurück, wenn die Variante mit dem laufend berechnenden Zufallsgenerator funktioniert und man mit dem Zufallsgenerator Geschwindigkeitsprobleme bekommt. Dann ersetzt man den Generator durch ein 1D-Array aus vorausberechneten Zufallszahlen; je grösser es ist, desto weniger wird die Repetition sichtbar. Allerdings würde ich wirklich erst versuchen, deine Perlin-Noise-Funktion zum laufen zu bringen, bevor du Optimierungstricks anwendest.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun
 

PhillipK

 BeitragFr, Sep 16, 2011 17:29
Antworten mit Zitat
Benutzer-Profile anzeigen
Wann läuft sie denn sauber ? Smile

Ich bin zu blöd, wirklich gescheiht zu sagen, ob "DAS" nun wirklich perlin noise ist oder nur zufällig ähnlich aussieht.
Leider bin ich grade durch ein wenig extra arbeit (eine PowerPoint präsentation für die Arbeit meiner Schwester^^) verhindert, deswegen kann ich grade nicht daran weiter werkeln.

Zitat:
Hm was? Du brauchst pro Oktave nur einen Satz Primzahlen. Im Prinzip geht es einfach darum, einen separaten Zufallsgenerator pro Oktave zu nehmen - das muss nicht unbedingt der sein, der dort im Artikel vorgeschlagen wird; man könnte ja auch den BMax-internen nehmen.


Mein einwand auf das "unendlich viele" generatoren bezog sich darauf, das ich im endeffekt maps damit gestalten, füllen und mit biomen ausstatten wollte. Ähnlich wie in minecraft (und nein, es wird kein minecraft clone, dient lediglich als erster test für perlin noise (und mal wieder zum lernen <.< ich tu fast nix anderes oO))
Da bei einem festen Primzahlensatz pro oktave immer die selben zahlen bei rumkommen, ist es im endeffekt nichts zufälliges. Ich denke sogar, ohne es zu wissen, das der Blitzmaxinterne zufallszahlen 'generator' ebenfalls eine ähnliche technik anwendet. Der aktuelle seed wird verrechnet, die werte auf min/max angepasst und ein neuer seed generiert.

Beharren tue ich nicht auf den Zufallszahlen array Very Happy Das war nur die einfachste methode, die mir auf und einfiel, um das blitzmaxinterne Rndzeugs zu nutzen und darauf die PerlinNoise funktion aufzubauen.

In etwa 2-3 stunden kann ich weiter an der 2d umsetzung arbeiten, sobald ich die fertig habe, werde ich mir deinen Code zu herzen nehmen, Noobody! Danke dafür (von anderen Lernt man immernoch am besten, nicht wahr? Smile )

In der zwischenzeit wäre es nett, wenn mir jemand die auswirkungen von den Oktaven und der Persistence erklären könnte ..
Meine jetzige 1d umsetzung scheint, wenn ich das richtig beobachte, indirekt 'reinzuzoomen' und mehr details freizulegen, je größer die Oktave ist, die ich angebe.
Persistence hingegen erhöht den unterschied den die werte aufweisen - Visualisiert nähern sich die punkte dem min/max an (-1 und 1, je nachdem was näher liegt) je höher die persistence ist. Ist das etwa das, was die werte verursachen oder habe ich hier wieder ganz klasse was falsch eingebaut und interpretiert? Smile

Noobody

 BeitragFr, Sep 16, 2011 20:26
Antworten mit Zitat
Benutzer-Profile anzeigen
PhillipK hat Folgendes geschrieben:
Mein einwand auf das "unendlich viele" generatoren bezog sich darauf, das ich im endeffekt maps damit gestalten, füllen und mit biomen ausstatten wollte. Ähnlich wie in minecraft (und nein, es wird kein minecraft clone, dient lediglich als erster test für perlin noise (und mal wieder zum lernen <.< ich tu fast nix anderes oO))
Da bei einem festen Primzahlensatz pro oktave immer die selben zahlen bei rumkommen, ist es im endeffekt nichts zufälliges.


Werde kreativ Wink Die Primzahlen sind nur eine der Methoden, den Output des Generators zu verändern - in meinem geposteten Code hat es in TNoise3D ein Beispiel davon, wie man benutzerdefinierte Parameter auch noch in den random seed einbauen kann. Hier noch schnell auf TNoise2D übertragen, mit kleinem Beispiel BlitzMax: [AUSKLAPPEN] 
SuperStrict

Const NOISE_SIZE:Int = 512

Graphics NOISE_SIZE, NOISE_SIZE

Local Pixmap:TPixmap = CreatePixmap(NOISE_SIZE, NOISE_SIZE, PF_RGBA8888)

Local Seed:Int = MilliSecs()

For Local Y:Int = 0 Until NOISE_SIZE
	For Local X:Int = 0 Until NOISE_SIZE
		Pixmap.WritePixel(X, Y, Int(TNoise2D.PerlinNoise(X, Y, 8, 0.7, 0.01, Seed)*128.0 + 127.0)*$010101)
	Next
Next

DrawPixmap Pixmap, 0, 0

Flip 0
WaitKey
End

Type TNoise1D
	Global PrimeNumbers:Int[][] = [ ..
	[ 15731, 789221, 1376312589, 1073741824 ], ..
	[ 15733, 789227, 1376312657, 1073741827 ], ..
	[ 15737, 789251, 1376312687, 1073741831 ], ..
	[ 15739, 789311, 1376312689, 1073741833 ], ..
	[ 15749, 789323, 1376312753, 1073741839 ], ..
	[ 15761, 789331, 1376312783, 1073741843 ], ..
	[ 15767, 789343, 1376312789, 1073741857 ], ..
	[ 15773, 789367, 1376312629, 1073741891 ] ]
	
	Global AdditionalSeed:Int
	
	Function PerlinNoise:Float( X:Float, OctaveCount:Int, Persistence:Float, Seed:Int = 0 )
		Local Result:Float, Frequency:Float = 0.01, Amplitude:Float = 1.0
		
		AdditionalSeed = Seed
		
		Local TotalAmplitude:Float
		
		For Local I:Int = 0 Until OctaveCount
			Result :+ InterpolatedNoise( X*Frequency, I )*Amplitude
			
			TotalAmplitude :+ Amplitude
			
			Amplitude :* Persistence
			Frequency :* 2.0
		Next
		
		Return Result/TotalAmplitude
	End Function
	
	Function InterpolatedNoise:Float( X:Float, Octave:Int )
		Local IntX:Int = Int( X )
		
		Return Interpolate( SmoothedNoise( IntX, Octave ), SmoothedNoise( IntX + 1, Octave ), X - IntX )
	End Function
	
	Function SmoothedNoise:Float( X:Int, Octave:Int )
		Return Noise( X, Octave )*0.5 + ( Noise( X - 1, Octave ) + Noise( X + 1, Octave ) )*0.25
	End Function
	
	Function Interpolate:Float( Y1:Float, Y2:Float, Blend:Float )
		Local Cosine:Float = ( 1.0 - Cos( Blend*180.0 ) )*0.5
		
		Return Y1*( 1.0 - Cosine ) + Y2*Cosine
	End Function
	
	Function Noise:Float( Seed:Int, Octave:Int )
		Seed :+ AdditionalSeed
		Seed = ( Seed Shl 13 ) ~ Seed
		
		Local Prime:Int[] = PrimeNumbers[ Octave ]
		
		Return 1.0 - ( ( ( Seed*Seed*Prime[ 0 ] + Prime[ 1 ] )*Seed + Prime[ 2 ] ) & $7FFFFFFF )/Float( Prime[ 3 ] )
	End Function
End Type

Type TNoise2D
	Global PrimeNumbers:Int[][] = [ ..
	[ 15731, 789221, 1376312589, 1073741824 ], ..
	[ 15733, 789227, 1376312657, 1073741827 ], ..
	[ 15737, 789251, 1376312687, 1073741831 ], ..
	[ 15739, 789311, 1376312689, 1073741833 ], ..
	[ 15749, 789323, 1376312753, 1073741839 ], ..
	[ 15761, 789331, 1376312783, 1073741843 ], ..
	[ 15767, 789343, 1376312789, 1073741857 ], ..
	[ 15773, 789367, 1376312629, 1073741891 ] ]
	
	Global AdditionalSeed:Int
	
	Function PerlinNoise:Float( X:Float, Y:Float, OctaveCount:Int, Persistence:Float, Frequency:Float = 0.01, Seed:Int = 0 )
		Local Result:Float, Amplitude:Float = 1.0
		
		AdditionalSeed = Seed
		
		Local TotalAmplitude:Float
		
		For Local I:Int = 0 Until OctaveCount
			Result :+ InterpolatedNoise( X*Frequency, Y*Frequency, I )*Amplitude
			
			TotalAmplitude :+ Amplitude
			
			Amplitude :* Persistence
			Frequency :* 2.0
		Next
		
		Return Result/TotalAmplitude
	End Function
	
	Function InterpolatedNoise:Float( X:Float, Y:Float, Octave:Int )
		Local IntX:Int = Int( X )
		Local IntY:Int = Int( Y )
		
		Local X1:Float = Interpolate( Noise( IntX, IntY,     Octave ), Noise( IntX + 1, IntY,     Octave ), X - IntX )
		Local X2:Float = Interpolate( Noise( IntX, IntY + 1, Octave ), Noise( IntX + 1, IntY + 1, Octave ), X - IntX )
		
		Return Interpolate( X1, X2, Y - IntY )
	End Function
	
	Function CubicInterpolatedNoise:Float( X:Float, Y:Float, Octave:Int )
		Local IntX:Int = Int( X )
		Local IntY:Int = Int( Y )
		
		Local X0:Float = CubicInterpolate( Noise( IntX - 1, IntY - 1, Octave ), Noise( IntX, IntY - 1, Octave ), Noise( IntX + 1, IntY - 1, Octave ), Noise( IntX + 2, IntY - 1, Octave ), X - IntX )
		Local X1:Float = CubicInterpolate( Noise( IntX - 1, IntY,     Octave ), Noise( IntX, IntY,     Octave ), Noise( IntX + 1, IntY,     Octave ), Noise( IntX + 2, IntY,     Octave ), X - IntX )
		Local X2:Float = CubicInterpolate( Noise( IntX - 1, IntY + 1, Octave ), Noise( IntX, IntY + 1, Octave ), Noise( IntX + 1, IntY + 1, Octave ), Noise( IntX + 2, IntY + 1, Octave ), X - IntX )
		Local X3:Float = CubicInterpolate( Noise( IntX - 1, IntY + 2, Octave ), Noise( IntX, IntY + 2, Octave ), Noise( IntX + 1, IntY + 2, Octave ), Noise( IntX + 2, IntY + 2, Octave ), X - IntX )
		
		Return CubicInterpolate( X0, X1, X2, X3, Y - IntY )
	End Function
	
	Function SmoothedNoise:Float( X:Int, Y:Int, Octave:Int )
		Return Noise( X, Y, Octave )*0.25 + ..
			( Noise( X - 1, Y, Octave ) + Noise( X + 1, Y, Octave ) + Noise( X, Y - 1, Octave ) + Noise( X, Y + 1, Octave ) )*0.125 + ..
			( Noise( X - 1, Y - 1, Octave ) + Noise( X + 1, Y + 1, Octave ) + Noise( X + 1, Y - 1, Octave ) + Noise( X - 1, Y + 1, Octave ) )*0.0625
	End Function
	
	Function Interpolate:Float( Y1:Float, Y2:Float, Blend:Float )
		Local Cosine:Float = ( 1.0 - Cos( Blend*180.0 ) )*0.5
		
		Return Y1*( 1.0 - Cosine ) + Y2*Cosine
	End Function
	
	Function CubicInterpolate:Float( Y0:Float, Y1:Float, Y2:Float, Y3:Float, Blend:Float )
		Local BlendSq:Float = Blend*Blend
		
		Local A0:Float = Y3 - Y2 - Y0 + Y1
		Local A1:Float = Y0 - Y1 - A0
		Local A2:Float = Y2 - Y0
		Local A3:Float = Y1
		
		Return A0*Blend*BlendSq + A1*BlendSq + A2*Blend + A3
	End Function
	
	Function Noise:Float( X:Int, Y:Int, Octave:Int )
		Local Seed:Int = X + Y*57 + AdditionalSeed
		Seed = ( Seed Shl 13 ) ~ Seed
		
		Local Prime:Int[] = PrimeNumbers[ Octave ]
		
		Return 1.0 - ( ( ( Seed*Seed*Prime[ 0 ] + Prime[ 1 ] )*Seed + Prime[ 2 ] ) & $7FFFFFFF )/Float( Prime[ 3 ] )
	End Function
End Type

Type TNoise3D
	Global PrimeNumbers:Int[][] = [ ..
	[ 15731, 789221, 1376312589, 1073741824 ], ..
	[ 15733, 789227, 1376312657, 1073741827 ], ..
	[ 15737, 789251, 1376312687, 1073741831 ], ..
	[ 15739, 789311, 1376312689, 1073741833 ], ..
	[ 15749, 789323, 1376312753, 1073741839 ], ..
	[ 15761, 789331, 1376312783, 1073741843 ], ..
	[ 15767, 789343, 1376312789, 1073741857 ], ..
	[ 15773, 789367, 1376312629, 1073741891 ] ]
	
	Global AdditionalSeed:Int
	
	Function PerlinNoise:Float( X:Float, Y:Float, Z:Float, OctaveCount:Int, Persistence:Float, Frequency:Float = 0.01, Seed:Int = 0 )
		AdditionalSeed = Seed
		
		Local Result:Float, Amplitude:Float = 1.0
		
		Local TotalAmplitude:Float
		
		For Local I:Int = 0 Until OctaveCount
			Result :+ CubicInterpolatedNoise( X*Frequency, Y*Frequency, Z*Frequency, I )*Amplitude
			
			TotalAmplitude :+ Amplitude
			
			Amplitude :* Persistence
			Frequency :* 2.0
		Next
		
		Return Result/TotalAmplitude
	End Function
	
	Function CubicInterpolatedNoise:Float( X:Float, Y:Float, Z:Float, Octave:Int )
		Local IntX:Int = Int( X )
		Local IntY:Int = Int( Y )
		Local IntZ:Int = Int( Z )
		
		Local X0 :Float = CubicInterpolate( Noise( IntX - 1, IntY - 1, IntZ - 1, Octave ), Noise( IntX, IntY - 1, IntZ - 1, Octave ), Noise( IntX + 1, IntY - 1, IntZ - 1, Octave ), Noise( IntX + 2, IntY - 1, IntZ - 1, Octave ), X - IntX )
		Local X1 :Float = CubicInterpolate( Noise( IntX - 1, IntY,     IntZ - 1, Octave ), Noise( IntX, IntY,     IntZ - 1, Octave ), Noise( IntX + 1, IntY,     IntZ - 1, Octave ), Noise( IntX + 2, IntY,     IntZ - 1, Octave ), X - IntX )
		Local X2 :Float = CubicInterpolate( Noise( IntX - 1, IntY + 1, IntZ - 1, Octave ), Noise( IntX, IntY + 1, IntZ - 1, Octave ), Noise( IntX + 1, IntY + 1, IntZ - 1, Octave ), Noise( IntX + 2, IntY + 1, IntZ - 1, Octave ), X - IntX )
		Local X3 :Float = CubicInterpolate( Noise( IntX - 1, IntY + 2, IntZ - 1, Octave ), Noise( IntX, IntY + 2, IntZ - 1, Octave ), Noise( IntX + 1, IntY + 2, IntZ - 1, Octave ), Noise( IntX + 2, IntY + 2, IntZ - 1, Octave ), X - IntX )
		
		Local X4 :Float = CubicInterpolate( Noise( IntX - 1, IntY - 1, IntZ    , Octave ), Noise( IntX, IntY - 1, IntZ    , Octave ), Noise( IntX + 1, IntY - 1, IntZ    , Octave ), Noise( IntX + 2, IntY - 1, IntZ    , Octave ), X - IntX )
		Local X5 :Float = CubicInterpolate( Noise( IntX - 1, IntY,     IntZ    , Octave ), Noise( IntX, IntY,     IntZ    , Octave ), Noise( IntX + 1, IntY,     IntZ    , Octave ), Noise( IntX + 2, IntY,     IntZ    , Octave ), X - IntX )
		Local X6 :Float = CubicInterpolate( Noise( IntX - 1, IntY + 1, IntZ    , Octave ), Noise( IntX, IntY + 1, IntZ    , Octave ), Noise( IntX + 1, IntY + 1, IntZ    , Octave ), Noise( IntX + 2, IntY + 1, IntZ    , Octave ), X - IntX )
		Local X7 :Float = CubicInterpolate( Noise( IntX - 1, IntY + 2, IntZ    , Octave ), Noise( IntX, IntY + 2, IntZ    , Octave ), Noise( IntX + 1, IntY + 2, IntZ    , Octave ), Noise( IntX + 2, IntY + 2, IntZ    , Octave ), X - IntX )
		
		Local X8 :Float = CubicInterpolate( Noise( IntX - 1, IntY - 1, IntZ + 1, Octave ), Noise( IntX, IntY - 1, IntZ + 1, Octave ), Noise( IntX + 1, IntY - 1, IntZ + 1, Octave ), Noise( IntX + 2, IntY - 1, IntZ + 1, Octave ), X - IntX )
		Local X9 :Float = CubicInterpolate( Noise( IntX - 1, IntY,     IntZ + 1, Octave ), Noise( IntX, IntY,     IntZ + 1, Octave ), Noise( IntX + 1, IntY,     IntZ + 1, Octave ), Noise( IntX + 2, IntY,     IntZ + 1, Octave ), X - IntX )
		Local X10:Float = CubicInterpolate( Noise( IntX - 1, IntY + 1, IntZ + 1, Octave ), Noise( IntX, IntY + 1, IntZ + 1, Octave ), Noise( IntX + 1, IntY + 1, IntZ + 1, Octave ), Noise( IntX + 2, IntY + 1, IntZ + 1, Octave ), X - IntX )
		Local X11:Float = CubicInterpolate( Noise( IntX - 1, IntY + 2, IntZ + 1, Octave ), Noise( IntX, IntY + 2, IntZ + 1, Octave ), Noise( IntX + 1, IntY + 2, IntZ + 1, Octave ), Noise( IntX + 2, IntY + 2, IntZ + 1, Octave ), X - IntX )
		
		Local X12:Float = CubicInterpolate( Noise( IntX - 1, IntY - 1, IntZ + 2, Octave ), Noise( IntX, IntY - 1, IntZ + 2, Octave ), Noise( IntX + 1, IntY - 1, IntZ + 2, Octave ), Noise( IntX + 2, IntY - 1, IntZ + 2, Octave ), X - IntX )
		Local X13:Float = CubicInterpolate( Noise( IntX - 1, IntY,     IntZ + 2, Octave ), Noise( IntX, IntY,     IntZ + 2, Octave ), Noise( IntX + 1, IntY,     IntZ + 2, Octave ), Noise( IntX + 2, IntY,     IntZ + 2, Octave ), X - IntX )
		Local X14:Float = CubicInterpolate( Noise( IntX - 1, IntY + 1, IntZ + 2, Octave ), Noise( IntX, IntY + 1, IntZ + 2, Octave ), Noise( IntX + 1, IntY + 1, IntZ + 2, Octave ), Noise( IntX + 2, IntY + 1, IntZ + 2, Octave ), X - IntX )
		Local X15:Float = CubicInterpolate( Noise( IntX - 1, IntY + 2, IntZ + 2, Octave ), Noise( IntX, IntY + 2, IntZ + 2, Octave ), Noise( IntX + 1, IntY + 2, IntZ + 2, Octave ), Noise( IntX + 2, IntY + 2, IntZ + 2, Octave ), X - IntX )
		
		Local Y0:Float = CubicInterpolate( X0 , X1 , X2 , X3 , Y - IntY )
		Local Y1:Float = CubicInterpolate( X4 , X5 , X6 , X7 , Y - IntY )
		Local Y2:Float = CubicInterpolate( X8 , X9 , X10, X11, Y - IntY )
		Local Y3:Float = CubicInterpolate( X12, X13, X14, X15, Y - IntY )
		
		Return CubicInterpolate( Y0, Y1, Y2, Y3, Z - IntZ )
	End Function
	
	Function CubicInterpolate:Float( Y0:Float, Y1:Float, Y2:Float, Y3:Float, Blend:Float )
		Local BlendSq:Float = Blend*Blend
		
		Local A0:Float = Y3 - Y2 - Y0 + Y1
		Local A1:Float = Y0 - Y1 - A0
		Local A2:Float = Y2 - Y0
		Local A3:Float = Y1
		
		Return A0*Blend*BlendSq + A1*BlendSq + A2*Blend + A3
	End Function
	
	Function Noise:Float( X:Int, Y:Int, Z:Int, Octave:Int )
		Local Seed:Int = X + Y*57 + Z*3251 + AdditionalSeed
		Seed = ( Seed Shl 13 ) ~ Seed
		
		Local Prime:Int[] = PrimeNumbers[ Octave ]
		
		Return 1.0 - ( ( ( Seed*Seed*Prime[ 0 ] + Prime[ 1 ] )*Seed + Prime[ 2 ] ) & $7FFFFFFF )/Float( Prime[ 3 ] )
	End Function
End Type


Im Prinzip muss man nur den Input-Seed des Generators ein wenig permutieren und erhält schon komplett andere Zahlenreihenfolgen, daher kann im Beispielcode auch mit Millisecs() geseedet werden und man erhält jedesmal eine andere Heightmap.

PhilipK hat Folgendes geschrieben:
In der zwischenzeit wäre es nett, wenn mir jemand die auswirkungen von den Oktaven und der Persistence erklären könnte ..
Meine jetzige 1d umsetzung scheint, wenn ich das richtig beobachte, indirekt 'reinzuzoomen' und mehr details freizulegen, je größer die Oktave ist, die ich angebe.
Persistence hingegen erhöht den unterschied den die werte aufweisen - Visualisiert nähern sich die punkte dem min/max an (-1 und 1, je nachdem was näher liegt) je höher die persistence ist. Ist das etwa das, was die werte verursachen oder habe ich hier wieder ganz klasse was falsch eingebaut und interpretiert? Smile

Dein Code läuft da ein wenig seltsam, da er die unkonventionelle Art der ersten von dir verlinkten Seite implementiert Razz Normalerweise läuft es so, dass mit zunehmender Oktavenzahl mehr und mehr Hochfrequenzrauschen aufaddiert wird. Wenn man sich das ganze als Terrain vorstellt, erhält man bei Oktave 1 also "Berge", mit Oktave 2 "Hügel", mit Oktave 3 "Steine", mit Oktave 4 "Kieselsteine" usw.
Persistence steuert dabei, wie stark die Amplitude des Rauschens mit steigender Oktavenzahl abnimmt - die Amplitude wird ja bei steigender Oktave immer wieder mit der Persistence multipliziert. Bei hoher Persistence haben also auch Oktaven mit hoher Frequenz noch starken Einfluss auf das Ergebnis (die Kurve wird "zackig"), bei kleiner Persistence haben hohe Oktaven aber fast keinen Einfluss mehr (die Kurve wird weich).

Ist aber im Prinzip alles auf der Perlin Noise-Seite erklärt (sogar mit Bildern), ansonsten kannst du in meinem Code mal mit den Argumenten für Oktavenzahl und Persistence herumspielen und schauen, was herauskommt. Sich das ganze grafisch zu veranschaulichen hilft (zumindest mir) am meisten Razz

Auf jeden Fall noch viel Erfolg bei deinem Vorhaben.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun
 

PhillipK

 BeitragFr, Sep 16, 2011 20:37
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich habe nun einmal meinen PerlinNoise1D auf 2d übertragen.
Als es wieder nur ein "leicht" gesmoothter whitenoise krams wurde, hab ich mir Noobody's version durchgelesen.

Das dickste was mir aufgefallen ist: Ich verwende Frequenzy anders -
Code: [AUSKLAPPEN]
frequency = 2^i

steht auf der seite.

Noobody verwendet aber als 'grundfrequenz' 0.02 und multipliziert diese pro oktave *2 !

noobody hat aber ausserdem eine wirklich sauber funktionierende version - wie kann das sein? :O Der nächste unterschied ist die normalisierung von Noobody.. und die Prime-number-sets :3
Ach ich verstehs einfach nicht ^^
 

PhillipK

 BeitragSa, Sep 17, 2011 11:22
Antworten mit Zitat
Benutzer-Profile anzeigen
Ahh ich depp =)

entschuldigt, gestern abend hatte ich keine lust mehr.
Tut mir leid, das ich deinen letzten post nimmer gelesen hatte, Noobody Smile


Mit deinem Code habe ich - sogar ungefragt (*g*) eh schon rumgespielt- ich konnte den effekt einbauen den ich mir erhoffe und hab das ganze als kleines, 256frames langes, TImage rendern lassen.

Mittlerweile habe ich anscheinend alle abweichungen von deinem Code zu meinem Code durchgearbeitet. Es bleibt trotzdem dabei - meins produziert no-no's und deiner go-go's :/

Ich werde mich nun dransetzen und wieder einen kompletten rewrite vornehmen.
Diesmal so wie es sein soll - ohne funktion, die mir einen Array generiert, sondern nur das "gibt mir mein Perlinnoise für Koordinate XY!!" Smile

Ps:

Die Art der Randomzahlen generierung ist mir schleierhaft. Es müssen angeblich umbedingt primzahlen sein, aber Noobody verwendet zb 1073741824 -> am ende ist eine 4 - dh eine Grade zahl - dh mindestens durch 2 teilbar - dh keine primzahl!

Und meine erste - recht dumme aber wirksame idee - die Primzahlen zu verändern - ist folgende gewesen:

BlitzMax: [AUSKLAPPEN] 
		SeedRnd(perlin.seed)
		For Local primeSet:Int = 0 Until Len(TPerlin2D.PrimeNumbers)
			For Local index:Int = 0 Until Len(TPerlin2D.PrimeNumbers[primeSet])
			'	TPerlin2D.PrimeNumbers[primeSet][index]:+Rand(-10, 10)
			Next
		Next

(aus meinem abklatsch kopiert, hatte getestet ob es mit deinem Random-generator besser funktioniert! aber auch in deinem code hatte ich es eingebaut - und es hat nach wie vor gute ergebnisse erzielt.)

Wie kann das sein? Smile Was ist das geheimnis hinter den Primzahlen, die scheinbar keine sein müssen? Oder hatte ich bis jetzt einfach nur glück ?




-----------

Edit:

So. Ich habe nun noobodys code analysiert und jeden schritt nachgeahmt. Und siehe da? Es funktioniert.
Komischerweise bin ich der meinung, das es keinerlei änderung zu meinem 3ten Code gegeben hat (habe ich hier allerdings noch nicht gepostet) - ich werde das ganze wohl nochmal genauer analysieren müssen.
Jetzt bin ich erstmal zufrieden und werde mir eine verfeinerung schreiben. Hierzu habe ich mir übelegt, eine Additionsfunktion zu schreiben.
Grundgedanke ist, das es bestimmt toll aussieht, wenn man zb nur jede 2te oktave addiert (und auch berechnet) - so könnte man berge mit Kieslsteinchen ohne Hügel erzeugen - vielleicht ja ganz nützlich.

Ich danke dir recht herzlich für deine gedult, noobody - du fällst mir immer wieder sehr positiv an diesem Board auf :3

Noobody

 BeitragSa, Sep 17, 2011 12:23
Antworten mit Zitat
Benutzer-Profile anzeigen
Oh, das mit der niedrigen Grundfrequenz ist eigentlich ziemlich wichtig, aber tatsächlich nirgends auf der Seite erwähnt. Im Prinzip ist es so, dass die Frequenz viel zu hoch wäre, wenn man tatsächlich 2^i nehmen würde.
Der Grund liegt darin, dass man ja mit Pixelkoordinaten arbeitet und schon bei der ersten Oktave die Frequenz 2^0 = 1 erhielte, was einer neuen zufälligen Zahl pro Pixel entspricht. Das ist natürlich nichts anderes als Ameisenrennen, darum sollte man die Frequenz verringern (in meinem Code ist es 0.01*2^i). Somit erstrecken sich bei niedrigen Oktaven die Einflussbereiche einzelner Zufallszahlen über mehrere dutzend Pixel, womit wir die gewünschten "Berge" erhalten Razz

PhillipK hat Folgendes geschrieben:
Die Art der Randomzahlen generierung ist mir schleierhaft. Es müssen angeblich umbedingt primzahlen sein, aber Noobody verwendet zb 1073741824

Oh, hihi, ich sehe erst jetzt, dass ich da eigentlich einen ziemlichen Fehler im Code habe. Die ersten drei Zahlen im Primzahl-Array müssen tatsächlich Primzahlen sein, aber die letzte sollte eigentlich immer 2^30 sein (1073741824). Der Grund dafür ist, dass, nachdem die Zufallszahl als Integer ausgerechnet wird, noch mit $7FFFFFFF geANDet wird. Damit liegt die Integer-Zufallszahl zwischen 0 und 2^31. Wenn man dann mit 2^30 dividiert, erhält man eine zufällige Fliesskommazahl zwischen 0 und 2.0 - wenn man die dann von 1.0 subtrahiert, erhält man die gewünschte Zufallszahl zwischen -1.0 und 1.0.
Ich habe das wohl damals falsch unterpretiert und die 1073741824 ebenfalls als frei wählbare Primzahl aufgefasst (obwohl sie ja nicht mal eine ist).

Der Generator funktioniert grundsätzlich immer noch, wenn man die anderen Zahlen nicht-prim wählt (d.h. es werden immer noch wild durcheinandergewürfelte Zahlen generiert), allerdings verringert sich die Periodenlänge um einiges, wenn man nicht-prime Zahlen wählt.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun
 

PhillipK

 BeitragSa, Sep 17, 2011 12:53
Antworten mit Zitat
Benutzer-Profile anzeigen
Wieder eine wichtige auskunft! Je größer frequenz desto weniger pixel werden überspannt!
Ziemlich wichtig zu wissen, wenn man (wie ich) einen gewissen einfluss auf die erscheinung der Berge haben möchte.

Ich bin beeindruckt, du kannst die rechnung hinter der Primzahlen-verwürfelung sogar verstehen?
Nun, wenn das auchnoch ein fehler ist, gibt das nacher beim normalisieren fehler und ich habe teilweise schwebende blöcke.
Das kommt auf meine Todoliste zum abändern des Codes Smile

Mich wurmts ziemlich, das mein code nun fast wie eine Kopie wie deiner aussieht, aber nunja. Ich glaube, eine wesentlich andere implementierung wird es wohl nicht geben.

Ich habe es mir noch zum ziel gesetzt, das ganze so schnell wie möglich zu machen.

Meine ideen hierzu sind:

-Aufrufe von Funktionen/methoden verringern - dh eine 2te Version anfertigen wo alles in ein-zwei riesenfunktionen aufgeteilt wird.
-Bei Cosinus-interpolierung bleiben, allerdings einen array vorfertigen, welcher NOISE_SIZE einträge enthält - statt (alpha * 180) aufzurufen, kommt einfach CosinusArray[alpha*180] dran - rein logisch betrachtet, sollte das hinhauen^^
-Rausfinden, wie ich die maximal sichtbare anzahl der oktaven anhand von NOISE_SIZE berechnen kann und diese max-zahl nicht überschreiten, auch wenn Octaves was größeres angibt.
-Generell variablen vermeiden und direkt die rechnugnen zusammentragen (megalangezahlen, ich komme)

Wenn alles klappt, kann ich den speed sicher noch drücken Very Happy Im moment liegt die Noobody-kopie meinerseits bei etwa 38ms für 256x256 als array verpackt.

Ihr dürft gespannt sein =)
 

PhillipK

 BeitragSo, Sep 18, 2011 9:39
Antworten mit Zitat
Benutzer-Profile anzeigen
Eine weitere Zwischenfrage.

Um fix wieder ein Erfolgserlebnis zu haben, hab ich angefangen, den Perlin-code in mein Projekt einzupflegen.
Ich konnte hieraus erfolgreich eine map anzeigen.

Um zu testen, habe ich ersteinmal die höhe auf 16 beschränkt - hierzu habe ich die farben auf eben diese 16 höhenstufen gebrochen.

(Nach dem wrappen auf einen wert von 0 bis 1 (float) : )
Arr[x,y] = Byte(Arr[x,y] * hoehenstufen:int) / Float(hoehenstufen)

Daraus kommen dann (visualisiert) solche bilder:
user posted image

Ist es irgendwie möglich, anhand der parameter (und evtl der Frequenzänderung pro Oktave) den Kontrast zu verändern?
Ich hätte gerne größere Täler, aber dafür Steilere Berge- sprich das was nun dunkel grau ist soll "mehr" werden, dafür aber stark abfallend weiß->hellgrau->grau für die Berge.

meine idee hierzu wäre, rauszufinden, welche Oktave eben diese weißen "berge" berechnet und diese evtl doppelt zu blenden. Nachteil wäre aber, das damit wahrscheinlich einfach nur die 'helligkeit' des gesamten bildes angehoben würde Sad

Also vermute ich, das es sehr wohl machbar ist, aber wahrscheinlich eher beim Interpolieren? Smile

EDIT:

Image-link ausgebessert. Ich idiot hab die Galerie-regeln missachtet Smile
Gleichzeitig ist dies wieder eine weitere Version meiner aktuellen fortschritte. Das problem ist allerdings immernochnicht behoben.

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Allgemein

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group