Кривой дракона (Dragon Curve) называется любая кривая, которая фрактально повторяет сама себя, и которую можно аппроксимировать рекурсивными способами (не знаю, что значат все эти слова, давайте побыстрее к делу :))
На картинке вы быстро опознаете фрактал. Но его чёрное тело не закрашено целиком, а состоит из плотно прилегающих друг к другу отрезков линии, и всё это изображение – одна непрерывная ломаная линия. Если посмотреть на неё вблизи, то можно увидеть такую картину:
Мы будем рассматривать конкретную разновидность (как на картинке): Дракон Хартера-Хейтуэя. Как видно, у линии есть начало и конец. Чтобы её нарисовать, нужно чертить отрезки, каждый раз меняя направление влево или вправо. Вопрос, как именно менять? Если вы попробуете найти здесь какую-то систему, например: R,R,R,L,R,R,L,L..., то быстро поймёте, что системы вроде бы никакой нет, а если она есть, то очень сложна.
Однако у данной драконьей кривой есть одно великолепное, замечательное свойство.
Это всего лишь сложенная пополам бумага!
Сложив лист бумаги пополам, мы получим две сложенные половинки. Сложив эти половинки ещё раз пополам, мы получим 4 сложенные половинки, и т.д. Каждая половинка сгибается вместе с другими в одну и ту же сторону, но давайте посмотрим, что будет, если этот сложенный лист потом разогнуть обратно и все сгибы выровнять под углом 90°:
Если вам что-то кажется непонятным, возьмите полоску бумаги в руки и проделайте это физически.
Как видим, каждая следующая итерация сгибов удваивает предыдущую. И... вот нам готовая система! Есть два подхода к реализации:
1. Рекурсия
Вообще говоря, тут всегда рекурсия, но эту я бы назвал "истинной". В каждом сгибе каждая половинка рекурсивно сгибается ещё раз, превращаясь в две половинки, которые опять сгибаются и т.д. Вопрос тут лишь в правильном направлении сгиба каждой половинки.
2. Разворот
Этот способ пришёл мне в голову первым и поэтому я решил реализовать именно его. И он, можно сказать, не рекурсивный: имея одну половинку, мы просто копируем её и разворачиваем вокруг точки сгиба на 90°, получая две половинки. Затем, имея обе эти половинки, разворачиваем их обе опять на 90° вокруг точки сгиба, получая 4 половинки. То есть мы разгибаем сложенный листок, а затем то, что получилось, считаем снова сложенным листком и опять разгибаем. Рекурсивных вызовов здесь нет. Просто нужно повторить процедуру столько раз, сколько раз мы хотим "разогнуть" листок. Но каждый вызов будет удваивать данные.
Итак, пишу реализацию на JavaScript.
Я почитал немного про разные реализации, но не на 100% их понимаю, а мне нужна полная наглядность. Поэтому буду действовать в лоб. Возможно, потом наступит просветление, и можно будет всё оптимизировать и главное – объяснить.
Мне нужна структура для хранения каждой половинки. Так как линия движется непрерывно от точки старта, и каждый следующий отрезок стартует от конца предыдущего, мне нужно хранить не координаты, а только направление по оси X и по оси Y. Ну то есть, если отрезок чертится влево, то направление будет (-1, 0), если вправо, то (1, 0), вверх – (0, -1), вниз – (0, 1). (Координатная ось Y экрана идёт сверху вниз.)
Я не буду ничего изобретать и буду просто хранить пару чисел в виде массива:
[-1, 0]
А этот массив я помещу в другой массив, который будет содержать все отрезки ломаной:
var dragon = [[-1, 0]];
То есть сейчас дракон состоит из одного отрезка, прочерченного влево (куда чертить – всё равно). И самое удивительное – больше ничего не надо! Он развернёт сам себя в кривую дракона, во всю эту великолепную сложность!
Чтобы сделать разворот, я применяю такой алгоритм:
Последняя нарисованная точка является точкой разворота всех предыдущих отрезков. Вокруг неё надо повернуть все отрезки, которые есть в массиве, на -90° (так мне получилось удобнее, пока рисовал схемы). Так как после рисования я нахожусь в конце массива, то буду просто двигаться назад к его началу, перебирая всё, что в нём есть. И вот я достал из него отрезок (-1,0), который только что нарисовал. Так как я смотрю из своей точки поворота на отрезок "задом наперёд", конец отрезка теперь является его началом. То есть относительно точки поворота этот отрезок уже не (-1,0), а (1,0). Короче говоря, перед поворотом координатам надо просто поменять знак.
Собственно поворот на -90° банален:
new_x = y
new_y = -x
Из (-1,0), сначала поменяв знаки: (1,0), я через поворот получил (0,-1). Это второй отрезок, который я добавляю в массив как новый элемент.
На этом первая итерация закончена, и теперь массив содержит два элемента. На второй итерации я разверну эти два элемента и получу +2 элемента, затем 4 разверну в +4 и т.д. пока не надоест. Ну а надоедает это довольно быстро, потому что число отрезков растёт экспоненциально и очень скоро компьютеру становится плохо :)
Я остановился на 17 итерациях:
Вы можете посмотреть на код и результат онлайн.
Можно попробовать 20 итераций, но больше не советую. Как можно видеть, я добавил в хранимые отрезки цвет, который меняется на каждой следующей итерации.
3. Самомодифицирующийся словарь (машина состояний?)
Это ещё один способ генерации кривой дракона, и он также не вполне (внешне) рекурсивен. Смысл в том, что каждый отрезок кодируется специальными символами (состояниями), из которых получается обыкновенная строка. Затем мы ищем в строке эти символы и заменяем их на другие символы (состояния), которые опять-таки содержат какие-то символы. Мы опять ищем символы и опять их заменяем, и т.д. То есть начальный символ может генерировать бесконечно много новых символов, что в нашем случае описывает схему сложения пополам уже сложенных половинок.
Этот метод генерации фрактальных кривых называется системой Линдермейера или L-системой. Подробности вы можете прочитать по ссылке, там на деле всё безумно интересно, а я сделал ещё одну реализацию кривой дракона.
Данная реализация работает заметно медленнее из-за строковых операций. Здесь используются следующие символы:
F: вперёд, +: поворот направо, -: поворот налево, X и Y - специальные символы для замены:
X → X+YF+
Y → -FX-Y
Первичной строкой является 'FX'. Как видим, при замене X и Y появляется в 2 раза больше символов X и Y, которые также подлежат замене, и т.д.
Теперь, почему именно такая замена? Очевидно, для создания правильных направлений поворота. Это как-то уже высчитано. Я примерно понимаю, как это работает, но увы, пока не проверил досконально и потому не способен объяснить (если кто из комментаторов поможет, буду рад). Поэтому я просто воспользовался готовыми строками для замены и получил правильный результат.
При чём тут драконы?
Вероятно, эти кривые похожи на традиционных китайских драконов: