[Перевод] Мозговой штурм: как смотреть на задачи под другим углом
Мозговой штурм с помощью транспонирования
Иногда я захожу в тупик и мне приходится искать способы думать над задачей под другим углом. Бывают задачи, которые можно отобразить в виде матрицы или таблицы. Их структура выглядит примерно так:
Ячейки, с которыми я работаю, выстроены в столбцы и строки. Давайте возьмём пример из простой игры:
Строки — это классы персонажей: воин, маг, вор.
Столбцы — это типы действий: нападение, защита, особое действие.
Матрица содержит весь код для обработки каждого из типов действий для каждого типа персонажа.
Обычно подобные структуры упорядочивают в такие модули: Как выглядит код?
Fighter
будет содержать код для обработки ударов мечом, снижения урона с помощью брони и особого мощного удара.Mage
будет содержать код обработки фаерболов, отражения урона и особую атаку заморозкой.Thief
будет содержать код для обработки атак кинжалом, избегания урона уклонением и особую обезоруживающую атаку.
Иногда бывает полезно транспонировать матрицу. Мы можем упорядочить её по другой оси:
Attack
будет содержать код обработки ударов мечом, стрельбы фаерболами и атак кинжалом.Defend
будет содержать код обработки снижения урона, отражения урона и ускользания от урона.Special
будет содержать код обработки мощного удара, заморозки и обезоруживания.
Меня учили, что один стиль «хорош», а другой «плох». Но мне не очевидно, почему всё должно быть именно так. Причина заключается предположении, что мы чаще будем добавлять новые классы персонажей (существительные), и редко добавлять новые виды действий (глаголы). Таким образом я смогу добавить код с помощью нового модуля, не трогая все имеющиеся. В вашей игре всё может быть иначе. Взглянув на транспонированную матрицу, я осознаю существование предположения и могу поставить его под сомнение. Затем я задумаюсь о необходимом мне виде гибкости, и уже потом буду выбирать структуру кода.
Давайте рассмотрим ещё один пример.
Нам нужно сгенерировать код для них всех. В интерпретациях языков программирования есть различные типы узлов, соответствующих примитивам: константы, операторы, циклы, ветвление, функции, типы и т.д.
Отлично! Можно создать по одному классу для каждого типа узла, и они все могут наследоваться от базового класса Node
. Но мы основываемся на предположении, что будем чаще добавлять строки и реже столбцы. Что происходит в оптимизирующем компиляторе? Мы добавляем новые проходы оптимизации. И каждый из них — это новый столбец.
Если я хочу добавить новый проход оптимизации, то мне нужно будет добавлять новый метод к каждому классу, и весь код прохода оптимизации будет разнесён по разным модулям. Я хочу избежать такой ситуации! Поэтому в некоторых системах поверх этого добавляется ещё один слой. С помощью паттерна «посетитель» (visitor) я могу хранить весь код слияния циклов в одном модуле, а не разбивать его на множество файлов.
Если взглянуть на транспонированную матрицу, то нам откроется ещё один подход:
Теперь вместо классов с методами я могу использовать меченные объединения (tagged union) и сопоставление с образцом (pattern matching) (они поддерживаются не во всех языках программирования). Благодаря этому весь код каждого прохода оптимизации будет храниться вместе и сможет обойтись без косвенности паттерна «посетитель».
Если применить её к объектно-ориентированной структуре, о которой думают все, то это может привести меня к чему-то другому, например, к паттерну «сущность-компонент-система», реляционным базам данным или реактивному программированию. Часто бывает полезно посмотреть на задачу с точки зрения матрицы.
Вот пример применения этой идеи к продуктам. И это касается не только кода. Допустим, что существуют люди с разными интересами:
Если бы я разрабатывал сайт социальной сети, то мог бы позволить людям следить за новостями других людей. Ник может подписаться на Алису, потому что им обоим интересны автомобили, и на Феня, потому что они оба интересуются путешествиями. Но Ник будет также получать посты Алисы о математике и посты Феня о политике. Если бы я рассматривал транспонированную матрицу, то мог бы позволить людям подписываться на темы. Ник мог бы вступить в группу любителей машин, а также в группу путешественников. Facebook и Reddit начали своё существование примерно в одно время, но они являются транспонированными матрицами друг друга. Facebook позволяет подписываться на людей; Reddit позволяет подписываться на темы.
Иногда взгляд на задачу под другим углом способен обеспечить более хорошее решение. Когда я захожу в тупик или когда хочу рассмотреть альтернативы, то смотрю на задачу и ищу в ней разные оси упорядочивания.
Мозговой штурм при помощи разложения
Я использую и другую технику, которая называется «разложение».
Чтобы решить уравнение 5x² + 8x — 21 = 0, мы сначала можем разложить его в (x + 3)·(5x — 7) = 0. В алгебре операция разложения преобразует многочлен вида 5x² + 8x — 21 в (x + 3)·(5x — 7). Разложение превращает сложную задачу в несколько более лёгких задач. Затем мы можем сказать, что 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).
При работе над генерацией процедурных карт, какое-то время поэкспериментировав с параметрами, я остановился и составил список того, что должно быть в игровых мирах одного проекта: Я чувствую, что часто попадаю в такую ситуацию в программировании.
- Игроки должны начинать игру далеко от берега.
- При повышении уровня игроки должны подниматься с гору.
- У игроков не должно быть возможности достичь края карты.
- С ростом уровня игроки должны объединяться в группы.
- На побережьях должны быть простые монстры без большой вариативности.
- На равнинах должно быть большое разнообразие монстров средней сложности.
- В гористой местности должны быть сложные монстры-боссы.
- Должен существовать какой-то ориентир, позволяющий игрокам оставаться на одном уровне сложности, и ещё один ориентир, позволяющий подниматься или опускаться в уровне сложности.
Составление этого списка привело к созданию следующих ограничений:
- Игровые миры должны быть островами со множеством побережий и небольшим пиком в центре.
- Высота над уровнем моря должна соответствовать сложности монстров.
- На малой и большой высотах должна быть меньшая вариативность биомов, чем на средних высотах.
- Дороги должны оставаться на одном уровне сложности.
- Реки должны течь с большой на малую высоту, и предоставлять игрокам возможность перемещаться вверх/вниз.
Эти ограничения привели меня к созданию дизайна генератора карт. А он привёл к генерации гораздо лучшего набора карт, чем те, которые я получал настройкой параметров, как это делаю обычно. А получившаяся в результате статья заинтересовала многих людей созданием карт на основе диаграмм Вороного.
Предполагается, что я должен придумать список примеров для проверки. Ещё один пример — юнит-тесты. Потом я могу вспомнить что нужно проверить нули: add(Hex(0, 1), Hex(7, 9)) == Hex(7, 10)
. Например, для сеток из шестиугольников я могу подумать, что мне нужно проверять условие add(Hex(1, 2), Hex(3, 4)) == Hex(4, 6)
. Ну вот, отлично, у меня есть несколько юнит-тестов. Потом я могу вспомнить, что нужно проверять и отрицательные значения: 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».
Часто выясняется, что это даёт мне более качественные решения, чем при рассуждениях в прямом направлении. Иногда бывает полезно подумать о задаче в обратном порядке.