Labyrinthe Labyrinthe::generer(unsigned int largeur, unsigned int hauteur)
{
   Labyrinthe* lab = new Labyrinthe();
   lab->m_graphe = Graphe();
   lab->m_graphe.ajouterSommet(Coordonnee(1, 1));
   lab->m_arrivee = Coordonnee(largeur - 2, hauteur - 2);
   lab->m_depart = Coordonnee(1, 1);
   lab->m_hauteur = hauteur;
   lab->m_largeur = largeur;
   Coordonnee courant = Coordonnee(1, 1);
   int random;
   bool courantChange;
   srand(time(0));
   while (courant != Coordonnee(largeur - 2, hauteur - 2))
   {
      random = rand() % 4;
      courantChange = false;
      switch (random)
      {
         case 0:
         {
            if (courant.y > 1)
            {
               courant = Coordonnee(courant.x, courant.y - 1);
               courantChange = true;
            }
            break;
         }
         case 1:
         {
            if (courant.x < largeur - 2)
            {
               courant = Coordonnee(courant.x + 1, courant.y);
               courantChange = true;
            }
            break;
         }
         case 2:
         {
            if (courant.y < hauteur - 2)
            {
               courant = Coordonnee(courant.x, courant.y + 1);
               courantChange = true;
            }
            break;
         }
         case 3:
         {
            if (courant.x > 1)
            {
               courant = Coordonnee(courant.x - 1, courant.y);
               courantChange = true;
            }
            break;
         }
      }
      if (courantChange && !lab->m_graphe.sommetExiste(courant))
      {
         lab->m_graphe.ajouterSommet(courant);
         Coordonnee enHaut = Coordonnee(courant.x, courant.y - 1);
         Coordonnee enBas = Coordonnee(courant.x, courant.y + 1);
         Coordonnee aDroite = Coordonnee(courant.x + 1, courant.y);
         Coordonnee aGauche = Coordonnee(courant.x - 1, courant.y);

         if (lab->m_graphe.sommetExiste(enHaut) && !lab->m_graphe.areteExiste(enHaut, courant))
         {
            lab->m_graphe.ajouterArete(enHaut, courant, 1);
         }
         if (lab->m_graphe.sommetExiste(enBas) && !lab->m_graphe.areteExiste(enBas, courant))
         {
            lab->m_graphe.ajouterArete(enBas, courant, 1);
         }
         if (lab->m_graphe.sommetExiste(aDroite) && !lab->m_graphe.areteExiste(aDroite, courant))
         {
            lab->m_graphe.ajouterArete(aDroite, courant, 1);
         }
         if (lab->m_graphe.sommetExiste(aGauche) && !lab->m_graphe.areteExiste(aGauche, courant))
         {
            lab->m_graphe.ajouterArete(aGauche, courant, 1);
         }
      }

   }

   Chemin chPlusCourt =
         rechercheCheminAlgorithmeAStar(lab->graphe(), lab->m_depart, lab->m_arrivee);
   lab->m_graphe = Graphe();
   courant = lab->arrivee();
   lab->m_graphe.ajouterSommet(courant);
   for (vector<Coordonnee>::iterator it = chPlusCourt.sequence.begin(); it
         != chPlusCourt.sequence.end(); ++it)
   {
      if ((*it) != lab->arrivee())
      {
         lab->m_graphe.ajouterSommet((*it));
         lab->m_graphe.ajouterArete((*it), courant, 1);
         courant = *it;
      }
   }
   int maxSommets = ((largeur - 2) * (hauteur - 2) - chPlusCourt.cout) / 2.5;
   int cpt = 0;
   int randomLargeur = 0;
   int randomHauteur = 0;
   while (cpt < maxSommets)
   {
      randomLargeur = rand() % (largeur - 2) + 1;
      randomHauteur = rand() % (hauteur - 2) + 1;
      courant = Coordonnee(randomLargeur, randomHauteur);
      if (!lab->graphe().sommetExiste(courant))
      {
         cpt++;
         lab->m_graphe.ajouterSommet(courant);
         Coordonnee enHaut = Coordonnee(courant.x, courant.y - 1);
         Coordonnee enBas = Coordonnee(courant.x, courant.y + 1);
         Coordonnee aDroite = Coordonnee(courant.x + 1, courant.y);
         Coordonnee aGauche = Coordonnee(courant.x - 1, courant.y);

         if (lab->m_graphe.sommetExiste(enHaut) && !lab->m_graphe.areteExiste(enHaut, courant))
         {
            lab->m_graphe.ajouterArete(enHaut, courant, 1);
         }
         if (lab->m_graphe.sommetExiste(enBas) && !lab->m_graphe.areteExiste(enBas, courant))
         {
            lab->m_graphe.ajouterArete(enBas, courant, 1);
         }
         if (lab->m_graphe.sommetExiste(aDroite) && !lab->m_graphe.areteExiste(aDroite, courant))
         {
            lab->m_graphe.ajouterArete(aDroite, courant, 1);
         }
         if (lab->m_graphe.sommetExiste(aGauche) && !lab->m_graphe.areteExiste(aGauche, courant))
         {
            lab->m_graphe.ajouterArete(aGauche, courant, 1);
         }
      }
   }

   return *lab;
}