#!/usr/bin/env python3 # -*- coding: utf-8 -*- """ Created on Sun May 29 23:52:56 2022 @author: fjunier Génération de labyrinthe par algorithme Diviser pour régner Voir Exercice 4 du sujet de Terminale NSI https://pixees.fr/informatiquelycee/term/suj_bac/2022/sujet_03.pdf (site de David Roche) Ce n'est pas parfait il reste des problème de chevauchement """ import pyxel import random COULEUR_LABY = 7 #blanc voir https://pypi.org/project/pyxel/ COULEUR_CADRE_APPEL = 1 COULEUR_PASSAGE = 8 class Laby: def __init__(self, nblig, nbcol, vitesse): self.nblig = nblig self.nbcol = nbcol self.vitesse = vitesse self.grille = [[self.numero_case(col, lig) for col in range(self.nbcol)] for lig in range(self.nblig)] self.pile = [(0,0, self.nbcol, self.nblig)] self.murs = [] self.construire_murs() self.murs_detruits = [] self.murs_interdits = [] self.cadre_appel = None self.dernier_passage = None def numero_case(self, col, lig): """ Renvoie un numéro de case associé à un couple (col, lig) """ return lig * self.nbcol + col def construire_murs(self): # MURS horizontaux for lig in range(self.nblig - 1): for col in range(self.nbcol): self.murs.append([(col, lig), (col, lig + 1)]) # MURS verticaux for lig in range(self.nblig): for col in range(self.nbcol - 1): self.murs.append([(col, lig), (col + 1, lig)]) def ouvrir_passage(self, liste_murs): return liste_murs[random.randint(0, len(liste_murs) - 1)] def case_possible(self, col, lig): return (0 <= lig < self.nblig) and (0 <= col < self.nbcol) def update(self): if pyxel.frame_count % self.vitesse == 0: if len(self.pile) > 0: col, lig, largeur, hauteur = self.pile.pop() if largeur <=1 and hauteur <= 1: self.cadre_appel = (col, lig, largeur, hauteur) liste_murs = [sorted([(col, lig), (col + dcol, lig + dlig)]) for (dcol, dlig) in [(-1,0), (1,0), (0,-1), (0,1)] if self.case_possible(col + dcol, lig + dlig)] liste_murs = [mur for mur in liste_murs if mur not in self.murs_interdits] if len(liste_murs) > 0: self.cadre_appel = (col, lig, largeur, hauteur) passage = self.ouvrir_passage(liste_murs ) self.murs_detruits.append(passage) self.dernier_passage = passage self.murs_interdits.extend([mur for mur in liste_murs if mur != passage]) elif largeur <= hauteur: demi_hauteur = hauteur // 2 liste_murs = [[(c, lig + demi_hauteur - 1), (c, lig + demi_hauteur)] for c in range(col, col + largeur) if self.case_possible(c, lig + demi_hauteur)] liste_murs = [mur for mur in liste_murs if mur not in self.murs_interdits] if len(liste_murs) > 0: self.cadre_appel = (col, lig, largeur, hauteur) passage = self.ouvrir_passage(liste_murs ) self.murs_detruits.append(passage) self.dernier_passage = passage self.murs_interdits.extend([mur for mur in liste_murs if mur != passage]) self.pile.append([col, lig, largeur, demi_hauteur]) self.pile.append([col, lig + demi_hauteur, largeur, hauteur - demi_hauteur]) else: demi_largeur = largeur // 2 liste_murs = [sorted([(col + demi_largeur - 1, l), (col + demi_largeur, l)]) for l in range(lig, lig + hauteur) if self.case_possible(col + demi_largeur, l)] liste_murs = [mur for mur in liste_murs if mur not in self.murs_interdits] if len(liste_murs) > 0: self.cadre_appel = (col, lig, largeur, hauteur) passage = self.ouvrir_passage(liste_murs ) self.murs_detruits.append(passage) self.dernier_passage = passage self.murs_interdits.extend([mur for mur in liste_murs if mur != passage]) self.pile.append([col, lig, demi_largeur, hauteur]) self.pile.append([col + demi_largeur, lig, largeur - demi_largeur, hauteur]) def draw(self): if pyxel.frame_count % self.vitesse == 0: pyxel.cls(0) (col, lig, largeur, hauteur) = self.cadre_appel pyxel.line(2 * col, 2 * lig, 2 * col + 2 * largeur, 2 * lig, COULEUR_CADRE_APPEL) pyxel.line( 2 * col + 2 * largeur, 2 * lig, 2 * col + 2 * largeur, 2 * lig + 2 * hauteur, COULEUR_CADRE_APPEL) pyxel.line( 2 * col + 2 * largeur, 2 * lig + 2 * hauteur, 2 * col , 2 * lig + 2 * hauteur, COULEUR_CADRE_APPEL) pyxel.line( 2 * col , 2 * lig + 2 * hauteur, 2 * col , 2 * lig, COULEUR_CADRE_APPEL) for lig in range(1, 2 * self.nblig): for col in range(1, 2 * self.nbcol): if lig % 2 == 1 and col % 2 == 1: pyxel.rect(col, lig, 1, 1, COULEUR_LABY) for case1, case2 in self.murs_detruits: col1, lig1 = case1 col2, lig2 = case2 if col1 == col2: pyxel.rect(2 * col1 + 1, 2 * min(lig1, lig2) + 2, 1, 1, COULEUR_LABY) else: pyxel.rect(2 * min(col1, col2) + 2, 2 * lig1 + 1, 1, 1, COULEUR_LABY) (col1, lig1), (col2, lig2) = self.dernier_passage dc, dl = col2 - col1, lig2 - lig1 pyxel.rect(2 * col1 + 1 + dc, 2 * lig1 + 1 + dl, 1, 1, COULEUR_PASSAGE) def generer(self): pyxel.init(2 * self.nbcol + 1, 2 * self.nblig + 1, "Labyrinthe") pyxel.run(self.update, self.draw) if __name__ == "__main__": maze = Laby(32, 32, 15) maze.generer()