Bonjour à tous.tes, je cherche à créer un générateur de labyrinthe aléatoire, labyrinthe parfait ou non peu importe tant qu'il peut être résolu, sous la forme d'une liste comme cela : [[1, 0, 1, 1], [1, 0, 0, 1], [1, 1, 0, 1], [1, 1, 0, 1]] avec des 0 pour le chemin et des 1 pour les murs.
J'ai trouvé et compris comment fonctionne cet algorithme :
from random import shuffle, randrange
def make_maze(w = 16, h = 8):
vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]
ver = [["| "] * w + ['|'] for _ in range(h)] + [[]]
hor = [["+--"] * w + ['+'] for _ in range(h + 1)]
def walk(x, y):
vis[y][x] = 1
d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
shuffle(d)
for (xx, yy) in d:
if vis[yy][xx]: continue
if xx == x: hor[max(y, yy)][x] = "+ "
if yy == y: ver[y][max(x, xx)] = " "
walk(xx, yy)
walk(randrange(w), randrange(h))
for (a, b) in zip(hor, ver):
print(''.join(a + ['\n'] + b))
make_maze()
Mais je n'arrive pas à l'adapter simplement pour obtenir le résultat que je voudrais.
Est ce que qqln aurait une solution, une idée ou un autre algorithme qui pourrait réaliser ce que je souhaite plus simplement ou rapidement ? Parce que j'ai déjà bien exploré de nombreux forums et testé plusieurs choses mais je n'arrive à rien de satisfaisant :/
Merci d'avance pour votre aide
D'ailleurs le code vient d'ici : https://rosettacode.org/wiki/Maze_generation#Python
- Edité par Anonyme2365 24 décembre 2021 à 10:47:57
si tu as compris l'algo et le code, tu dois savoir quels sont les caractères utilisés pour faire les murs et les chemins ?
spoiler, les murs ce sont "+--" pour les murs horizontaux, et "|" pour les murs verticaux; et les chemins (espaces libres) des espaces " " (ou "+ " quand on avait un mur).
donc en remplaçant les caractères des murs par un 1 et les espaces libres par un 0, on devrait pas être loin du résultat désiré.
si tu as compris l'algo et le code, tu dois savoir quels sont les caractères utilisés pour faire les murs et les chemins ?
spoiler, les murs ce sont "+--" pour les murs horizontaux, et "|" pour les murs verticaux; et les chemins (espaces libres) des espaces " " (ou "+ " quand on avait un mur).
donc en remplaçant les caractères des murs par un 1 et les espaces libres par un 0, on devrait pas être loin du résultat désiré.
Justement j'ai essayer de faire comme tu l'as dit et ça marche à "moitié" on va dire, c'est à dire qu'après avoir obtenu un premier labyrinthe, je doit créer une boucle pour séparer chaque 1 et 0 et cela marche bien.
Cependant, même si ce résultat est plutôt satisfaisant, j'aurais aimé ne pas avoir besoin de repasser une seconde fois sur le labyrinthe crée pour faire celui que je veux mais merci quand même pour la réponse !!
- Edité par Anonyme2365 23 décembre 2021 à 18:28:16
J'ai commencé il y a quelques temps un projet de labyrinthe géant, pour ma part j'ai choisi un algo Sidewinder que j'ai complexifié manuellement et à l'aide de plusieurs scripts... Bref des heures de boulot ! Et c'est pas fini...
L'un des meilleurs github selon moi c'est celui de gnmathur qui propose plusieurs algos (backtracking, aldous, binary tree, sidewinder, wilson) : https://github.com/gnmathur/aMAZEd
Sinon le code que j'utilise (trouvé je ne sais plus où et modifié à ma sauce je ne sais plus comment ) :
# generates a square maze (size*size) with the sidewinder technique
import numpy as np
import random as rd
def carve_maze(grid:np.ndarray, size:int) -> np.ndarray:
output_grid = np.empty([size*3, size*3],dtype=str)
output_grid[:] = '0'
i = 0
j = 0
while i < size:
w = i*3 + 1
previous_l = []
while j < size:
k = j*3 + 1
toss = grid[i,j]
output_grid[w,k] = '1'
if toss == 0 and k+2 < size*3:
output_grid[w,k+1] = '1'
output_grid[w,k+2] = '1'
previous_l.append(j)
if toss == 1:
# it's impossible to carve outside after preprocessing
# look back, choose a random cell
if grid[i,j-1] == 0:
# reaching from 0
# mandatory to be sure that previous_l has at least one element
# if we are coming from a list of previous cells, choose one and...
r = rd.choice(previous_l)
k = r * 3 + 1
# ...just carve north
# this just carve north if this is the first element of the row (1 element loop)
output_grid[w-1,k] = '1'
output_grid[w-2,k] = '1'
previous_l = []
j += 1
i += 1
j = 0
return output_grid
def preprocess_grid(grid:np.ndarray, size:int) -> np.ndarray :
# fix first row and last column to avoid digging outside the maze external borders
first_row = grid[0]
first_row[first_row == 1] = 0
grid[0] = first_row
for i in range(1,size):
grid[i,size-1] = 1
return grid
def maze_to_string(output_grid: np.ndarray) -> str:
s = ""
for elm in output_grid:
s+=",".join(elm)+"\n"
return s
def main():
n=1
p=0.4
size=500
# 1 (head) N, 0 (tail) E
#np.random.seed(42)
grid = np.random.binomial(n,p, size=(size,size))
processed_grid = preprocess_grid(grid, size)
output = carve_maze(processed_grid, size)
output_string = maze_to_string(output)
file = open("maze_3.txt","w")
file.write(output_string)
file.close()
if __name__ == '__main__':
main()
- Edité par ErispoeLeNarvalo 23 décembre 2021 à 22:11:17
J'ai commencé il y a quelques temps un projet de labyrinthe géant, pour ma part j'ai choisi un algo Sidewinder que j'ai complexifié manuellement et à l'aide de plusieurs scripts... Bref des heures de boulot ! Et c'est pas fini...
L'un des meilleurs github selon moi c'est celui de gnmathur qui propose plusieurs algos (backtracking, aldous, binary tree, sidewinder, wilson) : https://github.com/gnmathur/aMAZEd
Sinon le code que j'utilise (trouvé je ne sais plus où et modifié à ma sauce je ne sais plus comment ) :
# generates a square maze (size*size) with the sidewinder technique
import numpy as np
import random as rd
def carve_maze(grid:np.ndarray, size:int) -> np.ndarray:
output_grid = np.empty([size*3, size*3],dtype=str)
output_grid[:] = '0'
i = 0
j = 0
while i < size:
w = i*3 + 1
previous_l = []
while j < size:
k = j*3 + 1
toss = grid[i,j]
output_grid[w,k] = '1'
if toss == 0 and k+2 < size*3:
output_grid[w,k+1] = '1'
output_grid[w,k+2] = '1'
previous_l.append(j)
if toss == 1:
# it's impossible to carve outside after preprocessing
# look back, choose a random cell
if grid[i,j-1] == 0:
# reaching from 0
# mandatory to be sure that previous_l has at least one element
# if we are coming from a list of previous cells, choose one and...
r = rd.choice(previous_l)
k = r * 3 + 1
# ...just carve north
# this just carve north if this is the first element of the row (1 element loop)
output_grid[w-1,k] = '1'
output_grid[w-2,k] = '1'
previous_l = []
j += 1
i += 1
j = 0
return output_grid
def preprocess_grid(grid:np.ndarray, size:int) -> np.ndarray :
# fix first row and last column to avoid digging outside the maze external borders
first_row = grid[0]
first_row[first_row == 1] = 0
grid[0] = first_row
for i in range(1,size):
grid[i,size-1] = 1
return grid
def maze_to_string(output_grid: np.ndarray) -> str:
s = ""
for elm in output_grid:
s+=",".join(elm)+"\n"
return s
def main():
n=1
p=0.4
size=500
# 1 (head) N, 0 (tail) E
#np.random.seed(42)
grid = np.random.binomial(n,p, size=(size,size))
processed_grid = preprocess_grid(grid, size)
output = carve_maze(processed_grid, size)
output_string = maze_to_string(output)
file = open("maze_3.txt","w")
file.write(output_string)
file.close()
if __name__ == '__main__':
main()
- Edité par ErispoeLeNarvalo il y a environ 12 heures
Merci pour ta réponse je vais aller voir un peu sur ce que tu me proposes pour trouver quelque chose de satisfaisant :))
- Edité par Anonyme2365 24 décembre 2021 à 10:42:42
Génération d'un labyrinthe aléatoire
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
Rammstein - Mein Herz Brent (Piano)