Мозговой штурм с помощью транспонирования

Иногда я захожу в тупик и мне приходится искать способы думать над задачей под другим углом. Бывают задачи, которые можно отобразить в виде матрицы или таблицы. Их структура выглядит примерно так:


Ячейки, с которыми я работаю, выстроены в столбцы и строки. Давайте возьмём пример из простой игры:


Строки — это классы персонажей: воин, маг, вор.

Столбцы — это типы действий: нападение, защита, особое действие.

Матрица содержит весь код для обработки каждого из типов действий для каждого типа персонажа.

Как выглядит код? Обычно подобные структуры упорядочивают в такие модули:

1. Fighter будет содержать код для обработки ударов мечом, снижения урона с помощью брони и особого мощного удара.
2. Mage будет содержать код обработки фаерболов, отражения урона и особую атаку заморозкой.
3. Thief будет содержать код для обработки атак кинжалом, избегания урона уклонением и особую обезоруживающую атаку.

Иногда бывает полезно транспонировать матрицу. Мы можем упорядочить её по другой оси:

1. Attack будет содержать код обработки ударов мечом, стрельбы фаерболами и атак кинжалом.
2. Defend будет содержать код обработки снижения урона, отражения урона и ускользания от урона.
3. Special будет содержать код обработки мощного удара, заморозки и обезоруживания.

Меня учили, что один стиль «хорош», а другой «плох». Но мне не очевидно, почему всё должно быть именно так. Причина заключается предположении, что мы чаще будем добавлять новые классы персонажей (существительные), и редко добавлять новые виды действий (глаголы). Таким образом я смогу добавить код с помощью нового модуля, не трогая все имеющиеся. В вашей игре всё может быть иначе. Взглянув на транспонированную матрицу, я осознаю существование предположения и могу поставить его под сомнение. Затем я задумаюсь о необходимом мне виде гибкости, и уже потом буду выбирать структуру кода.

Давайте рассмотрим ещё один пример.

В интерпретациях языков программирования есть различные типы узлов, соответствующих примитивам: константы, операторы, циклы, ветвление, функции, типы и т.д. Нам нужно сгенерировать код для них всех.


Отлично! Можно создать по одному классу для каждого типа узла, и они все могут наследоваться от базового класса Node. Но мы основываемся на предположении, что будем чаще добавлять строки и реже столбцы. Что происходит в оптимизирующем компиляторе? Мы добавляем новые проходы оптимизации. И каждый из них — это новый столбец.


Если я хочу добавить новый проход оптимизации, то мне нужно будет добавлять новый метод к каждому классу, и весь код прохода оптимизации будет разнесён по разным модулям. Я хочу избежать такой ситуации! Поэтому в некоторых системах поверх этого добавляется ещё один слой. С помощью паттерна «посетитель» (visitor) я могу хранить весь код слияния циклов в одном модуле, а не разбивать его на множество файлов.

Если взглянуть на транспонированную матрицу, то нам откроется ещё один подход:


Теперь вместо классов с методами я могу использовать меченные объединения (tagged union) и сопоставление с образцом (pattern matching) (они поддерживаются не во всех языках программирования). Благодаря этому весь код каждого прохода оптимизации будет храниться вместе и сможет обойтись без косвенности паттерна «посетитель».

Часто бывает полезно посмотреть на задачу с точки зрения матрицы. Если применить её к объектно-ориентированной структуре, о которой думают все, то это может привести меня к чему-то другому, например, к паттерну «сущность-компонент-система», реляционным базам данным или реактивному программированию.

И это касается не только кода. Вот пример применения этой идеи к продуктам. Допустим, что существуют люди с разными интересами:


Если бы я разрабатывал сайт социальной сети, то мог бы позволить людям следить за новостями других людей. Ник может подписаться на Алису, потому что им обоим интересны автомобили, и на Феня, потому что они оба интересуются путешествиями. Но Ник будет также получать посты Алисы о математике и посты Феня о политике. Если бы я рассматривал транспонированную матрицу, то мог бы позволить людям подписываться на темы. Ник мог бы вступить в группу любителей машин, а также в группу путешественников. Facebook и Reddit начали своё существование примерно в одно время, но они являются транспонированными матрицами друг друга. Facebook позволяет подписываться на людей; Reddit позволяет подписываться на темы.

Когда я захожу в тупик или когда хочу рассмотреть альтернативы, то смотрю на задачу и ищу в ней разные оси упорядочивания. Иногда взгляд на задачу под другим углом способен обеспечить более хорошее решение.

Мозговой штурм при помощи разложения

Я использую и другую технику, которая называется «разложение».

В алгебре операция разложения преобразует многочлен вида 5x? + 8x — 21 в (x + 3)·(5x — 7). Чтобы решить уравнение 5x? + 8x — 21 = 0, мы сначала можем разложить его в (x + 3)·(5x — 7) = 0. Затем мы можем сказать, что x + 3 = 0 или 5x — 7 = 0. Разложение превращает сложную задачу в несколько более лёгких задач.


Давайте взглянем на пример: у меня есть шесть классов: File, EncryptedFile, GzipFile, EncryptedGzipFile, BzipFile, EncryptedBzipFile. Я могу разложить их в матрицу:


С помощью паттерна «декоратор» (или примесей) я превратил шесть разных типов файлов в четыре компонента: plain, gzip, bzip, encrypt. Не похоже, чтобы это позволило много сэкономить, но если я добавлю больше вариаций, то экономия будет увеличиваться. Разложение превращает O(M*N) компонентов в O(M+N) компонентов.

Ещё один пример: иногда люди задают мне вопросы типа «как написать на C# линейную интерполяцию?». Я могу написать множество потенциальных туториалов:


Если есть M тем и N языков, то я могу написать M*N туториалов. Однако это куча работы. Вместо этого я напишу туториал об интерполяции, кто-то другой напишет туториал про C#, а затем читатель объединит знания C# со знаниями об интерполяции, и напишет свою версию интерполяции на C#.

Как и транспонирование, разложение помогает не всегда, но если оно применимо, то может оказаться довольно полезным.

Мозговой штурм движением в обратную сторону

В предыдущих двух частях я рассказал о том, как иногда подхожу к задаче, пытаясь упорядочить её в матрицу. Иногда это не помогает и тогда я пробую посмотреть на задачу в обратном направлении. Давайте например рассмотрим процедурную генерацию карт. Часто я начинаю с функции шума, потом добавляю октавы, настраиваю параметры и добавляю слои. Я делаю так, потому что мне нужны карты, обладающие определёнными свойствами.


Вполне можно начать с экспериментов с параметрами, но пространство параметров довольно велико, и неизвестно, найду ли я параметры, наиболее соответствующие моим требованиям. Поэтому немного поэкспериментировав, я останавливаюсь и начинаю думать в обратном порядке: если я могу описать то, что мне нужно, то это может помочь в поиске параметров.

Именно такая мотивация заставила меня изучать алгебру. Если у нас есть уравнение вида 5x? + 8x — 21 = 0, то каким будет x? Когда я не знал алгебры, я бы решал это уравнение, пробуя подставлять разные значения x, сначала выбирая их случайным образом, а затем подстраивая их, когда почувствую, что подобрался к решению близко. Алгебра даёт нам инструмент, позволяющий пойти в другом направлении. Вместо угадывания ответов она даёт мне аппарат (разложение, или квадратные уравнения, или ньютоновский метод итеративного поиска корней), который я могу более осознанно использовать для поиска значений x (-3 или 7/5).

Я чувствую, что часто попадаю в такую ситуацию в программировании. При работе над генерацией процедурных карт, какое-то время поэкспериментировав с параметрами, я остановился и составил список того, что должно быть в игровых мирах одного проекта:

1. Игроки должны начинать игру далеко от берега.
2. При повышении уровня игроки должны подниматься с гору.
3. У игроков не должно быть возможности достичь края карты.
4. С ростом уровня игроки должны объединяться в группы.
5. На побережьях должны быть простые монстры без большой вариативности.
6. На равнинах должно быть большое разнообразие монстров средней сложности.
7. В гористой местности должны быть сложные монстры-боссы.
8. Должен существовать какой-то ориентир, позволяющий игрокам оставаться на одном уровне сложности, и ещё один ориентир, позволяющий подниматься или опускаться в уровне сложности.

Составление этого списка привело к созданию следующих ограничений:

1. Игровые миры должны быть островами со множеством побережий и небольшим пиком в центре.
2. Высота над уровнем моря должна соответствовать сложности монстров.
3. На малой и большой высотах должна быть меньшая вариативность биомов, чем на средних высотах.
4. Дороги должны оставаться на одном уровне сложности.
5. Реки должны течь с большой на малую высоту, и предоставлять игрокам возможность перемещаться вверх/вниз.

