LAlex devblog v6 - Articles

Interfaces et classes virtuelles

-Alexandre LEGOUT aka LAlex- — Tue, 01 Jun 2004 17:55:19 +0000

Plongé actuellement dans le passionant ouvrage qu'est Design patterns. Catalogue des modèles de conception réutilisables (merci Francis pour le conseil ;)), je constate que la base de chaque pattern consiste en un ensemble de classes abstraites ou d'interfaces, alors que peu de programmeurs non-habitués les utilisent réellement à leur plein potentiel. C'est pourquoi j'essaie modestement dans cet article de démontrer la réelle puissance apportée par ces outils.

Beaucoup de programmeurs non habitués à la POO ne se servent que trés peu des interfaces, ou des classes virtuelles (quand elles sont disponibles dans le langage utilisé). Cet article se propose de cerner l'utilité de tels outils dans la programmation orientée objet.

Les codes exemples sont partagés entre du PHP5 et de l'Actionscript. En effet, alors que le premier offre la possibilité de faire des classes abstraites, l'autre est à mon sens plus lisible et permet un typage fort des types simples !

Définitions

Signature d'un fonction/méthode : Il s'agit de la "structure" d'une méthode. En gros, cela correspond aux arguments qu'elle prend en entrée, ainsi que leurs types, et le type de la valeur retournée.

Méthode abstraite (ou virtuelle) : Il s'agit d'une méthode qui ne contient pas d'implémentation. Une telle méthode oblige les classes qui vont hériter de la classe la contenant à implémenter une méthode dont la signature sera exactement la même.

Classe abstraite : Il s'agit d'une classe possédant au moins une méthode abstraite. Une classe abstraite n'est pas instanciable, du fait que l'ensemble de ses fonctionnalités n'est pas implémenté. Une classe abstraite permet de définir certaines implémentations par défaut, et à fournir la signature des méthodes non implémentées.
Pour l'Actionscript 2, Francis Bourre propose un pattern destiné à émuler les classes abstraites : http://www.tweenpix.net/archives/000316.html

Interface : L'interface est un ensemble de méthodes qui devront être implémentées dans les classes qui utilisent cette interface. Elle ressemble trés fortement à une classe abstraite qui ne contiendrait que des méthodes abstraites, et ne contient donc que des signatures de méthodes.

Différence entre classe abstraite et interface

Tout d'abord, la classe abstraite est utilisée par le biais de l'héritage. Il s'agit donc d'une relation de type "est un". Les classes qui hériteront d'une classe abstraite auront donc toutes un lien étroit concernant leur type. De plus, la plupart des langages n'autorisant plus l'héritage multiple, une classe ne peut souvent hériter que d'une seule classe, abstraite ou non. Il s'agit donc pour une classe abstraite de définir un "super type", dont d'autres types concrets pourront dériver.

Par exemple, on peut considérer que tous les véhicules à moteur se remplissent de la même manière : il suffit de mettre du carburant dans le réservoir. Tous les véhicules à moteur peuvent également être démarrés, mais chacun est démarré d'une manière qui lui est spécifique. Ainsi, il serait possible de créer une classe abstraite qui implémente le remplissage du réservoir, mais qui oblige chacune de ses sous-classes à implémenter la méthode de démarrage.

// Classe abstraite de véhicule a moteur // Le replissage du reservoir possède une implémentation // Par défaut abstract class Vehicle { private var $_maxFuel; private var $_currentFuel; // Méthode concrète protected function fill($quantite) { // Code pour remplir le réservoir } // Methode abstraite // Les sous-classes devront l'implémenter abstract public function start(); } // Voiture // Heritant de VahiculeAMoteur, on est obligé d'implémenter démarrer // Si on ne le fait pas, une erreur va survenir class Car extends Vehicle { // Surcharge de la méthode abstraite public function start() { // Code pour démarrer la voiture } } L'interface elle, spécifie quelles vont être les possibilités d'une classe, sans en fournir la moindre implémentation. Elle est donc garante des méthodes d'accés à un objet dont la classe implémente cette interface. On peut dire que l'implémentation d'une interface est une relation de type "possède les fonctionnalités de". D'ailleurs, les interfaces ont souvent des noms synonymes de "capable de" (en plus du 'I' qui commence généralement leur nom) : IDragable, IViewable, etc... Par exemple, si l'on veut qu'un objet puisse être affiché, il est possible de créer une interface qui obligera la classe dont est issu l'objet d'implémenter une méthode display() ... Pour un objet qui doit pouvoir être déplacé par drag&drop, une interface pourra définir quelles sont les méthodes qui serviront à la manipuler pour cette tâche précise. // Interface définissant le comportement d'un objet // que l'on peut déplacer à la souris // Toute classe implémentant cette interface devra // implémenter deux méthodes startDrag et stopDrag interface IDragable { public function startDrag():Void; public function stopDrag():Void; } // Un curseur sur une jauge doit pouvoir // être déplacé à la souris class Cursor implements IDragable { public function startDrag() { // Code de début de déplacement } public function stopDrag() { // Code de fin de déplacement } } Utilisation Les interfaces et classe abstraites n'ont un véritable sens que si elles sont associées à un langage typé fortement, ou du moins qui permet d'imposer un type d'objet dans les signatures de méthodes (comme le "type hint" de PHP5). En effet, plus qu'un "carcan" imposé au développeur de classes, elles sont surtout utiles aux classes clientes, qui vont avoir besoin d'être assurée d'un certain comportement des objets qu'elles vont utiliser. En fait, pour pousser les choses plus loin, je dirait presque que pour une souplesse d'utilisation optimale, il ne faudrait utiliser que les interfaces et classes abstraites avec le typage fort. Il arrive souvent qu'un client ait besoin d'une implémentation précise, mais de toutes façons, le typage fort n'empêche pas une instance de sous-classe d'être utilisée, parfois avec une implémentation totalement différente. Ainsi, quand une méthode va afficher un objet, elle n'a pas forcément besoin de savoir de quel type est cet objet, mais uniquement de savoir si l'objet est "affichable" ! Donc, si le fait d'être affichable revient à implémenter une interface qui demande à ce qu'une méthode display() soit présente, on utilisera cette interface pour le typage fort. Et l'objet passé à la méthode peut être de n'importe quel type, on est alors sûr qu'il disposera d'une méthode display(), dont la signature est définie par l'interface. Prenons comme exemple une carte géographique. Cette carte est affichée en grand dans une fenêtre, et un ascenseur doit la déplacer. Pour cela, le déplacement de l'ascenseur recevra en paramètre l'objet qui représente la carte. Mais pour pouvoir la déplacer, il faut être certain que cette carte possède les méthodes qui vont nous permettre de la positionner. Il faut alors créer une interface imposant des méthodes d'accés. Ainsi, toute instance d'un classe qui implémente cette interface pourra être déplacée par l'ascenceur : // Interface de déplacement interface IMovable { // Positionnement de l'objet public function moveToCoord(x:Number, y:Number); // Déplacement de l'objet public function moveByOffset(dx:Number, dy:Number); } // Classe d'une carte géographique class Map implements IMovable { // Clip correspondant à l'affichage de la carte private var _targetMC:MovieClip; // Methode de positionnement public function moveToCoord(x:Number, y:Number) { this._targetMC._x = x; this._targetMC._y = y; } // Methode de déplacement public function moveByOffset(dx:Number, dy:Number) { this._targetMC._x += dx; this._targetMC._y += dy; } } // Scroller class Scroller { function moveObject(obj:IMovable) { obj.moveByOffset(10,50); } }

