A perfect Open Border implementation – does it exist?

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

Post by Dustin »

It was a pleasure, Arno! :D

I have some thoughts about your example concerning the "perfection question":
Arno wrote: 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.
In this case, I clearly prefer the first of the two resulting maps. There are two fireflies competing for the same space to move into, and the one on the top should win.

This makes me think of a suggestion you already made at Krissz's site - make more than one complete cavescan per frame, starting from each point of the map once, and take the result that occurs most often. I don't know whether this could give performance problems for 100x100 caves, but in sense of theoretical perfection, I see some advantages of this method over "parallel universes":
--> Strange effects like the number of fireflies increasing are ruled out completely.
--> Per definition, it's 100% certain that it makes no difference where the open border is.
At first sight, problems should only occur with very small caves, where there might not be a resulting map occuring more than once!
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 »

But now I also found a cave (as big as you wish) which favours the "parallel universes" concept over the "multiple scanning" method:
DFSDBDDDDDDDDDDDDDD
DDDDFSDBDDDDDDDDDDD
DDDDDDDFSDBDDDDDDDD
DDDDDDDDDDFSDBDDDDD
DDDDDDDDDDDDDFSDBDD
DBDDDDDDDDDDDDDDFSD
F-irefly (facing right), B-oulder (falling state), D-irt, S-pace

In an infinite world, every firefly should get crushed, which is also the "parallel universe" result. On the other hand, no singe "multiple scan" result sees all fireflies crushed - exactly one fly survives every time!
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 »

Dustin wrote:But now I also found a cave (as big as you wish) which favours the "parallel universes" concept over the "multiple scanning" method
Indeed! Still an interesting result, so it's good that you mention this method here as well, for completeness. ;)
Post Reply