Labyrinthes

Étape 2 : Création du labyrinthe

Le principe

Il faut imaginer cette grille comme un graphe, où chaque sommet est une case reliée à ses voisines par un mur.

Toutes les cases ont 4 voisines sauf celles du bord qui n'en n'ont que 2 ou 3.

On fait un parcours en profondeur de ce graphe en utilisant la boucle draw()

Dans le setup()

  • current <-- la case 0

  • p(une pile) <--- current

Dans le draw() ( qui est une boucle )

  • On note current comme visitée

  • On la met en bleu

  • voisines <--- la liste de ses voisines non déjà visitées

  • Si voisines n'est pas une liste vide :

    • next <--- l'une d'entre elles

    • p <--- next

    • On élimine le mur entre current et next

    • current <--- next

  • Sinon :

    • Si la pile n'est pas vide :

      • On dépile p dans current

    • Sinon : on a terminé

MéthodeMise en œuvre

Il nous faudra une classe Pile : ( à récupérer et à écrire dans un nouvel onglet de maze_generator).

Il faudra rajouter un attribut de classe à la classe Cell pour noter le fait qu'une case est visitée ou pas.

1
# coding=utf-8 (nécessaire dans Processing)
2
class Cell:
3
4
    def __init__(self,j,i,w=30):
5
        self.i=i
6
        self.j=j
7
        self.w=w
8
        self.walls=[True,True,True,True]
9
        self.visited=False
Il faudra modifier la méthode show 
Si la case a été visitée, on change sa couleur.
1
    def show(self):
2
        '''
3
4
        '''
5
        x=self.i*self.w
6
        y=self.j*self.w
7
        w=self.w
8
        stroke(255)
9
        if self.walls[0]:
10
            line(x,y,x+w,y)
11
        if self.walls[1]:
12
            line(x+w,y,x+w,y+w)
13
        if self.walls[2]:
14
            line(x+w,y+w,x,y+w)
15
        if self.walls[3]:
16
            line(x,y+w,x,y)
17
        if self.visited:
18
            noStroke()
19
            fill(255,0,255,100)
20
            rect(x,y,w,w)
Voilà le setup()
1
grid=[]
2
p=Pile()
3
w=40 # dimension(on peut modifier)
4
def setup():
5
    '''
6
7
    '''
8
    size(610,410)
9
    global cols,rows,current # déclarées comme globales
10
    #global current
11
    cols=width//w
12
    rows=height//w
13
    #creation du tableau
14
15
    for j in range(rows):
16
        for i in range(cols):
17
            cell=Cell(j,i,w)
18
            grid.append(cell)
19
20
    current=grid[0]
21
    p.empiler(current)
22
    frameRate(30)#vitesse (max 60)
Voici la méthode de la classe Cell qui permet de calculer l'indice d'une case à partir de ses coordonnées.
1
2
     def index(self,i,j):
3
        w=self.w
4
        cols=int(width/w)
5
        rows=int(height/w)
6
        if (i < 0 or j < 0 or i > cols-1 or j > rows-1):
7
            return -1
8
        else:
9
            return j*cols + i
Voici la fonction qui efface le mur entre deux cases.
1
def removeWalls(a,b):
2
    '''
3
    efface le mur entre a et b
4
    '''
5
    x=a.i-b.i
6
    if x==1:
7
        a.walls[3]=False
8
        b.walls[1]=False
9
    elif x==-1:
10
        a.walls[1]=False
11
        b.walls[3]=False
12
    y=a.j-b.j
13
    if y==1:
14
        a.walls[0]=False
15
        b.walls[2]=False
16
    elif y==-1:
17
        a.walls[2]=False
18
        b.walls[0]=False
À faire : Expliquer le principe de cette fonction.
Voici la méthode de la classe Cell qui permet de récupérer la liste des indices des voisines d'une case
Cette méthode utilise la fonction index ( donc attention si par hasard vous avez placé les classes dans des fichiers séparés...)
1
2
     def checkVoisin(self):
3
        '''
4
        renvoie la liste des numéros des cases voisines
5
        '''
6
        voisins=[]
7
        top_case = self.index(self.i,self.j-1)
8
        right_case = self.index(self.i+1, self.j)
9
        bottom_case = self.index(self.i, self.j+1)
10
        left_case =self.index(self.i-1, self.j)
11
        if top_case!=-1:
12
            voisins.append(top_case)
13
        if right_case!=-1:
14
            voisins.append(right_case)
15
        if bottom_case!=-1:
16
            voisins.append(bottom_case)
17
        if left_case!=-1:
18
            voisins.append(left_case)
19
        return voisins
Voici la fonction qui transforme la liste des indices des voisines en liste de voisines non visitées
1
def voisinage(liste):
2
    '''
3
    renvoie la liste des voisines non visitées
4
    '''
5
    neighbors=[]
6
    for vois in liste:
7
        if grid[vois].visited==False:
8
            neighbors.append(grid[vois])
9
    return neighbors  
SimulationLe draw() pour terminer
Il vous reste à écrire ce qu'il faut dans le draw...
Pour terminer le programme (une fois le labyrinthe créé) il suffit d'écrire l'instruction noLoop()
1
def draw():
2
    '''
3
    fonction qui boucle (par defaut 60 fois/seconde)
4
    '''
5
    global current,next
6
    background(51)
7
    for i in range(len(grid)):
8
        grid[i].show()
9
    current.highlight()
10
11
    # à compléter
PrécédentPrécédentSuivantSuivant
AccueilAccueilImprimerImprimer
								Stéphan Van Zuijlen
								Licence de documentation libre GNURéalisé avec Scenari (nouvelle fenêtre)