Саша Беспоясов
Это я.

Рисуем деревья, часть 3. От дерева Пифагора к настоящему

Заканчиваем писать рисовалку деревьев по канонам ООП и чистой архитектуры.

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

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

В этом заключительном посте напишем «переводчик» с языка L-систем на язык команд для рисования на canvas. Сгенерируем дерево Пифагора, добавим ему случайности и цвета, чтобы оно стало похоже на настоящее дерево.

Пишем интерпретатор

Задача этого модуля в том, чтобы получить символьное представление L-системы и превратить его в набор команд для рисовалки. Спроектируем API модуля и его зависимости.

Публичное API и зависимости модуля
Публичное API и зависимости модуля

Он будет зависеть от модуля геометрии и предоставлять будет интерфейс SystemInterpreter. Объявим API:

// src/interpreter/types.ts

export interface SystemInterpreter {
  translate(expression: Expression): List<Line>;
}

...И начнём писать реализацию:

// src/interpreter/implementation.ts

import { AppSettings } from "../settings";
import { StartSelector } from "../geometry/location";
import { ShapeBuilder } from "../geometry/shape";
import { Stack } from "./stack/types";
import { SystemInterpreter } from "./types";

export class SystemToGeometryMapper implements SystemInterpreter {
  // Эти поля будем менять по ходу построения списка команд:
  private currentLocation: Point = { x: 0, y: 0 };
  private currentAngle: DegreesAmount = 0;

  // В этих полях будем хранить список символов
  // и список команд, которые этим символам соответствуют:
  private systemTokens: List<Character> = [];
  private drawInstructions: List<Line> = [];

  // Объявляем зависимости:
  constructor(
    private shapeBuilder: ShapeBuilder,
    private startSelector: StartSelector,
    private stack: Stack<TreeJoint>,
    private settings: AppSettings,
  ) {}

  // Реализуем публичный метод:
  public translate(expression: Expression): List<Line> {
    this.currentLocation = { ...this.startSelector.selectStart() };
    this.systemTokens = expression.split("");
    this.systemTokens.forEach(this.translateToken);
    return this.drawInstructions;
  }

  // …
}

В методе translate мы принимаем выражение и разбиваем его на символы. Каждый из этих символов обрабатываем приватным методом translateToken, который напишем позже. Как результат возвращаем массив drawInstructions, в котором храним все уже переведённые команды.

Вы могли обратить внимание, что в зависимостях среди прочих есть Stack<TreeJoint>. Я не стал указывать его в списке зависимостей на диаграмме, потому что это по сути реализация структуры данных — библиотечный код, бизнес-логики особо не несёт.

Если вы не знакомы с тем, как работает стек, то рекомендую прочесть статью о нём и посмотреть его реализацию в исходниках.

Вернёмся к реализации, напишем приватный метод translateToken:

// src/interpreter/implementation.ts

export class SystemToGeometryMapper implements SystemInterpreter {
  // …

  private translateToken = (token: Character): void => {
    switch (token) {
      // Если мы встречаем среди символов 0 или 1,
      // рисуем линию из текущего положения на плоскости
      // и текущим углом:
      case "0":
      case "1": {
        const line = this.shapeBuilder.createLine(
          this.currentLocation,
          this.settings.stemLength,
          this.currentAngle,
        );

        this.drawInstructions.push(line);
        this.currentLocation = { ...line.end };
        break;
      }

      // При открывающей скобке мы «поворачиваем влево»
      // и кладём текущее положение и угол в стек:
      case "[": {
        this.currentAngle -= this.settings.jointAngle;
        this.stack.push({
          location: { ...this.currentLocation },
          rotation: this.currentAngle,
          stemWidth: this.settings.stemLength,
        });

        break;
      }

      // При закрывающей скобке вытаскиваем последнее положение
      // из стека и используем его как текущие,
      // а направление переводим направо:
      case "]": {
        const lastJoint = this.stack.pop();
        this.currentLocation = { ...lastJoint.location };
        this.currentAngle = lastJoint.rotation + 2 * this.settings.jointAngle;
        break;
      }
    }
  };
}

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

Давайте попробуем обновить настройки, вызвать метод и посмотреть, что получится:

// src/settings/index.ts

export const settings: AppSettings = {
  canvasSize: {
    width: 800,
    height: 600,
  },

  // Используем 5 итераций,
  // правила — те же, для дерева Пифагора:
  iterations: 5,
  initiator: "0",
  rules: {
    "1": "11",
    "0": "1[0]0",
  },

  // Длина секции ствола 10 пикселей,
  // поворачиваем всегда на 45 градусов.
  stemLength: 10,
  jointAngle: 45,
};

Правим входную точку:

// src/index.ts

const builder = container.get<SystemBuilder>();
const drawer = container.get<Drawer>();
const interpreter = container.get<SystemInterpreter>();
const settings = container.get<AppSettings>();

const system = builder.build(settings);
const lines = interpreter.translate(system);
lines.forEach((line) => drawer.drawLine(line));

При таких настройках мы получим классическое дерево Пифагора, крайние отрезки которого — это листья.

Пятая итерация дерева Пифагора; на очередной итерации из каждой ветки появляется по 2 новых
Пятая итерация дерева Пифагора; на очередной итерации из каждой ветки появляется по 2 новых

Можно поиграться с углом и посмотреть, какие фигуры можно сотворить 😃

Угол в 90 градусов превращает дерево в «антенну»
Угол в 90 градусов превращает дерево в «антенну»
Угол в 15 градусов — в «колосок»
Угол в 15 градусов — в «колосок»
Угол в 115 градусов — в... эмм...
Угол в 115 градусов — в... эмм...

Отлично, основа дерева есть! Но прежде, чем мы сделаем деревья похожими на настоящие, нам стоит привести в порядок входную точку в приложение.

Приводим в порядок входную точку приложения

Сейчас код старта приложения выглядит плохо:

// src/index.ts

const builder = container.get<SystemBuilder>();
const drawer = container.get<Drawer>();
const interpreter = container.get<SystemInterpreter>();
const settings = container.get<AppSettings>();

const system = builder.build(settings);
const lines = interpreter.translate(system);
lines.forEach((line) => drawer.drawLine(line));

Мы получаем из контейнера слишком много сервисов, вызываем всё руками, это некруто. Давайте спрячем все операции в одном объекте, который будет отвечать за старт приложения. Создадим интерфейс Application:

// src/app/types.ts

export interface Application {
  start(): void;
}

...Спрячем весь код за методом start:

// src/app/implementation.ts

export class App implements Application {
  constructor(
    private builder: SystemBuilder,
    private drawer: Drawer,
    private interpreter: SystemInterpreter,
    private settings: AppSettings,
  ) {}

  start(): void {
    const system = this.builder.build(this.settings);
    const lines = this.interpreter.translate(system);
    lines.forEach((line) => this.drawer.drawLine(line));
  }
}

...И зарегистрируем его:

// src/app/composition.ts

import { container } from "../composition";
import { App } from "./implementation";
import { Application } from "./types";

container.registerSingleton<Application, App>();

...А вызывать будем так:

// src/index.ts

import { container } from "./composition";
import { Application } from "./app/types";

const app = container.get<Application>();
app.start();

Вот, теперь гораздо чище.

Делаем деревья более реальными

Напомню, что идею того, как именно сделать деревья более реальными, я позаимствовал из того самого видео об L-системах, обязательно сходите посмотреть.

Сейчас наши деревья слишком строгие и «математические». Чтобы они были больше похожи на настоящие, надо добавить случайности и динамики, а именно:

  • Толщина ствола должна со временем уменьшаться;
  • Угол должен меняться на случайное значение в каком-то диапазоне;
  • Ветви должны появляться из относительно случайных мест ствола;
  • Листья должны быть зелёного цвета 😃

Первым делом слегка поменяем правила L-системы. Добавим новую константу "2", она позволит дереву не уменьшать длину веток слишком быстро. Сейчас на каждую итерацию длина сокращается в два раза, новый символ замедлит этот процесс.

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

Обозначим также начальную ширину ствола и ширину листьев, к ним мы вернёмся позже.

// src/settings/index.ts

export const settings: AppSettings = {
  // …

  iterations: 12,
  initiator: "22220",
  rules: {
    "1": "21",
    "0": "1[20]20",
  },

  leafWidth: 4,
  stemWidth: 16,

  // …
};

Теперь изменим код интерпретатора.

export class SystemToGeometryMapper implements SystemInterpreter {
  private currentLocation: Point = { x: 0, y: 0 };
  private currentAngle: DegreesAmount = 0;

