Deterministic Randomization

[+Karl G]

I thought I'd create a discussion about this to help me brainstorm this topic, and get good ideas from others.

 

So, I understand that if you give a randomization function a set seed, it will produce the same "random" numbers in the same sequence every time, so e.g. the river in River Raid looks the same every time you play the game. Easy enough.

 

In my case, I want certain features to be the same for a long-running game - e.g. if you see a fountain on a certain level of a certain dungeon, it will be the same kind of fountain every time you visit it (e.g. healing vs poison). If you play again with a new character, the fountain might be different.

 

One thing that would distinguish a different game with a different character would be the chosen character name/gender. So I could presumably use the bytes where this data is stored to seed my random function. My first question would be what would be the best way to combine multiple bytes of data for a single random function seed byte? My first thought would be to EOR all the data bytes together (between 2-4 bytes, depending on name length).

 

My next question would be how to use the random function in a non-linear fashion? In the River Raid example, you are going in one direction, and the random function could be called again and again to produce the same results. In my case, I e.g. want to use a random function to determine the properties of a dungeon feature. I would presumably use the static information about the feature along with my random seed based on the character name to get the same results every time. In my case, this would be the dungeon number (0-7), dungeon level (0-7), and x and y coordinates (0-15, 0-15). So, that's 14 bits of information to identify the dungeon feature. Should I EOR these as two bytes with the seed determined above to get a seed for that single use?

 

Anyway, I'm looking forward to hearing on what others have to say in terms of strategies for producing repeatable pseudorandom numbers with non-linear data. Thanks in advance for any thoughts!

 

 

 

[RevEng]

I think using xor to combine the bytes of a name will skew towards the same five bits being twiddled each round. (less than that with common characters) So you might throw in some shifting of bits for each new character position, to widen the result, when you generate the character seed.

 

The answer to the second part depends on what feature distribution qualities you want. e.g. if you want the same sorts of features within each level, but randomly distributed within the 256 rooms, you could use an 8-bit LFSR seeded with dungeoninfo^roomcoordinate^characterseed.

 

If you really want a real (pseudo) random feature distribution quality, I'd go for a 16-bit LFSR with the dungeoninfo in the top LFSR byte and roomcoordinate^characterseed in the lower byte. Just a bit less work.

 

Of course, nobody has the perfect answer without being in the problem space, which includes how you're extracting features from the result, so you may need to tweak and tinker once you're there.

[explorer]

Pengo (SEGA, arcade 1982) have a LFSR 16 bits, with a period of 8192 values.

 

Pseudo-code:

hl := (seed)
old_l := l
hl := 3 x hl
h := h + old_l
(seed) := hl

; -----------------------------------------------------------------------------
                        .org $2d7c
random:
                        push    bc
                        push    hl

                        ld      hl,(RANDOM)             ; seed
                        ld      b,h                     ; bc = hl
                        ld      c,l
                        add     hl,hl                   ; hl *= 2
                        add     hl,bc                   ; hl += bc (hl := 3*hl)

                        ld      a,c                     ; a = c
                        add     a,h                     ; a += h
                        ld      h,a                     ; h = a (h := h+c = h+old_l)

                        ld      (RANDOM),hl             ; new seed

                        pop     hl
                        pop     bc
                        ret

Pengo take the value of register A for all random values it needs. The first seed is $365A.

 

The 8192 values are perfectly balanced: http://zonadepruebas.com/viewtopic.php?f=115&t=5813&start=20#p77052

 

Edited October 21, 2019 by explorer

[+Karl G]

I guess it should have been obvious that the specifics of the solution depends greatly on the game and the data, but I was wondering if there was any kind of common method to produce repeatable numbers given that I can't just call the same random function over and over again as I could if it were linear data. It sounds like I'm at least on the right track.  Thanks!

[CapitanClassic]

Thomas Jentzsch modified Pitfall! co create 256 unique jungle maps. The LSFR is a modification of a maximal length lsfr that gets the next (2nd, 4th, etc.) pseudo random number. If you instead seeded the algorithm with the character class and name, turned into a single byte by either EORing/checksum the name/class bytes, you would also get 256 rooms in a unique order.

 

 

[+SvOlli]

For calculation a seed from the character name, I would go for a CRC-8 (http://www.6502.org/source/integers/crc-more.html, at bottom) instead of eor, because even with both charsets, numbers, dash and space, you're still using only 64 different characters, that means only six bits out of eight for "controlled entropy". And for the pseudo random number generator, you I'd go for a 16-Bit LFSR and eor both 8-bit values.

[+Karl G]

In my case, I pack the bytes to fit up to 6 5-bit characters and the gender in 4 variables, so sparse bytes aren't an issue, at least. 

[NoLand]

I think, the key is in when to iterate the random number. If you want to use it for procedural generation, iterate it in a controlled fashion from a known seed value (e.g., when entering a room). When you want "true" random, iterate it at every frame from the very beginning (users wont press a button to start a game in the exact millisecond) and/or iterate it at any user input (the exact duration of which will be some of a real world noise as well), e.g., for any frame the button is pressed or there's some other joystick or paddle input. In order to have both for a particular purpose (e.g., character generation), I'd opt for a splash screen and iterating the random number until the user deploys a button or switch to start the game – and by this the actual character generation. If you store this value, you may come back to it whenever you need/like and have the same results for the same seed. Putting this one step further, you might also use some bits of this value (or another random value) to determine any extra iterations between using the value in the LFSR to get some more (pseudo) random out of it. (So in one case, you might iterate the generator 2, 4 and 3 times between use and in another 5, 2 and 3 times, etc., avoiding subsequent values in the series, but still in a controlled manner.)

Edited October 22, 2019 by NoLand