Thésée

Thésée est une installation interactive qui consiste à faire apparaître une portion d'un labyrinthe généré de façon algorithmique sous les pieds du spectateur, le labyrinthe se découvre partiellement en fonction du mouvement du spectateur, l'invitant à un jeu de mémoire pour en trouver la sortie, clin d'oeil à la mythologie grecque et aux bâtisseurs de cathédrale qui ont parfois malicieusement, comme à Chartres, dessiné un labyrinthe au sol de l'édifice religieux.

Code

Labyrinthe labyrinthe;
int largeurLabyrinthe = 20;
int hauteurLabyrinthe = 15;
int epaisseurMurs = 10;
int largeurCellule = 40;
int hauteurCellule = 40;
boolean solution, sortie;

void setup() {
  size(largeurLabyrinthe * (largeurCellule + epaisseurMurs) + epaisseurMurs, hauteurLabyrinthe * (hauteurCellule + epaisseurMurs) + epaisseurMurs);
  labyrinthe = new Labyrinthe(this, largeurLabyrinthe, hauteurLabyrinthe, epaisseurMurs, largeurCellule, hauteurCellule);
  solution = false;
  sortie = false;
  labyrinthe.creationLab();
} // Fin setup

void draw() {
  background(0);
  
  if (solution) {
    labyrinthe.afficherLabyrinthe();
  } // Fin if
  labyrinthe.position(mouseX, mouseY);
  if (sortie) {
    labyrinthe.afficherCheminSortie(mouseX, mouseY);
  } // Fin if
} // Fin draw

void keyPressed() {
  if (key == 'c') {
    solution = !solution;
  } // Fin if
  if (key == ' ') {
    sortie = !sortie;
  } // Fin if
  if (key == 's') {
    File repertoire = new File(sketchPath + "/data");
    String[] fichiers = repertoire.list();
    saveBytes("data/lab_" + fichiers.length + ".dat", labyrinthe.sauvegarder());
  } // Fin if
} // keyPressed

class Cellule {
  int compteur;
  int largeurCellule, hauteurCellule, epaisseurMur;
  boolean murNord;
  boolean murOuest;
  boolean murSud;
  boolean murEst;
  boolean chemin;
  int cheminSortie;

  Cellule(int _largeurCellule, int _hauteurCellule, int _epaisseurMur) {
    largeurCellule = _largeurCellule;
    hauteurCellule = _hauteurCellule;
    epaisseurMur = _epaisseurMur;
    compteur = 0;
    murNord = true;
    murOuest = true;
    murSud = true;
    murEst = true;
    chemin = false;
  } // Fin constructeur Cellule

  void compteurSet(int _compteur) {
    compteur = _compteur;
  } // Fin compteurSet

  int compteurGet() {
    return compteur;
  } // Fin compteurGet

  void afficher() { //int centreX, int centreY) {
    noStroke();999
    fill(255);
    if (murNord) {
      rect(0, 0, largeurCellule + 2 * epaisseurMur, epaisseurMur);
    } // Fin if
    if (murOuest) {
      rect(0, 0, epaisseurMur, hauteurCellule + 2 * epaisseurMur);
    } // Fin if
    if (murSud) {
      rect(0, hauteurCellule + epaisseurMur, largeurCellule + 2 * epaisseurMur, epaisseurMur);
    } // Fin if
    if (murEst) {
      rect(largeurCellule + epaisseurMur, 0, epaisseurMur, hauteurCellule + 2 * epaisseurMur);
    } // Fin if
  } // Fin afficher
  
