Partage
  • Partager sur Facebook
  • Partager sur Twitter

Génération d'un labyrinthe aléatoire

Sujet résolu
    23 décembre 2021 à 17:29:39

    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

    • Partager sur Facebook
    • Partager sur Twitter
      23 décembre 2021 à 17:59:59

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

      • Partager sur Facebook
      • Partager sur Twitter
        23 décembre 2021 à 18:26:17

        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

        • Partager sur Facebook
        • Partager sur Twitter
          23 décembre 2021 à 22:06:55

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

          • Partager sur Facebook
          • Partager sur Twitter
            23 décembre 2021 à 22:19:59

            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.

            • Partager sur Facebook
            • Partager sur Twitter
              24 décembre 2021 à 10:40:32

              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



              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

              • Partager sur Facebook
              • Partager sur Twitter

              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é.
              • Editeur
              • Markdown