Pong per Constraint-Optimierung mit Musikbeats synchronisieren

 (victortao.substack.com)
1 Punkte von GN⁺ 2024-09-04 | 1 Kommentare | Auf WhatsApp teilen
  • Eine Musikvisualisierung im Pong-Stil behandelt die Spielphysik und die Paddle-Positionen als Optimierungsvariablen, um den Moment, in dem der Ball ein Paddle trifft, mit den Beats eines Songs abzustimmen
  • Der Ball bewegt sich mit konstanter Geschwindigkeit, die Paddles können sich jeweils überall in ihrer Bildschirmhälfte bewegen; der Kontaktpunkt bestimmt den Reflexionswinkel, und der Ball prallt an der oberen und unteren Wand ab
  • Platziert man die Paddles nahe der Mitte, lässt sich jedes Timing treffen, doch die Bildfläche wird nur wenig genutzt und die Bewegung wirkt eintönig, was eine gute Visualisierung erschwert
  • Das Problem wird als lineares Programm formuliert: Für jeden Beat werden die horizontale Paddle-Position und die horizontale Ballgeschwindigkeit bestimmt, um unter Einhaltung von Physik und Takt Paddle-Treffer fern der Mitte zu maximieren
  • Die Implementierung löst die linearen Nebenbedingungen mit CVXPY, berechnet aus den gefundenen Paddle-Positionen und Ballgeschwindigkeiten Reflexionswinkel und vertikale Positionen und erzeugt per Keyframe-Interpolation die Animation

Physik-Setup, um Pong an Musikbeats anzupassen

  • Ziel ist es, in dem klassischen Arcade-Spiel Pong die Momente, in denen der Ball von den Paddles abprallt, mit den Beats eines Songs zu synchronisieren und so eine Visualisierung zu erzeugen, in der sich die Paddles passend zur Musik bewegen
  • Dafür werden Teile der Spielphysik verändert
    • Der Ball bewegt sich mit konstanter Geschwindigkeit
    • Die Paddles können sich jeweils überall in ihrer eigenen Bildschirmhälfte bewegen
  • Einige Regeln aus dem klassischen Pong bleiben erhalten
    • Der Kontaktpunkt, an dem der Ball das Paddle trifft, bestimmt den Reflexionswinkel
    • Für die Paddles gibt es keine Geschwindigkeitsbegrenzung
    • Der Ball prallt an der oberen und unteren Bildschirmkante ab
  • Dieses Physik-Setup bietet genügend Freiheitsgrade, um den Ball zu gewünschten Zeitpunkten treffen zu lassen

Grenzen der Lösung mit zentraler Platzierung

  • Wenn beide Paddles nahe der Bildschirmmitte platziert werden, lassen sich beliebige Timing-Anforderungen erfüllen
    • Der horizontale Raum ist zwar klein, doch da der Ball an der oberen und unteren Wand abprallen kann, ist der vertikale Raum praktisch ausreichend
    • Soll ein Schlag länger dauern, kann der Ball näher an die Vertikale gespielt werden, wodurch die horizontale Geschwindigkeit sinkt
  • Diese Methode zeigt, dass für jede Eingabe eine Lösung existiert, ist visuell aber wenig interessant
  • Für eine gute Visualisierung ist die Nutzung der Bildschirmfläche wichtig
    • Wenn das Spiel in einem kleinen Bereich gefangen bleibt, wirkt es beengt und schwach
    • Das Publikum genießt die dynamische Bewegung, bei der die Paddles Bälle abfangen, die sie nur knapp zu erreichen scheinen
  • Entscheidend ist daher, wo die Paddles den Ball bei jedem Beat treffen sollten, um die Bildfläche großflächig zu nutzen und zugleich Beats und Physikregeln einzuhalten

