The Cave Scanning Order (CSO) university

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

Moderator: Admin

User avatar
LogicDeLuxe
Member
Posts: 633
Joined: Sun Jul 15, 2007 12:52 pm
Contact:

Post by LogicDeLuxe »

Open borders are a topic on its own, especially since there are several different implementations, and none of them is perfect. There is no official way, since the original game didn't have this feature.
Ideally, as far as CSO is concerned, it should only effect elements which set flags between frames, ie. amoeba for its status and resetting counter. In every other regard, the borderless world should be viewed as seamless instead of frames, which is what they physically would do in a perfect implementation. The catch is the representation of a particular moment, which can't be seamless, as it is still a frame.

You also may consider some Diego effects, especially when an explosion, a boulder or a diamond converts into amoeba. The particular way the original engine handles overgrown amoebas does matter in this regard. The code snipped of PLCK above shows, that it uses the actual count byte from the previous frame to decide between boulder or diamonds to convert. This will lead any newly produced amoebas in later games to convert to diamonds, as if the amoeba was suffocated, due to the previous frame's count being 0. This behavior is probably not copied much, if at all, as it ins't exactly the most efficient way to make the decision for every single piece of amoeba. Personally, I encode the element the amoeba shall convert to in the next frame into the status byte.

Also Diego effects converting anything to flies do matter for CSO for sure.
User avatar
Dustin
Member
Posts: 556
Joined: Sun Sep 23, 2007 1:15 am
Location: Erlangen, Germany

Post by Dustin »

I just noted that I forgot to mention one thing in episode 2:
As soon as a magic wall is activated (i.e. when a falling boulder is scanned and detects a piece of dormant magic wall below it), the amoeba state is changed from "alive into "trapped" if:
1. the engine supports the "MW stops amoeba" feature (which the BD2 engine doesn't but many fanmade engines do!);
2. the actual amoeba state was "alive" before the MW was activated.

I wonder whether there are also differences between the engines concerning the following two aspects:
a) when the amoeba state is changed (immediately after the falling boulder was scanned or at the end of the frame; the first is the case with Krissz's engine, which means that the amoeba is converted into diamonds over two frames!)
b) if the state can also change from "dormant" to "trapped" (Krissz: yes)
Of course, a) is especially interesting for our topic!

I'm starting to feel motivated to open a new thread only about those small differences between the BD engines and in which kind of caves these can matter :D
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: 633
Joined: Sun Jul 15, 2007 12:52 pm
Contact:

Post by LogicDeLuxe »

Dustin wrote:1. the engine supports the "MW stops amoeba" feature (which the BD2 engine doesn't but many fanmade engines do!);
It is worth a note that this feature is not present in any of the original BD engines. 1stB introduced this behavior and provides it as a per cave option.
The idea of converting the amoeba with the magic wall comes from the scan break bug only present in the C64 port of the BD1 engine, which was exploited in BD3 and several other BD1 engine games.
This bug just breaks the scan, and skips anything beyond the boulder which hit the magic wall, leaving a partially scanned cave. Thus, if no grow-able amoeba is detected before the boulder which hit the magic wall, it is assumed trapped due to not scanning the remainder of the cave in this frame.

Another side effect of this scan break bug is that converted diamonds don't fall immediately and some can be lost if you drop boulders too fast.
Dustin wrote:2. the actual amoeba state was "alive" before the MW was activated.
The current amoeba status doesn't matter for this effect. It just sets the amoeba status to trapped. There are caves where you have to convert a dormant amoeba.

An interesting question would be, what if you drop a boulder into a magic wall which has an overgrown amoeba under it? Will it still convert to boulders or gets it overridden by the convert to diamond feature? What if part of the amoeba is above that magic wall. Would part of it convert to boulders and the remainder to diamonds?
Surely some questions worth investigating.
User avatar
Dustin
Member
Posts: 556
Joined: Sun Sep 23, 2007 1:15 am
Location: Erlangen, Germany

Post by Dustin »

LogicDeLuxe wrote:An interesting question would be, what if you drop a boulder into a magic wall which has an overgrown amoeba under it? Will it still convert to boulders or gets it overridden by the convert to diamond feature? What if part of the amoeba is above that magic wall. Would part of it convert to boulders and the remainder to diamonds?
Very interesting! I checked this cave with GDash/Krissz's engine:
Image
(>200 amoebas overall)
In the first frame, the amoeba notes that it's overgrown and thereby changes its stae, ready to convert into boulders. At the same time, the boulder is ready to activate the magic wall.
Next frame, the amoebas above the MW should surely become boulders. But then the MW is activated, and that's where your point comes into play: will the amoeba state "overgrown" now be overwritten by "trapped/stopped by MW"?
If so, then the lower amoebas would actually convert into diamonds, which would be a really funny effect!

"Unfortunately", both of my tested engines make the whole amoeba convert into boulders. I had already made similar tests before, and that's why I thought that a change from "overgrown" to "trapped" was not possible. However, if any other engine makes half of the amoeba convert into diamonds, it'd be great to make caves out of this effect! :D
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: 556
Joined: Sun Sep 23, 2007 1:15 am
Location: Erlangen, Germany

Post by Dustin »

Episode 4 - CSO effects with movements

So let's start the systematic investigation of CSO effects!
Chapter I - 2-element CSO effects over 1 frame
We will start our investigation with these two simplifications, so the CSO
effects discussed in this chapter are the "building stones" for more complex
ones (most CSO effects that can be seen in caves have more than 2 active
elements included and last for longer than just one frame.)

Definition of 2-element and 1-frame CSO effects: A given map M
includes two active BD elements A and B, where A is scanned before B. The
resulting map for the next frame is N. However, if B was scanned before A
while not changing the scanning order of any other active element in the map,
there would be a different resulting map N', which I call the inverted map.


We discuss the CSO effects with pictures showing the maps M, N and N'. As
an example, these would be the pictures of the two CSO effects we already
saw in episode 1:
Image
Image
The green and red line shall highlight which map is the real resulting map for
the next frame. As stated above, the inverted map N' is always different from
the resulting map N. For a striking CSO effect in a cave, it should be the case
that the cave was unsolvable if N' was the real resulting map, so that the CSO
effect is strictly necessary for the cave to work.
For example, how could caves be built around the two above CSO effects?

In the first picture, it's interesting to note that from map N, Rockford is
scanned before the gwall and can therefore move down again before the gwall
blocks him off! So we could think of a cave where Rockford needs to move
away from beside the gwall and then immediately back again. This is, for
example, implemented in the following cave (which I analyzed in detail in the
other CSO thread):
https://www.youtube.com/watch?v=l1k1UkszZTw&t=156s
starting from 0:17.

In the second picture, we could, for example, imagine a cave where the
butterfly would quickly kill a voodoo if it came out first.

I decided to categorize the material in terms of the type of action the involved
elements do. Moving (or growing) is the action that most active BD elements
can do, so we'll start with CSO effects where only movements play a role
(such as the above two CSO effects):

Sub-chapter I.1: Movements
First, let's see which elements can move and under which conditions they do
so:
Image
Matters are simplest with the above four elements, which just move or grow
into the marked directions is possible. (However, I learned from LogicDeLuxe
that the gwall can't grow into both directions simultaneousely with the
BD2/PLCK engines, which might be a very nice detail for future episodes!)
Fire- and butterflies with a given facing direction can move into two different
directions and prefer turning left (firefly) / right (butterfly) over moving
forward.
Amoebas grow randomly into dirt or space, but as I prefer deterministic CSO
effects which don't rely on luck, I don't want to use the amoeba in this
chapter. (However, later on we'll of course see CSO effects that only the
amoeba can do.)
Rockford is the only character who can move into diamonds, but as we've
already excluded the amoeba for this sub-chapter, he's also the only one who
can move into dirt which makes him somewhat special.
We're going to divide the movement-related CSO effects into 2+1 categories.

Sub-subchapter I.1a): Movement competition
Definition:The initial map M includes two elements A<B ("<" means
from now on "is scanned before") which both try to move into the same
space. A wins and moves, while B is blocked off rests (or, in case of a fly, it
could still move into its second-priority direction).
Examples:
Image
Left: A=boulder, B=firefly. The boulder blocks the fly off, which could, for
example, become important if there was a voodoo somewhere at the right
side which the firefly must not touch.
Middle: A=gwall, B=Rockford
The gwall blocks Rockford off, which could be used for a failure scenario.
Right: A= firefly, B=butterfly. Note that I made a mistake here - in the
inverted map N', there should of course be a bfly in the middle instead of the
bottom firefly.
I know that some of the cave ideas I give here sound quite vague so far. This
is just because in chapter I, we're just discussing the "building stones" for
more complex CSO effects which we will see in chapter II!