Эти ограничения привели меня к созданию дизайна генератора карт. А он привёл к генерации гораздо лучшего набора карт, чем те, которые я получал настройкой параметров, как это делаю обычно. А получившаяся в результате статья заинтересовала многих людей созданием карт на основе диаграмм Вороного.

Ещё один пример — юнит-тесты. Предполагается, что я должен придумать список примеров для проверки. Например, для сеток из шестиугольников я могу подумать, что мне нужно проверять условие add(Hex(1, 2), Hex(3, 4)) == Hex(4, 6). Потом я могу вспомнить что нужно проверить нули: add(Hex(0, 1), Hex(7, 9)) == Hex(7, 10). Потом я могу вспомнить, что нужно проверять и отрицательные значения: add(Hex(-3, 4) + Hex(7, -8)) == Hex(4, -4). Ну вот, отлично, у меня есть несколько юнит-тестов.

Но если подумать чуть дальше, то на самом деле я проверяю add(Hex(A, B), Hex(C, D)) == Hex(A+C, B+D). Я придумал три показанных выше примера, основываясь на этом общем правиле. Я иду в обратном направлении от этого правила, чтобы прийти к юнит-тестам. Если я смогу напрямую закодировать это правило в тестовую систему, то сама система сможет работать в обратном порядке, чтобы создавать примеры для тестирования. Это называется «property-based-тестирование». (См. также: метаморфическое тестирование)

Ещё один пример: солверы ограничений. В таких системах пользователь описывает то, что хочет видеть на выходе, и система находит способ удовлетворения этих ограничений. Цитата из Procedural Content Generation Book, глава 8:

С помощью конструктивных методов из Главы 3, а также методов фракталов и шумов из Главы 4 мы можем создавать различные виды выходных данных, настраивая алгоритмы, пока нас не начнёт устраивать их выходные данные. Но если мы знаем, какими свойствами должен обладать генерируемый контент, то будет удобнее непосредственно указать, чего мы хотим, чтобы общий алгоритм нашёл контент, удовлетворяющий нашим критериям.

В этой книге описывается программирование наборов ответов (Answer Set Programming, ASP), при котором мы описываем структуру того, с чем работаем (тайлы являются полом и стенами, тайлы граничат друг с другом), структуру решений, которые мы ищем (подземелье — это группа соединённых тайлов с началом и концом) и свойства решений (боковые проходы должны содержать не более 5 комнат, в лабиринте должно быть 1-2 петли, нужно победить троих помощников, прежде чем добраться до босса). После этого система создаёт возможные решения и позволяет вам решать, что с ними делать.

Недавно был разработан солвер ограничений, который вызвал большой интерес благодаря своему крутому названию и любопытным демо: Wave Function Collapse (коллапс волновой функции). [Про этот солвер есть статья на Хабре.] Если передать ему изображения-примеры, чтобы сообщить, какие ограничения накладываются на соседние тайлы, то он создаст новые примеры, соответствующие заданным паттернам. Его работа описана в статье WaveFunctionCollapse is Constraint Solving in the Wild:

WFC реализует метод жадного поиска без возврата назад. В этой статье WFC исследуется как пример методов решений с учётом ограничений.

Мне уже многого удалось добиться с помощью солверов ограничений. Как и в случае с алгеброй, прежде чем я научусь использовать их эффективно, мне нужно многому научиться.

Ещё один пример: созданный мной космический корабль. Игрок может перетаскивать двигатели, куда угодно, и система будет определять, какие двигатели нужно активировать при нажатии на W, A, S, D, Q, E. Например, в этом корабле:


Если вы хотите полететь вперёд, то включаете два задних двигателя. Если хотите повернуться влево, то включаете правый задний и левый передний двигатели. Я пробовал искать решение, заставляя систему перебирать множество параметров:


Система работала, но не идеально. Позже я осознал, что это ещё один пример того, где бы могло помочь решение в обратном направлении. Оказалось, что движение космических кораблей может быть описано линейной системой ограничений. Если бы я это понял, то мог бы использовать готовую библиотеку, точно решающую ограничения, а не свой метод проб и ошибок, возвращающий аппроксимацию.

И ещё один пример: проект G9.js, в котором можно перетаскивать по экрану выходные данные некой функции, и он определяет, как изменять входные данные, чтобы соответствовать желаемым данным на выходе. Демки G9.js выглядят отлично! Обязательно раскомментируйте в демо Rings строку «uncomment the following line».

Иногда бывает полезно подумать о задаче в обратном порядке. Часто выясняется, что это даёт мне более качественные решения, чем при рассуждениях в прямом направлении.