Tableaux à 2 dimensions

En cours 15 et 16 nous avons appris comment stocker plusieurs données en ordre linéaire dans un tableau. Cependant, les données associées aux certains systèmes (images numériques, jeux de plateau etc.) vivent en plusieurs dimensions. Pour stocker ces données, nous avons besoin de tableaux à plusieurs dimensions. Un tableau à deux dimensions n'est rien d'autre qu'un tableau de tableaux :

int[][] tab = {{2, 5, 3}, {1, 4, 7}, {6, 1, 3}};

tableau 2D

On peut voir un tableau comme une matrice ou grille qui représente par exemple les niveaux de gris des pixels d'une image.

int[][] p = {
  {128, 128, 128, 128},
  {255, 128, 255, 128},
  {255, 128, 128, 128},
  {255, 128, 255, 255},
  {128, 128, 128, 255},
};

Pour parcourir un tableau, on utilise deux boucles imbriquées La boucle extérieure parcourt toutes les lignes. Pour chaque ligne, on parcourt toutes les colonnes dans la boucle intérieure :

Exemple 19.1. Parcours d'un tableau à deux dimensions

size(200, 250);

int[][] p = {
  {128, 128, 128, 128},
  {255, 128, 255, 128},
  {255, 128, 128, 128},
  {255, 128, 255, 255},
  {128, 128, 128, 255},
};

stroke(0);
for (int i = 0; i < 5; i++) {
  for (int j = 0; j < 4; j++) {
    fill(p[i][j]);
    rect(50 * j, 50 * i, 50, 50);
  }
}

Pour créer un tableau à deux dimensions, on utilise toujours l'opérateur new :

int lignes = 20;
int colonnes = 10;

int[][] tab = new int[lignes][colonnes];

for (int i = 0; i < lignes; i++) {
  for (int j = 0; j < colonnes; j++) {
    tab[i][j] = i + j;
  }
}

Tout comme les tableaux à une dimension, les tableaux à deux dimensions peuvent stocker des objets. L'exemple suivant dessine une grille de cellules. Chaque cellule est un rectangle dont la luminosité oscille entre 0 et 255 en suivant une onde sinusoïdale.

Exemple 19.2. Tableau d'objets à deux dimensions

// Un tableau 2D d'objets
Cellule[][] grille;

// Nombre de lignes et de colonnes de la grille
int lignes = 20;
int colonnes = 20;

void setup() {
  size(400, 400);
  grille = new Cellule[lignes][colonnes];
  for (int i = 0; i < lignes; i++) {
    for (int j = 0; j < colonnes; j++) {
      // Instantiation de chaque objet
      grille[i][j] = new Cellule(20 * j, 20 * i, 20, 20, i + j);
    }
  }
}

void draw() {
  background(0);
  for (int i = 0; i < lignes; i++) {
    for (int j = 0; j < colonnes; j++) {
      // Dessiner et faire osciller chaque objet
      grille[i][j].dessiner();
      grille[i][j].osciller();
    }
  }
}

class Cellule {
  float x, y; // position
  float w, h; // taille
  float alpha; // angle pour l'oscillation

  Cellule(float x, float y, float w, float h, float alpha) {
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
    this.alpha = alpha;
  }

  void dessiner() {
    noStroke();
    fill(map(sin(alpha), -1, 1, 0, 255));
    rect(x, y, w, h);
  }

  void osciller() {
    alpha += 0.02;
  }
}

On peut aller plus loin dans l'approche orientée objet et « cacher » le tableau de cellules dans un objet Grille qui s'occupera de les parcourir et les mettre à jour. L'exemple suivant pourrait constituer la base de différents jeux sur une grille. Chaque cellule possède un état (0 ou 1) qui change lorsque l'utilisateur clique dessus.

Exemple 19.3. Grille d'objets

Grille grille;

void setup() {
  size(400, 400);
  grille = new Grille(10, 10);
}

void draw() {
  background(0);
  grille.dessiner();
}

void mousePressed() {
  grille.click(mouseX, mouseY);
}

class Grille {
  Cellule[][] cellules;
  int lignes, colonnes;

