Discussion :

[yves1107]

Bonjour,

Dans le cadre de mes études d'ingénieur, je dois réaliser un programme qui génère un labyrinthe carré dont la densité de murs est donnée par l'entrée "densite" et dont la taille d'un coté est donnée par la variable "TAILLE".

J'ai développé les fonctions nécessaires à ce programme sous python 3.4, après exécution tout fonctionne à merveille. En revanche, l'objectif final de ce travail est de modéliser en 3D ce labyrinthe à l'aide du logiciel FreeCAD dont la version python est la 2.7. Lors du transfert, le programme a tourné dans le vide. Mon professeur m'a alors conseillé de vérifier mon code freeCAD, ce que je fis à l'aide d'une matrice que j'ai entrée à la main dans la console; le résultat était alors celui attendu. J'ai ensuite essayé d'exécuter mon programme sous python 2.7 pour voir si le résultat venait de là et j'ai alors eu le même problème que précédemment.

Après une longue recherche dans le code, la fonction qui "merde" est la fonction generer_grille(densite).

L'objectif de cette fonction est de générer une grille (liste de listes) dans laquelle la densité de murs est un entier entré par l'utilisateur compris entre 0 et 100, un espace vide est représenté par un 1 et un mur par un 0.

Pour les densités supérieures à 15, ce programme fonctionne comme un vers dans une pomme. La grille est initialement créée uniquement avec de 0 ( fonction grille-pleine(0)), on prend une coordonnée de départ au hasard et selon la position du point de départ on choisit de se déplacer soit à droite, gauche, bas ou haut; on affecte alors à la case la valeur de 1 et ainsi de suite. Si le vers tombe sur une case qu'il a déjà creusé, il est téléporté vers une autre afin de commencer un nouveau trou. La fonction s'arrête lorsque la densité de murs est atteinte.

Pour les densités inférieures à 15, les murs sont placés aléatoirement dans le labyrinthe vide.

Voici les fonctions

###############################

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
from random import *
TAILLE=10   #taille arbitraire
 
def grille_pleine(val):
    """ l'objectif de cette fonction est de generer une matrice TAILLE*TAILLE dont chaque case a la meme valeur val"""
    grille=[]
    for i in range(TAILLE):
        L=[]
        for j in range(TAILLE):
            L.append(val)
        grille.append(L)
    return grille
 
def position_alea():
    """ cette fonction renvoie l'abscisse et l'ordonnee d'un point choisi aleatoirement dans la grille """
    x=randint(0,TAILLE-1)
    y=randint(0,TAILLE-1)
    return x,y
 
def generer_grille(densite):
    """l'objectif de cette fonction est de generer une grille (liste de listes) dans laquelle la densite de murs est un entier entre par lutilisateur compris entre 0 et 100, un espace vide est represente par un 1 et un mur par un 0 """
    y,x=position_alea()                             # on choisit une case de depart au hasard
    if densite>=15:                  # Cette division en 2 cas permet de diminuer grandement le temps de calcul; la borne 15 a ete obtenue experimentalement car c'est pour cette valeur que la duree d'execution varie drastiquement
        grille=grille_pleine(0)                     # on cree une grille pleine de mur
        sommematrice=0                              # on initialise la valeur qui nous permettra de suivre l'evolution du nombre de cases vides creees au court de l'evolution de la fonction  
        espacevide=[]                               # on creer un liste regroupant les espaces vides
        while sommematrice<(TAILLE**2)*(1-(densite/100)):  #tant que l'on a pas atteint la densite de murs souhaitee             
            espacevide.append([y,x])                # on met a jour la liste des espaces vides
            if x==0:                                # si on se trouve sur la face ouest
                chemin=choice("d")                  # h pour haut, b pour bas, g pour gauche, d pour droite // choice("hbgd") permet de choisir au hasard une lettre entre h,b,g,d avec equiprobabilite
            elif x==TAILLE-1:                       # si on se trouve sur la face est
                chemin=choice("g")                  # cela pemet de diminuer le nombre de chemins sur les exterieurs
            elif y==0:                              # si on se trouve sur la face sud
                chemin=choice("b")
            elif y==TAILLE-1:                       # si on se trouve sur la face nord
                chemin=choice("h")            
            elif x==0 and y==0:                     # si on se trouve dans le coin nord ouest
                chemin=choice("bd")
            elif x==0 and y==TAILLE-1:              # si on se trouve dans le coin sud ouest 
                chemin=choice("hd")
            elif x==TAILLE-1 and y==0:              # si on se trouve dans le coin nord est
                chemin=choice("bg")
            elif x==TAILLE-1 and y==TAILLE-1:       # si on se trouve dans le coin sud est
                chemin=choice("gh")
            else:
                chemin=choice("hbgd")               # si on se trouve dans le coeur du labyrinthe
            if chemin=='d':
                x+=1
            elif chemin=='g':
                x+=-1
            elif chemin=='h':
                y+=-1
            elif chemin=='b':
                y+=1
            if grille[y][x]==1:                     # si la case est deja vide
                [y,x]=espacevide[randrange(len(espacevide))]            #on vient prendre les coordonnees d'un espace vide et on recommence a creuser            
            else:                                   # sinon elle devient une case vide
                grille[y][x]=1
                sommematrice+=1
    else:                                       # sinon on choisit de venir placer les murs aleatoirement dans la grille
        sommematrice=TAILLE**2
        grille=grille_pleine(1)                 # on vient creer une grille vide
        while sommematrice>(TAILLE**2)*(1-(densite/100)):  # tant que la densite souhaitee n'est pas atteinte, on continue
            x,y=position_alea()
            grille[x][y]=0
            sommematrice+=-1
    return grille

