Системы переписывания строк и «вперед, Черепаха!»

Как-то в блоге уже упоминались L-системы, однако, в той статье был приведен код из весьма известной книги без каких-либо объяснений, но эксперименты с системами итерированных функций и простыми фрактальными отображениями заставили вспомнить и L-системы.

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

Итак, наш план: написать свою собственную реализацию «черепашьей графики», посредством создания своего исполнителя типа «черепаха», а уж потом, если получится, то реализовать таким образом какую-нибудь L-систему.

Что такое «черепаха»? Представьте себе следующую картину: есть некоторый обширный пляж в форме прямоугольника с достаточно большими сторонами. Внутри этого гигантского прямоугольного пляжа находится небольшая «черепаха», которая может перемещаться в любую точку прямоугольника, при этом она может как оставлять за собой след, так и идти вообще не оставляя никаких следов. Но, самое интересное: «черепаха» способна выполнять ряд достаточно простых команд, а оставленные ею на песке (в ходе выполнения наших команд) следы — есть некоторый рисунок, который впрочем может быть достаточно сложным и любопытным, несмотря на лежащие в его основе простые действия.

Исполнителю «черепаха» доступны следующие команды:

F пройти вперед, оставляя после себя след
f пройти вперед, не оставляя следа
+ повернутся вправо на некоторый угол
повернутся влево на некоторый угол
[ сохранить текущее состояние исполнителя
] восстановить состояние исполнителя

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

Определим внутреннее состояние «черепахи» как некоторую структуру, которая имеет всего три поля (хотя при желании количество полей можно увеличить, расширив при этом количество возможных степеней свободы исполнителя):

// внутренний мир черепахи :D
struct turtleState {
    float x, y, angle;
}

Логичнее всего, сделать это состояние одним из начальных аргументов в конструкторе класса Turtle, который и будет реализовывать весь спектр методов (и весь спектр поведения) нашей «черепахи»: все методы, которые отвечают за изменение внутреннего состояния исполнителя и один метод, который интерпретирует команды к исполнителю и изменяет на их основе его состояние.

Код класса:

// черепаха
class Turtle
{
    private:
        turtleState[] stateStack;
        turtleState state;
        float step, delta;
        Canvas canvas;
        Pen pen;

    // конструктор черепахи
    public this(Canvas canvas, turtleState state, float step, float delta)
    {
       this.state = state;
       this.step = step;
       this.delta = delta;
       this.canvas = canvas;
       pen = new Pen(SystemColors.darkGreen, 1, PenStyle.solid);
    }

    // шаг вперед с отрисовкой следа
    private void drawStep()
    {
       float newX, newY;
       newX = state.x + cos(state.angle) * step;
       newY = state.y - sin(state.angle) * step;
       canvas.drawLine(pen, cast(int) state.x, cast(int) state.y, cast(int) newX, cast(int) newY);
       state = turtleState(newX, newY, state.angle);
    }

    // шаг вперед без отрисовки следа
    private void moveStep()
    {
       float newX, newY;
       newX = state.x + cos(state.angle) * step;
       newY = state.y - sin(state.angle) * step;
       state = turtleState(newX, newY, state.angle);
    }

    // поворот влево
    private void rotateLeft()
    {
       float newAngle;
       newAngle = state.angle + delta;
       state = turtleState(state.x, state.y, newAngle);
    }

    // поворот вправо
    private void rotateRight()
    {
       float newAngle;
       newAngle = state.angle - delta;
       state = turtleState(state.x, state.y, newAngle);
    }

    // поворот на случайный угол
    private void rotateRandom()
    {
       import std.random;
       float newAngle;
       auto gen = Random(unpredictableSeed);
       newAngle = uniform(-fabs(state.angle), fabs(state.angle), gen);
       state = turtleState(state.x, state.y, newAngle);
    }

    // сохранить состояние черепахи
    private void saveState()
    {
        stateStack ~= state;
    }

    // восстановить состояние черепахи
    private void restoreState()
    {
        // size_t l = stateStack.length - 1;
        // state = stateStack[l];
        // stateStack = stateStack[0 .. l - 1];
        import std.array;
        state = stateStack.back();
        stateStack.popBack();
    }

    // изобразить все мучения черепахи :D
    public void draw(string s)
    {
       for (int i = 0; i < s.length; i++)
       {
        switch(s[i])
        {
           case 'F':
              drawStep();
              break;
           case 'f':
              moveStep();
              break;
           case '+':
              rotateRight();
              break;
           case '-':
              rotateLeft();
              break;
           case '?':
              rotateRandom();
              break;
           case '[':
              saveState();
              break;
           case ']':
              restoreState();
              break;
           default:
              break;
        }
       }
    }

}

Работа этого кода в принципе понятна из комментариев (и самого кода), однако, стоит все-таки немного пояснить: нетрудно заметить, что в коде только есть только один метод, который дает «ощутимый» (в отличие, от остальных) эффект — это метод drawStep, т.е. метод, который напрямую рисует очередное движение «черепахи».

Метод drawStep, как и другие методы, ответственные за движения, оперирует структурой (определена в блоке private) turtleState и на основе простых примитивов полярной системы координаты (x = r * cos(phi), y = r * sin(phi) — думаю, это узнаваемые формулы перехода от полярной системы координат к декартовой) вычисляет новое состояние (и новое положение на плоскости) «черепахи».

Далее с помощью нехитрого приведения типа получаются необходимые для функции drawLine аргументы (сигнатура этой функции, кто забыл <Pen, int, int, int, int>) — и происходит отрисовка, с почти одновременным обновлением внутреннего состояния исполнителя.

Но, это уже очевидные вещи, помимо которых есть некоторые весьма необычные штучки.

Во-первых, я решил реализовать расширенный спектр команд исполнителя и добавил команду «?», которая позволяет повернутся на некоторый случайный угол, выбранный из диапазона [-начальный угол; начальный угол]. Дабы пресечь некоторые ошибки, которые могут возникнуть на стадии получении псевдослучайных чисел, использована небольшая хитрость: берется модуль от начального угла, и затем для левого края диапазона изменяется знак, а для правого — остается неизменным. Подобная хитрость позволяет избавится от ошибки «перевернутого диапазона»: когда нижняя граница (из-за своей положительности) больше верхней границы (в силу ее отрицательного значения).

Во-вторых, особый интерес вызывают команды saveState() и RestoreState(), которые позволяют, соответственно, сохранить и загрузить некоторое состояние «черепахи». Для того, чтобы это работало, требуется структура, аналогичная по принципу работы, структуре типа стек. В нашем случае, роль стека состояний будет играть массив структур turtleState[] — и соответственно правилам D, мы для сохранения состояния помещаем в конец такого массива внутреннее состояние «черепахи», а вот для восстановления состояния приходится использовать небольшую хитрость…

Чтобы манипулировать последними элементами массива, требуется применить ряд функций, которые доступны из std.array: нужны функции, которые работают с так называемыми диапазонами (англ. Ranges, адекватный перевод никто еще не придумал), позволяющими писать более обобщенные и более понимаемые алгоритмы. Метод back() позволяет получать элементы диапазона, начиная с конца, а метод popBack() позволяет «выкидывать», удалять элементы, начиная с последнего — и получается, что состояние из стека достается методом back() и тут же присваивается переменной, хранящей состояние, а затем удаляется из массива turtleState методом popBack() без всякого возврата значения.

Остальное достаточно понятно и очевидно: метод draw принимает строку с командами и сопоставляет каждую однобуквенную команду со своим методом — и все это реализовано с помощью (да, да, довольно очевидного подхода) оператора switch … case, в котором в пункте default производится игнорирование любой другой однобуквенной команды, кроме уже описанных.

Весь код (под спойлером):

import dgui.all;
import std.math;

// внутренний мир черепахи :D
struct turtleState {
    float x, y, angle;
}

// черепаха
class Turtle
{
    private:
        turtleState[] stateStack;
        turtleState state;
        float step, delta;
        Canvas canvas;
        Pen pen;

    // конструктор черепахи
    public this(Canvas canvas, turtleState state, float step, float delta)
    {
       this.state = state;
       this.step = step;
       this.delta = delta;
       this.canvas = canvas;
       pen = new Pen(SystemColors.darkGreen, 1, PenStyle.solid);
    }

