Exood4 Studio - Video Game Development, Toulouse (France)
Exood4 Studios Exood4 Tutorials

   
A l g o r i t h m e s

M t h o d o l o g i e   d e   l a   p r o g r a m m a t i o n




 L'activit de l'informaticien est l'criture de la programmation sur un ordinateur. Un ordinateur est un acteur capable d'enchaner des actions par rapport un modle donn (programme). Plus gnralement, le problme de la programmation est de dcrire le comportement d'un acteur. C'est ce que l'on appelle un algorithme (description du comportement face une situation donne).

Exemple :
Le joueur (acteur) entre dans une pice (situation)
La crature (acteur) attaque le joueur (situation)
 L'criture d'algorithmes requiert la connaissance de l'acteur et la dfinition d'un langage algorithmique.



L'Acteur


 Il est ncessaire de connatre :
  • les objets manipuls, par exemple pour l'acteur joueur nous pouvons imaginer : armes, cls, munitions ...
  • l'tat de ces objets : l'arme est elle charge ? combien de munitions ? ...
  • les actions lmentaires (ce que sait faire l'acteur) : se dplacer, utiliser une cl, charger une arme, tirer ...


Langage Algorithmique


 Un langage est dfinit par sa syntaxe (forme de la grammaire qui traite de l'arrangement des mots) et sa smantique (forme de la grammaire qui traite de la signification des mots).

 Le langage algorithmique permet de dfinir des schmas d'ordonnancement des actions. Il existe trois schmas (appels aussi structures de contrle) :
  • squence
  • slection (ou choix)
  • rptition
 En pratique, l'algorithme s'crit au moyen des actions de l'acteur et des trois structures de contrle.


Expression des actions lmentaires de l'acteur


 La syntaxe d'une action lmentaire est la suivante : VERBE + COMPLEMENT (ex: recharger l'arme, utiliser la cl ...)


Expression des conditions


 Il existe deux formes de condition :
  • Condition simple (une seule interrogation)
  • Condition compose (plusieurs interrogations) qui s'crit en utilisant les oprateurs : NON (ngation), ET (et logique), OU (ou logique)
Exemple :
condition simple : arme charge ? porte ouverte ?
condition compose : NON porte verrouille, (arme charge) OU (il reste des munitions), (NON arme charge) ET (plus de munitions)
Remarque : on peut combiner les oprateurs NON, ET, OU, mais attention au problme de lisibilit des algorithmes.


Structures de contrle


1) La squence

 Une squence est une suite conditionnelle d'actions. Sa syntaxe est la suivante :

action 1;
action 2;
...
action i; o action i est une action lmentaire de l'acteur
...
action n;

 Le symbole ';' est un lment de la syntaxe qui reprsente un terminateur d'action. Intuitivement nous comprendrons que l'action i se droule aprs l'action i-1 et avant l'action i+1. Parfois, l'ordre des actions peut s'avrer important :

Exemple : le joueur

 Ramasser les munitions;
 Charger l'arme;
 Tirer;


2) La slection

 Une action est ralise en fonction de la valeur d'une condition. Sa syntaxe est la suivante :

SI condition ALORS
 action 1;
SINON o action 1 et 2 sont des actions de l'acteur
 action 2;
FIN SI;

 Deux cas peuvent se prsenter :
- Si la condition est vrifie (valeur de condition = VRAI), l'action 1 est ralise mais pas l'action 2
- Si la condition n'est pas vrifie (valeur condition = FAUX), l'action 2 est ralise mais pas l'action 1
Exemple :

SI l'arme est charge ALORS
 tirer sur l'ennemi;
SINON
 fuir;
FIN SI;

 Nous avons un cas particulier pour lequel il peut ne pas y avoir d'action 2, il s'agit alors d'une slection rduite. Si la condition est vrifie, l'action est excute, sinon il ne se passe rien.

SI condition ALORS
 action;
FIN SI;


3) La rptition

 Une action est rpte tant qu'une condition reste vrifie :

TANT QUE condition FAIRE
 action;
FIN TANT QUE;


 Le droulement de la rptition est le suivant :
  1. valuation de la valeur de la condition
  2. Si la condition est vrifie, excution de l'action (sinon, la rptition est termine)
  3. Aprs l'excution de l'action, retour l'valuation de la condition (retour en 1)
