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 

Rolling fly formations explained

 
Post new topic   Reply to topic    Boulder Dash Forum Forum Index -> Tools, Fanstuff
View previous topic :: View next topic  
Author Message
Arno
Site Admin


Joined: 17 Mar 2007
Posts: 2625
Location: netherlands

PostPosted: Sun May 31, 2020 9:08 pm    Post subject: Rolling fly formations explained Reply with quote

Rolling fly formations explained

Introduction

Here’s my latest BD research article about rolling fly formations (RFFs), a group of fire/butterflies moving together, in a dense group, along a line of static BD items (like wall, T-wall or dirt). The main difference with dancing fly formations (DFFs) is that the help of a border to move along is necessary, whereas DFFs move freely through open space.

As an introductory demonstration, the following videos of some older caves show the phenomenon that we are going to discuss:





So, have you become curious how these formations work and which extensions and variants are possible? Then just read on!

Terminology

There are various general BD concepts, which I used in the DFF article series and which I will also use in this article. Here's a short list of common terminology.
- Frame: shortest unit of time in BD. Within a frame elements exist on each position and during the cave scan, their position for the next frame are determined.
- Phase of a RFF: one frame within the formation.
- Short loop: set of phases until the flies are positioned equivalently to the original starting phase (but the group as a whole has shifted). Note that the flies may mutually have changed position, for example, fly A takes over the position of fly B, B that of C, etc...
- Long loop: set of phases until all individual flies have returned to their original position within the rolling group. It could be that the short loop and long loop are the same. Otherwise, the long loop consists of multiple short loops.
- Interaction: this means that flies within the group influence each other’s move. For example, a firefly moves forward because its way to the left (first choice) is blocked by another fly.
- FF is my abbreviation for firefly.
- BF is my abbreviation for butterfly.

Which conditions determine the possible formations?

Before starting with the details, it is also good to recall the mechanics in the common BD engines which determine which formations are possible. In fact, there are two basic conditions which limit the possibilities:
1. Cave scan method. Caves are scanned line-by-line, from top to bottom, and from left to right.
2. Moving directions of the flies.
Firefly:
- First tries to move 1 position to its left.
- If this is not possible it will move 1 position forward.
- If this is also not possible, it will turn its direction to its right while staying at the same position.
Butterfly:
- First tries to move 1 position to its right.
- If this is not possible it will move 1 position forward.
- If this is also not possible, it will turn its direction to its left while staying at the same position.

We will start describing the FF formations and discuss the BF formations later on.

Firefly formations

A series of rolling FF formations is possible, which are all based on the same principles. The following video shows the base formation (with 4 FF) and a series of possible extensions, horizontally and vertically.



We will now discuss how the base formation and the various methods to extend this formation work.

The base formation: Rolling-F4

In the simples form, a rolling fly formation consists of 4 FFs. A smaller variant is not possible. All 4 FF need each other in order to stay together and move along. The above video shows this formation. It is the first in the series.

Below picture shows the 2 phases of Rolling-F4.

We use symbols in a similar way as in the DFF article. So arrows indicate the direction in which each fly is facing. A yellow star indicates a conflicting position where at least two flies want to move to. A red sign indicates that a fly cannot move into this direction (for example, because another fly is scanned before and gets priority). A green sign indicates that the fly can/will move into this direction, although currently the position is occupied. In the latter case, the fly occupying that position will be scanned first and move away before the concerning fly is scanned and will move to that position.

Especially for this article, a thick black line at the bottom indicates the solid wall along which the formation moves. From now on I’ll refer to this wall as the border.



It can be seen that the FFs make a circling movement, counterclockwise, while together moving leftward like a caterpillar-tracked vehicle. The short loop consists of these phases:

- Phase 1: First the top line is scanned, from left to right. The Red fly therefore moves down. Yellow moves forward (so left), since his left side is blocked by Purple. Green moves left after Yellow has made that position free. Next, the bottom line is scanned. The Purple fly cannot move to its left (since the border is present there), but also cannot move forward (since Red has already occupied that position). It will therefore change its facing direction to its right (so upward).
- Phase 2: Yellow and Green just move another position forward (i.e. to the left). Red cannot move to its left (blocked by Purple) or forward (border) so its facing direction is changed to its right (so left). Purple cannot move left (blocked by Red), so he will move forward (since Green has just freed up that position).
- Phase 1’: A similar composition as in Phase 1 has been formed, so now the cycle can start over again. (For simplicity, the signs have been left out in the picture of phase 1’.)

In Phase 1’ the formation has moved 1 step to the left. Also, each FF has taken over the role of another FF. Eventually all 4 FF will take all 4 roles. This implies that, since the short loop takes 2 phases, a long loop takes 2*4 = 8 phases. In other words, after 8 frames all FF have returned to their original position within the formation. Meanwhile, the formation has moved 4 steps.

Why does this construction work?
On the top line, each FF moves just one position to the left, except for the FF at the front which moves down eventually. This way, the top line forms a “queue” of FF moving left, in which every 2 frames the FF at front moves down, and at the back side a new FF connects from the bottom line. All this is possible because the cave scanning happens from left to right. Only then, a row of FF could move together to the left within a single frame. So clearly, a similar formation moving to the right won’t be possible.
The bottom line contains the FF (Purple) around which the top flies are circling. It also has interaction with the border. Most of the times, a FF on the bottom line cannot move because the border, the top line and a neighbor FF are blocking both its moving directions. When it ultimately is able to move it will move upward, joining the “queue” at the top line again. This way, the FF at the bottom keeps the formation together until its role is taken over by the next fly leaving the top line.

I’d like to call the Purple fly the carrier, and the other flies the wanderers. While the wanderers move to the left, each of them will take over the role of the carrier one by one. This makes the formation “rolling” gradually to the left, hence the name Rolling-F4.

Rolling-F5

Rolling-F4 can be extended naturally by adding a second carrier FF. This is the second formation in this video. Below picture shows the 2 phases of Rolling-F5.



The main difference with Rolling-F4 is the presence of an additional Blue FF at the bottom-right. This is the second carrier and it moves to the top line already at the same time when Red moves down. Where in Rolling-F4 the Purple FF would move up, in Rolling-F5 the Blue FF blocks Purple at this point, so Purple has to wait 2 more frames before moving up. In a certain sense, the Blue fly has filled a gap in the formation, such that the top line always contains 3 FF and the bottom line always 2 FF.

Also Rolling-F5 moves 1 step per short loop of 2 phases. Each FF will take all 5 roles one by one. The 5 flies form a rolling cycle in order Red-Yellow-Green-Blue-Purple and back to Red. So compared with Rolling-F4, the long loop takes longer. It takes 2*5 = 10 phases.

So far this is the only possible extension to Rolling-F4. For instance, if you try to find a different one by placing a FF on top or at the left side of the formation, it will either break the formation or the formation will integrate the extra FF, which ultimately results in a Rolling-F5 after some frames.

Horizontal extensions

Starting with Rolling–F5 it is easy to extend the formation horizontally, thereby creating an unlimited long “caterpillar”. By adding FFs at the back side of both rows, it is possible to create a working RFF. Just make sure that the back end equals that of Rolling-F4 or –F5. Two examples are shown in this video: check out the 6th and 8th formation.

Below picture shows the simplest possible extension. 3 grey FFs have been added to Rolling-F5, such that the back end of the formation looks like Rolling-F4.



This formation works according to the same principles as Rolling-F4. Of course, another FF could be added to the bottom line, such that the back end runs like Rolling-F5. Similarly, more flies could be added to make the formation even longer.

Although these horizontal extensions are interesting, their working is very similar. We will now discuss a series of vertical extensions. Since these vertical extensions are more dynamic, I will introduce separate names for these extensions.

Rolling-F6

The Rolling-F5 formation can be extended vertically by adding a FF on the top, thereby creating a new layer (video: third formation). Below picture shows the phases of Rolling-F6.



During phase 1-8, the formation looks like a Rolling-F5, rolling as usual, while the additional FF (Dark orange) runs from the right to the left, along the top of the formation. Since the Dark orange fly moves twice as fast as the formation, each 2 frames the Dark orange fly advances one step forward relative to the formation. (To avoid confusion, I have left out the red/green signs for the Rolling-F5-part of the formation, and only added those which are relevant for the interaction with the additional Dark orange fly.)

Between phase 8 and 1’ the crucial effect happens: the Dark orange FF moves down to the second layer, and by doing so he blocks the way for all flies moving on this layer. This causes the Purple and Red fly to stop for 1 frame. Because the Yellow fly is already pointing upward, he moves up to the upper layer and takes over the role of the Dark orange fly.

Rolling-F6 moves 4 step per short loop of 8 phases. Again each FF will take all 6 roles eventually. The long loop therefore takes 8*6 = 48 phases.

Rolling-F7

The next extension is possible by adding a second fly to the third layer. This is possible in two ways, which gives two variants of Rolling-F7 (video: 4th and 5th formation).

The first variant is shown below. Here, a second FF (again orange, but in a lighter shade) is added just next to the Dark orange fly. I name this variant Rolling-F7.



This formation works similar to Rolling-F6. The crucial step, where flies are exchanged between the top and second layer, happens two times: between phases 6/7 and phases 8/1’. Like Rolling-F6 also for –F7 the full short loop takes 8 phases and the formation moves 4 step per short loop. Again each FF will take all 7 roles one by one. So this time the long loop takes 8*7 = 56 phases.

The second variant with 7 FF is shown below. I name it Rolling-F7a.



The main difference with the “regular” Rolling-F7 is that the additional fly is placed such that there is one gap of space between both flies at the top. Since the top line has 4 positions, there are two ways to place 2 FF on this line: either next to each other (like Rolling-F7) or with a space in between (like Rolling-F7a).

Funny to note that Rolling-F7a only has 4 phases in its short loop. As soon as the front Orange fly has moved to the second layer, the formation looks again like phase 1. Also the formation has moved 2 steps in its short loop. Still, all FF take all 7 roles eventually. So the long loop takes 4*7 = 28 phases.

Rolling-F8

For an extension with 8 FF, a third FF is added to the top row (video: 7th formation). Since the top row has 4 positions this is possible in only one way: 3 occupied and 1 empty. Below picture shows the phases of Rolling-F8.



Again the working of this formation is similar. The exchange of flies between layers happens 3 times: between phases 4/5, phases 6/7 and phases 8/1’. The short loop again takes 8 phases and the formation moves 4 steps per short loop. Again all FF take all 8 roles eventually. So the long loop takes 8*8 = 64 phases.

Rolling-F9

As it turns out, 9 is a magic number for this series of formations! An extension with 9 FF is possible by adding a fourth FF to the top row (video: 9th formation). With this addition the top row is complete. Below picture shows the phases of Rolling-F9.



Since there are no holes in the top row, Rolling-F9 has only 2 phases. But something else might be more surprising. When the front Light-orange FF moves down to the second layer, at the same time the Blue fly moves up and connects to the queue on the top layer. The Blue fly forms in fact the other end of a cycle formed by the Orange flies, Red, Purple and Blue. The two inner flies Yellow and Green do not change position within the formation!
So we have now constructed a formation consisting of 2 inner flies staying in the center and 7 outer flies forming a ring around the inner flies and rolling the formation like a true caterpillar-tracked vehicle!

Even more funny is that this rolling movement can be made more visible by exchanging the 2 inner fireflies for butterflies (video: 10th formation)! Below picture shows this variant, using a slightly different Yellow and Green color to emphasize that the inner flies are now butterflies:



Since the inner flies are blocked by both the first and third layer, the formation works either with 2 FF or with 2 BF with opposite facing direction in the center. In addition, it is possible replace only one of the two inner FF by a BF. In total this gives 4 variants of Rolling-F9. These variants with butterflies are only possible if the top line is complete. Otherwise, the butterflies will eventually leave the formation via the top line.

For Rolling-F9 (either variant with FF or BF in the center) the formation moves 1 step per short loop, which consists of 2 phases. Out of the 9 flies, only the 7 outer flies switch roles one by one. The remaining 2 stay at the same position in the center. Therefore, the long loop takes 2*7 = 14 phases.

Another small surprise awaits us for Rolling-F9. It is possible to extend the outer ring with one additional FF as shown below and in the video (11th formation):



Here, the light-Blue FF fills up a gap in a similar way as Rolling-F5 has filled a gap in Rolling-F4. I call this formation Rolling-F9+t where the “+t” stands for “extra tail”. This addition is only possible when top line is complete. For example, if you try to extend Rolling-F8 with such additional FF, then this FF disconnects from the formation after few frames. Due to the additional fly in the outer ring, a long loop of Rolling-F9+t consists of 8 short loops (instead of 7), thus 2*8 = 16 phases in total.

With the option to add the “extra tail”, and the 4 options we already had for placing FF or BF in the center, a total number of 8 variants exist for Rolling-F9.

Overview table

The following table lists the properties of all rolling FF formations discusses so far:

Code:

Name         #FF  Height      Loop*  Moves**
============================================
Rolling-F4     4       2     2 /  8        1
Rolling-F5     5       2     2 / 10        1
Rolling-F6     6       3     8 / 48        4
Rolling-F7     7       3     8 / 56        4
Rolling-F7a    7       3     4 / 28        2
Rolling-F8     8       3     8 / 64        4
Rolling-F9     9       3     2 / 14        1
Rolling-F9+t  10       3     2 / 16        1

* #phases per short loop / long loop
** #positions per short loop


Rolling-F10 and further

Rolling-F9 can be extended further by adding a fourth layer on the top. This gives Rolling-F10 until Rolling-F14. Below picture shows all possible variants, but only the first phase. In the video, the 12th formation shows Rolling-F10. For the others, you could easily build them in a BD editor to see them at work.



Note that the formations with 11 and 12 FF exist in two variants, since there are two ways to position the fireflies on the top line. For Rolling-F14, for which the top line is complete, it is possible to replace all inner fireflies by butterflies! Just like Rolling-F9, the fireflies on the outer ring will roll around the flies in the center. Lastly, for Rolling-F14 it is possible to add an additional tail-fly, which gives Rolling-F14+t.

In a similar way, it is possible to add any number of layers to the formation! This increases the height and the width of the formation. Each layer can hold one fly more than the layer underneath.

Combining horizontal and vertical extensions

The discussed methods to extend a rolling formations horizontally or vertically can be combined as well. The last formation in the video show a giant formation, with 9 layers added to the base formation, and at the bottom 6 flies (instead of 2). With such a big center, funny things can be done as you can freely place a firefly or butterfly at each position. For instance: you could write letters, as in the video.

Also, stacking of formations is possible. The giant formation in the previous video carries a Rolling-F9 formation on its top. As another example, the following video shows a funny effect by stacking Rolling-F4 formations:



Launch methods

Any Rolling-Fx formation can be launched by creating a “colonne” of x FFs, with gaps of 2 spaces between each two subsequent flies, and letting them “roll” together from a diagonal stairs. This method is shown by the videos on the top of this article, for example this video.

As an alternative, it is possible to first create a Rolling-F4 via the stairs-method, and add the required number of FFs to the formation by letting the formation collide with a series of spinning FFs. Using this method, the formation looks like a tornado since it becomes bigger and swallows all flies it meets on its way. This method is demonstrated in the video below:



Other funny effects

Probably, various effects are possible using rolling formations. One example is that by using a formation with incomplete top row (e.g. Rolling-F6), a formation with free riding fireflies can be created. This way, the formation pushes a spinning FF forward, which in turn pushes the next FF forward, etc.:



Depending on the timing of a spinning FF, it may either merge with the formation (like in the tornado video), or become a free rider like above.

Butterfly formations

