logo

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 :

création du labyrinthe

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

Début Algorithme
  1. Choisissez un lieu de départ.
  2. 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.
  3. 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.
  4. 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 :

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 :

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