A perfect Open Border implementation – does it exist?

[LogicDeLuxe]

Just one thing about this issue

Well, the scanning has to start somewhere. Which gives me the idea that the exact starting position could be specified as a cave parameter. In your example, you would just specify the space between your Fireflies as the starting point, and they will never turn.
On the other hand, a starting point parameter is not really necessary, if the cave's author just take the given starting point into account. In your example, you just would place the Space at the top instead of the middle of the Fireflies. It doesn't really matter where the Space is, since it will be always at the scanning position after the current Firefly moved anyway, thus you would only really see it when the scanning takes a break waiting for the cave delay.

[Arno]

Hmmm... setting the empty space equal to the starting point of the cavescan solves this issue for the first frame, but does it also arrange that the 6 fireflies keep moving upward "forever"? I think not, unless for each frame, a custom starting point for the cavescan is used, namely the current position of the empty space. But how does the algorithm know that it must start at that position?

Thinking about this issue I came up with another extended example (6x6):

LUwUwU
wUwUww
wxwULU
wUwwwU
wULUwU
wwwUwU

This is a sort of infinite tunnel filled with a "snake" of fireflies and one piece of empty space.
Now the dependency chain runs 2 times over the cave width/heigth. Intuitively (thinking about an infinitely repeating world) it is clear for me what should happen: all fflies should move up or left, so the whole "snake" of fflies should move 1 position through the tunnel each frame, and so the empty space moves 1 position in the opposite direction.

But how to design an algorithm that does exactly that? Parallel Universes does not work in this case unless you extend it to 5x5 copies instead of 3x3. But then you can construct a similar/bigger example where 5x5 does not work either...

Perhaps the problem is just that infinite worlds can exist in a human mind, but not in a computer's storage...?

[LogicDeLuxe]

all fflies should move up or left, so the whole "snake" of fflies should move 1 position through the tunnel each frame

That is broken by design. You should know that's not how Fireflies work. They turn in place from left to up and blocking the following Flies by that. Try a formation like this on a regular world without wrapping, and you'll see.
And even if that design would work, you would need two spaces, since you're wrapping twice.

and so the empty space moves 1 position in the opposite direction.

The Space would not "move" 1 position, but it would rapidly go with the cave scan. You would see it where the scanning takes a break waiting for the cave delay, ie. at the bottom of the cave. You shouldn't think of empty space as "moving". It may look like it in certain situation, but it doesn't do anything on its own. Also, in an endless world, there is only once a starting point, not per frame, since the scanning is continues. Naturally, you're always one step ahead from the last scan, doesn't matter if it is on the border or in the middle of the cave. This lag has to be taken into account during design and it is easy to forget.

It's like in "Around the World in 80 Days" where they gained an extra day. Similarly, in Boulder Dash, if you're going down, you're gaining extra cycles, ie. the items scanned between intervals is the size of the cave plus the distance your moved. Those sum up to a complete scanning interval when you did an entire round eventually.
While there is an imaginary international date line, it is nothing physical. Think of a scanning interval as a day cycle. In Boulder Dash, this international date line is between the bottom and the top of the cave.
A day cycle doesn't really have a starting location. It's just continues around the world, yet not every place is at the same day simultaneously. It is certainly an effect flight schedules have to take into account, and so have cave authors.

Maybe it's a better exercise to examine how dancing fly formations would pass the borders.

[Arno]

That is broken by design. You should know that's not how Fireflies work. They turn in place from left to up and blocking the following Flies by that.

Oh sure, you're right. I forgot about the fireflies turning right at the same position in a bend to their right. So my expectation holds only for the single next frame.
If a certain frame looks like this:

LUwUwU
wUwUww
wxwULU
wUwwwU
wULUwU
wwwUwU

then, I would expect the result of the next frame to be:

LUwUwL
wxwUww
wUwLLU
wUwwwU
wLLUwU
wwwUwU

So all flies have moved one position. This because in an infinitely repeating world, there would be infinitely many "snakes" of 17 connected fireflies, which together move 1 position. Also, I see that it would work like that when "Parallel Universes" is applied with 5x5 copies (instead of 3x3).

It's like in "Around the World in 80 Days" where they gained an extra day. Similarly, in Boulder Dash, if you're going down, you're gaining extra cycles, ie. the items scanned between intervals is the size of the cave plus the distance your moved. Those sum up to a complete scanning interval when you did an entire round eventually.
While there is an imaginary international date line, it is nothing physical. Think of a scanning interval as a day cycle. In Boulder Dash, this international date line is between the bottom and the top of the cave.
A day cycle doesn't really have a starting location. It's just continues around the world, yet not every place is at the same day simultaneously. It is certainly an effect flight schedules have to take into account, and so have cave authors.

I think I got your points about the continuous scanning. I'm just wondering, would this method also work correctly when there are both vertical and horizontal open borders (like at Krissz' site)? I see how it works with C64-style of open borders, where the end of a line continues at the next line, so effectively there are only borders at the top/bottom of a cave (which could be "eliminated" by a continuous scanning). But I'd guess it won't work when there are vertical borders too, because of the jump to the next line at the end of each line...

Maybe it's a better exercise to examine how dancing fly formations would pass the borders.

Since dancing fly formations are usually small sized, I would expect that a method like "Parallel Univeses" would arrange that a formation just passes a border without side effects. (At least when the cave is bigger than the formation itself.) Do you see any scenario that might give issues?

[Dustin]

Hey professors!
Inspired by some side effects with the OB implementation at Krissz's site, this topic started to interest me, so I read everything carefully.

One basic question that comes to my mind is: what is a "perfect OBI"? For every given map, do you have a clear answer to the question what should be the next frame's map if the OBI is "perfect"?

Arno, your examples so far look to me very much orientated at the "infinite open world" idea. I, too, like this idea a lot (the visual aspects at Krissz's site, scrolling over the open border, are fascinating to me - on CLCK/GDash, I always disliked the fact that on the open border, you could never see where your intended next step would lead, though, of course, also these OBI's are great and much thought of! I just think that what Krissz did is the logical next step!)
So my following ideas are also based on the "infinite open world" idea.

What is "the perfect OBI" anyway?
My basic idea could hardly be simpler:
If what we see is part of an infinite open world, then the dynamics should also work exactly as they would do in this very world!
Of course, this immeidately gives an obvious problem: no engine in the world can scan an infinite open world in finite time. In fact, even if it could, it still is not clear where the scanning should start. So here's my next idea:

If we look at the idealistic infinite world as a limit of infinitely many finite worlds, that could be the "bridge" for a realistic realization.
Let "World 1" just be the normal cave map, "World 2" shall be a 3x3 parallel universe (according to Arno in previous posts in this thread), ... "World n"= a (2n-1)x(2n-1) parallel universe. I think it's fair to assume that our idealistic infinite world could be the limit as n goes to infinity.
Now, let's start scanning World 1 (assuming naive open borders) and create the next map. Then, let's scan World 2, 3... etc. and always take the central map, just as Arno suggested. Intuitively, I think there should be some n from which on the resulting map does not change anymore. And this map is supposed to be the "perfect OBI" map for the next frame!

Of course, there are some open questions with this approach:
1. Does such a n really always exist?
2. If so, how big can this n be in relation to the cave size? Is it potentially too big for a practical realization?
3. Is the approach really "perfect", i.e. are there never any visible side effects close to the open border?

All this is just a rough first idea of mine, but I think I'm going to check out what will happen to the "test maps" that were already investigated in this thread. and if the results make sense...

[Arno]

Thanks Dustin for joining this thread! Some fresh ideas are what this thread needs, I think!

If what we see is part of an infinite open world, then the dynamics should also work exactly as they would do in this very world!

That's exactly my idea too, and I couldn't think of any way how this definition might be nonsensical or ambiguous...

Of course, there are some open questions with this approach:
1. Does such a n really always exist?
2. If so, how big can this n be in relation to the cave size? Is it potentially too big for a practical realization?

Until now I have mainly focussed on firefly-chains. If such a chain spans the full width of the cave multiple times, in the form of a spiral, then obviously you need n>2. For example, if the cave is 100x100 then I imagine the firefly-spiral could cross the cave about 50 times, so for a correct working you need about n~50.