Sub-subchapter I.1b): Movement dependance
Definition (Type +): The initial map M includes two elements A<B. B
tries to move into A, so it depends on A moving away first. Luckily for B, A
does move away so B can immediately fill the gap A left behind.
Examples:
Image
Left: A=boulder, B=Rockford
Rockford moves "into" the boulder. This can actually be used in BD1-cave I, if
Rockford wants to switch sides from right to left while the boulders and
diamonds are falling (see next picture)!
Middle: A=firefly, B=butterfly
Right: A=Rockford, B=gwall
The gwall immediately fills the gap that Rockford left behind, which means
that nothing can be "smuggled" through that gap!

The following picture shows the aforementioned scenario which might occur in
BD1-I or similar caves:
Image[/b]
If the player presses "left" here, Rockford can immediately move "into the
boulder", which means he's in time to escape the next boulder before it would
crush him!

Definition (type -): The initial map M includes two elements A<B. A
tries to move into B and thereby depends on B moving away first. B is indeed
ready to move away, but as A<B, A still cannot move (into B) immediately.
Examples:
Image[/b]
Left: A=boulder, B=Rockford
This example is very common not only for CSO fans! :D If Rockford moves
under a boulder and then down, the boulder won't follow him immediately but
with a 1-space gap. This is actually a CSO effect!
Middle: A=gwall, B=Rockford
The counter-example of the right part of the "type +" picture. If Rockford has
a gwall on his left side and moves, the gwall cannot immediately follow him,
which means that here it's possible to "smuggle" a third element through
before it's blocked!
Right: A=boulder, B=firefly

Negative dependance is also the reason why Rockford can not switch sides
from left to right in the aforementioned BD1-cave I scenario!


Sub-subchapter I.1c): A special case - boulders/dias falling sideways
The attentive reader will have noted that so far, I (almost) excluded the
possibility that boulders fall sideways from other boulders, diamonds or brick
walls. This is because they deserve a special consideration as they have two
unique properties:
Image
1. A boulder/diamond falling sideways needs empty space not only where it
wants to move, but also below that place (see the dots in the picture!).
2. Also, it needs a boulder, diamond or brick wall as an "underlay" below it.
This means two more detections than usual for the movement! This allows
two special types of movement-based CSO effects, as shown in the following
pictures:
Image
The first one is a striking one: The boulder detects space to its right/left and
bottom-right/bottom-left side, so it moves right/left, intending to fall down
into the other empty space next frame. But simultaneousely, the bottom
space is blocked by another element, so the boulder cannot fall down next
frame. If only the boulder had known that before, it would never have started
moving! :D
Left: A firefly blocks the boulder, which means it is crushed next frame. (This
happens due to a slightly strange BD engine rule: when the boulder moves
right, it's already given the "falling"state though it hasn't really fallen yet!)
Right: A very funny effect with a gwall: the boulder just moved right, as if it
was pushed by a ghost! Thereby, it has moved away from the left border so
Rockford could now push it on to the right!

The next picture shows the other special CSO effect with boulders/dias falling
sideways:
Image
This looks less spectacular, but it's still a CSO effect: The diamond falls
sideways from the boulder, which moves away in the same frame. Had the
boulder been scanned first, the diamond would no longer have its "underlay"
and wouldn't have acted the same way.

So that's it for the purely movement-based 2-element CSO effects! While
writing this, I got an idea for a new CSO cave, which I want to try out
immediately :D See you in the next episode, where explosions will be the
main theme! :bye:

EDIT: Logic, I just noted that I had overlooked one of your posts, I'll answer it soon!
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: 556
Joined: Sun Sep 23, 2007 1:15 am
Location: Erlangen, Germany

Post by Dustin »