The article series on dancing fly formations (DFFs) introduced the concept of a mirrored pair. In short: a formation has a mirrored counterpart if any phase can be mirrored in a diagonal line from top-left to bottom-right, such that:
- Fireflies are exchanged for butterflies and vice versa,
- The facing directions of the flies are mirrored accordingly (e.g. arrow-left becomes arrow-up).
- The resulting construction gives you a working formation as well.
Not every DFF has a mirrored counterpart, but we know that least 3 mirrored pairs of DFFs exist.

The concept of a mirrored pair can also be applied to rolling fly formations (RFFs). As it turns out, the base formation Rolling-F4 has a perfectly mirrored counterpart, which we call Rolling-B4. It work very similar to Rolling-F4, but this time with butterflies. Also, the moving direction is upward along a vertical border, which results from mirroring the left moving-direction of the FF formation diagonally. Below picture shows the phases of Rolling-B4:



Now the big question is: Does a mirrored counterpart exist for all rolling firefly formations discussed so far in this article? Unfortunately this is not the case. Rolling-F5 cannot be mirrored in a similar way. The following picture shows what happens if we would try that:



After phase 2, the additional Blue BF is kicked out from the formation by Purple and the formation continues as Rolling-B4. The problem is that at this point Rolling-F5 relies specifically on the row-by-row cave scanning. Purple and Blue want to move to the same position. In Rolling-F5 Blue moves before Purple, since the top row is scanned first. But in Rolling-B5, Purple moves first since it is located on the row above Blue.

A similar problem happens with Rolling-B6, 7 and 8. These formations therefore do not exist. But… perhaps surprisingly, Rolling-B9 does exist! Below picture shows its phases:



Here, the Purple fly stays on its place, because the two inner flies (Green and Yellow) stay in the center. This way, there is no conflicting position which depends specifically on the row-by-row scanning. The Blue BF remains part of the formation and joins the left column, similar to what happens in Rolling-F9.

Some variations which are possible for Rolling-F9 are unfortunately not possible for Rolling-B9:
- Replacing the inner butterflies by fireflies is not possible. This phenomenon relies on the row-by-row scanning. Since for the BF formations, the left-most column is not fully scanned first (but rather as part of each row scan), any fireflies in the center will leave the formation via the left column.
- Adding an extra tail-butterfly is also not possible. This is for the same reason as why Rolling-B5 does not work: there is a conflicting position depending on the row-by-row scanning. Thus, a Rolling-F9+t does not exist.

Here’s an overview table of butterfly formations similar to the one presented above for fireflies. In fact it is a relatively poor one, since a lot of FF formations have no counterpart for BFs.

Code:

Name         #BF   Width      Loop*  Moves**
============================================
Rolling-B4     4       2     2 /  8        1
Rolling-B9     9       3     2 / 14        1

* #phases per short loop / long loop
** #positions per short loop


Nevertheless, from 10 butterflies onwards, it is again possible to add new butterflies to the left-most column of the formation. So, Rolling-F10, 11, 12, etc. do all exist. The following video shows a series of rolling BF formations:



The launch methods for the BF formations are similar to the methods for FF formations:
- One possibility is to create the formations using a stairs, like in the above video.
- Another way is to extend a formation with an additional BF by collision with a spinning BF. This gives a “butterfly tornado” as shown in the next video:



Relation with Dancing Fly Formations

As we approach the end of this article, one last thing worth mentioning is that the class of rolling fly formations discussed in this article is related to a class of dancing fly formations, the Swarm-formations. These DFFs will be discussed in full detail in a separate article in the DFF thread. But it is possible, with a slightly different composition, to make a RFF independent of the border, such that it could move through open space, resulting in a DFF. This is not possible for all RFFs, but only for a subset.

Below videos show some pairs of RFF and DFF, for both FF and BF formations. It also shows some of the RFFs without a dancing counterpart because it does not exist.





Conclusion

