Кратко о L-системах
Всем привет.
Долго откладывал написание этой статьи, но наконец нашёл в себе силы и дописал её!
Сегодня хотел бы показать интересную вещь как L-система или система Линденмайера.
Краткая справка из вики, для общего развития:
L-система или система Линденмайера — это параллельная система переписывания и вид формальной грамматики. L-система состоит из алфавита символов, которые могут быть использованы для создания строк, набора порождающих правил, которые задают правила подстановки вместо каждого символа, начальной строки («аксиомы»), с которой начинается построение, и механизма перевода образованной строки в геометрические структуры.
Чтобы заинтересовать давайте сразу глянем на результат того, что в итоге получиться:
Задача
Есть некоторая аксиома и N порождающих правил. Применяя каждое из правил к аксиоме мы получаем следующую итерацию значения системы. Для лучшего объяснения лучше почитайте вики или книжку.
Нам надо же произвести итерацию алгоритма и отрисовать текущее состояние системы, а потом повторить ещё N число раз.
Давайте рассмотрим на примере как происходит генерация для следующей системы:
переменные: A B
аксиома: A
правила:
A -> AB
B -> A
- A
- AB
- ABA
- ABAAB
На нулевом шаге у нас по сути ничего нет и мы просто подставляем значение аксиомы.
На первом шаге преобразуем A в AB по правилу A.
На втором шаге А преобразуется в AB, а B преобразуется в A.
И на третьем шаге первая и последняя A в AB, а В, та что в середине в A. И в результате получаем ABAAB.
Надеюсь на данном этапе уже понятен смысл преобразований.
Остаётся только назначить каждому правилу некоторую команду. Допустим A -> x + 1, а B -> y + 1.
Обновим систему правил:
переменные: A B
аксиома: A
правила:
A -> AB
B -> A
перемещение:
A -> x + 1
B -> y + 1
Исполнив полученный результат по определенным командам мы получаем интересное поведение системы.
Для ABAAB, если принять начальное положение (x, y) за (0, 0) получаем: (3, 2).
- A: (1, 0)
- B: (1, 1)
- A: (2, 1)
- A: (3, 1)
- B: (3, 2)
Вообще дополнительные правила можно придумать любые, но у нас будет в основном перемещение с отрисовкой.
Реализация
Сразу представлю вспомогательный код с краткими комментариями, а потом перейдём к основному коду.
from copy import deepcopy
from pathlib import Path
import subprocess as sp
import argparse
import json
import math
from PIL import Image, ImageDraw
# рендер через ffmpeg
# смотри статью: https://freecx.github.io/blog/2020/07/23/2.5d-effect
class ffmpeg:
def __init__(self, fps, output):
# команды ffmpeg
self.cmd_out = [
'ffmpeg', '-i', '-', '-f', 'image2pipe', '-r', str(fps), '-c:v', 'libx264', '-preset', 'slow',
'-profile:v', 'high', '-crf', '18', '-coder', '1', '-pix_fmt', 'yuv420p', '-vf', 'scale=iw:-2',
'-movflags', '+faststart', '-g', '30', '-bf', '2', '-y', str(output),
]
self.pipe = sp.Popen(self.cmd_out, stdin=sp.PIPE)
def push(self, frame):
# будем передавать PNGхи через pipe
frame.save(self.pipe.stdin, 'PNG')
def __del__(self):
# корректно завершаем работу
self.pipe.stdin.close()
self.pipe.wait()
if self.pipe.returncode != 0:
raise sp.CalledProcessError(self.pipe.returncode, self.cmd_out)
#
# здесь будет код генерирующий кадры L-системы
#
# функция выполняющая модель из файла
def execute_model(filename, *, savename=None):
with open(filename, 'r') as jsf:
# тут наша модель
data = json.load(jsf)
# генерируем финальный результат L-системы (прогон всех итераций)
result = generate(data['axiom'], data['iterations'], data['generate_rules'])
# определяем размер выходного видел делая пререндер модели
state = prerender(result, data['start_angle'], data['draw_rules'])
# рендерим видео каждого шага алгоритма
render(savename, state, result, data['start_angle'], data['draw_rules'])
if __name__ == '__main__':
# парсинг аргументов командой строки
parser = argparse.ArgumentParser(description='Draw L System model')
parser.add_argument('-m', metavar='model', type=str, default=None, help='input model file')
args = parser.parse_args()
if args.m:
# имя файла выходного видео по имени используемой модели
renamer = lambda model: str(model).rsplit('.', 1)[0] + '.mp4'
model = Path(args.m)
# если в -m передали папку, то обрабатываем каждый из файлов
if model.is_dir():
for file in model.iterdir():
print(f'> processing {file}')
# выполняем и рендерим модель
execute_model(file, savename=renamer(file))
else:
print(f'> processing {model}')
execute_model(model, savename=renamer(model))
else:
parser.print_help()
Теперь перейдём к функциям рендеринга изображений
# пререндер для определения размера холста
def prerender(cmds, angle, rules, border=10):
# инициализируем границы холста нулями
xmin, xmax, ymin, ymax, x, y = [0] * 6
# итерируемся по командам
for symbol in cmds:
# выполняем текущее правило и получаем текущее положение курсора
x, y, angle = execute(x, y, angle, symbol, rules)
# обновляем границы холста
xmin, xmax = min(x, xmin), max(x, xmax)
ymin, ymax = min(y, ymin), max(y, ymax)
# выводим размер картинки
width = abs(xmin) + abs(xmax)
height = abs(ymin) + abs(ymax)
# с окрушлением до чётных (нужно для mp4)
if width % 2 != 0:
width += 1
if height % 2 != 0:
height += 1
# сдвиги по осям
shift_x = abs(xmin)
shift_y = abs(ymin)
# и возвращаем результирующие размеры холста с границами
return (width + 2 * border, height + 2 * border, shift_x + border, shift_y + border)
# функция отрисовки
def render(output, state, cmds, angle, rules):
# положения курсора
px, py, lx, ly = [0] * 4
# размеры холста + сдвиги
w, h, sx, sy = state
# создаём наш холст
img = Image.new('RGB', (w, h), 'white')
# и получаем объект на котором можно рисовать
drw = ImageDraw.Draw(img)
# инициализируем pipe с ffmpeg
render = ffmpeg(fps=24, output=output)
# итерируемся по командам
for symbol in cmds:
# выполняем текущее правило и получаем текущее положение курсора
px, py, angle = execute(px, py, angle, symbol, rules)
# рисуем линию от прошлошо положения к текужему
drw.line((lx + sx, ly + sy, px + sx, py + sy), fill=(0, 0, 0))
# обновляем прошлое положение не текущее
lx, ly = px, py
# и отдаём кадр ffmpeg
render.push(img)
А теперь перейдём к самым интересным функциям:
def generate(init, iterations, rules):
"""основная функция генерирующая новое состояние системы
init - стартовая аксиома
itereations - количество итераций
rules - список правил
"""
for _ in range(iterations):
# создаём пустой список
res = []
# и заполняем его
for var in init:
# выполняем текущее правило и кладём в список
res.append(rules[var] if rules.get(var) else var)
# подменяем стартовую аксиому
init = ''.join(res)
return init
def execute(x, y, angle, symbol, rules):
"""функция исполняющая правила отрисовки
x, y - положение курсора
angle - угол
symbol - текущая команда
rules - все правила системы
"""
# существует ли символ в системе?
if rules.get(symbol):
# парсим наши команды
if ':' in rules[symbol]:
# на тип команды и значение
cmd, var = rules[symbol].split(':')
cmd, var = cmd.lower(), float(var) if var.isdigit() else None
else:
cmd = rules.get(symbol)
var = None
# команда продвижения вперёд
if cmd == 'forward':
x += round(var * math.cos(math.radians(angle)))
y += round(var * math.sin(math.radians(angle)))
# команда поворота налево
elif cmd == 'left':
angle = (angle + var) % 360
# команда поворота направо
elif cmd == 'right':
angle = (angle - var) % 360
# возвращаем новое состояние
return x, y, angle
Вот и всё, всё готово!
Рендер
В начале статьи был представлен рендер Треугольника Серпинского, который можно записать в нотации L-системы следующим образом:
переменные: F G
аксиома: F-G-G
правила:
F -> F-G+F+G-F
G -> GG
перемещение:
F -> пройти вперёд на 20
G -> пройти вперёд на 20
+ -> поворот налево на 120 градусов
- -> поворот направо на 120 градусов
Или сериализованный в json, для нашей программы:
{
"axiom": "F-G-G",
"generate_rules": {
"F": "F-G+F+G-F",
"G": "GG"
},
"draw_rules": {
"F": "forward:20",
"G": "forward:20",
"+": "left:120",
"-": "right:120"
},
"iterations": 5,
"start_angle": 0
}
Сохранив файл и скормив его программе получаем тот же результат, что и в начале статьи.
Заключение
Хотел бы выразить особую признательность и поблагодарить мою лень за то что успела выйти статья на хабре, прежде чем я продолжил дописывать эту статью!
Исходники, и некоторые виды описанных систем, как всегда можно забрать по ссылочке. Модели запихнул в один файл, где ключ - имя файла, а значение - содержимое модели.
А на этом пока всё, всем пока!
Что почитать
- Кроновер Р., Фракталы и хаос в динамических системах. Основы теории, 2000
- L-systems
- Фракталы на Python. Пошаговое руководство