L'aiguille dans une botte de foin en informatique

La voie lente : tout regarder

Si tu ne sais rien de l'endroit où se trouve l'aiguille, le seul choix est de vérifier chaque brin de foin jusqu'à la trouver. En informatique, on appelle cela une recherche linéaire. En moyenne, tu vérifies la moitié du tout avant de réussir, et dans le pire des cas tout. Cela marche toujours, mais le temps est proportionnel à la taille du tas.

Trier change tout

Imagine maintenant que le foin soit rangé dans l'ordre, comme les mots d'un dictionnaire. Une méthode plus maligne, la recherche dichotomique, ouvre au milieu, décide dans quelle moitié se trouve la réponse et jette l'autre. Recommence, et un million d'éléments se parcourent en une vingtaine d'étapes. Le hic, c'est qu'il faut d'abord que le tas soit en ordre, et une botte de foin ne l'est jamais.

Les index : tricher en se préparant

Les bases de données et les moteurs de recherche contournent le problème en faisant le gros du travail à l'avance. Ils construisent un index, comme la liste au dos d'un livre qui dit à quelle page se trouve un mot. La recherche devient rapide parce que le temps a été dépensé avant. Il n'existe pas d'index pour une vraie botte de foin, et c'est précisément pour cela que l'expression existe.

Suivre un signal

Un détecteur de métaux est différent. Il ne te dit pas où est l'aiguille, mais si tu t'en approches. Imagine un nombre qui augmente quand tu approches. Tu peux alors appliquer une règle simple : faire un pas, voir si le signal a grandi, et continuer dans la direction qui l'améliore. Les programmeurs appellent une version de cela la montée de colline (hill climbing), et elle alimente beaucoup d'optimisations pratiques.

Dans le jeu, le signal est calculé à partir de la distance qui te sépare du morceau de métal le plus proche, par rapport à la portée du détecteur. Les bips s'accélèrent quand ce nombre tend vers 1 : ton oreille fait la montée de colline à ta place. Plus de détails dans Comment fonctionne le détecteur de métaux.

Quand les signaux échouent

La montée de colline peut rester bloquée. Si beaucoup de métal de rebut se trouve près de l'aiguille, le signal le plus fort peut te mener à un clou. Le jeu règle cela en donnant aux détecteurs haut de gamme la capacité de reconnaître l'aiguille. Les recherches réelles rencontrent le même problème et utilisent de meilleurs capteurs ou des filtres supplémentaires.

La botte comme données

La botte de foin du jeu est elle-même une structure de données : une grille de 88 sur 40 sur 88 cellules, chacune contenant un nombre pour la densité du foin. Creuser, c'est changer des nombres, et des chunks de 16 cellules limitent le travail. Le fonctionnement est détaillé dans Comment fonctionne la botte de foin.