Was macht eine gute Permutationstabelle aus?

Ich implementiere verbessertes Perlin-Rauschen . Das Hauptmerkmal für die Randomisierung ist die fest codierte Permutationstabelle, die im Wesentlichen zufällige, aber reproduzierbare Gradienten an den Zellen des Gitters liefert. Die Permutationstabelle ist nur eine Permutation der ganzen Zahlen 0..255und normalerweise die folgende Tabelle (direkt aus Perlins ursprünglicher Implementierung kopiert):

{151, 160, 137, 91, 90, 15, 131, 13, 201, 95, 96, 53, 194, 233, 7,
225, 140, 36, 103, 30, 69, 142, 8, 99, 37, 240, 21, 10, 23, 190, 6, 148, 247,
120, 234, 75, 0, 26, 197, 62, 94, 252, 219, 203, 117, 35, 11, 32, 57, 177, 33,
88, 237, 149, 56, 87, 174, 20, 125, 136, 171, 168, 68, 175, 74, 165, 71, 134,
139, 48, 27, 166, 77, 146, 158, 231, 83, 111, 229, 122, 60, 211, 133, 230, 220,
105, 92, 41, 55, 46, 245, 40, 244, 102, 143, 54, 65, 25, 63, 161, 1, 216, 80,
73, 209, 76, 132, 187, 208, 89, 18, 169, 200, 196, 135, 130, 116, 188, 159, 86,
164, 100, 109, 198, 173, 186, 3, 64, 52, 217, 226, 250, 124, 123, 5, 202, 38,
147, 118, 126, 255, 82, 85, 212, 207, 206, 59, 227, 47, 16, 58, 17, 182, 189,
28, 42, 223, 183, 170, 213, 119, 248, 152, 2, 44, 154, 163, 70, 221, 153, 101,
155, 167, 43, 172, 9, 129, 22, 39, 253, 19, 98, 108, 110, 79, 113, 224, 232,
178, 185, 112, 104, 218, 246, 97, 228, 251, 34, 242, 193, 238, 210, 144, 12,
191, 179, 162, 241, 81, 51, 145, 235, 249, 14, 239, 107, 49, 192, 214, 31, 181,
199, 106, 157, 184, 84, 204, 176, 115, 121, 50, 45, 127, 4, 150, 254, 138, 236,
205, 93, 222, 114, 67, 29, 24, 72, 243, 141, 128, 195, 78, 66, 215, 61, 156, 180};

Als Referenz sieht ein kleiner Fleck aus dem von dieser Tabelle erzeugten Rauschen folgendermaßen aus:

Ich möchte jedoch, dass der Code etwas flexibler ist und dass diese Tabelle neu gemischt wird, damit ich ein völlig neues Rauschfeld erstellen kann (anstatt es nur mit einem anderen Versatz abzutasten). Aber nicht alle Permutationen werden gleich gut gemischt. In dem unwahrscheinlichen Fall, dass die zufällige Permutation nur das sortierte Array von 0bis ist 255, würde das Rauschen stattdessen so aussehen:

Das ist irgendwie schlecht. Natürlich mit einer Chance von zuDies ist kein Fall, über den ich mir Sorgen machen muss. Dies ist jedoch sicherlich nicht die einzige Permutation, die sehr auffällige Artefakte liefert. Umgekehrt sortierte und fast sortierte Permutationen hätten wahrscheinlich die gleichen Probleme. Wie viele andere Permutationen sind also ungeeignet? Angenommen, der Code würde in einem beliebten Spiel verwendet, um eine zufällige Welt im Voraus zu generieren. Es wäre immer noch ärgerlich, wenn jede 100.000ste generierte Welt aus der Ferne regelmäßig aussehen würde.$1$$256!$

Die Frage ist also, was genau eine gute (oder eine schlechte) Permutationstabelle ausmacht und wie ich die Qualität einer Permutationstabelle programmgesteuert einschätze, damit ich die Tabelle in dem unwahrscheinlichen Fall, dass ich eine "schlechte" würfle, erneut neu mischen kann " Tabelle?

Zuallererst - eine Zahl darf nicht zweimal vorkommen, das ist impliziert, da es sich um Permutationen handelt. Das Füllen der Tabelle mit einer einfachen Zufallsfunktion (255) funktioniert also nicht.

Zweitens müssen Sie sicherstellen, dass keine vorzeitigen Wiederholungsmuster auftreten:

Betrachten Sie die Werte 1,2,3,4 - die Permutationstabelle 4,3,2,1 ist aufgrund ihrer kurzen zyklischen Eigenschaften, dh 1 -> 4, 4 -> 1, nicht sehr gut. Ebenso mit 4,2 3,1 oder 1,2,3,4. Die optimalen Tische führen Sie durch alle Positionen: 3,1,4,2 oder 2,4,1,3.

Diese Eigenschaft wird immer wichtiger, wenn Sie die Anzahl der Dimensionen erhöhen und rekursive Suchvorgänge durchführen.

Dieser Ansatz allein kann jedoch zu Clustern zu ähnlicher Werte führen, die möglicherweise erwünscht sind oder nicht, was mich zum nächsten Punkt führt.

Drittens , wenn Sie eine Tabelle mit den nicht zyklischen Eigenschaften generieren, müssen Sie die verbleibenden nicht zugewiesenen Indizes auf zufällige Weise durchlaufen. Wenn möglich, beschränken Sie den zufälligen Schrittabstand hier auf einen bestimmten Min- und Max-Bereich, z. B. 5..120, um Clustergruppen mit ähnlichen Werten zu vermeiden. Es lohnt sich, mit diesen Zahlen zu experimentieren.

Eine Möglichkeit könnte darin bestehen, Kredite von der kryptografischen Gemeinschaft aufzunehmen, insbesondere die 8-Bit- bis 8-Bit-Substitution, die in der AES / Rijndael-Chiffre verwendet wird. Die Tabelle und der Code zum Generieren finden Sie auf Wikipedia.

Ich würde vermuten, dass Sie, um bis zu 256 zusätzliche Tabellen zu generieren, einfach Folgendes tun könnten:

Func(U8 input, U8 TableNum) = SBox( (TableNum + Sbox(input)) Mod256 )

(da die SBox-Funktion ziemlich nichtlinear ist)

Nachdem ich das gesagt habe (und bitte verzeihen Sie mir, wenn ich einige Details falsch verstanden habe), habe ich in einem früheren Leben Perlin-Rauschen mit einer relativ einfachen RNG / Hash-Funktion implementiert, aber die Korrelation in X / Y / Z aufgrund meiner einfachen gefunden Die Zuordnung von 2 oder 3 Dimensionen zu einem Skalarwert war problematisch. Ich fand, dass eine sehr einfache Lösung darin bestand, nur einen CRC zu verwenden, z. etwas wie

InputToRNGHash = CRC(Z xor CRC( Y xor CRC(X))). 

Angesichts der Tatsache, dass CRCs in CPU HW integriert sein können, kann dies ein schneller Ansatz sein.