Génération d'un labyrinthe

Mise en place de la stratégie

l'affichage du labyrinthe

Nous allons utiliser le module turtle pour tracer le labyrinthe.

Pour modéliser un labyrinthe de n lignes et p colonnes. Nous allons utiliser :

• Des cases modélisées chacune par une liste de 4 booléens.
• Des lignes modélisées par une liste de p cases.
• Le labyrinthe modélisé par une liste de n lignes.

création du labyrinthe

Nous aloons utiliser l'algorithme "Hunt and Kill".

Début 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.	

Fin Algorithme

L'affichage

Voici les différentes parties du code permettant de tracer le labyrinthe.

la case

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)

Le labyrinthe

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))

La fonction kill

La partie Kill est composée de 2 fonctions :

• La fonction possibilites qui cherche une case qui fera partie du chemin.
• La fonction 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))

La fonction hunt

La partie Hunt est composée de 2 fonctions :

• La fonction recherche qui cherche une case qui sera un nouveau point de départ.
• La fonction 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"

Le programme

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")

×

Console Python

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(10,12)))

Executer Ouvrir Sauver pseudocode

  Python avec mathartung.xyz@20018

 end 

Fermer