Umformulierung als Constraint-Optimierung

  • Das Problem lässt sich als Constraint-Optimierung mit Zielfunktion, Variablen und Nebenbedingungen behandeln
    • Das Ziel ist, die Nutzung der Bildschirmfläche zu erhöhen
    • Die Variablen sind die Positionen, an denen der Ball abprallt
    • Die Nebenbedingungen sind die Spielphysik und die Beats des Songs
  • Durch die Formulierung als Constraint-Optimierung kann statt eines selbst entworfenen Algorithmus ein bestehender Solver die optimalen Paddle-Positionen berechnen
  • Wenn sich die Physik ändert, müssen nur die Nebenbedingungen aktualisiert werden; auch mit der Zielfunktion lässt sich leicht experimentieren
  • Es ist nicht nötig, die komplette 2D-Bewegung zu modellieren
    • Da die Gesamtgeschwindigkeit des Balls konstant ist, bestimmt die horizontale Geschwindigkeit auch die vertikale Geschwindigkeit
    • Die vertikale Position des Balls zu einem beliebigen Zeitpunkt kann per Simulation berechnet werden
    • Die vertikale Position des Paddles muss zur vertikalen Ballposition passen, um den Ball zu treffen; für den gewünschten Winkel kommt noch ein kleines Delta hinzu
    • Die Paddle-Positionen zwischen Treffern werden per linearer Interpolation glatt verbunden

Eingaben und lineare Nebenbedingungen

  • Feste Eingaben sind die Bildschirmbreite und die Ballgeschwindigkeit
    • W: Bildschirmbreite
    • S: Geschwindigkeit des Balls
  • Die Beat-Zeitpunkte stammen aus einer MIDI-Datei
    • T = {t_0, t_1, ..., t_n} sind die jeweiligen Beat-Zeitpunkte, zu denen der Ball ein Paddle treffen muss
    • Künftig könnten auch stärker automatisierte Methoden zur Extraktion aus Audio untersucht werden
  • Aus den Differenzen benachbarter Beat-Zeitpunkte entsteht die Dauer jedes Schlags
    • D = {d_0, d_1, ..., d_{n-1}}
    • d_i = t_{i+1} - t_i
  • Die Optimierungsvariablen sind horizontale Position und horizontale Geschwindigkeit
    • P = {p_0, p_1, ..., p_{n-1}} ist die horizontale Entfernung von der Bildschirmmitte, wenn ein Paddle den Ball trifft
    • Gerade Indizes stehen für das linke Paddle, ungerade Indizes für das rechte Paddle
    • V = {v_0, v_1, ..., v_{n-1}} ist die horizontale Geschwindigkeit des Balls nach jedem Treffer
    • Damit die Nebenbedingungen leichter zu formulieren sind, wird v_i unabhängig davon, ob sich der Ball nach links oder rechts bewegt, immer als positiv definiert
  • Die physikalischen Nebenbedingungen legen die Bereiche für Paddle-Position und Ballgeschwindigkeit fest
    • 0 ≤ p_i ≤ W/2
    • 0 < v_i ≤ S
  • Die Nebenbedingung zur Beat-Synchronisierung sorgt dafür, dass der Ball das nächste Paddle exakt zur richtigen Zeit erreicht
    • p_{i-1} + p_i = d_i v_i
    • Die linke Seite ist die gesamte horizontale Strecke zwischen zwei aufeinanderfolgenden Paddle-Treffern
    • Die rechte Seite ist das Produkt aus Schlagdauer und horizontaler Ballgeschwindigkeit

