Хабрахабр

[Перевод] Мозговой штурм: как смотреть на задачи под другим углом

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

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

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

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

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

  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 = 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).

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

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

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

  1. Игровые миры должны быть островами со множеством побережий и небольшим пиком в центре.
  2. Высота над уровнем моря должна соответствовать сложности монстров.
  3. На малой и большой высотах должна быть меньшая вариативность биомов, чем на средних высотах.
  4. Дороги должны оставаться на одном уровне сложности.
  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».

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

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»