pour créer un labyrinthe parfait de 64 cases par exemple (c'est-à-dire sans case inaccessible), il faut, à partir d'un premier entier choisi entre 1 et 64 définir une liste d'entiers voisins dépendants su voisin préalablement choisi.
Pour des explications plus claires, voici un lien :
Pourquoi tu n'essayes pas plutôt de comprendre le programme du lien que tu nous montres ?
Sachant qu'il est en ruby, et même pas orienté objet, il est plutôt facile à lire si tu sais déjà faire du Python.
En fait, tu pourrais obtenir un programme qui fait le job en traduisant directement le code ruby en Python et tu obtiendrais déjà quelquechose de valable (ruby et Python sont des langages assez proches pour que l'on puisse se permettre de traduire directement un programme de l'un vers l'autre sans trop en fister les idiomatismes)
Alors plutôt que de nous poser la question d'une façon aussi vague, si tu nous disais plutôt ce qui te bloque dans le code que tu lis ?
Edit : Pour l'implémentation en Python, le plus judicieux, en termes de structures de données, sera :
une liste d'entiers (ou une liste de listes) pour représenter ton labyrinthe,
un set pour contenir les frontières
Le reste revient uniquement à traduire ses fonctions en Python, ce qui est facile. Tu n'es pas obligé de faire le même affichage que lui dans un terminal ANSI pendant la construction du labyrinthe. Le mieux serait peut-être que tu passes par tkinter pour avoir un truc portable si tu tiens vraiment à afficher l'animation. Ou n'importe quelle autre bibliothèque graphique. Ce ne sont pas les solutions qui manquent.
Allez, je suis de bonne humeur et j'avais une bonne demi-heure à perdre.
Voilà une version Python du script qui devrait aussi bien tourner sous Windows que sous Linux.
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from random import choice, randrange as rand
##
# Dimensions du labyrinthe
width = 10
height = 10
##
# Constantes servant à décrire les directions des passages
N, S, E, W = 1, 2, 4, 8
IN = 0x10
FRONTIER = 0x20
OPPOSITE = {E: W, W: E, S: N, N: S}
##
# Structures de données
grid = [([0] * width) for _ in range(height)]
frontier = set()
##
# Méthodes utilitaires
def add_frontier(x, y):
if (x >= 0 and y >= 0 and y < len(grid)
and x < len(grid[y]) and grid[y][x] == 0):
grid[y][x] |= FRONTIER
frontier.add((x, y))
def mark(x, y):
grid[y][x] |= IN
add_frontier(x-1, y)
add_frontier(x+1, y)
add_frontier(x, y-1)
add_frontier(x, y+1)
def neighbors(x, y):
if x > 0 and (grid[y][x-1] & IN):
yield (x-1, y)
if x + 1 < len(grid[y]) and (grid[y][x+1] & IN):
yield (x+1, y)
if y > 0 and (grid[y-1][x] & IN):
yield (x, y-1)
if y + 1 < len(grid) and (grid[y+1][x] & IN):
yield (x, y+1)
def direction(fx, fy, tx, ty):
return {(fx < tx): E,
(fx > tx): W,
(fy < ty): S,
(fy > ty): N}[True]
def is_empty(cell):
return cell == 0 or cell == FRONTIER
def display_maze():
print()
print(' ' + '_' * (len(grid[0]) * 2 - 1))
for y, row in enumerate(grid):
line = '|'
for x, cell in enumerate(row):
# Dessin du mur ou du passage Sud
if is_empty(cell) and y+1 < len(grid) and is_empty(grid[y+1][x]):
line += ' '
else:
line += ' ' if cell & S else '_'
# Dessin du mur ou du passage Est
if is_empty(cell) and x+1 < len(row) and is_empty(row[x+1]):
if y+1 < len(grid) and (is_empty(grid[y+1][x]) or
is_empty(grid[y+1][x+1])):
line += ' '
else:
line += '_'
elif cell & E:
line += ' ' if (cell | row[x+1]) & S else '_'
else:
line += '|'
print(line)
##
# Exécution du script
if __name__ == '__main__':
from sys import argv
if len(argv) == 3:
width, height = map(int, argv[1:])
grid = [[0] * width for _ in range(height)]
mark(rand(width), rand(height))
while frontier:
##
# Choix d'un voisin à la frontière
x, y = choice(list(frontier))
frontier.remove((x, y))
nx, ny = choice(list(neighbors(x, y)))
##
# Création d'un passage
dir = direction(x, y, nx, ny)
grid[y][x] |= dir
grid[ny][nx] |= OPPOSITE[dir]
mark(x, y)
## DEBUG :
# print("frontier =", frontier)
# print("(%d, %d) -> (%d, %d)" % (x, y, nx, ny))
# display_maze()
# input("Appuyez sur Entree pour continuer")
display_maze()
Vu que ça s'affiche mal dans les blocs de code, voilà un screen du résultat :
Note : Je suis pas super fan des labyrinthes générés par cet algo, aussi parfaits soient-ils.
Je trouve ceux qui résultent du recursive backtracking beaucoup plus esthétiques (et moins triviaux à résoudre pour un humain). D'autant plus que l'algo en lui-même est diaboliquement simple.
Décidément, j'avais encore un peu de temps à perdre.
Voilà une version Python de l'algorithme de recursive backtracking. C'est une implémentation itérative, qui évite donc d'exploser la pile d'appels en cas de TRÈS GROS labyrinthes, contrairement au code que j'ai linké au-dessus. Je le trouve beaucoup plus élégant que Prim.
L'idée de base, c'est de parcourir le labyrinthe de façon aléatoire, en creusant des couloirs au fur et à mesure, et de revenir sur nos pas jusqu'à la dernière intersection quand on est bloqué (d'où le "backtracking"), pour continuer à creuser jusqu'à ce que le labyrinthe soit parfait.
Dans la pratique, on fait ça en maintenant une pile (position, direction). On commence au point 0, 0 (en haut à gauche). On tire les 4 directions (nord, sud, est, ouest) dans un ordre aléatoire, et on empile les 4 triplets (0, 0, direction) sur une pile que j'ai appelée walls. Une fois que l'on a fait ça, on peut commencer à bouger : on dépile le premier mouvement, ça nous dit quel mur on doit creuser. Si ce mur ne débouche pas sur un couloir déjà creusé (et s'il ne sort pas du labyrinthe), alors on le fait tomber et on empile les 4 mouvements possibles depuis la case suivante. Si on se retrouve complètement bloqué à une case, alors le fait de dépiler le prochain mouvement nous fera sauter à la dernière intersection, et prendre une direction que l'on n'a pas encore essayée. L'algo s'arrête quand il n'y a plus de mur à creuser (on les essaye tous). Il est linéaire en temps et en mémoire.
#!/usr/bin/env python3
from random import sample
from time import sleep
width = 10
height = 10
N, S, E, W = 1, 2, 4, 8
OPPOSITE = {N: S, S: N, E: W, W: E}
MOVE = {N: lambda x, y: (x, y-1),
S: lambda x, y: (x, y+1),
E: lambda x, y: (x+1, y),
W: lambda x, y: (x-1, y)}
def carve_maze():
random_ways = lambda: sample((N, S, E, W), 4)
maze = [[0] * width for _ in range(height)]
walls = [(0, 0, d) for d in random_ways()]
while walls:
cx, cy, way = walls.pop()
nx, ny = MOVE[way](cx, cy)
if 0 <= ny < height and 0 <= nx < width and maze[ny][nx] == 0:
maze[cy][cx] |= way
maze[ny][nx] |= OPPOSITE[way]
walls += [(nx, ny, d) for d in random_ways()]
#draw(maze)
#sleep(0.05)
return maze
def draw(maze):
print(' ' + '_' * (width * 2 - 1))
for y, row in enumerate(maze):
line = ['|']
for x, cell in enumerate(row):
line.append(' ' if cell & S else '_')
if cell & E:
line.append(' ' if (cell | maze[y][x+1]) & S else '_')
else:
line.append('|')
print(''.join(line))
print()
if __name__ == '__main__':
from sys import argv
if len(argv) == 3:
width, height = map(int, argv[1:])
draw(carve_maze())
Le résultat est plus joli et "naturel" que celui de l'algorithme de Prim :
Bon, je m'arrête pour aujourd'hui avec les labyrinthes, parce que si je continuais sur ma lancée, ce serait pour générer des trucs de ce genre (avec les couloirs qui peuvent passer les uns au-dessus des autres) :
Non pas que ça soit difficile à faire ; c'est une simple adaptation du backtracking. Simplement j'ai carrément la flemme de dessiner ça sur une image ou dans une fenêtre tkinter.
Edit : Enfin ça peut être un bon exercice pour débutants :
Faire en sorte que la sortie du labyrinthe soit en bas à droite et que celle-ci ne puisse se trouver qu'au bout d'un couloir.
Trouver un moyen de représenter deux niveaux pour les couloirs en s'inspirant de la représentation que j'ai utilisée.
Adapter l'algorithme du backtracking pour générer des labyrinthes à deux niveaux.
Dessiner le labyrinthe (optionnellement : sous forme d'animation) dans un canvas tkinter, une fenêtre pygame ou autre.
Tu m'a coiffé au poteau ! J'avais fait un algorithme qui marchait très bien (au bout de quelques heures tout de même)... Enfin bref, ça m'aura fait une expérience de résolution de problème et ça c'est toujours bon à prendre.
Tu m'a coiffé au poteau ! J'avais fait un algorithme qui marchait très bien (au bout de quelques heures tout de même)... Enfin bref, ça m'aura fait une expérience de résolution de problème et ça c'est toujours bon à prendre.
Vu comme ce topic est parti, je pense que tu peux quand même nous montrer ton programme sur ce thread. Comme ça tu pourrais peut-être recueillir des conseils pour l'améliorer (et puis deux versions plutôt qu'une, c'est toujours bon à prendre).
Alors petite explication avant de montrer le code. Je me suis inspiré de la méthode exaustive de l'exploration de labyrinthe (voir : http://www.ilay.org/yann/articles/maze/). Ce qui donne ceci en langage humain : 1. On prend la première case # Début de la fonction récursive 2. On la marque comme visitée 3. On liste ses voisines 4. Si les voisines on déjà toutes été visitées : a. On recommence avec la case précedente 5. Sinon (si au moins une voisine n'a pas été visitée) a. On ne garde que les voisines non visitées b. On en choisit une au hazard c. Si le chemin n'est pas complet : on recommence avec la case choisie d. Sinon on renvoie le chemin
Il n'y a pas d'application graphique, je me suis simplement contenté de créer le chemin d'exploration qui relie chaque case par un chemin unique (la définition d'un labyrinthe parfait). Vous verrez souvent que je jongle entre coordonnées à une dimension (pour les listes) et à deux dimension (pour appeler la fonction et pour récupérer les voisines). Si ce n'est pas claire pour vous dites le moi, je suis avide de suggestions car cela ne fait que cinq mois que je programme en python.
Voilà le code (commenté en Français/Anglais) :
import random
une_dimension = lambda x, y, m: y*m+x
dimension_x = lambda z, m: z % m
dimension_y = lambda z, m: int(z/m)
historique = [0]
etatCase = []
chemin = []
caseX = 0
caseY = 0
m = 8
n = 8
for i in range(m * n):
etatCase.append(0)
def verrif_case (coorX, coorY, m, n):
global historique
global etatCase
# On marque la case comme visitée / We mark the box as visited
etatCase[une_dimension(coorX, coorY, m)] = 1
# On liste les voisines / We list the neighbors
voisine = []
if coorX > 0:
voisine.append(une_dimension(coorX-1, coorY, m))
if coorY > 0:
voisine.append(une_dimension(coorX, coorY-1, m))
if coorX < m-1:
voisine.append(une_dimension(coorX+1, coorY, m))
if coorY < n-1:
voisine.append(une_dimension(coorX, coorY+1, m))
# 'a' : voisine(s) visités / neighbor(s) visited
a = 0
for i in range(len(voisine)):
if etatCase[voisine[i]] == 1:
a = a + 1
# Si les voisines ont déjà été toutes visitées,
# on recommence avec la case précédente
# If the neighbors have alreaday been visited all,
# we start again with the previous box
voisine_a_supprimer = []
if a == len(voisine):
nextZ = historique[len(historique) - 2]
nextX = dimension_x(nextZ, m)
nextY = dimension_y(nextZ, m)
del voisine
del historique[len(historique) - 1]
verrif_case(nextX, nextY, m, n)
# Sinon,
# Else,
else :
# On ne garde que les voisines non visitées
# We only keep the neighbors not visited
for i in range(len(voisine)):
if etatCase[voisine[i]] == 1:
voisine_a_supprimer.append(voisine[i])
for i in range(len(voisine_a_supprimer)):
voisine.remove(voisine_a_supprimer[i])
# On en choisit une au hazard
# We choose a random
nextZ = voisine[random.randrange(len(voisine))]
nextX = dimension_x(nextZ, m)
nextY = dimension_y(nextZ, m)
del voisine
historique.append(une_dimension(nextX, nextY, m))
chemin.append(une_dimension(nextX, nextY, m))
# On recommence avec la case choisie
# We start again with the box choosed
if len(chemin) < m*n:
verrif_case(nextX, nextY, m, n)
# Si le chemin est complet on retourne le chemin
# If the path is complete we return path
elif len(chemin) == m*n:
return chemin
chemin.append(une_dimension(caseX, caseY, m))
verrif_case(caseX, caseY, m, n)
print(chemin)
C'est compliqué à lire et ce n'est pas du tout évident à comprendre mais si vous dessinez un labyrinthe, que vous numérotez toutes les cases de 0 à 63 il ne vous reste plus qu'à relier dans l'ordre et deux à deux les numéros qui sortent pour voir le chemin général du labyrinthe. Ensuite vous tracez les murs là où le chemin ne passe pas et vous obtenez le labyrinthe.
J'espère que vous serez critiques et indulgens si mon code n'est pas très optimisé.
Je le regarde en détail et j'édite ce post avec mes commentaires.
Edit:
Lignes 19 et 20 :
global historique
global etatCase
Ces deux variables sont déjà dans le scope du module (donc accessibles depuis ta fonction) donc tu peux virer ces deux lignes. D'une façon générale, n'utilise jamais global. C'est plutôt dangereux et très, très rarement utile (j'aurais même plutôt tendance à dire que ça ne l'est jamais : que des inconvénients, aucun avantage).
Ligne 67:
nextZ = voisine[random.randrange(len(voisine))]
Ça fonctionne, mais c'est dommage de pas utiliser la fonction choice qui est faite pour ça :
nextZ = random.choice(voisine)
J'ai un peu de mal à comprendre pourquoi tu n'as pas représenté le labyrinthe directement comme une donnée en mémoire. Certes ça n'empêche pas ton algorithme de tourner, mais imagine qu'après coup tu veuilles afficher ton labyrinthe dans un petit jeu pour permettre à l'utilisateur de le parcourir, comment tu fais ? Tu crois pas que ce serait plus simple de le créer directement ?
Là, tu te retrouves avec trois tableaux au lieu de deux, et tu transvases tes cases des unes vers les autres suivant qu'elles ont été visitées ou non…
J'ai un peu de mal à comprendre pourquoi tu n'as pas représenté le labyrinthe directement comme une donnée en mémoire. Certes ça n'empêche pas ton algorithme de tourner, mais imagine qu'après coup tu veuilles afficher ton labyrinthe dans un petit jeu pour permettre à l'utilisateur de le parcourir, comment tu fais ?
Quand tu dit représenter le labyrinthe comme une donnée, tu veux dire quoi ? Tu peux me donner un exemple s'il te plait ?
Et pour le petit jeu, je pensait recréer deux listes (une pour les murs verticaux et l'autre pour les murs horizontaux) et à partir de là reparcourir la liste chemin en cassant les murs à chaque fois que je passe d'une case à l'autre. J'obtiendrais deux listes qui contiendraient uniquement les murs à afficher.
Ben, si tu regardes mon deuxième code, par exemple, le labyrinthe est complètement représenté dans la double-liste maze.
En l'occurrence, j'ai utilisé la même astuce que sur le lien du premier topic, c'est-à-dire que chaque cellule est un entier, et suivant les bits qui sont activés ou non sur cet entier, on sait si d'une cellule on peut aller dans une direction donnée ou non. C'est un choix d'implémentation comme un autre, mais le principe reste le même : on a un tableau à deux dimensions qui représente le labyrinthe et chaque élément est une cellule, avec ses murs comme attribut.
Comme nohar j'utilise une pile et je reviens sur mes pas quand je suis bloqué.
from random import shuffle,randint
from pygame import *
w,h = 40,30
scr = display.set_mode((w*20,h*20))
scr.fill(-1)
display.flip()
event.clear()
time.wait(100)
maze = [[[] for x in range(w)] for y in range(h)]
foo = [(randint(0,w-1),randint(0,h-1))]
s = [(0,1),(1,0),(0,-1),(-1,0)]
while foo:
x,y = foo[-1]
shuffle(s)
for sx,sy in s:
X = sx + x
Y = sy + y
if 0<=X<w and 0<=Y<h and not maze[Y][X]:
maze[Y][X].append((-sx,-sy))
display.update(scr.fill(0,(X*20+1-sx,Y*20+1-sy,18,18)))
maze[y][x].append((sx,sy))
display.update(scr.fill(0,(x*20+1+sx,y*20+1+sy,18,18)))
foo.append((X,Y))
time.wait(20)
break
else:
foo.pop()
while event.wait().type != QUIT: pass
Quelle est la signification du delimiteur " |= ", l.26 du code de recursive backtracking de nohar? Mes recherches sur le net s'etant revelees infructueuses.
merci à tous pour toutes vos contributions. Je suis hyper débutant en Python d'où ma question un peu naïve au départ et mon incapacité pour l'instant à traduire du Ruby en Python. Mais je vais essayer de comprendre toutes vos contributions et cela m'aidera bien à progresser.
Nohar, je reviendrai peut-être vers toi pour te poser quelques questions sur ton premier code.
Merci à tous et n'hésitez pas à poursuivre ce fil passionnant
Quelle est la signification du delimiteur " |= ", l.26 du code de recursive backtracking de nohar? Mes recherches sur le net s'etant revelees infructueuses.
EDIT: c'est bon, help() m'est venu en aide!
Par contre moi je veux bien savoir parce que je n'ai pas trouvé.
Bon, vu qu'on ma posé la question plusieurs fois par MP en plus d'ici, je vais donner plus de détails sur la façon dont fonctionne mon code.
D'abord, mon labyrinthe est représenté par un tableau d'entiers, à deux dimensions. Chaque case du tableau correspond à une cellule du labyrinthe.
Pour représenter l'état de mes cellules, j'emploie une technique utilisée assez couramment en C : j'utilise des flags. En gros, j'active ou non des drapeaux sur chaque cellule pour dire s'il y a un mur ou non dans telle direction.
N, S, E, W = 1, 2, 4, 8
Le choix des valeurs de N, S, E et W (vous aurez compris que ça signifie "North, South, East, West") n'est pas dû au hasard : il s'agit de puissances de 2. Si je représente ces flags en binaire, cela me donne ceci :
N: 0001 # 1
S: 0010 # 2
E: 0100 # 4
W: 1000 # 8
Au passage, on remarquera qu'avec seulement 4 options, le nombre de combinaisons possibles est égal au nombre de valeurs que l'on peut représenter sur 4 bits, soit 16.
Bien, maintenant prenons une cellule cell. Par défaut, les cellules de mon labyrinthe sont toutes égales à 0, ce qui veut dire qu'elles ont toutes 4 murs. Si je veux modifier cette cellule pour dire que l'on a maintenant le droit d'aller vers le sud quand on s'y trouve, j'utilise l'opérateur OU bit à bit |. En binaire :
# cell == 0
cell = cell | S # 0b0000 | 0b0010
# cell est maintenant égal à 0010 en binaire.
Si j'abats un nouveau mur sur cette cellule (mettons le mur Est), cela me donnera :
# cell == 2 # 0010 en binaire
cell |= E # Ceci est équivalent à "cell = cell | E"
# cell est maintenant égal à 0110 en binaire
De cette façon, lorsque je me trouve sur cette cellule et que je veux savoir si je peux me déplacer dans une direction donnée, j'ai juste à tester si le flag correspondant est activé, en utilisant l'opérateur ET bit à bit, & :
C'est pourquoi, par exemple pour abattre le mur Nord de la case (5, 5), j'active le flag N en (5, 5) ainsi que le flag S en (5, 4). Si l'on peut aller vers le Nord depuis (5, 5), ça veut dire que l'on peut aller vers le Sud depuis (5, 4).
C'est un truc sympa à savoir, parce que ces opérations bit à bit sont extrêmement rapides à exécuter, et que si j'avais à coder ce programme en C, un simple octet (un unsigned char) suffirait largement à encoder l'état d'une cellule. En fait, j'aurais même deux fois plus de place que nécessaire sur un octet, puisque je ne me sers que de 4 bits (= un nibble), mais à moins d'avoir une contrainte très forte sur la taille des données (comme quand on définit un protocole de transmission, par exemple) on ne descend jamais en-dessous de l'octet pour représenter une donnée unitaire. En gros, c'est une technique très utile si l'on veut représenter l'état d'un objet par un petit ensemble de valeurs booléennes (= d'options), parce qu'elle est quasiment gratuite en performances (sur des entiers plus petits que 64 bits), qu'on ne peut pas faire plus économe en mémoire, et qu'elle fait appel à une syntaxe très simple.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.