    // шаг вперед с отрисовкой следа
    private void drawStep()
    {
       float newX, newY;
       newX = state.x + cos(state.angle) * step;
       newY = state.y - sin(state.angle) * step;
       canvas.drawLine(pen, cast(int) state.x, cast(int) state.y, cast(int) newX, cast(int) newY);
       state = turtleState(newX, newY, state.angle);
    }

    // шаг вперед без отрисовки следа
    private void moveStep()
    {
       float newX, newY;
       newX = state.x + cos(state.angle) * step;
       newY = state.y - sin(state.angle) * step;
       state = turtleState(newX, newY, state.angle);
    }

    // поворот влево
    private void rotateLeft()
    {
       float newAngle;
       newAngle = state.angle + delta;
       state = turtleState(state.x, state.y, newAngle);
    }

    // поворот вправо
    private void rotateRight()
    {
       float newAngle;
       newAngle = state.angle - delta;
       state = turtleState(state.x, state.y, newAngle);
    }

    // поворот на случайный угол
    private void rotateRandom()
    {
       import std.random;
       float newAngle;
       auto gen = Random(unpredictableSeed);
       newAngle = uniform(-fabs(state.angle), fabs(state.angle), gen);
       state = turtleState(state.x, state.y, newAngle);
    }

    // сохранить состояние черепахи
    private void saveState()
    {
        stateStack ~= state;
    }

    // восстановить состояние черепахи
    private void restoreState()
    {
        // size_t l = stateStack.length - 1;
        // state = stateStack[l];
        // stateStack = stateStack[0 .. l - 1];
        import std.array;
        state = stateStack.back();
        stateStack.popBack();
    }

    // изобразить все мучения черепахи :D
    public void draw(string s)
    {
       for (int i = 0; i < s.length; i++)
       {
        switch(s[i])
        {
           case 'F':
              drawStep();
              break;
           case 'f':
              moveStep();
              break;
           case '+':
              rotateRight();
              break;
           case '-':
              rotateLeft();
              break;
           case '?':
              rotateRandom();
              break;
           case '[':
              saveState();
              break;
           case ']':
              restoreState();
              break;
           default:
              break;
        }
       }
    }

}


Использовать «черепаху» в своих целях очень просто:

/*
 задаем начальное состояние черепахи: координаты ее начального местоположения,
 а также угол, с которого она начнет старт: рекомендую использовать 90 градусный угол, 
 т.е значение PI / 2.0
*/
turtleState ts = turtleState(250.0, 500.0, PI / 2.0);
// Новый объект типа "черепаха"
Turtle turtle = new Turtle(c, ts, 2.75, 22.7 * (PI / 180.0));
// заставим "черепаху" отобразить что-нибудь
turtle.draw("F+fff+F+F+FF-fF?F");

А теперь немного о том, как это можно применить.

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

Определимся со следующимся терминами: аксиома — начальная строка на входе системы переписывания строк; правило переписывания — некая замена символов строки на другие символы, повторяемая в течении некоторого времени; поколение — некоторое число, определяющее, который раз применяется преобразование исходной строки.

Для начала работы с L-cистемами потребуется функция, которая бы проводила замену в строке и которая могла бы выглядеть примерно вот так:

// функция переписи строки
string rewrite(string s, string p, string ns)
{
  auto acc = "";
  auto search = 0;
  for (uint i = 0; i < s.length; i++)
  {
    import std.string : indexOf;
    auto ind = indexOf(s[search .. search + p.length], p);
    if (ind != -1)
    {
        search += p.length;
        acc ~= ns;
    }
    else
    {
        search++;
        acc ~= s[search-1];
    }
  }

  return acc;
}

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

После того, как мы написали функцию переписывания, нужно вспомнить тот факт, что редко в L-системах бывает одно правило переписывания, а это значит, что нужно придумать как хранить правила переписывания в удобном и понятном виде. К счастью, у меня есть неплохая идея: для хранения правил переписывания будем использовать ассоциативный массив типа string[string], ключом будут служить строки, которые будем заменять; а значениями будут строки, на которые заменяем. По-моему, такое описание процесса слабо понимаемо, а потому вот небольшой пример, заодно демонстрирующий инициализацию ассоциативного массива:

string[string] rewriteRules = [
           "X" : "F[F[+X][-XF]-F]XF",
           "F" : "FF"
        ];

Все просто: строка до двоеточия — это строка для замены, а строка после двоеточия — результат замены; вот в таком виде и будут записаны наши правила.

Обрабатывать L-систему достаточно просто: необходимо просто в цикле, отсчитывающем поколения, осуществить замену в строке аксиомы, согласно правилам переписывания. Это хорошо бы сработало, если бы правило переписывания было бы одно, а в случае нескольких таких правил, нужно пройтись циклом еще и по словарю: ключ словаря будет выступать в функции замены «старой» строкой (строкой, которую заменяем), а значение, хранимое под ключом, будет служить «новой строкой» (строкой, на которую заменяем), ну а самый первый аргумент — это не что иное, как строка-накопитель результатов переписывания, первоначальным значением которой станет аксиома.

Как результат, получаем следующую функцию:

// генерация L-системы
string lSystemGenerate(string axiom, string[string] rewriteRules, uint generationNumber)
{
    auto lSystemString = axiom;
    for (uint i = 1; i < generationNumber; i++)
    {
        foreach (rule; rewriteRules.keys)
        {
            lSystemString = rewrite(lSystemString.idup, rule, rewriteRules[rule]);
        }
    }
    return lSystemString;
}

Логичнее всего, испытать это на достаточно простой L-системе, для чего нужно создать пустой проект DGui и положить в папку source проекта файл turtle.d, содержащий код с классом «черепахи», после чего простой командой import этот модуль вставляется в «пустой» проект, в котором уже оформлен основной код, использующий «черепашью графику».

В качестве примера, мой тестовый код:

import dgui.all;
import std.math;
import turtle;

// генерация L-системы
string lSystemGenerate(string axiom, string[string] rewriteRules, uint generationNumber)
{
    auto lSystemString = axiom;
    for (uint i = 1; i < generationNumber; i++)
    {
        foreach (rule; rewriteRules.keys)
        {
            lSystemString = rewrite(lSystemString.idup, rule, rewriteRules[rule]);
        }
    }
    return lSystemString;
}

// функция переписи строки
string rewrite(string s, string p, string ns)
{
  auto acc = "";
  auto search = 0;
  for (uint i = 0; i < s.length; i++)
  {
    import std.string : indexOf;
    auto ind = indexOf(s[search .. search + p.length], p);
    if (ind != -1)
    {
        search += p.length;
        acc ~= ns;
    }
    else
    {
        search++;
        acc ~= s[search-1];
    }
  }

  return acc;
}

class MainForm : Form
{
    public this()
    {
        this.text = "";
        this.size = Size(500, 550);
        this.startPosition = FormStartPosition.centerScreen;
    };

    protected override void onPaint(PaintEventArgs e)
    {

        Canvas c = e.canvas;

        // черепаха - вперед !
        turtleState ts = turtleState(250.0, 500.0, PI / 2.0);
        Turtle turtle = new Turtle(c, ts, 2.75, 22.7 * (PI / 180.0));

        // задание L-системы
        string axiom = "X";
        string[string] rewriteRules = [
           "X" : "F[F[+X][-XF]-F]XF",
           "F" : "FF"
        ];
        auto ls = lSystemGenerate(axiom, rewriteRules, 7);

        // отрисовка
        turtle.draw(ls);

        super.onPaint(e);
    }
};

int main(string[] args)
{
    return Application.run(new MainForm());
}

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

Снимокэкранаот2015-01-2120 40 02_0_o

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

Скриншот работы двух черепах (тест переработанного модуля):

Снимокэкранаот2015-01-2120 40 39_0_o

Первое дерево (светло-зеленое) получено с помощью такого правила переписывания, которое я придумал сам:

string[string] rewriteRules = [
           "X" : "F[[+XR[+XR]][-XFr[+XR?]]]",
           "F" : "FRF"
        ];

А параметры состояния черепахи такие:

Pen pen = new Pen(Color(0u, 255u, 120u), 3, PenStyle.solid);
turtleState ts = turtleState(250.0, 500.0, PI / 2.0, c, pen);

На этом у меня все.

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