Generation de labyrinthe

Version imprimable

1 pièce(s) jointe(s)

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 : Pièce jointe 636683

voici mon code :

Code:

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)

01/04/2023, 21h11
Sve@r
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:

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
02/04/2023, 17h11
JheyFaid

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.
02/04/2023, 18h06
Sve@r
Citation:

Envoyé par JheyFaid

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)
03/04/2023, 13h16
JheyFaid

Citation:

Envoyé par Sve@r

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

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

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

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 !
04/04/2023, 19h04
JheyFaid

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...
05/04/2023, 18h06
AznarAkeba
Bonjour,

Je pense que ton problème vient de la condition
Code:

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:

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.
05/04/2023, 19h10
Sve@r
Citation:

Envoyé par AznarAkeba

Chez moi ça fonctionne avec cette modification.

Joli :applo:
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

...

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:
  
  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é.
05/04/2023, 23h20
JheyFaid
Un grand merci a vous deux pour avoir résolu mon problème !

Citation:

Envoyé par Sve@r

[*]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

[*]Pour la fin du code, je proposerais cette modification

Code:

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 !
05/04/2023, 23h37
Sve@r
Citation:

Envoyé par JheyFaid

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:

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.
07/04/2023, 22h01
JheyFaid

Merci pour cette précision !

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:

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

10/04/2023, 12h53
Sve@r

Citation:

Envoyé par JheyFaid

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

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).
10/04/2023, 15h21
JheyFaid

Citation:

Envoyé par Sve@r

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

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.

J'ai suivi tes conseils Sve@r et j'ai consacré ma soirée a refaire cet algo, cela donne :

Code:

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 !

10/04/2023, 23h35
Sve@r
Citation:

Envoyé par JheyFaid

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)
11/04/2023, 09h06
JheyFaid

Je commence par réaliser une grille sur le labyrinthe une case sur deux, donc si le labyrinthe est pair ça pose problème

1 pièce(s) jointe(s)

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.
Pièce jointe 637668

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:

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)

22/04/2023, 19h07
Sve@r

Citation:

Envoyé par JheyFaid

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 ???
22/04/2023, 20h17
JheyFaid

Citation:

Envoyé par Sve@r

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

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

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é
22/04/2023, 20h40
Sve@r

1 pièce(s) jointe(s)

Citation:

Envoyé par JheyFaid

tandis que avec le premier programme ca prendrait plusieurs heures, voir jours...

Oui c'est vrai que j'ai lancé un 900x900 il y a probablement 40mn et il n'est toujours pas généré. Hé oui, la complexité augmente proportionnellement au carré de la taille...

Citation:

Envoyé par JheyFaid

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.

Oui, effectivement.

Citation:

Envoyé par JheyFaid

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.

Pourquoi faire? Le problème est déjà résolu: en entrant dans le labyrinthe je pose ma main gauche(*) contre un mur puis je ne la décolle plus du mur et j'avance en longeant donc le mur gauche. Je suis forcé d'arriver à la sortie à un moment ou un autre.
(*) ça marche aussi avec la droite

Citation:

Envoyé par JheyFaid

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.

Pas évident car l'algo permet de créer des chemins mais n'évite pas les culs de sac. Faudra donc gérer si le labyrinthe permet de sortir sur un autre ou pas.
Exemple
Pièce jointe 637677
Comme tu vois, en arrivant dans un cul de sac le type repart chercher dans une autre direction. Mais si la case avec une croix est un labyrinthe, cela signifie que c'est un labyrinthe "cul de sac" donc avec l'entrée et la sortie sur le même côté. Ca va pas être évident...

Citation:

Envoyé par JheyFaid

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

Ah si. Puisque ça garantit l'unicité pour les cases, ça garantit l'unicité pour les labyrinthes. Mais ça ne garantit pas que tu passeras par les 9 (cf mon exemple où on peut shunter les deux du haut)