Ainsi, la classe Scroller devient appliquable à n'importe quel objet qui possède les méthodes nécessaires à son déplacement. Il peut tout aussi biuen s'agir d'un dessin ou d'un texte. Ces classes n'ont rien à voir entre elles, mais leur comportement est unifié par l'utilisation de l'interface.

Conclusion

Comme vous pouvez le constater, les interfaces et classes abstraites offrent un moyen d'assouplir votre code, le rendant ainsi plus évolutif. Le fait d'utiliser un comportement et non plus une classe dans ses typages forts permet de généraliser une instruction à un ensemble bien plus large d'objets.

Alors que les interfaces sont souvent utilisées uniquement comme structure de classes lorsqu'on les connait peu, les associer au typage fort en font un outil trés puissant !

Communautés Flash francophone sur divan

-Alexandre LEGOUT aka LAlex- — Wed, 28 Apr 2004 09:40:58 +0000

Le Flash Festival souhaite organiser une rencontre de flasheurs à l'occasion du festival. Voici donc le mail qui a été envoyé à tous ceux qui peuvent promouvoir cette trés bonne idée !

Bonjour,

Nous aimerions susciter une grande rencontre des communautés à l'occasion de la 3e édition du Flash Festival en France, festival francophone du contenu animé et interactif sur Internet, organisé au centre Pompidou le samedi 08 mai 2004 !