LogicDeLuxe wrote:Open borders are a topic on its own, especially since there are several different implementations, and none of them is perfect. There is no official way, since the original game didn't have this feature.
Ideally, as far as CSO is concerned, it should only effect elements which set flags between frames, ie. amoeba for its status and resetting counter. In every other regard, the borderless world should be viewed as seamless instead of frames, which is what they physically would do in a perfect implementation. The catch is the representation of a particular moment, which can't be seamless, as it is still a frame.
Yes, that's true of course. I have most experience with Krissz's OB implementation, which goes basically as follosw:
1. The cave is scanned in the same order as without open borders.
2. Visually, the open border caves look like an endless open world.
3. There are a few special rules with the intention of reducing discontinuity effects on the OB.
So I'll mainly focus on this implementation when it comes to this chapter, but I also want to mention some other implementations as far as I know them.
LogicDeLuxe wrote:You also may consider some Diego effects, especially when an explosion, a boulder or a diamond converts into amoeba. The particular way the original engine handles overgrown amoebas does matter in this regard. The code snipped of PLCK above shows, that it uses the actual count byte from the previous frame to decide between boulder or diamonds to convert. This will lead any newly produced amoebas in later games to convert to diamonds, as if the amoeba was suffocated, due to the previous frame's count being 0. This behavior is probably not copied much, if at all, as it ins't exactly the most efficient way to make the decision for every single piece of amoeba. Personally, I encode the element the amoeba shall convert to in the next frame into the status byte.
This would be interesting, but I'll stick to my rule to only consider classical elements (and effects) for the investigation, as otherwise the thread could expand to 100 pages or so... :D
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: 556
Joined: Sun Sep 23, 2007 1:15 am
Location: Erlangen, Germany

Post by Dustin »

Episode 5 - CSO effects with explosions

Sub-chapter I.2: Explosions
There are five (classical) pairs of "deadly enemies" which explode when
touching each other (where I united fire-and butterflies as "flies", and falling
boulders/dias):
Fly explodes when next to Rockford
Fly explodes when next to amoeba
Fly explodes when next to voodoo*
Falling boulder/diamond explodes when above Rockford**
Falling boulder/diamond explodes when above fly**

*That's a special case because "kill Rockford" is activated. This is dealt with in
another chapter.
**Note that, although the falling boulder does the explosion, the center of the
explosion is Rockford/the fly.

The left element is the one which does the explosion (i.e. it's in the
cavescanner when the explosion happens; I'll call it the "exploder"), the right
element is the detected one (the "trigger"). Note that when the right element
is scanned and detects the left one, no explosion happens! This fact is used in
our first sub-subchapter:

Sub-subchapter I.2a): Explosion check
Definition (type "-"): A given map M includes two deadly enemies
A<B, where B is the exploder and A the trigger. A and B touch each other, but
A is ready to move away from B, and as A<B, it can actually do so before B
explodes.


Variant: A given map M includes two deadly enemies A<B, where A is the
exploder and B the trigger. A and B don't touch each other yet, but B is ready
to move closer to A so it would then touch A. However, A moves before B, so
no explosion happens.


Examples:
Image
Oh, I actually forgot the green and red connection lines. Remember: the
above picture is the initial map M, the bottom-left pic is the resulting map one
frame later, and the bottom-right pic is the inverted map that would result if
the cavescanning order was reversed.
Left: A=Rockford, B=firefly. Rockford touches the fly from left, so he's
scanned first and escapes before the fly explodes.
Right: same thing, this time Rockford touches the fly from above. In fact, in
our above definition A=Rockford is the only possibility with classical elements!
:D

Unfortunately I forgot to make pics showing the variant. Such an example would be:
DDDDD
SSFSS
SSSRS
DDDDD
where S=Space, D=Dirt, F=Firefly facing right, R=Rockford moving left.
The fly is scanned first and moves closer to Rockford. When Rockford is
scanned, he does not explode because he's the trigger. He moves left, thereby
safely passing the fly.

Definition (type "+"): A given map M includes two deadly enemies
A<B, where A is the exploder. A and B touch each other. B is ready to move
away from A, but as A<B, A explodes anyway.

Variant: A given map M includes two deadly enemies A<B, where B is the
exploder. A and B don't touch each other yet, but A moves first and touches B
afterwards, so B explodes although it was ready to move away from A.


