Nous allons utiliser le module turtle
pour tracer le labyrinthe.
Pour modéliser un labyrinthe de n
lignes et p
colonnes. Nous allons utiliser :
p
cases.
n
lignes.
Nous aloons utiliser l'algorithme "Hunt and Kill".
Début AlgorithmeFin Algorithme
- Choisissez un lieu de départ.
- Effectuez une marche aléatoire :
- en faisant des passages vers des voisins non visités,
- jusqu'à ce que la cellule actuelle n'ait pas de voisins non visités.
- Entrez en mode «chasse» :
- Scannez la grille à la recherche d'une cellule non visitée adjacente à une cellule visitée.
- Si elle est trouvée, taillez un passage entre les deux ;
- La cellule non visitée devient le nouvel emplacement de départ.
- Répétez les étapes 2 et 3 jusqu'à ce que le mode de recherche analyse l'intégralité de la grille
et ne trouve aucune cellule non visitée.
Voici les différentes parties du code permettant de tracer le labyrinthe.
La case est un carré modélisé par une liste de 4 booléens, la première valaur coorespond au coté du bas si cette valeur est 1, le coté est visible, et si c'est 0, il n'est pas visible. La deuxième valeur de la liste correspond au coté de droite, puis celui du haut et enfin celui de gauche.
import turtle
from random import randint
t=turtle.Turtle()
t.penup()
t.goto(-200,0)
t.speed(10)
COTE=200
def case(liste):
for a in liste:
if a==1:
t.pendown()
else:
t.penup()
t.forward(COTE)
t.left(90)
t.penup()
t.forward(COTE)
carre=[randint(0,1),randint(0,1),randint(0,1),randint(0,1)]
print("tracer du carre associe a la liste",carre)
case(carre)
On met en place des lignes de codes qui adaptent la taille des cases à la grandeur du labyrinthe.
import turtle
from random import shuffle
t=turtle.Turtle()
t.penup()
t.speed(10)
COTE=40
def case(liste):
for a in liste:
if a==1:
t.pendown()
else:
t.penup()
t.forward(COTE)
t.left(90)
t.penup()
t.forward(COTE)
def tracer(liste,taille=400,origineX=-200,origineY=200):
lignes=len(liste)
cols=len(liste[0])
global COTE
COTE=min(taille//lignes,taille//cols)
t.goto(origineX,origineY-COTE)
for l in range(lignes):
for c in range(cols):
case(liste[l][c])
t.goto(origineX,origineY-(l+2)*COTE)
def labyInit(lignes,cols):
liste=[]
for l in range(lignes):
ligne=[]
for c in range(cols):
ligne.append([1,1,1,1])
liste.append(ligne)
return liste
tracer(labyInit(10,12))
kill
La partie Kill
est composée de 2 fonctions :
possibilites
qui cherche une case qui fera partie du chemin.
kill
qui génére un chemin en effaçant les cotés des cases.
def possibilites(x,y,laby):
pos=[]
lignes=len(laby)
cols=len(laby[0])
if y+1 < cols and laby[x][y+1]==[1,1,1,1]:
pos.append(1)
if x+1 < lignes and laby[x+1][y]==[1,1,1,1]:
pos.append(0)
if y-1 >= 0 and laby[x][y-1]==[1,1,1,1]:
pos.append(3)
if x-1 >= 0 and laby[x-1][y]==[1,1,1,1]:
pos.append(2)
shuffle(pos)
return pos
def kill(x,y,laby):
test=possibilites(x,y,laby)
while test != []:
a=test[0]
laby[x][y][a]=0
x=x+(-1)**(a//2)*((a+1)%2)
y=y+(-1)**(a//2)*((a)%2)
laby[x][y][((a+2)%4)]=0
test=possibilites(x,y,laby)
return laby
Voici le code qui permet de tester la partie kill
de l'algorithme.
import turtle
from random import shuffle,randint
t=turtle.Turtle()
t.penup()
#t.goto(-200,200)
t.speed(10)
COTE=40
def case(liste):
t.color("black")
if liste != [1,1,1,1]:
t.color("red")
for a in liste:
if a==1:
t.pendown()
else:
t.penup()
t.forward(COTE)
t.left(90)
t.penup()
t.forward(COTE)
def tracer(liste,taille=400,origineX=-200,origineY=200):
lignes=len(liste)
cols=len(liste[0])
global COTE
COTE=min(taille//lignes,taille//cols)
t.goto(origineX,origineY-COTE)
for l in range(lignes):
for c in range(cols):
case(liste[l][c])
t.goto(origineX,origineY-(l+2)*COTE)
def labyInit(lignes,cols):
liste=[]
for l in range(lignes):
ligne=[]
for c in range(cols):
ligne.append([1,1,1,1])
liste.append(ligne)
return liste
def possibilites(x,y,laby):
pos=[]
lignes=len(laby)
cols=len(laby[0])
if y+1 < cols and laby[x][y+1]==[1,1,1,1]:
pos.append(1)
if x+1 < lignes and laby[x+1][y]==[1,1,1,1]:
pos.append(0)
if y-1 >= 0 and laby[x][y-1]==[1,1,1,1]:
pos.append(3)
if x-1 >= 0 and laby[x-1][y]==[1,1,1,1]:
pos.append(2)
shuffle(pos)
return pos
def kill(x,y,laby):
test=possibilites(x,y,laby)
while test != []:
a=test[0]
laby[x][y][a]=0
x=x+(-1)**(a//2)*((a+1)%2)
y=y+(-1)**(a//2)*((a)%2)
laby[x][y][((a+2)%4)]=0
test=possibilites(x,y,laby)
return laby
def onekill(laby,a,b):
cible=[a,b]
x=cible[0]
y=cible[1]
laby=kill(x,y,laby)
return laby
a=randint(0,9)
b=randint(0,11)
print"la fonction kill a commence ligne",a+1,"colonne",b+1
tracer(onekill(labyInit(10,12),a,b))
hunt
La partie Hunt
est composée de 2 fonctions :
recherche
qui cherche une case qui sera un nouveau point de départ.
hunt
qui efface les cotés de la nouvelle case et de la case adjacente.
def recherche(x,y,laby):
lignes=len(laby)
cols=len(laby[0])
if laby[x][y]==[1,1,1,1]:
if y+1 < cols and laby[x][y+1]!=[1,1,1,1]:
return 1
if x+1 < lignes and laby[x+1][y]!=[1,1,1,1]:
return 0
if y-1 >= 0 and laby[x][y-1]!=[1,1,1,1]:
return 3
if x-1 >= 0 and laby[x-1][y]!=[1,1,1,1]:
return 2
return -1
def hunt(laby):
lignes=len(laby)
cols=len(laby[0])
for x in range(lignes):
for y in range(cols):
a=recherche(x,y,laby)
if a != -1:
laby[x][y][a]=0
laby[x+(-1)**(a//2)*((a+1)%2)][y+(-1)**(a//2)*((a)%2)][((a+2)%4)]=0
return [x,y],laby
return [],laby
Voici le code pour tester
import turtle
from random import shuffle,randint
t=turtle.Turtle()
t.penup()
#t.goto(-200,200)
t.speed(10)
COTE=40
def case(liste):
t.color("black")
if liste != [1,1,1,1]:
t.color("red")
for a in liste:
if a==1:
t.pendown()
else:
t.penup()
t.forward(COTE)
t.left(90)
t.penup()
t.forward(COTE)
def tracer(liste,taille=400,origineX=-200,origineY=200):
lignes=len(liste)
cols=len(liste[0])
global COTE
COTE=min(taille//lignes,taille//cols)
t.goto(origineX,origineY-COTE)
for l in range(lignes):
for c in range(cols):
case(liste[l][c])
t.goto(origineX,origineY-(l+2)*COTE)
def labyInit(lignes,cols):
liste=[]
for l in range(lignes):
ligne=[]
for c in range(cols):
ligne.append([1,1,1,1])
liste.append(ligne)
return liste
def possibilites(x,y,laby):
pos=[]
lignes=len(laby)
cols=len(laby[0])
if y+1 < cols and laby[x][y+1]==[1,1,1,1]:
pos.append(1)
if x+1 < lignes and laby[x+1][y]==[1,1,1,1]:
pos.append(0)
if y-1 >= 0 and laby[x][y-1]==[1,1,1,1]:
pos.append(3)
if x-1 >= 0 and laby[x-1][y]==[1,1,1,1]:
pos.append(2)
shuffle(pos)
return pos
def kill(x,y,laby):
test=possibilites(x,y,laby)
while test != []:
a=test[0]
laby[x][y][a]=0
x=x+(-1)**(a//2)*((a+1)%2)
y=y+(-1)**(a//2)*((a)%2)
laby[x][y][((a+2)%4)]=0
test=possibilites(x,y,laby)
return laby
def onekill(laby,a,b):
cible=[a,b]
x=cible[0]
y=cible[1]
laby=kill(x,y,laby)
return laby
def recherche(x,y,laby):
lignes=len(laby)
cols=len(laby[0])
if laby[x][y]==[1,1,1,1]:
if y+1 < cols and laby[x][y+1]!=[1,1,1,1]:
return 1
if x+1 < lignes and laby[x+1][y]!=[1,1,1,1]:
return 0
if y-1 >= 0 and laby[x][y-1]!=[1,1,1,1]:
return 3
if x-1 >= 0 and laby[x-1][y]!=[1,1,1,1]:
return 2
return -1
def hunt(laby):
lignes=len(laby)
cols=len(laby[0])
for x in range(lignes):
for y in range(cols):
a=recherche(x,y,laby)
if a != -1:
laby[x][y][a]=0
laby[x+(-1)**(a//2)*((a+1)%2)][y+(-1)**(a//2)*((a)%2)][((a+2)%4)]=0
return [x,y],laby
return [],laby
a=randint(0,7)
b=randint(0,6)
print"la fonction kill a commence ligne",a+1,"colonne",b+1
labyrinthe=onekill(labyInit(8,7),a,b)
tracer(labyrinthe, 300,-300,200)
c,chasse=hunt(labyrinthe)
tracer(chasse, 300,0,200)
print "La chasse trouve la case de la ligne",c[0]+1," et la colonne",c[1]+1
print "cette case est le nouveau depart de la fonction kill"
a=int(input("entrer le nb de lignes"))
b=int(input("entrer le nb de colonnes"))
import turtle
from random import shuffle
t=turtle.Turtle()
t.penup()
#t.goto(-200,200)
t.speed(10)
COTE=40
def case(liste):
for a in liste:
if a==1:
t.pendown()
else:
t.penup()
t.forward(COTE)
t.left(90)
t.penup()
t.forward(COTE)
def tracer(liste,taille=400,origineX=-200,origineY=200):
lignes=len(liste)
cols=len(liste[0])
global COTE
COTE=min(taille//lignes,taille//cols)
t.goto(origineX,origineY-COTE)
for l in range(lignes):
for c in range(cols):
case(liste[l][c])
t.goto(origineX,origineY-(l+2)*COTE)
def labyInit(lignes,cols):
liste=[]
for l in range(lignes):
ligne=[]
for c in range(cols):
ligne.append([1,1,1,1])
liste.append(ligne)
return liste
def possibilites(x,y,laby):
pos=[]
lignes=len(laby)
cols=len(laby[0])
if y+1 < cols and laby[x][y+1]==[1,1,1,1]:
pos.append(1)
if x+1 < lignes and laby[x+1][y]==[1,1,1,1]:
pos.append(0)
if y-1 >= 0 and laby[x][y-1]==[1,1,1,1]:
pos.append(3)
if x-1 >= 0 and laby[x-1][y]==[1,1,1,1]:
pos.append(2)
shuffle(pos)
return pos
def kill(x,y,laby):
test=possibilites(x,y,laby)
while test != []:
a=test[0]
laby[x][y][a]=0
x=x+(-1)**(a//2)*((a+1)%2)
y=y+(-1)**(a//2)*((a)%2)
laby[x][y][((a+2)%4)]=0
test=possibilites(x,y,laby)
return laby
def recherche(x,y,laby):
lignes=len(laby)
cols=len(laby[0])
if laby[x][y]==[1,1,1,1]:
if y+1 < cols and laby[x][y+1]!=[1,1,1,1]:
return 1
if x+1 < lignes and laby[x+1][y]!=[1,1,1,1]:
return 0
if y-1 >= 0 and laby[x][y-1]!=[1,1,1,1]:
return 3
if x-1 >= 0 and laby[x-1][y]!=[1,1,1,1]:
return 2
return -1
def hunt(laby):
lignes=len(laby)
cols=len(laby[0])
for x in range(lignes):
for y in range(cols):
a=recherche(x,y,laby)
if a != -1:
laby[x][y][a]=0
laby[x+(-1)**(a//2)*((a+1)%2)][y+(-1)**(a//2)*((a)%2)][((a+2)%4)]=0
return [x,y],laby
return [],laby
def creerlaby(laby):
cible=[1,1]
while cible != []:
x=cible[0]
y=cible[1]
laby=kill(x,y,laby)
cible,laby=hunt(laby)
return laby
tracer(creerlaby(labyInit(a,b)))
print("voici un labyrinthe de",a,"lignes et",b,"colonnes")