Rapport sur Le labyrinthe

Table of Contents

  • Présentation du problème
  • Métode de résolution
  • Bilan de ce travail

    • Lien vers ma page web ISIMA

    labyrinthe.jpg

    Présentation du problème

    Le labyrinthe est un problème du site Codingame. Le but de ce problème sera d’atteindre le plus vite possible un point précis dans un labyrinthe qui est décrit dans l’énoncé comme la salle de commande. Puis il faudra ensuite retourner au point de départ. Le labyrinthe est rectangulaire et il est possible de s’y déplacer selon 4 directions: haut, bas, droite, gauche. Lorsque que l’on explore le labyrinthe, il est possible de voir toutes les cases dans un carré de 5 unitées de longueur, le carré étant centré sur le joueur. Le dernier élement important est que lorsque l’on aura trouver la salle de commande, il ne nous restera qu’un temps limité pour atteindre la sortie, sinon on aura perdu. En effet, le test sera considéré comme échoué dans les cas suivants:

    • Si on ne rejoint pas la sortie du labyrinthe à temps.
    • Si on dépasse les 1200 mouvements.
    • Si on touche un mur.

    Afin de résoudre ce problème, le site Codingame nous fourni un certain nombre d’entrée.

    • Au lancement du programme:
      • R et C: les dimensions du labyrinthe.
      • A: indique le nombre de déplacements maximum dont on dispose une fois la salle de commande trouvée.
    • A chaque tour:
      • KR, KC: les coordonnées de notre position (la case en haut à gauche correpond aux coordonnées 0,0)
      • R lignes de C caractères composées de la façon suivante:
        • Le caractère peut être un . qui représente un espace dans lequel on peut avancer.
        • Le caractère peut être un ? qui représente une zone inconnue.
        • Le caractère peut être un # qui représente un mur.
        • Le caractère peut être un T qui représente le point de départ.
        • Le caractère peut être un C qui représente la salle de controle.

    Notre programme devra ainsi renvoyer à chaque tour la direction dans laquelle on doit se diriger. Les directions à renvoyer sont donc:

    • UP
    • DOWN
    • LEFT
    • RIGHT

    Métode de résolution

    Description de la stratégie

    La solution que je propose pour résoudre ce problème se divise en plusieurs parties et utilise plusieurs algotithme connu. Nous allons dans un premier temps voir ces différentes parties, puis nous nous interresserons aux algorithmes qu’elles utilisent.

    Partie 1: Définition des structures

    typedef struct st_coo {

  int y;
  int x;

} st_coo;

typedef struct st_voisin {

  st_coo gauche;
  st_coo droite;
  st_coo haut;
  st_coo bas;

} st_voisin;

typedef struct st_maillon {

  st_coo valeur;
  struct st_maillon *suivant;

} st_maillon;

typedef struct st_liste {

  int taille;
  struct st_maillon *tete;

} st_liste;

    On retrouve deux structures étant utiles pour les listes chainées, une structure qui répertori les voisins d’un élement sur la carte, et enfin une structure qui représente les coordonnées d’un point.

    Partie 2: Fonctions auxiliaires

    int r, c, a;

int carte(st_coo point) { // Check si une cordonnée est sur la carte

  if ((point.y < 0) || (point.y >= r) || (point.x < 0) || (point.x >= c)) {
    return 0;
  }
  return 1;
}

st_voisin voisin(st_coo point) {

  st_voisin voisin_point;
  voisin_point.bas.x = point.x; // On défini le voisin du dessous
  voisin_point.bas.y = point.y - 1;
  if (carte(voisin_point.bas) ==
      0) { // Si ses coordonnées ne sont pas dans la grille
    voisin_point.bas.y = -1;
    voisin_point.bas.x = -1; // On initialise à -1 le voisin
  }

  voisin_point.haut.x = point.x; // On défini le voisin du haut
  voisin_point.haut.y = point.y + 1;
  if (carte(voisin_point.haut) ==
      0) { // Si ses coordonnées ne sont pas dans la grille
    voisin_point.haut.y = -1;
    voisin_point.haut.x = -1; // On initialise à -1 le voisin
  }

  voisin_point.gauche.x = point.x - 1; // On défini le voisin de gauche
  voisin_point.gauche.y = point.y;
  if (carte(voisin_point.gauche) ==
      0) { // Si ses coordonnées ne sont pas dans la grille
    voisin_point.gauche.y = -1;
    voisin_point.gauche.x = -1; // On initialise à -1 le voisin
  }

  voisin_point.droite.x = point.x + 1; // On défini le voisin de droite
  voisin_point.droite.y = point.y;
  if (carte(voisin_point.droite) ==
      0) { // Si ses coordonnées ne sont pas dans la grille
    voisin_point.droite.y = -1;
    voisin_point.droite.x = -1; // On initialise à -1 le voisin
  }

  return voisin_point;
}