Zielfunktion und Animationserzeugung

  • Um die degenerierte Lösung zu vermeiden, bei der alles in der Mitte bleibt, werden die Paddles dazu angehalten, sich von der Bildschirmmitte zu entfernen
  • Die Zielfunktion maximiert die Summe der Abstände der Paddles von der Mitte
    • Maximize Σ p_i
  • Da alle Nebenbedingungen linear sind, lässt sich das Problem mit einem Solver für lineare Programmierung (LP) lösen
  • Für die Implementierung wird CVXPY verwendet
    • CVXPY löst konvexe Optimierungsprobleme; LP ist eine Teilmenge davon
    • Für diese Aufgabe wird nicht der gesamte Funktionsumfang benötigt, doch die Unterstützung komplexerer Zielfunktionen und Nebenbedingungen ist für kreative Experimente nützlich
  • Der Solver gibt die horizontalen Positionen zurück, an denen die Paddles den Ball treffen müssen, sowie die horizontale Geschwindigkeit des Balls
    • Daraus lässt sich der Reflexionswinkel berechnen
    • Die vertikale Position wird per Simulation berechnet
  • Die finale Animation verwendet die Positionen von Ball und Paddles zu den Trefferzeitpunkten als Keyframes
    • Zwischen den Treffern werden die Positionen interpoliert, um eine flüssige Bewegung zu erzeugen
  • Der Code ist als Open Source veröffentlicht: Github Repo

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-09-04
Hacker-News-Kommentare

  • Das erinnert mich an ein Projekt von vor etwa 20 Jahren, bei dem ich Audio für mehrere gleichzeitige Spieler für eine Kunstausstellung programmiert habe.
    Je intensiver das Spiel wurde, desto deutlicher wurde, dass die Ball-/Wandgeräusche tatsächlich Musik spielten, und die drei Spieler spielten in Wahrheit gemeinsam ein einziges Stück.
    Drei Arcade-Kabinette waren einander zugewandt aufgestellt, sodass jeder Spieler den Bildschirm der anderen nicht sehen konnte, und Geschwindigkeit/Richtung des Balls wurden leicht angepasst, damit er an musikalisch passenden Stellen Schläger oder Wand berührte und der richtige Ton entstand.
    Josh hat dazu auch etwas als Referenz auf seine Website gestellt: https://www.autogena.org/work/ping

    • Großartig. Gab es also eine fest vorgegebene Komposition, und das Gameplay wurde leicht daran angepasst?

  • Als Variante dieser Idee stelle ich mir vor, einen Reinforcement-Learning-Agenten für Atari-Spiele oder Super Mario zu trainieren und musikbasierte Belohnungen/Eingaben hinzuzufügen, damit das Spiel „musikalisch“ wirkt.
    Wie gut das aussehen würde oder ob es den Aufwand wert wäre, weiß ich nicht.

    • Ich bin nur ein Anfänger in Machine Learning, aber OpenAI hat einmal eine Python-Bibliothek für Reinforcement Learning mit Videospielen erstellt, und ein Fork davon wird noch immer aktiv gepflegt [1].
      Soweit ich mich von vor ein paar Jahren erinnere, konnte man sie in ein bis zwei Tagen, höchstens an einem Wochenende, zum Laufen bringen. Sie nutzte den RetroArch-Emulator und unterstützt sehr viele Emulatoren und Konsolen.
      https://github.com/Farama-Foundation/Gymnasium
      Es gibt auch ein großartiges YouTube-Video von SethBling über Machine Learning mit Super Mario World:
      https://www.youtube.com/watch?v=qv6UVOQ0F44
      Ich würde empfehlen, es selbst auszuprobieren. Im aktuellen AI-Hype scheinen Videospiele etwas unterschätzt zu werden, und ich denke, es steckt viel Potenzial darin, dass Maschinen beim Spielen Fähigkeiten lernen. Es gibt auch großes Potenzial darin, Spiele gezielt auszuwählen oder neu zu entwickeln, um bestimmte Fähigkeiten zu vermitteln. Andererseits ist es ab einem gewissen Punkt womöglich besser, Audio und Visuals ganz wegzulassen und mit der Maschine über Text oder reine Daten zu kommunizieren.
      Gleichzeitig habe ich schon Videos von Convolutional Neural Networks gesehen, die die einzelnen Pixel eines Bildes als Eingabe verwenden, daher könnte es auch positive Ergebnisse geben, wenn man mit Audiodaten oder Spektrogramm-Pixeln trainiert. Spiele im Takt der Musik zu spielen oder passend zu Melodie, Harmonie und Erzählung fast tänzerisch zu agieren, klingt auf jeden Fall unterhaltsam.
      Alles, was Menschen erschaffen haben, existierte zuerst in ihrer Vorstellung, und du besitzt ebenfalls ein solches Gehirn. Einer inneren Vision zu folgen und sie in die physische Realität zu bringen, ist etwas Schönes und wirkt wie ein Geschenk an die ganze Menschheit.
    • Crypt of the NecroDancer untersucht diese Idee, indem das Spiel Boni vergibt, wenn sich die Figur im Rhythmus bewegt.
    • Ich glaube nicht, dass das besonders gut wäre. In Mario gibt es nicht genug Rhythmus, um starke Musikalität hervorzurufen.
      Im Original waren die Sounds an die Bildrate gebunden, daher passierte so etwas im Grunde schon ein wenig. Spätere PAL-Portierungen liefen dann mit niedrigerer Bildrate, wodurch diese Eigenschaft verloren ging.

  • Das erinnert mich an die Polyrhythmus-Visualisierungen auf YouTube. Ein gutes Beispiel ist LucidRhythms:
    https://www.youtube.com/@LucidRhythms
    Ein bereits geschriebenes Stück nachträglich an eine Visualisierung anzupassen, wäre wohl fast unmöglich, aber es wäre interessant, wenn verschiedene Balken verschiedene Töne repräsentieren und sich der Ball bei Akkorden aufspalten würde.

    • Es wäre auch cool, N Schläger zu haben. Damit es nicht zu leicht wird, könnte man Kosten einführen, wenn die Schläger zu nah beieinander liegen, optimieren, welcher Schläger welchen Ton oder Schlag übernimmt, und außerdem große Tonhöhenwechsel bestrafen, damit sich einzelne Schläger auf bestimmte Register spezialisieren.

  • Wirklich großartig. Ich war völlig gefesselt davon, wie sich die Schläger bewegen, während der Beat weiterläuft.
    Manche Dinge passen schon allein beim Zuschauen einfach perfekt zusammen, und genau deshalb wirken sie schön; dieses Projekt ist so ein Fall.

  • Vorläufer: Eisenfunk - Pong (https://www.youtube.com/watch?v=cNAdtkSjSps)

    • Trotzdem ziemlich anders. In diesem Beispiel ertönen die Pieptöne mit konstanter Geschwindigkeit, also wurde das Video manuell auf die BPM des Stücks synchronisiert.
      Im Grunde ist das eher eine handgemachte Visualisierung auf jeden zweiten Kick-Drum-Schlag.
      Die eingereichte Arbeit dagegen hat Noten, die nicht einfach in einem simplen Viertelnoten-Tempo liegen, und wird auf Basis von Constraint Optimization automatisch „animiert“. Dadurch wird auch die Visualisierung viel interessanter.

  • Wirklich gut. Nur fühlt es sich für mich etwas unpassend an, dass man keine Herzen schicken kann, ohne zu abonnieren.

  • Technisch ist es in Ordnung, aber es gibt mehrere Stellen, an denen sich Schläger und Ball fast mit derselben Geschwindigkeit bewegen, sodass es so aussieht, als würde der Schläger den Ball ständig vor sich herschieben.
    Deshalb wäre es vermutlich besser, p[i] = 0 nicht zuzulassen. Wenn direkt auf ein großes d[i] ein sehr kleines d[i+1] folgt, ist das vielleicht unvermeidbar, aber wo es möglich ist, sollte man es wohl vermeiden.

    • Man könnte der Zielfunktion eine Strafe proportional zu d'[i] hinzufügen.

  • Ich stelle mir vor, in meinem Raum eine installation zu haben und dazu den MT-80S mit einem Display zu verwenden.
    Könnte ich dieses Timing überhaupt richtig begreifen? Ich bin darin nicht besonders klug, aber ich finde es interessant.
    https://www.matrixsynth.com/2014/07/roland-mt-80s-midi-playe...

  • Sehr interessant, aber irgendwie hasst mein Gehirn das Ganze total.
    Es scheint so etwas wie mein internes Kausalitätsmodell zu triggern, und deshalb ist es schwer anzusehen. Seltsam.

    • Was mir am deutlichsten fehlt, ist Dynamik. Vor allem in schnellen Passagen, wenn es zwischen viel lauteren Tönen „Ghost Notes“ gibt, fühlt es sich an, als würde etwas fehlen.
      Trotzdem ist es seltsamerweise befriedigend anzusehen. Ich frage mich, ob meine Erfahrung mit mehreren Instrumenten etwas mit diesem Gefühl zu tun hat. Für mich wirkt das ziemlich ähnlich wie Xylophon oder Steelpan.
    • Es sieht so aus, als würde der Ball in der Mitte des Schlägers abprallen und nicht an dessen Kante, und das wirkt weiterhin merkwürdig. Vielleicht schauen wir auch auf dasselbe Problem.

  • Atari hatte schon Ende der 1970er Jahre ein Gerät zur Visualisierung von Videomusik. Es wurde von einem der Pong-Entwickler entworfen und war entweder das erste oder eines der ersten Verbraucherprodukte dieser Art.
    https://en.wikipedia.org/wiki/Atari_Video_Music
    Falls du den Film Over the Edge gesehen hast: Claude und Johnny haben dort zu Hause so eins.