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

Вступление

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

Модель

Для начала я решил выбрать достаточно простую модель. В моей модели существует только два типа объектов: шарики (marbles) и платформы либо доски (planks). Платформы имеют строго фиксированные координаты, задаются двумя точками концов и имеют константную ширину. Шарики же падают под воздействием гравитации и могут отбиваться по законам физики от платформ. Также, я решил использовать только абсолютно упругие столкновения, чтобы энергия системы всегда оставалась неизменной. Но самое главное — при столкновении шарика и платформы проигрывается звук, у каждой платформы он свой и может состоять из нескольких нот сразу.

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

Алгоритм

С моделью разобрались, но как сгенерировать такой мир, чтобы звуки отбиваний шариков выстроились в известную мелодию?

Я решил использовать максимально топорный, тем не менее, показавший себя достаточно хорошо, рекурсивный перебор, а в простонародье bruteforce. Но, чтобы все работало как надо, пришлось использовать несколько хитростей. Все последующие шаги выполняются внутри рекурсивной функции:

1. Симулируем мир, до следующего момента когда нужно сыграть ноту.
2. Если в процессе симуляции произошло нежелательное столкновение, возвращаемся на уровень выше.
3. За один тик, до того как надо сыграть ноту, пытаемся добавить на карту новую платформу, вплотную к шарику. При этом длину платформы я зафиксировал, а угол я выбираю из конечного списка поворотов платформы относительно направления скорости шарика. При этом углы эти лежат в диапазоне приблизительно от $\$inline\$-70^\backslash circ\$inline\$$ до $\$inline\$+70^\backslash circ\$inline\$$. Таким образом шарик всегда «налетает» на поставленную платформу под достаточно острым углом (если угол падения будет близким к прямому, то визуально не будет ощущения, что шарик оттолкнулся).
4. 4. Рекурсивно вызвать функцию для нового мира и следующей ноты.
5. 5. Если ни один из вариантов расположения платформы не дал результат, возвращаемся на уровень выше
6. 6. Если в списке нот мы дошли до конца, проверяем, чтоб следующие $\$inline\$m\$inline\$$ тиков не происходило столкновений, и если это так, возвращаем полученный мир как результат.

На картинке вы можете видеть визуализацию одного шага данного алгоритма:




Застревание рекурсии

Как и любой bruteforce алгоритм, этот имеет недостаток в виде «застревания рекурсии», это происходит когда какая-то «плохая» платформа не позволяет в дальнейшем сгенерировать карту полностью, но при этом позволяет генерировать достаточно большую ее часть, но не до конца. В таком случае рекурсия застрянет до тех пока не переберёт все варианты в поддереве рекурсии которое порождает эта «плохая» платформа. Нет никаких проблем, когда высота этого поддерева не превышает 4-8 уровней рекурсии, но иногда она может достигать и 20-30 уровней, что делает перебор всех вариантов этого поддерева просто невозможным.

Поэтому в своей реализации я принял решение использовать эвристику для преодоления застревания. Идея заключается в схлопывании некоторой части рекурсии при выявлении таких случав. Самым очевидным для меня показалось возвращаться на $\$inline\$d\$inline\$$ уровней рекурсии выше, если на протяжении $\$inline\$k\$inline\$$ итераций мы не смогли улучшить максимальную длину сгенерированного пути по платформам. В моем случае я выбираю $\$inline\$k\$inline\$$ как 10% от количества нот, а $\$inline\$d\$inline\$$ как 2000.

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

Итеративная генерация

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



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

Загрузка мелодии

Для загрузки мелодии я использую midi файлы, но перед этим прогнав через tonejs.github.io/Midi, чтобы превратить его в понятный для браузера json (но в данный момент в демке нет функционала загрузки своего файла, доступен только выбор из готового списка).

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

Результаты

Добавив немного эффектов я записал первое видео:


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


На видео может быть заметен раcсинхрон, я заметил это позже. Если вы зайдете на страничку с демо, расcинхрона наблюдаться не должно (звук в действительности проигрывается только при регистрации удара).

В результате я на память знаю все эти мелодии, а мои уши узнают любую мелодию по первым двум нотам

Что дальше?

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

Еще одной моей идеей было добавление новых объектов: кнопок, трамплинов, пушек (?), колец… список можно дополнять :) Они могут значительно разнообразить мир.

Код

Весь исходный код вы сможете найти в моем репозитории

Приветствуются любые предложения, пул реквесты, ишью!