st_coo origine(st_coo point, st_coo depart,
               st_coo parents[][201]) { // Récupère le point d'où l'on vient

  st_coo temp = point;
  while ((parents[point.y][point.x].y != depart.y) &&
         (parents[point.y][point.x].x !=
          depart.x)) { // Tant que l'on a pas trouvé le point de départ
    temp = parents[point.y][point.x]; // On remonte le chemin
  }
  return temp;
}

    On retrouve trois fonctions qui seront utilisées lors de l’algorithme de recherche du prochain déplacement. La fonction carte permet de vérifier si un point est bien sur la carte. La fonction voisin permet de déterminer les différents voisins d’un élement. Elle fait appel à la fonction carte. Enfin, la fonction origine permet de remonter le chemin effectué afin de connaitre la direction à prendre.

    Partie 3: Fonctions listes chainées

    // FONCTIONS LISTES CHAINEES

st_liste *creerlistevide() {
  st_liste *pointeurSurListe;
  pointeurSurListe = malloc(1 * sizeof(st_liste *));
  pointeurSurListe->tete = NULL;
  pointeurSurListe->taille = 0;
  return pointeurSurListe;
}

void ajouterdebut(st_liste *pointeurSurListe, st_coo valeurAAjouter) {
  st_maillon *pSurMaillon;
  pSurMaillon = malloc(1 * sizeof(st_maillon *));
  pSurMaillon->valeur = valeurAAjouter;
  pSurMaillon->suivant = pointeurSurListe->tete;
  pointeurSurListe->tete = pSurMaillon;
  pointeurSurListe->taille += 1;
}

void afficherliste(st_liste *pSurListe) {
  st_maillon *pSurMaillon;
  pSurMaillon = pSurListe->tete;
  while (pSurMaillon != NULL) {
    printf("%d,%d ->", pSurMaillon->valeur.x, pSurMaillon->valeur.y);
    pSurMaillon = pSurMaillon->suivant;
  }
  printf("NULL\n");
}

void supprimerpremier(st_liste *pSurListe) {
  if (pSurListe->tete != NULL) {
    st_maillon *pSurDeuxieme;
    pSurDeuxieme = pSurListe->tete->suivant;
    free(pSurListe->tete);
    pSurListe->tete = pSurDeuxieme;
    pSurListe->taille--;
  }
}

void ajouterfin(st_liste *pSurListe, st_coo reel) {
  st_maillon *pSurMaillon;
  st_maillon *prec;
  pSurMaillon = pSurListe->tete;
  while (pSurMaillon != NULL) {
    prec = pSurMaillon;
    pSurMaillon = pSurMaillon->suivant;
  }
  st_maillon *new_maillon = malloc(1 * sizeof(st_maillon));
  new_maillon->valeur = reel;
  new_maillon->suivant = NULL;
  prec->suivant = new_maillon;
  pSurListe->taille++;
}

void destruction(st_liste *pointeurSurListe) {
  st_maillon *pSurMaillon;
  st_maillon *pSurPrecedent;
  pSurMaillon = pointeurSurListe->tete;
  while (pSurMaillon != NULL) {
    pSurPrecedent = pSurMaillon;
    pSurMaillon = pSurMaillon->suivant;
    free(pSurPrecedent);
  }
  free(pointeurSurListe);
}


// FIN

    Ces fonctions permettent de gérer les listes chainées qui seront utilisées pour construire la file de la fonction parcour_largeur.

    Partie 4: Fonction utilisant l’algorithme BFS

    st_coo parcour_largeur(char grille[101][201], char cible, st_coo depart) {

  st_coo actif;
  st_coo parents[101][201]={0};
  int check[101][201]={0};
  int vbx,vby,vhx,vhy,vgx,vgy,vdx,vdy;
  check[depart.y][depart.x] = 1;
  st_liste *file = creerlistevide();
  ajouterdebut(file, depart);
  char liste_interdit[5];
  liste_interdit[0] = '#';
  if (cible == '?') {
    liste_interdit[1] = 'C';
  }else{
    liste_interdit[1] = 'X';
  }

  while (file->taille != 0) {
    actif = file->tete->valeur;
    supprimerpremier(file);
    st_voisin voisins = voisin(actif); // On récupère les voisins du point étudié
    vbx=voisins.bas.x;
    vby=voisins.bas.y;
    vhx=voisins.haut.x;
    vhy=voisins.haut.y;
    vgx=voisins.gauche.x;
    vgy=voisins.gauche.y;
    vdx=voisins.droite.x;
    vdy=voisins.droite.y;


    if ((vbx != -1) && (check[vby][vbx] == 0)) { // Si il a un voisin en bas
      check[vby][vbx] = 1;  // On marque ce vosin
      parents[vby][vbx] = actif; // On enregistre d'où l'on vient
      if(grille[vby][vbx]!=liste_interdit[0] && grille[vby][vbx]!=liste_interdit[1]){
        ajouterdebut(file, voisins.bas); // On ajoute l'élements à la file
        if (grille[vby][vbx] ==cible) { // Si on trouvé ce que l'on cherche
          destruction(file);
          return origine(voisins.bas, depart,parents); // Récupère le point d'où l'on vient
        }
      }
    }

    if ((vhy != -1) && (check[vhy][vhx] == 0)) { // Si il a un voisin en haut
      check[vhy][vhx] = 1;  // On marque ce vosin
      parents[vhy][vhx] = actif; // On enregistre d'où l'on vient
      if(grille[vhy][vhx]!=liste_interdit[0] && grille[vhy][vhx]!=liste_interdit[1]){
        ajouterdebut(file, voisins.haut); // On ajoute l'élements à la file
        if (grille[vhy][vhx] ==cible) { // Si on trouvé ce que l'on cherche
            destruction(file);
          return origine(voisins.haut, depart,parents); // Récupère le point d'où l'on vient
        }
      }
    }

    if ((vgy != -1) && (check[vgy][vgx] == 0)) { // Si il a un voisin à gauche
      check[vgy][vgx] = 1;  // On marque ce vosin
      parents[vgy][vgx] = actif; // On enregistre d'où l'on vient
      if(grille[vgy][vgx]!=liste_interdit[0] && grille[vgy][vgx]!=liste_interdit[1]){
        ajouterdebut(file, voisins.gauche); // On ajoute l'élements à la file
        if (grille[vgy][vgx] ==cible) { // Si on trouvé ce que l'on cherche
          destruction(file);
          return origine(voisins.gauche, depart,parents); // Récupère le point d'où l'on vient
        }
      }
    }


    if ((vdy != -1) && (check[vdy][vdx] == 0)) { // Si il a un voisin à droite
      check[vdy][vdx] = 1;  // On marque ce vosin
      parents[vdy][vdx] = actif; // On enregistre d'où l'on vient
      if(grille[vdy][vdx]!=liste_interdit[0] && grille[vdy][vdx]!=liste_interdit[1]){
        ajouterdebut(file, voisins.droite); // On ajoute l'élements à la file
        if (grille[vdy][vdx] ==cible) { // Si on trouvé ce que l'on cherche
          destruction(file);
          return origine(voisins.droite, depart,parents); // Récupère le point d'où l'on vient
        }
      }
    }

  }

  st_coo defaut;
  defaut.y = -3;
  defaut.x = -3;
destruction(file);
  return defaut;
}

    Cette fonction permet de faire un parcour en largeur du graph correspondant au labyrinthe et donc de trouver le chemin pour rejoindre les différents objectifs.

    Partie 5: Fonction déplacement

    st_coo deplacement(char grille[101][201], int retour, st_coo depart) {

  if (retour == 0) { // Si on est pas sur le chemin du retour
    st_coo suivant = parcour_largeur(grille, '?', depart); // On explore tout le labyrinthe
    if (suivant.y == -3) {                    // Si on a tout exploré
      return parcour_largeur(grille, 'C',
                             depart); // On cherche la salle de controle
    }
    return suivant;
  } else {
    return parcour_largeur(grille, 'T', depart); // On cherche la sortie
  }

  st_coo defaut;
  defaut.y = -3;
  defaut.x = -3;
  return defaut;
}

    Cette fonction permet de gérer les appels de la fonction parcour_largeur, selon les objectifs atteints par le joueur.

    Partie 6: Fonction principale

    int main() {

  scanf("%d%d%d", &r, &c, &a);
  a++; // Décalage pour affichage
  int retour = 0; // Détermine si le joueur a trouvé la salle
  int nrj=1200; // Nb de mouvements restants

  while (1) { // boucle principale

    int KR;
    int KC;
    char grille[101][201];


    scanf("%d%d", &KR,
          &KC); // Récupération des coordonnées actuelles du personnage

    st_coo depart;
    depart.y = KR;
    depart.x = KC;

    printf("Carte connue du labyrinthe:\n");

    for (int i = 0; i < r; i++) { // Récupération du labyrinthe actuel

      char ROW[201];
      scanf("%s", ROW);
      for(int j=0;j<c;j++){
        grille[i][j]=ROW[j];
      }
      printf("%s\n",grille[i]);
    }

    printf("\n---Informations---\nLe joueur se déplace sur la case %d,%d\nIl reste %d d'énergie dans son jetpack.\n",KC,KR,nrj);

    if (grille[KR][KC] == 'C') {
      retour = 1;
      printf("\nLe joueur a trouvé la salle de controle, il doit maintenant repartir.\n");
    }

    if(retour==1){ // Test si le joueur doit revenir, si c'est le cas on vérifie qu'il ne soit pas trop lent
        a--;
        printf("Il reste %d tours au joueur avant l'activation de l'alarme\n",a);
        if(a<0){
            printf("Le joueur est trop lent... GAME OVER");
            return 0;
        }else if(grille[KR][KC] == 'T'){
            printf("\nLe joueur s'en est sorti, fin de la mission !\n");
            return 0;
        }
    }

    printf("\nDéplacement:  ");

    st_coo suivant = deplacement(grille, retour, depart);

    if (suivant.x > depart.x) {
      printf("RIGHT");
    }
    else if (suivant.x < depart.x) {
      printf("LEFT");
    }
    else if (suivant.y > depart.y) {
      printf("DOWN");
    } else {
      printf("UP");
    }

    printf("\n\n");
    nrj--;
  }

  return 0;
}

    Cette partie coorepond au programme principale, c’est donc à ce moment là que l’on va créer la boucle infini nous permettant de réaliser le parcour complet du labyrinthe. On va également récupérer les entrées tour par tour fournies par le site, et afficher la direction dans laquelle on souhaite se diriger.

    Remarque importante: Ma proposition pour ce Codingame a un temps d’execution trop important à chaque tour, ce qui fait qu’elle ne passe pas le test Codingame. Par ailleurs, avec les entrées fourni par Codingame j’ai pu recréer le test 1, ainsique les informations que le site affiche à chaque tour. Ainsi, la fonction print est également utilisé pour l’affichage des informations (en plus de l’affichage de la solution).

    Détail algorithmique de la méthode

    Nous allons dans cette partie, nous intéresser aux différents algorithmes importants qui consituent notre solution.

    Fonctionnement général

    Afin de bien comprendre le principe général du programme, voici ci dessous un schéma explicatif.

    labyrintheschema1.png

    Cliquez ici pour agrandir

    Dans ce schéma, les flèches rouges représentent un test négatif, et les vertes un test positif.

    On distingue deux grandes parties dans ce schéma. La première est l’exploration et la recherche de la salle de controle. La seconde consiste en retourner jusqu’à la sortie.

    Algorithme BFS

    Le parcour en largeur est un algorithme de parcour de graph. Il utilise une file. Le but est de prendre un noeud dans un graph, que l’on considérera comme le noeud de départ. On ajoutera alors ce noeud à une file. Le premier noeud de la file sera le prochain à être exploré. Ainsi on explorera ce premier noeud, cela consistera à regarder si il est relié à d’autres noeuds. Si tel est le cas, on ajoutera ces mêmes noeuds à la file, et ainsi de suite…

    Dans le contexte de ce programme, cet algorithme nous permettra d’explorer le labyrinthe afin de trouver la salle de controle, et un chemin optimal pour en sortir.

    • Exemple

      Voici ci dessous un graph représentant le fonctionnement du parcour en largeur.

      labyrintheschema2.png

      Cliquez ici pour agrandir

      Dans ce schéma, on distingue deux informations importantes. La première est que chaque case se trouvant à la même distance de la case départ est coloré de la même couleur. La distance est calculé par le nombre de noeuds entre le noeud de départ et celui coloré. La deuxième information est que les traits de couleurs représentent un ajout à la file. Par exemple, A ajoute E, mais B n’ajoute pas D. Alors, voici comment la file évoluera au fur et à mesure de l’exploration.

      • Etape 1: A

        C’est le point de départ de l’exploration.

      • Etape 2: B E

        Les deux point générés par A.

      • Etape 3: C D F

        C est généré par B, D et F par E.

      • Etape 4: G H

        C et D ne génèrent rien, H et G sont générés par F.

      Dans le cadre de notre problème, on arrètera l’exploration dès lors que l’on trouve l’élement que l’on recherche. Si on ne le trouve pas, c’est que l’on doit se concentrer sur le prochain objectif, on changera alors d’objet de recherche.

    • Point sur la file

      Afin de créer la file lors du parcour en largeur, on utilise une liste chainée. En effet, cet élement permet de diminuer la complexité du programme, car lorsque l’on défile pour ensuite re enfiler, il faut décaler tout les élements de la file, ce qui est beaucoup plus simple à faire avec une liste chainée. Il suffit alors d’ajouter ou de supprimer un élement au début ou à la fin de la liste.

    • Marquage

      Afin de marquer les chemins que l’on a déjà exploré à chaque tour, on utilise un tableau 2D de même dimension que le labyrinthe. A chaque fois que l’on trouve un voisin à une case, on le marque dans le tableau 2D, en passant la case correspondant à ses coordonée à la valeur 1. Puis, on l’explore, et on ajoute ses voisins à la file, et ainsi de suite, jusqu’à atteindre la case que l’on recherche.

    Algorithme de traçage

    Afin de se déplacer dans la bonne direction, on explore le graph jusqu’à trouver l’élement que l’on recherche. Mais l’élement que l’on recherche n’est pas forcement dans la même direction que celle dans laquelle on doit se déplacer. Ainsi il faut enregistrer le chemin afin de revenir au premier déplacement à effectuer.

    • Exemple
      ? ? ? ? ? ? ?
      ? # # # # # #
      ? # . . F # #
      ? # . # # # #
      ? # . . . C #
      # # # # # # #
      ? ? ? ? ? ? ?

      En effet, dans ce cas précis, la salle de controle se trouve en bas à droite du point de départ. Il faut pourtant se déplacer à gauche. Ainsi à chaque déplacement, on va inscrire d’où on vient.

    • Exemple

      Grille d’origine

      # # # # # # #
      . . . . . T #
      . # # # . # #
      . # # # . # #
      C # # # # # #
      # # # # # # #

      Grille parents

      labyrintheschema3.png

      Les X représentent des cases vides. T le point de départ. On se place dans le cas où on cherche la salle. Chaque case est de nature st_coo. Les nombres sont inscrits sous la forme ligne,colonne. Enfin, les cases bleues correspondent au chemin, la rouge au C, et les noirs aux murs.

      Ainsi, en appliquant simplement la fonction origine à ce tableau, on remonte jusqu’au premier déplacement effectué.

    Code commenté ayant résolu le problème

    Voici ci dessous le code complet m’ayant permis de résoudre le problème. 

    #include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct st_coo {

  int y;
  int x;

} st_coo;

