Диэдральная группа — это математическое обозначение всех поворотов и отражений правильного многоугольника. Для n‑стороннего многоугольника всегда существует n возможных поворотов и n отражений, что даёт нам 2n возможных симметрий.
Сочетание любых двух симметрий даёт нам элемент из той же группы, и это превращает её в группу в математическом смысле.
Теория групп полезна при разработке игр. Я вспомнил об этом, прочитав девлог Factorio, в котором разработчик рассказал о проблемах, возникших из‑за того, что изначально он забыл учесть все случаи.
Спрайты Factorio
Factorio построена на сетке квадратов, в которой состоящие из спрайтов здания заполняют прямоугольник в этой сетке. При постройке можно вращать здания, чтобы они лучше подходили к создаваемым вами конструкциям. Однако в Factorio используется странный угол камеры, освещение под углом и заранее отрендеренные спрайты, поэтому игра не может рендерить 3D‑модели и поворачивать изображения спрайтов. Все повороты реализуются сменой спрайтов.
Некоторые здания считаются симметричными. Они выглядят одинаково со всех сторон, поэтому при их повороте используется один и тот же спрайт.
Для других зданий в игре есть четыре спрайта, по одному на каждый поворот.
В некоторых редких случаях используются два спрайта. При повороте на 180 градусов можно использовать те же спрайты, но не при повороте на 90 градусов.
Если учитывать только повороты, то теория нам особо не пригодится. Есть всего три случая, которые можно обрабатывать по отдельности.
Однако в следующем обновлении разработчик захотел добавить возможность отзеркаливания зданий, чтобы можно было взять большую конструкцию и скопипастить в неё отзеркаленную копию. Разработчик не хотел создавать новые спрайты для игры, поэтому ему нужно было понять, как классифицировать все имеющиеся здания по паттернам многократного использования спрайтов. Оказывается, что при добавлении отражений возникает довольно много новых случаев!
Если же понять лежащую в основе них математику, то все случаи можно найти очень легко. Для начала давайте проведём небольшой урок по теории групп.
Введение в группы и подгруппы
Для начала рассмотрим только повороты. В основе Factorio лежит сетка квадратов, поэтому возможны только повороты на 90 градусов. При многократном применении поворотов на 90 градусов мы получим 180, 270 и 360 градусов. 360 градусов эквивалентны повороту на 0 градусов, поэтому мы вернулись к началу. Математики называют абстрактную коллекцию таких повороторов и правил их комбинирования группой. В этом случае мы создали группу Z4 — циклическую группу четвёртого порядка.
Важное свойство группы заключается в том, что она замкнутая — комбинирование любых двух операций в группе даёт ещё один элемент группы. Мы можем убедиться в истинности этого для поворотов на 90 градусов — что бы мы ни делали, у нас будет число, кратное 90 градусов, и существует только 4 таких поворота, если считать 0 и 360 идентичными.
Рассмотрим другую группу: все повороты, которые можно получить при вращении на 180 градусов. Это только 0 и 180. Да, мы получили Z2. Аналогично, если бы мы начали с 45 градусов, то получили бы Z8. Все они замкнуты, так что это определённо группы. Но также стоит отметить, что поворот в Z2 также оказывается и поворотом в Z4, потому что 180 кратно 90. Аналогично Z4 входит в Z8. Так мы приходим к понятию подгруппы.
Здесь также стоит упомянуть тривиальную группу. Это группа из всего одного элемента — поворота на ноль градусов. Она соответствует всем изложенным выше требованиям, поэтому всё равно остаётся группой. Тривиальная группа — подгруппа всех перечисленных выше групп.
Подгруппы и спрайты
Мы отступили от темы спрайтов потому, что описанные мной различные случаи многократного использования спрайтов точно соотносятся с подгруппами.
У Z4 есть всего 3 подгруппы, соответствующие трём видам рассмотренных выше спрайтов:
-
Z4 — все повороты общие
-
Z2 — общие повороты на 180 градусов
-
тривиальная — общих поворотов нет
В каждом случае необходимое количество равно размеру полной группы (4), поделённому на размер подгруппы (4, 2 или 1). На самом деле, спрайты образуют новую группу, называемую факторгруппой, но здесь мы её рассматривать не будем.
Теперь мы готовы к добавлению отражений и можем создать полный список всех случаев. Как я уже говорил, группа всех отражений и поворотов на сетке квадратов — D4, диэдральная группа восьмого порядка. В ней 8 элементов: 4 поворота и 4 отражения. Обозначим их 
..
, 
…
.
Также мы можем найти её подгруппы.
Она содержит уже рассмотренные нами повороты.
{
} — тривиальная группа
{
} — Z2
{
} — Z4
Каждое отражение — это подгруппа размера 2, потому что если выполнить одинаковое отражение дважды, мы придём к тому, с чего начинали, аналогично повороту на 0 градусов.
{
}
{
}
{
}
{
}
Также есть подгруппы, составленные комбинированием поворота на 180 градусов с отражением. Размер этих групп больше, потому что если выполнить поворот на 180 градусов, отразить изображение, а потом снова повернуть его на 180 градусов, то отражение будет другим. Поэтому чтобы группа была замкнутой, нужно включить и их тоже.
{
} — 180 градусов плюс отражения по горизонтали и вертикали
{
} — 180 градусов плюс оба отражения по диагонали
Наконец, вот полная группа:
{
} — D4
Теперь рассмотрим некоторые из спрайтов, соответствующих каждой из этих групп. Симметрия объекта в спрайте определяет группу. Примечание: я нарисовал спрайты с реалистичным затенением и тенями, чтобы было понятно, что вращается именно объект, мы не можем просто поворачивать, отражать само изображение!
Если симметрии нет, то это случай тривиальной группы. Подгруппа имеет размер 1, поэтому нужно 8/1=8 уникальных спрайтов. {
}
Если бы у нас была четырёхсторонняя вращательная симметрия и отсутствовали отражения, то нам бы понадобилось 8/4=2 тайла. {
}
И аналогично для двухсторонней вращательной симметрии. {
}
Теперь рассмотрим объекты, имеющие только одну зеркальную симметрию. {
}
Или с другой осью отражения. {
}
(Есть ещё два подобных случая, но все они выглядят похоже)
Подгруппы по 180 градусов с отражениями по вертикали и горизонтали. {
}
И диагональные отражения. {
}
Наконец, когда объект полностью симметричен, достаточно одного спрайта.
{
}
Эти десять случаев охватывают все возможные симметрии.
Вернёмся к Factorio
Что всё это означает для Factorio и как связано с попытками добавить отражения?
Первая большая проблема заключается в том, что первые три случая требуют особых спрайтов, необходимых только для работы с отражением. Но в обновление нельзя добавлять новых спрайтов (это поломает все моды игры). Factorio жульничает, используя спрайты повторно и игнорируя асимметрию. То есть, по сути, первые три случая не учитываются.
На самом деле, ситуация со спрайтами Factorio — это самое простое, потому что игра очень много жульничает. Самое сложное связано с созданием входов/выходов; это внутриигровые свойства, которые тоже нужно обновлять. В своём посте разработчик написал, что создал код для обработки отзеркаливания, но, похоже, не учёл все случаи, потому что из‑за здания, присутствующего только в моде, ему пришлось переписать весь код.
Это Manufactory. Если учесть все входы и выходы (синие стрелки), то здание имеет диагональную симметрию, схожую с рассмотренным нами случаем.
Если бы разработчик знал теорию групп, то смог бы предусмотреть такую возможность.
В посте также отмечается, что некоторые здания просто некачественно спроектированы. В базовой игре у нефтяной вышки (Pumpjack) есть набор из четырёх спрайтов, между которыми можно переключаться, нажимая кнопку «Rotate».
Если приглядеться, можно понять, что эти спрайты нарушают правила. Не смотрите на все «жульнические» детали, не меняющиеся между изображениями, и обратите внимание на красную трубу. На самом деле, она не соответствует повороту на 90 градусов! Это вызвало такую кучу проблем у разработчиков, что в конечном итоге они заблокировали поддержку вращения/отзеркаливания этого объекта. Этого можно было избежать с самого начала.
Итак, вот, что у нас получилось: 10 подгрупп группы D4 дают нам 10 уникальных симметрий, которые нужно учитывать в играх (если бы в игре использовались шестиугольники, то потребовалась бы D6, имеющая 12 подгрупп). Вооружившись этим знанием, вы сможете эффективнее проектировать свои спрайты и учитывать все пограничные случаи.
Я коснулся лишь самых основ теории групп. Она очень глубока и имеет фундаментальные связи со множеством других областей чистой математики. Если вы хотите узнать подробности, то рекомендую посмотреть видео 3b1b.
Дополнение: спустя несколько недель после написания этого поста разработчики Factorio начали исправлять некоторые из спрайтов, нарушающих правила. Теперь у нефтяных вышек 8 уникальных спрайтов, как и должно быть согласно тривиальной группе (отсутствие симметрии).
ссылка на оригинал статьи https://habr.com/ru/articles/1066864/