Xu & Verbrugge : faire de la « direction de la gravité » et du « temps » des coordonnées de génération de niveaux — lu par Fukai

Résumé en un paragraphe

La génération automatique de niveaux a longtemps été un « travail de création de terrain ». On aligne murs, sols et couloirs, puis on vérifie après coup des mécaniques comme « la gravité peut s'inverser » ou « la plateforme bouge ». Kaijie Xu et Clark Verbrugge, de l'Université McGill, ont inversé cet ordre : leur proposition est d'élever la mécanique elle-même au rang de coordonnée et de l'explorer en même temps que le terrain.

Ce cadre s'appelle HDPCG (High-Dimensional Procedural Content Generation, génération procédurale de contenu en haute dimension). On construit un grand graphe en ajoutant aux coordonnées de grille (x, y) des informations comme « dans quelle couche on se trouve » ou « à quelle seconde on en est ». En effectuant une recherche de chemin ordinaire sur ce graphe, une exigence comme « un chemin comportant exactement trois inversions de gravité » peut être satisfaite dès la génération, et non par un contrôle a posteriori.

J'ai lu la version déposée sur arXiv. Un article du même titre est publié dans les actes de FDG 2026 (21e Foundations of Digital Games), preuve qu'il a passé l'évaluation par les pairs.

À propos de cet article

Le titre est « High Dimensional Procedural Content Generation ». Les auteurs, Kaijie Xu et Clark Verbrugge, sont tous deux rattachés à l'Université McGill, à Montréal, au Canada.

J'ai lu la version arXiv, dont le coin de page indique « arXiv:2602.18943v1 [cs.AI] 21 Feb 2026 » : un preprint déposé le 21 février 2026 (un manuscrit publié avant évaluation par les pairs). Mais un article du même titre figure, avec un DOI, dans les actes de FDG 2026, tenu du 10 au 13 août à la Royal Danish Academy de Copenhague. Autrement dit, il a bien passé l'évaluation par les pairs. Je précise que les chiffres ci-dessous proviennent de la version arXiv et peuvent différer, dans le détail, de la version finale des actes.

J'ai choisi cet article aujourd'hui car, pour un site de puzzles, c'est un type de recherche rare, « directement implémentable ». Inversion de gravité, bascule entre mondes parallèles, plateformes traversées en arrêtant le temps : ce sont là des verbes majeurs du puzzle-plateforme, que ce site a déjà traités dans Retourner la gravité comme verbe. Cette recherche pousse la question au-delà de « peut-on générer » jusqu'à « peut-on générer sur commande ».VVVVVV (Terry Cavanagh, 2010), page Steam. Un bouton suffit à inverser la gravité haut/bas. L'article cite ce jeu comme modèle pour sa reconstitution sous Unity.

Ce que l'on savait déjà

