A perfect Open Border implementation – does it exist?

[Arno]

A perfect Open Border implementation – does it exist?

This is a topic I’ve been pondering about several times. Some Boulder Dash engines allow for open borders. That is, when a movable item (Rockford, boulder, firefly, etc…) leaves the cave at a border, it returns at the other side, so effectively the cave behaves like an infinitely repeating world.

Until now, the open border implementations that I have seen all have some strange side effects, where at the border the BD engine behaves slightly different than in the middle of the cave.

The main question that I’d like to pose here is:
Is it possible to develop an open border BD implementation without side effects, and if so how would the algorithm work?

I’m curious to hear your views (especially from BD developers ). So if you have any ideas, or comment on mine, please chime in!

Before I share my ideas, I’ll first describe two different existing open border implementations, how they work, and what kind of side effects I have observed.

1. CLCK-engine (commodore 64):
The open border feature works whenever the border is not occupied by t-walls or other unmovable items. When Rockford leaves the screen, the game pauses for a moment while the “camera” scrolls to the other side of the cave, after which Rockford appears and the game continues (video).
Also important to note is that in this engine the cave maps are stored as an array (rather than a rectangular grid or matrix). So when Rockford leaves at the right border, he returns at the left border on the next row. Similarly, a dancing fly formation moving to the left will also slowly move up (video).
I guess that in this implementation the cave scanning works by simply looping over the single array. Then, clearly, there are no side effects at the left and right border, since the behaviour at these borders is not different from any other place. But: at the top and bottom borders there are some side effects. For example, dancing fly formations usually break when they cross these borders.

2. Krissz’ site (online BD remake):
In this implementation, the open borders are optional and can be disabled/enabled in the editor. This can be done for the vertical border, the horizontal border, or both. The gameplay depends on the size of the cave. If the cave fits on one screen, then no scrolling happens and any item leaving at one side just returns at the other side (video). If the cave is bigger, the game scrolls continuously, so crossing a border happens unnoticed and for the player the cave really looks like an infinite world (video).
As opposed to the CLCK-engine, cave maps are stored as a rectangular grid, so any item leaving at a border will just return at the other side (without shifting a row like in CLCK).
As I understood, the cave scanning algorithm for open border caves is quite complex and Krissz has spent a lot of time to minimize the amount of side effects (which I admire and appreciate a lot, by the way). Still we have seen some remaining side effects like the following:
- Amoeba converts to diamonds while not fully enclosed at the border.
- When a butterfly moves down along a falling boulder it is crushed by the boulder when it hits the bottom border.
- Dancing fly formations mostly break (or they miraculously continue in another direction along the border ).
- Finally, I’ve spotted a side effect, which does not occur specifically at the border but rather affects the whole cave: when Rockford snaps dirt downward, the item to the right of this dirt moves first, while normally the left item moves first because it is scanned first.

Of course, side effects like above are not a big problem. In most cases, the gameplay works fine, so open borders are just a great feature. Yet, these observations have challenged me think about a possible cave scanning algorithm, which solves these issues such that the behaviour at the border is not different from any other place in the cave.

With the Krissz-variant of open borders as the target feature (so cave maps are rectangles, not arrays), I currently have 2 ideas which I will share in next posts…

[Arno]

Idea 1: The Sledgehammer

This was the first idea that came to my mind. Good thing about it is that it guarantees that there is no different behaviour at the borders. This is because every position in the cave is treated the same way, so effectively there are no borders at all.

The basic idea is:
Instead of scanning the cave 1x per frame, a separate full cave scan is performed for every position in the cave as if it is a position in the middle of a cave.
Suppose we have a 5x5 cave with positions numbered 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

For one frame, the resulting cave map for the next frame is determined as follows:
- First scan the cave row-by-row starting at position 1. Then put the resulting item on position 13 (which is the central position) on position 13 of the final map after the frame.
- Next scan the cave using position 2 as the top-left corner, so the first row is 2, 3, 4, 5, 1, the second 7, 8, 9, 10, 6, et cetera. Then accept the item at position 14 (the central point) on the final map.
- Repeat this procedure until all 25 positions have been the top-left corner as starting point for a specific cavescan. This way all items on the final map result from a cave scan in which they were located at the centre of the cave map.