Nous lançons un rendez-vous (après la soirée de remises des trophées), le samedi 08 mai à partir de 22h30 et jusqu'à 02h00, au Divan du monde qui sera l'occasion aux membres de nos communautés, d'échanger de visu et de se rencontrer ! L'entrée est bien sûr libre et ouverte à tous ! (pas d'open bar ;))

Nous invitons donc les différentes communautés qui le souhaitent (Flash France, Flash-Forum, VisionFlash, Flashxpress et les blogs Lalex, TweenPix et GotoAndPlay) à communiquer sur ce rendez-vous dans leurs forums ou blogs pour que celui-ci soit une réussite et un grand moment d'échange et de rencontre !

N'hésitez pas à revenir vers nous pour toutes suggestions

Le Divan du monde : http://www.divandumonde.com/
Flash Festival en France : http://www.flashfestival.net/

Divan du monde (Angle des rues La Cigale / chez Michou. Métro Pigalle, ligne 2 ou 12).
Plan: par ici

Bon, je suis super déçu de pas pouvoir y aller ... mais je conseille vivement à ceux qui en ont la possibilité de s'y rendre, ca devrait être super sympa !

Erratum article sur le pathfinding A star

-Alexandre LEGOUT aka LAlex- — Mon, 26 Apr 2004 10:05:07 +0000

Patrick Lester, auteur de l'article sur le pathfinding A* que j'ai traduit, me signale qu'en lisant les commentaires fait sur ce blog à la suite de l'article, il s'est rendu compte d'une erreur, signalée par Yogaman. En effet, dans le cas où les diagonales sont utilisées, l'heuristique Manhatan peut retourner une estimation supérieure à la distance restant à parcourir. Or, pour une fiabilité complète, il faut que l'estimation de la distance à parcourir soit inférieure ou égale à la distance restant réellement à parcourir ...

Il est maintenant signalé que la méthode Manhatan est inadmissible pour l'exemple donné, mais pour des raisons de simplification, elle reste celle qui sera utilisée dans l'exemple de l'article, comme l'a signalé l'auteur dans son article original.

Mon implémentation de l'algorithme se retrouve donc avec la même erreur, faisant que le chemin retourné peut ne pas être le plus court (toujours dans le cas des diagonales autorisées) ... Il s'agit donc de modifier la méthode heuristic pour prendre en compte les diagonales ou non. C'est là que je suis bien content d'avoir fait de l'heuristique une méthode statique indépendante ! A ce propos, je rappelle que le cout par défaut utilisé est de 10. Dans le cas où les couts de chaque case peuvent varier (couts des terrains, contenu dans chaque case de la carte), il faut donc mettre le coût minimum dans la propriété statique DEFAULT_COST ...

Voici donc la version modifiée du pathfinder pour une plus grande fiabilité. J'ai également joint la classe Grid dont je me sert maintenant (tableau à deux dimensions), et modifié un peu le package de la classe (maintenant com.lalex.game) ...

::Télécharger pathfinder.zip::

ActionScript : Les secrets des prototypes

-Alexandre LEGOUT aka LAlex- — Mon, 01 Mar 2004 09:18:00 +0000

Les prototypes sont la base de la POO avec Flash, même en AS2. C'est pourquoi j'ai considéré qu'il pouvait être sympa de faire une explication détaillée de leur fonctionnement, dans un didacticiel rédigé pour MediaBox. En fait, l'idée de ce tutoriel m'est venue il y a un petit moment deja, quand dans un éclair, j'ai fini par comprendre pourquoi la méthode d'héritage préconisée par Macromedia faisait effectivement de l'héritage ....

Auteur : LAlex
Mail : lalex@flash-forum.net
URL : http://www.flash-forum.net
Date de création : 26/02/2004
Version : Flash 5 / MX / MX 2004

Pré requis
Connaître les principes de la POO
Pour appliquer dans Flash MX 2004 : De ActionScript 1 à ActionScript 2

Introduction

Le programmation orientée objet sous Flash est dite "prototype based", soit en français "basée sur les prototypes". Ce type de programmation est opposée à la programmation dite "class based", utilisée par la plupart des langages objets célèbres, tels que le C/C++/C# ou Java. Bien qu'essayant de simuler la même syntaxe que ces derniers langages, l'ActionScript 2 reste un langage de prototypes, transformé en ActionScript 1 lors de la compilation. C'est pourquoi il est également important de connaître les rouages de cette mécanique même si l'on utilise la dernière mouture de Flash.

Bien que limitant quelques possibilités très avancées de la POO, les prototypes sont également un outil fantastique, permettant une programmation plus souple, et une compréhension plus facile du fonctionnement interne de votre code. Nous allons ici faire le tour des spécificités de la programmation à base de prototypes, et plus particulièrement celle de Flash.

1. D'ou vient le prototype ?

Nous partirons du constat que toute fonction à un prototype, qui est créé en même temps que la fonction. Le prototype est un objet, contenant des propriétés et des méthodes. En fait, il n'est pas nécessaire d'en savoir plus sur ce point. D'ailleurs, l'aide de Flash nous donne peu d'informations sur ce qu'est le prototype, et se contente de dire Dans une fonction constructeur ActionScript 1, la propriété prototype fait référence à un objet qui est le prototype de la classe construite.Nous parlons ici de fonction constructeur, c'est à dire qui va servir à instancier un nouvel objet. Or, toute fonction peut être utilisée comme constructeur. ActionScript 2 fonctionne de la même manière, et les équivalences avec AS1 sont décrites dans le tutorial "D'ActionScript 1 à ActionScript 2".

Lorsque l'on crée une fonction, on peut considérer que Flash crée automatiquement un prototype associé, de type Object :

// Création d'une fonction

myFunction = function() {

   trace("myFunction a été appellée");

}



// Instruction implicite

// myFunction.prototype = {}

2. L'opérateur new() Elément de base de la POO, l'opérateur new() sert à créer un nouvel objet à partir d'une fonction constructeur. Son fonctionnement consiste à attribuer le prototype de la fonction constructeur à un objet nouvellement crée. Examinons les différentes étapes de la création de cet objet. - L'opérateur new() crée un nouvel objet - Il initialise la propriété système "__proto__" de ce nouvel objet avec le prototype de la fonction constructeur - Il initialise la propriété système "__constructor__" de ce nouvel objet avec la fonction constructeur - Il exécute la fonction sur l'objet nouvellement crée Nous pouvons reproduire le fonctionnement de new() de la manière suivante :

// Déclaration du constructeur

function MaClasse(arg) {

   trace("Instance de MaClasse créée avec le paramètre : '" + arg + "'");

}



// Instruction new "classique"

var monInstance = new MaClasse("Argument");

// Même instruction décomposée

// On crée un nouvel objet

var monInstance = new Object();

// On lui attribue le prototype de la fonction

monInstance.__proto__ = MaClasse.prototype;

// On lui attribue le constructeur

monInstance.__constructor__ = MaClasse;

// On applique la fonction constructeur à l'objet

MaClasse.call(monInstance, "Argument");

3. __proto__ et la chaîne de prototypes
Nous avons vu précédemment que la construction d'un objet consiste à mettre un prototype dans sa propriété __proto__. Il s'agit maintenant de comprendre pourquoi l'on peut accéder aux méthodes et propriétés d'un objet, alors qu'elles sont créées dans le prototype. Nous allons prendre l'exemple d'un appel de méthode. En fait, lorsque l'on accède à la propriété d'un objet, Flash va chercher tout d'abord si cette méthode existe dans l'objet lui-même. Si c'est le cas, c'est cette méthode qui va être utilisée. Dans le cas contraire, Flash va rechercher dans la propriété __proto__ de l'objet si la méthode est présente, et l'utiliser s'il la trouve. S'il ne la trouve toujours pas, étant donné que __proto__ est un objet, il contient lui-même une propriété __proto__, dans laquelle Flash va continuer sa recherche, et ainsi de suite, jusqu'à ne plus avoir de __proto__ dans lequel rechercher. Voici une illustration du fonctionnement :

// Classe "maison"

function MaClasse (arg) {

   trace("Instance créée avec l'argument '" + arg + "'");

}



// Ajout d'une méthode dans le prototype

MaClasse.prototype.innerDoIt = function(arg) {

        trace("innerDoIt exécuté");

}

// Création d'une instance

monInstance = new MaClasse("Argument");

// Création d'une fonction dans l'instance

monInstance.doIt = function() {

        trace("doIt exécuté");

}

// Appel des différentes méthodes

monInstance.doIt();

monInstance.innerDoIt();

trace(monInstance.toString());

Instance créée avec l'argument 'Argument' doIt exécuté innerDoIt exécuté [object Object] Ce code a en fait exécuté les méthodes suivantes : - Constructeur - monInstance.doIt(); - monInstance.__proto__.innerDoIt(); - monInstance.__proto__.__proto__.toString() (méthode toString() de Object) Cette succession de recherche s'appelle "parcourir la chaîne de prototypes". La fin du parcours se fait lorsque la méthode est trouvée, ou lorsque la chaîne se termine. Nous reviendrons plus tard sur la raison pour laquelle la chaîne se termine.

4. L'héritage

Il existe deux méthodes pour implémenter l'héritage en ActionScript 1. L'instruction 'extends' d'AS2 est un mixage des deux, assez bizarre il faut bien le dire ... Pour rappel, l'héritage permet de profiter des fonctionnalités d'une classe mère dans une classe fille qui en hérite. Pour plus d'informations, rendez-vous sur le tutorial concernant les principes de la POO.
La méthode officielle de Macromedia
Elle consiste à faire du prototype de la classe fille une instance de la classe mère. Les instances de cette classe fille possèderont donc le prototype de la classe mère dans leur chaîne de prototypes.

// Classe mère<br />

Parent = function() {<br />

      trace("Nouvelle instance de Parent");<br />

}<br />

// Classe fille<br />

Child = function() {<br />

       trace("Nouvelle instance de Child");<br />

}<br />

// La classe fille hérite de la classe mère<br />

Child.prototype = new Parent()<br />

// Instanciation de la classe fille<br />

monInstance = new Child();

Pourquoi cette instruction permet-elle de faire de l'héritage ? Penchons nous en détail dessus, en se servant de ce que nous avons vu ci-dessus concernant l'instruction new() ... Si l'on utilise la notation "équivalente" de new, nous obtiendrions :

// Classe mere<br />

Parent = function() {<br />

   trace("Nouvelle instance de Parent");<br />

}<br />

// Classe fille<br />

Child = function() {<br />

   trace("Nouvelle instance de Child");<br />

}<br />

// "Traduction" de Child.prototype = new Parent()<br />

Child.prototype = new Object();<br />

Child.prototype.__proto__ = Parent.prototype;<br />

Child.prototype.__constructor__ = Parent;<br />

Parent.call(Child.prototype);<br />

// "Traduction" de monInstance = new Child()<br />

monInstance = new Object();<br />

monInstance.__proto__ = Child.prototype;<br />

monInstance.__constructor__ = Child;<br />

Child.call(monInstance);

Nous avons donc dans monInstance.__proto__ = Child.prototype, et plus haut, nous avions Child.prototype.__proto__ = Parent.prototype ... Donc, on peut en déduire que monInstance.__proto__.__proto__ = Parent.prototype ! Lorsque l'on va accéder à une méthode de monInstance, conformément au parcours de la chaîne de prototypes, Flash va d'abord chercher dans monInstance, puis dans monInstance.__proto__ (prototype de Child), puis dans monInstance.__proto__.__proto__ (prototype de Parent). Nous avons donc bien de l'héritage !

La méthode plus "propre".
Dans la "traduction" ci-dessus, on peut se rendre compte que toutes les lignes ne sont pas utiles. En effet, si l'on regarde la sortie générée par ce code, on peut voir Nouvelle instance de Parent Nouvelle instance de ChildEn effet, le constructeur de Parent a été appelé, alors qu'il n'est absolument pas nécessaire. Afin d'éviter cela, une méthode d'héritage préférable consiste à utiliser les lignes de traduction, mais uniquement celles qui sont nécessaires. L'instanciation de monInstance peut être refaite par l'opérateur new(), étant donné que le principe reste le même que ci dessus :

// Classe mere<br />

Parent = function() {<br />

   trace("Nouvelle instance de Parent");<br />

}<br />

// Classe fille<br />

Child = function() {<br />

   trace("Nouvelle instance de Child");<br />

}<br />

// Héritage<br />

// ** Child.prototype = new Object();<br />

// Cette ligne n'est pas nécessaire, étant donné que<br />

// le prototype de Child est crée automatiquement à la<br />

// création de la fonction<br />

Child.prototype.__proto__ = Parent.prototype;<br />

Child.prototype.__constructor__ = Parent;<br />

// ** Parent.call(Child.prototype);<br />

// Cette ligne n'est pas nécessaire : il est inutile<br />

// d'exécuter le constructeur de la classe mère<br />

// "Traduction" de monInstance = new Child()<br />

monInstance = new Child()

Ainsi, les fonctionnalités de l'héritage sont préservées, sans qu'aucune instruction inutile ne soit executée. Les spécifications du format SWF v7 donnent l'implémentation de l'instruction extends en ActionScript 2:

Subclass.prototype = new Object();<br />

Subclass.prototype.__proto__ = Superclass.prototype;<br />

Subclass.prototype.__constructor__ = Superclass;

Cette implémentation a fait débat, concernant le fait qu'en executant la première ligne, à priori inutile, elle détruit le prototype actuel, détruisant ainsi le prototype courant, et la propriété "constructor" de celui-ci ... Vous pouvez avoir plus d'informations sur la discussion en français qui a eu lieu sur le devblog de LAlex.

5. Pourquoi parle-t-on de "prototypes de MovieClip" ? Lorsque l'on parle de prototypes de MovieClip comme les petits utilitaires permettant de faire un mouvement élastique ou autre, il s'agit d'un abus de langage, issu des débuts de la programmation Flash durant lesquels le vocabulaire propre à la POO n'était pas des plus répandus chez les programmeur utilisant cette technologie. En réalité, pour être exact, faire un "prototype de MovieClip" signifie "rajouter une méthode au prototype de MovieClip". Etant donné que tous les clips de Flash on un __proto__ qui pointe vers MovieClip.prototype, ajouter une méthode à ce prototype revient à ajouter une méthode a chaque clip !!!

6. La cas particulier de Object
Nous parlions plus haut de parcourir la chaîne de prototypes jusqu'à ce qu'il n'y ai plus de prototype à parcourir. La question est de savoir à quel moment s'arrête cette chaîne. Le cas particulier est en fait la classe Object. Elle a pour particularité le fait que son prototype n'a pas de constructeur. Elle possède bien un prototype, comme toute fonction constructeur, c'est pourquoi il est possible d'utiliser new Object(). Par contre ce prototype n'est issu d'aucune classe, ce qui fait que le __proto__ de Object.prototype n'existe pas. C'est comme si l'instruction implicite (vue au début de ce tutoriel) à la création de la fonction "Object" n'avait pas été exécutée. En effet, cela se vérifie facilement :

// Classe interne<br />

trace("== MovieClip ==");<br />

trace(MovieClip.prototype);<br />

trace(MovieClip.prototype.__proto__);<br />

// Classe "maison"<br />

MaClasse = function() {}<br />

trace("== MaClasse ==");<br />

trace(MaClasse.prototype);<br />

trace(MaClasse.prototype.__proto__);<br />

// Classe Object<br />

trace("== Object ==");<br />

trace(Object.prototye);<br />

trace(Object.prototype.__proto__);

== MovieClip==
[object Object]
[object Object]

== MaClasse ==
[object Object]
[object Object]

== Object ==
[object Object]
undefined

C'est la raison pour laquelle la remontée de la chaîne de prototypes s'arrête à un moment donné, lorsqu'elle rencontre un __proto__ qui n'existe pas. Cette constatation nous amène aussi au fait que toutes les classes héritent forcément de Object, étant donné que leurs prototypes sont soit de type Object, soit héritent eux-mêmes de Object. C'est d'ailleurs pour ca que toutes les classes, personnelles ou intégrées à Flash, possèdent une méthode "toString"

Conclusion

Une fois les prototypes compris, se balader dans les chaînes de prototypes devient beaucoup plus clair, et l'on arrive ainsi à une compréhension accrue du fonctionnement de son code, ce qui simplifie évidemment son élaboration ainsi que son debugage.
Les prototypes peuvent également poser des problématiques inédites, véritable gymnastique de l'esprit. Les manipuler peut amener à des fonctionnalités très pointues, directement au coeur du code, traitant les classes elles-mêmes comme l'on traite des objets "normaux".

Quelle place pour Flash dans le développement d'applications online ?

-Alexandre LEGOUT aka LAlex- — Thu, 22 Jan 2004 09:18:16 +0000

Ma première contribution au webzine EMMA de MediaBox est un article sur la place de Flash dans les applications online. Je parle ici de Flash en tant qu'outil de développement pour des applicatifs avancés, et de la difficulté qu'à ce format à s'imposer dans le monde de l'entreprise, que ce soit pour des applications Intranet ou des gros sites dynamiques tels que Amazon.

J'y fais l'analyse non-exhaustive des raisons qui pourraient pousser à l'adopter, et des raisons qui rendent les décisionnaires souvent frileux à utiliser une telle technologie. Doit-on voir du Flash partout ? Pourquoi pas ! Pourquoi n'est-ce pas le cas ? Je vous livre mon explication ...

Traduction : article sur le pathfinding A*

-Alexandre LEGOUT aka LAlex- — Mon, 15 Sep 2003 19:17:00 +0000

Voici l'article qui m'a fait comprendre le pathfinding !

Je l'ai traduit en français afin que le plus grand nombre puisse en profiter. L'auteur se nomme Patrick Lester et l'article original se situe à l'adresse suivante : http://www.policyalmanac.org/games/aStarTutorial.htm

Pathfinding A* pour les débutants

Alors qu'il est relativement facile à utiliser une fois que l'on a pris le coup, l'algorithme A* (prononcer "A star") peut être difficle à aborder pour des débutants. Il existe beaucoup d'articles sur le web qui expliquent A*, mais la plupart sont destinés à ceux qui en comprennent dejà les bases. Celui-ci est destiné aux vrais débutants du pathfinding.

Cet article n'est pas spécifique à un langage donc vous devrier facilement pouvoir l'adapter a n'importe quel langage de programmation.

Introduction : la zone de recherche.

Considérons que quelqu'un veut aller d'un point A à un opint B. Considérons également qu'un mur est situé entre ces deux points. Cette situation est illustrée par l'image ci-contre, où le point A (départ) est affiché en vert, le point B (arrivée) est en rouge, et où les cases en bleu représentent le mur.

La première chose que vous remarquerez est que la zone de recherche est divisée en cases. Simplifier la zone de recherche, comme nous l'avons fait ici, est la première étape en pathfinding. Cette méthode particulière réduit notre zone de recherche à un simple tableau a deux dimensions. Chaque élément du tableau représente une case de notre grille, est son statut est notifié comme étant "traversable" ou "non traversable". Le chemin va être la succession de cases à parcourir pour passer de la case A à la case B. Une fois le chemin trouvé, notre personnage va passer du centre d'une case au centre de la prochaine case, jusqu'à ce qu'il atteigne sa cible.

Ces points au centre de chaque case sont appelés "noeuds" (nodes). Quand vous lisez un texte traitant du pathfinding, vous retrouverez souvent ce terme de noeuds. Pourquoi ne pas appeler ca simplement une case ? Tout simplement parce qu'il est possible de diviser une zone de recherche en autre chose qu'une case "carrée". Cela peut-être une forme rectangulaire, ou hexagonale, ou en fait n'importe quelle forme. Ces noeuds peuvent égelement être placés n'importe ou sur les formes - au centre ou sur les contours, ou n'importe où ailleurs. Nous utilisons ici ce système tout simplement parce que c'est le plus simple ...

Commencer la recherche

Une fois la zone de recherche simplifiée à un nombre de noeuds facilement gérable, comme nous l'avons fait avec la grille ci-dessus, la prochaine étape consiste à effectuer la recherche pour trouver le chemin le plus court. En pathfinding A*, on commence cette recherche par le point A, puis en vérifiant les cases adjacentes, et en général en cherchant encore à l'extérieur jusqu'à ce que la cible soit trouvée.

Nous commencons notre recherche de la manière suivante :

Commencons au point de départ et ajoutons le a une "liste ouverte" (open list) de cases à étudier. La liste ouverte est une sorte de "shopping list". Pour l'instant, nous n'avons qu'un seul point à l'intérieur (le point A), mais il y en aura bientôt plus. Elle contient une liste de cases qui pourraient éventuellement faire partie de notre chemin, mais pas forcément. En fait, c'est une liste de pionts que nous devrons vérifier. Regardez maintenant toutes les cases ateignables (ou "traversables") adjacentes au point de départ, en ignorant les cases avec les murs, ou de l'eau, ou toute case qu'on ne peut pas traverser. Ajoutez les a la liste ouverte également. Pour chacune de ces cases, enregistrez la case A comme son étant son "parent". Cette notion de "parent" est trés importante ensuite pour pouvoir retracer le chemin. Une explication vous est donnée plus loin.
Supprimez maintenant le point A de la "liste ouverte", et ajoutez le à une "liste fermée" (closed list), qui va contenir les points que nous n'aurons plus besoin de vérifier.

A cette étape, vous devriez avoir quelquechose comme l'image ci-contre. Sur ce schéma, la carré vert foncé au centre est notre case de départ. Elle est entourée de bleu clair pour signifier que la case a bien été ajoutée à notre "liste fermée". Toutes les cases adjacentes sont maintenant dans la "liste ouverte" de case à vérifier, et sont entourées de vert clair. Chacune d'elle possède une "pointeur" vers son parent, qui n'est autre que la case de départ.

Ensuite, choisissons une case de la "liste ouvert", et répétons plus ou moins le raisonnement précédent. Mais quelle case choisir ? Celle avec le coût F le plus bas.

Cout d'un chemin.

La clé servant à déterminer quelle case utiliser parmi celles contenues dans la "liste ouverte" est l'équation suivante :
F = G + H
avec

G est le coût de mouvement pour aller de la case A à une case donnée sur la grille, en suivant le chemin généré jusqu'ici.
H est le coût de mouvement pour aller d'une case donnée sur la grille jusqu'au point de destination, le point B. Il est souvent appelé "heuristique", ce qui peut-être troublant. La raison pour laquelle on le nomme ainsi est que ce coût est estimé. En effet, nous ne connaissons pas vraiment la distance qu'il nous reste à parcourir, car toute sortes d'obstacles peuvent se trouver sur le parcours (mur, eau, etc..). Un moyen de calculer ce coût est donné dans ce tutoriel, mais il en existe d'autres que vous pourrez trouver dans d'autres articles sur le net.

Notre chemin est généré récursivement en parcourant notre "liste ouverte" et en y choisissant le case ayant le coût F le plus faible. Ce raisonnement sera abordé un peu plus loin dans cet article, mais regardons d'abord commentutiliser l'équation que nous venons de voir.

Comme décris précédemment, G est le coût de mouvement du point de départ jusqu'à la case donnée en parcourant le chamin généré jusque là. Dans cet exemple, nous allons assigner un coût de 10 pour chaque déplacement horizontal ou vertical, et un coût de 14 pour un mouvement en diagonale. Nous utilisons ces données car la distance nécessaire pour se déplacer est la racine carrée de 2 (ne prenez par peur, restez la ! ;)), ou approximativement 1.414 fois le coût d'un déplacement vertical ou horizontal. Nous utiliserons 10 et 14 pour des raisons évidentes de simplification. Le rapport est à peu prés correct, et nous évitons ainsi les calculs de racines carrées et le nombres à virgule. Mais cela n'est pas seulement pour que nous n'aimons pas les maths : utiliser des nombres entiers est aussi bien plus rapide pour l'ordinateur également. Comme vous allez bientôt le constater, le pathfinding peut être trés lent si vous n'utilisez pas ce genre d'astuces.

Etant donné que nous calculont le coût G le long d'un chemin donné, le moyen de trouver ce coût est de prendre le coût G de son parent, et de lui ajouter 10 ou 14 selon qu'il soit situé en diagonale ou pas par rapport à son parent. L'interêt de cette méthode deviendra plus clair lorsque nous serons plus loin qu'à une case du point de départ.

Le coût H peut être estimé d'un grand nombre de facons. La méthode que nous utiliserons ici est nommée la méthode "Manhattan", avec laquelle vous calculez le nombre de cases verticales et horizontales pour parvenir au point d'arrivée (en ignorant les mouvements en diagonale). Nous multiplions alors ce total par 10. Cette méthode s'appelle "Manhattan" parce qu'elle revient à calculer le nombre de patés de maisons d'un endroit à un autre, sans couper à travers un bloc en diagonale.

En lisant ceci, il est courant de penser que l'heuristique est simplement une estimation de la distance restant à parcourir à vol d'oiseau. Or, ce n'est pas le cas. Nous essayons en fait de calculer la distance restant à parcourir via le chemin à trouver (qui est généralement plus long). Plus cette estimation est proche, plus l'algorithme trouvera le chemin facilement (et rapidement). Si le chemin estimé est sur-évalué, il n'est pas certain de trouver le chemin optimal. Dans ce cas, l'heuristique est dite "inadmissible".

Techniquement, dans cet exemple, la méthode "Manhatan" est inadmissible, car elle surévalue quelque peu la distance restante. Mais nous l'utiliserons quand-même, car elle est la plus facile à comprendre dans ce cas là, et qu'il s'agit d'une surestimation assez légère. Dans les rares cas où le chemin trouvé n'est pas le plus court, il n'en sera pas trés éloigné. Si vous voulez en savoir plus, rendez vous ici.

Le coût F est calculé en ajoutant G et H. Vous pouvez constater le résultat sur le schéma ci-contre. Les coûts F, G et H sont notés dans chaque case. Comme indiqué, F est situé en haut à gauche, G en bas à gauche et H en bas à droite.

Jetons maintenant un coup d'oeil à ces cases. Dans celle qui contient les lettres, nous avons G=10. C'est parce qu'elle est située à une case du point de départ, dans une direction horizontale. Les cases en dessous et au dessus de la case de départ, ainsi que celle située à sa gauche ont toutes le même coût de 10. Les cases en diagonales ont un coût de 14.

Les coûts H sont calculés en estimant la distance "Manhattan" jusqu'à la case d'arrivée, en se déplacant horizontallement et verticalement, et en ignorant le mur qui est sur le chemin. Avec cette méthode, la case située juste à droite du départ est à trois déplacement horizontaux de l'arrivée, soit un coût H de 30. La case située juste en dessous est à quatre cases de l'arrivée (souvenez-vous, on se déplace uniquement horizontalement et verticalement) pour un coût H de 40. Vous constaterez facilement le calcul des coûts H des autres cases.

Le coût F de chaque case est calculé par une simple addition de G et H.

Continuer la recherche

Pour continuer la recherche, nous choisissone tout simplement la case ayant le coût F le plus faible parmi les case de la "liste ouverte". Puis, avec cette case nous faisons le processus suivant :

Nous la supprimons de la "liste ouverte" et la rajoutons à la "liste fermée"
Nous vérifions toutes ses cases adjacentes, en ignorant celles qui font partie de la "list fermée", ainsi que celle qu'on ne peut pas traverser, que nous ajoutons à la "liste ouverte" si elles n'y sont pas déjà. Assignez la case en cours comme étant le "parent" des cases nouvellement ajoutées.
Si une des cases adjacentes est déjà dans la "liste ouverte", vérifiez si le chemin pour y arriver n'est pas meilleur. En d'autres termes, vérifiez si le coût G de cette case est inférieure si nous utilisons la case en cours pour y parvenir. Si ce n'est pas le cas, ne changez rien.
D'un autre côté, si le coût G du nouveau chemin est inférieur, faites que la case en cours soit le nouveau parent de cette case adjacente (dans le schéma précédent, chagez la direction du pointeur pour pointer vers la case en cours). Pour finir, re-calculez les coût F et G de cette case. Cela semble assez confus, mais vous le verrez illustré graphiquement ci-dessous.

Bon, voyons maintenant comment cela fonctionne. Sur nos 9 cases initiales, nous en avons 8 qui font partie de la "liste ouverte" aprés que la case de départ ait été envoyée vers la "liste fermée". De ces 8 cases, celle ayant le coût F le plus faible est celle qui se situe immédiatement à droite de la case de départ, avec un coût F de 40. Donc, nous choisissons cette case comme étant la prochaine. Elle est entourée en bleu dans l'illustration ci-contre.

Tout d'abord, nous supprimons cette case de la "liste ouverte" pour l'envoyer dans la "liste fermée" (c'est pourquoi elle est maintenant entourée en bleu). Puis, nous vérifions ses cases adjacentes. Celle qui est immédiatement à droite est un mur, donc nous l'ignorons. Celle immédiatement à gauche est la case de départ. Comme elle fait partie de la "liste fermée", on l'ignore également.

Les quatre autres cases sont deja dans la "liste ouverte", donc nous devons vérifier si les chemins qui y vont sont meilleurs en passant par notre case en cour, en utilisant le coût G comme point de comparaison. Regardons la case située juste en dessous de notre case actuelle. Son coût G est de 14. Si nous y allions en passant par notre case en cours, le coût serait de 20 (10 de coût G de la case, plus 10 de déplacement vertical depuis la case en cours). Un coût G de 20 est supérieur à 14, donc le chemin en cours n'est pas meilleur. Il suffit de regarder le schéma pour que cela saute aux yeux : il est plus direct d'eller sur cette case depuis le départ en se déplacant en diagonale, plutôt qu'en se déplacant d'abord horizontalement d'une case puis verticalement d'une case.

Lorsque nous répétons ce processus pour les quatre cases adjacentes deja dans la "liste ouverte", nous nous rendons compte qu'aucun chemin n'est amélioré en passant par la case en cours, donc nous ne changeons rien. Maintenant que nous avons traité toutes les cases adjacentes, nous en avons fini avec la case en cours, et nous sommes prêts à passer à la suivante.

Donc nous parcourons a nouveau notre "liste ouverte", qui est maintenant composée de 7 cases, et nous prenons celle qui a le coût F le plus faible. Il est interessant de constater que dans ce cas, il y a deux cases avec un coût de 54. Dans ce cas, laquelle choisir ? En fait, cela a peu d'importance. Pour des raisons d'optimisation, il peut être plus rapide de choisir le dernier que vous avez ajouté à la "liste ouverte". Cela oriente la recherche en faveur des cases qui sont trouvées le plus tard au cours de la recherche, quand vous êtes arrivés plus prés de votre destination. Mais cela n'a réellement pas d'importance (différentes approches de cette notion peuvent faire que deux algorithmes A* peuvent trouver des chemins différents de longueurs égales).

Choisissons la case située juste en dessous et à droite de la case de départ, comme illustré dans le schéma ci-contre.

Cette fois-ci, quand nous vérifions les cases adjacentes, nous voyons que celle située immédiatement à droite est un mur, donc nous l'ignorons. Nous faisons la même constatation pour celle située juste au dessus. Nous ignorerons également celle qui est située en dessous du mur. Pourquoi ? Parce que vous ne pouvez pas vous y rendre directement depuis la case en cours sans passer au dessus du coin du mur. Vous avez en fait besoin d'aller vers le bas d'abord, pour ensuite vous rendre sur cette case (Note : cette règle est optionnelle. Elle dépend en fait de l'endroit ou sont situés les "noeuds").

Ceci nous laisse cing autres cases. Les deux cases situées en dessous de la case en cours ne sont pas encore dans la "liste ouverte", donc nous les ajoutons avec la case en cours comme parent. En ce qui concerne les trois autres cases, deux sont deja dans la "liste fermée" (la case de départ et celle située à sa droite, toutes les deux entourées en bleu sur le schéma), donc nous les ignorons. Et la dernière case, immédiatement à gauche de la case en cours, est vérifiée pour voir si le coût G est inférieur en passant par la case en cours. Ce n'est pas le cas, donc nous pouvons vérifier la case suivante dans notre "liste ouverte".

Nous allons répeter ce processus jusqu'à ce que la case d'arrivée soit ajoutée à la "liste fermée", ce qui nous donne quelque chose comme le schéma ci-contre.

Vous contaterez que le parent de la case située deux cases en dessous du départ a changé par rapport au précédent schéma. Avant, elle avait un coût G de 28, et pointait vers la case situé en haut à droite. Maintenant elle a un score de 20 et pointe vers la case juste au dessus d'elle. Ceci est arrivé quelque part au long de notre recherche, alors que le coût G a été vérifié et modifié pour être plus faible en utilisant un autre chemin - donc le parent a été changé, et les coûts F et G recalculés. Bien que ce changement paraisse anodin ici, il existe beaucoup de situations ou cette vérification constante va faire la différence pour déterminer le meilleur chemin jusqu'à votre destination.

Maintenant, comment déterminer le chemin lui-même ? Tout simplement en partant de la case d'arrivée, et en remontant le chemin en sens inverse d'une case à sa case parent, en suivant les flèches. Cela va vous ramener à votre chemin de départ, et voila votre chemin ! Cela devrait ressembler à l'illustration ci-contre. Se déplacer du point A ou point B consiste maintenant à vous déplacer du centre d'une case au centre de la prochaine case de votre chemin, jusqu'à ce que vous atteignez votre destination. Simple non ?!?

Récapitulatif de la méthode A*

Maintenant que nous avons effectué la totalité de nos explications, faisons un petit récapitulatif étape par étape :

Ajouter le point de départ à la "liste ouverte"
Répéter les instructions suivantes :
1. Cherche la case ayant le coût F le plus faible dans la "liste ouverte". Elle devient la case en cours.
2. Passer la case en cours de la "liste ouverte" à la "liste fermée"
3. Pour les 8 case adjacentes à la case en cours
  - Si on ne peut pas la traverser, on l'ignore.
  - Si elle n'est pas dans la "liste ouverte", on l'y ajoute. La case en cours devient le parent de cette case. On calcule les coûts F, G et H de cette case.
  - Si elle est déjà dans la "liste ouverte", on teste si le chemin passant par la case en cours est meilleur en comparant les coûts G. Un coût G inférieur signifie un meilleur chemin. Si c'est le cas, on change le parent de la case pour devenir la case en cours, en on recalcule les coûts F et G. Si vous conservez une "liste ouverte" triée par coût F, la liste doit être retriée à ce moment la.
4. On s'arrête quand
  - La case de destination est ajoutée à la "liste fermée"
  - Vous ne trouvez pas la case de destination et la "liste ouverte" est vide.
Enregistrez le chemin. En partant de la case de destination, remontez d'un case à son parent jusqu'à atteindre la case de départ. Vous avez votre chemin !

Petit apparté

Excusez moi pour ce hors-sujet, mais il est important de noter qu'à de nombreuses discussions concernant le pathfinding A* sur le web et dans des forums, vous trouverez parfois certains codes qui sont dit A*, mais ne le sont pas. Pour utiliser la méthode A*, il faut absolument inclure les notions abordées précedemment, et plus précisemment la "liste ouverte" et la "liste fermée", ainsi que le calcul des coûts F, G et H. Il existe beaucoup d'algorithmes de pathfinding, mais ces autres méthodes ne sont pas A*, qui est générallement considéré comme étant le meileur de tous. Bryan Stout aborde beaucoup d'entre eux dans cet article, incluant leurs avantages et inconvénients. Parfois, une alternative est mailleure dans certaine circonstances, mais réflechissez à ce dans quoi vous mettez les pieds!