Opérations Morphologiques

Opérations Morphologiques

> Programmation

Pourquoi ne pas s'amuser a tenter des opérations morphologiques sur la map ?

C'est quoi une opération morphologique ?

Les opérations morphologiques sont des éléments du domaine de la morphologie mathématique. Ne fuyez pas ! C'est extrêmement simple. En gros résumé, il s’agit d'utiliser un ensemble (une "liste" d'objets) pour modifier un autre ensemble. Dans notre cas, l'ensemble a utiliser est la map, et la "liste" d'objets c'est... une liste de cellules ! Et c'est tout !

Donc en résumé, en entrée on a un ensemble (une map) et on va sortir un ensemble (une autre map).

Les opérations les plus communes (et faciles a implémenter !) sont la dilatation et l'érosion, qui modifient la valeur d'une cellule par rapport a l'état de ses voisins. Le choix de "qu'est ce qui est un voisin" est un autre sujet, mais pour LeekWars, j'ai décidé d'utiliser les 4 voisins d'une cellule.

C'est très simplifié mais c'est l'idée générale.

Ops sur la map

Pour réaliser des opérations morphologiques sur la map, on va commencer par représenter notre map en mémoire. Faites comme vous le sentez ! On a pas besoin d'avoir une représentation approfondie, juste des 0 et 1 pour commencer.

Pour débuter, on va commencer par marquer tous les obstacles avec la valeur 1. Ça nous affichera les cellules suivante (map utilisée: 304026719):  Ici les obstacles sont colorés en verts, car ils sont les seuls avec une valeur a 1.

On va commencer par implémenter une dilatation: chaque cellules avec au moins un voisin a 1 verra sa valeur passer a 1 également. Il suffit de tester chaque voisin de chaque cases et de passer la valeur de la case a 1 quand on rencontre un voisin avec la valeur 1. On devrait obtenir le résultat suivant :  Ici j'ai considéré que les bords de la map sont des obstacles, ça n'est pas une obligation. On remarque que les obstacles apparaissents dilatés, comme du camembert qui aurait fondu.

Nous allons ensuite appliquer une érosion a cette map. L'érosion est l'inverse de la dilatation: chaque cellule avec au moins un voisin a 0 passera a 0. Une dilatation suivie d'une érosion est une opération morphologique qui s'appelle Fermeture: Cette opération créer un "passage" entre les obstacles proches. L'opération inverse est appelée Ouverture, et consiste a faire une érosion puis une dilatation.

Sur l'image ci dessous, les cellules en rouge sont celles qui seront supprimées par l'érosion : 

Le résultat final (avec les cellules rouge supprimées) est le suivant :  On observe alors apparaitre une map qui repére les passages étroits proches des obstacles ! Tout simplement.

Pour en retirer les obstacles, on pourrait implémenter d'autres opérations, comme un AND et un NOT. Un algorithme qui applique par exemple, un NOT (inversion des 1 et des 0) sur la map avec les obstacles a 1 va nous donner une map pleine de 1 avec les obstacles a 0. Ensuite on peut appliquer un AND (si deux cases sont a 1, renvoi 1, sinon renvoi 0) sur cette map pleine et notre map obtenue précedemment avec la fermeture, ce qui passe tous les obstacles a 0. Tadam !


On obtient une liste de cellules proches des obstacles. On pourrait l'utiliser pour détecter les endroits ou il y a peu de déplacements possibles, les culs de sac, d'éventuelles cachettes, ... Essayez de faire deux dilatations suivie de deux érosions, ou d'alterner les deux, vous observerez des résultats intéressants.

Si cette méthode est bien implémentée, elle ne consomme pratiquement pas d'opérations: je l'ai implémenté avec une map sous forme binaire (voir Map sous forme binaire), ce qui ne consomme que environs 68 opérations par opération morphologique.

L'utilisation d'opérations morphologiques permet donc de réaliser rapidement une analyse de la map, et d'en tirer des informations. D'autres opérations sont facilement programmables, et peuvent fournir des résultats intéressants. A vos claviers !