  // Будем менять не только положение и угол, но и ширину ствола:
  private currentWidth: PixelsAmount = 0;

  private systemTokens: List<Character> = [];
  private drawInstructions: List<Instruction> = [];

  constructor(
    private shapeBuilder: ShapeBuilder,
    private startSelector: StartSelector,
    private stack: Stack<TreeJoint>,
    private settings: AppSettings,

    // Нам здесь понадобится источник рандома,
    // это обёртка над Math.random с более удобным API,
    // предоставляет целочисленные случайные значения.
    // Код этого модуля можно также найти на Гитхабе.
    private random: RandomSource,
  ) {}

  // …
}

Дальше правим перевод символов, если мы встречаем лист, красим его в случайно выбранный зелёный цвет:

private translateToken = (token: Character): void => {
  switch (token) {
    case "0": {
      const line = this.createLine();

      this.currentLocation = { ...line.end };
      this.drawInstructions.push({
        line,
        color: this.selectLeafColor(),  // Добавляем зелёный цвет
        width: this.settings.leafWidth, // и ширину листа.
      });

      break;
    }

    // …
  }
}

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

private translateToken = (token: Character): void => {
  switch (token) {
    // …

    case "1":
    case "2": {
      // Рисуем ветки только в 60% случаев:
      if (this.shouldSkip()) return;

      const line = this.createLine();
      this.drawInstructions.push({ line, width: this.currentWidth });
      this.currentLocation = { ...line.end };

      break;
    }

    // …
  }
};

При повороте также уменьшаем ширину веток и добавляем случайное отклонение в угол поворота:

private translateToken = (token: Character): void => {
  switch (token) {
    // …

    case "[": {
      // Уменьшаем ширину ветки:
      this.currentWidth *= 0.75;

      // Добавляем случайное отклонение от поворота:
      this.currentAngle -=
        this.settings.jointAngle + this.randomAngleDeviation();

      // Запоминаем место разветвления, ширину и угол,
      // чтобы потом вернуться сюда и повернуть в другую сторону:
      this.stack.push({
        location: { ...this.currentLocation },
        rotation: this.currentAngle,
        stemWidth: this.currentWidth,
      });

      break;
    }

    case "]": {
      // Получаем место последнего разветвления:
      const lastJoint = this.stack.pop();

      // Используем его положение, угол и ширину,
      // чтобы создать вторую ветку:
      this.currentWidth = lastJoint.stemWidth;
      this.currentLocation = { ...lastJoint.location };
      this.currentAngle =
        lastJoint.rotation +
        2 * this.settings.jointAngle +
        this.randomAngleDeviation();

      break;
    }
  }
};

Добавим также все приватные методы, которых не хватает сейчас:

export class SystemToGeometryMapper implements SystemInterpreter {
  // …

  private createLine = (): Line => {
    return this.shapeBuilder.createLine(
      this.currentLocation,
      this.settings.stemLength,
      this.currentAngle,
    );
  };

  // В 40% случаев не рисуем ветки:
  private shouldSkip = (): boolean => {
    return this.random.getValue() > 0.4;
  };

  // Случайное отклонение угла будет колебаться
  // в пределах от -5 до 5 градусов:
  private randomAngleDeviation = (): Angle => {
    return this.random.getBetweenInclusive(-5, 5);
  };

  // Случайно выбираем среди 3 зелёных цветов:
  private selectLeafColor = (): Color => {
    const randomColor = this.random.getBetweenInclusive(0, 2);
    return leafColors[randomColor];
  };
}

…А теперь попробуем наконец запустить и посмотреть на результат.

Результат работы генератора
Результат работы генератора

Получилось настоящее дерево! 🌳

Все изменения локальны

Что важно отметить, последние изменения ограничены модулем Interpreter. Хотя рисунок и изменился сильно, мы изменили только реализацию интерпретатора. Остальные модули остались прежними.

Более того, интерфейсы тоже остались прежними, нам не пришлось менять ни SystemInterpreter, ни ShapeBuilder:

Мы можем заменить реализацию, не меняя места соединения модулей
Мы можем заменить реализацию, не меняя места соединения модулей

