Как-то в блоге уже упоминались 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());
}
После компиляции и запуска получается весьма интересный результат, представленный на картинке ниже.
Завершая эту статью, хочу сказать то, что я немного усовершенствовал код класса "черепахи": добавил несколько новых команд для исполнителя, а также ввел некоторые функции, позволяющие манипулировать состоянием "черепахи" и для использования в целях моделирования были вставлены члены класса, с помощью которых, можно клонировать сам исполнитель или перенести состояние одного из исполнителей на другого. Все эти возможности стали доступны из-за некоторых переработок класса и структуры, ответственной за хранение внутреннего состояния "черепахи": структура теперь имеет больше полей, а конструктор класса был упрощен - более подробно все описано в самом модуле turtle, который доступен здесь.
Скриншот работы двух черепах (тест переработанного модуля):
Первое дерево (светло-зеленое) получено с помощью такого правила переписывания, которое я придумал сам:
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);
На этом у меня все.