Examples:
Image
Left and middle: A=Firefly, B=Rockford. If Rocky touches a fly from right or
below, there's no chance to escape anymore.
Right: A=Falling boulder, B=Firefly. The fly is ready to move away, but the
boulder is scanned first and explodes the fly. Knowing this defines the right
timing for situations such as in BD1, intermission 1, where Rockford tries to
kill a butterfly with a boulder!

An example of the variant:
DDDDD
SSRSS
SSSFS
DDDDD
It's not advisable for Rockford to move right here, because then the fly would
detect him and explode!

Sub-subchapter I.2b): Escape an explosion
Definition (type "success"):A given map M includes two elements
A<B. B touches his deadly enemy C, where B is the exploder of the two. A is
currently in B's explosion range but moves out successfully before B
explodes.

Type "failure": Same as above, except B<A, which means B explodes
before A can escape.


Examples:
Image
Left: A=Rockford, B=Falling boulder, C=Firefly (success)
Rockford escapes out of the firefly's explosion range before the explosion
happens.
Middle: A=Diamond, B=Firefly, C=Amoeba (failure)
The diamond tries to fall out of the fly's explosion range but fails because the
fly is scanned before.
Right: A=C=Amoeba, B=Firefly (success)
A special case. The firefly is about to explode because of the amoeba, but the
amoeba is scanned first and has a tiny random chance to grow out of the
explosion range and survive.

t.b.c.
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: 556
Joined: Sun Sep 23, 2007 1:15 am
Location: Erlangen, Germany

Post by Dustin »

Episode 6 - more explosion effects

Sub-subchapter I.2c): Move into an explosion ("suicide")

Definition (type "success"): A given map M includes two elements A<B, where B is about to explode because of its deadly enemy C. A is currently out of B's explosion range but moves in before the explosion happens.
Type "prevented": Same as above, except B<A, so that B explodes before A can move into the explosion range.

Examples:
Image
Left: A=firely, B=falling boulder, C=firefly (success)
The left firefly (A) is scanned before the falling boulder (B) and moves into the explosion range before the explosion happens.
Middle: A=left firefly, B=falling boulder, C=right firefly (prevented)
This time the left firefly is scanned after the boulder, so the explosion happens before the left fly can move in.
Right: A=butterfly, B=firefly, C=amoeba (success)
The butterfly moves closer before the firefly explodes. Note that the "explosion check" issue (see last episode) is also relevant here, as the amoeba is scanned before the butterfly but does not explode (which would prevent the butterfly from "committing suicide".)
In the last two sub-subchapters, two explosions are relevant inside the same frame:

Sub-subchapter I.2d): One explosion prevents another
Definition: A given map M includes two elements A<B, both of which are exploders and about to explode because of their deadly enemies C and D. A explodes first and thereby crushes either B or D, so that the second explosion does not happen.
A variant is B<A, so that actually both explosions happen.

Examples:
Image
Left: A=left firefly, B=right firefly, C=D=amoeba
The left firefly explodes first. This destroys the amoeba, so when the right firefly is scanned, it has no reason to explode anymore!
Middle: A=top-left firefly, B=bottom-right firefly, C=amoeba, D=Rockford
Another way how Rockford can survive touching a firefly - the fly is destroyed by a previous explosion in the same frame!
Right: A=bottom-right firefly, B=top-left firefly, C=amoeba, D=amoeba
An example for the variant: the second explosion would prevent the first, but not vice versa, so actually both explosions happen.

Sub-subchapter I.2e): Overwriting
Definition: A given map M includes two exploders A<B which are about to explode because of their deadly enemies C and D. Both explosions take place closely, so that B's explosion partly overwrites A's.
Of course, the overwriting only makes a difference if A and B explode into different objects - one into smoke, the other into diamonds.
Examples are therefore limited but striking:
Image
A=falling boulder, B=falling boulder, C=butterfly, D=firefly
The left explosion happens first and gives nine diamonds. However, the second explosion in the same frame overwrites three of these diamonds with explosion smoke, so 3 diamonds get lost!
This CSO effect gave me the idea for a cave which is analyzed in episode 34 of the other CSO thread!

In the next episode, we'll see CSO effects where Rockford uses his ability to snap instead of moving, which can, for example, clear the space for another element to move!
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