0
\$\begingroup\$

Generating Simplex noise requires a permutation table for randomisation (e.g. see this question or this example).

In some applications, we need to persist the state of the permutation table. This can be done by creating the table, e.g. using

def permutation_table(seed):
    table_size = 2**10  # arbitrary for this question
    l = range(1, table_size + 1) 

    random.seed(seed) # ensures the same shuffle for a given seed
    random.shuffle(l)
    return l + l  # see shared link why l + l; is a detail

and storing it.

Can we avoid storing the full table by generating the required elements every time they are required?

Specifically, currently I store the table and call it using table[i] (table is a list). Can I avoid storing it by having a function that computes the element i, e.g. get_table_element(seed, i).

I'm aware that cryptography already solved this problem using block cyphers, however, I found it too complex to go deep and implement a block cypher.

Does anyone knows a simple implementation of a block cypher to this problem?

\$\endgroup\$
3
  • \$\begingroup\$ what is the problem of storing it in a table and looking it up ? \$\endgroup\$
    – concept3d
    Commented Nov 10, 2013 at 10:58
  • \$\begingroup\$ As far as understand, memory allocation. E.g. in random map generation, a table can be large. This and the fact that one may need more than one table for a given map, makes this procedure interesting. \$\endgroup\$ Commented Nov 10, 2013 at 11:06
  • \$\begingroup\$ Looking at the code on 6by9.net/simplex-noise-for-c-and-python it looks like the tables are under 1 kbyte. Do you really need one table for each map? I thought the permutation table is shared among all maps. The compiled code is probably more than 1k. \$\endgroup\$
    – amitp
    Commented Nov 10, 2013 at 19:13

1 Answer 1

2
\$\begingroup\$

Rather than using very large table sizes, I would suggest just using a hash function. The permutation table is just a kind of pre-calculated hash function anyway. I don't believe the permutation property (i.e. that there are no collisions within the table size) is required for good simplex noise.

Some hash functions that could do the job are listed here. I've used the first one on that page, Thomas Wang's 32-bit integer hash, quite a bit. I copied its source code below:

uint32_t hash(uint32_t a)
{
    a = (a ^ 61) ^ (a >> 16);
    a = a + (a << 3);
    a = a ^ (a >> 4);
    a = a * 0x27d4eb2d;
    a = a ^ (a >> 15);
    return a;
}

This might even be faster than looking up a value from a large table, if the memory access takes longer than the 10 math operations in the above function. I haven't benchmarked this though. Probably the table stays in cache pretty well when you're generating many noise values.

Also, you can easily incorporate a per-map seed by changing the values passed to the hash function. For instance you can pass (seed * mapHeight + y) * mapWidth + x to generate a different value for each xy coordinate in each map.

\$\endgroup\$
1
  • \$\begingroup\$ I confirm that being or not permutation table is irrelevant. This simplifies the job from the start. Thanks. \$\endgroup\$ Commented Dec 8, 2013 at 9:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .