The Cave Scanning Order (CSO) university

Everything about the various Boulder Dash tools, and other stuff created by the fans.

Moderator: Admin

User avatar
Dustin
Member
Posts: 589
Joined: Sun Sep 23, 2007 1:15 am
Location: Erlangen, Germany

The Cave Scanning Order (CSO) university

Post by Dustin »

Episode 0 - Intro and motivation

In the other thread about cavescanning order effects, I'm analyzing mini caves in which I used more or less specific cave scanning order effects of the BD engine.At the beginning, I just thought that there would be a few caves to make, and then the issue would be closed again. But the more ideas I got, the more I understood how rich this topic is and how many different effects have all the same origin, namely the cavescanning order! So in this thread, I'm trying to do a systematic approach to these effects, categorize them and maybe also find some new effects that haven't been used in caves yet.
I think that this approach makes this thread different from the other one - at least different enough to open a new thread for it at all! :D Also, I want to explain everything "from zero", so it's not necessary to read the other thread to understand everything!

The general structure of this thread will (probably) be as follows:
1. Explaining how exactly the BD engine works, thereby defining what CSO effects are and also showing some specific engine rules that can be exploited for CSO effects.
2. Once we understood how the BD engine works, the real fun starts - we can systematically categorize CSO effects and, for each category, find each and every possibility to use the CSO for funny, strange, unintuitive and stunning BD effects!

I just note that it's quite not so easy to write this intro, the reason being that it might not even be clear at first sight what this topic is all about! In fact, I learned about the CSO only a year ago, when I joined Krissz's site and read what the "real" BD experts wrote about very deep BD stuff! So I'm optimistic that everything will become clearer after the next few episodes! :D

In the first episode, I'll start explaining the BD engine. There's quite a lot to say about how all the BD elements are programmed, so it'll definitely take several episodes, but in episode 1, I'll explain enough to give a proper definition of what this thread is all about!
Boulder Dash X Rock, Paper, Scissors:
ROCKFORD collects DIAMOND, digs DIRT
DIAMOND outvalues DIRT & BOULDER
DIRT carries BOULDER, blocks FIREFLY
BOULDER kills FIREFLY & ROCKFORD
FIREFLY kills ROCKFORD, guards DIAMOND
User avatar
Arno
Site Admin
Posts: 2826
Joined: Sat Mar 17, 2007 2:26 pm
Location: netherlands
Contact:

Post by Arno »

Very good idea Dustin! I think this is going te be a very interesting series! :D
User avatar
LogicDeLuxe
Member
Posts: 637
Joined: Sun Jul 15, 2007 12:52 pm
Contact:

Post by LogicDeLuxe »

In the past, I made several caves which require some understanding of the scanning order. Most of them, I wouldn't consider fair nowadays, since some of them depend on luck to a degree or require an insane amount of endurance. Those are not too hard to figure out by chance though. Some examples include:

In Deluxe Dash 1 Cave 12, the success relies on the firefly not to explode at the amoeba, but from a converted diamond:
Image

Deluxe Dash 1 Cave 13 and 19 have some tight places which require frame exact movement to get past the creatures:
Image

And Crazy Dream 5 Cave "Viel spass!" is probably the most insane offender. It can be frustrating for sure.

Also other authors used some scanning order tricks in old caves before. I've seen at least the boulder slide on growing wall before.

EDIT: changed cycle to frame to be consistent with the given terminology.
Last edited by LogicDeLuxe on Wed Nov 04, 2020 5:04 pm, edited 1 time in total.
User avatar
Dustin
Member
Posts: 589
Joined: Sun Sep 23, 2007 1:15 am
Location: Erlangen, Germany

Post by Dustin »

@Arno: Thanks! I'm looking forward to write these episodes, as with the more
scientific and systematic approach, I might find some new CSO tricks to
complete the topic!

@Logic: Thanks for your reply and the info/material! I'll surely come back to it
when this thread has developed further!

Episode 1 - Definitions: What are CSO effects?
In this first episode, we'll start analyzing how the BD engine is programmed.
When I say "the BD engine", I mean the engines of most modern BD clones,
which are based on the original BD2 engine to a huge extent. In fact, I could
define "the BD engine" as the original BD2 engine with the following slight
differences:
1. The way amoebas that are trapped from the beginning are dealt with. As
far as I know, the original BD2 engine was not programmed to design such
caves at all, while most modern engines define such amoebas as "dead", an
amoeba state that the original BD1/2 engines did not know. (Wanna know
more about it? Stay on the ball in this thread! :D)
EDIT: LogicDeLuxe has corrected me here - the BD2 engine actually
does work properly with amoebas that are trapped from the beginning! See
the next two posts in this thread (from Logic and me).
2. The way random numbers are calculated (for boulder-pushing, amoeba-
growth and slime-activity) is not consistent among modern BD engines.
Fortunately, this has nothing to do with our topic anyway, so we can just
ignore this aspect.
As far as I konw, all modern BD clones use engines that are programmed
identical w.r.t. all relevant functions, so I think that speaking of "the" BD
engine makes absolute sense.

Definitions
Let's first clarify some terms that I'll use throughout this thread. Some of
them are taken from LogicDeLuxe's posts in other threads, so I hope I sound
perfectly professional! :D
A frame is the shortest BD time unit, usually a small fraction of a
second.
A (real) map is a BD cave picture that the player sees while playing. So
whenever you play a BD cave and pause the game, what you see is a map. So
every frame has a different map. The initial map of a cave is the map
the cave starts with.
Furthermore, a virtual map is a BD cave picture that is not visible for
the player. Virtual maps are calculated by the BD engine between two (real)
maps.
A BD element is an object in the BD universe. In this thread, I'll
exclusively deal with the classical BD elements, which I hereby define as:
Rockford, dirt, empty space, diamond, boulder, firefly, butterfly, wall, magic
wall, growing wall, titanium wall, amoeba, slime, outbox, voodoo, and, last
but not least, explosion smoke.
The cavescan is a major tool of the BD engine. The BD engine scans
the map according to specific rules (see below), and whenever a BD element
is scanned, it acts according to specific rules (see the following episodes).
When a BD element is scanned, the BD engine needs to detect the
elements close to the scanner to decide what the scanned element should do.
For example, if a firefly is scanned and decides whether it should explode, it
makes the decision according to the four elements that it currently touches.
When the cavescanner has scanned and moved a BD element, this element is
given a delay state to ensure that it cannot move again in the same
frame. See below for a more precise explanation!

How the BD engine works - basic rules
To understand what CSO effects are, we first need some basic understanding
of the BD engine. What does it do while we play a BD cave? Well, technically
speaking, a BD cave is just a sequence of maps, starting with the initial map
and ending with the final map where Rockford has hit the open outbox and
finished the cave. So it comes down to the following question:
How does the BD engine calculate the map for the next frame, given the
map for the actual frame and the player's keyboard input?


Here's the answer:
1. The BD engine scanes every element of the current map one by one,
decides what to do with it (move, grow, explode, do nothing...) and then goes
on to the next element.
2. (CSO rule): The order in which the cave is scanned is row-by-row, from
top to bottom, each row from left to right.
For a 5x5 cave, this order is:
ABCDE
FGHIJ
KLMNO
PQRST
UVWXY
3. Some BD elements are "passive" elements, which can't move/grow/do
anything interesting by themselves. Passive elements are just skipped by the
cavescanner. Those elements are: dirt, empty space, wall, magic wall,
titanium wall, outbox, voodoo.
4. When an active BD element is scanned, the BD engine decides what to do
with it according to the specific rules of each element.
5. If a BD element is scanned and moves/grows, it is given a delay state.
Elements in delay state are always passive, so they can't act again in the
same frame. At the end of a cavescan, all delay states are removed so each
element can be active again in the next frame.
I think this was quite a lot of theory - time for an...

Example!
Let's consider the following map which arose while playing a BD cave:
Image
Let's check step by step how the next frame's map is calculated!
The cavescanner starts at the top-left cornerand scans the map according to
the CSO rule above. In the top row, there are only titanium walls (passive
elements), which are skipped. In the second row, the first active element is
the diamond:
Image
White square=cavescanner
White dot=detected element (in this case: dirt)
The cavescanner has found a diamond. What could a diamond possibly do? It
could fall down if there's empty space below it! So the BD engine detects the
element below the diamond. It finds dirt and concludes that the diamond
cannot fall down. That's it. The diamond does nothing and the cavescanner
moves on.
The next active element is a boulder:
Image
With a boulder in the scanner, the BD engine also wonders whether the
boulder can fall. So again, it detects the element below the boulder. Ah!
There's empty space, so the boulder can and will actually fall. So the boulder
is moved one step down and gets a delay state because it has moved. (Also,
the boulder's state is changed into "falling", which means it's now ready to kill
flies or careless Rockfords.)
Image
Red dot=delay state
The scanner moves on to the next active element, the firefly:
Image
With a firefly in the scanner, the BD engine makes, first of all, an "explosion
check". It detects the four elements touching the firefly and if there's anything
hostile (which is Rockford, a piece of amoeba or a voodoo), the firefly blasts.
Here, however, there's nothing dangerous in the detector, so the next
question is if and where the firefly moves.
First of all, the firefly wants to turn left, which means, given that it currently
faces downwards, that it would like to move right. But there's dirt in the way,
so it's not possible. Next, the firefly would like to move forward (down). This
is possible because there's empty space, so finally, the firefly knows what to
do: move down, get a delay state mark, and enjoy its life ;)
Image
The scanner moves on. to the growing wall:
Image
As indicated by the arrows, it's a horizontally growing wall, so the elements
left and right must be detected. If there would be empty space, the wall
would grow, but there's dirt and Rockford in the way, so the growing wall does
nothing and the scanner moves on to Rockford personally!
Image
One might think that Rockford also makes "explosion checks" as the firefly
does, but actually this is not the case. (More about all the specifities of each
BD element in the next episodes!) What happens is that the BD engine asks
the player what to do with our hero. Let's say we press "up" on our keyboard,
then the BD engine detects the element above Rockford to see whether it's
actually possible for Rockford to move there. It is, since there's dirt which
Rockford can easily dig away. So Rockford moves up, gets his delay state
mark and the scanner moves on.
Now we see something interesting: the next element in the scanner is the
delay state boulder that has already fallen down. As delay state elements are
always passive, the scanner just skips the boulder and moves on. And that's
the sense of delay states, otherwise the boulder would fall again (and again
and again) within the same frame! The same goes for the delay state firefly,
so the next active element in the scanner is the butterfly.
Image
Obviously, the explosion check is negativ also here, so the butterfly tries to
move. Its favourite direction would be right from the fly's point of view (up
from our point of view), but there's dirt in the way. Next, the butterfly wants
to move forwand (left), but there's the firefly in the way. (For detections, it
makes no difference whether or not an element has a delay state.) So,
instead of moving, the butterfly just turns left (facing down now) and stays
where it is, hoping to be able to move next frame.
Image
The scanner moves on to a boulder which cannot fall:
Image
The rest of the cavescanning is simple: the scanner finds, apart from passive
elements, only some boulders and diamonds which cannot fall. So the
cavescanning for this frame is over, all delay states are removed and the next
map is proudly presented to the player:
Image
Note that only the first and last picture of this episode are real, visible maps.
All others are virtual maps that the player can't see. All the scans and
detections we just saw happen inside one frame!

Definition: CSO effects
By now we understood enough about the BD engine to finally define properly
what this whole topic is all about:
We speak of a CSO effect whenever the CSO rule (rule 2. above) has an
influence on the resulting map for the next frame.


In other words, we might wonder if the resulting cave map (last picture) could
have been any different if the cave had been scanned in a different order (e.g.
from right to left, from bottom to top, diagonally, spiral-shaped......) while not
changing any other rules? What do you think?

In fact, our above example includes even two independant CSO effects, one
obvious and one perhaps slightly less obvious.

CSO effect #1: firefly vs. butterfly
In the first map, buth the firefly and the butterfly pointed towards the same
empty space. The CSO rule decided that the firefly was scanned first, so it
could move. Then when the butterfly was scanned, it was already blocked by
the firefly. Had the butterfly been scanned first, then the roles would have
changed. Later, when it comes to categorizing the CSO effects, I'll call this one
"movement competition". In movement competitions, the element which is
scanned first "wins" and moves, while the other one is blocked off.

CSO effect #2: growing wall vs. Rockford
That's the not-so-obvious CSO effect. The growing wall was blocked by
Rockford, who then moved away to free the space, but it was already too late
for the growing wall because it was scanned before Rockford. Had the growing
wall been scanned after Rockford, then in the final map, it would already have
grown right. Here, we see that being scanned first is not always
"advantageous"! As the growing wall depended on Rockford moving away so it
could grow, I'll classify this CSO effect as "dependance, negative". "Negative"
means that the growing wall could actually not grow because it was scanned
too early.

Alright! I'm happy with the results of this episode - now we know what CSO
effects are and as a bonus, we've also seen two big categories already.
In the next few episodes, we'll have a look at all active BD elements one by
one and see what exactly the BD engine does when each of them is in the
scanner. The precise knowledge of the BD engine is necessary to be able to
analyze and categorize every single CSO effect and see how each of them can
be used to make interesting and challenging caves!
Last edited by Dustin on Wed Nov 04, 2020 1:45 pm, edited 2 times in total.
Boulder Dash X Rock, Paper, Scissors:
ROCKFORD collects DIAMOND, digs DIRT
DIAMOND outvalues DIRT & BOULDER
DIRT carries BOULDER, blocks FIREFLY
BOULDER kills FIREFLY & ROCKFORD
FIREFLY kills ROCKFORD, guards DIAMOND
User avatar
LogicDeLuxe
Member
Posts: 637
Joined: Sun Jul 15, 2007 12:52 pm
Contact:

Post by LogicDeLuxe »

Dustin wrote:1. The way amoebas that are trapped from the beginning are dealt with. As
far as I know, the original BD2 engine was not programmed to design such
caves at all, while most modern engines define such amoebas as "dead", an
amoeba state that the original BD1/2 engines did not know.
Actually, the dormant amoeba feature already was there in BD1, but buggy. An amoeba which is trapped from the beginning does not convert immediately and it is muted as it's used to be. The random decision for spreading still takes place, though, and if it decides to, it gets active and will convert in the next scan.
This was fixed in BD2 and behaves like in PLCK, but it was not used in any of the original caves. Rockford's Profiboulder series has many games using the BD2 engine and use this feature occasionally.
User avatar
Dustin
Member
Posts: 589
Joined: Sun Sep 23, 2007 1:15 am
Location: Erlangen, Germany

Post by Dustin »

Thanks for the info, Logic! I have not played that many Profi Boulder caves (definitely something to consider for the future, as these games ahve a good reputation as far as I know!)

So the BD2 engine actually has a working "dormant amoeba" feature, which makes it even more sensible to define it as "the" BD engine!
A terminological note: from now on, I'll also call a pre-trapped amoeba "dormant" instead of "dead". It makes a lot more sense since "dead" sounds very final and unchangeable which is not at all the case. Given this, it seems logical to me to call the other amoeba states "awake", "trapped" and "overgrown" (the last two only existing for one frame). All of this will be explained further in episode 2 or 3.

And another general note I haven't mentioned yet: as I'm not a programmer and as I've taken all my knowledge about the BD engine from experience and specific experiments, it's very possible that I'll make small mistakes when I'm explaining how the BD engine works. In this case, corrections are welcome, of course, as is everything that helps increasing the quality of the thread!
Boulder Dash X Rock, Paper, Scissors:
ROCKFORD collects DIAMOND, digs DIRT
DIAMOND outvalues DIRT & BOULDER
DIRT carries BOULDER, blocks FIREFLY
BOULDER kills FIREFLY & ROCKFORD
FIREFLY kills ROCKFORD, guards DIAMOND
User avatar
LogicDeLuxe
Member
Posts: 637
Joined: Sun Jul 15, 2007 12:52 pm
Contact:

Post by LogicDeLuxe »

Instead of "virtual map" I'd rather would call in "intermediate map state". And "resulting map" is fine, but I wouldn't call it "visible map", as on Atari and C64, you can in fact also see intermediate map states, since it is a virtual screen drawn in real-time, which can happen in the middle of a frame. If there is much going on in the cave, this can even last for multiple TV fields.
Modern clones usually render the view after the frame is scanned completely, though.
User avatar
Dustin
Member
Posts: 589
Joined: Sun Sep 23, 2007 1:15 am
Location: Erlangen, Germany

Post by Dustin »

Thx for the comment, Logic! I'll do the redefinition "virtual map" into
"intermediate map", first of all because this sounds easier to understand!

Episode 2 - specific BD engine rules for each BD element
In this episode, I'm going to finish the explanation of the BD engine rules, so
after this episode, we'll know exactly how the BD engine works and can move
on to exploiting some specific rules for CSO effects!

In the previous episode, we've already seen that the BD engine is based on
cavescans. Each frame, each element in the current map is scanned one by
one. So what exactly does the BD engine do if it has a specific BD element in
the scanner?

First of all, remember that there are some passive elements which
can't do anything on their own. These elements, which are dirt, empty space,
wall, magic wall, titanium wall, voodoo and outbox, are just skipped by the
scanner. (Of course, these elements still make a huge difference when
detected!)

Before I start analyzing all active elements, I have one more note about
"states" that the BD engine has to remember for more than just one frame. These states are:
Kill Rockford (on/off): (switched "on" if a voodoo gets killed by a fly)
Amoeba state (dormant/awake/trapped/overgrown):
A dormant amoeba is one that is trapped from the beginning (silent).
An awake amoeba is the "normal" one: makes noise, grows unpredictably...
A trapped amoeba is ready to convert into diamonds.
An overgrown amoeba (usually >200 pieces) is ready to convert into boulder.
Amoeba growth speed (slow/fast): changes from "slow" to "fast" when
the amoeba timer runs out.
Magic wall state (dormant/active/dead): starts with "dormant",
changes into "active" as soon as there's something to convert, then changes
into "dead" after the magic wall timer runs out.
Outbox state (open/close): changes from "close" to "open" when
Rockford has collected enough diamonds.
And, last but not least, the visible ones: cave timer, collected diamonds,
score.
At the start of a cave (i.e. in the initial map), the states are always as follos:
Kill Rockford: off
Amoeba state: dormant
Amoeba growth speed: slow
Magic wall: dormant
Outbox: close

Now let's start! What does the engine do if each active BD element is in the
cavescanner?
General note 1: Whenever a BD element movesor grows, it gets a
"delay state" mark. Elements with delay state are always passive, i.e. skipped
by the scanner.. At the end of each frame, all delay states are removed.
General note 2: If an element explodes, the BD engine detects all eight
surrounding elements and converts them into explosion smoke (phase 1) or,
in case of a butterfly, diamond birth (phase 1).Exception: Titanium walls
aren't converted. All explosion smoke/diamond birth pieces get delay states.
General note 3: I won't mention any sound effects or animations - we
all know them, and they aren't interesting for our topic!

Rockford
1. If the "kill Rockford" state is on, then Rockford explodes.
2. Otherwise, the engine asks the player for his input:
2a) If the player's input is "move up/down", the BD engine detects the element in this direction.
If it's dirt or empty space, Rockford moves there.
If it's a diamond, Rockford moves into the diamond and the diamond
counter is increased. If now the diamond counter is equal to the diamond
requirement, the outbox state is changed from "close" into "open".
If it's an open outbox, the cave is successfully finished.
In any other case, Rockford stays where he is.
2b) If the player's input is "move left/right", the same happens as 2a), with
the following extra possibility:
If the detected element is a boulder, the engine also detects the element
behind the boulder. Now, in case of empty space, Rockford gets a 25% chance
to push the boulder and in case of success, Rockford and the boulder are both
moved.
2c) If the player's input is "snap", the same things happen as in 2a) or 2b),
the only difference being that in case of a successful snap, the engine does
not move Rockford but changes the snapped element into empty space.
Note: Rockford does not explode when he touches a fly! It's always the
fly's job to do the explosion. That's the reason why Rockford can touch a fly
from top or left: in these two cases, Rockford is scanned before the fly and
escapes before the fly detects him and explodes. This specific rule defines a
whole category of CSO effects which I'll later call "explosion checks"!

Boulder
The element "boulder" is in fact split in two - "(dormant) boulder" and "falling
boulder". They look identical for the player, but they do make a difference for
the BD engine!

(Dormant) boulder
The engine detects the element below the boulder:
(A) If it's empty space, then the boulder moves down and converts into
a "falling boulder".
(B) If it's another (dormant) boulder, a (dormant) diamond or a wall, the
engine detects the two elements to the left and to the bottom-left side of the
scanned boulder.
(B1) If both are empty space, the boulder is moved left and converts
into a "falling boulder". (the boulder "falls sideways")
(B2) Otherwise, the engine detects the two elements to the right and
bottom-right side of the scanned boulder:
(B21) If both are empty space, the boulder moves right and converts
into a "falling boulder".
(B22) Otherwise, the boulder does nothing.
(C) In any other case, the boulder does nothing.

Falling boulder
The engine detects the element below the falling boulder:
(A) If it's empty space, then the falling boulder moves down.
(B) If it's Rockford, a firefly or a butterfly, the detected element explodes.
(C) If it's a (dormant) boulder, a (dormant) diamond or a wall, the
engine detects the two elements to the left and to the bottom-left side of the
scanned falling boulder.
(C1) If both are empty space, the falling boulder is moved left.
(C2) Otherwise, the engine detects the two elements to the right and
bottom-right side of the scanned falling boulder:
(C21) If both are empty space, the falling boulder moves right
(C22) Otherwise, the falling boulder does not move, but it converts into
a (dormant) boulder.
(D) If there's a dormant or active magic wall, the engine detects the
element below that magic wall:
(D1) In case of empty space, this space is filled with a falling diamond. The
falling boulder in the scanner vanishes and, if the magic wall was dormant,
the state changes into "active". The magic wall timer starts.
(D2) In any other case, the falling boulder in the scanner vanishes and, if the
magic wall was dormant, it changes into "active".
(E) If there's a dead magic wall, the falling boulder vanishes.
(F) In any other case, the falling boulder converts into a (dormant)
boulder.
Note: That's how the magic wall can be a passive element - the falling
boulder does all the conversion work by itself, so the magic wall doesn't do
anything on its own!
Note2: When a falling boulder falls through a magic wall, it moves two
steps at a time, i.e. it falls double as quickly as usual!

Diamond/ Falling Diamond
That's quickly explained - diamonds just behave 1:1 analogously to boulders!
In fact, the only difference between diamonds and boulders occurs when
they're detected by Rockford.(OK, and also when an amoeba decides how to
convert.)