typedef struct st_voisin {

  st_coo gauche;
  st_coo droite;
  st_coo haut;
  st_coo bas;

} st_voisin;

typedef struct st_maillon {

  st_coo valeur;
  struct st_maillon *suivant;

} st_maillon;

typedef struct st_liste {

  int taille;
  struct st_maillon *tete;

} st_liste;

int r, c, a;

int carte(st_coo point) { // Check si une cordonnée est sur la carte

  if ((point.y < 0) || (point.y >= r) || (point.x < 0) || (point.x >= c)) {
    return 0;
  }
  return 1;
}

st_voisin voisin(st_coo point) {

  st_voisin voisin_point;
  voisin_point.bas.x = point.x; // On défini le voisin du dessous
  voisin_point.bas.y = point.y - 1;
  if (carte(voisin_point.bas) ==
      0) { // Si ses coordonnées ne sont pas dans la grille
    voisin_point.bas.y = -1;
    voisin_point.bas.x = -1; // On initialise à -1 le voisin
  }

  voisin_point.haut.x = point.x; // On défini le voisin du haut
  voisin_point.haut.y = point.y + 1;
  if (carte(voisin_point.haut) ==
      0) { // Si ses coordonnées ne sont pas dans la grille
    voisin_point.haut.y = -1;
    voisin_point.haut.x = -1; // On initialise à -1 le voisin
  }

  voisin_point.gauche.x = point.x - 1; // On défini le voisin de gauche
  voisin_point.gauche.y = point.y;
  if (carte(voisin_point.gauche) ==
      0) { // Si ses coordonnées ne sont pas dans la grille
    voisin_point.gauche.y = -1;
    voisin_point.gauche.x = -1; // On initialise à -1 le voisin
  }

  voisin_point.droite.x = point.x + 1; // On défini le voisin de droite
  voisin_point.droite.y = point.y;
  if (carte(voisin_point.droite) ==
      0) { // Si ses coordonnées ne sont pas dans la grille
    voisin_point.droite.y = -1;
    voisin_point.droite.x = -1; // On initialise à -1 le voisin
  }

  return voisin_point;
}

st_coo origine(st_coo point, st_coo depart,
               st_coo parents[][201]) { // Récupère le point d'où l'on vient

  st_coo temp = point;
  while ((parents[point.y][point.x].y != depart.y) &&
         (parents[point.y][point.x].x !=
          depart.x)) { // Tant que l'on a pas trouvé le point de départ
    temp = parents[point.y][point.x]; // On remonte le chemin
  }
  return temp;
}

// FONCTIONS LISTES CHAINEES

st_liste *creerlistevide() {
  st_liste *pointeurSurListe;
  pointeurSurListe = malloc(1 * sizeof(st_liste *));
  pointeurSurListe->tete = NULL;
  pointeurSurListe->taille = 0;
  return pointeurSurListe;
}

void ajouterdebut(st_liste *pointeurSurListe, st_coo valeurAAjouter) {
  st_maillon *pSurMaillon;
  pSurMaillon = malloc(1 * sizeof(st_maillon *));
  pSurMaillon->valeur = valeurAAjouter;
  pSurMaillon->suivant = pointeurSurListe->tete;
  pointeurSurListe->tete = pSurMaillon;
  pointeurSurListe->taille += 1;
}

void afficherliste(st_liste *pSurListe) {
  st_maillon *pSurMaillon;
  pSurMaillon = pSurListe->tete;
  while (pSurMaillon != NULL) {
    printf("%d,%d ->", pSurMaillon->valeur.x, pSurMaillon->valeur.y);
    pSurMaillon = pSurMaillon->suivant;
  }
  printf("NULL\n");
}

void supprimerpremier(st_liste *pSurListe) {
  if (pSurListe->tete != NULL) {
    st_maillon *pSurDeuxieme;
    pSurDeuxieme = pSurListe->tete->suivant;
    free(pSurListe->tete);
    pSurListe->tete = pSurDeuxieme;
    pSurListe->taille--;
  }
}

void ajouterfin(st_liste *pSurListe, st_coo reel) {
  st_maillon *pSurMaillon;
  st_maillon *prec;
  pSurMaillon = pSurListe->tete;
  while (pSurMaillon != NULL) {
    prec = pSurMaillon;
    pSurMaillon = pSurMaillon->suivant;
  }
  st_maillon *new_maillon = malloc(1 * sizeof(st_maillon));
  new_maillon->valeur = reel;
  new_maillon->suivant = NULL;
  prec->suivant = new_maillon;
  pSurListe->taille++;
}

void destruction(st_liste *pointeurSurListe) {
  st_maillon *pSurMaillon;
  st_maillon *pSurPrecedent;
  pSurMaillon = pointeurSurListe->tete;
  while (pSurMaillon != NULL) {
    pSurPrecedent = pSurMaillon;
    pSurMaillon = pSurMaillon->suivant;
    free(pSurPrecedent);
  }
  free(pointeurSurListe);
}


// FIN

st_coo parcour_largeur(char grille[101][201], char cible, st_coo depart) {

  st_coo actif;
  st_coo parents[101][201]={0};
  int check[101][201]={0};
  int vbx,vby,vhx,vhy,vgx,vgy,vdx,vdy;
  check[depart.y][depart.x] = 1;
  st_liste *file = creerlistevide();
  ajouterdebut(file, depart);
  char liste_interdit[5];
  liste_interdit[0] = '#';
  if (cible == '?') {
    liste_interdit[1] = 'C';
  }else{
    liste_interdit[1] = 'X';
  }

  while (file->taille != 0) {
    actif = file->tete->valeur;
    supprimerpremier(file);
    st_voisin voisins = voisin(actif); // On récupère les voisins du point étudié
    vbx=voisins.bas.x;
    vby=voisins.bas.y;
    vhx=voisins.haut.x;
    vhy=voisins.haut.y;
    vgx=voisins.gauche.x;
    vgy=voisins.gauche.y;
    vdx=voisins.droite.x;
    vdy=voisins.droite.y;


    if ((vbx != -1) && (check[vby][vbx] == 0)) { // Si il a un voisin en bas
      check[vby][vbx] = 1;  // On marque ce vosin
      parents[vby][vbx] = actif; // On enregistre d'où l'on vient
      if(grille[vby][vbx]!=liste_interdit[0] && grille[vby][vbx]!=liste_interdit[1]){
        ajouterdebut(file, voisins.bas); // On ajoute l'élements à la file
        if (grille[vby][vbx] ==cible) { // Si on trouvé ce que l'on cherche
          destruction(file);
          return origine(voisins.bas, depart,parents); // Récupère le point d'où l'on vient
        }
      }
    }

    if ((vhy != -1) && (check[vhy][vhx] == 0)) { // Si il a un voisin en haut
      check[vhy][vhx] = 1;  // On marque ce vosin
      parents[vhy][vhx] = actif; // On enregistre d'où l'on vient
      if(grille[vhy][vhx]!=liste_interdit[0] && grille[vhy][vhx]!=liste_interdit[1]){
        ajouterdebut(file, voisins.haut); // On ajoute l'élements à la file
        if (grille[vhy][vhx] ==cible) { // Si on trouvé ce que l'on cherche
            destruction(file);
          return origine(voisins.haut, depart,parents); // Récupère le point d'où l'on vient
        }
      }
    }

    if ((vgy != -1) && (check[vgy][vgx] == 0)) { // Si il a un voisin à gauche
      check[vgy][vgx] = 1;  // On marque ce vosin
      parents[vgy][vgx] = actif; // On enregistre d'où l'on vient
      if(grille[vgy][vgx]!=liste_interdit[0] && grille[vgy][vgx]!=liste_interdit[1]){
        ajouterdebut(file, voisins.gauche); // On ajoute l'élements à la file
        if (grille[vgy][vgx] ==cible) { // Si on trouvé ce que l'on cherche
          destruction(file);
          return origine(voisins.gauche, depart,parents); // Récupère le point d'où l'on vient
        }
      }
    }


    if ((vdy != -1) && (check[vdy][vdx] == 0)) { // Si il a un voisin à droite
      check[vdy][vdx] = 1;  // On marque ce vosin
      parents[vdy][vdx] = actif; // On enregistre d'où l'on vient
      if(grille[vdy][vdx]!=liste_interdit[0] && grille[vdy][vdx]!=liste_interdit[1]){
        ajouterdebut(file, voisins.droite); // On ajoute l'élements à la file
        if (grille[vdy][vdx] ==cible) { // Si on trouvé ce que l'on cherche
          destruction(file);
          return origine(voisins.droite, depart,parents); // Récupère le point d'où l'on vient
        }
      }
    }

  }

  st_coo defaut;
  defaut.y = -3;
  defaut.x = -3;
destruction(file);
  return defaut;
}

st_coo deplacement(char grille[101][201], int retour, st_coo depart) {

  if (retour == 0) { // Si on est pas sur le chemin du retour
    st_coo suivant = parcour_largeur(grille, '?', depart); // On explore tout le labyrinthe
    if (suivant.y == -3) {                    // Si on a tout exploré
      return parcour_largeur(grille, 'C',
                             depart); // On cherche la salle de controle
    }
    return suivant;
  } else {
    return parcour_largeur(grille, 'T', depart); // On cherche la sortie
  }

  st_coo defaut;
  defaut.y = -3;
  defaut.x = -3;
  return defaut;
}

int main() {

  scanf("%d%d%d", &r, &c, &a);
  a++; // Décalage pour affichage
  int retour = 0; // Détermine si le joueur a trouvé la salle
  int nrj=1200; // Nb de mouvements restants

  while (1) { // boucle principale

    int KR;
    int KC;
    char grille[101][201];


    scanf("%d%d", &KR,
          &KC); // Récupération des coordonnées actuelles du personnage

    st_coo depart;
    depart.y = KR;
    depart.x = KC;

    printf("Carte connue du labyrinthe:\n");

    for (int i = 0; i < r; i++) { // Récupération du labyrinthe actuel

      char ROW[201];
      scanf("%s", ROW);
      for(int j=0;j<c;j++){
        grille[i][j]=ROW[j];
      }
      printf("%s\n",grille[i]);
    }

    printf("\n---Informations---\nLe joueur se déplace sur la case %d,%d\nIl reste %d d'énergie dans son jetpack.\n",KC,KR,nrj);

    if (grille[KR][KC] == 'C') {
      retour = 1;
      printf("\nLe joueur a trouvé la salle de controle, il doit maintenant repartir.\n");
    }

    if(retour==1){ // Test si le joueur doit revenir, si c'est le cas on vérifie qu'il ne soit pas trop lent
        a--;
        printf("Il reste %d tours au joueur avant l'activation de l'alarme\n",a);
        if(a<0){
            printf("Le joueur est trop lent... GAME OVER");
            return 0;
        }else if(grille[KR][KC] == 'T'){
            printf("\nLe joueur s'en est sorti, fin de la mission !\n");
            return 0;
        }
    }

    printf("\nDéplacement:  ");

    st_coo suivant = deplacement(grille, retour, depart);

    if (suivant.x > depart.x) {
      printf("RIGHT");
    }
    else if (suivant.x < depart.x) {
      printf("LEFT");
    }
    else if (suivant.y > depart.y) {
      printf("DOWN");
    } else {
      printf("UP");
    }

    printf("\n\n");
    nrj--;
  }

  return 0;
}

    Présentation des tests

    Afin de coder ce programme et de le valider, il a fallut passer plusieurs tests. Malheuresement, mon programme est trop lent pour passer les tests sur le site codingame. J’ai donc reconstitué le premier test de Codingame qui fonctionne, puisque le programme indique les bonnes directions à chaque étape.

    Exemple de test

    • Entrée
      15 31 7
