I have some thoughts about your example concerning the "perfection question":
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.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.
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!