  Grille(int lignes, int colonnes) {
    this.lignes = lignes;
    this.colonnes = colonnes;
    cellules = new Cellule[lignes][colonnes];

    float w = float(width) / colonnes;
    float h = float(height) / lignes;
    for (int i = 0; i < lignes; i++) {
      for (int j = 0; j < colonnes; j++) {
        cellules[i][j] = new Cellule(w * j, h * i, w, h);
      }
    }
  }

  void dessiner() {
    for (int i = 0; i < lignes; i++) {
      for (int j = 0; j < colonnes; j++) {
        cellules[i][j].dessiner();
      }
    }
  }

  void click(int mx, int my) {
    for (int i = 0; i < lignes; i++) {
      for (int j = 0; j < colonnes; j++) {
        cellules[i][j].click(mx, my);
      }
    }
  }
}

class Cellule {
  float x, y; // position
  float w, h; // taille
  int etat;

  Cellule(float x, float y, float w, float h) {
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
    etat = 0;
  }

  void click(int mx, int my) {
    if (x <= mx && mx < x + w && y <= my && my < y + h) {
      etat = 1 - etat;
    }
  }

  void dessiner() {
    stroke(0);
    if (etat == 0) {
      fill(255);
    } else {
      fill(128);
    }
    rect(x, y, w, h);
  }
}

Jeux de plateau

Source xkcd

Exercice 19.1. En se basant sur l'exemple précédent réalisez un jeu de Tic-tac-toe (morpion) où deux joueurs jouent tour à tour en plaçant des X et des O dans les cellules.

Exercice 19.2. Faites en sorte que la grille détecte la fin du jeu et le résultat (victoire de X, victoire de O ou match nul).

Le monde de Chip

Pour rendre la vie de notre robot Chip plus intéressante (et légèrement plus réaliste), nous allons lui construire un petit « monde » dans lequel il va évoluer. Comme vous vous en doutez déjà, le monde sera une grille de cellules rectangulaires. Les cellules sont de trois types : vide, obstacle ou trésor. Chip va se balader sur les cases vides jusqu'à ce qu'il tombe sur le trésor.

La classe Cellule n'est pas très différente de celles des exemples précédents si ce n'est que pour changer un peu, on considère que x et y sont les coordonnées non pas du coin supérieur gauche, mais du centre de la cellule. On définit également des constantes symboliques pour chaque type de cellule.

// types de cellule
final int VIDE = 0;
final int OBSTACLE = 1;
final int TRESOR = 2;

class Cellule {
  float x, y; // position du centre
  float w, h; // taille
  int type;

  Cellule(float x, float y, float w, float h, int type) {
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
    this.type = type;
  }

  void dessiner() {
    if (type == VIDE) {
      fill(255);
    } else if (type == OBSTACLE) {
      fill(0);
    } else {
      fill(255, 200, 50);
    }
    noStroke();
    rectMode(CENTER);
    rect(x, y, w, h);
  }
}

La classe Monde ressemble beaucoup à la classe Grille de l'exemple 19.3. Le constructeur prend plus d'arguments pour plus de flexibilité. Au lieu de remplir toute la fenêtre, le monde occupe une zone rectangulaire définie par x, y, w et h. L'argument pObstacle règle la proportion des cellules obstacles et les cellules vides. On ajoute 2 méthodes yLigne() et xColonne() qui permettent de passer de numéro de ligne et colonne en coordonnées fenêtre. Enfin, les méthodes estDedans(), estAccessible() et contientTresor() permettront à Chip de s'informer sur les cellules du monde.

class Monde {
  Cellule[][] cellules;
  int lignes, colonnes;

  Monde(float x, float y, float w, float h, int lignes, int colonnes, float pObstacle) {
    this.lignes = lignes;
    this.colonnes = colonnes;
    cellules = new Cellule[lignes][colonnes];

    float wCellule = w / colonnes;
    float hCellule = h / lignes;
    for (int i = 0; i < lignes; i++) {
      for (int j = 0; j < colonnes; j++) {
        float xCellule = x + wCellule * (j + 0.5);
        float yCellule = y + hCellule * (i + 0.5);

        // le type de la cellule est OBSTACLE avec probabilité pObstacle
        // et VIDE avec probabilité 1 - pObstacle
        int type = VIDE;
        if (random(1) < pObstacle) {
          type = OBSTACLE;
        }
        cellules[i][j] = new Cellule(xCellule, yCellule, wCellule, hCellule, type);
      }
    }

    // s'assurer que la cellule (0, 0) est vide, c'est là où Chip démarre
    cellules[0][0].type = VIDE;

    // cacher un trésor quelque part
    int iTresor = int(random(1, lignes));
    int jTresor = int(random(1, colonnes));
    cellules[iTresor][jTresor].type = TRESOR;
  }

