Partage
  • Partager sur Facebook
  • Partager sur Twitter

vérifier qu'un labyrinthe peur se résoudre python

.

Sujet résolu
    25 juillet 2021 à 16:59:15

    Bonjour, bonjour,

    je souhaiterais créer un labyrinthe représenté par une liste à 2 dimensions dont les éléments prennent deux valeurs: 1 pour un mur et 0 pour une case libre, donc sur laquelle on peut circuler.

    voilà mon code:

    class Level:
        def __init__(self,nOfWalls):
            self.__grid=[]
            self.grid_is_valid=False
            self.__nOfWalls=nOfWalls%194
            self.generate_grid()
            self.check_grid_validity()
        @property
        def nOfWalls(self):
            return self.__nOfWalls
        @property
        def grid(self):
            return self.__grid
        def generate_grid(self):
            proba=self.nOfWalls/225
            for i in range(15):
                self.grid.append([])
                for j in range(15):
                    if random.random()<=proba:
                        self.grid[i].append(1)
                    else:
                        self.grid[i].append(0)
        def check_grid_validity(self):
            p=[0,0]
            if self.grid[p[0]][p[1]+1] == 0:
                self.move([p[0],p[1]+1])
            if self.grid[p[0]][p[1]-1] == 0:
                self.move([p[0],p[1]-1])
            if self.grid[p[0]+1][p[1]] == 0:
                self.move([p[0]+1,p[1]])
            if self.grid[p[0]-1][p[1]] == 0:
                self.move([p[0]-1,p[1]])
            if not self.grid_is_valid:
                self.generate_grid()
                self.check_grid_validity()
        def move(self,p):
            if not self.grid_is_valid:
                if self.grid[p[0]][p[1]+1] == 0:
                    if p == [14,13]:
                        self.grid_is_valid=True
                    else:
                        self.move([p[0],p[1]+1])
                if self.grid[p[0]][p[1]-1] == 0:
                    self.move([p[0],p[1]-1])
                if self.grid[p[0]+1][p[1]] == 0:
                    if p == [13,14]:
                        self.grid_is_valid=True
                    else:
                        self.move([p[0]+1,p[1]])
                if self.grid[p[0]-1][p[1]] == 0:
                    self.move([p[0]-1,p[1]])

    mais avec cette méthode, le programme me retourne une RecursionError (plutôt logique). Comment faire?

    Merci d'avance de votre aide!

    • Partager sur Facebook
    • Partager sur Twitter
      25 juillet 2021 à 17:36:58

      Comment faire?

      Ne pas faire de récursif.

      • Partager sur Facebook
      • Partager sur Twitter

      "il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"

        25 juillet 2021 à 18:33:34

        Merci déjà de ta contribution, mais pourrais-tu développer un peu plus? Me donner des pistes? Aurais-tu des idées?
        • Partager sur Facebook
        • Partager sur Twitter
          25 juillet 2021 à 22:59:23

          Bonjour,

          Il y a une tonne d'algorithmes différents pour générer des labyrinthes. Ta méthode du «j'en génère un et je vérifie qu'il existe une solution» est lourde. Il vaut mieux en créer un dont tu es certain qu'il possède une solution tout de suite = un labyrinthe qui possède la propriété que toute case peut être reliée à n'importe quelle autre par un chemin unique.

          Mon algo préféré est sans doute l'algorithme d'Eller. Tu trouveras beaucoup d'infos sur le net sur cet algo ou n'importe quel autre (avec backtrack, par divisions récursives, …).

          Un ouvrage sympa : Mazes for Programmers: Code Your Own Twisty Little Passages, J. Buck.

          Certains algorithmes sont plus adaptés pour produire certains labyrinthes, avec beaucoup/peu de  cul-de-sac, de longs chemins, …

          • Partager sur Facebook
          • Partager sur Twitter
            25 juillet 2021 à 23:29:34

            Un logo A*.
            • Partager sur Facebook
            • Partager sur Twitter

            "il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"

              26 juillet 2021 à 10:32:35

              the-chellist a écrit:

              Bonjour, bonjour,

              je souhaiterais créer un labyrinthe représenté par une liste à 2 dimensions dont les éléments prennent deux valeurs: 1 pour un mur et 0 pour une case libre, donc sur laquelle on peut circuler.

              voilà mon code:

              Plutôt que de donner du code indique quel algorithme tu utilises pour générer ton labyrinthe (cf. message de WhiteCow) et décris en mots cet algorithme. Par ailleurs, ta POO avec ta classe et ses méthodes, les attributs privés, les getters ne font qu'obscurcir l'algorithme que tu utiliserais, sans compter les constantes magiques. Même ta structure de données n'est pas claire. Pas certain que la récursivité soit ici adaptée.

              White Crow a écrit:

              Mon algo préféré est sans doute l'algorithme d'Eller. Tu trouveras beaucoup d'infos sur le net sur cet algo ou n'importe quel autre (avec backtrack, par divisions récursives, …).

              Un ouvrage sympa : Mazes for Programmers: Code Your Own Twisty Little Passages, J. Buck.


              Je ne connaissais pas l'algo d'Eller, merci de cette référence. L'auteur du livre cité a un blog où l'algo est expliqué et accompagné d'un applet javasript :

              permettant de réaliser pas à pas l'algo

              • Partager sur Facebook
              • Partager sur Twitter

              vérifier qu'un labyrinthe peur se résoudre python

              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
              • Editeur
              • Markdown