However, if performance would be a problem, I would say n=3 (which gives a 5x5 parallel universe) is already quite on the safe side as you really need to do your best to construct a failing scenario.

3. Is the approach really "perfect", i.e. are there never any visible side effects close to the open border?

Well, I think this method solves at least all side-effects that we have spotted at Krissz' site so far. But I haven't thought deeply about dependency chains other than lines of fireflies yet. For instance, events affecting the cave at a non-neighbour location: voodoos killing rockford, magic wall stopping amoeba, etc... Also, parhaps very small caves (e.g. 2x2) might show issues...

[Dustin]

Thx for the welcome confetti!

That's exactly my idea too, and I couldn't think of any way how this definition might be nonsensical or ambiguous...

Well, I do see a potential problem with it. Or, more precisely, not with the idea itself, but with its interactions with other plausible assumptions, such as consistency in terms of the number of each object. I considered one of your previous maps:

xUxUx
xUxxx
xULLx
xxxUx
xExUx

Where,
x = wall
E = empty space
U = firelfly pointing up
L = firefly pointing left

If you play this map and see an infinite world around it, then the only plausible next map would be the one you already found out:
xUxUx
xUxxx
xLLLx
xxxUx
xUxUx
One firefly has left the map but two new ones have entered. The number of fireflies has increased! Why? Well, the thing is that if you consider a big (but finite) world, say 55x55 where this map is copied 121 times, the fireflies would tend to move away from the edges and into the middle. If we note this as a fact, it's clear what the problem with an idealized infinite world is: there is no "edge" where the flies could come from, but still we don'T want any "new" flies to enter the scene, so it's actually not so clear how the map should develop. Either we have to live with the number-of-flies inconsistency or with flies that do not move as expected - so I guess that in idealistic terms (as given in the title of this thread) we've already reached a dead end here, or, to answer the question in the title, a "no"...

In practical terms, however, this might not be so severe, as normal caves are a lot bigger and dependency chains throughout the whoule cave occur as good as never, so the general parallel universe idea could still be kept alive and we could have fun constructing caves that show the rare inconsistencies...

[Arno]

If you play this map and see an infinite world around it, then the only plausible next map would be the one you already found out:
xUxUx
xUxxx
xLLLx
xxxUx
xUxUx

Well, actually I get the above map when I apply the parallel universe method for n=2 (so 3x3 where only the middle column is relevant here), but assuming a closed border implementation is applied on the extended map.

When using parallel universe with n=2 plus the naive OBI instead, I get the following map:

xUxEx
xUxxx
xLLUx
xxxUx
xUxUx

This map has the same number of fflies, so it is ok in this sense.

Since the first ffly on the top line of the extended map moves to the bottom of the extended map (thanks to the naive OBI), all other fflies in the same sequence move one position (up or left). This results in an empty space at the end of the tunnel, which is at the top right of the central map.

To be clear, the 3x3 repeated world only exists for one frame. For the next frame it is re-created again based on the resulting central map from the previous frame. So whenever the naive open border affects something at the border of the extended map, it can only affect the central map when there is a dependency chain that runs over a single frame (like a line of fireflies). So we don't have to worry about effects that eventually (i.e. after multiple frames) arrive at the central map.

So in my view, for this specific example, it is quite clear what to expect for the next frame in an "infinitely repeated world". In fact this example is quite simple because it consist of a finite S-shaped tunnel filled with fireflies and 1 piece of empty space. But maybe I just didn't get some key point in your explanation...?

EDIT: I do think there are examples with multiple plausible outcomes. I have some ideas but will have a closer look later. But in this particular example, I think there's just one: that all fireflies move one position.

[Dustin]

You're right! I just misconstructed something So actually, the idea of perfection might still be "hot"...

Also, I think that the "MW stops A" issue should be relatively simple to deal with. If a new map has an activated magic wall in it, the engine marks that in the next frame, every amoeba converts. The only important thing I can see is that the mark happens only at the end of a frame, so that an activated magic wall in one parallel universe doesn't affect an amoeba in a different universe. The same should also go for voodoos, I think...

[Dustin]

So here's my idea for a (close-to) perfect OBI (at least in theory):

1. Create the next map with a simple, naive OBI implementation.
2. Now, independant of step 1, create the new map by using a 3x3 Parallel Universe scanning (also naive OBI).
3. If the maps of 1. and 2. match, then the scan is over and the next map is done.
4. If not, do a 5x5 PU scan and see if the result matches with the 3x3 result. If so, this is the next map. If not, ... and so on.

Theoretical problem: As long as we can't prove that the algorithm is always finite, there might be scenarios without a new map.

Practical solution: The algorithm might halt after at most n steps, for some n (small enough not to give performance problems, big enough to run well for every cave that isn't designed especially to show the imperfectnesses)

How about this?

[Arno]

How about this?

I think this is the way to go indeed. For a constant performance, however, I would rather just apply the method for the selected maximum feasible steps directly, rather than trying n = 1, 2, ... max. steps until 2 successive steps give identical result. Also, I would be surprised if there is a case where, for instance, n=3 and n=4 give the same result while n=10 gives a different result... so why not use n=10 from the beginning?

Talking about performance, another way I had in mind to reduce calculation times is the following:
Suppose n=3, so the method creates 5x5 copied maps as follows

Code: Select all

 1  2  3  4  5
 6  7  8  9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

Now instead of taking the middle map (no. 13) as the resulting map, take map no. 19 as result. Because dependency chains from the right or bottom side to the middle seem (to me) hard to construct, this might be just as good as n=4, while only 25 copied maps need to be scanned instead of 49. I'm not 100% sure yet if this reasoning is correct, but it's someting to consider...

Now back to the question whether a perfect OBI exists:
I found an example of a map which has multiple plausibe result maps for the next frame:

wRE
UwU
UUw

Where, w = Wall, E = Empty space, U/R = Firefly pointing Up/Right.

How does this look in the infinite repeating world?
Well, we see a pattern of infinitely many diagonal (stair-shaped) tunnels filled repeatedly with:
- 4 fireflies pointing Up
- 1 firefly pointing Right
- 1 empty space

When I apply parallel universes (for any n >= 1), I get the following result:

wER
RwR
RRw

In other words, the original Empty space is occupied by the firefly which originally pointed Right. This ffly in turn blocks the remaining fflies which therefore change their direction to the Right.

But now suppose that the original map is represented like this:

UUw
wUU
EwR

In the infinite world this looks exactly the same as before. However, when I apply parallel universes (for any n >= 1), this time I get:

LUw
wLU
UwE

Now the original Empty space is occupied by the first Upward pointing firefly, which causes the remaining 4 fireflies to move one position (left or up).

So here we have 2 maps which are the same in the infinite world, but give 2 different maps for the next frame. Which of the two is "correct"? Well, I'd say for a BD player both results are plausible: there are no flies (dis)appearing. Also, to me, none of them is preferable over the other. In the infite world there is no start of cave scan, so it is undertermined whether the Upward or Right pointing fflies will occupy the empty space. You cannot say, for instance, that all R-flies are scanned before all U-flies or the other way around.

Practically, I'd say it is completely fine that the chosen representation determines the outcome. But for the question on the existence of a perfect OBI, I would suggest that a near-perfect OBI is the best we can get.

[Dustin]

Interesting stuff, the practical approach as well as the theoretical one!

I'll try to summarize the
Idea for a practical OBI
1. Basic Rule:
Each frame, instead of just scanning tha map, copy the map n² times (where n is odd) and extend it to a nxn "parallel universe" world. Then scan this world in the usual order and take the central map as the resulting map for the next frame. EDIT: Scan the extended map assuming naive open borders!

2. Aims/Advantages:
Normally, the open borders would be discontinuity lines where the cavescanning order is different, so there are unusual/unexpected effects close to the open borders. With our Basic Rule above, these discontinuity lines would be far away from the central map, so in the vast majority of cases, we could expect usual BD behaviour also close to the open borders.

3. n=?
In the vast majority of cases, n=3 should be absolutely sufficient. Counter-examples include dependance chains throughout the whole cave, and these will as good as never occur in "normal" caves (i.e. caves which aren't designed especially to show new strange effects of our new OBI). Of course, there's nothing to say against bigger n, as long as the engine performance isn't affected.

4. What about random effects?
Random effects (amoeba, boulder pushing, slime) should be identic in all of the n² parallel universes. Otherwise, a random effect close to (but outside) the central map could influence the dynamics inside the central map, which obviously makes no sense if the same random event isn't visible inside our central map as well. So all random decisions the engine makes in the top-left parallel universe should be memorized and repeated in all other universes for the same frame.For example, if a certain piece of amoeba grows upwards in the top-left parallel universe, the same piece of amoeba should also (try to) grow up in all other universes. If this is not possible in any universe, the piece of amoeba just doesn't grow at all. This way, we have ensured that all parallel universe truly develop due to the same rules, so that everything that happens in the central map can be explained because of other happenings inside the same map.
And BTW, though this is not a random effect, but the multiple Rockfords should also act all the same way (according to the player's input)!

5. What about happenings that affect the whole cave rather than only close elements?
That's an important question because the main advantage of our Basic Rule was to fix open border effects that occur when two elements touch each other over the open border. Luckily, 90% of Boulder Dash works this way - whenever an element is scanned, its behaviour depends only on what's going on in close proximity. However, there are a few exceptions:
a) If a voodoo is killed, the engine wants to kill Rockford, too (wherever he is).
b) If a MW is activated, it stops the amoeba even if it's far away.
c) Amoeba tuning into diamonds/boulders when trapped/overgrown.
d) Last but not least, sound effects!

To keep all parallel universes "syncronized", such effects should be postponed until the end of the actual frame. This means:
a) If a voodoo is killed, the engine should only start killing Rockfords in the next frame (which it usually does, anyway). AND it should do so only if a voodoo in the CENTRAL MAP was killed! Otherwise, consider the following map with F-ireflies, V-oodoo, D-irt, B-oulder (falling state), R-ockford:
DFFVD
DDDDD
DDDRD
DBDDD
With 3x3 parallel universes, the top-left voodoo is killed but the central one survives, so Rockford should survive as well!
b) If a MW is activated, the engine should also wait with the amoeba-turns-into-diamonds-stuff until the next frame. (Also here, the decisive question must be if a MW in the CENTRAL MAP was activated!)
c) I don't know how exactly this is usually programmed in the engine, but what seems plausible to me for our OBI is the following:
c1) Whenever an amoeba inside the central map is scanned and ABLE to grow, the engine activates an "alive" checkmark for this frame. If, at the end of the frame, this checkmark was not activated, the engine concludes that the amoeba is trapped and, next frame, starts to convert it into diamonds.
c2) After the normal scan, a second cavescan is made only to count the amoeba pieces inside the central map. If it has overgrown, then in the next frame, all amoebas are converted into boulder..
d) Only explosions etc. inside the central map should make any sound effects.

6. Potential weaknesses:
a) Dependance chains throughout the whole cave could cause "magic" effects like increasing the number of fireflies or something. However, this should happen only if there are long dependance chains throughout the whole cave.
b) Also, while writing this, 5. started to seem more problematic to me than I originally thought. But also here, some unusually long dependance chains should be necessary in order to create any problematic effects.

All in all, I think the advantages clearly outvalue the potential problems for normal caves that just want to use open borders without side effects. And the fact that such an OBI might motivate cave creators to show each and every strange side effect with carefully created caves would add to the fun rather than spoil it imo! On the other hand, it looks like it's a lot of programming work...

[Arno]

I think this is a very good summary of the method and its pros/cons!

Just one note. I would add to the "Basic Rule" the use of the naive open border scanning. This makes the method just more robust for dependency chains throughout the cave, but with limited extra programming effort.

[Dustin]

Thx Arno! Oh yes, I just forgot to mention that. I edited this and some other minor things

BTW, I'm still reflecting upon the perfection issue...

[Arno]

Great! Now the overview looks quite complete to me, in particular the random and distant events. Also the sound effects are a good mention, indeed.
Thank you so far for filling in those details which I hadn't thought about deeply yet!