Slime and (im)permeability explained

[Arno]

This thread is intended to share information about the element of slime in Boulder Dash. The main reason why I have created this thread is that I’d like to refer to it in the description of some youtube videos of some caves recently created at Krissz’ site. Therefore, the information below is currently limited to the knowledge about slime which is required to understand the solution of these caves.

Slime was first introduced in Boulder Dash 2, caves E and M. It looks similar to amoeba, although it does not produce any sound.
A boulder or diamond lying on a piece of slime might fall through it, with a certain probability, provided that there is empty space directly below the slime.
A cave setting called ‘slime permeability’ determines the probability that a slime will be activated during a cave scan, meaning that any boulder/diamond will fall through it, if it can.

In BD2 Cave E, slime is used to produce a seemingly “random” rain of boulders and diamonds. Here, the slime permeability is a probability of 0.125 (=1/8 ). It therefore takes some time before all boulders/diamonds have fallen down through the slime.

In BD2 Cave M, the slime permeability is set to a probability of 1, so any boulder/diamond will immediately fall through the slime, as soon as Rockford clears the dirt below a piece of slime. This creates a puzzle where Rockford must prepare his path to the exit through a series of mixed boulder/diamond-columns.

How does the random number generator work for slime?

Every frame, when a slime-item is scanned, a random number between 0 and 255 is drawn. Depending on this number and the slime permeability setting, the slime is activated or not. When it is “active”, any boulder/diamond will fall through provided that there is empty space below the slime. Note that this generation of a random number happens irrespective of whether a boulder/diamond is carried by the slime and it could fall through it. It just happens for each slime which is scanned during a full cave scan. If there are x slimes in a cave, then x numbers are generated during a cave scan.

In the BD2 engine, the random numbers for the slime activation are generated by the same pseudo-random number generator (RNG) as used for filling the cave-map with random items. More info about this random generator here:
https://www.boulder-dash.nl/forum/viewtopic.php?t=647

Note that the first random value for the first slime is generated after the cave filling has taken place. So, the first 21*40 = 840 draws are used for the cave filling, and the 841st draw is used for the first slime in the first frame, and so on. The behavior of slime therefore also depends on the initial seed value of the cave.

In the PLCK engine, there is no random cave filling, yet the same RNG is used, always with initial seed value 30.

Krissz’ site (speaking of September 2021) is compatible with the PLCK engine concerning slime. This implies that the remake-version of a cave like BD2 Cave E on Krissz’ site is NOT compatible with the original (for all 5 levels). That is, the cave and solution are similar, but the exact slime behavior (i.e. the timing of falling boulders/diamonds) is different.

Impermeable slimes - How does this happen?

It is possible that a slime, from a certain moment onwards, no longer swallows any boulder/diamond.
This is visible, for example in BD2 Cave E, when Rockford is killed by a boulder/diamond and 3 pieces of slime are destroyed by the explosion (observed by Dustin).

How does this work?

As explained in the aforementioned tread about the RNG, any random generation consists of a combination of two numbers (seed1 and seed2), where seed1 is used to determine the slime behavior. Seed2 contains a repetitive cycle of 73 numbers. The combination (seed1, seed2) still gets different pair-values, until the 73-pattern has been run for 13 times. So a the RNG has a repetitive cycle of 13*73 = 949 random numbers.

Now suppose that the amount of slimes in a cave is a multiple of either 13 or 73. Then for each slime, a limited set of random numbers will be checked. For instance, when 2*73 = 146 slimes are present, only 13 different numbers will be checked, since after 13 frames there are 13*146 = 1898 slimes scanned, which is then a multiple of 949 for the first time. Possibly, this limited set of 13 random numbers is such that, depending on the slime permeability setting, the slime is never activated. This is what we call an impermeable slime: it never lets a boulder/diamond through!

As an example, in BD2 Cave E, there are 4 rows of 19 slimes present, so the total number of slimes is 76. When Rockford is killed by a boulder/diamond, while standing along the bottom line of slime, this may reduce the amount of slimes with 3, so there are exactly 73 slimes present! When this happens, impermeable slimes become visible.

Note that the numbers 13 and 73 also form the prime factor decomposition of 949. Therefore, impermeable slimes are possible if and only if the number of slimes is a multiple of 13 or 73.

As of September 2021, the Construction Kit at Krissz’ site features the option ‘show impermeable slimes’, which shows which slimes on the cave-map are permeable (marked green) and which are impermeable (marked red) from the start of the cave onwards.

Of course, while playing a cave, it is possible to change the (im)permeability behavior of slime by destroying slimes, thereby changing the total number of slimes in a cave. This way, it is possible to make a permeable slime impermeable, or vice versa. And yes, there are several caves based on this idea, which were recently created at Krissz’ site! I’d like to provide some youtube-links here when I have the videos ready.

This is it for now, feel free to provide any additions or corrections to this topic!

[Dustin]

Very nice idea to make a topic out of it!
While reading this, I got another idea what could be made out of the slime behaviour. Let's see...

