What makes a good permutation table?

Question

I'm implementing improved Perlin noise. Its key feature for randomisation is the hardcoded permutation table, which gives essentially random but reproducible gradients at the cells of the grid. The permutation table is just a permutation of the integers 0..255, and is usually the following table (copied straight from Perlin's original implementation):

{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};

For reference, a small patch drawn from the noise generated by this table looks like this:

However, I would like the code to be a bit more flexible and allow this table to be reshuffled so that I can create a completely new noise field (instead of just sampling it at a different offset). But not all permutations are equally well shuffled. In the unlikely event that the random permutation is just the sorted array from 0 to 255, the noise would look like this instead:

That's kinda bad. Of course, at a chance of $1$ in $256!$, this is not a case I need to be worried about. But surely, this is not the only permutation that yields very noticeable artefacts. Reverse sorted and almost sorted permutations would likely have the same problems. So how many other permutations are unsuitable? Say the code would be used in a popular game to generate a random world up front, it would still be annoying if every 100,000th generated world would look remotely regular.

So the question is, what exactly makes a good (or a bad) permutation table, and how do I assess the quality of a permutation table programmatically, such that I can reshuffle the table once more in the unlikely event that I roll a "bad" table?

Answer 1

First of all - a number must not occur twice, that is implied since we're talking about permutations. So filling the table with a simple random(255) function won't work.

Secondly, you need to ensure that there are no premature recurrence patterns:

Consider the values 1,2,3,4 - the permutation table 4,3,2,1 is not a very good one because of its short cyclic properties, i.e. 1 -> 4, 4 -> 1. Likewise with 4,2,3,1 or 1,2,3,4. The optimal tables take you all the way through all positions: 3,1,4,2 or 2,4,1,3.

This property becomes increasingly important as you increase the number of dimensions and perform recursive lookups.

However this approach alone may create clusters of too similar values, which may or may not be wanted, which leads me to next point.

Thirdly, When you generate a table with the non cyclic properties, you need to step through remaining unassigned indices in a random manner. When possible constrain the random step distance here to a certain min and max range, e.g. 5..120 to avoid clustered groups of similar values. These numbers are worth experimenting with.

Answer 2

One possibility might be to borrow from the cryptographic community and, in particular, the 8-bit to 8-bit substitution used in the AES/Rijndael cipher. The table and code to generate it can be found on wikipedia.

I'd guess that, in order to generate up to 256 additional tables, you could just do something like:

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

(since the SBox function is quite non-linear)

Having said that, (and please forgive me if I've got some of the details wrong) in a past life I implemented Perlin noise using a relatively simple RNG/Hash function but found the correlation in X/Y/Z due to my simple mapping of 2 or 3 dimensions to a scalar value was problematic. I found that a very simple fix was just to use a CRC, eg. something like

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

Given CRCs intrinsics may be built in to CPU HW, this can be fast approach.