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

umfred a écrit:

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

Salut !

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

Tu trouveras sûrement ton bonheur ici : https://github.com/topics/maze-generator?l=python

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 Anonyme 23 décembre 2021 à 22:11:17

Bonjour, si vous utilisez l'éditeur HTML du forum c'est le bouton code </> de la barre d'outil que vous devez utiliser pour l'insertion de code.

En image cela donne :

Merci d'éditer votre message précédant.

Salut !

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

Tu trouveras sûrement ton bonheur ici : https://github.com/topics/maze-generator?l=python

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

-
Edité par Anonyme2365 24 décembre 2021 à 10:42:42