IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Python Discussion :

Generation de labyrinthe [Python 3.X]


Sujet :

Python

  1. #1
    Membre habitué
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2023
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2023
    Messages : 13
    Par défaut Generation de labyrinthe
    Bonjour,
    j'essaie de creer un labyrinthe reccursif mais mon programme ne genere que des labyrinthes 20*20, au dela il n'y arrive qu'une fois de temps en temps.
    Le principe du Labyrinthe récursif : Nom : clusters.gif
Affichages : 1070
Taille : 16,1 Ko

    voici mon code :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
     
    import matplotlib.pyplot as plt
    import numpy as np
    import random as rd[ATTACH=CONFIG]636683[/ATTACH]
    ########################################################
    ########################################################
     
    def init_Labyrinthe(n) :
        """Initialisation du Labyrinthe : pose des murs exterieurs"""
        Laby = np.zeros((n, n), dtype = int)
        for i in range (n):
            Laby[0,i] = 1
            Laby[n-1,i] = 1
            Laby[i,0] = 1
            Laby[i,n-1] = 1
        return Laby
     
    ########################################################
     
    def matrice_Trou (n) :
        """Création de la Matrice receuillant l'emplacement des Trous"""
        Matrou = np.zeros((n, n), dtype = int)
        return Matrou
     
    ########################################################
     
    def entree_Sortie (n, Matrou, Laby) :
        """Definition de l'entrée et la sortie"""
        Debut = rd.randint(1, n-2)
        Laby[Debut,0] = 0
        Matrou[Debut,1] , Matrou[Debut,0] = 1,1
     
        Arrivee = rd.randint(1, n-2)
        Laby[Arrivee,n-1] = 0
        Matrou[Arrivee,n-2],Matrou[Arrivee,n-1] = 1,1
     
    ########################################################
     
    def labyrinthe_Final (n,fps) :
        """Creation du Labyrinthe de taille n"""
        Matrou = matrice_Trou(n)
        Laby = init_Labyrinthe(n)
        entree_Sortie(n, Matrou, Laby)
        img = mur((1,1), (n-2,n-2), Laby, Matrou)
        afficher(Laby, Matrou)
     
    ########################################################    
     
    def afficher (labyrinthe, Matrou):
        """Permet l'affichage de la matrice sous forme de labyrinthe
            et aussi de l'affichage de la matrice de trou"""
    #    plt.subplot(2,1,2)
        plt.imshow(labyrinthe, cmap='GnBu')
        plt.axis('off')
    #    plt.subplot(2,1,1)
    #    plt.imshow(Matrou, cmap='Greys')
    #    plt.imshow(labyrinthe, cmap='GnBu', alpha=0.6)
    #    plt.axis('off')
        plt.show()
     
    ########################################################
     
    def mur_Horizontal(GH, DB, Laby, Matrou):
        """Création de mur horizontal
            GH = (ligne, colonne)"""
        rdLigne=0
        while Matrou[rdLigne, GH[1]] == 1 or Matrou[rdLigne, DB[1]] == 1 or rdLigne == 0:
            rdLigne = rd.randint(GH[0]+1,DB[0]-1)
        rdTrou = rd.randint(GH[1],DB[1])
        Laby[rdLigne,GH[1]:DB[1]+1] = 1
        Laby[rdLigne,rdTrou] = 0
        Matrou[rdLigne-1:rdLigne+1 +1, rdTrou] = 1
        return rdLigne
     
    ########################################################
     
    def mur_Vertical(GH, DB, Laby, Matrou):
        """Création de mur vertical
            GH = (ligne, colonne)"""
        rdColonne=0
        while Matrou[GH[0], rdColonne] == 1 or Matrou[DB[0], rdColonne] == 1 or rdColonne == 0:
            rdColonne = rd.randint(GH[1]+1,DB[1]-1)
        rdTrou = rd.randint(GH[0],DB[0])
        Laby[GH[0]:DB[0]+1,rdColonne] = 1
        Laby[rdTrou,rdColonne] = 0
        Matrou[rdTrou, rdColonne-1:rdColonne+1 +1] = 1
        return rdColonne
     
    ########################################################
     
    def mur (GHinit, DBinit, Laby, Matrou):
        n=len(Matrou[0])
        attente = []
        attente.append ((GHinit , DBinit))
        while attente != [] :
            #afficher2(Laby, attente, Matrou)
            (GH,DB) = attente.pop()
            if not( DB[0]-GH[0] >= 2 and DB[1]-GH[1] >= 2 and not(Matrou[GH[0]+1 : DB[0]-1 +1, GH[1] ] + Matrou[GH[0]+1 : DB[0]-1 +1, DB[1] ] >= 1).all() ) :
                pass
            elif DB[1]-GH[1] >= DB[0]-GH[0] :
                colonne = mur_Vertical(GH, DB, Laby, Matrou)
                attente.append((GH, (DB[0], colonne-1)))
                attente.append(((GH[0], colonne+1), DB))
     
            else :
                ligne = mur_Horizontal(GH, DB, Laby, Matrou)
                attente.append((GH, (ligne-1, DB[1])))
                attente.append(((ligne+1, GH[1]), DB))
     
     
     
    labyrinthe_Final(20,3)

  2. #2
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 851
    Billets dans le blog
    1
    Par défaut
    Bonjour
    J'aime bien ton code. Il a quelques défauts (ex attente.append ((GHinit , DBinit)) sur une liste vide => autant créer la liste avec ces valeurs ; ou bien while attente != [] qui s'écrit simplement while attente) mais c'est juste un manque d'expérience.

    Alors pour ton souci j'ai mis des print() dans la fonction "labyrinthe_Final()" et j'ai vu que le blocage se passait au niveau de la fonction "mur()" (qui ne renvoie rien donc qui n'a pas besoin d'être récupérée par une variable "img" que tu n'utilises pas ensuite).
    Dans la fonction "mur()" il est évident que le souci se situe au niveau de la boucle qui ne s'arrête jamais. Et pourquoi elle ne s'arrête jamais? Parce qu'à un moment une des fonctions "mur_vertical" ou "mur_horizontal" passe en boucle infinie, très certainement dans leurs while respectifs. Donc tu continues, du print() pour vérifier les tests que tu y fais...

    En fait j'ai continué et j'ai vu que ça se passait dans "mur_vertical()". J'y ai rajouté...
    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    print("test1:", Matrou[GH[0], rdColonne])
    print("test2:", Matrou[DB[0], rdColonne])
    print("test3:",  rdColonne)
    ... et j'obtiens à un moment un blocage sur test2: 1. Donc à un moment le test Matrou[DB[0], rdColonne] == 1 passe à True et ensuite ne change plus => boucle infinie
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  3. #3
    Membre habitué
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2023
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2023
    Messages : 13
    Par défaut
    Merci beaucoup pour ta réponse,

    J'avais compris que le problème venait soi de mur_horizontal() soit de mur_vertical(), mais je ne comprends pas pourquoi l'une de ces deux fonctions, codées sur la même base, fonctionne et l'autre non. Saurais tu me dire comment résoudre cette boucle infinie ? J'essaie differentes solution mais aucune n'aboutit a quelque chose...

    Bonne soirée.

  4. #4
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 851
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par JheyFaid Voir le message
    mais je ne comprends pas pourquoi l'une de ces deux fonctions, codées sur la même base, fonctionne et l'autre non. Saurais tu me dire comment résoudre cette boucle infinie ?
    Il faudrait que je comprenne un peu mieux la logique initiale et ces "DB" et "GH" ("Droite-Bas" et "Gauche-Haut" ?)
    Alors c'est vrai que les fonctions sont codées de façon similaires (ou plutôt symétriques) mais peut-être que la symétrie n'a pas été respectée au départ. Comme je le dis j'ai pas étudié le détail des valeurs donc je ne fais qu'une hypothèse mais imaginons que la position minimale (ici 0) soit incluse mais que la position maximale (20 pour un labyrinthe 20x20) ne le soit pas?
    Donc regardons ce que ça entraine sur les deux tests
    • mur horizontal: Matrou[rdLigne, GH[1]] == 1 or Matrou[rdLigne, DB[1]] == 1
    • mur vertical: Matrou[GH[0], rdColonne] == 1 or Matrou[DB[0], rdColonne]

    Alors imaginons que GH[1] (valeur de droite du tuple du premier test) représente une valeur exclue mais que rdColonne (valeur là aussi de droite du tuple du second test) représente une valeur inclue ou autre dissonance du même genre... En fait j'ai l'impression que ça s'apparente à un souci style var[x:y] où "x" est inclus mais que "y" est exclu dans le slice. Peut-être donc revérifier les valeurs extrèmes dans un labyrinthe n*n (qui vont de 0 à n-1) en se souvenant bien que généralement la valeur de gauche est considérée comme incluse mais pas celle de droite...

    Autre indice: ces "-2" que tu as mis dans certaines expressions semblent signifier que tu exclus les bords (pour un labyrinthe de 20 tu iras de 1 inclus à 18 inclus, en excluant le bord gauche 0 et bord droit 19). Ok ça semble correct. Mais as-tu pris en compte ces exclusions dans les fonctions "mur_xxx" ? Surtout "mur_vertical" où on retrouve à droite ce qui ressemble à une dimension et non pas un indice... Je pense effectivement que tu as dû utiliser quelque part une valeur de dimension là où il aurait fallu une valeur d'indice (et il y a systématiquement un écart de "1" entre les deux => pour une dimension "20" un indice ne va que jusqu'à 19)
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  5. #5
    Membre habitué
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2023
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2023
    Messages : 13
    Par défaut
    Citation Envoyé par Sve@r Voir le message
    Il faudrait que je comprenne un peu mieux la logique initiale et ces "DB" et "GH" ("Droite-Bas" et "Gauche-Haut" ?)
    Effectivement les couples GH et DB représentent les couples de coordonées en haut à gauche et en bas a droite des rectangles à "découper".

    Citation Envoyé par Sve@r Voir le message
    je ne fais qu'une hypothèse mais imaginons que la position minimale (ici 0) soit incluse mais que la position maximale (20 pour un labyrinthe 20x20) ne le soit pas?
    Je pense avoir réglé ce problème dans une version différente, c'est pour ça que j'appelle la fonction mur en avec GH = (1,1) et DB=(n-2,n-2), le labyrinthe allant de 0 a n-1 et en enlevant 1 de chaque côté pour les murs.


    Citation Envoyé par Sve@r Voir le message
    Peut-être donc revérifier les valeurs extrèmes dans un labyrinthe n*n (qui vont de 0 à n-1) en se souvenant bien que généralement la valeur de gauche est considérée comme incluse mais pas celle de droite...
    Je vais rejeter un œil aux différentes documentations des fonctions que j'ai utilisé pour vérifier que j'ai bien fait en fonction de ça.

    Citation Envoyé par Sve@r Voir le message
    Ces "-2" que tu as mis dans certaines expressions semblent signifier que tu exclus les bords
    Effectivement, ça peut poser des problème mais je pense ne les avoir utilisés que dans les fonctions d'initialisation pour lancer les fonctions murs. J'avais précédemment mis les moins deux au sein des fonctions murs mais a chaque tour de boucle la case rétrécissait a cause des -2, je pensais avoir résolu le problème en les plaçant dans les fonctions d'initialisation.

    En tout cas un grand merci pour ton implication, je vais désormais me penchait sur ces fonctions qui prennent jusqu'à borne supérieure -1 !

  6. #6
    Membre habitué
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2023
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2023
    Messages : 13
    Par défaut
    Après avoir vérifié toutes mes fonctions, le code et le gestion des indices me paraît bonne. J'ai comparé l'évolution du labyrinthe avec ce que le programme devrait faire (a l'écrit) eu le programme fait bien ce qu'il est censé faire jusqu'au moment où il s'arrête d'un coup...

  7. #7
    Membre confirmé
    Homme Profil pro
    Ingénieur Système
    Inscrit en
    Novembre 2019
    Messages
    22
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Mayenne (Pays de la Loire)

    Informations professionnelles :
    Activité : Ingénieur Système

    Informations forums :
    Inscription : Novembre 2019
    Messages : 22
    Par défaut
    Bonjour,

    Je pense que ton problème vient de la condition
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    if not( DB[0]-GH[0] >= 2 and DB[1]-GH[1] >= 2 and not(Matrou[GH[0]+1 : DB[0]-1 +1, GH[1] ] + Matrou[GH[0]+1 : DB[0]-1 +1, DB[1] ] >= 1).all() ) :
    Il faut que la distance entre les bornes soit strictement supérieur à 2 (3 minimum)
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    if not( DB[0]-GH[0] > 2 and DB[1]-GH[1] > 2 and not(Matrou[GH[0]+1 : DB[0]-1 +1, GH[1] ] + Matrou[GH[0]+1 : DB[0]-1 +1, DB[1] ] >= 1).all() ) :
    Car ensuite tu tire un nombre aléatoire entre GH[0]+1,DB[0]-1 ou GH[1]+1,DB[1]-1 et si tu n'as qu'une distance de 2. Tu tombes toujours sur le même nombre...

    Chez moi ça fonctionne avec cette modification.

  8. #8
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 851
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par AznarAkeba Voir le message
    Chez moi ça fonctionne avec cette modification.
    Joli
    Chez-moi aussi. Je viens de générer un 50x50 sans souci (j'ai tenté 100 mais bon là ça partait dans des délais...)

    Citation Envoyé par JheyFaid Voir le message
    ...
    Maintenant que grâce à AznarAkeba le souci est réglé, quelques détails
    • concernant les noms de variable, soit on utilise le camel case (exemple "labyrintheFinal"), soit le snake case (exemple "labyrinthe_final") mais on ne fait pas un mix des deux (ie "labyrinthe_Final")
    • pas d'espace devant les parenthèses lors des appels => for i in range(n) et non pas for i in range (n). En revanche, il faut un espace après la virgule => Laby[0, i] = 1 et non Laby[0,i] = 1.
    • Pour la fin du code, je proposerais cette modification
      Code python : Sélectionner tout - Visualiser dans une fenêtre à part
      1
      2
      3
      if __name__ == "__main__":
      	import sys
      	labyrinthe_Final(int(sys.argv[1]) if len(sys.argv) > 1 else 20)
      Ainsi on peut appeler le programme en lui passant la taille en paramètre tout en offrant la possibilité de l'importer dans un autre code. Et j'ai viré le paramètre "fps" de la fonction "labyrinthe_Final" qui n'était pas utilisé.
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  9. #9
    Membre habitué
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2023
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2023
    Messages : 13
    Par défaut
    Un grand merci a vous deux pour avoir résolu mon problème !

    Citation Envoyé par Sve@r Voir le message
    [*]concernant les noms de variable, soit on utilise le camel case (exemple "labyrintheFinal"), soit le snake case (exemple "labyrinthe_final") mais on ne fait pas un mix des deux (ie "labyrinthe_Final")[*]pas d'espace devant les parenthèses lors des appels => for i in range(n) et non pas for i in range (n). En revanche, il faut un espace après la virgule => Laby[0, i] = 1 et non Laby[0,i] = 1.
    Je vais changer ça merci, j'avoue que je faisais un peu au feeling pour les noms de fonctions/variables en fonction de ce que j'ai déjà vu comme code ...
    Citation Envoyé par Sve@r Voir le message
    [*]Pour la fin du code, je proposerais cette modification
    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    if __name__ == "__main__":
    	import sys
    	labyrinthe_Final(int(sys.argv[1]) if len(sys.argv) > 1 else 20)
    Je ne comprends pas cette partie, je n'ai pas encore vu les codes avec __main__ et pour le FPS, je l'ai mis en paramètres car j'ai une autre fonction me permettant de créer un gif du labyrinthe que je n'avais pas posté ici !

    Encore merci a vous !

  10. #10
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 851
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par JheyFaid Voir le message
    Je ne comprends pas cette partie, je n'ai pas encore vu les codes avec __main__
    Cela permet d'utiliser un programme de façon indépendante (on l'exécute directement) ou bien en tant que "module", c'est à dire que ses fonctions sont simplement incorporées dans un autre qui peut les utiliser comme il le sent.
    Exemple: script "toto.py"
    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    def carre(n):
    	return n * n
     
    if __name__ == "__main__":
    	for i in range(10):
    		print(i, carre(i))

    Si tu appelles (exécutes) directement ce programme "toto.py", la variable interne Python "__name__" a pour valeur la chaine littérale "__main__" et la partie qui suit le "if" est exécutée. Mais si un autre programme veut utiliser la fonction "carre()" alors il peut importer toto.py. Dans ce cas, lorsque l'import se fait, tout le code de "toto.py" est exécuté (la fonction "carre()" est alors définie dans l'autre programme) ; mais la variable interne Python "__name__" n'a pas pour valeur la chaine littérale "__main__" et la partie qui suit le "if" est alors ignorée.
    Et comme la fonction "carre()" a été définie, elle est alors connue. Ainsi l'autre programe peut l'exécuter. Mais il n'aura pas été perturbé, lors de l'import, par l'affichage des 10 premiers entiers avec leurs carrés respectifs.
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  11. #11
    Membre habitué
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2023
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2023
    Messages : 13
    Par défaut
    Merci pour cette précision !

  12. #12
    Membre habitué
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2023
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2023
    Messages : 13
    Par défaut
    Re-bonjour,

    Je pensais que ce sujet était clos, mais finalement nonje me suis appercu que me en corrigeant cette errreur d'inégalité, il y a toujours un labyrinthe qui n'est pas renvoyé 1 fois sur 5 je dirais.
    J'ai beaucoup réflechi a ce problème avant de revenir demander de l'aide ici mais je n'ai rien trouvé.
    Je vous rappelle mon code :

    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
     
    import matplotlib.pyplot as plt
    import numpy as np
    import random as rd
    import matplotlib.animation as animation
    import matplotlib.colors as colors
     
     
    colorlist=["white", "black", "blue", "red"]
    newcmp = colors.LinearSegmentedColormap.from_list('testCmap', colors=colorlist, N=256)
     
     
    ########################################################
     
     
    #GH = (ligne coin interieur haut gauche, colonne coin interieur haut gauche)
    #DB = (ligne coin interieur bas droit, colonne coin interieur bas droit)
    #matrou = matrice de 0 de taille n*n ou les 1 sont les endroits ou le script ne peut mettre ni ligne ni colonne sinon il refermerait un trou
     
     
    ########################################################
     
     
     
     
    def init_labyrinthe(n) :
        """Initialisation du labyrinthe : pose des murs exterieurs"""
        laby = np.zeros((n, n), dtype = int)
        for i in range(n):
            laby[0, i] = 7
            laby[n-1, i] = 7
            laby[i, 0] = 7
            laby[i, n-1] = 7
        return laby
     
     
    ########################################################
     
     
    def matrice_trou (n) :
        """Création de la Matrice receuillant l'emplacement des Trous"""
        matrou = np.zeros((n, n), dtype = int)
        return matrou
     
     
     
     
    ########################################################    
     
    def afficher (labyrinthe):
        """Permet l'affichage de la matrice sous forme de labyrinthe"""
        plt.imshow(labyrinthe, cmap=newcmp)
        plt.colorbar()
        plt.axis('off')
        plt.show()
     
     
    ########################################################
     
     
    def afficher2 (labyrinthe ,matrou):
        """Permet l'affichage de la matrice sous forme de labyrinthe
            et aussi de l'affichage de la matrice de trou"""
        plt.imshow(labyrinthe, cmap='GnBu')
        plt.axis('on')
        plt.imshow(matrou, cmap='Greys')
        plt.imshow(labyrinthe, cmap='GnBu', alpha=0.6)
        plt.axis('off')
        plt.show()
     
     
    ########################################################
     
     
    def entree_sortie (n, matrou, laby, ligne) :
        """Definition de l'entrée et la sortie"""
        Debut = rd.randint(1, ligne-1)
        laby[Debut, 0] = 20
        matrou[Debut, 1] , matrou[Debut, 0] = 1,1
     
        Arrivee = rd.randint(ligne+1, n-2)
        laby[Arrivee, n-1] = 13
        matrou[1, Arrivee],matrou[0, Arrivee] = 1,1
     
    ########################################################
    ################### labyrinthe n * n ###################
    ####################### itératif #######################
    ########################################################
     
     
     
    def labyrinthe_final (n) :
        """Creation du labyrinthe de taille n"""
        matrou = matrice_trou(n)
        laby = init_labyrinthe(n)
        mur((1, 1), (n-2, n-2), laby, matrou)
        afficher(laby)
    #    afficher2(laby, matrou)
     
    ########################################################
     
    def mur_horizontal(GH, DB, laby, matrou):
        """Création de mur horizontal
            GH = (ligne, colonne)"""
        rd_ligne = 0
        while matrou[rd_ligne, GH[1]] == 1 or matrou[rd_ligne, DB[1]] == 1 or rd_ligne == 0:
            rd_ligne = rd.randint(GH[0]+1, DB[0]-1)
        rd_trou = rd.randint(GH[1], DB[1])
        laby[rd_ligne, GH[1]:DB[1]+1] = 7
        laby[rd_ligne, rd_trou] = 0
        matrou[rd_ligne-1:rd_ligne+1 +1, rd_trou] = 1
        return rd_ligne
     
     
     
     
    def test_mur_horizontal():
        test = init_labyrinthe(20)
        mat = matrice_trou(20)
        ligne = mur_horizontal((1, 1),(18,1 8), test, mat)
        test[1:ligne, 1:19] = 2
        test[ligne+1:19, 1:19] = 3
        afficher(test)
     
    ########################################################
     
     
    def mur_vertical(GH, DB, laby, matrou):
        """Création de mur vertical
            GH = (ligne, colonne)"""
        rd_colonne = 0
        while matrou[GH[0], rd_colonne] == 1 or matrou[DB[0], rd_colonne] == 1 or rd_colonne == 0:
            rd_colonne = rd.randint(GH[1]+1, DB[1]-1)
        rd_trou = rd.randint(GH[0], DB[0])
        laby[GH[0]:DB[0]+1, rd_colonne] = 7
        laby[rd_trou, rd_colonne] = 0
        matrou[rd_trou, rd_colonne-1:rd_colonne+1 +1] = 1
        return rd_colonne
     
     
     
     
    def test_mur_vertical():
        test = init_labyrinthe(20)
        mat = matrice_trou(20)
        colonne = mur_vertical((1,1),(18,18),test,mat)
        test[1:19,1:colonne] = 2
        test[1:19,colonne+1:19] =3
        afficher(test)
     
    ########################################################
     
     
    def mur (GHinit, DBinit, laby, matrou):
        """creation de mur par itération en appellant mur_vertical et mur_horizontal"""
        n = len(matrou[0])
        attente = []
        """premier passage pour initialisation debut/arrivée"""
        ligne = mur_horizontal(GHinit, DBinit, laby, matrou)
        attente.append((GHinit, (ligne-1, DBinit[1])))
        attente.append(((ligne+1, GHinit[1]), DBinit))
        entree_sortie(n,matrou,laby,ligne)
        while attente :
            #afficher2(laby, matrou)
            (GH,DB) = attente.pop()
            if not( DB[0]-GH[0] > 2 and DB[1]-GH[1] > 2 and not(matrou[GH[0]+1 : DB[0]-1 +1, GH[1]] + matrou[GH[0]+1 : DB[0]-1 +1, DB[1]] >= 1).all()) :
                pass
            elif DB[1]-GH[1] >= DB[0]-GH[0] :
                colonne = mur_vertical(GH, DB, laby, matrou)
                attente.append((GH, (DB[0], colonne-1)))
                attente.append(((GH[0], colonne+1), DB))
     
     
            else :
                ligne = mur_horizontal(GH, DB, laby, matrou)
                attente.append((GH, (ligne-1, DB[1])))
                attente.append(((ligne+1, GH[1]), DB))
     
     
    labyrinthe_final(50)

    Mon but serait de réaliser des labyrinthes récursif (bien que ici je le réalise en itératif) assez grand, or avec ce probleme dès 20*20 cela pose probleme, et je ne pense pas que la capicité mémoire soit le probléme.
    Merci beaucoup

  13. #13
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 851
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par JheyFaid Voir le message
    J'ai beaucoup réflechi a ce problème avant de revenir demander de l'aide ici mais je n'ai rien trouvé.
    Envisagerais-tu de revoir entièrement l'algorithme? J'ai un peu regardé sur le net et j'ai trouvé un algo nommé "fusion aléatoire" qui m'a l'air assez bien pensé => https://fr.wikipedia.org/wiki/Mod%C3...7un_labyrinthe

    Citation Envoyé par JheyFaid Voir le message
    Mon but serait de réaliser des labyrinthes récursif (bien que ici je le réalise en itératif) assez grand, or avec ce probleme dès 20*20 cela pose probleme, et je ne pense pas que la capicité mémoire soit le probléme.
    La récursivité est une fausse "bonne solution". Si la solution itérative est possible, elle est toujours bien meilleure.
    La récursivité c'est "mémoriser le contexte actuel puis créer un contexte neuf en plus réduit pour pouvoir trouver la solution avant de la renvoyer au contexte précédent". Or toute cette opération de "mémorisation" est super lourde pour l'OS. C'est pourquoi dans Python elle est limitée à 1000
    Exemple def fact(n): return (n or 1) if n <= 2 else fact(n-1): Cette fonction tourne jusqu'à 999 puis plante à 1000 en RecursionError.

    Donc tu as une solution itérative, en plus solution qui "simule" la récursivité via ta pile et c'est super, conserve-la. Tu bénéficies des avantages de la récursivité sans ses inconvénients (en fait tu ne mémorises que ce qui est utile et non pas tout le contexte du programme).
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  14. #14
    Membre habitué
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2023
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2023
    Messages : 13
    Par défaut
    Citation Envoyé par Sve@r Voir le message
    Envisagerais-tu de revoir entièrement l'algorithme? J'ai un peu regardé sur le net et j'ai trouvé un algo nommé "fusion aléatoire" qui m'a l'air assez bien pensé
    Oui, je pourrais eventuellement recommencer mon projet avec cet algorithme, si celui ci est plus efficace mais je n'ai pas envie d'abandonner celui-ci sans savoir pourquoi il ne fonctionne pas.

    Citation Envoyé par Sve@r Voir le message
    Donc tu as une solution itérative, en plus solution qui "simule" la récursivité via ta pile et c'est super, conserve-la. Tu bénéficies des avantages de la récursivité sans ses inconvénients (en fait tu ne mémorises que ce qui est utile et non pas tout le contexte du programme).
    C'est exactement pour cela que j'ai choisi cette solution, j'avais commencé avec un algo recursif mais celui ci ne fonctionnait pas, justement a cause de la lourdeur du code et de ce qui etait demandé, or celui ci me parrait bien niveau memoire. Apres je pense que la complexité de cet algo est tout sauf la meilleure et que ca peut aussi contribuer au probleme plus tard, mais étant donné que la géneration fonctionne de temps en temps sur les grosses dimensions, je ne pense pas que la complexité soit le probleme.

  15. #15
    Membre habitué
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2023
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2023
    Messages : 13
    Par défaut
    J'ai suivi tes conseils Sve@r et j'ai consacré ma soirée a refaire cet algo, cela donne :

    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    import matplotlib.pyplot as plt
    import numpy as np
    import random as rd
    import matplotlib.animation as animation
    import matplotlib.colors as colors
     
    colorlist=["white", "black", "limegreen", "red"]
    cmp_laby = colors.LinearSegmentedColormap.from_list('testCmap', colors=colorlist, N=256)
     
    ########################################################
     
    #mat_mur = binaire de 2^0 = mur gauche
    #                     2^1 = mur haut
    #                     2^2 = mur droit
    #                     2^3 = mur bas
     
    ########################################################
     
    def afficher (labyrinthe):
        """Permet l'affichage de la matrice sous forme de labyrinthe"""
        plt.imshow(labyrinthe, cmap=cmp_laby)
        plt.colorbar()
        plt.axis('off')
        plt.show()
     
    ########################################################
     
    def init (n) :
        m = (n-1)//2
        laby = np.zeros((m, m), dtype = int)
        for i in range(m):
            for j in range(m) :
                laby[i,j] = i*m + j
     
        mat_mur = np.zeros((n,n), dtype = int)
        for i in range(0, n, 2):
            mat_mur[i, 0:n] = 1
            mat_mur[0:n, i] = 1
        return laby, mat_mur, m
     
    #########################################################
     
    def crea_mur(n) :
        '''orientation : (gauche/droite, haut/bas)
            (-1,0)=gauche, (1,0)=droite, (0,-1)=haut, (0,1)=bas'''
        laby, mat_mur, m = init(n)
        maxi = m*m - 1
        compteur = 0
        while compteur < maxi :
            rd_ligne, rd_colonne = rd.randint(0, m-1), rd.randint(0, m-1)
            orientation = rd.choice([(-1, 0), (1, 0), (0, -1), (0, 1)])
            coordonnees = addition((rd_ligne, rd_colonne), orientation)
            if coordonnees[0]<0 or coordonnees[0]>m-1 or coordonnees[1]<0 or coordonnees[1]>m-1 :
                continue
            rd_nombre, coord_nombre = laby[rd_ligne, rd_colonne], laby[coordonnees[0],coordonnees[1]]
            if rd_nombre == coord_nombre :
                continue
            else:
                petit = min(rd_nombre, coord_nombre)
                grand = max(rd_nombre, coord_nombre)
                coord_mur = addition((1+2*rd_ligne,1+2*rd_colonne), orientation)
                mat_mur[coord_mur[0], coord_mur[1]] = 0
                for (i,j) in [(i, j) for i in range(m) for j in range(m) if laby[i, j] == grand] :
                    laby[i, j] = petit
                compteur += 1
    #         afficher(mat_mur)
    #         afficher(laby)
        return mat_mur
    #########################################################
     
    def addition(couple1, couple2) :
        return [e1+e2 for e1, e2 in zip(couple1, couple2)]
     
    #########################################################
     
    def labyrinthe_final(n):
        if n%2 == 0 :
            n = n+1
        mat_mur = crea_mur(n)
        entree_sortie(n, mat_mur)
        afficher(mat_mur)
     
    #########################################################
     
    def entree_sortie (n, matrice_mur) :
        """Definition de l'entrée et la sortie"""
        debut = rd.randint(1, n-2)
        while matrice_mur[debut,1] == 1 :
            debut = rd.randint(1, n-2)
        matrice_mur[debut,0] = 3
     
        fin = rd.randint(1, n-2)
        while matrice_mur[fin,n-2] == 1 :
            fin = rd.randint(1, n-2)
        matrice_mur[fin, n-1] = 4
     
    labyrinthe_final(15)

    Et ca marche NICKEL !

  16. #16
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 851
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par JheyFaid Voir le message
    Et ca marche NICKEL !
    Exact. J'ai généré des labyrinthes de 150 sans souci (illisibles mais fonctionnels).

    Quelques détails
    • je ne pige pas pourquoi tu forces le labyrinthe à être toujours impair avec if n%2 == 0: n = n+1 mais ça peut s'écrire n=n+(n-1)%2.
    • return [e1+e2 for e1, e2 in zip(couple1, couple2)] => return list(map(sum, zip(couple1, couple2))) (et encore retourner une liste n'est pas forcément nécessaire si le retour n'a pas à être modifié => return tuple(map(sum, zip(couple1, couple2))) (toujours préférer le tuple à la liste si pas besoin de modifier son contenu)
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  17. #17
    Membre habitué
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2023
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2023
    Messages : 13
    Par défaut
    Je commence par réaliser une grille sur le labyrinthe une case sur deux, donc si le labyrinthe est pair ça pose problème

  18. #18
    Membre habitué
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2023
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2023
    Messages : 13
    Par défaut Demande d'idée
    Bonjour,
    je mène a bien mon projet de labyrinthe, je reviens ici pour vous demander des idées, je m'explique :
    j'arrive desormais a réaliser des labyrinthes de toutes tailles en ajoutant des labyrinthes de 100*100 les uns aux autres. Le probleme est que pour les relier c'est plus compliqué :

    j'obtiens dont une grille de labyrinthe et au niveau des jonctions, je crée des plus petits labyrinthes de 7*100 que j'incorpore au milieu.
    Nom : SyCOJ - Copie (1).png
Affichages : 876
Taille : 879,7 Ko

    Le problème étant que cette méthode ne garantit en rien un unique chemin, or c'est ce qui m'interesse...

    Je viens donc vous demander si vous avez une idée me permettant de garantir cet unique chemin ?

    PS : voici mon code (attention il est tres long et non necessaire pour comprendre mon probleme) :

    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    303
    304
    305
    306
    307
    308
    309
    310
    311
    312
    313
    314
    315
    316
    317
    318
    319
    320
    321
    322
    323
    324
    325
    326
    327
    328
    329
    330
    331
    332
    333
    334
    335
    336
    337
    338
    339
    340
    341
    342
    343
    344
    345
    346
    347
    348
    349
    350
    351
    352
    353
    354
    355
    356
    357
    358
    359
    360
    361
    362
    363
    364
    365
    366
    367
    368
    369
    370
    371
    372
    373
    374
    375
    376
    377
    378
    379
    380
    381
    382
    383
    384
    385
    386
    387
    388
    389
    390
    391
    392
    393
    394
    395
    396
    397
    398
    399
    400
    401
    402
    403
    404
    405
    406
    407
    408
    409
    410
    411
    412
    413
    414
    415
    416
    417
    418
    419
    420
    421
    422
    423
    424
    425
    426
    427
    428
    429
    430
    431
    432
    433
    434
    435
    436
    437
    438
    439
    440
    441
    442
    443
    444
    445
    446
    447
    448
    449
    450
    451
    452
    453
    454
    455
    456
    457
    458
    459
    460
    461
    462
    463
    464
    465
    466
    467
    468
    469
    470
    471
    472
    473
    474
    475
    476
    477
    478
    479
    480
    481
    482
    483
    484
    485
    486
    487
    488
    489
    490
    491
    492
    493
    494
    495
    496
    497
    498
    499
    500
    501
    502
    503
    504
    505
    506
    507
    508
    509
    510
    511
    512
    513
    514
    515
    516
    517
    518
    519
    520
    521
    522
    523
    524
    525
    526
    527
    528
    529
    530
    531
    532
    533
    534
    535
    536
    537
    538
    539
    540
    541
    542
    543
    544
    545
    546
    547
    548
    549
    550
    551
    552
    553
    554
    555
    556
    557
    558
    559
    560
    561
    562
    563
    564
    565
    566
    567
    568
    569
    570
    571
    572
    573
    574
    575
    576
    577
    578
    579
    580
    581
    582
    583
    584
    585
    586
    587
    588
    589
    590
    591
    592
    593
    594
    595
    596
    597
    598
    599
    600
    601
    602
    603
    604
    605
    606
    607
    608
    609
    610
    611
    612
    613
    614
    615
    616
    617
    618
    619
    620
    621
    622
    623
    624
    625
    626
    627
    628
     import matplotlib.pyplot as plt
    import matplotlib.animation as animation
    import matplotlib.colors as colors
    import numpy as np
    import random as rd
    import string
    from collections import deque
    from matplotlib.gridspec import GridSpec
    import time
     
    cmp_laby = colors.LinearSegmentedColormap.from_list('testCmap', colors=["blue", "black", "white", "limegreen",  "red"], N=256)
    cmp_laby_bis = colors.LinearSegmentedColormap.from_list('testCmapBis', colors=["black", "white", "limegreen",  "red"], N=256)
    cmp_tempo = colors.LinearSegmentedColormap.from_list('tempo', colors=["black", "white"], N=256)
     
    ########################################################
    #################### Affichage #########################
    ########################################################
     
    def afficher (labyrinthe):
        """Permet l'affichage de la matrice sous forme de labyrinthe"""
        plt.figure(figsize=(50,50))
        plt.imshow(labyrinthe, cmap=cmp_tempo)
        plt.axis('off')
    #     plt.colorbar()
        plt.show()
     
    ########################################################
     
    def afficher2 (img, long, sauvegarde,  fps_vid=500):
        """Permet l'affichage de la matrice sous forme de labyrinthe
            animation"""
        maxi = max(long[0],long[1],long[2])
        for i in range(3):
            for _ in range(long[i],maxi) :
                img[i].append(img[i][long[i]-1])
        titre = ''.join(rd.choice(string.ascii_letters) for x in range(10))
        fig = plt.figure(figsize=(300,100))
        gs = fig.add_gridspec(1, 3)
        ax0 = fig.add_subplot(gs[0, 0])
        plt.axis('off')
        ax1 = fig.add_subplot(gs[0, 1])
        plt.axis('off')
        ax2 = fig.add_subplot(gs[0, 2])
        plt.axis('off')
        # Initialisation des graphiques
        im0 = ax0.imshow(img[0][0], cmap=cmp_laby_bis)
        im1 = ax1.imshow(img[1][0], cmap=cmp_laby_bis)
        im2 = ax2.imshow(img[2][0], cmap=cmp_laby_bis)
     
        # Fonction d'animation
        def update(frame):
            if frame % fps_vid == 0:
                print( '.', end ='' )
            im0.set_data(img[0][frame])
            im1.set_data(img[1][frame])
            im2.set_data(img[2][frame])
     
        # Création de l'animation
        anim = animation.FuncAnimation(fig, update, frames = max(long[0],long[1],long[2]), interval = 1000 / fps_vid,repeat = True)
        if sauvegarde:
            print(titre)
            anim.save('Laby/'+titre +'.gif',writer = animation.PillowWriter(fps = fps_vid))
        # Affichage du graphique
        plt.show()
     
    ########################################################
     
    def afficher3 (labyrinthe, longueur, sauvegarde):
        """Permet l'affichage de la matrice sous forme de labyrinthe"""
    #     px = 1/plt.rcParams['figure.dpi']  # pixel in inches
        plt.figure(figsize=(200,200))
        plt.imshow(labyrinthe, cmap=cmp_tempo)
        plt.axis('off')
    #     plt.colorbar()
        if sauvegarde : 
            plt.title('Nombre de cases visitées : ' + str(longueur), fontsize = len(labyrinthe)/3)
            titre = ''.join(rd.choice(string.ascii_letters) for x in range(5))
            plt.savefig('Laby/'+titre+'.png')
            print('Telechargement : ok \n Titre : '+titre)
        plt.show()
     
    ########################################################
     
    def afficher4 (liste_laby, direct, longueur, sauvegarde, direct_cond):
        """Permet l'affichage de la matrice sous forme de labyrinthe"""
        n = len(liste_laby)
        nom = ['DFS', 'BFS', 'Suivre droite']
        plt.figure(figsize=(50*n,50))
        for i in range(n) :
            plt.subplot(1, n, i+1)
            plt.title(nom[i]+", cases = " + str(longueur[i]),fontsize = len(liste_laby[0]))
            plt.imshow(liste_laby[i], cmap=cmp_laby)
            if direct_cond :
                plt.imshow(direct, cmap='Greys', alpha=.4)
            plt.axis('off')
    #     plt.colorbar()
        if sauvegarde : 
            titre = ''.join(rd.choice(string.ascii_letters) for x in range(5))
            plt.savefig('Laby/'+titre+'.png')
            print('Telechargement : ok \n Titre : '+titre)
        plt.show()
     
    ########################################################
     
    def afficher5 (labyrinthe, titre, sauvegarde):
        """Permet l'affichage de la matrice sous forme de labyrinthe avec fleche"""
    #     px = 1/plt.rcParams['figure.dpi']  # pixel in inches
        plt.figure(figsize=(200,200))
        plt.imshow(labyrinthe, cmap=cmp_laby_bis)
        plt.axis('off')
    #     plt.colorbar()
        if sauvegarde : 
            plt.title(titre, fontsize = len(labyrinthe)/3)
            titre = ''.join(rd.choice(string.ascii_letters) for x in range(5))
            plt.savefig('Laby/'+ titre +'.png')
            print('Telechargement : ok \n Titre : ' + titre)
        plt.show()
     
    ########################################################
    #################### Algorithme ########################
    ########################################################
     
    couleur_arrivee = 5000
    couleur_debut = 3000
    couleur_vide = 1700
    ind = 7
     
    def labyrinthe_final(n, p, affichage=True, sauvegarde = False, anim = False):
        """Fonction mère, crée le labyrinthe et le resout de différentes manieres
            Attention : n et p impairs"""
        if n%2 == 0 :
            n = n+1
        if p%2 == 0 :
            p = p+1
     
        mat_mur = crea_mur(n, p, False)
     
        mat_mur, debut, fin = entree_sortie(n, p, mat_mur)
    #     afficher5(mat_mur,'',False)
    #-----------DFS-----------
        dfs_chemin, predecesseur = dfs(mat_mur, debut, n, p)
        if affichage : 
            dfs_laby, dfs_archive = transformation(dfs_chemin, mat_mur, debut, fin)
            dfs_direct = chemin_direct(debut, fin, n, p, predecesseur)
    #-----------BFS-----------
        bfs_chemin, predecesseur = bfs(mat_mur, debut, n, p)
        if affichage :
            bfs_laby, bfs_archive = transformation(bfs_chemin, mat_mur, debut, fin)
    #--------à droite---------
        droite_chemin, predecesseur = a_droite(mat_mur, debut, n, p)
        if affichage :
            droite_laby, droite_archive = transformation(droite_chemin, mat_mur, debut, fin)
     
        longueur = [len(dfs_chemin), len(bfs_chemin), len(droite_chemin)]
        if affichage : 
            if not anim :
                afficher4([dfs_laby, bfs_laby, droite_laby], dfs_direct, longueur, sauvegarde)
            else :
                afficher2([dfs_archive, bfs_archive, droite_archive], longueur, sauvegarde)
     
        return longueur
     
    ########################################################
     
    def dfs (labyrinthe, debut, n, p) :
        """les sommets sont sous la forme [ligne, colonne]
            renvoie une liste des sommets visités"""
        attente = []
        predecesseur = {}
        chemin = []
        laby = np.copy(labyrinthe)
        depart = [debut, ind]
        attente.append(depart)
        while attente != []:
            sommet = attente.pop()
            if laby[sommet[0], sommet[1]] == couleur_vide or laby[sommet[0], sommet[1]] == couleur_debut :
                laby[sommet[0], sommet[1]] = 5
                chemin.append(sommet)
                for e in [[sommet[0]+1, sommet[1]],[sommet[0]-1, sommet[1]],[sommet[0], sommet[1]+1],[sommet[0], sommet[1]-1]] :
                    if e[0] >=n or e[0] < 0 or e[1] >= p + ind or e[1] < ind :
                        pass
                    elif laby[e[0], e[1]] == couleur_vide :
                        predecesseur[(e[0], e[1])] = (sommet[0], sommet[1])
                        attente.append(e)
    #                     afficher(chemin)
                    elif laby[e[0], e[1]] == couleur_arrivee :
                        predecesseur[(e[0], e[1])] = (sommet[0], sommet[1])
                        chemin.append(e)
                        return chemin, predecesseur
     
    ########################################################
     
    def bfs (labyrinthe, debut, n, p) :
        """les sommets sont sous la forme [ligne, colonne]
            renvoie une liste des sommets visités"""
        attente = deque()
        chemin = []
        predecesseur = {}
        laby = np.copy(labyrinthe)
        depart = [debut, ind]
        attente.append(depart)
        while attente != deque():
            sommet = attente.popleft()
            if laby[sommet[0], sommet[1]] == couleur_vide or laby[sommet[0], sommet[1]] == couleur_debut :
                laby[sommet[0], sommet[1]] = 5
                chemin.append(sommet)
                for e in [[sommet[0]+1, sommet[1]],[sommet[0]-1, sommet[1]],[sommet[0], sommet[1]+1],[sommet[0], sommet[1]-1]] :
                    if e[0] >=n or e[0] < 0 or e[1] >= p + ind or e[1] < ind :
                        pass
                    elif laby[e[0], e[1]] == couleur_vide :
                        predecesseur[(e[0], e[1])] = (sommet[0], sommet[1])
                        attente.append(e)
    #                     afficher(chemin)
                    elif laby[e[0], e[1]] == couleur_arrivee :
                        predecesseur[(e[0], e[1])] = (sommet[0], sommet[1])
                        chemin.append(e)
                        return chemin, predecesseur
     
    ########################################################
     
    def a_droite(labyrinthe, debut, n, p) :
        attente = []
        chemin = []
        predecesseur = {}
        laby = np.copy(labyrinthe)
        depart = [debut, ind, [0,1]]
        attente.append(depart)
        ordre = {(-1, 0) : [(0,1), (1,0), (0,-1), (-1,0)] ,
                 (1, 0) : [(0,-1), (-1,0), (0,1), (1,0)],
                 (0, -1) : [(-1,0), (0,1), (1,0), (0,-1)],
                 (0, 1) : [(1,0), (0,-1), (-1,0), (0,1)]}  #inversé car structure = pile
     
        while attente != []:
            sommet = attente.pop()
            direction = tuple(sommet[2])
            if laby[sommet[0], sommet[1]] == couleur_vide or laby[sommet[0], sommet[1]] == couleur_debut :
                laby[sommet[0], sommet[1]] = 5
                chemin.append(sommet[0:2])
                for e in [addition((sommet[0], sommet[1]), e) for e in ordre[direction]] :
                    if e[0] >=n or e[0] < 0 or e[1] >= p + ind or e[1] < ind :
                        pass
                    elif laby[e[0], e[1]] == couleur_vide :
                        predecesseur[(e[0], e[1])] = (sommet[0], sommet[1])
                        e.append(soustraction(sommet[0:2], e))
                        attente.append(e)
    #                     afficher(chemin)
                    elif laby[e[0], e[1]] == couleur_arrivee :
                        predecesseur[(e[0], e[1])] = (sommet[0], sommet[1])
                        chemin.append(e)
                        return chemin, predecesseur
     
    ########################################################
    ########### Fonctions Auxilliaires #####################
    ########################################################
     
    def init (n, p) :
        """permet l'initialisation du labyrinthe, renvoie une matrice allant de  a n²-1, une grille de labyrinthe vierge
            et la taille de la matrice"""
        m = (n-1)//2
        q = (p-1)//2
        laby = np.zeros((m, q), dtype = int)
        for i in range(m):
            for j in range(q) :
                laby[i,j] = i*q + j
     
        mat_mur = np.full((n, p), couleur_vide, dtype = int)
        for i in range(0, n, 2):
            mat_mur[i, 0:p] = 0
        for i in range(0, p, 2):
            mat_mur[0:n, i] = 0
        return laby, mat_mur, m, q
     
    #########################################################
     
    def crea_mur(n, p, anim = False) :
        '''creation des murs du labyrinthe
            orientation : (haut/bas, gauche/droite)
            (-1,0)=bas, (1,0)=haut, (0,-1)=gauche, (0,1)=droite'''
        if anim :
            img=[]
        laby, mat_mur, m, q = init(n, p)
        maxi = m*q - 1
        compteur = 0
        while compteur < maxi :
            rd_ligne, rd_colonne = rd.randint(0, m-1), rd.randint(0, q-1)
            orientation = rd.choice([(-1, 0), (1, 0), (0, -1), (0, 1)])
            coordonnees = addition((rd_ligne, rd_colonne), orientation)
            if coordonnees[0] < 0 or coordonnees[0] > m-1 or coordonnees[1] < 0 or coordonnees[1] > q-1 :
                continue
            rd_nombre, coord_nombre = laby[rd_ligne, rd_colonne], laby[coordonnees[0],coordonnees[1]]
            if rd_nombre == coord_nombre :
                continue
            else:
                if anim :
                    img.append(np.copy(mat_mur))
                petit = min(rd_nombre, coord_nombre)
                grand = max(rd_nombre, coord_nombre)
                coord_mur = addition((1+2*rd_ligne,1+2*rd_colonne), orientation)
                mat_mur[coord_mur[0], coord_mur[1]] = couleur_vide
                for (i,j) in [(i, j) for i in range(m) for j in range(q) if laby[i, j] == grand] :
                    laby[i, j] = petit
                compteur += 1
    #         afficher3(mat_mur, 0, False)
        if anim : 
            return mat_mur, img
        else :
            return mat_mur
     
    #########################################################
     
    def addition(couple1, couple2) :
        """permet de faire la somme des elements d'un couple un à un"""
        return [e1+e2 for e1, e2 in zip(couple1, couple2)]
     
    #########################################################
     
    def soustraction(couple1, couple2) :
        """permet de faire la différence des elements d'un couple un à un"""
        return [e1-e2 for e1, e2 in zip(couple1, couple2)]
     
    #########################################################
     
    def entree_sortie (n, p, matrice_mur) :
        """Definition de l'entrée et la sortie"""
        hauteur = len(matrice_mur)
        largeur = len(matrice_mur[0])
        laby_fleche = np.full((hauteur, largeur + ind*2), couleur_vide)
        laby_fleche[:,ind:largeur+ind] = matrice_mur
        debut = rd.randint(3, n-4)
        while matrice_mur[debut, 1] == 0 :
            debut = rd.randint(3, n-4)
     
        laby_fleche[debut,:ind+1] = couleur_debut
        laby_fleche[debut-1,3:ind-1], laby_fleche[debut+1,3:ind-1] = couleur_debut, couleur_debut
        laby_fleche[debut-2,3:ind-2], laby_fleche[debut+2,3:ind-2] = couleur_debut, couleur_debut
        laby_fleche[debut-3,3:ind-3], laby_fleche[debut+3,3:ind-3] = couleur_debut, couleur_debut
     
        fin = rd.randint(3, n-4)
        while matrice_mur[fin, p-2] == 0 :
            fin = rd.randint(3, n-4)
     
        laby_fleche[fin,largeur+ind-1:] = couleur_arrivee
        laby_fleche[fin-1,largeur+ind+1:largeur+ind+4], laby_fleche[fin+1,largeur+ind+1:largeur+ind+4] = couleur_arrivee, couleur_arrivee
        laby_fleche[fin-2,largeur+ind+2:largeur+ind+4], laby_fleche[fin+2,largeur+ind+2:largeur+ind+4] = couleur_arrivee, couleur_arrivee
        laby_fleche[fin-3,largeur+ind+3:largeur+ind+4], laby_fleche[fin+3,largeur+ind+3:largeur+ind+4] = couleur_arrivee, couleur_arrivee
        return laby_fleche, debut, fin
     
    ##########################################################
     
    def transformation(chemin, labyrinthe, debut, arrivee, archive=True):
        """permet de transformer une liste de sommet en une matrice montrant le chemin parcouru"""
        laby = np.copy(labyrinthe)
        ajout = (couleur_arrivee - couleur_debut)/len(chemin)
        if archive :
            archive = []
            for i in range(len(chemin)) :
                archive.append(np.copy(laby))
                laby[chemin[i][0], chemin[i][1]] = couleur_debut + (i+1)*ajout
            n=len(laby)
            laby[debut, ind] = -1500
            laby[arrivee, n-1+ind] = -1500
            archive.append(np.copy(laby))
            return laby, archive
        else :
            for i in range(len(chemin)) :
                laby[chemin[i][0], chemin[i][1]] = couleur_debut + (i+1)*ajout
            n=len(laby)
            laby[debut, ind] = -1500
            laby[arrivee, n-1+ind] = -1500
            return laby
     
    ##########################################################
     
    def chemin_direct(debut, arrivee, n, p, predecesseur) :
        """retrouve le chemin direct du labyrinthe"""
        sommet = (arrivee, p-1+ind)
        laby = np.full((n,p+2*ind), couleur_vide, dtype = int)
        while sommet != (debut, ind) :
            laby[sommet[0], sommet[1]] = 0
            sommet = predecesseur[sommet]
        laby[debut, ind] = -1500
        laby[arrivee, p-1+ind] = -1500
        return laby
     
    ########################################################
    ################### Statistiques #######################
    ########################################################
     
    def statistique(repetition, debut, fin):
        moy = {'DFS' : [], 'BFS' : [], 'Droite' : []}
        print(str(00) + ' %  : ' + 100 * '▁')
        taille = 0
        for i in range(debut, fin, 2) :
            taille = taille + i*i*repetition
        pas = taille // 100
        tot = 0
        for i in range(debut, fin, 2) :
            for _ in range(repetition):
                a,b,c = labyrinthe_final(i, i, False)
                moy['DFS'].append([a,i])
                moy['BFS'].append([b,i])
                moy['Droite'].append([c,i])
                tot = tot + i*i
                i2 = tot//pas
                print(str(i2) + ' %  : ' +  (i2) * '▉' + (100 - i2) * '▁')
     
        fig = plt.figure()
        fig.suptitle('Efficacité des algorithmes')
        gs = GridSpec(3, 3, figure=fig)
        ax0 = fig.add_subplot(gs[0, 0])
        ax1 = fig.add_subplot(gs[0, 1], sharex=ax0, sharey=ax0)
        ax2 = fig.add_subplot(gs[0, 2], sharex=ax0, sharey=ax0)
        ax3 = fig.add_subplot(gs[1:, :])
    #     ax3.set_yscale('log')
     
        ax0.set_ylabel('Nombre de cases visitées')
        for i in range(3) :
            axes = [ax0, ax1, ax2]
            methodes = ['DFS', 'BFS', 'Droite']
            couleur = ['orange', 'blue', 'green']
            x, y = en_place_points(axes[i], moy[methodes[i]], couleur[i], True)
            ax3.plot(x, y, linestyle = '-',  color = couleur[i], linewidth = 1.5, label=methodes[i])
        plt.legend()
        plt.show()
     
    ########################################################
     
    def moyenne(liste):
        total = 0
        n = len(liste)
        for i in range(n) :
            total = total + liste[i]
        return total/n
     
    ########################################################
     
    def en_place_points(axe, points, couleur, ligne_condition):
        points = np.array(points)
        x = points[:,1]
        y = points[:,0]
        axe.scatter(x, y, 5, couleur, 'x', alpha = 0.3)
        a,b,c = np.polyfit(x, y, 2)
        y2 = a*x**2 + b*x + c
        if ligne_condition :
            axe.plot(x, y2, linestyle = '-',  color = couleur, linewidth = 1.5)
    #     axe.set_yscale('log')
        return x, y2
     
    ########################################################
     
    def statistique_creation(debut, fin):
        moy = []
        print(str(00) + ' %  : ' + 100 * '▁')
        taille = 0
        for i in range(debut, fin, 2) :
            taille = taille + i*i
        pas = taille // 100
        tot = 0
        for i in range(debut, fin, 2) :
            temps = time.time()
            crea_mur(i, i, False)
            moy.append( (time.time()-temps, i))
            tot = tot + i*i
            i2 = tot//pas
            print(str(i2) + ' %  : ' +  (i2) * '▉' + (100 - i2) * '▁')
     
        fig = plt.figure()
        fig.suptitle('Temps de création des Labyrinthes')
        ax0 = fig.add_subplot()
        ax0.set_ylabel('Temps en seconde')
        en_place_points(ax0, moy, 'blue', False)
        plt.show()
     
    ########################################################
    ############### Enorme Labyrinthe ######################
    ########################################################
     
    def enorme_laby(n,p, sauvegarde =False):
        '''assemblage du gros labyrinthes'''
        if n%2 == 0 :
            n = n+1
        if p%2 == 0 :
            p = p+1
        m = n//100
        mr = n%100
        q = p//100
        qr = p%100
        total = 0
    #     print('m = ' +str(m) + ', mr = ' +str(mr) +', q = ' +str(q)+', qr = ' +str(qr))
        big_laby = np.zeros((n,p), dtype = int)
        possibilite_i, possibilite_j = [100 for i in range(m)], [100 for j in range(q)]
        possibilite_i.append(mr)
        possibilite_j.append(qr)
        a_faire = [[(i,j) for j in possibilite_j ] for i in possibilite_i]
    #     print(possibilite_i)
    #     print(possibilite_j)
    #     print(a_faire)
        liste_laby = [[] for _ in range(m+1)]
        liste_indice = []
        total = m*q + q + m -1
        x=0
        for k in range(m+1):
            for (i,j) in a_faire[k] :
                indice = rd.randint(1,1000)
                while indice in liste_indice :
                    indice = rd.randint(1,1000)
                liste_laby[k].append(crea_mur(i, j))
                liste_indice.append(indice)
                print(str(x*100//total) + ' %  : ' +  (x*100//total) * '▉' + (100 - x*100//total) * '▁')
                x+=1
        repartition(big_laby, liste_laby, m, q, mr, qr)
        suppression_ligne(big_laby, m, q, mr, qr)
        a_afficher, debut, fin = entree_sortie(n, p, big_laby)
        afficher5(a_afficher, str(n)+' * '+str(p), sauvegarde)
        return a_afficher, debut, fin
     
    ################################################
     
    def repartition(laby, liste_laby, m, q, mr, qr):
        for i in range(m):
            for j in range(q) :
                laby[i*100:(i+1)*100, j*100:(j+1)*100] = liste_laby[i][j]
        for j in range(q):    
            laby[m*100:m*100+mr, j*100:(j+1)*100] = liste_laby[m][j]
        for i in range(m):
            laby[i*100:(i+1)*100, q*100:q*100+qr] = liste_laby[i][q]
        laby[m*100:m*100+mr, q*100:q*100+qr] = liste_laby[m][q]
     
    ###################################################
     
    def suppression_ligne(laby, m, q, mr, qr):
        '''remplissage des intersection des labyrinthes par un motif de labyrinthe'''
        ##### Ligne #####
        liste_laby = [[] for _ in range(2)]
        a_faire = [[(7, 101) for _ in range (q)],[(101, 7) for _ in range (m)]]
        a_faire[0].append((7, qr))
        a_faire[0] = a_faire[0]*m
        a_faire[1] = a_faire[1]*q
        for _ in range(q):
            a_faire[1].append((mr, 7))
     
        for k in range(2):
            for (i,j) in a_faire[k] :
                liste_laby[k].append(crea_mur(i, j))
        for i in range(1, m+1):
            for j in range(q) :
                laby[i*100-3:i*100+2, j*100+1:(j+1)*100+1] = liste_laby[0][j][1:6,1:]
            for j in range(1,q):
                laby[i*100-3:i*100+2, q*100+1:] = liste_laby[0][j*(q+1)-1][1:6,1:]
        for j in range(1, q+1) :
            for i in range(m):
                laby[i*100+1:(i+1)*100+1, j*100-3:j*100+2] = liste_laby[1][i][1:,1:6]
            for i in range(1,q+1):
                laby[m*100+1:, i*100-3:i*100+2] = liste_laby[1][q*m + i-1][1:,1:6]
     
    #     afficher(laby)
     
    ###################################################
     
    def entree_sortie_bis(n, p, matrice_mur) :
        """Definition de l'entrée et la sortie"""
        hauteur = len(matrice_mur)
        largeur = len(matrice_mur[0])
        laby_fleche = np.full((hauteur, largeur + 6*2), couleur_vide)
        debut = rd.randint(1, n-2)
        while matrice_mur[debut, 1] == 0 :
            debut = rd.randint(1, n-2)
        matrice_mur[debut,0] = couleur_debut
        laby_fleche[debut,:7] = couleur_debut
        laby_fleche[debut-1,3:6], laby_fleche[debut+1,3:6] = couleur_debut, couleur_debut
        laby_fleche[debut-2,3:5], laby_fleche[debut+2,3:5] = couleur_debut, couleur_debut
        laby_fleche[debut-3,3:4], laby_fleche[debut+3,3:4] = couleur_debut, couleur_debut
     
        fin = rd.randint(1, n-2)
        while matrice_mur[fin, p-2] == 0 :
            fin = rd.randint(1, n-2)
        matrice_mur[fin, p-1] = couleur_arrivee
        laby_fleche[fin,largeur+5:] = couleur_arrivee
        laby_fleche[fin-1,largeur+6:largeur+9], laby_fleche[fin+1,largeur+6:largeur+9] = couleur_arrivee, couleur_arrivee
        laby_fleche[fin-2,largeur+7:largeur+9], laby_fleche[fin+2,largeur+7:largeur+9] = couleur_arrivee, couleur_arrivee
        laby_fleche[fin-3,largeur+8:largeur+9], laby_fleche[fin+3,largeur+8:largeur+9] = couleur_arrivee, couleur_arrivee
        laby_fleche[:,6:largeur+6] = matrice_mur
        return laby_fleche, debut, fin
     
    ##########################################################
     
    def labyrinthe_final_enorme(n, p, affichage=True, sauvegarde = False):
        """Fonction mère, crée le labyrinthe énorme et le resout de différentes manieres
            Attention : n et p impairs"""
        if n%2 == 0 :
            n = n+1
        if p%2 == 0 :
            p = p+1
     
        mat_mur, debut, fin = enorme_laby(n, p)
        print('Labyrinthe -- : check')
    #-----------DFS-----------
        dfs_chemin, predecesseur = dfs(mat_mur, debut, n, p)
        if affichage : 
            dfs_laby = transformation(dfs_chemin, mat_mur, debut, fin, False)
            dfs_direct = chemin_direct(debut, fin, n, p, predecesseur)
        print('DFS --------- : check')
    #-----------BFS-----------
        bfs_chemin, predecesseur = bfs(mat_mur, debut, n, p)
        if affichage :
            bfs_laby = transformation(bfs_chemin, mat_mur, debut, fin, False)
        print('BFS --------- : check')
    #--------à droite---------
        droite_chemin, predecesseur = a_droite(mat_mur, debut, n, p)
        if affichage :
            droite_laby= transformation(droite_chemin, mat_mur, debut, fin, False)
        print('A droite ---- : check')
     
        longueur = [len(dfs_chemin), len(bfs_chemin), len(droite_chemin)]
        if affichage : 
            afficher4([dfs_laby, bfs_laby, droite_laby], dfs_direct, longueur, sauvegarde, False)
     
        return longueur
     
    #     afficher3(laby, 0, False)
    #     afficher3(laby_indice, 0, False)
    #     return laby
     
     
     
    # labyrinthe_final(400,True)
    # labyrinthe_final(300)
    # labyrinthe_final(100, False ,False)

  19. #19
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 851
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par JheyFaid Voir le message
    Je viens donc vous demander si vous avez une idée me permettant de garantir cet unique chemin ?
    Déjà au lieu de générer 9 labyrinthe de 100x100, tu pourrais générer un labyrinthe de 900x900. Comme le chemin est garanti unique dans le labyrinthe, cela élimine ton problème.

    Sinon la seule solution c'est que la porte d'entrée du labyrinthe n+1 soit à la même position (enfin en fonction de la symétrie axiale) que la porte de sortie du labyrinthe n. Ca te force déjà à savoir comment sera positionné le labyrinthe n+1. Si par exemple il est en dessous du n, alors il te faut créer sa porte d'entrée sur son "toit" puis ensuite tu crées la sortie du n sur son "plancher" à la même abscisse.

    Ceci dit, le 100x100 c'est déjà une belle taille (quand j'en génère un j'ai du mal à le résoudre). T'as besoin d'aller sur du 900x900 ???
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  20. #20
    Membre habitué
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2023
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2023
    Messages : 13
    Par défaut
    Citation Envoyé par Sve@r Voir le message
    Déjà au lieu de générer 9 labyrinthe de 100x100, tu pourrais générer un labyrinthe de 900x900. Comme le chemin est garanti unique dans le labyrinthe, cela élimine ton problème.
    Effectivement, le programme en est capable mais au dela de 300 le programme a du mal, c(est pour ca que j'ai decidé de diviser le problème... Et c'est pour un 300*300 qu'il faut 9 labyrinthe, pour un 900*900 il en faut 81 ! Et avec ce nouveau programme, le 900*900 il me le fait en meme pas 2 minutes (bien qu'il n'y ai pas d'unicité de la solution) tandis que avec le premier programme ca prendrait plusieurs heures, voir jours...

    Citation Envoyé par Sve@r Voir le message
    Sinon la seule solution c'est que la porte d'entrée du labyrinthe n+1 soit à la même position (enfin en fonction de la symétrie axiale) que la porte de sortie du labyrinthe n. Ca te force déjà à savoir comment sera positionné le labyrinthe n+1. Si par exemple il est en dessous du n, alors il te faut créer sa porte d'entrée sur son "toit" puis ensuite tu crées la sortie du n sur son "plancher" à la même abscisse.
    Si je fais ca on verra directement par ou il faut passer pour résoudre le labyrinthe : il y aura 1 seule solution mais qui ne passera pas aléatoirement par tous les minis-labyrinthes, cela reviendrait a résoudre plusieurs mini_labyrinthes a la suite.

    Citation Envoyé par Sve@r Voir le message
    T'as besoin d'aller sur du 900x900 ?
    Mon but est d'obtenir des labyrinthes de toutes tailles pour pouvoir faires différents types d'études (que j'ai deja commencé a implémenter dans le programme) quant à l'efficacité des différents algorithmes.

    Pour créer les mini-labyrinthes, j'utilise la technique de la fusion aléatoire que tu m'avais proposé, qui attribue a chaque case un indice et compare l'indice a ses voisins.
    Je me dis que je pourrais, à la place d'inserer des labyrinthes pour faire la jonction, realiser cette methode en attribuant aux labyrinthes différents indices. Il faut encore que j'y réflechisse car elle me semble assez lourde a cette echelle, mais je ne sais pas si c'est la seule méthode qui garantirait l'unicité.

    Edit : en y repensant même cette méthode ne garantit pas l'unicité

+ Répondre à la discussion
Cette discussion est résolue.
Page 1 sur 2 12 DernièreDernière

Discussions similaires

  1. Réponses: 6
    Dernier message: 30/07/2003, 14h59
  2. Limite des GENERATORS
    Par Débéa dans le forum Débuter
    Réponses: 5
    Dernier message: 24/07/2003, 13h05
  3. Génération de code
    Par YAMKI dans le forum Rational
    Réponses: 5
    Dernier message: 22/04/2003, 16h41
  4. Generation d'evenements a une date precise
    Par pascalzzz dans le forum MFC
    Réponses: 2
    Dernier message: 04/06/2002, 15h21

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo