Synchroniser Pong avec le beat de la musique grâce à l’optimisation sous contraintes

 (victortao.substack.com)
1 points par GN⁺ 2024-09-04 | 1 commentaires | Partager sur WhatsApp
  • Une visualisation musicale façon Pong ajuste la physique du jeu et traite la position des raquettes comme une variable d’optimisation afin de faire coïncider le moment où la balle touche une raquette avec les beats du morceau
  • La balle se déplace à vitesse constante et chaque raquette peut se déplacer n’importe où dans sa moitié de l’écran ; le point de contact détermine l’angle de réflexion, et la balle rebondit sur les murs du haut et du bas
  • Placer les raquettes près du centre permet de respecter n’importe quel timing, mais l’utilisation de l’écran est réduite et le mouvement devient monotone, ce qui rend difficile la création d’une bonne visualisation
  • En fixant la position horizontale de la raquette et la vitesse horizontale de la balle à chaque beat, le problème est formulé comme un programme linéaire qui respecte les contraintes physiques et le rythme tout en maximisant les coups de raquette loin du centre
  • L’implémentation résout les contraintes linéaires avec CVXPY, puis calcule les angles de réflexion et les positions verticales à partir des positions de raquette et des vitesses de balle obtenues, avant de générer l’animation par interpolation de keyframes

Configurer la physique de Pong pour suivre les beats de la musique

  • L’objectif est de synchroniser, dans le jeu d’arcade classique Pong, le moment où la balle rebondit sur une raquette avec les beats d’un morceau, afin de créer une visualisation où les raquettes bougent au rythme de la musique
  • Pour cela, une partie de la physique du jeu est modifiée
    • La balle se déplace à vitesse constante
    • Chaque raquette peut se déplacer n’importe où dans sa propre moitié de l’écran
  • Certaines règles du Pong original sont conservées
    • Le point de contact entre la balle et la raquette détermine l’angle de réflexion
    • Les raquettes n’ont pas de limite de vitesse
    • La balle rebondit sur les bords supérieur et inférieur de l’écran
  • Cette configuration physique fournit les degrés de liberté nécessaires pour faire arriver la balle au moment souhaité

Les limites de la solution avec placement central

  • Si les deux raquettes sont placées près du centre de l’écran, il est possible de satisfaire n’importe quelle contrainte de timing
    • L’espace horizontal est réduit, mais comme la balle peut rebondir sur les murs du haut et du bas, l’espace vertical est en pratique suffisant
    • Si la durée souhaitée d’un tir est longue, on peut frapper la balle avec une trajectoire plus proche de la verticale afin de ralentir sa vitesse horizontale
  • Cette méthode montre qu’une solution existe pour toutes les entrées, mais elle n’est pas très intéressante visuellement
  • Pour une bonne visualisation, l’utilisation de l’espace de l’écran est importante
    • Si le jeu reste confiné dans une petite zone, il paraît étouffé et peu dynamique
    • Le public apprécie les mouvements dynamiques où les raquettes rattrapent une balle qui semble presque leur échapper
  • Le point essentiel est donc de déterminer, pour chaque beat, où les raquettes doivent frapper la balle afin d’utiliser largement l’écran tout en respectant le beat et les règles physiques

Transformer le problème en optimisation sous contraintes

  • Ce problème peut être traité comme un problème d’optimisation sous contraintes, avec une fonction objectif, des variables et des contraintes
    • L’objectif est d’augmenter l’utilisation de l’écran
    • Les variables sont les positions où la balle rebondit
    • Les contraintes sont la physique du jeu et les beats du morceau
  • En le formulant comme une optimisation sous contraintes, on peut calculer les positions optimales des raquettes avec un solveur existant plutôt que de concevoir un algorithme à la main
  • Si la physique change, il suffit de mettre à jour les contraintes, et il est également facile d’expérimenter avec la fonction objectif
  • Il n’est pas nécessaire de modéliser toute la 2D
    • Comme la vitesse totale de la balle est constante, la vitesse horizontale détermine aussi la vitesse verticale
    • Une simulation permet de calculer la position verticale de la balle à un instant donné
    • La position verticale de la raquette doit correspondre à celle de la balle pour la toucher, avec un petit delta ajouté pour obtenir l’angle souhaité
    • Les positions des raquettes entre deux coups sont reliées en douceur par interpolation linéaire

