Игра Хаоса: случайность против детерменизма

Фракталы — одни из самых интересных, поражающих воображение математических объектов. Фракталы обладают свойством самоподобия, иными словами, они в точности или приближённо совпадает с частью самого себя. Может показаться, что случайность и фракталы попросту не могут иметь ничего общего, ведь фракталы — одни из самых детерменистичных объектов, которые только можно себе представить. В этой статье мы познакомимся со способам создавать фрактальные узоры, используя случайность и хаос.

Игра Хаоса и её правила#

Игра Хаоса — это метод создания итеративных фракталов с помощью многоугольников.

Приведём правила игры на простейшем случае — треугольнике:

1. Пронумируем вершины треугольника;
2. Отметим произвольную точку внутри треугольника;
3. Случайным образом выберем одну из вершин треугольника;
4. Перемещаемся в середину отрезка, соединяющего произвольную точку и случайно выбранную вершину треугольника и отмечаем её;
5. Повторяем пункты (3-4) множество раз.

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

Перед нами предстаёт удивительная картина: некоторые области треугольника так и останутся незакрашенными, несмотря на количество итераций. Результатом окажется фрактал, известный как «Треугольник Серпинского», впервые описанного польским математиком Вацлавом Серпинским в 1915 году:

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

Немного красок#

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

Обобщение сторон и скучный случай#

Попытаемся обобщить правила игры. Самым очевидным и наиболее простым способом сделать это можно с помощью количества сторон многоугольника. Рассмотрим следующий наиболее простой случай — квадрат:

К сожалению, в случае с четырёхугольником «Игра Хаоса» не даёт интересного результата, точки равномерно заполняют область многоугольника, чего на самом деле и ожидалось при непосредственном знакомстве с правилами игры. На самом деле, четырёхугольник — единственный «непримечательный» случай, и тому есть объяснение.

Предположим, что внутри произвольного многоугольника имеется множество случайных точек. Пусть волей немыслимых обстоятельств и удачи каждая по правилам игры сдвинется (важно, что именно сдвинется — для иллюстративности объяснения) в сторону одной и той же вершины. Результатом окажется новая закрашенная область, подобная по форме исходному многоугольнику с машстабом 1:2. Повторив подобный сдвиг для каждой из вершин, и соединяя всё воедино, получаем карту плотности точек — иллюстративное отображение возможного расположения множества случайных точек.

Если внутри карты плотности имеются пустоты, то предположение о равномерном распределении точек — ложь, далее необходимо повторить процедуру снова и снова, получая в итоге фрактал:

В первую очередь можно выделить треугольник и квадрат: результат кардинально отличается от остальных многоугольников. Это можно объяснить отсутствием какого-либо пересечения плотностей, связанных с вершинами.

Так как квадрат можно покрыть четырьмя подобными копиями себя (k = 0.5), то пустот не возникает. Можно возразить, что треугольник тоже, но тут именно важно количество сторон. Именно по этой причине и наблюдается равномерное распределение точек. Другим подтверждением этого факта является несмешиваемость цветов, наблюдаемую у квадрата (и треугольника). В остальных случаях, как можно заметить по пересечению плотностей и имеющимся пустотам, можно предсказать визуальную структуру будущего фрактала.

Неслучайная случайность#

До сих пор фракталы выглядели довольно привычно, если так можно выразиться. Самое интересное начинается, когда мы решим “вмешаться” в процесс “случайности” выбора. Вершины многоугольника всё также будут избираться случайным образом, но с некоторым вмешательством - включением некого свода правил. Рассмотрим это на примере “скучного” четырёхугольника:

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

• Соседи случайной вершины не могут быть выбраны в следующий раз;
• Если та же самая вершина была выбрана два раза подряд, то следующая должна быть хотя бы в двух шагах от неё.

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

К примеру, правило «вершина не может быть выбрана два раза подряд» для четырёхугольника может быть сформулировано множеством 3: в множестве перечислены расстояния до следующих возможных вершин. Или же для краткости! 4 — как запрещённое расстояние до следующей вершины; а так как вершин всего четыре, то получается как раз та же самая.

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

Для подсчёта возможных комбинаций необходимо посчитать количество подмножеств множества, содержащего все возможные вершины. Треугольник Серпинского получается множеством 3 — таким образом может быть выбрана любая вершина. Количество всех возможных комбинаций (включая пустое множество — его рассматривать не стоит, нужно хоть куда-то двигаться) находится как удвоенный квадрат количества элементов этого множества.

Например:

• Для треугольника: 7,
• Для четырёхугольника: 15,
• Для пятиугольника: 31.

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

На самом деле, этим дело не ограничивается. Наиболее изощренные и интересные формулировки возможно описать лишь множеством ограничений. Это и логично, ведь мы упускаем из виду ещё один параметр — относительно какой уже выбранной вершины мы создаём ограничения. Например, вот что получится при запрете выбора следующей вершины на расстоянии 1 от предыдущей и 3 от предпредыдущей:

С учётом предпредыдущей выбранной вершины для формулировки ограничений (не стоит останавливаться, можно уходить в прошлое ещё «глубже»), количество новых фракталов становится ещё больше: если при ограничении одной вершины количество возможностей 2^n — 1, то после учёта предпредыдущей — все (2^n — 1) * n для каждой их возможных вершин. Если для треугольника это теперь существует 343 комбинации (было всего лишь 7), то для восьмиугольника целых 17 878 103 347 812 890 625!

Изменяя шаг#

До сих пор во время «игры» мы перемещали точку на полпути к случайно выбранной вершине. Почему бы не изменить это, введя новый параметр — фактор шага «r». Используя величину шага как коэффициент, получаем что при r = 0 движения не происходит, при r = 1 точка перемещается непосредственно к самой вершине, а r = 0.5 — та самая величина, которой мы пользовались до сих пор. Конечно, можно использовать величину и за пределами единицы, выходя за внутреннюю область многоугольника.

Попробуем поэкспериментировать, как же влияет фактор шага на результат:

Изменяя коэффициент, можно увидеть, как масштабируется привычный рисунок. Самое важное, чему стоит уделить внимание — при определённой величине шага при отдалении «плотностей точек» друг от друга, можно получить непересекающиеся области. Величина коэффициент при этом будет зависеть от количества сторон многоугольника. В общем случае r = 3 / (n + 3), где n — количество сторон многоугольника. С таким коэффициентом даже обделённый квадрат перестаёт быть скучным и демонстрирует интересный паттерн.

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

Подводя итоги#

Нет сомнений, несмотря на простоту правил игры, всё ещё остаётся «океан» возможностей: можно рассмотреть вместо правильных многоугольников аффинные преобразования, дополнительного движения или даже изменять параметры окраски и яркости на основе случайности выбора. Может показаться, что «Игра Хаоса» — всего лишь забавное математическое развлечение, не более. Однако, игра представляет собой частный случай ещё более интересного математического объекта — аттрактора, но об этом — как-нибудь в другой раз.

При желании, можете попробовать сыграть в «Игру Хаоса» с возможностью поэкспериментировать со всеми описанными в этой статье параметрами.

Ссылки#

• Треугольник Серпинского
• The Chaos Game: Sierpinski triangles and beyond, part 1
• Numberphile: Chaos Game
• The Chaos Game