[Dustin]

It actually works very well!
Actually, with the number of slimes in a cave being a multiple of 13 or 73, there are even more unusual effects!
If you start BD2-E and don't move, then after Rockford gets crushed, you see not only impermeable slimes, but you can clearly see a slime which lets a boulder through at a very constant rate (about once every 2 seconds). This is because with 73 slimes in the cave, every slime gets only 13 different values from the RNG before the cycle restarts, i.e. the behaviour of each slime has a periodicity of 13 frames (~2 seconds)! Normally the periodicity would be 949 frames, which is more than 2 minutes so the periodicity can't really be spotted and the slime behaviour feels random.
Also, with 73 slimes in the cave, there are slimes which are clearly "more permeable" than others! This is easily explained: As mentioned before, each slime gets only 13 different RNG values (and no value which one slime gets is identic to a value another slime gets, so all 73 slimes together still get 13*73= all 949 RNG values!) Now assume that slime A has zero active values among its 13 values ("active value"= value such that the slime tries to swallow a boulder or diamond), slime B has one active value among its 13 RNG values, and slime C has three active values, then slime A is impermeable, slime B will be active once in 13 frames, and slime C three times. This means that slime C is three times as active as B! So we have differently liquid slimes in the same cave!
I'm sure there can be made very crazy caves with this...

[Arno]

Interesting! Or even the liquidities can be changed while playing a cave, by destroying slimes such that the amount goes from one multiple of 13 or 73 to another one...

[Dustin]

Yep, indeed! And then you need the right timing out of 73 possibilities to make certain slimes very permeable and others impermeable

[Dustin]

I just had the idea to try and simplify the topic as much as possible. In fact, it is not necessary to know anything about how the slime RNG works, except for two things:
(1) The cycle length is 949=73*13.
(2) Each of the 949 RNG states makes a slime either active or inactive for the current frame.

One can just imagine a series of 949 numbers for each RNG state, each of which is either green (active) or red (inactive), for example:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 .......... 945 946 947 948 949

The percentages of red and green numbers depends on the slime permeability. Traditionally, this is a value between 0 and 8.
Permeability 0: All 949 numbers are green.
Permeability 1: About 1/2 of the numbers are green.
Permeability 2: About 1/4 of the numbers are green.
Permeability 3: About 1/8 of the numbers are green.
...
Permeability 8: About 1/256 of the numbers are green.
(In our above example, green and red numbers are about 50/50, so the permeability would probably be 1).

Now let's consider a cave with exactly 3 pieces of slime. Let's call them A, B and C. How does our RNG deal with those?
In the first frame, slime A is scanned first and is given the RNG number 1. In our above example, it is a green number, so the slime is active in this frame and swallows a boulder/diamond if possible. During the same frame, the cavescan next comes to slime B and gives it the number 2. It is green as well, so B swallows if possible. Slime C gets the red number 3 and does not work in this frame.
In the second frame from the start, slime A gets the green number 4 and swallows if possible. Slime B (number 5, red) and C (6, red) are passive.
And so the same procedure runs on frame for frame. After 949 slime scans, the 950th slime scan just restarts the cycle with the number 1. As 949/3=316 1/3, this means that in the 317th frame from the start, slime A gets the green number 949, and B gets the green number 1 and so on. Note that after 949 frames, each slime has each of the 949 numbers exactly once, and in the 950th frame, slime A finally gets number 1 again, and the slime behaviour pattern restarts.

Now what happens if there are 73 slimes in the cave?
Frame 1: the slimes get the numbers 1-73.
Frame 2: The slimes get 74-146 (2*73).
Frame 3: The slimes get 147-219 (3*73).
...
...
Frame 13: The last slime gets 949 (13*73), which is exactly the cycle length!
Frame 14: The slimes get 1-73 again, just as in frame 1, and same slimes get same numbers in frames 1 and 14! This pattern continues.
So as long as no slimes are destroyed, all the slimes in the cave get only 13 different numbers from the RNG. For example, the first slime in the cave gets the numbers 1, 74, 147, 220, 293, 366, 439, 512, 585, 658, 731, 804, 877, and then 1 again (pattern is of course "+73")
This means:
- The pattern of the slime behaviour already restarts after 13 frames (not only after 949 frames as in the previous example with 3 slimes!)
- If all of the above thirteen numbers are red, then the first slime in the cave will never swallow anything - here's the phanomenon of impermeability! Of course, all other slimes in the cave could as well be impermeable by the same logic.
However, it must also be said that with 50% of all 949 numbers being green, it is very unlikely that among a set of 13 numbers, none of those is green. The probability of a particular slime being impermeable (with 73 slimes in the cave) is 0.5^13=0.000122..., and indeed you won't find any impermeable slimes with 73 total slimes and permeability 1. For 73 slimes, permeability must be at least 3 to have some impermeable slimes!
- I already mantioned that if you start BD2-E/1 and don't move, then after Rockford is crushed (and therefore 73 slimes left), you see some impermeable slimes and also one slime which swallows at a very constant rate (about once in 2 seconds). You can easily explain this now: as we've just seen, the slime behaviour repeats after 13 frames, which is about 2 seconds!
- Another phanomenon is that some slimes are more permeable than others, depending on how many green RNG values a particular slime has among "its" 13 different values! For example, if there's exactly one green value among the above numbers 1, 74, 147, 220, 293, 366, 439, 512, 585, 658, 731, 804, 877, then the first slime in the cave is active exactly once in 13 frames.The second slime has the values 2, 75, 148, 221, ..., 878, and perhaps four of those are green and the others red, which means that this slime is "four times as active" as the first slime!

A similar phanomenon occurs if the number of slimes in the cave is (a multiple of) 13. Now each slime gets 73 different RNG values until the cycle restarts, so slime behaviour repeats after 73 frames ~ 10 seconds. Each slime now has 73 different RNG values, which makes it less likely for a slime to be impermeable than in the above example of 73 slimes with 13 RNG values each. Consequently, you need at least permeability 4 here to have one impermeable slime!

---------------------------------------------------------------------------------------
Hmm, I wanted to keep everything as simple as possible, but now I can't withstand the temptation to make the following list (assuming 13 slimes in the cave):
Permeability // Expected number of impermeable slimes // actual number of impermeable slimes
0 // 0 // 0
1 // 13*(1/2)^73=0.00000... // 0
2 // 13*(3/4)^73=0.00000... // 0
3 // 13*(7/8)^73=0.00075... // 0
4 // 13*(15/16)^73=0.11690... // 1
5 // 13*(31/32)^73=1.28055... // 2
6 // 13*(63/64)^73=4.1178... // 4
7 // 13*(127/128)^73=7.33309... // 8
8 // 13*(255/256)^73=9.76920... // 10
Not such a bad match between expected and actual values, although the actual values tend to be slightly too high! Now come on, let's do it for 73 slimes as well (here I'm especially curious if there are a lot more impermeable slimes than expected because 73 is the cycle length of the seed_2 value of the RNG):
0 // 0 // 0
1 // 73*(1/2)^13=0.00891... // 0
2 // 73*(3/4)^13=1.73428... // 0
3 // 73*(7/8)^13=12.8655... // 4
4 // 73*(15/16)^13=31.5... // 32
5 // 73*(31/32)^13=48.3... // 48
6 // 73*(63/64)^13=59.4... // 55
7 // 73*(127/128)^13=65.9... // 67
8 // 73*(255/256)^13=69.3... // 70
Hmmm... the perm. 3 value strikes as far too little, the rest is OK. No idea what this tells us, it was just a mathematical playing...
--------------------------------------------------------------------------------------

Now the craziest effects occur with 949 slimes in a cave! In this case, every slime always gets the very same number from the RNG, which means it either is always active or never! Also, a cave with 949 slimes (and a diamond above each and empty space below) will tell you all about which numbers from the RNG are actually red and green! Just start the cave and watch which diamonds fall, those are the green numbers, the rest is red. Note, however, that there is an issue with starting values that do not belong to the 949 cycle and can change the behaviour of the first ~30 slimes in the first frame (and only there). So if you really want to check it out, make sure to place dirt under the first 30 slimes (so they cannot swallow in the first frame), and dig it away later.
Note that:
- as mentioned before, every slime that swallows a diamond will do so instantly, so you needn't wait!
- every RNG state (1-949) which is green with a given permeability (0-8) will also be green with a lower permeability. This means that each RNG number from 1 to 949 can be assigned with the highest permeability for which the number is green. Doing this for all 949 RNG states would give a complete picture of the slime RNG (together with the starting values)! But this would be a lot of work...

[LogicDeLuxe]

Note, however, that there is an issue with starting values that do not belong to the 949 cycle and can change the behaviour of the first ~30 slimes in the first frame (and only there).

You should clarify which engine we are talking about. Obviously not Atari/C64, whose caves are too small for 949 slimes plus diamonds/boulders and spaces to even give them the ability to do their thing. So 73 and 13 really would be the only values of practical use for this.
So is this ~30 with random placements taken into account? Random placement on BD1 and BD2 always use up the first 800 (40x20) random numbers during cave build up, while PLCK using a map based format doens't have such a thing.
So when using an engine with variable cave size, the actual pattern would depend on several factors (given, it uses the same slime code at all):
Cave size.
Is the random placement in the engine mandatory, even if it doesn't actually place anything, like in BD1/BD2?
Do placeable structures like mazes use the same RNG?
Does the engine reset the seed after cave buildup?
Does the slime use the same RNG instance for any of the above at all?

I could imagine that cross compatibility between engines is lacking at this, since nobody came up with this stuff until now.

[Arno]

I have decided to create a Youtube playlist of all caves which exploit the phonomenon of slime impermeability or other patterns of slime behaviour due to the existing patterns in the pseudo-RNG.

Watch them all here:

https://www.youtube.com/watch?v=zRDdo59 ... Eo_zu6uh_L