Boulder Dash Forum Forum Index Boulder Dash Forum
The only Boulder Dash discussion board in English language!
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

A perfect Open Border implementation does it exist?
Goto page Previous  1, 2, 3
 
Post new topic   Reply to topic    Boulder Dash Forum Forum Index -> Tools, Fanstuff
View previous topic :: View next topic  
Author Message
Dustin
Member


Joined: 23 Sep 2007
Posts: 464
Location: Erlangen, Germany

PostPosted: Tue Sep 15, 2020 12:37 am    Post subject: Reply with quote

It was a pleasure, Arno! Very Happy

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
Back to top
View user's profile Send private message
Dustin
Member


Joined: 23 Sep 2007
Posts: 464
Location: Erlangen, Germany

PostPosted: Tue Sep 15, 2020 1:02 am    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Boulder Dash Forum Forum Index -> Tools, Fanstuff All times are GMT + 1 Hour
Goto page Previous  1, 2, 3
Page 3 of 3

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group