Exemple :

TANT QUE il reste des munitions FAIRE
 Tirer sur l'ennemi;
FIN TANT QUE;

 Le nombre de munitions tant connu priori, la boucle se termine car l'action (tirer sur l'ennemi) diminue de 1 le nombre de munitions. Attention si l'arme est dfectueuse, la rptition est infinie (l'action tirer sur l'ennemi n'influence plus la valeur de la condition). Avec une rptition, l'action peut tre excute : 0 fois, 1 fois, n fois ou l'infini. Pour s'assurer que la rptition n'est pas infinie, il faut que l'action modifie la valeur de la condition.



Composition d'actions


 Nous avons vu jusqu' prsent qu'une action = une action lmentaire. Maintenant nous allons voir qu'une action peut correspondre une action compose (squence, slection et rptition) :

SI condition ALORS
 Action 1; (action compose)
SINON
 Action 2; (action compose)
FIN SI;

Ce qui peut s'crire sous une forme plus dtaille :

SI condition ALORS
 Action 1.1;
 Action 1.2;
SINON
 TANT QUE condition 1 FAIRE
 SI condition 2 ALORS
 Action 2.1;
 FIN SI;
 Action 2.2;
 FIN TANT QUE;
FIN SI;

Exemple :

Acteur joueur

 SI il y a un objet prendre ALORS
 Prendre l'objet; (action compose)
 FIN SI;

On remplace "prendre l'objet" par :

 TANT QUE l'objet est trop loin FAIRE
 Avancer vers l'objet;
 FIN TANT QUE;
 Ramasser l'objet;

En combinant les deux :

 SI il y a un objet prendre ALORS
 TANT QUE l'objet est trop loin FAIRE
 Avancer vers l'objet;
 FIN TANT QUE;
 Ramasser l'objet;
 FIN SI;

Attention ne pas crire :

 SI il y a un objet prendre ALORS
 TANT QUE l'objet est trop loin FAIRE
 Avancer vers l'objet;
 FIN TANT QUE;
 FIN SI;
 Ramasser l'objet;

L'action "ramasser l'objet" sera toujours excute (car dans une squence) : s'il n'y a pas d'objet comment pourrait-on le ramasser !?



Mthodologie des algorithmes


Spcification du problme rsoudre


 Un algorithme transforme les tats d'un problme : au dpart, avant l'algorithme, on a un tat initial. Aprs excution on obtient un tat final. Il faut donc crire la spcification des tats initial et final de l'algorithme.

Exemple :
  • Le vhicule du joueur a besoin d'tre amlior. Quelles amliorations ? dfinir prcisment les amliorations...
  • Acteur "personnage architecte" : le joueur souhaite construire une muraille. Le problme de l'architecte est de savoir quel type de muraille ? quelle matire (bois, pierre) ? quelle longueur ?
La rponse la question QUOI est appele spcification. On crira par exemple :
Etat initial : construire une muraille de pierre autour des btiments du joueur
Etat final : la muraille encercle les btiments du joueur
L'algorithme doit transformer l'état initial en état final.

Remarque : l'tat final est entirement dtermin, alors que l'tat initial peut parfois tre indtermin. Par consquent l'algorithme doit en tenir compte.


Raffinages successifs


 L'criture des algorithmes par raffinages successifs est le dveloppement d'une action complexe en termes d'actions plus lmentaires. Le dveloppement doit tre une squence, une slection ou une rptition. On rpte ce processus de raffinage jusqu' atteindre le niveau des actions lmentaires de l'acteur (actions non dcomposables). Chaque niveau montre un niveau de dtail de l'algorithme. D'o la ncessit de faire le plan de l'algorithme.

 Schma gnral de constitution d'un algorithme :

Travail de conception (rflexion) 1er niveau de raffinage (plan gnral de l'algorithme)

2e niveau de raffinage

Dernier niveau de raffinage (algorithme dtaill)
Travail de traduction (codage) PROGRAMME

  • Raisonnement de faon descendante : partir du problme pour arriver la solution
  • Documenter l'algorithme au fur et mesure de son criture. En particulier, les commentaires doivent tre conus en mme temps que le programme. Les commentaires dans un programme sont en fait la trace du raffinage
  • Sparation des difficults : une seule difficult doit tre tudie la fois
  • Valider l'algorithme au fur et mesure de sa construction (droulement manuel de l'algorithme chaque niveau de raffinage) et si un problme apparat, remettre en cause le niveau prcdent
  • Sparation claire entre algorithme et programmation
 Inconvnients :
  • Fixer ds le dpart certains choix algorithmiques. Si les premiers niveaux sont faux, le reste l'est aussi (ex : criture d'une squence la place d'une rptition)
  • Limitation de la mthode pour des applications de grande taille (conception de logiciel)