С тем же успехом мы могли бы полностью заменить реализацию интерпретатора на другую! Могли бы рисовать трёхмерное дерево или не дерево вовсе, а другой фрактал. При условии, что интерфейсы сохранились, приложение бы работало, как ни в чём ни бывало:

Реализация может быть совершенно другой
Реализация может быть совершенно другой

Что у нас получилось

Давайте теперь соберём всю систему и посмотрим, в каких отношениях находятся модули друг с другом.

Диаграмма всех компонентов приложения с отмеченными входами и выходами
Диаграмма всех компонентов приложения с отмеченными входами и выходами

Модули соединены контрактами на поведение — интерфейсами. Пока интерфейсы не меняются, можно заменить реализацию любого модуля на другую, и приложение продолжит работать.

Это полезно при тестировании: каждый модуль можно тестировать в изоляции ото всех остальных. Зависимости мы можем заменить моками, реализующими те же интерфейсы. Тогда не придётся создавать экземпляров настоящих зависимостей.

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

Ещё один плюс — возможность по-разному сочетать модули в сборках, чтобы деплоить приложение кусками. Очень подробно об этом написано в DDD, Hexagonal, Onion, Clean, CQRS, …How I put it all together.

Если мы, например, хотим обновить конкретный слой приложения, то мы можем перепубликовать только модули из этого слоя:

Диаграмма архитектуры компонентов с выделенными слоями
Диаграмма архитектуры компонентов с выделенными слоями

Направление зависимостей — всегда к домену, из-за чего доменный слой максимально независим. Мы можем его переиспользовать в приложении для другой платформы и с другой инфраструктурой.

Заметка на полях об инфраструктуре и Share Kernel

Под инфраструктурой обычно понимают код, с помощью которого мы цепляемся к БД, поиску и другим управляемым внешним сервисам.

У нас инфраструктуры не было, потому что не было необходимости сохранять результат в БД или в виде картинки. (Ставь лойс, если хочешь, чтобы появился модуль сохранения изображений в файл.)

Концептуально инфраструктурные модули были бы очень похожи:

  • в прикладном слое мы бы описали условия, при которых нам нужно сохранить изображение в файл, а также порты — как именно наше приложение хочет сохранить данные;
  • в слое адаптеров — как подружить наш порт и интерфейсы внешних сервисов.

Shared Kernel — это всё, от чего одновременно зависят несколько модулей, будучи при этом всё ещё расцепленными. В нашем случае это может быть lib.d.ts, потому что мы используем его, даже не замечая.

Если копнуть чуть шире, то с оговоркой настройки и аннотации доменных типов в нашем приложении тоже можно назвать Shared Kernel.

Мы не ссылаемся на модуль L-system, чтобы получить из него тип Expression; аннотации у нас доступны всем модулям, хотя они при этом всё ещё расцеплены. Это, правда, больше особенность аннотаций — ведь если мы «запечатаем» типы внутри .ts файлов, то нам придётся импортировать их обычным import.

Что ещё можно улучшить

Если побыть идеалистами, то можно придумать себе ещё кучу задач 😃
Ну, например:

  • Добавить паттерн-матчинг в метод translateToken класса SystemToGeometryMapper, чтобы рассказать ему, какие токены могут попасться, а какие нет.
  • Сделать тип Instruction более расширяемым, вынеся настройки «кисти» в под-объект.
  • Вынести цвета листьев в настройки; будет полезно для «тем» (листья на закате, ночью).
  • Реализовать адаптер для PixelRatioSource, чтобы не зависеть напрямую от window.
  • В интерфейсе ElementSource возвращать не Nullable<HTMLElement>, а свой собственный тип, чтобы не привязываться к HTML-разметке.
  • Имитировать internal-реализации, экспортируя наружу только типы и композицию из каждого модуля.
  • Сделать интерпретатор компактнее: по зависимостям определить, на какие подмодули его разбить, чтобы класс не был таким большим как сейчас.

В общем, можно ещё над чем-то поработать, но для примера проектирования архитектуры — вполне сойдёт 🙂

Список литературы

Другие посты из серии, репозиторий с исходниками и проект живьём:

Ссылки из последнего поста:

L-системы, фракталы и вот это всё:

Архитектура, ООП, DI:

Принципы SOLID:

Шаблоны проектирования, TypeScript, C#:

Инструменты:

Неделя в @jsunderhoodРисуем деревья, часть 2. Геометрия, графика и работа с DOM