[Tutoriel] Guide Mapmaking - Boucles et récursivité

Cet article fait partie d’une série servant à enseigner l’art du développement sur Minecraft. Vous pourrez retrouver l’introduction et le sommaire en cliquant ici.

Jeunes padawan, vous êtes sur la dernière ligne droite avant de devenir un vrai Jedi des commandes Minecraft ! Il vous reste encore 2 ou 3 petites notions à découvrir. L’une d’entre elles était utilisée jusqu’ici sans même que l’on s’en rende compte : les boucles.

Comme vous le savez, un programme se présente comme une recette de cuisine… mais pour l’ordinateur… et ça ne fait pas de bons petits plats malheureusement. Mais une simple liste d’instructions, c’est tout de même assez limité si l’on veut faire un programme qui dure dans le temps ou qui manipule un nombre indéfini d’éléments. Vous allez répondre qu’il suffit de mettre le command-block en “repeat” pour faire durer le système dans le temps et vous auriez raison. Cependant, cette option utilise quelque chose que nous ne maîtrisons pas encore. En effet, en l’activant, vous placez votre command-block dans la boucle lente de Minecraft, qu’on assimile directement aux ticks. 1 tick représente un tour de boucle. Le nombre de boucles par seconde est alors appelé “fréquence d’actualisation” ou encore “tickrate”.

Notion de temps en jeu

Concrètement c’est quoi le tickrate ? Il s’agit du nombre de fois par seconde que le jeu va calculer les différents éléments qui le constituent (position des objets, animations, actions, sons etc…). Il ne peut en effet pas calculer les choses de façon continue car cela demanderait une capacité de calcul infini. C’est pour cela qu’un jeu découpe le temps en une succession d’instants. En générale, les jeux tournent autour de 30 TPS (“Tick Per Second”, ce qui est différent des FPS ou “Frame Per Second” qui, grâce à certaines astuces, peut aller bien au delà). Les jeux compétitifs peuvent même atteindre 60 TPS. Minecraft quand à lui à un tickrate très bas: seulement 20 TPS.

Il s’agit de la boucle lente principale de Minecraft, qu’on utilisait jusqu’ici sans vraiment sans y prêter attention. Mais au fait, c’est quoi un boucle lente et une boucle rapide ? A vrai dire, peu de gens font la différence, mais il s’agit de l’unité servant à la répétition de la boucle. Pour faire simple, une boucle lente est une boucle utilisant une unité de temps (ex: la boucle s’exécutera toutes les X secondes). Une boucle rapide, quand à elle, est une boucle se basant sur un nombre d’instructions (ex: la boucle s’exécutera à chaque fois que toutes les instructions qu’elle contient ont été exécutées). Généralement, on utilise des boucles rapides pour manipuler des éléments (exemple: trouver un élément précis dans une grande liste). La boucle lente quand à elle est utilisée pour faire durer un programme dans le temps (autrement, il s’arrêterait juste après avoir été lancé).

Dans Minecraft, les boucles lentes utilisent toutes le tickrate du jeu car c’est la plus petite unité de temps que nous ayons à disposition (et presque la seule vu qu’un 1 redstone tick, l’autre unité de temps dont on dispose, est égale à 2 game ticks).

Boucles

Bon, c’est bien joli cette histoire de ticks, mais rentrons un peu plus du côté pratique et voyons comment utiliser les boucles !

Pour créer une boucle lente, rien de plus simple dans Minecraft, il suffit de poser un command-block en repeat et de l’alimenter ! La command qui sera dedans s’exécutera… en boucle. Mais si on veut lui mettre une limite, comment on fait ? Et bien il faut mettre ce qu’on appelle une “condition de point d’arrêt” (ou “condition de boucle”, qui est un nom plus approprié même si moins utilisé). Si la condition est remplie, la boucle s’exécute, sinon, elle s’arrête.

C’est là où les command-blocks diffèrent vraiment d’un langage de script conventionnel : ne disposant pas de quoi faire une boucle avec des commandes, ils faut utiliser celle du jeu. Mais ne pouvant arrêter la boucle du jeu, la condition d’arrêt ne doit pas se faire sur la boucle elle-même mais sur chacune des instructions qu’elle contient. Autrement dit, vous devrez faire en sorte que chacune des commandes que vous mettez dans la boucle ne s’exécutent que si une condition est remplie (appelée “condition d’exécution”). Par exemple, si vous souhaitez faire une boucle qui ne s’exécute que pendant 1 seconde, vous devrez définir un score qui va prendre une certaine valeur au début de la boucle (cette instruction est appelée “initialisation”), par exemple: 0. Ensuite, ce score va évoluer a chaque fois que la boucle va faire un tour, par exemple, on va lui ajouter 1 a chaque fois (cette instruction est appelée “continuité”). Enfin, chaque commande devra s’exécuter que si notre score correspond à un certain intervalle, par exemple 0 à 20 (la fameuse condition de point d’arrêt).

Prenons un exemple concret car je vous sens un peu perplexe :

scoreboard players add Boblennon Burn 0

execute as @e at @s if entity @a[name=Boblennon,scores={Burn=0..20}] run setblock ~ ~ ~ fire replace air

scoreboard players add Boblennon Burn 1

