Les B-arbres dans Factorio

Apprendre les B-arbres

• Arbres de recherche binaires (Binary Search Trees, BST) : chaque nœud possède une clé ; les nœuds de gauche ont des valeurs de clé plus faibles et les nœuds de droite des valeurs plus élevées.

• Les BST ne fonctionnent que lorsque les clés peuvent être triées, et leur équilibre se dégrade si des valeurs ne sont ajoutées que d’un seul côté, ce qui réduit leur efficacité.

• Un BST déséquilibré peut être corrigé par pivotement, mais cela convient mal au stockage sur disque (rééquilibrages fréquents et possibilité que des nœuds adjacents soient stockés sur des pages différentes).

• B-arbres (B-Trees) : ils sont composés de nœuds contenant plus de clés et de pointeurs qu’un arbre binaire.

• Chaque nœud contient plusieurs clés et plusieurs pointeurs associés à ces clés (par exemple, un nœud avec les clés 17 et 24 possède des pointeurs vers des nœuds contenant des clés inférieures à 17, comprises entre 17 et 24, et supérieures à 24).

Implémentation des B-arbres dans Factorio

• Implémentation simple d’un arbre de recherche binaire dans Factorio (jeu de construction d’usines) : chaque nœud est constitué d’un coffre en bois (clé) et de deux chemins (pointeurs).
• Comme il n’existe pas de moyen de comparer la valeur des matériaux, un ordre arbitraire leur est attribué, puis la comparaison est effectuée avec des bras filtrants.
• L’implémentation d’un B-arbre est plus complexe : chaque nœud possède trois clés et des pointeurs vers quatre nœuds enfants.
• Le B-arbre peut stocker davantage d’informations et, au lieu de trier manuellement les objets, l’arbre est laissé vide jusqu’à ce qu’une meilleure méthode de représentation soit trouvée plus tard.

L’avis de GN⁺

• Le point le plus important de cet article est de comprendre le concept des B-arbres et l’approche créative consistant à les implémenter dans le jeu Factorio.
• Ce que les lecteurs trouveront intéressant, c’est la possibilité de comprendre de manière visuelle et intuitive des structures de données complexes de l’informatique à travers un jeu.
• Cette approche rend l’apprentissage plus amusant et plus captivant, et propose une nouvelle manière d’explorer les concepts fondamentaux du génie logiciel à travers un média non traditionnel comme le jeu.

[GN⁺]

Commentaires Hacker News

• La conception du jeu Factorio ne reflète pas parfaitement la théorie de l’informatique et privilégie le plaisir de jeu plutôt qu’un style de jeu théoriquement optimal.
• Dans Factorio, les arbres binaires auto-équilibrés (arbres 2-3, arbres rouge-noir, B-arbres) ne peuvent pas être réorganisés, ce qui supprime leur fonctionnalité la plus importante : l’auto-équilibrage.
• Du point de vue de l’optimisation, les bras robotisés de Factorio sont plus lents que les tapis roulants : quatre bras robotisés peuvent traiter 12 objets par seconde sur un tapis, tandis qu’un tapis bleu peut en transporter 45 par seconde. Pour une conception optimale reposant uniquement sur les tapis, il est donc recommandé d’utiliser des répartiteurs.
• La combinaison de l’informatique et des répartiteurs inclut le concept de réseau de Benes (un réseau composé uniquement de crossbars 2 entrées / 2 sorties), qu’il faut étudier pour concevoir des usines efficaces.
• La conception de tapis mixtes est importante dans Factorio, et lire un livre sur les structures internes des bases de données peut être utile.
• Les arbres de recherche binaires (BST) ne sont pas adaptés au stockage sur disque, et la recherche dans les nœuds d’un B-arbre est plus rapide que le parcours de pointeurs d’un arbre binaire. La complexité d’implémentation augmente, mais sauf si l’on utilise le langage C, il est rare d’avoir à implémenter soi-même une map basée sur des arbres.
• Il est souligné que l’absence de majuscules peut nuire à la lisibilité du texte.
• Le partage de contenus liés à Factorio ravive l’envie d’y consacrer à nouveau des centaines d’heures.
• Tout peut être réalisé uniquement avec des répartiteurs, sans avoir besoin de coffres ni de bras robotisés à filtre.
• Quelqu’un fait remarquer qu’il s’attendait à une implémentation utilisant les circuits de Factorio, mais que ce n’est pas le cas.