  void dessiner() {
    for (int i = 0; i < lignes; i++) {
      for (int j = 0; j < colonnes; j++) {
        cellules[i][j].dessiner();
      }
    }
  }

  float yLigne(int i) {
    return cellules[i][0].y;
  }

  float xColonne(int j) {
    return cellules[0][j].x;
  }

  boolean estDedans(int i, int j) {
    return 0 <= i && i < lignes && 0 <= j && j < colonnes;
  }

  boolean estAccessible(int i, int j) {
    return estDedans(i, j) && cellules[i][j].type != OBSTACLE;
  }

  boolean contientTresor(int i, int j) {
    return estDedans(i, j) && cellules[i][j].type == TRESOR;
  }
}

Enfin on va reprendre la classe Chip de l'exemple 14.2. et l'enrichir avec quelques attributs et fonctionnalités.

Tout d'abord on va doter Chip d'une référence vers son monde pour qu'il puisse l'interroger ainsi que des indices de la case vers laquelle il se dirige :

Monde monde;
int iDest, jDest;

Ensuite on modifie légèrement le constructeur. Il prend en argument le monde et initialise x et y avec les coordonnées de la case de départ (0, 0).

Chip(Monde monde, float vitesse, float largeur, color couleur) {
  this.monde = monde;
  iDest = 0;
  jDest = 0;
  x = monde.xColonne(jDest);
  y = monde.yLigne(iDest);
  this.vitesse = vitesse;
  this.largeur = largeur;
  this.couleur = couleur;
}

Ensuite une méthode qui vérifie si Chip est arrivé à sa case destination :

boolean estArrive() {
  float d = dist(x, y, monde.xColonne(jDest), monde.yLigne(iDest));
  return d < vitesse;
}

et une autre qui vérifie si Chip a trouvé le trésor :

boolean tresorTrouve() {
  return estArrive() && monde.contientTresor(iDest, jDest);
}

Maintenant la partie la plus difficile. Lorsque Chip arrive à sa case destination, il doit choisir une nouvelle case parmi les 4 cases voisines. Bien sûr, il peut y aller seulement si la case estAccessible(). On commence par stocker les voisins accessibles dans un tableau choix. Ensuite on choisit au hasard un d'eux.

void choisirDestination() {
  int[] di = { 1,  0, -1,  0};
  int[] dj = { 0,  1,  0, -1};
  int[] choix = new int[4];
  int nbChoix = 0;
  // parcourir les 4 voisins de la cellule courante
  for (int k = 0; k < 4; k++) {
    // si le voisin est accessibles, mettre son numéro dans le tableau des choix
    if (monde.estAccessible(iDest + di[k], jDest + dj[k])) {
      choix[nbChoix] = k;
      nbChoix++;
    }
  }
  // si nbChoix == 0, Chip est coincé
  if (nbChoix > 0) {
    // choisir au hasard une des possibilités
    int k = choix[int(random(nbChoix))];
    iDest += di[k];
    jDest += dj[k];
  }
}

Après avoir écrit toutes ces méthodes, il devient relativement facile à faire une méthode permettant à Chip de bouger en toute autonomie :

void bouger() {
  if (estArrive() && !tresorTrouve()) {
    choisirDestination();
  }
  avancerVers(monde.xColonne(jDest), monde.yLigne(iDest));
}

Pour faire fonctionner tout ça, nous avons besoin d'écrire très peu de code dans setup() et draw().

Exemple 19.4. Chasse au trésor

Monde monde;
Chip chip;

void setup() {
  size(720, 720);
  monde = new Monde(60, 60, 600, 600, 10, 10, 0.2);
  chip = new Chip(monde, 1, 25, 191);
}

void draw() {
  background(128);
  monde.dessiner();
  chip.bouger();
  chip.dessiner();
  if (chip.tresorTrouve()) {
    fill(0);
    textSize(24);
    textAlign(CENTER, TOP);
    text("Chip a trouvé le trésor !", width / 2, 20);
    noLoop();
  }
}

Le code complet des classes Monde et Chip est dans le dépôt principal.

