27.09.2024 07:32
PatientZero 4 1300 Источник

В последнее время я экспериментирую с визуализаторами музыки. Источником вдохновения для одного из моих любимых стала классическая игра Pong. В классическом Pong мяч отбивается от ракеток в постоянном ритме. Что если мы синхронизируем удары с долями музыкальных композиций, заставив ракетки танцевать?

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

Также мы сохраним следующие правила классической игры:

  • Точка контакта мяча с ракеткой определяет угол отражения
  • У ракеток нет ограничений по скорости
  • Мяч отскакивает от верха и низа экрана

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

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

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

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

Оптимизация с заданными ограничениями


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

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

Звучит отлично, но моделировать 2D-ограничения сложно; действительно ли наша игра двухмерна? Оказывается, достаточно моделировать лишь горизонтальный компонент! В нашем наборе правил мяч движется с постоянной скоростью, поэтому вертикальный компонент скорости чётко определён горизонтальным. Благодаря симуляции игры мы сможем вычислять вертикальную позицию мяча в любой момент времени.

Знание вертикальной позиции мяча также даёт нам вертикальную позицию ракеток, потому что она должна совпадать с позицией мяча (плюс небольшая дельта для получения нужного угла). Между ударами мы просто линейно интерполируем позиции, чтобы получить плавное движение. Таким образом, солвер нужен нам только для вычисления горизонтальных позиций и скоростей в моменты удара мяча об ракетки; остальное можно получить из физики игры.


Диаграмма полёта мяча i

Константы


Давайте начнём с того, что определим жёстко заданные параметры игры:

$\begin{align} &\text{} W \in \mathbb{R}^+ \text{ - ширина экрана} \\ &\text{} S \in \mathbb{R}^+ \text{ - скорость мяча} \end{align}$


Входные данные таймингов


Далее нам нужно синхронизировать время доль. Каждое t — это время, когда мяч должен удариться об ракетку. Мы получаем это время из файлов MIDI, хотя в будущем я бы хотел исследовать более автоматизированные способы их извлечения из аудио.

$\text{} T = {t_0, t_1, \ldots, t_{n}} \text{ - время каждой доли}$


Мы берём разности между соседними моментами, чтобы получить длительность перемещения мяча между ударами. Каждое d — это временной интервал между двумя ударами мяча.

$\begin{align*} \text{} D &= {d_0, d_1, \ldots, d_{n-1}} \text{ - длительность каждого перемещения}\\ d_i &= t_{i+1} - t_{i} \quad \text{для } i = 0,1, 2, \ldots, n-1 \\ \end{align*}$


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

Переменные


Стоит помнить, что нам нужно оптимизировать лишь горизонтальные позиции и скорости.

$\text{} P = {p_0, p_1, \ldots, p_{n-1}} \text{ - горизонтальное расстояние от ракетки до центра}$


Каждое $p_i$ обозначает расстояние по горизонтали от ракетки до центра, где она ударяет по мячу в i-тый раз. Чётные индексы ($p_0$, $p_2$, …) относятся к левой ракетке, а нечётные ($p_1$, $p_3$, …) — к нечётной.

$\text{} V = {v_0, v_1, \ldots, v_{n-1}} \text{ - горизонтальная скорость мяча}$


Множество скоростей мяча по горизонтали. Каждое $v_i$ обозначает скорость мяча по горизонтали после i-того удара. Чтобы упростить создание ограничений, мы делаем её всегда положительной, вне зависимости от того, движется ли мяч вправо или влево.

Ограничения


Сначала мы ограничиваем ракетки их половиной экрана:

$0 \leq p_i \leq \frac{W}{2}$


Мы определили $p$ как расстояние от центра, так что оно неотрицательно вне зависимости от того, на какой половине экрана находится ракетка.

Далее мы ограничим величину скорости мяча по горизонтали положительными значениями, не превышающими его общей скорости S.

$0 < v_i \leq S$


Эти два ограничения полностью определяют физику нашей игры. Для синхронизации с темпом музыки мы добавляем ещё одно ограничение:

$p_{i-1} + p_i = d_i v_i$


Это гарантирует, что мяч достигнет следующей ракетки в нужный момент. Левая часть уравнения описывает общее расстояние перемещения по горизонтали (сумму расстояний до центра для двух последовательных ударов об ракетки), которое должно быть равно произведению длительности полёта и скорости мяча по горизонтали.

Цель


Мы знаем, что существует вырожденное решение, при котором ракетки не удаляются от центра. Нужно будет мотивировать их к противоположному поведению; максимизировать расстояние до центра.

Тогда наша цель заключается в максимизации суммы расстояний от ракетки до центра.

$\text{Максимизировать} \sum_{i=1}^n p_i$


Решение задачи


После составления математической формулировки нам остаётся лишь решить её. Все наши ограничения линейны, поэтому достаточно будет любого солвера линейного программирования (linear programming, LP). Я выбрал CVXPY за его простоту и обобщённость. CVXPY решает задачи выпуклой оптимизации, а задачи LP относятся к её подмножеству. Хотя нам не потребуется полный набор возможностей солвера, его гибкость в поддержке более сложных целей и ограничений упростит процесс творческого исследования.

В CVXPY мы можем выразить перечисленные выше ограничения следующим образом:


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

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

Для анимирования готового результата мы используем позиции мяча и ракеток на момент каждого удара в качестве ключевых кадров. Между ударами мы интерполируем позиции для создания плавной анимации.

Заключение


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

Код выложен в опенсорс: репозиторий Github

Благодарности


Благодарю Пэта О’Нила за вычитку черновиков поста.

Примеры





Комментарии (4)


  1. TomskDiver
    27.09.2024 07:50
    #27347168

    Круто! Прикольная идея.


  1. jbourne
    27.09.2024 07:50
    #27347708

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


  1. DevFx
    27.09.2024 07:50
    #27347800

    Классно. Подскажите, а как можно сгенерировать json с таймингами для .mp3, чтобы передать его в скрипт?


  1. SuperFly
    27.09.2024 07:50
    #27349622

    хах, а я когда-то видел такой клип: https://www.youtube.com/watch?v=cNAdtkSjSps