Mis à jour le 11/07/2017
  • 15 heures
  • Facile

Ce cours est visible gratuitement en ligne.

Ce cours est en vidéo.

Vous pouvez obtenir un certificat de réussite à l'issue de ce cours.

J'ai tout compris !

Sortez automatiquement de tous les labyrinthes

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Trouvez un autre moyen pour sortir

Fermons Scratch un instant, et imaginez-vous dans un labyrinthe dont vous ne connaissez pas la sortie. Vous êtes en plein milieu d’un labyrinthe sombre et effrayant, et il vous faut absolument sortir. Maigre consolation, mais consolation quand même : vous savez qu’il existe bien une sortie au labyrinthe, et que vous ne risquez pas de tourner en rond. Comment faites-vous pour sortir ?

Une solution consisterait à vous fier à votre bonne étoile (!) en avançant tout droit, et chaque fois que vous vous retrouvez face à une intersection ou une bifurcation, vous choisissez au hasard le chemin à prendre. Au bout d’un certain nombre de « hasards », vous devriez trouver la sortie…

Qu’est-ce que cela signifie pour votre lutin ?

  • Il va falloir tout d’abord faire en sorte que votre lutin avance indéfiniment, jusqu’à ce qu’il trouve la sortie en tout cas. D’ailleurs, posez tout de suite la condition qui permettra à votre lutin de reconnaître la sortie (si telle couleur est touchée, alors basculer sur l’arrière-plan…)

  • Mais il doit aussi pouvoir reconnaître les murs, et donc gérer les collisions : il faudra donc penser à mettre une condition pour que votre lutin ne traverse pas les murs.

  • Puis, vous pourrez par exemple ajouter une condition, qui permettra à votre lutin de tourner à gauche ou à droite (ou de tourner d’un angle particulier) aléatoirement à chaque fois qu’il se heurte à un mur…

Pas trop difficile ? Un indice peut être : pour ajouter de l'aléatoire à votre programme, vous aurez sûrement besoin d'un nouvel opérateur de Scratch que nous n'avons pas encore utilisé.

Ajoutez un grain d'aléatoire dans votre code...
Ajoutez un grain d'aléatoire dans votre code...

Ce problème n'est pas simple, mais il existe plusieurs solutions possibles. N'hésitez pas à persévérer. Si vraiment vous ne voyez pas par où commencer, voici une proposition que vous pouvez tester. N’hésitez pas à enregistrer localement le lutin et à le réutiliser dans votre labyrinthe.

Voici encore une autre proposition que vous pouvez également essayer.

Trouvez (encore !) un autre moyen pour sortir

Refermons Scratch à nouveau pour nous replonger dans notre labyrinthe mental… Choisir ses chemins de manière aléatoire, ce n’est probablement pas la solution la plus optimale pour sortir du labyrinthe (tout dépend de la taille du labyrinthe, certes).

Une autre solution consisterait par exemple à poser sa main droite sur le mur (qui est donc à notre droite) et de suivre ce mur tout le temps. Bien entendu, on peut aussi poser sa main gauche sur le mur de gauche, le tout étant de ne pas changer de main ni de mur en cours de chemin…

Comme on sait qu’il y a une sortie, et qu’on ne peut pas tourner en rond, on arrivera forcément à la sortie, à un moment donné…

Encore une fois, qu’est-ce que cela signifie pour votre lutin ? Eh bien, il faudra lui ajouter une « main » qui détecte les murs. Une fois sa main posée, il n’a plus qu’à suivre le mur !

Plus facile à dire qu’à faire, vous pouvez visualiser cet algorithme dit "de pledge" sur ce projet scratch.

Et si vous voulez comprendre un peu mieux comment tout ça fonctionne, vous trouverez sur cet article d'Interstices, une explication un peu plus détaillée.

La meilleure solution…

… existe-t-elle ?

 N’oubliez pas que vous pouvez toujours explorer, dans l’arbre des remix, les solutions des autres, mais également publier les vôtres si vous les jugez intéressantes, pour agrandir l’arbre.

Vous avez cherché et testé des algorithmes permettant la sortie automatique de votre personnage : certains algorithmes ont fonctionné dans certains labyrinthes et pas dans d’autres, d'autres pas du tout, d’autres tout le temps peut-être. Parmi ceux qui ont fonctionné, l'un d'entre eux était-il meilleur, ou plus efficace, que tous les autres ? 

En fait, dans certains cas et pour certains problèmes que l’on souhaite résoudre, il n’y a pas une seule “bonne” solution. Il y a des solutions qui arrivent au même résultat, mais qui ne se valent pas toutes : si l’on souhaite par exemple que le lutin sorte de n’importe quel labyrinthe, alors plusieurs algorithmes peuvent être utilisés, il suffit que le lutin sorte ; mais si l’on souhaite qu’il sorte le plus rapidement possible par exemple, ces algorithmes ne seront pas équivalents.

Dans d’autres cas encore, on pourra préférer des solutions approximatives, notamment lorsque les algorithmes de résolution d’un problème mettent trop de temps à résoudre ce problème. 

Passez tout de suite au chapitre suivant pour en savoir plus ! 

Exemple de certificat de réussite
Exemple de certificat de réussite