Un escargot dans une matrice !!!

Titre un peu surprenant je vous l’accorde 🙂

Dans le cadre de mon projet SimImmuno II, j’ai besoin de connaître quelles sont les cellules qui avoisine une cellule donnée. Pour cela, chaque cellule est placée dans une matrice (tableau à deux dimensions !).

Le but de l’algorithme est de parcourir cette matrice à partir d’un point donnée (la position de la cellule) en tournant autour comme un escargot.

Petit exemple illustré :

Pour ne penser qu’à l’algorithme oublions les histoires de cellule. Prenons un tableau de 100×100 avec un point de référence aux coordonnées 50;50.

Nous voulons juste récupérer les coordonnées des positions autour de notre point de référence qu’empruntera notre escargot (Il suffira après de tester si aux coordonnées visitées il y a ou pas la présence d’une cellule).

Dans notre cas, les coordonnées à visiter sont : 50;49, 51;49, 51;50, 51;51, 50;51, 49;51, 49;50, 49;49, etc…

Si l’on illustre ça par le schéma :

On peut observer que l’on avance de x cases suivant notre avancement par multiple de 2 : 2 fois 1case, 2fois 2cases, 2fois 3cases, 2fois 4 cases, etc… L’on appellera cela le nombre de pas qui s’incrémentera tous les 2 avancement. Puis l’on « tourne » : Haut->Droit->Bas->Gauche->Haut->etc…

Pour coder ca en c#, définissions tout d’abord une énumération pour la direction :

public enum Direction {       Haut,       Bas,       Gauche,       Droit, }

1	public enum Direction { Haut, Bas, Gauche, Droit, }

Nous allons maintenant créer une fonction Tourner qui prend en argument la direction précédente et retourne la nouvelle direction de cette maniere : Haut->Droit->Bas->Gauche->Haut->etc.. Ce qui nous ammene à écrire :

public Direction Tourner(Direction origine) {
       if (origine == Direction.Haut)
           return Direction.Droit;
       else if (origine == Direction.Bas)
           return Direction.Gauche;
       else if (origine == Direction.Droit)
           return Direction.Bas;
       else if (origine == Direction.Gauche)
           return Direction.Haut;
       else
           return Direction.Haut; }

public Direction Tourner(Direction origine) {

if (origine == Direction.Haut)

return Direction.Droit;

else if (origine == Direction.Bas)

return Direction.Gauche;

else if (origine == Direction.Droit)

return Direction.Bas;

else if (origine == Direction.Gauche)

return Direction.Haut;

else

return Direction.Haut; }

Maintenant, il nous faut une fonction nous permettant de nous renvoyer les coordonnées de la prochaine position en fonction de la position précédente, du nombre de pas et de la direction (a noter que les positions sont matérialisés par l’objet Point possédant les propriétés X et Y) :

public Point CalculerNewPosition(Point _origine, Direction _direction) {
      int x = _origine.X;
      int y = _origine.Y;
      switch (_direction)
      {
           case Direction.Haut:
               return new Point(x,(y - 10));
           case Direction.Bas:
               return new Point(x,(y + 10));
           case Direction.Droit:
               return new Point((x + 10), y);
           case Direction.Gauche:
               return new Point((x - 10), y);
           default:
               return new Point(x,y);
      }
 }

public Point CalculerNewPosition(Point _origine, Direction _direction) {

int x = _origine.X;

int y = _origine.Y;

switch (_direction)

{

case Direction.Haut:

return new Point(x,(y - 10));

case Direction.Bas:

return new Point(x,(y + 10));

case Direction.Droit:

return new Point((x + 10), y);

case Direction.Gauche:

return new Point((x - 10), y);

default:

return new Point(x,y);

}

Une fois tout cela créé, il nous reste plus qu’a créer la fonction principale du programme composée de 3 boucles :

La 1er, boucle de 0 au nombre de pas (nommé jump) et calcule les prochaines positions.
La 2eme, boucle de 0 a 2 et appelle la 1er boucle, incrémente jump puis appelle la fonction Tourner
Enfin la dernière, de 0 a X où X le point d’arrêt.

Le code donne :

Point pointRef = new Point(50, 50);
int jump = 1;
Direction direct = Direction.Haut;
Point lastPoint = pointRef;
for (int a = 0; a < 20; a++) {
      for (int avc = 0; avc < 2; avc++)
      {
           for (int jmp = 0; jmp < jump; jmp++)
           {
                Point newPoint = CalculerNewPosition(lastPoint, direct);
                // NOUVEAU POINT DANS newPoint !
                // Inserer le code voulu !
                lastPoint = newPoint;
           }
           direct = Tourner(direct);
       }
        jump++;
 }

Point pointRef = new Point(50, 50);

int jump = 1;

Direction direct = Direction.Haut;

Point lastPoint = pointRef;

for (int a = 0; a < 20; a++) {

for (int avc = 0; avc < 2; avc++)

{

for (int jmp = 0; jmp < jump; jmp++)

{

Point newPoint = CalculerNewPosition(lastPoint, direct);

// NOUVEAU POINT DANS newPoint !

// Inserer le code voulu !

lastPoint = newPoint;

}

direct = Tourner(direct);

}

jump++;

}

Et voila le tour est joué ! Si l’on s’amuse a mettre le code :

 g.DrawLine(new Pen(new SolidBrush(Color.Black)), lastPoint, newPoint);

1	g.DrawLine(new Pen(new SolidBrush(Color.Black)), lastPoint, newPoint);

à l’endroit de Insérer le code voulu ! nous obtenons :

Facile non ? 🙂

Dev,Algo,.NET

dotNET

Comments(1)

y_nk
le 24 septembre 2009 à 02:41
Merci, je viens de retrouver ce (vieux) post encore bien référencé, et je l’ai porté sur flash a des proportions défiant les limites de flash. Je posterai bientot un article dessus 🙂

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.

Sébastien Warin

Creative Technologist
& Chief Technology Officer

Feb.05