Le PCG (Procedural Content Generation, génération automatique de contenu) désigne la technique consistant à faire créer des niveaux et des assets par la machine. Étudié depuis des décennies, il excelle désormais dans la création de terrain. Mais selon les auteurs, la formulation de la génération de niveaux reste « largely geometry-first » (essentiellement centrée sur la géométrie d'abord).

Comment les mécaniques ont-elles été traitées jusqu'ici ? L'article explique que le mouvement dépendant du temps, les règles d'interaction discrètes ou les états autres que le terrain ont été injectés non pas directement dans le générateur, mais comme fonctions objectif basées sur la simulation ou heuristiques de post-traitement. L'ordre est : créer, faire jouer, baisser la note si ça ne va pas.

Cet ordre a un point faible. Les auteurs écrivent que « la simulation ne force les exigences que de manière indirecte », rendant difficile de viser, pendant la génération, une structure de niveau précise pour une mécanique donnée. Pour créer « un niveau avec trois inversions de gravité », il faut générer au hasard, compter, et jeter — encore et encore.

Le point de départ, c'est donc que ce qui manque n'est pas un algorithme particulier mais la représentation elle-même. Il faut une représentation générale et extensible, et une manière de poser le problème, pour traiter des niveaux riches en mécaniques.

Comment ils ont résolu le problème

L'idée est étonnamment simple. On dote les cases d'« attributs » et on écrit l'état du monde comme une cellule dans un espace d'état étendu. Le programme de recherche de chemin peut alors considérer terrain et mécaniques ensemble, dans un seul graphe. Seul le graphe grandit ; la méthode de recherche, elle, ne change pas.

一つ目の軸は空間(Direction-Space)である。地形に「層」という飛び飛びの次元を足し、(x, y, z, 層)という4つの座標で到達できるかどうかを検証する。こうすると、重力の反転も、並行世界の切り替えも、「層をまたぐ辺を1本通った」という同じ出来事として扱える。バラバラだった仕掛けが一つの型に収まる。

Le premier axe est l'espace (Direction-Space). On ajoute au terrain une dimension discrète, la « couche », et on vérifie l'accessibilité avec quatre coordonnées (x, y, z, couche). L'inversion de gravité et la bascule entre mondes parallèles peuvent ainsi être traitées comme un seul et même événement : « on a emprunté une arête qui traverse les couches ». Des mécaniques jusque-là disparates entrent dans un seul modèle.

Le second axe est le temps (Direction-Time). On utilise ici un graphe étendu dans le temps (time-expanded graph : la même carte dupliquée à chaque pas de temps, reliée par des arêtes représentant l'écoulement du temps). Les actions du joueur sont écrites comme trois types de transitions — « attendre », « marcher », « monter » — avec des contraintes comme la vérification que la case n'est pas occupée, ou le fait qu'on ne peut monter ou descendre d'une plateforme mobile qu'à ses extrémités.

Les deux axes passent par un même pipeline en quatre étapes : on crée d'abord un squelette grossier, on le traduit en terrain sous contrôle, on vérifie sa validité sur le graphe de haute dimension, puis on note avec plusieurs indicateurs. Côté espace, trois méthodes sont proposées : Naive Noise Baseline (NNB), qui se contente d'un bruit i.i.d. (indépendant et identiquement distribué) ; Naive Penalty A* (NP-A*), qui disperse en plaçant une répulsion autour des passages déjà empruntés ; et Potential Field A* (PF-A*), qui vise directement les points de bascule via des champs d'attraction et de répulsion.

Côté temps, trois méthodes également : Static Backbone Baseline, qui trace d'abord un squelette en A* 2D/3D puis place des plateformes périodiques et des obstacles vérifiés par recherche en largeur ; TEG-A*, doté d'une mémoire légère via masque de bits ; et TEG-DP, une programmation dynamique qui résout vers l'avant sur un graphe orienté acyclique en couches.

Ce que l'on a appris

Côté espace, le chiffre le plus parlant est celui de la conformité à la commande. Pour l'écart à la cible sur l'intervalle de bascule (MAE, erreur absolue moyenne), le tableau 3 donne pour PF-A*, aux échelles petite, moyenne et grande : 0,002 / 0,000 / 0,000. NP-A* : 0,091 / 0,093 / 0,097. NNB, sans guidage : 0,288 / 0,284 / 0,326. Les méthodes ciblées respectent quasi parfaitement la commande d'intervalle.

La densité de bascule est moins nette. Dans le même tableau 3, PF-A* obtient 2,247 / 2,078 / 1,343, et NP-A* 2,217 / 1,366 / 2,554 : les deux méthodes se disputent la victoire selon l'échelle. Mais NNB affiche 9,410 / 8,738 / 10,978, un ordre de grandeur différent. On peut lire que « guider fonctionne » est clair, mais que « quel guidage est le plus fort » dépend de l'échelle.

Comme indicateur de robustesse, l'article mesure l'ARR (alternative route robustness, robustesse des chemins alternatifs). En moyenne sur une exécution unique, PF-A* obtient 0,338 / 0,319 / 0,530, NP-A* 0,156 / 0,215 / 0,360, NNB 0,037 / 0,042 / 0,057. Comparé à l'absence de guidage, PF-A* laisse subsister 9 à 10 fois plus de chemins alternatifs — autrement dit, on n'aboutit pas à une multitude d'impasses.

La vitesse reste dans une plage utilisable. Selon le tableau 4, une exécution unique de PF-A* prend 0,138 ± 0,060 s à petite échelle, 0,663 ± 0,278 s à échelle moyenne, et 4,119 ± 1,136 s même à grande échelle. Quelques secondes pour créer un niveau : largement suffisant pour un traitement par lots quotidien.

Côté temps, l'échelle des expériences est clairement précisée. Le tableau 2 indique : petite = grille 30×15, plafond temporel 200, 12 graines aléatoires ; moyenne = 50×25, plafond 300, 8 graines ; grande = 80×40, plafond 500, 4 graines. Le score global du tableau 6 (exécution unique), à grande échelle : Static Backbone 7,81 ± 1,77, TEG-A* 13,30 ± 3,51, TEG-DP 20,35 ± 9,58. Les durées correspondantes : 0,31 ± 0,20 s / 0,25 ± 0,18 s / 6,42 ± 0,68 s.

Le tableau 5 montre que TEG-DP surpasse significativement TEG-A* « dans tous les cas sauf deux réglages (petite échelle en exécution unique, moyenne échelle en exécution unique) », avec une taille d'effet (delta de Cliff) qualifiée de « large ». Un résultat de forme familière : plus on résout finement, mieux c'est, mais aussi plus c'est lent.

Comment les créateurs peuvent s'en servir

Premièrement. Pour un puzzle d'inversion de gravité, on peut confier « le nombre de bascules » et « l'intervalle de bascule » comme commande. Cet article montre qu'une commande d'intervalle peut être respectée avec une erreur quasi nulle. On peut fixer verbalement une courbe de difficulté — « intervalle large au début, resserré à la fin » — et la transformer directement en paramètre du générateur, sans plus avoir à générer, compter, jeter.

Deuxièmement. Pour une scène de plateformes mobiles, le graphe étendu dans le temps permet de concevoir le ratio « attente » / « trajet ». La proportion de temps passé à l'arrêt, la proportion de temps sur la plateforme, l'intervalle de contact : ces indicateurs alignés font de la « sensation d'attente forcée » un bouton réglable. Ajuster le tempo devient une commande chiffrée plutôt qu'une affaire de ressenti.Contrast (Compulsion Games, 2013), page Steam. On va et vient entre un monde en 3D et un monde d'ombres projetées sur les murs. Cité ici comme exemple parlant du verbe « changer de couche » (ce jeu n'a pas été utilisé dans l'article).

Troisièmement. Utile même sans générer. Il suffit de placer un niveau conçu à la main sur ce graphe étendu. L'existence d'un « raccourci permettant d'atteindre l'objectif sans utiliser l'inversion de gravité » se détecte en lançant la recherche de chemin en interdisant les arêtes traversant les couches. Pas besoin d'adopter tout le générateur : on peut n'en extraire que le vérificateur.

Quatrièmement. Un test de perturbation comme porte de qualité. L'article mesure la robustesse en introduisant de petites perturbations après génération et en vérifiant si l'on peut regénérer. La même approche vaut en production : pour un puzzle quotidien, avant publication, on teste « décaler une plateforme d'une case » ou « retarder d'un cran », et on ne diffuse pas les plateaux dont la solution s'effondre. L'idée : utiliser un indicateur comme l'ARR pour la décision d'envoi.

Cinquièmement, en guise d'avertissement. « conforme à la commande » et « amusant » sont deux choses distinctes. Tous les indicateurs de cet article mesurent la première. En intégrant un générateur, mieux vaut ne pas faire l'économie de tests de jeu même si tous les indicateurs sont au vert.

Limites

Les auteurs relèvent cinq limites. D'abord, le TEG-A* idéal côté temps doit gonfler l'état avec mémoire et récompense pour favoriser des contacts « significatifs et non répétitifs », ce qui entraîne une explosion d'état. En pratique, on utilise donc une version simplifiée, plus maniable mais moins capable de façonner strictement les interactions — ce qui laisse un écart entre la base Static et le DP, écrivent-ils.

Ensuite, seules des méthodes constructives basées sur la recherche sont traitées ; le PCGML (PCG par apprentissage automatique) ou l'apprentissage par renforcement (un cadre où l'on apprend, par essais-erreurs, des actions à plus forte récompense), capables d'apprendre des connaissances préalables ou des fonctions de valeur sur cet espace d'état de haute dimension, ne sont pas encore intégrés. Troisièmement, chaque axe mécanique est évalué séparément ; le succès et la montée en échelle lorsqu'on mélange plusieurs mécaniques dans un même espace d'état restent non évalués. Quatrièmement, la robustesse n'est mesurée qu'a posteriori par perturbation, sans être intégrée à la fitness d'un algorithme génétique (cela impliquerait de régénérer à répétition, avec un coût qui exploserait).

Et la cinquième est la plus lourde. Les auteurs écrivent clairement « we have not conducted user studies » (aucune étude utilisateur n'a été menée) : la jouabilité et le tempo s'appuient sur des indicateurs et des replays, mais une preuve formelle du plaisir reste un travail futur, reconnaissent-ils.

Ce que Fukai souligne ici concerne le point de comparaison. La base NNB, côté espace, est une méthode quasi sans guidage (« bruit i.i.d. et bascule de couche dans l'ordre numérique »). Il serait plus honnête de lire le chiffre « 9 à 10 fois supérieur » comme une confirmation soigneuse d'une évidence : le guidage bat l'absence de guidage. Je n'ai pas trouvé, dans ce que j'ai lu, de tableau comparant frontalement cette méthode aux techniques de PCG existantes.

Un dernier point : TEG-DP prend 6,42 s en exécution unique à grande échelle, mais l'ordre de grandeur change dès qu'on le fait tourner dans un algorithme génétique. Pour un usage type puzzle quotidien (un niveau par jour), pas de problème ; mais pour une génération à la volée pendant le jeu, je pense que l'état actuel de cet article n'y suffit pas encore.

La lecture de Fukai

Je souhaite situer cette recherche dans le mouvement « la génération de niveaux déménage de la cartographie vers la satisfaction de contraintes ». Dans le vocabulaire de la critique de conception, c'est un travail qui traduit en coordonnées explorables le « placement des verbes » que le level designer effectue implicitement dans sa tête. Au moment où l'inversion de gravité cesse d'être « un élément visuel » pour devenir « une arête du graphe », l'intervalle comme le nombre deviennent commandables. Ce qui est intéressant, c'est qu'on n'a presque inventé aucun nouvel algorithme pour cela : on garde les vieux outils que sont A* et la programmation dynamique, en ne changeant que la manière d'écrire le plateau. Je lis là un article qui illustre, avec le vocabulaire du puzzle-plateforme, la leçon classique selon laquelle changer de représentation rend le problème plus facile.

Conclusion

L'article présente aussi une démonstration sous Unity. Côté espace, un niveau 2,5D d'inversion de gravité, et un niveau 3,5D où l'on bascule entre deux états temporels pour traverser terrain et ennemis. Ce dernier cite comme modèles A Crack in the Slab de Dishonored 2 et Effect and Cause de Titanfall 2. Les auteurs écrivent : « ce qui est généré est directement un niveau Unity ; ce que l'on voit est directement jouable. » En conclusion, relier ces indicateurs au tempo ressenti, à la sensation de jeu et au plaisir est laissé comme travail futur.

Pour aller plus loin : lire, dans la même lignée de conférence, des travaux portant sur l'évaluation même du PCG — par exemple le courant qui cherche à établir un benchmark du PCG (The Procedural Content Generation Benchmark) — permet de dessiner une carte de « ce qui fait une bonne génération ». Sur ce site, les trois rubriques Magnétisme et gravité, Manipulation du temps et Puzzle-plateforme correspondent exactement aux verbes que cet article a transformés en coordonnées. Avant d'implémenter, observer comment les jeux existants ont utilisé ces verbes devrait aider à voir quels chiffres commander.

Références

Articles et documents consultés pour ce texte :

・High Dimensional Procedural Content Generation (Kaijie Xu, Clark Verbrugge, McGill University, 2026, arXiv:2602.18943v1 [cs.AI], 21 Feb 2026)

・Même article / Proceedings of the 21st International Conference on the Foundations of Digital Games (FDG 2026), DOI 10.1145/3815598.3815606 (version évaluée par les pairs)

・Site officiel de FDG 2026 (10-13 août 2026, Royal Danish Academy, Copenhague)

・Images de l'article issues des pages Steam : VVVVVV (Terry Cavanagh, 2010) / Contrast (Compulsion Games, 2013). Aucun des deux n'a été un jeu expérimental de l'article ; ils illustrent seulement les verbes.

・Le schéma est une réalisation originale de Fukai (caractères alphanumériques uniquement).