Entrées et contraintes linéaires

  • Les entrées fixes sont la largeur de l’écran et la vitesse de la balle
    • W: largeur de l’écran
    • S: vitesse de la balle
  • Les timings des beats sont obtenus depuis un fichier MIDI
    • T = {t_0, t_1, ..., t_n} correspond aux instants de chaque beat où la balle doit toucher une raquette
    • Il serait aussi possible d’explorer à l’avenir des méthodes d’extraction plus automatisées à partir de l’audio
  • La différence entre deux instants de beat adjacents donne la durée de chaque tir
    • D = {d_0, d_1, ..., d_{n-1}}
    • d_i = t_{i+1} - t_i
  • Les variables d’optimisation sont la position horizontale et la vitesse horizontale
    • P = {p_0, p_1, ..., p_{n-1}} est la distance horizontale par rapport au centre de l’écran au moment où une raquette frappe la balle
    • Les indices pairs représentent la raquette gauche, les indices impairs la raquette droite
    • V = {v_0, v_1, ..., v_{n-1}} est la vitesse horizontale de la balle après chaque coup
    • Pour faciliter la formulation des contraintes, v_i est toujours défini comme positif, indépendamment du fait que la balle se déplace vers la gauche ou vers la droite
  • Les contraintes physiques bornent la position des raquettes et la vitesse de la balle
    • 0 ≤ p_i ≤ W/2
    • 0 < v_i ≤ S
  • La contrainte de synchronisation avec les beats fait en sorte que la balle atteigne la raquette suivante exactement au bon moment
    • p_{i-1} + p_i = d_i v_i
    • Le membre de gauche est la distance horizontale totale parcourue entre deux coups de raquette consécutifs
    • Le membre de droite est le produit de la durée du tir par la vitesse horizontale de la balle

Fonction objectif et génération de l’animation

  • Pour éviter une solution dégénérée où les raquettes restent au centre, on les incite à s’éloigner du centre de l’écran
  • La fonction objectif maximise la somme des distances des raquettes par rapport au centre
    • Maximize Σ p_i
  • Toutes les contraintes étant linéaires, le problème peut être résolu avec un solveur de programmation linéaire (LP)
  • L’implémentation utilise CVXPY
    • CVXPY résout des problèmes d’optimisation convexe, dont les LP sont un sous-ensemble
    • Même si toutes ses fonctionnalités ne sont pas nécessaires ici, sa prise en charge de fonctions objectif et de contraintes plus complexes est utile pour expérimenter de manière créative
  • Le solveur renvoie les positions horizontales où les raquettes doivent frapper la balle, ainsi que la vitesse horizontale de la balle
    • Ces valeurs permettent de calculer les angles de réflexion
    • Les positions verticales sont calculées par simulation
  • L’animation finale utilise les positions de la balle et des raquettes aux instants de frappe comme keyframes
    • Entre deux coups, les positions sont interpolées pour créer un mouvement fluide
  • Le code est publié en open source : Github Repo

À lire aussi

1 commentaires

 
GN⁺ 2024-09-04
Commentaires Hacker News

  • Ça me rappelle un projet, il y a une vingtaine d’années, où j’avais codé un audio multijoueur pour une exposition d’art
    Plus la partie devenait intense, plus il apparaissait clairement que les sons de balle et de mur jouaient de la musique, et que les trois joueurs interprétaient en réalité une seule et même composition ensemble
    On avait disposé trois bornes d’arcade face à face pour que chaque joueur ne puisse pas voir l’écran des autres, et on ajustait légèrement la vitesse/la direction de la balle afin qu’elle touche la raquette ou le mur au bon moment sur le plan musical, pour produire le bon son
    Josh a aussi mis une référence sur son site : https://www.autogena.org/work/ping

    • Super. Donc il y avait une composition fixe, et le gameplay était légèrement ajusté pour s’y conformer ?

  • Une variante de cette idée me fait imaginer qu’on pourrait entraîner des agents d’apprentissage par renforcement sur des jeux Atari ou Super Mario, en ajoutant des récompenses/entrées basées sur la musique pour produire un gameplay paraissant « musical »
    Je ne sais pas à quel point ce serait agréable à regarder, ni si ça vaudrait le coup

    • Je suis débutant en machine learning, mais OpenAI a autrefois créé une bibliothèque Python pour l’apprentissage par renforcement sur jeux vidéo, et son fork est toujours activement maintenu [1]
      De mémoire, il y a quelques années, on pouvait faire tourner quelque chose en un ou deux jours, ou au plus sur un week-end. Ça utilisait l’émulateur RetroArch et prenait en charge énormément d’émulateurs et de consoles
      https://github.com/Farama-Foundation/Gymnasium
      Il y a aussi une excellente vidéo YouTube de SethBling sur le machine learning avec Super Mario World :
      https://www.youtube.com/watch?v=qv6UVOQ0F44
      Je recommande de l’essayer soi-même. Avec l’emballement actuel autour de l’IA, j’ai l’impression que les jeux vidéo sont un peu sous-estimés, alors qu’il y a beaucoup de potentiel dans le fait de faire apprendre des compétences à une machine en jouant. Il y a aussi un grand potentiel dans le choix, ou la création, de jeux pour enseigner des compétences précises. Cela dit, à ce stade, il vaudrait peut-être mieux abandonner l’audio et le visuel et communiquer avec la machine via du texte ou des données brutes
      J’ai aussi vu une vidéo de réseau neuronal convolutif prenant en entrée chaque pixel d’une image, donc je me dis qu’on pourrait aussi obtenir des résultats positifs en apprenant à partir de données sonores ou de pixels de spectrogramme. Voir un jeu joué en rythme avec la musique, ou d’une manière qui danse avec la mélodie, l’harmonie et le récit, serait clairement amusant
      Tout ce que l’humain a créé a d’abord existé dans son imagination, et vous avez vous aussi un cerveau capable de cela. Poursuivre une vision intérieure et l’amener dans la réalité physique est une belle chose, et cela ressemble à un cadeau fait à l’humanité tout entière
    • Crypt of the NecroDancer explore cette idée en accordant des bonus en jeu quand on déplace le personnage en rythme
    • Ça ne serait probablement pas terrible. Mario n’a pas assez de rythme pour évoquer fortement une musicalité
      Les sons de l’original étaient liés à la fréquence d’images, donc ce genre de chose se produisait déjà un peu de base. Les versions PAL, ensuite, tournaient à une fréquence d’images plus basse, ce qui a cassé cette propriété

  • Ça me fait penser aux visualisations de polyrythmes sur YouTube. Un bon exemple, c’est LucidRhythms
    https://www.youtube.com/@LucidRhythms
    Faire correspondre à rebours un morceau déjà écrit à une visualisation serait presque impossible, mais ce serait amusant si différentes barres représentaient différentes notes et que la balle se divisait sur les accords

    • Avoir N raquettes pourrait aussi être sympa. Pour éviter que cela ne devienne trop facile, on pourrait imposer un coût quand les raquettes se rapprochent trop, optimiser quelle note ou quel temps chaque raquette prend en charge, et ajouter aussi un coût pour les changements brusques de hauteur, de sorte que chaque raquette puisse se spécialiser dans une certaine tessiture

  • Vraiment superbe. J’étais hypnotisé en regardant les raquettes bouger au fil du rythme
    Il y a des choses qui tombent juste rien qu’à les regarder, et c’est ce qui les rend belles ; ce projet en fait partie

  • Antécédent : Eisenfunk - Pong (https://www.youtube.com/watch?v=cNAdtkSjSps)

    • C’est quand même assez différent. Dans cet exemple, les bips ont une cadence constante, donc la vidéo a été synchronisée manuellement sur le BPM du morceau
      En gros, ça se rapproche davantage d’une visualisation faite à la main sur un coup de grosse caisse sur deux
      Ici, en revanche, les notes ne sont pas sur un simple tempo en noires, et l’« animation » est automatisée à partir de l’optimisation sous contraintes. La visualisation devient donc bien plus intéressante

  • J’aime beaucoup. En revanche, comme on ne peut pas envoyer de cœur sans s’abonner, ça me paraît un peu inadapté pour moi

  • Techniquement, c’est correct, mais il y a plusieurs moments où les raquettes et la balle se déplacent presque à la même vitesse, ce qui donne l’impression que les raquettes poussent continuellement la balle
    Pour cette raison, il vaudrait mieux ne pas autoriser p[i] = 0. Si un grand d[i] est immédiatement suivi d’un tout petit d[i+1], ce sera inévitable, mais on devrait pouvoir l’éviter quand c’est possible

    • On pourrait ajouter à la fonction objectif une pénalité proportionnelle à d'[i]

  • Ça me donne envie d’avoir une installation chez moi, avec un MT-80S et un écran
    Est-ce que je pourrais vraiment comprendre correctement ce timing ? Je ne suis pas très calé là-dessus, mais ça m’intéresse
    https://www.matrixsynth.com/2014/07/roland-mt-80s-midi-playe...

  • C’est vraiment fascinant, mais curieusement mon cerveau déteste ça profondément
    J’ai l’impression que ça heurte une sorte de modèle causal interne, et je trouve ça difficile à regarder. Étrange

    • Ce qui me manque le plus visiblement, c’est la dynamique. En particulier dans les passages rapides où il y a des « ghost notes » entre des notes bien plus fortes, on a l’impression qu’il manque quelque chose
      Et pourtant, d’une manière étrange, c’est satisfaisant à regarder. Je me demande si le fait d’avoir joué de plusieurs instruments a un lien avec cette sensation. Pour moi, ça évoque assez fortement des instruments comme le xylophone ou le steelpan
    • Le fait que la balle semble rebondir au centre des raquettes plutôt que sur leurs bords continue à me paraître bizarre. C’est peut-être le même problème qui nous saute aux yeux

  • Atari avait à la fin des années 1970 un appareil de visualisation musicale vidéo. Il a été conçu par l’un des développeurs de Pong, et c’était le premier produit grand public de ce genre, ou l’un des tout premiers
    https://en.wikipedia.org/wiki/Atari_Video_Music
    Si vous avez vu le film Over the Edge, Claude et Johnny en ont un chez eux