Getting a seeded value from a list

[Nobody]

On Mon, 19 Nov 2012 21:45:55 -0800, frednotbob wrote:

> What I'm trying to do is set a persistent state for the levels generated
> by make_map(), so the player can move between floors without generating a
> totally new randomized floor each time.

You need to distinguish between immutable data (e.g. walls) and mutable
data (monsters, treasure). The former can be generated from the seed each
time you enter the level; the latter must be generated the first time then
stored.

If the number of levels is reasonable, you can use a PRNG to generate a
list of random numbers at game start, which are the seeds used to generate
each level.

Alternatively, you can generate a single random "game id" at game start
then generate the seed for each level from a hash of the level number and
the game id.

When it comes to random level generation, a single sequential PRNG isn't
always the best option, as it requires that you always use all of the
generated numbers in the same order, even if you only want a subset of the
level's data. This is particularly significant for large levels.

It's sometimes better to use a hierarchy of PRNGs, where the values
generated by higher-level PRNGs are used as seeds for the lower-level
PRNGs. This way, if you need to generate a subset of the data, you only
need to run the PRNGs for the specific subset, and their ancestors.

E.g. if you want a 256x256 grid of random numbers, you could just generate
65536 random numbers and use them in top-to-bottom, left-to-right order.
But if you only want the bottom-right tile, you still need to generate all
of the preceding numbers to ensure that you get the correct value.

A hierarchical approach would generate 4 numbers which are used as the
seeds for the 4 128x128 quarters. Each quarter uses its seed to generate 4
more numbers for the 4 64x64 quarters. And so on until you get down to a
2x2 region, at which point the 4 numbers generated are the actual values
used.

This way, calculating a single cell only requires 4*log(n) (e.g. 4*8=32)
values, while generating the entire grid only requires 33% more numbers
for the higher levels (1 + 1/4 + 1/16 + 1/64 + ... = 1+1/3).