Of course, these are a lot of cave scans. For example, if a cave is 100x100, then 10,000 full cave scans are needed for each frame. I’m not sure, but perhaps (depending on the hardware) this amount of work will slow down the game significantly…

But apart from these potential performance issues, there are some functional issues as well.
Suppose the cave consists of walls, except for one line, which consists of fireflies pointing left (L) and one piece of empty space (x):

LLxLL

Starting the scan at positions 1 to 5, this gives the following configurations (where U is a firefly pointing up). The bold items are at the central position (from the perspective of the starting point) and therefore accepted on the final map:
1: UULLx
2: xULLL
3: LxLLL
4: LxLLL
5: UULxU

This gives on the final map, for this line:

LULLL

Oops… now a line with 4 fireflies has been magically transformed to a line with 5 fireflies. Clearly not expected BD behaviour…

In conclusion, this algorithm is not the perfect open border implementation, since there exist side effects on the whole cave.

I have a second idea which I will post later.

[Arno]

Idea 2: Parallel universes

This is an idea I have a good feeling about. I’m curious what you guys think about it.

Basic idea:
Instead of scanning just the cave map, scan a way bigger area consisting of the current cave map surrounded by 8 copies of the same map.

Suppose that (again) we have a 5x5 cave.
Given a certain frame and its current map, determine the map for the next frame in 3 steps:
1. Create an internal 15x15 grid representing 9 exact copies of the map of the current frame, numbered as follows:

Code: Select all

1 2 3
4 5 6
7 8 9

2. Scan this 15x15 map in the usual way (without open borders).
3. Take the central 5x5 area (= map number 5 in the above scheme) as the resulting map for the next frame.
Repeat these steps each frame. That’s basically it.

This method solves at least the problem mentioned in previous post. Suppose again that the cave consists of walls, except for one line, which consists of fireflies pointing left (L) and one piece of empty space (x):

LLxLL

The internal grid with the 9 copies (step 1) will contain the following line (using bars | to indicate the copies):

LLxLL | LLxLL | LLxLL

Scanning this line from left to right (step 2) results in the following line (where U is an upward pointing firefly):

UULLL | LxLLL | LxLLx

Taking the central area as the resulting map (step 3) gives for this line:

LxLLL

This looks plausible. No fireflies have (dis)appeared. The empty space just moved one position to the left, which seems usual BD behaviour for a player.

So, this idea seems promising to me. Please let me know if you can find a configuration which gives problems when using this method. Until now, I couldn’t. My gut feeling: if there are problems, they probably occur for very small caves (like 2x2).

Lastly, one side note:
When in step 2 the cavescan goes through the areas 1-9, any random stuff should work the same in all 9 instances. So, for example, if Rockford successfully pushes a boulder in area 1, this should also happen in areas 2-9. The same holds for random events with growing amoeba and slime. This should technically be possible (just remember and reuse the random numbers which determine the outcome of random events).

[Arno]

