Boulder Dash Forum

Posted: **Fri Jul 10, 2020 10:39 am**

Sometimes, you don't want any of those properties. That's why Crazy Dream 10 got an optional alternative random number generator, which is used in some caves. Speed should be very similar. If you want to analyze that as well, here is the code, which shouldn't be too hard to implement in any existing Boulder Dash engine, if you wish to experiment with it:

Code: Select all

get_predictable_random_number_32_bit:
        lda random_seed2
        asl
        asl
        eor random_seed2
        asl
        eor random_seed2
        asl
        asl
        eor random_seed2
        asl
        rol random_seed1
        rol random_seed2
        lda random_seed4
        asl
        eor random_seed4
        asl
        asl
        ror random_seed3
        rol random_seed4
        lda random_seed1
        eor random_seed3
        rts

And this is the original Boulder Dash random number generator:

Code: Select all

get_predictable_random_number_c64:
        lda random_seed2
        ror
        ror
        and #$80
        sta random_seed3
        lda random_seed1
        ror
        and #$7f
        sta random_seed4
        lda random_seed1
        ror
        ror
        and #$80
        clc
        adc random_seed1
        adc #$13
        sta random_seed1
        lda random_seed2
        adc random_seed3
        adc random_seed4
        sta random_seed2
        rts

I set the seed with:

Code: Select all

set_seeds:
        sta random_seed1
        sta random_seed3
        sta random_seed4
        bne :+
        inc random_seed3
:       lda #$00
        sta random_seed2
        rts

Of course, random_seed3 and random_seed4 don't have to be initialized with original C64 random, but since there is no need to have a separate initiator for them, I used that for both.
The bne is only there because I realized that the random numbers don't work when all bytes are zero, but I already had designed some caves by then, which would be all different without that bne.

Posted: **Fri Jul 10, 2020 2:05 pm**

Thanks Logicdeluxe!
To be honest, I have no experience with C64 code, but perhaps for others it is very useful!

I did nevertheless an analysis of the original PRNG (= pseudo-random number generator). I wanted to understand how this PRNG works, so I have translated the various binary operations into mathematical expressions which I'm more familiar with. In this post I'm going to share these steps.

I took the C code from the following website as the basis: http://www.elmerproductions.com/sp/pete ... %20numbers.
After cleaning up comments, the code is as follows:

Code: Select all

void NextRandom(int *RandSeed1,int *RandSeed2)
{
    short TempRand1;
    short TempRand2;
    short carry;
    short result;
    TempRand1 = (*RandSeed1 & 0x0001) * 0x0080;
    TempRand2 = (*RandSeed2 >> 1) & 0x007F;
    result = (*RandSeed2) + (*RandSeed2 & 0x0001) * 0x0080;
    carry = (result > 0x00FF);
    result = result & 0x00FF;
    result = result + carry + 0x13;
    carry = (result > 0x00FF);
    *RandSeed2 = result & 0x00FF;
    result = *RandSeed1 + carry + TempRand1;
    carry = (result > 0x00FF);
    result = result & 0x00FF;
    result = result + carry + TempRand2;
    *RandSeed1 = result & 0x00FF;
}

As you can see the function has two input variables *RandSeed1 and *RandSeed2. Within each call, new values are generated for both variables *RandSeed1 and *RandSeed2. Both numbers are always integers and between 0 and 255.

First a summary how this function is used to generate random BD cave maps:
- The map is generated row-by-row from left to right and from top to bottom. The top line is skipped as it's always filled with steelwall. The left and right borders are not skipped, even though they are eventually filled with steelwall.
- For each position on the map a number is drawn by calling the above function. The resulting value of *RandSeed1 is used.
- Next, this number is compared with the filling rules of the particular cave. For example, for BD1 Cave A, the rule is: SPACE 60, BOULDER 50, DIAMOND 9. If the drawn number is <9, a diamond will be placed. If it is >=9 but <50, a boulder is placed, If it is >=50 but <60, empty space is placed. If it is >=60, then the default dirt is placed.
- For the first draw, the input value *RandSeed1 is 0, and the input value of *RandSeed2 is the seed value for the particular cave/level. For example, for BD1 Cave A, the values for the 5 levels are: 10, 11, 12, 13, 14.

As an example, for level 1 of BD1 Cave A, the first call is with arguments (0, 10). This results in (5, 29). Since 5<9 a diamond is placed at the upper-left corner (however, this position is covered by steelwall in the end). The second call is then with arguments (5, 29) which gives (147, 176). Since 147 is >=60, a piece of dirt is placed in the first visible corner of the cave. This way the full cave is filled.

I will now explain what the NextRandom function does by examining it line by line and translate the code into mathematical expressions.

We will denote *RandSeed1 seed by S_1 and *RandSeed2 by S_2.

Code: Select all

    short TempRand1;
    short TempRand2;
    short carry;
    short result;