6 5
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???#####??????????????????????
???#####??????????????????????
???##T..??????????????????????
???#####??????????????????????
???#####??????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
6 6
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???######?????????????????????
???######?????????????????????
???##T...?????????????????????
???######?????????????????????
???######?????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
6 7
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???#######????????????????????
???#######????????????????????
???##T....????????????????????
???#######????????????????????
???#######????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
6 8
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???########???????????????????
???########???????????????????
???##T.....???????????????????
???########???????????????????
???########???????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
6 9
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???#########??????????????????
???#########??????????????????
???##T......??????????????????
???#########??????????????????
???#########??????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
6 10
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???##########?????????????????
???##########?????????????????
???##T......C?????????????????
???##########?????????????????
???##########?????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
6 11
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???###########????????????????
???###########????????????????
???##T......C#????????????????
???###########????????????????
???###########????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
6 12
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???############???????????????
???############???????????????
???##T......C##???????????????
???############???????????????
???############???????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
6 11
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???############???????????????
???############???????????????
???##T......C##???????????????
???############???????????????
???############???????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
6 10
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???############???????????????
???############???????????????
???##T......C##???????????????
???############???????????????
???############???????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
6 9
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???############???????????????
???############???????????????
???##T......C##???????????????
???############???????????????
???############???????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
6 8
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???############???????????????
???############???????????????
???##T......C##???????????????
???############???????????????
???############???????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
6 7
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???############???????????????
???############???????????????
???##T......C##???????????????
???############???????????????
???############???????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
6 6
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???############???????????????
???############???????????????
???##T......C##???????????????
???############???????????????
???############???????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
6 5
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???############???????????????
???############???????????????
???##T......C##???????????????
???############???????????????
???############???????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????





      Carte connue du labyrinthe:
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???#####??????????????????????
???#####??????????????????????
???##T..??????????????????????
???#####??????????????????????
???#####??????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????

---Informations---
Le joueur se déplace sur la case 5,6
Il reste 1200 d'énergie dans son jetpack.

Déplacement:  RIGHT

Carte connue du labyrinthe:
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???######?????????????????????
???######?????????????????????
???##T...?????????????????????
???######?????????????????????
???######?????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????

---Informations---
Le joueur se déplace sur la case 6,6
Il reste 1199 d'énergie dans son jetpack.

Déplacement:  RIGHT

Carte connue du labyrinthe:
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???#######????????????????????
???#######????????????????????
???##T....????????????????????
???#######????????????????????
???#######????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????

---Informations---
Le joueur se déplace sur la case 7,6
Il reste 1198 d'énergie dans son jetpack.

Déplacement:  RIGHT

Carte connue du labyrinthe:
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???########???????????????????
???########???????????????????
???##T.....???????????????????
???########???????????????????
???########???????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????

---Informations---
Le joueur se déplace sur la case 8,6
Il reste 1197 d'énergie dans son jetpack.

Déplacement:  RIGHT

Carte connue du labyrinthe:
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???#########??????????????????
???#########??????????????????
???##T......??????????????????
???#########??????????????????
???#########??????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????

---Informations---
Le joueur se déplace sur la case 9,6
Il reste 1196 d'énergie dans son jetpack.

Déplacement:  RIGHT

Carte connue du labyrinthe:
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???##########?????????????????
???##########?????????????????
???##T......C?????????????????
???##########?????????????????
???##########?????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????

---Informations---
Le joueur se déplace sur la case 10,6
Il reste 1195 d'énergie dans son jetpack.

Déplacement:  RIGHT

Carte connue du labyrinthe:
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???###########????????????????
???###########????????????????
???##T......C#????????????????
???###########????????????????
???###########????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????

---Informations---
Le joueur se déplace sur la case 11,6
Il reste 1194 d'énergie dans son jetpack.

Déplacement:  RIGHT

Carte connue du labyrinthe:
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???############???????????????
???############???????????????
???##T......C##???????????????
???############???????????????
???############???????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????

---Informations---
Le joueur se déplace sur la case 12,6
Il reste 1193 d'énergie dans son jetpack.

Le joueur a trouvé la salle de controle, il doit maintenant repartir.
Il reste 7 tours au joueur avant l'activation de l'alarme