Based on some feedback on my second idea "Parallel Universes" (from Nesdori at Krissz' site), I'd like to make one change to this method:

Instead of scanning the extended map in step 2 in the normal way (without open borders), I propose to use a naive open border scanning algorithm at this step. That is, the scan takes place row by row, from top to bottom, and from left to right, but when scanning an object at a border, the neighbour objects at the other side should be taken into account. For instance, a firefly at the left border should be able to move to the other side, ending up at the right border.

Without this change, it is quite easy to handcraft a dependency chain from the left or top border to the central cave map, such that unexpected behaviour will occur in the central map. For example, a firefly entering the central map without one leaving at the other side.

By using a (naive) open border scanning, such dependency chains are more difficult to construct as they must exploit a discontinuity issue in the naive scanning method.

[LogicDeLuxe]

Parallel Universes seems a bit over the top.

Let me explain the compromise way we did it on the C64 first:
What I did it in XDC is copying the 2 topmost and the bottom lines at the other end of the array, then do the scan, and finally copy back the items marked moved into the actual cave array. Prof. Knibbles implementation redirects movements, which is necessary for the legacy renderer still in place, but also does the copying before the scan cycle. Both implementations have an imperfect seam, for performance' sake.

I think, the key to the solution is the resetting method of the delay states the C64 uses, ie. it is always done in sync with the scanning 2 lines behind the actual scanning. This combined with redirected movements and detections would allow the scanning on a continues loop making it perfect I think.
As said, this was never fully done on the C64, since it would be quite some overhead slowing down the scanning significantly. On modern systems, that really should be no issue though. Even on C64 turbo boards, that should be very doable.

[Arno]

Thx Logic!

I think, the key to the solution is the resetting method of the delay states the C64 uses, ie. it is always done in sync with the scanning 2 lines behind the actual scanning. This combined with redirected movements and detections would allow the scanning on a continues loop making it perfect I think.

This sounds interesting, but I don't really get it. Could you clarify this method, in particular the terms delay states, redirected movements and detections?

[LogicDeLuxe]

Elements in delay states are those which have moved during the current scan, and it is their to prevent a second movement during the same scan interval. Only XDC has a "scanned" flag for this, as modern ports usually do as well. Other C64/Atari engines have their own elements for this, and they are reset to their non-delayed state using the effect table. Delayed elements are those with the "d" added to their name in BDCFF. Most modern engines do the resetting in a separate loop between cave scans, which is most likely the major cause for imperfect wraparound.

For movements, the physics engine on the C64 does not redirect anything. It is a continues array, and movements are always relative to the current scan position. Since the upper and lower lines weren't scanned in original BD engines, no "access violations" beyond the array could happen.
With redirected movements, the engine would always check if the target is before or after the end of the array, and add/subtract the size of the array accordingly in order to wrap around.

Last thing is the detection. Before the engine desides wether or not to move an element, it has to look for what elements are nearby. Up to 5 checks before a Boulder/Diamond starts to slide off and fall. Explosions have even 8 checks (the exploding element itself does not need to be checked nor redirected). In original C64 engines, this is also always relative to the current scan position. Redirecting that kind of detection would involve the same math as with the movements, sometimes multiple times before an element moves or even don't move. For instance, Fireflies and Butterflies always involve to checks wether they move or not, as they potentially could turn in their preferred direction or move straight ahead. Only when both aren't possible, they turn in place in the other direction.

I hope that clarifies the idea.

And for the delay between cave scans, that pause should be done in the area currently not visible on screen in order to prevent visual artifacts.

[Arno]

Thanks! I think I get the basic idea.
So within each frame:
- Scan an extended area, but instead of using 8 surrounding copies of the full map (like in "Parallel Universes") only copy the bottom 2 lines at the top and the top line at the bottom.
- If an item moves from the actual game field to one of the 3 "copy lines", place it on the correponding location on the actual game field, and mark it as moved (delay state).
- If an item with this mark is scanned it is not allowed to move again.
- With a delay of 2 lines, a second parallel scan resets moved marks from all items.

Am I correct?

Of course this method works for the C64-style of open borders, so only horizontal borders. If we like use this idea on an implementation with vertical borders as well, then I'd suggest that also the 2 right-most columns have to be copied at the left side, and the left-most column copied at the right side.

I tried out the methods on a sheet of paper using the following simple cave:

xUxUx
xUxxx
xULLx
xxxUx
xExUx

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

Using "Parallel Universes" I get the following map for the next frame, which is almost the same as original except that the empty space is now occupied by a firefly:

xUxUx
xUxxx
xULLx
xxxUx
xUxUx

This is clearly a failure since there is 1 ffly more than originally.
Explanation: All flies in the chain move one position; one ffly leave to the top copy field, another enters from the bottom. But, at the location of the empty space, a ffly enters from the bottom, while the top-right ffly cannot leave to the top copy (there the ffly chain ends at the border of the extended map).

Using the method you describe (if I get it correctly), this would give:

xUxEx
xUxxx
xULLx
xxxUx
xUxUx

This seems all right: same number of fflies, and the empty space has moved to the top line.
Explanation:
- When the top line is scanned the upper-left ffy is moved upward to a copy-line and thus placed on the bottom line with moved mark.
- When the bottom line is scanned, this fly is scanned again, but nothing happens since it has the moved mark.
- Meanwhile, all files in the chain have moved one position up or left, as usual.
- When the line below the bottom is scanned, the copy ffly of the top-right ffly moves from the copy-line to the actual gameflield joining the chain at the bottom. Therefore the actual top-right ffly is replaced by empty space.

This seems indeed a very good open border method!

[LogicDeLuxe]

So within each frame:
- Scan an extended area, but instead of using 8 surrounding copies of the full map (like in "Parallel Universes") only copy the bottom 2 lines at the top and the top line at the bottom.
- If an item moves from the actual game field to one of the 3 "copy lines", place it on the correponding location on the actual game field, and mark it as moved (delay state).
- If an item with this mark is scanned it is not allowed to move again.
- With a delay of 2 lines, a second parallel scan resets moved marks from all items.

Am I correct?

That is basically the speed optimized but imperfect way we used to do on the C64.

A simple example of what can go wrong: Imagine an entirely empty cave with Rockford walking on the top border and a Boulder falling through the bottom border. If the Boulder incidentally falls into the same field Rockford has moved during the same cave scan, Rockford would just vanish, since he was one field behind in the copied line the Boulder has seen thus overwriting Rockford inadvertently. I've seen this happening in First Boulder.

The perfect way does not involve copying lines at all, but instead use redirected movements and detections (check for certain elements relative to the current scan position), as described above.
That way, the Boulder would detect Rockford as he has moved already, and decides to explode him.

[LogicDeLuxe]

Thinking of it, those extra considerations are actually only required on the top most line and the last 2 lines, so they could be disabled with self-modifying code for the remaining cave scan on a plain C64 to save time.
Some overhead would be still there though, as the simple zeropage indexed instructions used to deal with this have to go into a subroutine, but I think, this is actually doable. I might give it a try.

[Arno]

Thx, but I still have a few remaining questions to check if I got the method right.
First:

A simple example of what can go wrong: Imagine an entirely empty cave with Rockford walking on the top border and a Boulder falling through the bottom border. If the Boulder incidentally falls into the same field Rockford has moved during the same cave scan, Rockford would just vanish, since he was one field behind in the copied line the Boulder has seen thus overwriting Rockford inadvertently.

So, in simplified form (ignoring the sizes which C64 caves are bound to), such a cave could look like:

xxRxx
xxxxx
xxxxx
xBxxx

With x = empty space, R = Rockford, B = falling boulder, and the user input is "go left".
With the copied lines (as in the "imperfect method") the area to be scanned would be:

xxxxx
xBxxx
xxRxx
xxxxx
xxxxx
xBxxx
xxRxx

But now I actually don't see a problem. Both boulders are scanned before the Rockford on the next line is scanned, so both boulders will fall down 1 step and both Rockfords are just blocked from moving left. The second boulder enters a copy line and overwrites the first boulder (not Rockford), so the end result for that frame would be:

xBRxx
xxxxx
xxxxx
xxxxx

So probably the imperfect method works slightly different than I understood. Why would Rockford vanish?

[LogicDeLuxe]

xxxxx
xBxxx
xxRxx
xxxxx
xxxxx
xBxxx
xxRxx

But now I actually don't see a problem. Both boulders are scanned before the Rockford on the next line is scanned, so both boulders will fall down 1 step and both Rockfords are just blocked from moving left.

The copied lines aren't scanned at all. They are there for detection. In this example, the scan begins in the line with Rockford, thus he is free to go to the left. The last line to be scanned is the one with the original Boulder, which will detect a space under it and starts falling, thus overwriting Rockford.

Including the copied lines in the scan would inherit its own set of imperfections. Imagine, the Boulder will be caught in an explosion. Since the copied Boulder has started to fall already, it will survive anyway.

Btw., you would have two copied lines at the bottom and only one at the top. This is due to explosions' need to reach two lines bellow the current scan position when caused by a Boulder or Diamond.

[Arno]

OK, that's clear for me now! Just two remaining things that came to my mind:

1. I don't see yet why a second parallel scan (with a delay of 2 lines) to reset the delay state (or "moved" mark) would be necessary. Would it make a difference / give problems if this scan were done just after completing the first scan?
Or perhaps it is only for performance?

2. Using this method, I'm wondering what would happen in a scenario with a vertical line of upward pointing fireflies, with one empty hole in the middle? For example:

wwwUwww
wwwUwww
wwwUwww
wwwxwww
wwwUwww
wwwUwww
wwwUwww

Where w = wall, U = firefly pointing upward and x = empty space.
If, for instance, the scan of the first line only takes the last line at the bottom into account for detections, the top firefly would just change its direction to the right, without moving. So the result would be (with R = firefly pointing right):

wwwRwww
wwwRwww
wwwRwww
wwwUwww
wwwUwww
wwwUwww
wwwxwww

Am I correct?

[LogicDeLuxe]

1. I don't see yet why a second parallel scan (with a delay of 2 lines) to reset the delay state (or "moved" mark) would be necessary. Would it make a difference / give problems if this scan were done just after completing the first scan?

Doing a complete scan cycle and then a reset cycle would produce a seam. This is about how to avoid exactly that, isn't it? Imagine a firefly moved through the bottom border to the top border. If you reset it just after that, it could move again without scanning everything else in the cave inbetween, which shouldn't be the case. If you reset it after you scanned the 2nd line, it can only move in the next scan again, which is what you really want. The scan interval should be always the size of the cave +- the distance it naturally can move per scan.
The always 2 lines distance for resetting should wrap as well, of course, ie. when scanning the first line, the resetting still takes places on the second to last line etc..

Or perhaps it is only for performance?

That would be the actual reason they implemented it that way in the first place, I guess. The current position in original BD is indexed with 81, which is exactly two lines and one field ahead. The same counter can be indexed with 0 to reset flags (actually processing the effect table, which is also there for explosion progress). It doesn't have to be exactly that distance. It only has to be far enough not to interfere with the actual movements from scanning the elements. It doesn't even have to be per field, but also could be implemented on a per line basis.

2. Using this method, I'm wondering what would happen in a scenario with a vertical line of upward pointing fireflies, with one empty hole in the middle? For example:

wwwUwww
wwwUwww
wwwUwww
wwwxwww
wwwUwww
wwwUwww
wwwUwww

Where w = wall, U = firefly pointing upward and x = empty space.
If, for instance, the scan of the first line only takes the last line at the bottom into account for detections, the top firefly would just change its direction to the right, without moving. So the result would be (with R = firefly pointing right):

wwwRwww
wwwRwww
wwwRwww
wwwUwww
wwwUwww
wwwUwww
wwwxwww

Am I correct?

Looks correct to me.

[Arno]

Thanks Logic for clarifying and Happy New Year!

Just one thing about this issue:

2. Using this method, I'm wondering what would happen in a scenario with a vertical line of upward pointing fireflies, with one empty hole in the middle? For example:

wwwUwww
wwwUwww
wwwUwww
wwwxwww
wwwUwww
wwwUwww
wwwUwww

Where w = wall, U = firefly pointing upward and x = empty space.
If, for instance, the scan of the first line only takes the last line at the bottom into account for detections, the top firefly would just change its direction to the right, without moving. So the result would be (with R = firefly pointing right):

wwwRwww
wwwRwww
wwwRwww
wwwUwww
wwwUwww
wwwUwww
wwwxwww

Am I correct?

Looks correct to me.

This outcome seems quite ok for me since no firefly (dis)appears, although I would have preferred:

wwwUwww
wwwUwww
wwwxwww
wwwUwww
wwwUwww
wwwUwww
wwwUwww

This would happen in an infinitely repeating world. So every stack of 6 fireflies would just move 1 position up. The "parallel universes" method would arrange this for this particular example, but as we know it gives other discontinuity issues as well...