  void afficherSortie() {
    noStroke();
    if (cheminSortie != 0) {
      fill(0, 255, 0);
      int masque = 15;
      for (int i = 0; i < 2; i++) {
        int val = (cheminSortie >> (4 * i)) & masque;
        switch(val) {
        case 1 :
          rect(epaisseurMur + 3 * largeurCellule / 8, 0, 2 * largeurCellule / 8, epaisseurMur + 5 * hauteurCellule / 8);
          break;
        case 2 :
          rect(0, epaisseurMur + 3 * hauteurCellule / 8, epaisseurMur + 5 * largeurCellule / 8 , 2 * hauteurCellule / 8);
          break;
        case 3 :
          rect(epaisseurMur + 3 * largeurCellule / 8, epaisseurMur + 3 * hauteurCellule / 8, 2 * largeurCellule / 8, epaisseurMur + 5 * hauteurCellule / 8);
          break;
        case 4 :
          rect(epaisseurMur + 3 * largeurCellule / 8, epaisseurMur + 3 * hauteurCellule / 8, epaisseurMur + 5 * largeurCellule / 8, 2 * hauteurCellule / 8);
          break;
        } // Fin switch
      } // Fin for999
    } // Fin if
  } // Fin afficherSortie
} // Fin Class Cellule

class Labyrinthe {
  int largeur;
  int hauteur;
  int epaisseurMur;
  int largeurCellule;
  int hauteurCellule;
  PVector sortie;
  Cellule[][] cellule;

  Labyrinthe(PApplet parent, int _largeur, int _hauteur, int _epaisseurMur, int _largeurCellule, int _hauteurCellule) {
    largeur = _largeur;
    hauteur = _hauteur;
    epaisseurMur = _epaisseurMur;
    largeurCellule = _largeurCellule;
    hauteurCellule = _hauteurCellule;
    cellule = new Cellule[largeur][hauteur];999
    for (int j = 0; j < hauteur; j++) { // Pacours des lignes
      for (int i = 0; i < largeur; i++) { // Parcours des colonnes
        cellule[i][j] = new Cellule(largeurCellule, hauteurCellule, epaisseurMur);
      } // Fin for
    } // Fin for
  } // Fin constructeur Labyrinthe

  void creationLab() {
    int[] parcours = new int[4];
    int indice;
    int x = 0;
    int y  = hauteur /2;
    boolean finProcessus = false;
    boolean sortieTrouvee = false;
    int compteur = 1;
    int xSortie = 0;
    int ySortie = 0;

    cellule[x][y].murOuest = false;
    cellule[x][y].chemin = true;
    while (!finProcessus) {
      cellule[x][y].compteur = compteur;
      if ((x == largeur - 1) && (!sortieTrouvee)) {
        cellule[x][y].murEst = false; // Arrivée à la façade Est du Labyrinthe
        cellule[x][y].chemin = true;
        sortieTrouvee = true;
        indice = 0; // Ne vérifie pas les cellules voisines donc saute directement à la recherche d'un cellule libre
        xSortie = x;
        ySortie = y;
        sortie = new PVector(x, y);
        println("Sortie " + x + " : " + y);
      } // Fin if
      else {
        indice = 0;
        if (y > 0) {
          if (cellule[x][y-1].compteur == 0) {
            parcours[indice] = 1;
            indice++;
          } // Fin if
        } // Fin if
        if (x > 0) {
          if (cellule[x-1][y].compteur == 0) {
            parcours[indice] = 2;
            indice++;
          } // Fin if
        } // Fin if
        if (y < (hauteur - 1)) {
          if (cellule[x][y+1].compteur == 0) {
            parcours[indice] = 3;
            indice++;
          } // Fin if
        } // Fin if
        if (x < (largeur - 1)) {
          if (cellule[x+1][y].compteur == 0) {
            parcours[indice] = 4;
            indice++;
          } // Fin if
        } // Fin if
      } // Fin else
      if (indice == 0) { // Arrive dans une impasse
        PVector nouvelleCelluleLibre = celluleLibre(); // Choix d'une nouvelle cellule libre adjacente
        if (nouvelleCelluleLibre.z == -1) {
          finProcessus = true;
        } // Fin if
        else {
          x = (int)nouvelleCelluleLibre.x;
          y = (int)nouvelleCelluleLibre.y;
          switch (int(nouvelleCelluleLibre.z)) { // Ouvertire des murs entre la cellule 
          case 1:
            cellule[x][y].murNord = false;
            cellule[x][y-1].murSud = false;
            compteur = cellule[x][y-1].compteur + 1;
            break;
          case 2 :
            cellule[x][y].murOuest = false;
            cellule[x-1][y].murEst = false;
            compteur = cellule[x-1][y].compteur + 1;
            break;
          case 3 :
            cellule[x][y].murSud = false;
            cellule[x][y+1].murNord = false;
            compteur = cellule[x][y+1].compteur + 1;
            break;
          case 4 :
            cellule[x][y].murEst = false;
            cellule[x+1][y].murOuest = false;
            compteur = cellule[x+1][y].compteur + 1;
            break;
          } // Fin switch
        } // Fin else
      } // Fin if
      else { // Choix d'une case adjacente
        int alea = int(random(indice)); // Choix aléatoire d'une direction
        //println(alea + " : " + parcours[alea]);
        compteur++;
        switch (parcours[alea]) {
        case 1 :
          cellule[x][y].murNord = false;
          y = y - 1;
          cellule[x][y].murSud = false;
          break;
        case 2 : 
          cellule[x][y].murOuest = false;
          x = x- 1;
          cellule[x][y].murEst = false;
          break;
        case 3 : 
          cellule[x][y].murSud = false;
          y = y + 1;
          cellule[x][y].murNord = false;
          break;
        case 4 : 
          cellule[x][y].murEst = false;
          x = x + 1;
          cellule[x][y].murOuest = false;
          break;
        } // Fin switch
      } // Fin else
    } // Fin while
    // Création du chemin de l'entrée à la sortie du labyrinthe
    while (cellule[xSortie][ySortie].compteur != 1) {
      if ((xSortie > 0) && !cellule[xSortie][ySortie].murOuest) {
        if (cellule[xSortie - 1][ySortie].compteur < cellule[xSortie][ySortie].compteur) {
          xSortie--;
          cellule[xSortie][ySortie].chemin = true;
          continue;
        } // Fin if
      } // Fin if
      if ((xSortie < largeur) && !cellule[xSortie][ySortie].murEst) {
        if (cellule[xSortie + 1][ySortie].compteur < cellule[xSortie][ySortie].compteur) {
          xSortie++;
          cellule[xSortie][ySortie].chemin = true;
          continue;
        } // Fin if
      } // Fin if
      if ((ySortie > 0) && !cellule[xSortie][ySortie].murNord) {
        if (cellule[xSortie][ySortie - 1].compteur < cellule[xSortie][ySortie].compteur) {
          ySortie--;
          cellule[xSortie][ySortie].chemin = true;
          continue;
        } // Fin if
      } // Fin if
      if ((ySortie < hauteur) && !cellule[xSortie][ySortie].murSud) {
        if (cellule[xSortie][ySortie + 1].compteur < cellule[xSortie][ySortie].compteur) {
          ySortie++;
          cellule[xSortie][ySortie].chemin = true;
          continue;
        } // Fin if
      } // Fin if
    } // Fin while
  } // Fin creationLab

  void position(float _posX, float _posY) { // Visualisation de l'espace environnant
    int caseX, caseY;
    caseX = int(_posX) / (largeurCellule + epaisseurMur);
    caseY = int(_posY) / (hauteurCellule + epaisseurMur);
    caseX = constrain(caseX, 0, largeur - 1);
    caseY = constrain(caseY, 0, hauteur - 1);
    //println(caseX + " : " + caseY);

    int i = caseY;
    do {
      pushMatrix();
      translate(caseX * (largeurCellule + epaisseurMur), i * (hauteurCellule + epaisseurMur));
      cellule[caseX][i].afficher();
      popMatrix();
      i--;
    } 
    while ( (i >= 0) && !cellule[caseX][i + 1].murNord);
    i = caseY;
    do {
      pushMatrix();
      translate(caseX * (largeurCellule + epaisseurMur), i * (hauteurCellule + epaisseurMur));
      cellule[caseX][i].afficher();
      popMatrix();
      i++;
    } 
    while ( (i < hauteur) && !cellule[caseX][i - 1].murSud);
    i = caseX;
    do {
      pushMatrix();
      translate(i * (largeurCellule + epaisseurMur), caseY * (hauteurCellule + epaisseurMur));
      cellule[i][caseY].afficher();
      popMatrix();
      i--;
    } 
    while ( (i >= 0) && !cellule[i + 1][caseY].murOuest);
    i = caseX;
    do {
      pushMatrix();
      translate(i * (largeurCellule + epaisseurMur), caseY * (hauteurCellule + epaisseurMur));
      cellule[i][caseY].afficher();
      popMatrix();
      i++;
    } 
    while ( (i < largeur) && !cellule[i - 1][caseY].murEst);
  } // position

  void afficherCheminSortie(int _posX, int _posY) {     // Création du chemin de sortie jusqu'au chemin principal
    int posX = int(_posX) / (largeurCellule + epaisseurMur);
    int posY = int(_posY) / (hauteurCellule + epaisseurMur);
    posX = constrain(posX, 0, largeur - 1);
    posY = constrain(posY, 0, hauteur - 1);
    // Remise à zéro des valeurs du chemin de sortie
    for (int i = 0; i < largeur; i++) {
      for (int j = 0; j < hauteur; j++) {
        cellule[i][j].cheminSortie = 0;
      } // Fin for
    } // Fin for
    // Trouver le chemin de la position actuelle jusqu'à une case du chemin entrée / sortie
    while (!cellule[posX][posY].chemin) {
      if ((posX > 0) && !cellule[posX][posY].murOuest) {
        if (cellule[posX - 1][posY].compteur < cellule[posX][posY].compteur) {
          cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie | (2 << 4);
          posX--;
          cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie | 4;
          continue;
        } // Fin if
      } // Fin if
      if ((posX < largeur) && !cellule[posX][posY].murEst) {
        if (cellule[posX + 1][posY].compteur < cellule[posX][posY].compteur) {
          cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie | (4 << 4);
          posX++;
          cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie | 2;
          continue;
        } // Fin if
      } // Fin if
      if ((posY > 0) && !cellule[posX][posY].murNord) {
        if (cellule[posX][posY - 1].compteur < cellule[posX][posY].compteur) {
          cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie | (1 << 4);
          posY--;
          cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie | 3;
          continue;
        } // Fin if
      } // Fin if
      if ((posY < hauteur) && !cellule[posX][posY].murSud) {
        if (cellule[posX][posY + 1].compteur < cellule[posX][posY].compteur) {
          cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie | (3 << 4);
          posY++;
          cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie | 1;
          continue;
        } // Fin if
      } // Fin if
    } // Fin while
    cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie << 4;
    int valeurCompteur = cellule[posX][posY].compteur;
    // Trouver le chemin de la sortie jusqu'à la case trouvée précédemment
    posX = (int)sortie.x;
    posY = (int)sortie.y;
    //println(posX + " : " + posY + " : " + valeurCompteur);
    while (cellule[posX][posY].compteur != valeurCompteur) {
      if ((posX > 0) && !cellule[posX][posY].murOuest) {
        if (cellule[posX - 1][posY].compteur < cellule[posX][posY].compteur) {
          cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie | (2 << 4);
          posX--;
          cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie | 4;
          continue;
        } // Fin if
      } // Fin if
      if ((posX < largeur) && !cellule[posX][posY].murEst) {
        if (cellule[posX + 1][posY].compteur < cellule[posX][posY].compteur) {
          cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie | (4 << 4);
          posX++;
          cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie | 2;
          continue;
        } // Fin if
      } // Fin if
      if ((posY > 0) && !cellule[posX][posY].murNord) {
        if (cellule[posX][posY - 1].compteur < cellule[posX][posY].compteur) {
          cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie | (1 << 4);
          posY--;
          cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie | 3;
          continue;
        } // Fin if
      } // Fin if
      if ((posY < hauteur) && !cellule[posX][posY].murSud) {
        if (cellule[posX][posY + 1].compteur < cellule[posX][posY].compteur) {
          cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie | (3 << 4);
          posY++;
          cellule[posX][posY].cheminSortie = cellule[posX][posY].cheminSortie | 1;
          continue;
        } // Fin if
      } // Fin if
    } // Fin while

      // Affichage du chemin
    for (int u = 0; u < largeur; u++) {
      for (int v = 0; v < hauteur; v++) {
        pushMatrix();
        translate(u * (largeurCellule + epaisseurMur), v * (hauteurCellule + epaisseurMur));
        cellule[u][v].afficherSortie();
        popMatrix();
      } // Fin for
    } // Fin for
  } // Fin afficherCheminSortie

  void afficherLabyrinthe() {
    //strokeWeight(0);
    noStroke();
    for (int j = 0; j < hauteur; j++) { // Parcours des lignes
      for (int i = 0; i < largeur; i++) { // Parcours des colonnes
        pushMatrix();
        translate(i * (largeurCellule + epaisseurMur), j * (hauteurCellule + epaisseurMur));
        cellule[i][j].afficher();
        if (cellule[i][j].chemin) {
          fill(255, 0, 0);
          ellipse(epaisseurMur + largeurCellule / 2, epaisseurMur + largeurCellule / 2, largeurCellule / 2, largeurCellule / 2);
        } // Fin if
        popMatrix();
        // text(cellule[i][j].compteur, i * (largeurCellule + epaisseurMur) + largeurCellule / 2, j * (hauteurCellule + epaisseurMur) + largeurCellule);
      } // Fin for
    } // Fin for
  }// Fin afficherLabyrinthe()

  PVector celluleLibre() {
    PVector[] tableau = new PVector[hauteur*largeur];
    int compt = 0;
    int verif;

    for (int j = 0; j < hauteur; j++) { // Parcours des lignes
      for (int i = 0; i < largeur; i++) { // Parcours des colonnes
        if (cellule[i][j].compteur == 0) {
          verif = 0;
          if (j > 0) {
            if (cellule[i][j-1].compteur != 0) {
              verif = 1;
            } // Fin if
          } // Fin if
          if (i > 0) {
            if (cellule[i-1][j].compteur != 0) {
              verif = 2;
            } // Fin if
          } // Fin if
          if (j < (hauteur - 1)) {
            if (cellule[i][j+1].compteur != 0) {
              verif = 3;
            } // Fin if
          } // Fin if
          if (i < (largeur - 1)) {
            if (cellule[i+1][j].compteur != 0) {
              verif = 4;
            } // Fin if
          } // Fin if
          if (verif > 0) {
            tableau[compt] = new PVector(i, j, verif);
            compt++;
          } // Fin if
        } // Fin if
      } // Fin for i
    } // Fin for j
    if (compt == 0) {
      return new PVector(-1, -1, -1);
    } // Fin if
    else {
      return tableau[int(random(compt))];
    } // Fin else
  } // Fin celluleLibre()

  byte[] sauvegarder() {
    byte[] tableau = new byte[4 * largeur * hauteur];
    int compteur = 0;
    for (int j = 0; j < hauteur; j++) {
      for (int i = 0; i < largeur; i ++) {
        tableau[compteur] = byte(cellule[i][j].murNord);
        compteur++;
        tableau[compteur] = byte(cellule[i][j].murOuest);
        compteur++;
        tableau[compteur] = byte(cellule[i][j].murSud);
        compteur++;
        tableau[compteur] = byte(cellule[i][j].murEst);
        compteur++;
      } // Fin for i
    } // Fin for j
    return tableau;
  } // Fin sauvegarder
} // Fin Class Labyrinthe

Liens

Algorithmes