###############################################################

Je ne comprend pas d'où provient cette différence d'exécution entre les deux versions.
Pourriez vous m'aider à adapter ma fonction à la version 2.7 s'il vous plait.

Merci d'avance pour le temps de réflexion accordé.


Larry

[wiztricks]

Salut,

Si çà met beaucoup plus de temps voire un temps infini pour sortir du while c'est que la condition: sommematrice<(TAILLE**2)*(1-(densite/100)) ne se réalise pas.
Et la différence entre les 2 Python est sur la division entière: n/100 retournera toujours 0 (ce que vous pouvez vérifier avec des "print"). Il faut forcer densité à être un "float" en écrivant: sommematrice<(TAILLE**2)*(1-(float(densite)/100)).
Pour le reste, votre code est truffé d'erreurs, converge lentement, c'est une peine à voir... Mais si le "boss" est content

- W

[yves1107]

Salut wiztricks,
Effectivement c'est bien le manque de float qui posait problème.
Merci pour votre rapide réponse.
Si je suis venu sur ce forum, c'est pour apprendre, pas pour que le "boss" soit content.
Pourriez vous donc expliciter les différentes erreurs de mon code s'il vous plaît ?
Quand à la complexité, je sais qu'il existe d'autres façons plus rapides de faire mais dans le cadre du problème qui nous est posé, c'est la méthode que j'ai trouvée le plus rapidement qui m'assure que chaque espace vide est relié à n'importe quel autre espace vide.

P.S.: Ce n'est pas comme ça que l'on donne envie de travailler. J'espère sincèrement que vous n'êtes pas enseignant. Votre intérêt pour la transmission du savoir est " une peine à voir ".

[wiztricks]

Votre intérêt pour la transmission du savoir est " une peine à voir".

C'est pour cela que je ne le montre pas (contrairement à votre code).

Pourriez vous donc expliciter les différentes erreurs de mon code s'il vous plaît ?

Si vous écrivez sans sourciller des chemin=choice("b"), c'est que vous ne réfléchissez pas trop aux instructions que vous écrivez (pourvu que çà marche)....
En programmant avec un tel état d'esprit, pour moi, il est inutile d'essayer de vous expliquer quoi que ce soit... Mais peut être que d'autres seront plus compatissants, qui sait?

- W

[yves1107]

C'est pour cela que je ne le montre pas (contrairement à votre code).

Je ne comprends pas ce que vous souhaitez dire ici.

Si vous écrivez sans sourciller des chemin=choice("b"), c'est que vous ne réfléchissez pas trop aux instructions que vous écrivez (pourvu que çà marche)....
En programmant avec un tel état d'esprit, pour moi, il est inutile d'essayer de vous expliquer quoi que ce soit... Mais peut être que d'autres seront plus compatissants, qui sait?

C'est un choix de ma part car sur les bords du labyrinthe autres que les coins, il est possible de prendre 3 directions. Toutefois, si on propose les 3 directions il y a plus de chance que les bords du labyrinthe soient creusés ( étude de probabilité à la clef). Proposer une unique direction me permet d'obtenir un labyrinthe que je considère comme valable. Néanmoins, je garde cette ligne afin de pouvoir démontrer mes dires lors de la soutenance. Je comprends les instructions que j'écris, rien n'est fait au hasard et tout à été écrit sur feuille avant de se lancer. Le pourvu que çà marche n'est pas enseigné dans mes études fort heureusement.
Pourriez vous je vous prie m'expliquer mes erreurs s'il vous plait ?
Ne vous obstinez pas à croire que c'est inutile.

[wiztricks]

Je comprends les instructions que j'écris, rien n'est fait au hasard et tout à été écrit sur feuille avant de se lancer. Le pourvu que çà marche n'est pas enseigné dans mes études fort heureusement.
Pourriez vous je vous prie m'expliquer mes erreurs s'il vous plait ?

Ben réfléchissez un peu à la construction:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
            if x==0:                                # si on se trouve sur la face ouest
                chemin=choice("d")                  # h pour haut, b pour bas, g pour gauche, d pour droite // choice("hbgd") permet de choisir au hasard une lettre entre h,b,g,d avec equiprobabilite
            elif ...            
            elif x==0 and y==0:                     # si on se trouve dans le coin nord ouest
                chemin=choice("bd")
            ...

Et si vous n'avez pas envie de réfléchir vous écrivez une fonction genre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
>>> def f(x, y):
...     if x == 0:
...        print ('x == 0')
...     elif  x == 0 and y == 0:
...        print ('x == 0 and y == 0')
...

Et essayez de lui faire afficher 'x == 0 and y == 0'...
Désolé mais pour moi, c'est du code écrit avec les pieds.

- W