The RFFs form a big class of formations, which provide many possibilities for BD caves. Until now, the class discussed in this article is the only unique set of RFFs discovered so far. Of course, more simple constructions exist, like a stack of 2 fireflies moving along a border to the left. However, I would rather classify such phenomenon as a single fly with a free rider, since one fly influences the other but not vice versa.

An interesting question is whether more unique RFFs exist, in which all flies impact each other’s movements. We’ll have to see in the future. Perhaps at some point in time a new RFF article will appear in this thread. Smile
_________________
---- Boulder Dash Fansite ----


Last edited by Arno on Fri Jun 05, 2020 9:58 am; edited 2 times in total
Back to top
View user's profile Send private message Send e-mail Visit poster's website
LogicDeLuxe
Member


Joined: 15 Jul 2007
Posts: 631

PostPosted: Mon Jun 01, 2020 10:47 am    Post subject: Reply with quote

Very interesting analysis.

Your table states 2 phase loops as moving 2, while those are moving only 1 per short loop.

Nice discovery, that you can turn those into flying formations. I don't think, I've seen those before.

I wonder why you chose to start Rolling-F6 to Rolling-F8 with exactly that phase. The flies in the second to bottom row abandon their all left facing formation is new to those. Phase 3 on the other hand would be the obvious extension to phase 1 of Rolling-F5.
Back to top
View user's profile Send private message Visit poster's website
Arno
Site Admin


Joined: 17 Mar 2007
Posts: 2625
Location: netherlands

PostPosted: Mon Jun 01, 2020 3:19 pm    Post subject: Reply with quote

LogicDeLuxe wrote:
Your table states 2 phase loops as moving 2, while those are moving only 1 per short loop.

Thanks! I've corrected both tables.

LogicDeLuxe wrote:
I wonder why you chose to start Rolling-F6 to Rolling-F8 with exactly that phase. The flies in the second to bottom row abandon their all left facing formation is new to those. Phase 3 on the other hand would be the obvious extension to phase 1 of Rolling-F5.

Good point. I just started on scrap paper with Rolling-F5 plus additional FF at the right-most position, with the idea that the last phase would be the key step. Soon I realized after one cycle that phase 1 had to be adjusted on the second row, but then I didn't consider to select another phase as starting phase anymore. Smile
_________________
---- Boulder Dash Fansite ----
Back to top
View user's profile Send private message Send e-mail Visit poster's website
LogicDeLuxe
Member


Joined: 15 Jul 2007
Posts: 631

PostPosted: Tue Jun 02, 2020 11:08 am    Post subject: Reply with quote

Arno wrote:
As an alternative, it is possible to first create a Rolling-F4 via the stairs-method, and add the required number of FFs to the formation by letting the formation collide with a series of spinning FFs. Using this method, the formation looks like a tornado since it becomes bigger and swallows all flies it meets on its way. This method is demonstrated in the video below:

While that video there seems pretty straight forward, I think, the very first video is the more interesting variation of it:
https://www.youtube.com/watch?v=pmFKt4joGhg
Fireflies above the actual formation are seemingly sucked in to become a part of it, while in the latter video, they obviously collide with the formation and join it. The staircase apparently is only a part of the process, and the formations continues forming on its way with no spinning flies involved.
Maybe, this launching process at and beyond the staircase would be worth its own analysis.
Back to top
View user's profile Send private message Visit poster's website
Arno
Site Admin


Joined: 17 Mar 2007
Posts: 2625
Location: netherlands

PostPosted: Tue Jun 02, 2020 5:14 pm    Post subject: Reply with quote

LogicDeLuxe wrote:
Fireflies above the actual formation are seemingly sucked in to become a part of it, while in the latter video, they obviously collide with the formation and join it. The staircase apparently is only a part of the process, and the formations continues forming on its way with no spinning flies involved.

Oh that's interesting indeed. Until now I didn't realize that there's more going on than "just" the staircase method. Smile
_________________
---- Boulder Dash Fansite ----
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Boulder Dash Forum Forum Index -> Tools, Fanstuff All times are GMT + 1 Hour
Page 1 of 1

 
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