Dihedral Subgroups Explained Via Factorio – BorisTheBrave.Com

Skip to content

The dihedral group is the mathematical formalism behind all the rotations and reflections of a regular polygon. For an n sided polygon, there are always n possible rotations, and n reflections, for 2n possible symmetries.

Combining any two symmetries gives another from the same group, that is what makes it a group in the mathematical sense.

The theory of it is useful to know for gamedev. I was reminded of this when seeing this Factorio devlog, where the developer ran into some trouble because he initially forgot to account for all the cases.

Sprites in Factorio

Factorio features a square grid, and sprite-based buildings that fill a rectangle of that grid. While building, you can rotate the buildins to better fit your design. But Factorio has an odd camera angle, angled lighting, and pre-rendered sprites. So it doesn’t cannot 3d models, and it cannot rotate the sprites images. All rotates are handled by swapping between sprites.

Some buildings are considered symmetric. They look the same from all sides, so rotating the building just re-uses the same sprite.

Other buildings, the game has four sprites, one for each rotation.

A few rare entities, have two sprites. When rotating 180 degrees they can re-use sprites, but rotating 90 they cannot.

With rotations only, you don’t really need theory. These are the only 3 cases to worry about, you can handle them each distinctly.

But for the next update, the developer wanted to add the ability to mirror buildings, not just rotate them. This was so you could take a large design, and copy paste a mirrored copy of it. He didn’t want to create any more sprites for the game, so he needed to consider how to classify all the existing buildings into sprite re-use patterns. Once you add in reflections, it turns out there are quite a few more cases to consider!

But once you understand the maths behind it, it’s straightforward to find (or lookup) all the cases. It’s time for a short lesson in Group Theory .

An introduction to groups and subgroups

First, let’s consider the rotations only case. Factorio is played on a square grid, so the only rotation is 90 degrees. If you keep applying a 90 degree rotation, you’ll get the 180, 270 and then 360 degrees. 360 degrees is equivalent to rotating by 0 degrees, it doesn’t do anything, so we’re back where we started. Mathematicians call the abstract1 collection of these rotations and the rules for how to combine them a group . In this case, we’ve created the group \(Z_4\), the cyclic group of order 4.

The important property of the group is that it is closed – combining any two operations in the group gives another element of the group. You can check that’s true for 90 degree rotations – no matter what, you are going to end up rotated at some multiple of 90 degrees, and there’s only 4 such rotations once you consider 0 and 360 to be identical.

Here’s another group. We’ll consider all the rotations you can get from rotating 180 degrees. It’s 0, and 180 only. Yes, it’s \(Z_2\). Likewise, if we started with 45 degrees, you’d get \(Z_8\). These are all closed, so they’re definitely groups. But also, you’ll notice that rotation in \(Z_2\) is also a rotation in \(Z_4\), because 180 is a multiple of 90. Similarly \(Z_4\) neatly fits inside \(Z_8\). This gives a notion of a subgroup .

Finally, it’s worth mentioning the trivial group . This is the group with only one element – rotation by zero degrees. It fits all the requirements I listed above, so it’s still a group. The trivial group is a subgroup of all of the above.

Subgroups and sprites

The reason for this whole digression is the different cases of sprite re-use I described above exactly correspond to subgroups.

There are only 3 subgroups of \(Z_4\), and they correspond to the 3 sorts of sprites we saw earlier:

\(Z_4\) – all rotations are shared

\(Z_2\) – rotations by 180 are shared

trivial – no rotations are are shared

In each case, the number of sprites needed is the size of the full group (4) divided by the size of the subgroup (4, 2 or 1). In fact, the sprites form a new group, called a quotient group, which we won’t go into here.

Anyway, we’re now armed to deal with adding reflections, and we can comprehensively list all cases. As mentioned, the group of all reflections and rotations on a square grid is \(D_4\), the dihedral group of order 8. It has 8 elements, 4 rotations, and 4 reflections. We’ll call them \(r_0\)..\(r_3\), \(s_0\)…\(s_3\).

We can also lookup its subgroups.

It’s got the rotations we saw before.

\(\{r_0\}\) – the trivial group<br>\(\{r_0, r_2\}\) – \(Z_2\)<br>\(\{r_0, r_1, r_2, r_3\}\) – \(Z_4\)

Then each reflection is a subgroup of size 2, because if you do the same reflection twice, you always get back to where you started, which is the same as rotating by zero degrees.

\(\{r_0, s_0\}\)<br>\(\{r_0, s_1\}\)<br>\(\{r_0, s_2\}\)<br>\(\{r_0, s_3\}\)

Then there are subgroups made...