Stratégies algorithmiques avancées pour Scratch

Pour résoudre un problème, il est nécessaire de savoir choisir, et parfois combiner, les bonnes boucles et/ou structures conditionnelles.

Résolution par boucle

Le problème à résoudre nécessite :

• de répéter des instructions un nombre de fois connu à l’avance → utilisation d’une boucle « répéter n fois » ;
• de répéter des instructions sans jamais s’arrêter → utilisation d’une boucle « répéter indéfiniment ».

Résolution par structure conditionnelle

Le problème à résoudre nécessite :

• que des instructions soient exécutées uniquement dans un certain cas → utilisation d’une structure conditionnelle « si … alors » ;
• que des instructions soient exécutées dans un certain cas, et que d’autres instructions soient exécutées dans les autres cas → utilisation d’une structure conditionnelle « si … alors … sinon » ;
• que des instructions différentes soient exécutées, en fonction de la situation → utilisation de plusieurs structures conditionnelles « si … alors » et/ou « si … alors … sinon », imbriquées les unes dans les autres.

Autre bloc

Pour mettre un algorithme en pause jusqu’à ce qu’un événement particulier se produise → utilisation d’un bloc « attendre jusqu’à ce que ».

Illustration

On veut créer un programme dans lequel le lutin dit « 1, 2, 3, Soleil ! ». On a besoin :

• de répéter des instructions sans jamais s’arrêter (boucle « répéter indé  finiment ») ;
• que le lutin affiche un nombre (1,2,3) qui augmente de 1 tant que ce nombre est plus petit que 4. Sinon, le lutin écrit « Soleil » puis le nombre revient à 1 → utilisation d’une structure conditionnelle « si … alors … sinon ».

Ainsi, la solution peut donner :

Stylo et formes géométriques

L’utilisation des bonnes boucles dans un programme utilisant le stylo permet de faire dessiner au lutin des formes géométriques régulières. Par exemple, si l’on veut faire dessiner un triangle isocèle au lutin, on pourra partir des propriétés géométriques d’un tel triangle, qui disent que :

• ses trois angles mesurent 60° ;
• ses côtés sont de même mesure.

Ainsi, pour dessiner un triangle isocèle de côté 150, il faudra :

• faire se déplacer le lutin trois fois de suite avec un boucle « répéter 3 fois » ;
• faire avancer le lutin de 150 à chaque tour de boucle ;
• faire tourner le lutin de 60° après chaque déplacement.

Illustrations

Voici un programme comportant trois algorithmes : 

• celui en haut à gauche sert à effacer les éventuels dessins faits au stylo dans la scène. L’algorithme se déclenche dès qu’on appuie sur la touche « a » ;
• celui de droite permet de faire dessiner un triangle isocèle vert en déplaçant trois fois de suite le lutin. L’algorithme se déclenche dès qu’on appuie sur la touche « e » ;
• le dernier permet de faire dessiner un hexagone orange en déplaçant six fois de suite le lutin. À chaque déplacement, un dessin du lutin est réalisé. L’algorithme se déclenche dès qu’on appuie sur la touche « z ». 

Si on appuie d’abord sur « a », puis sur « z », puis sur « e », on obtient : 

Scratch offre la possibilité de créer ses propres blocs, en allant dans la catégorie Mes Blocs. Le comportement de chaque bloc personnalisé sera décrit par un algorithme, constitué de plusieurs blocs, qui seront exécutés quand on placera le bloc personnalisé dans un programme.

Créer un bloc personnalisé

Chaque bloc personnalisé débute par un bloc « définir », suivi d’une série d’autres blocs nécessaires pour construire son algorithme. Voici par exemple un bloc personnalisé servant à faire sauter le lutin :

Une fois un bloc personnalisé défini, il peut être placé à l’intérieur des programmes, comme tous les autres blocs de Scratch. Voici par exemple un programme qui se déclenche lorsque l’utilisateur appuie sur le drapeau vert, et qui permet d’utiliser le bloc personnalisé « sauter » créé précédemment :

Emplacements

Dans le bloc « définir » du bloc personnalité, il est possible d’intégrer des emplacements servant à paramétrer les blocs personnalisés.

Emplacements arrondis

L’emplacement aux bords arrondis permet de transmettre une valeur numérique au bloc personnalisé, qui pourra être utilisée en tant que variable dans son algorithme. Voici un exemple où deux emplacements arrondis servent à choisir la   longueur et la hauteur du saut :

Emplacements hexagonaux 

L’emplacement hexagonal permet de transmettre une condition au bloc personnalisé, qui pourra être utilisé en tant que condition dans son algorithme. Voici un exemple où un emplacement hexagonal sert à indiquer quand le lutin peut sauter : 

Il est possible de faire exécuter à Scratch plusieurs algorithmes en même temps : on parle d’exécution parallèle.

Avec un seul Sprite (lutin)

Plusieurs algorithmes peuvent se dérouler en même temps. Pour cela, il suffit que chaque algorithme soit suffisamment long à exécuter. C’est le cas si ils contiennent des blocs « attendre » par exemple. Il est même fréquent de créer un algorithme qui ne se termine jamais, avec une boucle « répéter indéfiniment ».

Une fois la condition de déclenchement de chaque algorithme validée, les algorithmes s’exécutent en parallèle.

Voici un exemple de deux algorithmes exécutés en parallèle dès qu’on appuie sur les touches « a » et « z » :

• le premier fait se déplacer le Sprite ;
• le second fait parler le Sprite si il est touché par la  souris.

Plusieurs Sprites (lutin)

Il est aussi possible d’avoir plusieurs Sprites dans un même programme. Chaque Sprite possède alors ses propres algorithmes. En déclenchant leurs algorithmes en parallèle, il sera alors possible de créer des interactions entre les Sprites : les actions de l’un pourront avoir un impact sur l’autre. C’est très utile pour créer des jeux !

Voici un exemple avec deux Sprites (un chat et un ballon de basket) dans un programme. Trois algorithmes sont exécutés en parallèle dès qu’on clique sur le drapeau vert :

• pour le Sprite du ballon de basket, son algorithme le fait se déplacer aléatoirement ;
• pour le Sprite du chat, un de ses algorithmes lui permet de se déplacer aléatoirement, et l’autre lui   fait dire « Aie ! Lorsque le ballon de basket le touche.

Stratégie de résolution de problème complexe

Découpage en sous-problèmes

En algorithmique, lorsque le problème à résoudre est complexe, il est préférable de le découper en plusieurs sous-problèmes plus simples.

Résolution des sous-problèmes

Une fois la découpe choisie, chaque sous-problème pourra être résolu par son propre sous-algorithme. Un bloc personnalisé peut alors être créé pour contenir chaque sous-algorithme.

Regroupement des sous-solutions

Enfin, les sous-algorithmes peuvent être regroupés, pour résoudre le problème de départ.

Illustration

On souhaite réaliser un programme de jeu : le joueur doit faire traverser la scène au chat, de gauche à droite, tout en évitant un ballon de basket. Si le chat est touché, il retourne tout à gauche. Si le chat atteint la droite de l’écran, le joueur à gagné.

Créer le jeu est un problème complexe. À la place d’essayer de créer un seul grand algorithme, on va le décomposer en 5 sous-problème :

• déplacer le chat ;
• déplacer le ballon de basket ;
• faire sauter le chat ;
• gérer quand le ballon de basket touche le chat ;
• gérer la victoire du joueur.

Chaque sous-problème sera traité par un sous-algorithme, qu’on peut éventuellement mettre dans un bloc personnalisé.

Le résultat sera, pour le Sprite (lutin) du chat, 4 blocs personnalisés qui seront ensuite placés dans une boucle « répéter indéfiniment » :

On aurait aussi un algorithme plus simple pour le ballon de basket :