Dans l’ordre, on à l’initialisation (on voit au passage une petite astuce permettant d’initialiser un score sans modifier sa valeur. Si on ne le fait pas, le score sera indéterminé et la condition sur la commande suivante ne sera pas remplie). Ensuite, on a la commande qu’on souhaite exécuter, ici, mettre le feu un peu partout pendant la première seconde où Boblennon se manifeste. D’où la condition de point d’arrêt qui est: le score Burn de Boblennon doit être compris entre 0 et 20. Enfin, la condition de continuité, permettant d’atteindre le point d’arrêt. Ici on ajoute 1 pour avoir une boucle qui durera 1 seconde (20 ticks).

Cette petite précision sur les boucles lentes, cumulé à votre expérience « intuitive » de ces boucles est suffisant pour commencer à faire de belles choses. Pas la peine donc de développer plus que ça sur ce sujet.

Oh, si, j’oubliais, vous pouvez faire des boucles DANS d’autres boucles ;)

Récursivité

On attaque désormais les boucles rapides. Encore une fois, dans Minecraft, pas question d’utiliser des instructions comme “for” ou encore “while” pour créer ces boucles. Ici, nous allons utiliser une propriété que possèdent les fonctions, à savoir, s’appeler elle même !

Prenons un exemple : vous cherchez une valeur dans un intervalle donné. Cette valeur est inconnue et vous voulez la trouver très rapidement. Si vous avez bien suivi le guide, vous reconnaissez là un cas où la dichotomie va être de mise. Pour l’appliquer, on pourrait placer les instructions les unes à la suite des autres dans un même fichier. Mais cela implique 2 problèmes:

Les instructions s’exécuteront même une fois la valeur trouvée, ce qui n’est pas génial niveau optimisation.
Si l’intervalle donné peut être différent à chaque exécution de la fonction, vous devrez prévoir suffisamment d’instructions pour considérer le plus grand intervalle possible, ça non plus, ce n’est pas génial pour l’optimisation.

Pour pallier à ces problèmes, il faut passer par un système plus dynamique. Imaginons par exemple que vous votre fonction ne contient que 2 instructions : une permettant de faire un et un seul test et l’autre permettant de relancer la fonction si ce test n’est pas concluant. À ce moment là, on a une fonction qui, lorsqu’elle trouvera notre valeur inconnue, s’arrêtera directement après. De plus, si le premier test dépend de la taille de l’intervalle, alors votre fonction serait parfaite pour résoudre votre problème.

Tout ça c’est bien beau, mais un peu théorique. En pratique ça donnerait quoi ?

Prenons un cas complexe : imaginons que vous souhaitez faire déplacer une entité à une vitesse correspondant à un score. Ce score peut alors prendre beaucoup de valeurs ! Difficile de traiter chaque possibilité… et pourtant ! En créant 2 fonctions récursives, vous pourrez faire des miracles:

Une fonction permettant de diviser ce score par 2 temps que le score est hors d’un certain intervalle (intervalle qui sera utilisé pour la dichotomie). À chaque division par 2, vous multipliez par 2 un score qui servira de compteur (initialement placé à 1)
Une fonction qui va faire une dichotomie sur un petit intervalle, prenons par exemple de 0 à 10. Vous aurez alors à gérer dans ce fichier les vitesses 0 à 10 seulement ! Une petite particularité vient s’ajouter à cette dichotomie: la fonction s’appellera elle même temps que le score de compteur n’est pas à 0. La fonction décrémente ainsi ce score à chaque fois qu’elle est exécutée.

Ainsi, si le score de vitesse était à 100, la première fonction aura pour conséquence de s’exécuter un première fois pour mettre votre score à 50 et le compteur à 2, une deuxième fois pour mettre le score à 25 et mettre le compteur à 4 (attention, 4 et non 3, ici, on multiplie par 2 car on divise notre premier nombre par deux à chaque fois. Pour le retrouver, il faut bien savoir quelle fraction représente notre nombre « réduit » par rapport au nombre qu’on avait en entrée, ici, 100/25 = 4). La fonction s’exécute alors une 3ème fois pour placer le score à 12 et le compteur à 8, puis une dernière fois pour placer le score à 6 et le compteur à 16.

De là, la deuxième fonction va pouvoir s’exécuter sur son intervalle de 0 à 10 en ayant en entrée un score de 6 et un autre score, représentant le nombre de fois où elle devra s’exécuter avec cette valeur : ici, 16 fois. Ainsi, 16 fois un déplacement de, disons 6 blocs, revient à un déplacement de 96 blocs !

On ne retrouve pas parfaitement le nombre pris en entrée à cause aux divisions du jeu qui ne conservent que les nombres entiers. Ainsi, on a perdu de la précision lors de la division par 2 du nombre impair 25. Il est cependant possible de compenser cette perte de précision en faisant une opération « modulo » entre le score en entrée (ici, 100), et le score compteur (ici, 16) , ce qui nous donnerait ici 4 ! (la différence entre 100 et 96). Il suffit alors de ré-exécuter la deuxième boucle une dernière fois avec cette valeur (qui, mathématiquement, ne peut être que compris entre 0 et 10) pour retrouver parfaitement le nombre en entrée.

Enfin, si vous vous souvenez du cours sur la dichotomie, vous vous rappelez que la dichotomie devient extrêmement efficace lorsqu’il s’agit de rechercher dans des grands intervalles. Ici, on peut donc faire un compromis en mettant une dichotomie de 1000 (ou plutôt 1024 car c’est le nombre le plus proche de 1000 qui sera toujours divisible par 2 sans jamais obtenir les valeurs impaires qui nous embête). De là, vous pourrez avoir un score en entré qui soit potentiellement infini, il sera de toute façon découpé par tranches de 1000.