This is just a declaration of help variables.

Code: Select all

    TempRand1 = (*RandSeed1 & 0x0001) * 0x0080;

Here, & is the Bitwise AND operator. This compares the binary expression of two numbers bit-by-bit. If both bits are 1, the resulting number also has 1 as the corresponding bit, otherwise 0. In this case, S_1 is compared with 0x0001, which is hexadecimal notation for the decimal number 1. So, in binary notation, S_1 is compared with 0000001, which implies that the first 7 bits are always 0 and the last bit is 0 when S_1 is even and 1 when S_1 is odd.
Next, this 0 or 1 is multiplied by 0x0080, which is hexadecimal for 128 (which is half of 256, the maximum olf the range of numbers we draw from).
So, to put it simply, TempRand1 equals 128 if S_1 is odd and 0 if S_1 is even. I'd like to denote this as follows:

TR_1 := 128[S_1 odd]

Code: Select all

    TempRand2 = (*RandSeed2 >> 1) & 0x007F;

The >> 1 means "shift all bits 1 position to the right and add a leading zero to the left". For example for 00000011 (=3) this gives 00000001 (=1). It is easy to see that applying this operator on S_2 is equivalent to floor(S_2 / 2), in other words: divide S_2 by 2 and round down the result.
The & 0x007F is again a Bitwise AND, this time comparing with 01111111 (=127). However, since the >> operation already guarantees that the result is at most 127, this &-operation actually does not make any difference! Thus:

TR_2 := floor(S_2 / 2)

Code: Select all

    result = (*RandSeed2) + (*RandSeed2 & 0x0001) * 0x0080;

Like the TR_1 calculation, this involves a check on even/oddness and multiplication by 128:

R_1 := S_2 + 128[S_2 odd]

(Because there are more "result" variables, I'm adding a number to each R-variable.)

Code: Select all

    carry = (result > 0x00FF);

This is an expression which evaluates to 1 when the expression between the brackets is true, and to 0 otherwise. It checks whether result is bigger than 0x00FF (=255). If that's the case it falls outside the feasible 0-255 range.

C_1 := 1[R_1 > 255]

(Also for "carry" there will be more C-variables.)

Code: Select all

    result = result & 0x00FF;

This applies the Bitwise AND with 11111111. This is equivalent to performing a modulo opertation with modulus 256. If the value of "result" is outside the range (which is also checked in the previous statement), it is taken modulo 256, which ensures that result is always in the 0-255 range.
Examples:
0 mod 256 = 0
1 mod 256 = 1
...
254 mod 256 = 254
255 mod 256 = 255
256 mod 256 = 0
257 mod 256 = 1
... (etc)

The formula thus becomes:

R_2 := R_1 mod 256

Code: Select all

    result = result + carry + 0x13;

The number 0x13 (=19) and C_1 is added:

R_3 := R_2 + C_1 + 19

Code: Select all

    carry = (result > 0x00FF);

C_2 := 1[R_3 > 255]

Code: Select all

    *RandSeed2 = result & 0x00FF;

S_2 := R_3 mod 256

Code: Select all

    result = *RandSeed1 + carry + TempRand1;

R_4 := S_1 + C_2 + TR_1

Code: Select all

    carry = (result > 0x00FF);

C_3 := 1[R_4 > 255]

Code: Select all

    result = result & 0x00FF;

R_5 := R_4 mod 256

Code: Select all

    result = result + carry + TempRand2;

R_6 := R_5 + C_3 + TR_2

Code: Select all

    *RandSeed1 = result & 0x00FF;

S_1 := R_6 mod 256

Taking all these calculations together, first note that the S_2 sequence does not depend on the values of S_1. By combining the above formulas, S_2 is effectively calculated by the following recursive formula:

S_2 := (S_2 + 128[S_2 odd] + 19 + C_1) mod 256

In short: S_2 moves 19 steps when it's even and 128+19=147 steps when it's odd. Plus possible one extra depending on C_1. The extra C_1 ensures that the sequence isn't just alternating even/odd.

The input value of S_2 is used in the formula for S_1. Taking the above calculations for S_1 together, this gives:

S_1 := (S_1 + 128[S_1 odd] + floor(S_2 / 2) + C_2 + C_3) mod 256

Here, only the terms floor(S_2 / 2) and C_2 depend on S_2. So the value of S_1 shifts with a value between 0 and 127 depending on S_2. If it is odd, it shifts with 128 more steps. This way, big shifts are possible.
I guess, the extra bits C_2 and C_3 are there for some extra unpredictability, and of course, to mix the even/oddness.

Now that the formulas for both seed values have been written out mathematically, this gives perhaps some possibilities to explain some typical patterns in generated cave maps!

Posted: **Fri Jul 10, 2020 4:55 pm**

Wow, I didn't know that a randomizing formula could be that simple!

I got the first explanation! As I worte before, it happens often that two consecutive seeds (i.e. S_2 values) give very similar cave maps. After just a quick look, we see now that the S_1 output does not depend on the parity (i.e. even-/oddness) of S_2!
Well, on the other hand the S_2 output does depend on this parity, so after two draws, S_1 is indirectly influenced by it as well. Still, this has to be the main reason, it just needs to be investigated further!

EDIT For example, seeds 254 and 255 create very similar cave C maps, but there are small differences scattered around the whole map. So i don't think that these seeds actually collide - it's more that they always stay very close together, even after hundreds of draws! I wonder how this happens - I think that the terms "+128 if S_1/2 is odd" were included to avoid exactly that

Posted: **Fri Jul 10, 2020 6:58 pm**

Let me add the concrete rules for C_1/2/3 because they aren't that complicated:
C_1=1 exactly if S_2 is odd and >128.
C_2=1 exactly if S_2 is even and >=238
C_3=1 exactly if S_1 is odd and >128, or if S_1=127 and C_1=1.

Posted: **Fri Jul 10, 2020 10:27 pm**

Dustin wrote:Let me add the concrete rules for C_1/2/3 because they aren't that complicated:...

Great! That really helps too!

Dustin wrote:As I worte before, it happens often that two consecutive seeds (i.e. S_2 values) give very similar cave maps.

Well, I have dived into this issue too.

Until now, I remember three of such pairs have been mentioned: 100/101, 160/161 and 254/255.

Note that for these pairs, the resulting maps are not identical after some point, but rather very similar with a few differences here and there.

Nesdori already gave part of the explanation (at Krissz' site):

I checked 160/161. At first both seeds are off but after a few calls there's pattern: seed2 is always the same in both and seed1 of off by 2 for the rest of the randomfill, like this (a snippet from a middle of the fill):

160_s1 160_s2 : 161_s1 161_s2

...
144 150 : 146 150
219 169 : 221 169
176 61 : 178 61
206 208 : 208 208
54 227 : 56 227
167 119 : 169 119
100 10 : 102 10
...

Because seed1 if always off just by 2 it may look with some densities that the values are equal but they aren't

Indeed, this gives the reason why the maps are similar but not identical at some point: the seed1 is off by 2 so at most locations this would give the same item on the map, except, for example, when the rule BOULDER 60 applies and the seed1 is 59 and 61. Then we get a boulder in one map and dirt in the other map.

Now, in my view, there are 2 phenomena that ask for further explanation:

1. How does seed2 sync at some point?

In the case of 160/161, seed2 syncs very early, after the 6th draw:
- Start seed 160: seed2 moves from 129 to 21.
- Start seed 161: seed2 moves from 2 to 21.
These moves are easy to check by the above formulas.

By itself, it is not uncommon that two different seed2 values give the same resulting next seed2 value. But it is coincedence (I think) that for these two start seeds it happens at the same time (i.e. after draw no. 6).

2. How could seed1 stay off by 2 for the rest of the random fill?

In the case of 160/161, this pattern starts after the 74th draw:
- Start seed 160: (seed1, seed2) moves from (151, 35) to (41, 182).
- Start seed 161: (seed1, seed2) moves from (26, 35) to (43, 182).
Again, these moves are easily checked by using the above formulas.

Now, seed1 is off by 2, but why does it stay like that?

Well, remember the formula:

S_1 := (S_1 + 128[S_1 odd] + floor(S_2 / 2) + C_2 + C_3) mod 256

Since seed1 is off by 2, either both values are even or both are odd. So the term 128[S_1 odd] won't break the pattern. Also terms floor(S_2 / 2) and C_2 won't break the pattern as they only depend on S_2, which is already the same.
What's left is C_3. When is this term different? This can only be the case when S_1 + 128[S_1 odd] + C2 is <= 255 for the first sequence and >255 for the second sequence. However, this does not happen during the rest of the filling.

I also checked the pairs 100/101 and 254/255.
In these pairs, seed2 gets synced at some point on the first row of the map. The seed1 behaviour is slightly different:
- For 100/101, for about 1/3 part of the cave map, seed1 is off by 4, which is a few times temporatily broken due to a different C_3 value. Then, for about 1/3 of the map, seed1 is off by 2 (again temporarily broken a few times). And for the last 1/3 of the map, seed1 is off by 4 again.
- For 254/255, seed1 is off by 4 for about 2/5 of the map, then, after 4 unsynced draws, seed1 is off by 2 for the remainder of the map.

I would expect that more seed pairs with similar maps due to these phenomena exist, but I can imagine that until now only the above 3 pairs have been spotted by human eye just because the seeds are consecutive. Dustin, what do you think?

Posted: **Fri Jul 10, 2020 11:43 pm**

Actually there are a looooot more of such consecutive seed pairs! There are whole blocks of seeds where this pattern occurs, and the even number is always the smaller of the two.
Just checked it out:
34/35, 38/39, 40/41, 50/51, all pairs from 90 to 101, 108/109, 134/135, all from 160-177, 180/181, 184/185, 192/193, 196/197, 218/219 (these actually generate identic cave C maps after some draws - collision?), all from 218-235, 250/251, 254/255.
Some are more extreme, some less, and I left out some even less extreme examples. In some cases, the similarity is combined with a 1-row-shift. But the general pattern is too striking to be a coincidence!
But now, first of all, I need some sleep!

Posted: **Sat Jul 11, 2020 9:18 am**

Just compared 218/219 with Nesdori's list - indeed they collide after 7 draws! So these seeds officially win the random-seed-dream-couple-contest which was... um... never announced!

Posted: **Sat Jul 11, 2020 10:53 am**

I actually think I know how the seed2 sync works.
S_2 := (S_2 + 128[S_2 odd] + 19 + C_1) mod 256
Let's first ignore the last "+C_1" term. Let's start with the even seed x on the one hand and with x+1 on the other hand and compare how they develop (without "+C_1"!). All numbers modulo 256:

Draw 0: x / x+1
Draw 1: x+0+19=x+19 / (x+1)+128+19=x+148
Draw 2: (x+19)+128+19=x+166 / (x+148)+0+19=x+167
Here we have it already - after only 2 draws, we have again a pair of consecutive seeds, shifted by 166!
So in fact, the "+C_1" can easily sync the seed2 if the left seed gets its "+1" at some point but the right seed doesn't.
C_1=1 exactly if S_2 is odd and >128.
This means that the left seed can get its "+1" only in draw 2 if x+19>128, which means x>109.
On the other hand, the right seed may not get a "+1" in draw 1, which means that x+1<128 or x<127.
So for even numbers 109<x<127, the seed2 values x and x+1 sync after two more draws!
Let's see how this works for 218/219:
Draw 0: 218 / 219
Draw 1: 218+0+19+0=237 / 219+128+19+1=111
Draw 2: 237+128+19+1=129 / 111+128+19+0=2
Draw 3: 129+128+19+1=21 / 2+0+19+0=21
Voilà! In fact it worked a little different from my above scheme, because both seeds already got a "+1" in draw 1/2. Let's also try to generalize that:

Again everything modulo 256:
Draw 0: x / x+1
Draw 1: x+0+19+0=x+19 / (x+1)+128+19+1*=x+149
Draw 2: (x+19)+128+19+1**=x+167 / (x+149)+128+19+0***=x+40
Draw 3: (x+167)+128+19+1****=x+59 / (x+40)+0+19+0=x+59
...and synced.
* For this "+1", x+1 must be >128 ==> x>127.
**For this "+1", x+19 must be >128 ==> 109<x<256-19=237.
***For this "+0", x+149 must be <128 ==> 107<x<235
****For this "+1", x+167 must be >128, and given that (*) already claims x>127, this is equivalent to x>217.
Taking all these inequations together, we get 217<x<235,and that's a perfect match with the list I gave two posts above! Yeah!

Next question - why doesn't the other range 109<x<127 match the list? Of course it must have something to do with seed1. It should be easy to figure out what happens to the initially synced seed1 after two or three draws!

Posted: **Sat Jul 11, 2020 7:01 pm**

That's very insightful! Great!

Posted: **Sun Jul 12, 2020 11:51 am**

Thx Arno!

These calculations were of course still incomplete as they only considered seed2. It is obviously also important that seed1 syncs as well in order to get identical maps. So I want to make a full calculation of the first eight draws to see how the random seeds 218/219 (the most extreme example with a full sync after 8 draws) work. I think this will also give more insights about what happens in other cases.

For a better oversight, the recursive formulas again - also I have spotted a mistake with C_2 which is now corrected:
S_1 := (S_1 + 128[S_1 odd] + floor(S_2 / 2) + C_2 + C_3) mod 256
S_2 := (S_2 + 128[S_2 odd] + 19 + C_1) mod 256
C_1=1 exactly if S_2 is odd and >128.
C_2=1 exactly if S_2 is even and >=238, or if S_2 is odd and 108<S_2<128.
C_3=1 exactly if S_1 is odd and >128, or if S_1=127 and C_1=1..

Draw 0: (0 218) / (0 219)

Draw 1 left:
S_1=0+0+109+0+0=109
S_2=218+0+19+0=237
Right:
S_1=0+0+109+0+0=109
S_2=219+128+19+1=111
(109 237) / (109 111)
[Remark: We see that seed1 is still identic, while seed2 has stretched, mainly because the right S_2 got a "+128" for its oddness and the left one didn't.]

Draw 2 left:
S_1=109+128+118+0+0=99
S_2=237+128+19+1=129
Right:
S_1=109+128+55+1+0=37
S_2=111+128+19+0=2
(99 129) / (37 2)
[Remark: Now S_1 has asynced by 62. The main reason being the "floor(S_2/2)" terms, where the left seed1 got 126 bigger input than the right S_1.]

Draw 3 left:
S_1=99+128+64+0+0=35
S_2=129+128+19+1=21
Right:
S_1=37+128+1+0+0=166
S_2=2+0+19+0=21
(35 21) (166 21)
[So S_2 has synced after 3 draws, which I already proved in my general calculations of my previous post. S_1 is still far off, so let's see how they sync now:]

Draw 4:
Left: S_1=35+128+10+0+0=173
Right: S_1=166+0+10+0+0=176
Both: S_2=21+128+19+0=168
(173/168) (176/168)

Draw 5
Left: S_1=173+128+84+0+1=130
Right: S_1=176+0+84+0+0=4
Both: S_2=168+0+19+0=187
(130 187) / (4 187)

Draw 6:
Left: S_1=130+0+93+0+0=223
Right: S_1=4+0+93+0+0=97
Both: S_2=187+128+19+1=79
(223 79) (97 79)

Draw 7:
Left: S_1=223+128+39+0+1=135
Right: S_1=97+128+39+0+0=8
Both: S_2=79+128+19+0=226
(135 226) / (8 226)

Draw 8
Left: 135+128+113+0+1=121
Right: 8+0+113+0+0=121
Both: 226+0+19+0=245
(121 245) / (121 245)

So here we have it! To show that this sync is no mere coincidence, I want to analyse how the difference between the left and right S_1 values develops after each draw:
S_1(left)-S_1(right) = 0, 0, 62, -131, -3, 126, 126, 127, 0.
One can easily see that four of these values are close to +/-128, four are close to 0 and one is close to 64.

How does S_1 sync after the 3rd draw (when S_2 is already synced)?
After the third draw, S_1 is off by 131. How can this be "equalized" with identic S_2 values? Let's see the formula again:
S_1 := (S_1 + 128[S_1 odd] + floor(S_2 / 2) + C_2 + C_3) mod 256
The term "floor(S_2/2)" doesn't make any difference with identic S_2 values, and C_2 amd C_3 clearly cannot equalize a 131 gap in a few draws, so the interesting term is "+128(S_1odd)".

This means:
1. If the S_1 values are ~128 off and have different parity, they will come very close together after the next draw! (Don't forget that 2*128=0!) We see this happening in draws 4 and 8.
2. If the S_1 values are ~128 off and both are odd, then both will get a "+128" in the next draw, so they won't come closer immediately. But! Exactly one of those values will get a "C_3=1" extra term, so after the next draw the values will have different parities, so according to 1., they will come closer in the second-next draw. This can be seen in draw 7.
3. Finally, if the S_1 values are ~128 off and both are even, none will get a "+128" or a "C_3=1", so their gap will stay exactly the same after the next draw. But! The parities can easily become odd by the term "floor(S_2/2)" if this is an odd term, and it's only a question of time until this happens, which brings us back to 2. This can be viewed in draw 6.

To summarize, A S_1 value gap of ~128 will always quickly be overcome once S_2 is synced! That's why after the 3rd draw, when S_2 is synced and S_1 is 131 off, it's already clear that the S_1 values will come very close together after some more draws. The fact that S_1 actually also perfectly syncs is quite specific for the seed pair 218/219, but as Artno has already shown, the cave maps will also look very similar if S_1 stays off by a small even number. So in general the calculations should be very similar for the whole seed block 218-235, and this explains why this works as it works!
But there's still one more question:

2. What happens in the first three draws so that S_1 is ~128 off afterwards?
--> Before the first draw, S_1 is equal and S_2 is off by 1.
--> In the first draw, the right S_2 gets its "+128" for oddness, so S_2 is ~128 off after draw 1. Also, the S_2 values get same parity because of C_1.
--> S_1 is still equal after draw 1.
--> In the second draw, S_1 go off by ~64. This is because of the floor(S2/2) term when S_2 is off by ~128.
--> S_2 stays off by ~128.
--> In draw 3, S_2 syncs and S_1 goes by by another ~64. This could either mean, like here, that the S_1 values come close together, or it could also mean the gaps add to ~128.
So after the third draw, S_2 has synced and S_1 could either be close or off by ~128, which, as we saw before, makes no big difference anyway!

So I think this wraps up the 218-235 block. One thing to note: The fact that 128+128=0 plays a big role for the whole argumentation, so if in the formulas, there was some weird prime like 113 used instead of 128, this would in fact change a lot!

Posted: **Sun Jul 12, 2020 9:56 pm**

Great analysis Dustin!

Nice to see how the formulas explain the observations with those seed pairs!

Hereby I will post some other research results.

The main question I'm currently focussing on is:

Why do certain shapes occur repeatedly in random cave maps?

For example, below picture shows Cave A of BD1 (on level 1, so seed=10), where the walls and vertical steelwall borders have been removed in order to show the underlying random items.
Here, some areas are highlighed which show a nearly similar pattern. This is what I'll call a "repeated shape". None of them are exactly the same. There is variation, mostly in the non-dirt items, but there is a similarity which cought my eye already long time ago when I played BD on C64.

If you check out the other caves from BD1 (or from BD1-engine games in general), you will easily recognize this shape in many caves. It occurs for any random seed, but at different spots on the map.

Why do we observe these repeated shapes? At this point, I'm very sure that Seed2 plays a big role in the explanation. Therefore I will now provide the answer to the first sub-question:

Sub-question 1: Does Seed2 show any regular pattern which could be related to the observed repeated shapes?

It turns out that, for any inital seed, the sequence of Seed2 values shows relatively short repeated cycles.

Remember the recursive formula for the sequence of Seed2 values:

S_2 := (S_2 + 128[S_2 odd] + 19 + C_1) mod 256

Where

C_1 = 1 if and only if S_2 is odd and >128

Applying this for initial seed 10 (which is used in BD1 Cave A, level 1), the first 73 draws give the following results:

29, 176, 195, 87, 234, 253, 145, 37, 184, 203, 95, 242, 5, 152, 171, 63, 210, 229, 121, 12, 31, 178, 197, 89, 236, 255, 147, 39, 186, 205, 97, 244, 7, 154, 173, 65, 212, 231, 123, 14, 33, 180, 199, 91, 238, 1, 148, 167, 59, 206, 225, 117, 8, 27, 174, 193, 85, 232, 251, 143, 35, 182, 201, 93, 240, 3, 150, 169, 61, 208, 227, 119, 10

Thus, after 73 draws, the value is again 10, like the initial seed, so that the cycle starts at 29 again. Now this is interesting: for initial seed 10, out of all possible values from 0 to 255, actually only 73 different values occur!

Below picture, a screenshot from Excel, presents the Seed2 values for initial seed 10, for all 20 visible rows (of 40 columns each) in a cave.
Colors are used to indicate intervals in which each value falls:
- Yellow: <50
- Green: >=50, <100
- Blue: >=100, <150
- Red: >=150, <200
- White: >=200.

It is easy to see that the above 73 numbers are repeated in cycles, which results in a sort-of carpet with clearly visible repeated patterns.

But what happens for the other initial seeds, other than 10?
Well, first or all, it is trivial that if the initial seed is taken from the above list of 73 values it will show the same 73-cycles and patterns, but just in a shifted variant.
For all other initial seeds, I have checked them all and it turns out that after at most 21 draws the sequence end up in the same 73-cycle as mentioned above.
For example, for initial seed 134, the first 21 draws are as follows:

153, 45, 192, 211, 103, 250, 13, 160, 179, 71, 218, 237, 129, 21, 168, 187, 79, 226, 245, 137, 29

Here, 29 is part of the 73-cycle, so the sequence will continue repeating this cycle until forever. (It is easily checked by the above formulas that 10 and 137 both give 29 as the next value for Seed2.)

As another example, for initial seed 20 (which is not in the list of 73), the very first draw gives 39 (which is already in the list).

In conclusion, for each initial seed, after a number of draws between 0 and 21, the sequence ends up in the 73-cycle. This implies that each initial seed will show the same repeated patters like for seed 10 above (basically a shifted variant of the carpet shown above), except for the first part of the first line which may be different.

This is a remarkable result! Out of all possible values 0-255, only 73 will occur on the long run. On the other hand, this may be not a big surprise either given the simplicity and predictability of the sequence.

Next, you could notice that the way in which the repeated shapes are located towards each other is very similar to the repeated patterns on the Seed2 map. For example if you start at some number on the Seed2 map, go 2 steps up and 7 steps right, you will end up on the same number.
Now look at the above picture of cave A with the highlighted repeated shapes. Some pairs of shapes are mutually located in a similar way: 2 vertical and 7 horizontal steps in between.

This makes it very likely that the repeated cycles in the Seed2 sequence form part of the exaplanation for the repeated shapes!

The next task is to investigate how the 73-cycles in Seed2 affect the Seed1 values so hopefully the repeated shapes can be fully explained.

Posted: **Tue Jul 14, 2020 8:25 pm**

Now it's time to reveal the second and last part of the analysis.

In the previous post we have seen that Seed2 contains a 73-cycle, while at the same time, some mysteriously repeated shapes in BD1-engine-caves also show up in a pattern which fits into a 73-cycle.

The second sub-question is therefore:

Sub-question 2: Can those repeated shapes be explained by the way how the 73-cycle in Seed2 affects Seed1?

The answer is yes! Again, the formulas are very helpful to explain the relation theoretically:

S_2 := (S_2 + 128[S_2 odd] + 19 + C_1) mod 256
S_1 := (S_1 + 128[S_1 odd] + floor(S_2 / 2) + C_2 + C_3) mod 256

C_1=1 if and only if if S_2 is odd and >128.
C_2=1 if and only if S_2 is even and >=238, or S_2 is odd and 108<S_2<128
C_3=1 if and only if S_1 is odd and >128, or S_1=127 and C_1=1

Given that S_2 contains a 73-cycle, does S_1 also show some pattern in its series which is repeated after each 73 draws?

Well, according to its formula, S_1 increases with a number given by: 128[S_1 odd] + floor(S_2 / 2) + C_2 + C_3 (modulo 256).
- The first term, 128[S_1 odd] does not depend on S_2. On the other hand, since it depends on the parity (even/oddness) of S_1 it may either cause a big shift (128), or not at all (0).
- The terms floor(S_2 / 2) and C_2 depend only on S_2. So these terms will repeat every 73 draws!
- The term C_3 depends on both S_1 and S_2, so this value is less predictable. On the other hand it is always small (0 or 1).

I decided to make the relation more clearly visible by expanding the cave width from 40 to 73 items.

Below pictures show the values of Seed2, Seed1 and the increments of Seed1 (modulo 256), for a cave field of 73 columns and 20 rows, using initial seed 10 (like in BD1 Cave A, level 1):

Now, the cycles are repeated at the start of each row. The Seed1 field is colored depending on the item resulting from the filling rules of BD1 Cave A, that is:
- Space: <60 (red)
- Boulder: <50 (blue)
- Diamond: <9 (green)
- Dirt for other Seed1 values (so >= 60) (white)

Now it is clearly visible that various shapes occur repeatedly, but not always exactly the same. Seed1 starts repeating itself from row 14 column 3: there the value is 108 (from predecessor 20), which already occurred on row 1 column 3 (from predecessor 147). (Indeed, it's possible to check with the formulas, that when S_2 = 176, the S_1 values of 147 and 20 both give 108 as next value.)
But in all prevous rows, there are some similarities which are not exact. Basically, there are two reasons for that:
- The start value of S_1 is not the same for each row.
- The series of increments are not the same. As can be seen from the third picture above, many times the increment equals floor(S_2 / 2), sometimes with an extra 128 depending on the parity, and occasionally with a little extra depending on C_2 and C_3.

How does this all translate to a cave with regular size (40 columns)?

Let's consider again the random filling of BD1 Cave A, with clearly similar shapes at various spots:

Below picture shows the corresponding Seed1 values of this map. The areas where we expect the shapes to occur have been colored in a gray scale. Lower numbers have darker grey background.

In areas A, C, G, H, I and J the repeated shapes are clearly visible on both the cave map and the Seed1 grid. To a less extend, areas B and D also show the shape (or part of it) on the Seed1 grid. These shapes are not visible on the cave map because most of the numbers are >60 and thus result in dirt. But the shape itself is still there! Only the areas E and F do not show the typical shape. As explained before, the similarities are not exact, but still striking enough to be distinguished by the human eye.

Summary

In this pair of posts I started with the question "Why do certain shapes occur repeatedly in random cave maps?"
In one sentence, the answer is: Because the value by which the random number Seed1 increments each draw shows a non-exact pattern due to the fact that the most important term, Seed2 contains a cycle of length 73.

Posted: **Thu Jul 16, 2020 8:27 pm**

Here's another interesting research question related to the Boulder Dash RNG:

Why is there a tendency for vertical lines in random filled caves?

As an example, below picture shows a variant of BD1 Cave A (level 1), from which the walls and T-walls along the vertical borders have been removed. Also the inbox and outbox have been moved in order to show the full area of random-filled items. Furthermore I have marked horizontal lines of 3 or more non-dirt items by a yellow line; vertical lines by a green line.

It stands out immediately that vertical lines occur way more often (17 times) than horizontal lines (4 times). This is not coincidence. In fact, many BD1-engine caves show a similar tendency.

I have always found this tendency for vertical lines quite remarkable. Thinking about it, it might even be a desired feature! For instance, consider the situation that Rockford must move downward through a narrow corridor. Then, a horizontal line of boulders might easily block the way. Vertical stacks, on the contrary, can often easy be passed very well, also in a horizontal corridor. So, it could well be that this feature has been a selection criterion for this RNG! But I'm not sure...

Anyway, I will hereby provide an explanation based on the working of the RNG.
First note that in a previous post I already shared some numerical results:

Arno wrote:I've experimented a bit in my Excel implementation on an extended cave map (still with 40 columns, but with 100 rows instead of 20).
I tried various random seeds combined with the filling rule of BD1 Cave A, in which a non-dirt item is placed when the random value is <60.

My results:
- Probability of a random number <60 (i.e. non-dirt item): 60/256 ~ 23.4%
- Frequency that a number is <60: around 23-24% (that is, indeed near the theoretical value)
- Frequency that the next number is <60 given that the current number is <60: around 18-19% (that is, lower than the expected 23-24%)
- Frequency that the 40th next number is <60 given that the current number is <60: around 38-40% (that is, way higher than the expected 23-24%)

Combining these observations, you can conclude that there is indeed a tendency for vertical lines of non-dirt items!

So, the statistics confirm the observations, but how does the RND mechanism lead to higher probability for vertical repetition of non-dirt items than horizontal?

Remember the formula for Seed1:

S_1 := (S_1 + 128[S_1 odd] + floor(S_2 / 2) + C_2 + C_3) mod 256

Assume that a non-dirt item is placed when S_1 is in the interval [0, 59] (like BD1 Cave A).

To see how likely horizontal and vertical lines are, we will estimate the expected interval for the next draw and the 40th next draw, given that the current draw is in [0, 59]. (Remember that the standard cave width is 40, so the item below the current item is determined after 40 draws.)

Behaviour after 1 draw (horizontal next position):
- Term floor(S_2 / 2): In a previous post I've shown that S_2 has a repeating cycle of length 73. Therefore it is quite easy to calculate a long run average of floor(S_2 / 2) based on the 73 values of S_2 within the cyle: this value turns out to be ~69.548.
- Term C_2: Also C_2 is repeated in the 73-cycle, so the long run average of C_2 could be calculated similarly: ~0.110.
- Term C_3: The term C_3 does not follow the 73-cycle. Still, based on a S_1 generation in Excel, I have calculated a long run average, which is around 0.2.
- Adding up these numbers implies that S_1, on average, increments by ~69.858 from these terms.
- But, there's still the term 128[S_1 odd], which is either 0 or 128.

Based on the these results, we could calculate two expected intervals for the next draw: first by adding the 69.858 to the boundaries of [0, 59], and second by also adding 128 (modulo 256). Either interval occurs with a ~50% probability, since it depends on term 128[S_1 odd]. The two intervals calculated in this way are, respectively, after rounding: [70, 129] and [198, 1] (modulo 256).

The first interval has no overlap with the [0, 59] interval which gives non-dirt items. This does not mean that values in this interval are not possible, but just less likely compared to the situation when there is overlap. The second interval has only a very small overlap with [0, 59]: it just contains the values 0 and 1.

Behaviour after 40 draws (vertical next position):

By a similar calculation we could estimate the expected cumulative value of the various terms S_1 after 40 draws, just by multiplying the numbers from the previous calculation by 40.
- For the terms floor(S_2 / 2) + C_2 + C_3, this gives 40 * 69.858 ~ 2794.301 = 234.301 modulo 256.
- For the term 128[S_1 odd], doing this 40 times gives modulo 256 still either 0 or 128, with approximately the same probability.

So again, we can calculate two expected intervals for the 40th next draw by adding 234.301 plus either 0 or 128 to the boundaries of [0, 59]. This gives, after rounding: [234, 37] and [106, 165] (modulo 256). This time the second interval has no overlap with [0, 59], while the first interval overlaps with [0, 59] for the bigger part of it.

We see: after 40 draws the expected intervals have way more overlap with [0, 59] than after 1 draw. This makes it more likely that a dirt item is placed after 40 draws.
Add to this reasoning the fact that after 40 draws, the distribution of possible outcomes will be much more spread around the expected intervals than after 1 draw. In other words, after 1 draw the possible outcomes are more concentrated around a limited set of values with almost no overlap with [0, 59], while after 40 draws any value is possible while the distribution is still peaked at intervals with significant overlap.

Taking all this together leads to the conclusion that a non-dirt item is more likely to occur below another non-dirt item than next to a non-dirt item. So vertical lines of non-dirt items occur more frequently than horizontal lines!

Posted: **Sun Dec 13, 2020 11:36 am**

Seed 3
Here I just noted another funny similarity, which I think wasn't mentioned here
yet. In BD1-B/1, Rockford meets the very first firefly in his life. It's a rather
harmless one, and most Rockfords probably won't harm it either. As Rockford
proceeds, clears level 1 and moves on to H/2, he actually meets the same
firefly again in the bottom-left corner! Now it's even more harmless, it seems
af though it just wanted to see how Rockford is doing since they met first...
When Rockford asks the fly how it is doing, it answers "well I found a friend,
see the bottom-right corner, but please don't kill it!" And indeed there's another
firefly (which was overwirtten by wall in B/1)!

Posted: **Sun Dec 13, 2020 12:04 pm**

Dustin wrote:Here I just noted another funny similarity, which I think wasn't mentioned here
yet. ...

Ah, funny! Seed 3 was treated in a previous post, but indeed I focused on the boulder/space pattern and overlooked Rockford's reunion with that firefly!

Boulder Dash Forum

Random seeds in classic BD games