Exemple : Algorithme de remise l'heure d'un rveil


 Soit un rveil possdant 3 boutons A, B et C, et deux registres (zone mmoire contenant des valeurs) nots H et M mmorisant respectivement les heures et les minutes du rveil.

 Notice de l'appareil :
  • Le bouton A permet de mettre le rveil dans le mode Remise l'heure
  • Une pression sur B permet de modifier les minutes
  • Chaque pression sur le bouton C ajoute 1 unit aux minutes (registre M) modulo 60 (sans modifier H)
  • Le bouton B stoppe ce processus et autorise la modification de la partie H
  • Le bouton C modifie alors les heures (registre H) module 24 (sans modifier la partie M)
  • Une pression sur A permet de quitter le mode remise l'heure. Le rveil est alors en fonctionnement normal.
  • L'heure de rfrence est donne par une horloge externe et s'obtiendra par l'action ENTRER(HR,MR) o HR dsigne l'heure de rfrence et MR les minutes.
 Problme : crire un algorithme de remise l'heure du rveil par un acteur (l'utilisateur) dont les seules actions lmentaires sont :
  • ENTER(HR,MR) : Entre l'heure et les minutes de rfrence
  • APPUYER A : Appuyer sur le bouton A
  • APPUYER B : Appuyer sur le bouton B
  • APPUYER C : Appuyer sur le bouton C
 On suppose que l'acteur sait enchaner les actions lmentaires en squences, slections et rptitions. Il sait comparer les valeurs des registres HR et MR aux registres H et M (grce aux oprateurs =, /=, >, <, >=, <=). On nglige le temps de manipulation de remise l'heure.

 Etat initial : rveil en tat de marche et heure quelconque
 Etat final : rveil en tat de marche et mis l'heure


Algorithme

// Mettre l'heure le rveil

 Mettre le rveil en mode mise l'heure;
 Lire les heures et les minutes de rfrence;
 Modifier les minutes;
 Modifier les heures;
 Mettre le rveil en mode fonctionnement normal;

Pour les premiers niveaux de raffinage, ne pas crire l'algorithme dans le langage de l'acteur mais en pseudo-franais.

 Dans cet exemple, les actions complexes dtailler pour le second niveau de raffinage sont : "Modifier les minutes" et "Modifier les heures" :

// Mettre l'heure le rveil

 Mettre le rveil en mode mise l'heure;

 Lire les heures et les minutes de rfrence;

 // Modifier les minutes
 TANT QUE les minutes ne sont pas jour FAIRE
 Ajouter 1 minute aux minutes;
 FIN TANT QUE;

 // Modifier les heures
 TANT QUE les heures ne sont pas jour FAIRE
 Ajouter 1 heure aux heures;
 FIN TANT QUE;

 Mettre le rveil en mode fonctionnement normal;

 La phase algorithmique est termine. Nous pouvons maintenant crire le programme car les actions de l'algorithme se traduisent simplement dans le langage de l'acteur :

// Mettre l'heure le rveil

 // Mettre le rveil en mode mise l'heure
 APPUYER A;

 // Lire les heures et les minutes de rfrence
 ENTRER (HR, MR);

 // Modifier les minutes
 APPUYER B;
 TANT QUE (M /= MR) FAIRE Le symbole /= correspond "diffrent"
 // Ajouter 1 minute aux minutes
 APPUYER C;
 FIN TANT QUE;

 // Modifier les heures
 APPUYER B;
 TANT QUE (H /= HR) FAIRE
 // Ajouter 1 heure aux heures
 APPUYER C;
 FIN TANT QUE;

 // Mettre le rveil en mode fonctionnement normal
 APPUYER A;


Remarque : si le rveil est dj l'heure, aucune action de rptition n'est excute.


Retour en haut de page