> Programmation
Pourquoi ne pas s'amuser à tenter des opérations morphologiques sur la map ?
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 à 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 à implémenter !) sont la dilatation et l'érosion, qui modifient la valeur d'une cellule par rapport à l'état de ses voisins. Le choix de "qu'est-ce qui est un voisin" est un autre sujet, mais pour Leek Wars, 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.
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 suivantes (map utilisée: 304026719):  Ici les obstacles sont colorés en vert, car ils sont les seuls avec une valeur à 1.
On va commencer par implémenter une dilatation: chaque cellule avec au moins un voisin à 1 verra sa valeur passer à 1 également. Il suffit de tester chaque voisin de chaque case et de passer la valeur de la case à 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 apparaissent dilatés, comme du camembert qui aurait fondu.
Nous allons ensuite appliquer une érosion à cette map. L'érosion est l'inverse de la dilatation: chaque cellule avec au moins un voisin à 0 passera à 0. Une dilatation suivie d'une érosion est une opération morphologique qui s'appelle Fermeture: Cette opération crée un "passage" entre les obstacles proches. L'opération inverse est appelée Ouverture, et consiste à 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 rouges 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 à 1 va nous donner une map pleine de 1 avec les obstacles à 0. Ensuite on peut appliquer un AND (si deux cases sont à 1, renvoie 1, sinon renvoie 0) sur cette map pleine et notre map obtenue précédemment avec la fermeture, ce qui passe tous les obstacles à 0. Tadam !
On obtient une liste de cellules proches des obstacles. On pourrait l'utiliser pour détecter les endroits où il y a peu de déplacements possibles, les culs de sac, d'éventuelles cachettes, ... Essayez de faire deux dilatations suivies 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ée avec une map sous forme binaire (voir Map sous forme binaire), ce qui ne consomme qu'environ 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 !
Impossible de charger les données du jeu.
Vérifiez votre connexion et réessayez.