Exercice 19.3. Si on laisse suffisamment de temps à Chip, il va finir par trouver le trésor (bien sûr à condition que la case du trésor soit atteignable à partir de la case de départ, ce qui n'est pas toujours le cas). Mais compter uniquement sur le hasard n'est pas une stratégie très efficace. Pour trouver le trésor plus rapidement, Chip pourrait se servir d'une « craie » avec laquelle il marquera les cases visitées. En choisissant sa nouvelle destination, il privilégiera les cases qui ne sont pas encore marquées. Implantez cette stratégie qui privilégiera l'exploration de nouvelles cases.

Exercice 19.4. Pourriez-vous proposer une stratégie plus systématique d'exploration du monde ? Mettez-vous à la place de Chip. Comment vous allez vous prendre pour trouver le trésor ? Vous avez déjà la craie pour marquer les cases visitées. Ce qui vous manque est le fil d'Ariane pour pouvoir revenir en arrière.

Exercice 19.5. Organisez une chasse aux œufs pour Chip. Remplacez l'unique trésor par plusieurs œufs. Paramétrez leur probabilité d'apparition comme nous l'avons fait avec les obstacles. Ne connaissant pas le nombre des œufs, Chip doit explorer toutes les cellules du monde qu'il peut atteindre et ramasser tous les œufs qu'il trouve. Tenez à jour le nombre des œufs ramassés et visualisez la progression de Chip quelque part dans la zone de la fenêtre qui n'est pas occupée par le monde, par exemple :

œufs

Triangle de Pascal

Rappelons qu'un tableau à deux dimensions est un tableau dont chaque élément est un tableau. L'instruction

int [][] tab = new int[m][n];

crée un tableau de m éléments dont chaque élément est un tableau de n entiers. Mais rien ne nous oblige d'avoir le même nombre de colonnes sur chaque ligne. On peut utiliser par exemple

int[][] tab = new int[3][];

pour créer un tableau de 3 trois tableaux d'entiers et ensuite créer chaque ligne avec la taille qui nous convient, par exemple

tab[0] = new int[2];
tab[1] = new int[3];
tab[2] = new int[1];

Tableau à deux dimensions avec taille de colonnes variable

On peut parcourir un tel tableau avec la double boucle suivante :

for (int i = 0; i < tab.length; i++) {
  for (int j = 0; j < tab[i].length; j++) {
    tab[i][j] = ... ;
  }
}

Pour illustrer ce propos, considérons le triangle de Pascal. Il peut être représenté par un tableau dans lequel la première ligne contient un élément, la deuxième en contient deux et ainsi de suite.

Exercice 19.6. Complétez le code suivant pour générer le triangle de Pascal.

int n = 6;
int[][] pascal = new int[n][];

for (int i = 0; i < n; i++) {
  pascal[i] = new int[___];
  pascal[i][0] = 1;
  for (int j = 1; j < ___; j++) {
    pascal[i][j] = pascal[___][___] + pascal[___][___];
  }
  pascal[i][i] = 1;
}

// afficher le triangle
for (int i = 0; i < n; i++) {
  println("Ligne " + i);
  println(pascal[i]);
}

Exercice 19.7.

L'affichage sur la console dans l'exercice précédent n'est pas très parlant. Faites un affichage graphique plus funky du triangle de Pascal, par exemple

Triangle de Pascal

Exercice 19.8. On ne s'intéresse pas aux valeurs exactes des coefficients dans le triangle mais seulement de leur parité. Faites les calculs modulo 2, ainsi chaque coefficient va devenir soit 0, soit 1.

Triangle de Pascal modulo 2

Changez l'affichage et n'affichez plus les nombres mais seulement les cercles correspondant à des coefficients impairs. Ainsi vous pouvez diminuer le rayon des cercles et afficher des triangles beaucoup plus grands.

Triangle de Sierpiński

La structure ainsi obtenue est une approximation d'une fractale connue sous le nom de triangle de Sierpiński.

cours19 - sbalev/processing101 GitHub Wiki

Tableaux à 2 dimensions

Le monde de Chip

Triangle de Pascal

⚠️ GitHub.com Fallback ⚠️

cours19 - sbalev/processing101 GitHub Wiki

Tableaux à 2 dimensions

Le monde de Chip

Triangle de Pascal

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️