Firefly (facing left)
Fireflies, too, aren't just one element for the BD engine - in fact, the element
"firefly" is split into four, one for each facing direction. I'll explain what a
"firefly (left)" does, the others are just analogous:
1. First, the firefly makes an "explosion check". The BD engine detects the
four elements touching the firefly, and if it finds Rockford, an amoeba or a
voodoo, the firefly explodes. In case of a voodoo, the engine also activates
the "kill Rockford" checkmark after the end of the frame.
2. If the explosion check was negative, the engine detects the element below
the firefly (or, from the firefly's point of view, to its left side.)
(2A) If there's empty space, the firefly moves there and changes into a "firefly
(down)".
(2B) Otherwise, the engine detects the element to the firefly's left (from the
fly's point of view: forward).
(2B1) If there's empty space, the firefly moves there.
(2B2) If not, the firefly doesn't move but changes into a "firefly (up)". (From
the fly's point of view, it turns right).

Butterfly
Butterflies just behave the same way as fireflies, with two exceptions:
1. Butterflies explode into diamond birth instead of explosion smoke.
2. The directions in which the butterfly turns and moves (from the fly's point
of view) are reversed, compared with a firefly.

Amoeba
With an amoeba in the scanner, the BD engine's actions depend on the
current amoeba state (dormant, awake, trapped, overgrown):
(A) Dormant amoeba
The BD engine detects the four elements touching the amoeba.
(A1) If at least one of them is dirt or empty space, the amoeba state is
changed into "awake". The engine generates a random number to decide
whether the amoeba wants to grow and, if so, into which direction. If, for
example, the random number says "grow left", the BD engine again detects
the element to the amoeba's left side. If this is dirt or empty space, the
amoeba grows into it. Otherwise, or if the random number says "do not
grow", nothing happens.
(A2) If none of the four elements is dirt or empty space, nothing happens at
all.
(B) Awake amoeba
In this state, the BD engine has three things to consider each frame:
1. an amoeba piece counter
2. a "stay awake" checkmark
3. an "overgrown" checkmark
Now if an amoeba is scanned while the amoeba state is "awake", the BD
engine increases the amoeba piece counter and, if it hits 200, the amoeba
state is changed into "overgrown". Next, the engine detects the four elements
touching the amoeba.
(A) If none of them is dirt or empty space, nothing happens (the scanner
moves on).
(B) If at least one of them is dirt or empty space, the engine activates the
"stay awake" checkmark (if it wasn't activated before). Then, a random numer
decides whether the amoeba wants to grow and in which direction. If, for
example, the result is "grow down", the engine detects the element below the
amoeba. In case of dirt or empty space, the amoeba grows there and the
amoeba counter is increased, otherwise nothing happens.
If, at the end of the cavescan, the "stay awake" checkmark was not activated,
the amoeba state is changed into "trapped".
Trapped amoeba
The amoeba is changed into a diamond.
Overgrown amoeba
The amoeba is changed into a boulder.
Note:We see that if an amoeba is trapped, it is changed into diamonds
piece by piece in the following frame. This makes it actually possible for a
firefly to trap an amoeba without exploding! We'll see exactly how it works
when it comes to analyzing the CSO effects!
Note 2: An interesting question is what happens with an amoeba that
is trapped into exactly 200 pieces. Is it trapped or overgrown? According to
my above "programming" it would be trapped and give you 200 diamonds, but
there are also modern BD engines which give such an amoeba the
"overgrown" state.In this case, the max amount of diamonds that you can get
from an amoeba would be 199. That's just a side note, as there's no relevance
for our topic here.

Slime
First, a random number is generated. Based on the slime permeability of the
cave, the random number decides whether the current piece of slime shall be
active in this frame.
(A) If the slime is not active, nothing happens.
(B) If the slime is active, the BD engine detects whether there's a (dormant)
boulder/diamond above the slime and, at the same time, empty space below
the slime.
(B1) If not both is the case, nothing happens.
(B2) If both is the case, the boulder/diamond vanishes while at the same time
the empty space below the slime is changed into a falling boulder/diamond.

Growing wall
If the BD engine scans a horizontally growing wall, it detects the elements to
the wall's left and right side. If there's empty space, the wall grows into it. It
can also simultaneousely grow into both directions. Analogous for
vertically/bidirectional gwalls.

Explosion smoke
This exists in four phases. Phase 1-3 change into the next phase when
scanned, phase 4 changes into empty space. Analogous for diamond birth.

Whoa, that was a lot of theory! But, as I mentioned, it was necessary to write
all this down as I want to be able to refer to this later on. I'm almost sure that
I haven't given everything 100% correctly, but I'm happy as long as there are
no "visible" mistakes, i.e. mistakes that can actually lead to false engine
behaviour in a cave. If I have made such a mistake, I would be happy to be
corrected! Every detail is a potential new CSO effect! :D

In the next episode, we'll finally start to systematically analyze and categorize
CSO effects, with the goal to discover every possible effect that can be made
with the classical elements!
Boulder Dash X Rock, Paper, Scissors:
ROCKFORD collects DIAMOND, digs DIRT
DIAMOND outvalues DIRT & BOULDER
DIRT carries BOULDER, blocks FIREFLY
BOULDER kills FIREFLY & ROCKFORD
FIREFLY kills ROCKFORD, guards DIAMOND
User avatar
LogicDeLuxe
Member
Posts: 637
Joined: Sun Jul 15, 2007 12:52 pm
Contact:

Post by LogicDeLuxe »

Dustin wrote:First of all, remember that there are some passive elements which
can't do anything on their own. These elements, which are dirt, empty space,
wall, magic wall, titanium wall, voodoo and outbox, are just skipped by the
scanner.
Outbox is a somewhat special case.
It is not a passive element from the engine point of view. Like with the inbox, the flashing animation is executed during the scan, thus the speed depends of the cave speed.
From the physics point of view, it can be considered passive nevertheless, since the executed code is only for the visibility.
Outbox: close
Actually, outbox closed and outbox open are two different elements, outbox closed will be converted during the scan when the cave's "open" flag is set, which happens during collecting the final required diamond. It is infact possible to have an open outbox in the cave from the beginning, and the cave can be solved without actually collecting enough diamonds.
I did this once in order to confuse the player.
Since this is a very minor detail, it is very possible that some engine clones didn't implement it that way.
General note 1: Whenever a BD element movesor grows, it gets a
"delay state" mark. Elements with delay state are always passive, i.e. skipped
by the scanner.. At the end of each frame, all delay states are removed.
General note 2: If an element explodes, the BD engine detects all eight
surrounding elements and converts them into explosion smoke (phase 1) or,
in case of a butterfly, diamond birth (phase 1).Exception: Titanium walls
aren't converted. All explosion smoke/diamond birth pieces get delay states.
This logic does work and fits what can be observed. Most engines have some exceptions to those rules for optimization, though.
Objects moving behind the scan don't set the delay state in many cases, which takes the need to reset its state later on.
And the titanium wall check indeed only takes place for the 8 surrounding elements and the source of the explosion is converted regardless, as we already know it is not a titanium wall.
2. Otherwise, the engine asks the player for his input:
It's worth noting, that left/right takes priority over up/down, ie. pressing the stick diagonally behaves the same as it was only moved to the side.
(Dormant) boulder
Not to be confused with prof. Knibbles mutant stone, which also has a dormant state and then looks just like a regular boulder. I think, calling it "resting boulder" for distinction makes much more sense.
In case of a voodoo, the engine also activates
the "kill Rockford" checkmark after the end of the frame.
"Kill Rockford" is set immediately. It clearly makes a difference if Rockford is scanned before or after the explosion (albeit of no practical use when you'll die anyway).
1. an amoeba piece counter
2. a "stay awake" checkmark
3. an "overgrown" checkmark
It's worth mentioning that the "trapped" and "overgrown" flags are reset during cave initialisation. The counter is reset to 0 each frame. The "stay awake" flag is reset each frame.
Now if an amoeba is scanned while the amoeba state is "awake", the BD
engine increases the amoeba piece counter and, if it hits 200, the amoeba
state is changed into "overgrown".
This does never happen during the scan. Instead, the counter is checked after the scan and set when the limit is reached. There is indeed a chance for the amoeba to grow over the limit during the final frame before the conversion starts in the next frame.
Note 2: An interesting question is what happens with an amoeba that
is trapped into exactly 200 pieces. Is it trapped or overgrown? According to
my above "programming" it would be trapped and give you 200 diamonds, but
there are also modern BD engines which give such an amoeba the
"overgrown" state.
As mentioned, both checks take place after the scan and "overgrown" has priority over "trapped", so 199 diamonds is indeed the most you can get from the amoeba.
Except when the initial amoeba size is more than 255 pieces, which overflows the counter. The overflow was fixed in later engines and probably all clones as well.
User avatar
Dustin
Member
Posts: 589
Joined: Sun Sep 23, 2007 1:15 am
Location: Erlangen, Germany

Post by Dustin »

Thx for the interesting comments, Logic!
LogicDeLuxe wrote:
Dustin wrote: First of all, remember that there are some passive elements which
can't do anything on their own. These elements, which are dirt, empty space,
wall, magic wall, titanium wall, voodoo and outbox, are just skipped by the
scanner.
Outbox is a somewhat special case.
It is not a passive element from the engine point of view. Like with the inbox, the flashing animation is executed during the scan, thus the speed depends of the cave speed.
From the physics point of view, it can be considered passive nevertheless, since the executed code is oGnly for the visibility.
Good to know! I was actually wondering whether the outbox is really passive because of the animations. The same question occured to me considering the magic wall, because it also needs animation when it's in active state. So is the magic wall also not completely passive?
That's the reason why I wrote that I exclude animations and sound effects from my investigations - firstly, they don't have anything to do with the topie and secondly, I often don't know how these are programmed! :D
LogicDeLuxe wrote:
Dustin wrote: Outbox: close
Actually, outbox closed and outbox open are two different elements, outbox closed will be converted during the scan when the cave's "open" flag is set, which happens during collecting the final required diamond. It is infact possible to have an open outbox in the cave from the beginning, and the cave can be solved without actually collecting enough diamonds.
I did this once in order to confuse the player.
Since this is a very minor detail, it is very possible that some engine clones didn't implement it that way.
Interesting! Also here, I was wondering whether "open outbox" and "closed outbox" are two different states ore elements. Both assumptions were logical w.r.t. everything I've seen so far. GDash (the engine I know best by far) supports outboxes that are open from the beginning, but GDash supports 100 non-classical elements, so this was not meaningful at all. Krissz's engine, which I know second-best by far, does not support pre-open outboxes, so I guessed that "open" and "close" were different states. I have to admit that I haven't that much experience with the PLCK engines - the thing is that I fell in love with GDash very early (despite its bugs, first of all for the easy-to-handle five-level feature I used a lot), so I definitely have some "gaps in my education" concerning classical C-kits!
LogicDeLuxe wrote:
Dustin wrote: General note 1: Whenever a BD element movesor grows, it gets a
"delay state" mark. Elements with delay state are always passive, i.e. skipped
by the scanner.. At the end of each frame, all delay states are removed.
General note 2: If an element explodes, the BD engine detects all eight
surrounding elements and converts them into explosion smoke (phase 1) or,
in case of a butterfly, diamond birth (phase 1).Exception: Titanium walls
aren't converted. All explosion smoke/diamond birth pieces get delay states.
This logic does work and fits what can be observed. Most engines have some exceptions to those rules for optimization, though.
Objects moving behind the scan don't set the delay state in many cases, which takes the need to reset its state later on.
And the titanium wall check indeed only takes place for the 8 surrounding elements and the source of the explosion is converted regardless, as we already know it is not a titanium wall.
Interesting, I was thinking about this, too, but as I have absolutely no experience with programming, I wasn't sure whether such precision work would pay off.
LogicDeLuxe wrote:
Dustin wrote: (Dormant) boulder
Not to be confused with prof. Knibbles mutant stone, which also has a dormant state and then looks just like a regular boulder. I think, calling it "resting boulder" for distinction makes much more sense.
OK true, but in this case, as I already emphasized that this thread is only about classical elements, I think I can as well keep calling it "dormant boulder" without any possible misunderstandings.
LogicDeLuxe wrote:
Dustin wrote: In case of a voodoo, the engine also activates
the "kill Rockford" checkmark after the end of the frame.
"Kill Rockford" is set immediately. It clearly makes a difference if Rockford is scanned before or after the explosion (albeit of no practical use when you'll die anyway).
Wait, this might be very relevant for this topic! Does this mean that with BD2/PLCK engines, Rockford can survive this scenario:
DDDDD
DORSS
DDDDD
DVFSS
DDDDD
D Dirt, R Rocky, O Open Outbox, S Space, F Firefly, V Voodoo
But he's doomed in the following scenario:
DDDDD
DVFSS
DDDDD
DORSS
DDDDD
If this is the case, then this would definitely be a nice CSO effect!!
My experiments with GDash/Krissz, where Rockford survives both scenarios, make me assume that these engines activate "kill Rockford" only at the end of the frame. I saw no reason why it might have been different with BD2/PLCK, but if this is actually the case, the above scenarios definitely belong to the list of CSO effects!
LogicDeLuxe wrote:
Dustin wrote: 1. an amoeba piece counter
2. a "stay awake" checkmark
3. an "overgrown" checkmark
It's worth mentioning that the "trapped" and "overgrown" flags are reset during cave initialisation. The counter is reset to 0 each frame. The "stay awake" flag is reset each frame.
Ah yes of course, I just forgot to mention that :D
LogicDeLuxe wrote:
Dustin wrote: Now if an amoeba is scanned while the amoeba state is "awake", the BD
engine increases the amoeba piece counter and, if it hits 200, the amoeba
state is changed into "overgrown".
This does never happen during the scan. Instead, the counter is checked after the scan and set when the limit is reached. There is indeed a chance for the amoeba to grow over the limit during the final frame before the conversion starts in the next frame.
Ah yes, of course. I knew that but mixed it up when I wrote the episode. Actually, in GDash (where "trapped" has preferrance over "overgrown") I managed once to get 201 diamonds from an amoeba! :D
LogicDeLuxe wrote:
Dustin wrote: Note 2: An interesting question is what happens with an amoeba that
is trapped into exactly 200 pieces. Is it trapped or overgrown? According to
my above "programming" it would be trapped and give you 200 diamonds, but
there are also modern BD engines which give such an amoeba the
"overgrown" state.
As mentioned, both checks take place after the scan and "overgrown" has priority over "trapped", so 199 diamonds is indeed the most you can get from the amoeba.
Except when the initial amoeba size is more than 255 pieces, which overflows the counter. The overflow was fixed in later engines and probably all clones as well.
Alright, so GDash is programmed differently here. There can surely be made funny caves with it, but unfortunately, it doesn't seem to have any overlaps with the CSO topic.
So, theoretically speaking, it is possible that a BD2 amoeba does not convert if the counter raises from 199 to 256 in one frame? Of course, this would be so unlikely to happen that it might in fact be truly impossible - if we take into account the way that pseudo-random numbers are calculated, there might be no initial values that actually lead to such a behaviour.
Boulder Dash X Rock, Paper, Scissors:
ROCKFORD collects DIAMOND, digs DIRT
DIAMOND outvalues DIRT & BOULDER
DIRT carries BOULDER, blocks FIREFLY
BOULDER kills FIREFLY & ROCKFORD
FIREFLY kills ROCKFORD, guards DIAMOND
User avatar
LogicDeLuxe
Member
Posts: 637
Joined: Sun Jul 15, 2007 12:52 pm
Contact:

Post by LogicDeLuxe »

Dustin wrote:So is the magic wall also not completely passive?
Magicwall is passive. Most animations are done within the raster interrupt, ie. completely separated from the scanning. BD1 and BD2 caves have even flags for turning on or off the amoeba, butterfly and firefly animations to speed up the engine. Some cave authors, including those of BD3 didn't even bother to set them appropriately, leaving the amoeba unanimated in several caves.
Wait, this might be very relevant for this topic! Does this mean that with BD2/PLCK engines, Rockford can survive this scenario:
DDDDD
DORSS
DDDDD
DVFSS
DDDDD
D Dirt, R Rocky, O Open Outbox, S Space, F Firefly, V Voodoo
But he's doomed in the following scenario:
DDDDD
DVFSS
DDDDD
DORSS
DDDDD
Exactly. In the first scenario, he can of course grab the outbox before the firefly is scanned.
In the latter case, Rockford will explode, since the firefly will detected the voodoo and set the kill flag before Rockford is scanned.

Also related to this might be the "win" condition. If during the scan Rockford snaps or walks over an open outbox, the "win" flag is set immediately, no matter what still happens within the current frame. There are cases where Rockford gets caught into an explosion after getting the outbox and still wins. This can be easily tested by placing a firefly next to the outbox, so that the scanning order reaches the firefly after Rockford.
Ah yes, of course. I knew that but mixed it up when I wrote the episode. Actually, in GDash (where "trapped" has preferrance over "overgrown") I managed once to get 201 diamonds from an amoeba! Very Happy
That's odd. I've never seen this happening. I guess, amoeba pieces which grew up or left aren't counted since they are behind the scanning position, so if they filled up the last possibility to grow in multiple places in one frame, it would infact be possible to meet both conditions at once during the next frame. Maybe we should investigate this.
There can surely be made funny caves with it, but unfortunately, it doesn't seem to have any overlaps with the CSO topic.
I certainly can think of situations where the order of the condition checks are CSO relevant. It sure makes a difference whether the conversion begins mid-frame or later.
So, theoretically speaking, it is possible that a BD2 amoeba does not convert if the counter raises from 199 to 256 in one frame?
Exactly. In Lord Diego's Effect Kit, you can set the amoeba limit to 250, which increases the chance of an overflow significantly, and I've seen this happening quite a lot with this setting. If you're lucky, it can overflow multiple times and fill the entire cave.
The original PLCK limits the amoeba pieces you can set in a cave to 200 in order to prevent a constructed overflow. 1stB and later engines extended the counter to 16 bit to prevent any overflows.
if we take into account the way that pseudo-random numbers are calculated, there might be no initial values that actually lead to such a behaviour.
Except that amoeba (and also boulder pushing) does not use the pseudo random generator in original BD1 and BD2. However, GDash does indeed has one here, which is required for the playback feature.
User avatar
LogicDeLuxe
Member
Posts: 637
Joined: Sun Jul 15, 2007 12:52 pm
Contact:

Post by LogicDeLuxe »

I've checked it, and my suspicions are true. And so are your observations for Gdash. There are relevant differences in Gdash compared to the Atari/C64 engines.

First, let's analyze the voodoo behavior:
After the scan, there are these checks in Gdash:

Code: Select all

   /* PLAYER */
    if ((player_state == GD_PL_LIVING && player_seen_ago > 15) || kill_player) /* check if player is alive. */
        player_state = GD_PL_DIED;
    if (voodoo_touched) /* check if any voodoo exploded, and kill players the next scan if that happended. */
        kill_player = true;
The comment says it.
In the C64 disassembly, we can see that the kill flag (BGZ_f9), set by the fly code when a voodoo doll is detected, is checked directly, and it is the first check done in the Rockford code:

Code: Select all

DynMoveRoFo             subroutine                  ; 
                        lda BGZ_f9                  ; 
                        beq B_4813                  ; 
                        
                        lda #$1c                    ; 
                        sta BGZ_83                  ; 
                        jsr DynExplodeFlyHandler    ; 
                        jmp MoveTilesReturn         ; 
It is also noteworthy that the kill flag is a byte incremented by the fly's detection code, leaving it vulnerable to another overflow exploit, ie. if there are exactly 256 voodoo dolls detected before Rockford is scanned, he would survive! If a fly touches multiple voodoo dolls at once, all of them are counted before the explosion code is executed.

And the analysis for the amoeba:
Newly grown amoeba pieces aren't counted in either version, thus the order of checks is important. If both conditions are met at the same time, the latter overrides the first condition in Gdash, leaving infact a chance to get it trapped at or over the limit:

Code: Select all

    /* AMOEBA */
    if (amoeba_state == GD_AM_AWAKE) {
        /* check flags after evaluating. */
        if (amoeba_count >= amoeba_max_count)
            amoeba_state = GD_AM_TOO_BIG;
        if (amoeba_found_enclosed)
            amoeba_state = GD_AM_ENCLOSED;
    }
The beginning of the amoeba code from the C64 disassembly of the PLCK on the other hand shows that if overgrown is met (cmp #$c8), it is converted to stone (lda #$11) and no further checks are done, ie. it has priority over trapped:

Code: Select all

DynMoveAmoeba           subroutine                  ; 
                        inc TabAmoebaCountThis      ; 
                        lda TabAmoebaCountLast      ; 
                        cmp #$c8                    ; 
                        bcc B_454f                  ; 
                        
                        lda #$11                    ; 
                        jsr GameScreenOutHandler    ; 
                        jmp MoveTilesReturn         ; 

Another thing you missed, which can be also relevant to scanning order is the fact that a growing wall will not grow to both sides at once. Left is checked first, and if it can grow there, that's it.


C64 disassembly is taken from here: https://www.forum64.de/index.php?thread ... ost1566309
User avatar
Dustin
Member
Posts: 589
Joined: Sun Sep 23, 2007 1:15 am
Location: Erlangen, Germany

Post by Dustin »

Thanks a lot for your research, Logic! These differences are very relevant for the topic!

At the moment, I'm still thinking about how best to systematize the CSO effects, that's why there was no new episode yet this weekend. My current intention is to have a look at all one-frame CSO effects where only two active BD elements are involved. Later, we could move on and see how these "basic CSO effects" can be put together to create more complex CSO effects. But before making the next episode, I want to check whether this approach is really the best!
Boulder Dash X Rock, Paper, Scissors:
ROCKFORD collects DIAMOND, digs DIRT
DIAMOND outvalues DIRT & BOULDER
DIRT carries BOULDER, blocks FIREFLY
BOULDER kills FIREFLY & ROCKFORD
FIREFLY kills ROCKFORD, guards DIAMOND
User avatar
Dustin
Member
Posts: 589
Joined: Sun Sep 23, 2007 1:15 am
Location: Erlangen, Germany

Post by Dustin »

LogicDeLuxe wrote:Another thing you missed, which can be also relevant to scanning order is the fact that a growing wall will not grow to both sides at once. Left is checked first, and if it can grow there, that's it.
That's especially interesting. Agin, this seems to be engine-dependant. GDash/Krissz's engine work differently - there the gwall can also grow simultaneousely into both directions. That's a pity because one could make very nice caves if the gwall can only grow into one direction/frame. For example, something like this:
DDFDDT
DDBDDT
DDDDDT
DDDDDT
DDDHDT
DDDTB'T
TTTTTTT
B=Boulder B'=Butterfly D=Dirt T=Titanwall H=Horizontal gwall F=Firefly
To snap the BFly free, one could of course destroy the Hwall. But let's say you still need the Hwall elsewhere later on or it's just protected by more Twalls. Then you could crush the FF in a way that the Hwall can grow left after the smoke clears, and snap the BF free exactly in the frame where the Hwall grows left. Then the BF has one frame to come out (i.e. 50/50 chance). Perhaps an idea for future PLCK caves (or perhaps such an idea has already been implemented?!)
Boulder Dash X Rock, Paper, Scissors:
ROCKFORD collects DIAMOND, digs DIRT
DIAMOND outvalues DIRT & BOULDER
DIRT carries BOULDER, blocks FIREFLY
BOULDER kills FIREFLY & ROCKFORD
FIREFLY kills ROCKFORD, guards DIAMOND
User avatar
Dustin
Member
Posts: 589
Joined: Sun Sep 23, 2007 1:15 am
Location: Erlangen, Germany

Post by Dustin »

Episode 3 - rough structure and explanation

Hi, here we go again! I thought quite some time about how to systematize the material. My first, idealistic approach was to find a way to ensure that we'll find every possible CSO effect there is in BD. But I haven't found a convincing way to do so, so I'm now happy with a less perfect approach! Finally, I've come up with the following rough structure (which will probably still be edited a few times):

I CSO effects with exactly 2 active BD elements involved
1. Movements
a) Movement competitions
b) Movement dependance
c) Special case: b/d falling sideways
2. Explosions
a) Explosion checks
b) Escape the explosion
c) Move into the explosion
d) One explosion prevents another
e) Overwrite explosions
3. Convertions and changes
a) Rockford snaps
b) Slimy actions
c) Convertions
4. Other actions
a) Voodoo vs. Rockford and other last-frame scenarios
b) Magic wall activation
c) Pushing a boulder
d) Amoeba states
5. Open border effects
II CSO effects with >2 active elements involved
III CSO effects over several frames

