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

Автор оригинала: Amit Patel
  • Перевод

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


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

A B C D E
1 A1 B1 C1 D1 E1
2 A2 B2 C2 D2 E2
3 A3 B3 C3 D3 E3
4 A4 B4 C4 D4 E4
5 A5 B5 C5 D5 E5

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

Attack Defend Special
Fighter sword armor slam
Mage fireball reflect freeze
Thief dagger dodge disarm

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

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

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

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

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

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

Fighter Mage Thief
Attack sword fireball dagger
Defend armor reflect dodge
Special slam freeze disarm

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

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

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

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

Generate Code
Constant
Operator
Loop
Branch
Function
Type

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

Generate Code Data flow Constant folding Loop fusion
Constant
Operator
Loop
Branch
Function
Type

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

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

Constant Operator Loop Branch Function Type
Generate code
Data flow
Constant folding
SSA
Loop fusion

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

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

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

Nick Feng Sayid Alice
cars X X
politics X X
math X X
travel X X

Если бы я разрабатывал сайт социальной сети, то мог бы позволить людям следить за новостями других людей. Ник может подписаться на Алису, потому что им обоим интересны автомобили, и на Феня, потому что они оба интересуются путешествиями. Но Ник будет также получать посты Алисы о математике и посты Феня о политике. Если бы я рассматривал транспонированную матрицу, то мог бы позволить людям подписываться на темы. Ник мог бы вступить в группу любителей машин, а также в группу путешественников. 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. Разложение превращает сложную задачу в несколько более лёгких задач.

x 3
5x 5x² 15x
-7 -7x -21

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

Uncompressed Gzip Bzip
Unencrypted File Gzip(File) Bzip(File)
Encrypted Encrypt(File) Encrypt(Gzip(File)) Encrypt(Bzip(File))

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

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

C++ Python Java C# Javascript Rust Idris
Interpolation
Neighbors
Pathfinding
Distances
River maps
Isometric
Voronoi
Transforms

Если есть 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».

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

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

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 23

    0

    Отличный пример для того, что ООП — это просто ужас. Система трейтов отлично реализует ваш случай, и совершенно не требует отвечать на Экзистенциальный Вопрос Объектного Программирования — "Что Есть Объект?".


    Смотрите:


    trait Special{
       fn do_special(self, Other) where Other: Player + Mob;
    
    }
    trait Attack{
       fn do_attack(self, Other) where Other: Player + Mob;
    }
    
    impl Special For Fighter {
    ...
    }
    
    impl Attack for Mage {
    ...
    }

    Можно даже сказать, что у нас есть класс (игровой) Dumb у которого нет Special. Тогда, если в коде мы попытаемся вызывать do_special, нам скажут, что трейт Special для Dumb не реализован. При компиляции.


    (код на Rust).


    Забудьте про ООП, это была удачная для GUI метафора, которую попытались возвести в статус религии.

      0
      Отличный пример для того, что ООП — это просто ужас. Система трейтов отлично реализует ваш случай, и совершенно не требует отвечать на Экзистенциальный Вопрос Объектного Программирования — "Что Есть Объект?".

      Разве то что вы написали нельзя реализовать интерфейсами в ООП?

        0

        Формально, языки с ООП парадигмой вполне тьюринг-полные, так что реализовать можно.


        Но интерфейсы по-прежнему подразумевают, что у нас есть жёсткая иерархия объектов, а это неправда в большинстве доменов. В Гуи — да, очень удачная модель. В большинстве других применений — просто нет.

          0
          Но интерфейсы по-прежнему подразумевают, что у нас есть жёсткая иерархия объектов

          Можете пояснить чем именно интерфейсы подразумевают жесткую иерархию объектов?

        +1
        Я думаю когда говорят о ООП религии подразумевают четкое следование всем канонам ООП (включая всеми ненавистную инкапсуляцию и набор паттернов проектирования, которые почему-то некоторые работодатели на интервью требуют знать наизусть)
        ООП это набор хороших практик, на которых держится мир, особенно мир геймдева где реально все объекты. Но это не значит что нельзя их нарушать — уже все издавна ООП языки позволяют подмешивать хорошие приемы функционального программирования и некоторые вещи выходят проще и красивее. Потихоньку появляются новые ООП приемы (прочитайте про миксины в Dart и возможно частично в Python- классная же штука)
          0

          В то же самое время появляются языки программирования, в которых ООП вообще отсутствует. Нет поддержки оператора GOTO (как было в Си), операторов управления ленточным накопителем (как было в кобол) и классов для наследования (как было в С++/java).

            0
            современные языки поддерживают много парадигм, плюс на выбор есть тонны архитектурных паттернов и тд. Для геймдева отлично подходят — композиция, ECS, событийная и реактивные модели. Это помимо ООП здорового человека (без фанатизма). Который тоже хорош. В любом проекте есть комбинация подходов, и это нормально. Я к тому что нормальный ООП до сих пор хорош и решает большинство вопросов.
              0
              Да они часто и не взаимоисключающи. Тот же ECS то же может быть ООП, но только в плане моделирования не предметной области, а механизмов самого ECS.
          +2
          Простите, но разве трейты — это не ООП?
            –3

            Нет. В Rust'е нет ни классов, ни наследования. А трейты есть. Трейты реализуются на структурах. Ключевая разница состоит в том, что методы в классе — это таблица методов (то есть indirect call), а ассоциированные функции для структуры и функции в реализации трейта — это compile-time вещь, в runtime — это обычные функции (прямой вызов), включая inline.

              +3
              А для программиста есть разница, от того что они «compile-time»? Мне всегда казалось, что ООП — это в первую очередь про семантику языка, а не про то, во что оно компилируется.
                –1

                Разница в производительности. Если вы вызываете метод у класса, это inderect call с нулём шансов на оптимизацию (есть есть jit, но там проблемы другого порядка). inderect call уже дорого, вызов функции тоже дорого. В 90% случаев функцию лучше инлайнить.


                Это называется zero cost abstractions и это одна из целей Rust'а. Пользователь городит выразительные отношения между типами и очень кратко и ёмко описывает что происходит с данными. Компилятор на это смотрит, проверяет отношения, а дальше потихоньку-полегоньку всю эту красоту до нескольких байт доводит.


                Справедливости ради в Rust есть dyn traits/trait objects (т.е. динамический диспатчинг методов), но его использование дороже, чем для нормальных трейтов (по описанной выше причине).


                Чем больше язык делает в compile time, тем меньше программа вынуждена выполнять ритуалы программиста в runtime, и тем быстрее она работает.

                  +1
                  Ну то есть, если разрабы Java перепишут компилятор так, чтобы он не использовал inderect call, то Java перестанет быть объектно-ориентированным языком?
                    0

                    А как они будут знать какой метод вызывать, если в объекте не будет таблицы указателей на методы?


                    ООП без таблицы методов не реализовать (если можно — хочу на это посмотреть), а таблица методов — это inderect call.


                    Но у java проблема куда большая — у неё все объекты на куче, т.е. являются указателями.

                      0
                      А как они будут знать какой метод вызывать, если в объекте не будет таблицы указателей на методы?
                      А не важно. Важен принцип, что в ваше классификации особенности рантайма важнее, чем нотация языка.
                        0

                        Нет, таблица методов — это не особенности рантайма, это основа ООП. Вы храните методы в классе, а так же имеете отношения с предком. Всё это — таблица методов (в лучшем случае) или таблицы методов с сылками (в худшем).

                        0
                        А как они будут знать какой метод вызывать, если в объекте не будет таблицы указателей на методы?

                        С++:
                        class A {
                            void foo() {cout << "Im a method, btw" << endl;}
                        }
                        

                        Вот незадача: в объекте нет таблицы указателей на метод, а метод есть. Это не OOP?
                          0

                          У вас нет объекта, для начала, а есть только класс. Инстансируете класс, получите таблицу методов.

                            0
                            Да, что вы такое говорите?
                            int main()
                            {
                               A a;
                            }
                            

                            В объекте a есть таблица методов?
                              0

                              Почитал. Нет, будет direct call. Чтобы таблица появилась, надо использовать виртуальные методы.

                                0
                                Воооот. Смотрите как интересно получилось — OOP есть, а таблицы методов нет. Тут можно заключить, что выводы
                                таблица методов — это не особенности рантайма, это основа ООП.

                                ООП без таблицы методов не реализовать

                                Ключевая разница состоит в том, что методы в классе — это таблица методов (то есть indirect call)

                                оказались немного поспешны, да и, собственно, трейты — это концепция разработанная внутри объектно-ориентированного подхода. А то как она сделана в различных ( в том числе не-ООP) языках — это как раз детали реализации.
                                  0
                                  Почитал. Нет, будет direct call. Чтобы таблица появилась, надо использовать виртуальные методы.

                                  да вы что, а тут что будет как вы думаете?
                                  struct A {
                                      virtual void foo() {cout << "Im a method, btw" << endl;}
                                  }
                                  struct B : public A {
                                      void foo() override {cout << "Im a method too" << endl;}
                                  }
                                  
                                  int main()
                                  {
                                     B b;
                                     b.foo();
                                  }
                                  
              0
              Статья перевод чей-то? Автор прыгает с примера на пример ничего толком не объясняя. Я еще не въехал что там про мага с вором и воином, зачем он вообще про это рассказывал, а он уже новую таблицу рисует… Непонятно…

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

              Самое читаемое