Déplacement:  LEFT

Carte connue du labyrinthe:
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???############???????????????
???############???????????????
???##T......C##???????????????
???############???????????????
???############???????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????

---Informations---
Le joueur se déplace sur la case 11,6
Il reste 1192 d'énergie dans son jetpack.
Il reste 6 tours au joueur avant l'activation de l'alarme

Déplacement:  LEFT

Carte connue du labyrinthe:
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???############???????????????
???############???????????????
???##T......C##???????????????
???############???????????????
???############???????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????

---Informations---
Le joueur se déplace sur la case 10,6
Il reste 1191 d'énergie dans son jetpack.
Il reste 5 tours au joueur avant l'activation de l'alarme

Déplacement:  LEFT

Carte connue du labyrinthe:
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???############???????????????
???############???????????????
???##T......C##???????????????
???############???????????????
???############???????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????

---Informations---
Le joueur se déplace sur la case 9,6
Il reste 1190 d'énergie dans son jetpack.
Il reste 4 tours au joueur avant l'activation de l'alarme

Déplacement:  LEFT

Carte connue du labyrinthe:
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???############???????????????
???############???????????????
???##T......C##???????????????
???############???????????????
???############???????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????

---Informations---
Le joueur se déplace sur la case 8,6
Il reste 1189 d'énergie dans son jetpack.
Il reste 3 tours au joueur avant l'activation de l'alarme

Déplacement:  LEFT

Carte connue du labyrinthe:
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???############???????????????
???############???????????????
???##T......C##???????????????
???############???????????????
???############???????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????

---Informations---
Le joueur se déplace sur la case 7,6
Il reste 1188 d'énergie dans son jetpack.
Il reste 2 tours au joueur avant l'activation de l'alarme

Déplacement:  LEFT

Carte connue du labyrinthe:
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???############???????????????
???############???????????????
???##T......C##???????????????
???############???????????????
???############???????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????

---Informations---
Le joueur se déplace sur la case 6,6
Il reste 1187 d'énergie dans son jetpack.
Il reste 1 tours au joueur avant l'activation de l'alarme

Déplacement:  LEFT

Carte connue du labyrinthe:
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
???############???????????????
???############???????????????
???##T......C##???????????????
???############???????????????
???############???????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????
??????????????????????????????

---Informations---
Le joueur se déplace sur la case 5,6
Il reste 1186 d'énergie dans son jetpack.
Il reste 0 tours au joueur avant l'activation de l'alarme

Le joueur s'en est sorti, fin de la mission !

      Ainsi, on peut voir que le programme détecte la salle de controle, arrive à s’y diriger, et à repartir dans le temps imparti.

    Debuggage Valgrind & DDD

    Valgrind

    Afin d’être certain de ne pas avoir de problèmes de mémoire et autres, que le compilateur n’aurait pas détecté, on utilise valgrind. 

    valgrind ./labyrinthe < labyrinthetest/test2

    valgrindlabyrinthe.png

    Je me suis alors rendu compte qu’il y a avait énormement d’erreurs. Alors en allant chercher des informations supplémentaires grace à l’option -s, j’en ai conclu que l’erreur était toujours la même, et qu’elle se répetait à chaque étape du programme: invalid read of size 8. Cette erreur est dû à la liste chainée car elle est provoqué par les fonctions creer_liste, ajoute_debut et supprimer_premier. Malgré de nombreux essais je n’ai pas réussi à résoudre le problème. J’ai pu tout de même résoudre certains problèmes d’allocation de mémoire comme le montre la capture d’écran, puisqu’aucune ressource n’est perdue après l’execution du programme.

    DDD

    Le débuggeur DDD nous permet de voir différentes choses intéressantes sur notre code. Tout d’abord, on peut s’assurer que la fonction voisin fonctionne, et qu’elle renvoie bien les voisins attendu. Ci dessous, voici ce que renvoie la fonction voisin pour la case de coordonnée 6,6.

    labyrinthed1.png

    De plus, le débuggeur nous permet de voir le contenu de la file, constituée à l’aide d’une liste chainée. Dans les images ci-dessous, on part de la case 7,6.

    labyrinthed2.png

    Ici on enfile les deux voisins qui sont des potentiels chemins 8,6 et 6,6

    labyrinthed3.png

    On enfile 9,6 voisin de 8,6

    labyrinthed4.png

    On enfile 10,6 voisin de 9,6, puis on supprimera la liste. Cela signifit que un des voisins de 10,6 (forcement 11,6 dans l’exemple) correspond à la cible que l’on recherche. Dans ce cas là, 11,6 est un ’?’.

    Remarque: N’ayant pas réussi à passer les tests Codingame, il m’est impossible de présenter une solution de la communautée.

    Doxygene

    Pour plus d’information sur mon code, voici de la documentation suplémentaire réalisée grace à Doxygene.

    Bilan de ce travail

    Ce travail m’a permi de découvrir de nouveaux algorithme et de travailler sur la notion de file. Ce travail principalement centré sur l’algorithmique m’a montré que le plus important n’était pas de savoir coder, mais bien de créer/reprendre un algorithme assez complexe afin de trouver la réponse à un problème.

    Author: Mathieu CHEDAS

    Created: 2023-04-28 ven. 11:33