I think it's best to first have a look at CSO effects with only 2 BD elements involved, and then see how these can be combined for more complex CSO effects.
Furthermore, I decided for a thematic structure. There's only a handful of different actions that active BD elements can do:

Rockford, flies, boulders, diamonds, gwalls and amoebas can move (or grow, which I hereby also define as a kind of movement). In chapter I.1, we'll have a look at CSO effects where only movements play a role. This makes sense to me, as there are so many elements which can move.

Fireflies, butterflies, Rockford and falling boulders can explode. We'll see CSO effects where explosions may or may not take place, and also effects where Rockford can try to escape the range of an explosion just in time.

Changes and conversions:
Rockford can change dirt or diamonds into space by snapping. Slime can swallow boulders and diamonds (thereby changing them into space as well, while at the same time spitting them out again). Falling boulders convert into normal (dormant) boulders if they detect an obstacle below them, and the amoeba can convert into either boulders or diamonds. What CSO effects can be made with these actions? We'll see in chapter I.3.

Open border effects are very interesting. They're all based on the fact that the cavescanning order reverses if two BD elements touch each other over the open border! More about this in chapter I.5.

I know I haven't explained everything yet, but let's just start our investigation in the next episode and finally enter the fascinating world of CSO effects!
Now that I know which topic I want to investigate first - movement competitions - I'm going to prepare the pictures for the following episodes! I hope you'll enjoy the following episodes and perhaps some of them even inspire you for your own caves! :D
Last edited by Dustin on Sun Dec 13, 2020 10:25 pm, edited 1 time in total.
Boulder Dash X Rock, Paper, Scissors:
ROCKFORD collects DIAMOND, digs DIRT
DIAMOND outvalues DIRT & BOULDER
DIRT carries BOULDER, blocks FIREFLY
BOULDER kills FIREFLY & ROCKFORD
FIREFLY kills ROCKFORD, guards DIAMOND
Post Reply