{"id":10475,"date":"2019-12-12T15:18:50","date_gmt":"2019-12-12T14:18:50","guid":{"rendered":"https:\/\/www.triforce-legend.com\/v6\/?p=10475"},"modified":"2019-12-12T15:18:22","modified_gmt":"2019-12-12T14:18:22","slug":"mathematica-hyrulea-1","status":"publish","type":"post","link":"https:\/\/www.triforce-legend.com\/v6\/mathematica-hyrulea-1\/","title":{"rendered":"Mathematica Hyrulea – Tome 1"},"content":{"rendered":"

B<\/strong>onjour et bienvenue dans Mathematica Hyrulea<\/strong>.<\/p>\n

Vous avez peut-\u00eatre eu la chance de tester les donjons d’Igor<\/strong> dans le tout nouveau Link’s Awakening<\/strong>. Dans ce mode, Igor nous fournit un ensemble donn\u00e9 de salles \u00e0 assembler pour faire un donjon. Mais vous \u00eates vous d\u00e9j\u00e0 demand\u00e9 combien de salles diff\u00e9rentes vous pourriez cr\u00e9er<\/em>, si vous en aviez le temps et les outils ? C’est ce que l’on va tenter de compter aujourd’hui.<\/p>\n

 <\/h3>\n

I. Un peu de d\u00e9nombrement :<\/h3>\n

Dans Link\u2019s Awakening, les salles<\/strong> sont des rectangles <\/strong>de 8×6 cases<\/strong>. En simplifiant \u00e0 l\u2019extr\u00eame on pourrait dire que chaque case est soit un mur soit une case traversable. Dans les faits, il y a d\u2019autres possibilit\u00e9s comme des vases, des torches, des trous, des tapis roulants, des coffres et j\u2019en passe. Mais on va simplifier les calculs en se limitant \u00e0 ces deux objets<\/strong> : mur<\/strong> et sol<\/strong>. Croyez moi, \u00e7a fait d\u00e9j\u00e0 beaucoup.<\/p>\n

Faisons donc le calcul, il y a 8*6 = 48 cases<\/strong>. Chacune de ces cases peut \u00eatre dans deux \u00e9tats diff\u00e9rents : mur ou sol. Ce qui devrait donner 248<\/sup> salles diff\u00e9rentes<\/strong>. 248<\/sup> c\u2019est 2*2*2*…*2 avec 48 fois le nombre 2. Comment on sait \u00e7a ? C\u2019est assez simple, laissez-moi vous montrer cet arbre. Quand on a une seule case, il n\u2019y a que deux possibilit\u00e9s, on rajoute une deuxi\u00e8me case et cela multiplie par deux les possibilit\u00e9s, puis on en rajoute une troisi\u00e8me et on multiplie par deux de nouveau. Et ainsi de suite jusqu’\u00e0 obtenir 248<\/sup>.<\/p>\n

<\/p>\n

On pourrait croire que 248<\/sup> est un petit nombre vu comme \u00e7a. Il ne prend que 3 chiffres \u00e0 \u00e9crire. Et pourtant c\u2019est un nombre un peu plus grand que 280 000 milliards. M\u00eame si vous parcourez chacune de ces salles en 10 secondes, il vous faudra 90 millions d\u2019ann\u00e9es pour visiter toutes les salles possibles. Il y aurait assez pour remplir 9 milliards de Link\u2019s Awakening diff\u00e9rents.<\/p>\n

CEPENDANT, parmi les milliards de salles<\/strong> que l\u2019on a d\u00e9nombr\u00e9e, il en existe un grand nombre<\/strong> qui sont injouables<\/strong>. Des salles qui ne ressemblent \u00e0 rien ou n\u2019ont aucun int\u00e9r\u00eat ludique. Des salles qui n\u2019auraient pas leur place dans un jeu Zelda. Ni m\u00eame dans un jeu tout court, en fait.<\/p>\n

<\/p>\n

 <\/p>\n

II. Affinons le calcul :<\/h3>\n

On va tenter d\u2019am\u00e9liorer notre d\u00e9nombrement. On aimerait donc compter uniquement<\/strong> les salles<\/strong> qui sont traversables<\/strong>. C’est-\u00e0-dire les salles o\u00f9 toutes les entr\u00e9es sont connect\u00e9es entre elles.<\/p>\n

Pour calculer \u00e7a, il n\u2019existe pas de formules math\u00e9matiques. On va donc \u00e9crire un programme<\/strong> qui va tester toutes les possibilit\u00e9s<\/strong>. Malheureusement, ce n\u2019est pas aussi simple que \u00e7a en a l\u2019air.<\/p>\n

 <\/p>\n

Le premier r\u00e9flexe serait de faire un programme qui regarde chaque salle une par une<\/strong> et v\u00e9rifie qu\u2019elle est traversable. Le probl\u00e8me c\u2019est que c’est beaucoup trop long<\/strong>. L\u2019ordinateur est extr\u00eamement rapide mais pas assez. Imaginons qu\u2019il puisse v\u00e9rifier 100 000 salles par secondes, il lui faudrait tout de m\u00eame 9000 ans pour finir son calcul. Et je n\u2019ai pas sp\u00e9cialement envie d\u2019attendre 9 mill\u00e9naires pour publier cet article. Il faut donc trouver une autre solution<\/strong>.<\/p>\n

 <\/p>\n

La solution que j\u2019ai choisie prend le probl\u00e8me dans l\u2019autre sens. Puisque je veux pouvoir traverser la salle, je compte d\u2019abord tous les chemins possibles<\/strong> qui passent par toutes les entr\u00e9es. Je trace donc tous ces chemins, et pour chacun, je compte les cases qu\u2019il traverse. Supposons qu\u2019un chemin fasse 18 cases. Il reste alors 48-18=30 cases libres que l’on peut remplir comme on le souhaite. Ce qui fait donc 230<\/sup> salles qui ont ce chemin. On sait avec certitude que ces 230<\/sup> salles sont bien jouables car on a un chemin garanti entre toutes les entr\u00e9es.<\/p>\n

 <\/p>\n

Gr\u00e2ce \u00e0 ce programme bien plus rapide, on peut calculer le r\u00e9sultat en temps raisonnable. Par exemple, combien existe-t-il de salles qui ont une entr\u00e9e \u00e0 gauche et une entr\u00e9e en haut, \u00e0 votre avis<\/em> ?<\/p>\n

Il y en a 7 752 713 218 476. Soit pr\u00e8s de 8000 milliards. Et on ne parle ici que des salles avec deux entr\u00e9es perpendiculaires<\/strong>. Il faudrait compter les salles aux entr\u00e9es face \u00e0 face, et celles avec 1, 3 ou 4 entr\u00e9es.
\nSi j’ai choisi les salles avec deux entr\u00e9es, c’est que ce sont les plus nombreuses.<\/p>\n

 <\/p>\n

III. Conclusion :<\/h3>\n

Si jamais un Zelda Maker<\/strong> sort un jour, vous pouvez \u00eatre s\u00fbr qu\u2019on ne sera jamais \u00e0 court de jeux \u00e0 jouer. Imaginez vous bien qu\u2019ici, nous avons simplifi\u00e9 le probl\u00e8me \u00e0 l’extr\u00eame. Ajoutez les diff\u00e9rentes cases, des salles de donjons plus grandes, des monstres, des objets du donjon, vous obtiendrez tr\u00e8s vite un nombre \u00e9norme de possibilit\u00e9s<\/strong>. Il faut aussi consid\u00e9rer le fait qu’un donjon est constitu\u00e9 d’une vingtaine de salles. On peut donc, en th\u00e9orie, concevoir bien plus de donjon de LA qu’il n’y a d\u2019atomes dans l\u2019univers. C\u2019est vous dire si on peut en faire beaucoup !<\/p>\n","protected":false},"excerpt":{"rendered":"

Bonjour et bienvenue dans Mathematica Hyrulea. Vous avez peut-\u00eatre eu la chance de tester les donjons d’Igor dans le tout nouveau Link’s Awakening. Dans ce mode, Igor nous fournit un ensemble donn\u00e9 de salles \u00e0 assembler pour faire un donjon. Mais vous \u00eates vous d\u00e9j\u00e0 demand\u00e9 combien de salles diff\u00e9rentes vous pourriez cr\u00e9er, si vous […]<\/p>\n","protected":false},"author":32,"featured_media":10632,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0,"footnotes":""},"categories":[45],"tags":[269,272,270,196],"class_list":["post-10475","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-articles","tag-calculs","tag-mathematica-myrulea","tag-mathematiques","tag-zelda"],"_links":{"self":[{"href":"https:\/\/www.triforce-legend.com\/v6\/wp-json\/wp\/v2\/posts\/10475","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.triforce-legend.com\/v6\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.triforce-legend.com\/v6\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.triforce-legend.com\/v6\/wp-json\/wp\/v2\/users\/32"}],"replies":[{"embeddable":true,"href":"https:\/\/www.triforce-legend.com\/v6\/wp-json\/wp\/v2\/comments?post=10475"}],"version-history":[{"count":0,"href":"https:\/\/www.triforce-legend.com\/v6\/wp-json\/wp\/v2\/posts\/10475\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.triforce-legend.com\/v6\/wp-json\/wp\/v2\/media\/10632"}],"wp:attachment":[{"href":"https:\/\/www.triforce-legend.com\/v6\/wp-json\/wp\/v2\/media?parent=10475"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.triforce-legend.com\/v6\/wp-json\/wp\/v2\/categories?post=10475"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.triforce-legend.com\/v6\/wp-json\/wp\/v2\/tags?post=10475"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}