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.