Alt-F4 n°63 - Dana Dev Blog : Spaghettis dans les schémas de recettes 12-08-2022
traduit par bev, Credne, Firerazer
Après une pause plutôt longue, Alt-F4 vous revient avec un article rappelant les bons vieux FFF : un journal de développeur ! Seulement ici, ce n’est pas à propos du jeu en lui-même, mais d’un mod unique et un peu fou. Credne a mis Dana au monde, et cela a nécessité pas mal de boulot pour y arriver. Beaucoup de détails techniques et même des concepts issus du football sont au menu, il est temps d’y aller !
Le journal du développeur de Dana : à propos des spaghettis dans les schémas de recettes Credne
Dana… C’est quoi ?
Dana est un mod qui vise à répondre à une question simple et récurrente dans Factorio : “Comment puis-je fabriquer l’objet X ?”.
Il y a déjà pas mal de mods qui font cela : FNEI, Recipe Book, What is it really used for?, etc. Ces mods ont tous une approche commune. Supposons qu’un nouveau joueur veuille savoir comment fabriquer le pack de science chimique (celui de couleur bleue). Ce joueur le recherche donc avec l’un de ces mods (ou directement via la liste des recettes de Factorio), et voit qu’il existe une seule recette, qui demande des circuits rouges, du soufre et des moteurs. Ce nouveau joueur se demande donc “Comment faire des circuits rouges ?”, il cherche et ne trouve qu’une seule recette qui nécessite des barres de plastique, des fils de cuivre et des circuits verts. Question suivante : “Comment faire des barres de plastique ?” : une recette qui nécessite du gaz de pétrole. “Comment faire du gaz de pétrole ?” : quatre recettes, qu’il faut inspecter une à une, et ainsi de suite. C’est long, fastidieux, et le joueur risque d’oublier certaines étapes (comme le soufre, ou l’acier).
Dana est née de cette frustration d’avoir à appliquer ce processus pendant des heures avec des mods complexes. Il a une approche légèrement différente pour répondre à ces questions.
Dana travaille en profondeur. Lorsqu’on lui demande comment fabriquer un pack de science chimique, il vous montre toutes les étapes successives nécessaires, en partant des matières premières. Et il le fait directement dans le jeu, en vous dessinant un schéma de recettes agréable™ et compréhensible™. Les joueurs peuvent naviguer dans le schéma avec les touches de déplacement, zoomer et dézoomer avec la molette de la souris, et sélectionner des nœuds ou des liens pour obtenir des informations supplémentaires. Il est également possible de dessiner le schéma de fabrication complet de la partie en cours (celui du jeu de base sera présenté plus loin dans cet article), ou un schéma “d’utilisation” (c’est-à-dire, quels sont tous les objets qui peuvent être fabriqués à partir de X).
Dana a été conçu dès le départ pour fonctionner avec n’importe quelle combinaison de mods ajoutant/modifiant/supprimant des recettes ou des objets. Il n’y a pas de configuration codée en dur apportée par le joueur, les modeurs, ou livrée directement avec Dana. Dans cette vidéo, le mod a lui-même placé le “Bloc du cuivre” entre le “Bloc du fer” et le “Bloc du raffinage”, le “Pétrole lourd” au-dessus du “Pétrole léger”, a décidé seul de la manière dont les lignes devaient être dessinées/fusionnées/courbées, des coordonnées X-Y de chaque bloc, etc. Tout ce que Dana a comme information, c’est la liste complète des objets, des recettes et des ressources naturelles disponibles. Ce travail est effectué par un algorithme de tracé de graphes (le morceau de code qui prend le tas de recettes/objets et décide où les placer sur l’écran et comment les relier) spécialement conçu pour Factorio, qui fera l’objet de cet article.
Journal de développement : dessiner les spaghettis du schéma
L’article d’aujourd’hui présente quelques détails (que nous espérons intéressants) sur le fonctionnement interne du générateur de schémas de Dana agréables™ et compréhensibles™. Pour donner une introduction générale, les schémas de Dana sont une variante des graphes en couches. Cela signifie que les objets et les recettes sont placés dans des couches de nœuds, séparées par des couches de liens.
La première chose que fait Dana est de décider combien de couches de nœuds sont nécessaires, et dans quelle couche chaque objet/recette sera placé. La deuxième étape a pour but de déterminer la coordonnée horizontale de chaque objet/recette. La troisième étape consiste à construire les couches de liens. Et la dernière permet d’attribuer une coordonnée verticale à chaque élément du graphe, maintenant que le nombre de couches et leur hauteur sont connus.
L’algorithme complet de mise en page est bien trop vaste et technique pour un article d’Alt-F4, donc le reste de cet article se concentrera sur la troisième étape, qui consiste à construire les couches de liens. Voici le problème : étant donné deux couches de nœuds consécutives, tracez les liens nécessaires dans la couche de liens, afin d’obtenir un schéma agréable™ et compréhensible™ :
Accessoirement, il s’agit plus ou moins d’une variante d’un exercice de maternelle :
Puisque des enfants de 5 ans le font, ça ne devrait pas être difficile à programmer, non ?
La conception : un schéma agréable™ et compréhensible™ ?
Tout d’abord, prenons un papier et un crayon (ou votre éditeur d’images préféré) et répondons à une question importante : à quoi doivent ressembler ces liens ? Comme on peut l’imaginer, ce qui rend un schéma agréable™ et compréhensible™ est assez difficile à définir.
Peut-être de simples lignes droites, comme la plupart des générateurs de graphes ?
C’est peut-être efficace sur des petits schémas, mais ça ne parvient pas à être agréable™ et compréhensible™ avec des grands schémas. Les lignes presque parallèles qui se croisent sont difficiles à suivre, et les zones avec une forte densité de lignes deviennent un bloc tout blanc. La bonne vieille ligne droite n’est même pas suffisante pour les schémas de fabrication du Factorio standard, que dire alors des schémas en modés !
Donc, retour à la planche à dessin pour une solution plus agréable™ et compréhensible™. Souvenons-nous des directives générales pour la convivialité des liens dans les graphes :
- Minimiser les croisements de lignes, surtout entre des lignes presque parallèles.
- Minimiser les courbes pour un lien.
- Minimiser la longueur des liens.
En plus de cela, il existe des règles générales de conception d’interface utilisateur :
- L’expérience de l’utilisateur est réduite à néant s’il doit faire défiler l’écran horizontalement/verticalement pour recouper les informations provenant de différentes parties de l’interface. Pour éviter cela, les schémas doivent être aussi compacts que possible.
- Moins, c’est plus : si la même quantité d’informations peut être transmise avec quatre lignes au lieu de vingt, c’est probablement une bonne chose à faire.
Donc maintenant, il est temps de chercher de meilleures idées. Et la meilleure façon de rechercher quoi que ce soit, comme nous le savons tous, c’est de demander à Google d’appuyer sur “T” dans Factorio :
Le moteur de rendu des graphes de Factorio a une façon plus subtile de présenter les liens. Chaque lien est décomposé en trois segments : deux verticaux et un horizontal. Cette approche s’adapte bien mieux aux graphes plus larges, car :
- Il n’y a jamais de croisement de lignes presque parallèles. Tous les croisements sont à angle droit, ce qui est optimal pour empêcher les utilisateurs de suivre la mauvaise ligne.
- La densité des liens est maîtrisée : il y a toujours suffisamment d’espace entre les lignes parallèles pour les distinguer les unes des autres.
Le prix de cette lisibilité est l’espace vertical : il doit y avoir suffisamment d’espace entre deux rangées de technologies pour pouvoir ajouter tous les segments horizontaux sans qu’il y ait de collisions :
Pour minimiser ce coût, il existe une optimisation simple mais néanmoins énorme : et si les lignes ne reliaient pas seulement deux éléments, mais un nombre quelconque d’éléments ? Il suffit de tracer une seule ligne horizontale large pour chaque objet/technologie, puis d’ajouter autant de lignes verticales que nécessaire pour se connecter aux nœuds.
Beaucoup plus compact, moins d’encombrement, assurément agréable™ et compréhensible™. Cela donne une ambiance “bus principal” à ces sections de schéma qui, nous l’espérons, semblera naturelle à un joueur de Factorio, tout en atteignant un bon compromis du point de vue des directives générales. C’est également techniquement possible avec l’API de rendu de Factorio, car les liens ne sont qu’un ensemble de lignes, de triangles et de cercles. Cela permet presque à Dana de faire tenir le schéma complet des fabrications de Factorio sur un seul écran :
La partie codage
Voilà, c’est terminé pour la planche à dessin. Il est temps de transformer ce problème en de nombreuses lignes de code pour que le travail soit terminé ! Mais avec cela viennent d’autres problèmes. Tout d’abord, les mods de Factorio sont réalisés dans un langage appelé Lua, et Lua a un écosystème ridiculement stérile. Impossible de trouver une bibliothèque capable de faire ce genre de routage de liens.
Une autre solution serait de porter une bibliothèque à partir d’autres langages. Malheureusement, il existe de nombreuses bibliothèques pour dessiner des graphes conventionnels, mais Dana doit maintenant gérer des liens entre un nombre quelconque de nœuds. Ce n’est plus un graphe, mais un hypergraphe. Bien que ce mot ait l’air nettement plus cool, il n’existe pas beaucoup de bibliothèques logicielles pour les dessiner et, en général, il y a beaucoup moins de littérature scientifique sur le sujet. Je n’ai pas réussi à trouver des pistes pour faire le routage à la manière de Dana.
Dana a donc un routeur fabriqué “presque” de toutes pièces. “Presque”, parce qu’il y avait beaucoup d’inspiration à trouver ailleurs, il fallait juste regarder dans des endroits inattendus…
La conception de circuits imprimés
Il existe des personnes dont le travail quotidien nécessite de relier des points sur un plan 2D : les concepteurs de circuits imprimés (PCB). Et pour des problèmes presque identiques au routage des liens de Dana, ils disposent d’une famille d’algorithmes bien documentés, vieille de plusieurs décennies : les routeurs de canaux.
Avant de regarder la solution, la première chose que Dana en a obtenue est une façon correcte de modéliser le problème. L’objectif de notre routeur de liens est double : déterminer le nombre de canaux entre les rangées de nœuds, et attribuer un canal à chaque segment horizontal de liens.
Le début et la fin de chaque ligne horizontale sont simplement déterminés par les nœuds auxquels ils doivent être liés, et les segments verticaux sont de simples projections des nœuds sur les lignes horizontales.
Alors, peut-être que Dana pourrait juste récupérer cette solution ? Plaçons les liens comme les pistes étaient placées sur les circuits imprimés dans les années 80 !
En fait, ce n’est pas vraiment satisfaisant. Ces algorithmes ont été conçus en tenant compte des contraintes de l’industrie des circuits imprimés, où les croisements de liens ne sont généralement pas un problème : seul le fait de rendre le circuit imprimé final aussi petit que possible compte vraiment. Mais quand il s’agit de schémas agréable™, tous ces spaghettis enchevêtrés sont vraiment désastreux. Pour résoudre ce problème, Dana doit fournir au routeur un ordre partiel pour les lignes horizontales : quelque chose indiquant que la ligne A doit être placée au-dessus de la ligne B pour minimiser les croisements.
Les tournois sportifs
Pour trouver un bon ordre vertical, commençons par une idée simple : Pour chaque paire (A,B) de lignes horizontales, on calcule le nombre de croisements si on place A au-dessus de B, de même que B au-dessus de A. On peut en déduire que placer A au-dessus de B économise (ou coûte) un certain nombre de croisements, ou éventuellement que cela ne change rien.
Malheureusement, l’astuce ci-dessus peut aboutir à des contradictions, du style : A doit être placé au-dessus de B, B doit être placé au-dessus de C, et C doit être placé au-dessus de A. Pour obtenir un ordre correct, Dana doit donc sacrifier certaines des contraintes générées, mais d’une manière qui ajoute à nouveau le moins de croisements possibles.
C’est le moment idéal pour, par hasard, discuter de sport. Reformulons le paragraphe précédent, mais en utilisant des termes sportifs à la place. A a gagné contre B, B a gagné contre C, et C a gagné contre A. Pour obtenir un classement correct, Dana doit ignorer certains des résultats des matchs, mais de manière à ignorer le moins de différences de score possible.
Le problème fondamental est le même. Heureusement pour nous, la version sportive est aussi vieille que les championnats (tournois dits toutes rondes), et ce qui est bien avec les vieux problèmes traditionnels, c’est qu’il y a beaucoup de gens intelligents qui ont fait des recherches dessus !
Une façon générique de résoudre le problème est d’utiliser la théorie des graphes, où notre problème sportif serait équivalent au problème de l’ensemble d’arcs de retour minimum. La mauvaise nouvelle : il s’agit d’un problème d’optimisation NP-difficile. En termes simples : trouver la meilleure solution peut prendre un temps considérable, même avec seulement quelques dizaines de joueurs. La bonne nouvelle : il existe une quantité importante d’articles de recherche proposant des heuristiques. Les solutions de ces algorithmes peuvent ne pas être optimales, mais “suffisamment proches” de l’optimum en un temps “raisonnable”. Il existe plusieurs heuristiques qui dépendent du temps de calcul que l’on est prêt à payer pour obtenir des garanties d’optimalité plus fortes, ou qui peuvent être adaptées à des types de graphes spécifiques.
Dana utilise l’heuristique de Eades, P., Lin, X. and Smyth, W.F. (1993), avec des modifications triviales pour les graphes pondérés. Il s’agit d’un algorithme extrêmement rapide et, espérons-le, “pas trop mauvais” pour calculer un ordre partielle (les schémas complets de Pyanodon doivent sortir avant la fin des temps, après tout). C’est suffisant pour obtenir un résultat beaucoup plus convaincant sur le dernier schéma de fabrication :
Conclusion
Donc, pour la version courte : Dana organise une compétition sportive entre les éléments de Factorio. Leurs classements sont ensuite utilisés pour connecter quelques résistances, condensateurs et bobines sur un circuit imprimé imaginaire, avec classe. Cela permet à Dana de générer des schémas de fabrication agréables™ et compréhensibles™.
Faites-moi confiance, je suis ingénieur.
Contribuer
Comme toujours, nous attendons vos contributions pour les Alt-F4, que cela soit par la soumission d’un article ou en aidant pour les traductions. Si vous avez quelque chose d’intéressant en tête que vous souhaitez partager avec la communauté, vous êtes au bon endroit. Si vous n’êtes pas sûr, nous serons heureux de vous aider en discutant structure, contenu et idées. Donc si vous voulez vous impliquer dans les Alt-F4, rejoignez-le Discord pour ne rien rater !