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 cannot rerender 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
\(\{r_0, r_2\}\) – \(Z_2\)
\(\{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\}\)
\(\{r_0, s_1\}\)
\(\{r_0, s_2\}\)
\(\{r_0, s_3\}\)
Then there are subgroups made by combining a 180 degree rotation with a reflection. These are larger groups, because if you rotate 180 degrees, reflect, then rotate 180 degrees again, you end up with a different reflection. So to make the group closed, you must include that too.
\(\{r_0, r_2, s_0, s_1\}\) – 180 degrees, plus horizontal and vertical reflections
\(\{r_0, r_2, s_1, s_2\}\) – 180 degrees, plus both diagonal reflections
And finally, it has the full group
\(\{r_0, r_1, r_2, r_3, s_0, s_1, s_2, s_3\}\) – \(D_4\)
Now let’s look at some sprites that would correspond to each of these groups. The symmetry of the thing in the sprite determines the group. Note: I’ve drawn the sprites with realistic shading and shadows, to make it clear that is is the object depicted that is rotating, we cannot just rotate/reflect the image itself!
If you have no symmetry, then you are in the trivial group case. Your subgroup is of size one, so you need \(8/1 = 8\) unique sprites. \(\{r_0\}\)
If you had 4 way rotational symmetry, but no reflections, you need \(8/4 = 2\) tiles. \(\{r_0, r_1, r_2, r_3\}\)
And similarly for 2 way rotational symmetry. \(\{r_0, r_2\}\)
Then there’s the objects that only have one reflectional symmetry. \(\{r_0, s_1\}\)
Or with another reflection axis. \(\{r_0, s_2\}\)
(there’s 2 more cases like this, but they all look similar)
The subgroups of 180 degrees horizontal and vertical reflections. \(\{r_0, r_2, s_0, s_1\}\)
And for diagonal reflections. \(\{r_0, r_2, s_1, s_2\}\)
And finally, when the object is fully symmetric, only a single sprite is needed. \(\{r_0, r_1, r_2, r_3, s_0, s_1, s_2, s_3\}\)
These 10 cases are all possible symmetries.
Back to Factorio
Finally, what does that mean for Factorio, and the dev’s attempts at adding reflection?
The first big problem is that the first three cases all require special sprites that only needed to handle reflection. But this update cannot add any new sprites (it would break every mod for the game). Factorio does this by cheating and re-using sprites anyway, ignoring the asymmetry. So essentially the first three cases are never used.
In fact, the sprite situation in Factorio is the easy part, because there’s so much cheating. The actual fiddliness comes from building input/outputs, which are some in-game properties that also need updating. The dev explains in the blog that he wrote code to handle mirroring. But he must have not considered all the cases, as an obscure building only found in a mod forced him to rewrite all the code.
This is the Manufactory. If you include the inputs and outputs (the blue arrows), it has diagonal symmetry, similar to this case we discussed.
Had the devs known some group theory, he could have predicted this possibility in advance.
The post also notes some buildings are just badly designed. In the base game, the Pumpjack has this set of 4 sprites, which you can switch between by pressing the “Rotate” key.
If you look closely, you’ll realise that these sprites break the rules. Ignore the “cheated” parts that stay unchanged in each image, and look at the red output pipe. It doesn’t actually correspond to a 90 degree rotation in space! This eventually caused so much headache for the devs they just had to block support for rotating / mirroring this entity entirely. This could have been avoided from the start.
So there you have it. The 10 subgroups of \(D_4\) give us 10 different symmetries to consider in games2. Armed with this knowledge, you can design your sprites more effectively, and consider all the edge cases.
I’ve only touched the surface for group theory. The maths runs extremely deep, and has fundamental connections to a great deal of other areas in pure mathematics. I can recommend 3b1b’s video if you’d like to learn more.
Edit: Only a few weeks after I wrote this post, the Factorio devs started correcting some of the rule breaking sprites I identified. Pumpjacks now have 8 unique sprites, as dictated by the trivial group (no symmetry).
