Mon projet consiste à réaliser un générateur de labyrinthes aléatoires (non parfaits) et à en chercher les solutions. Les labyrinthes générés doivent posséder 5, 10, 15 ou 20% de murs internes. Comment peut-on contrôler le nombre de murs ouverts ou fermés ?
Une solution peut-être simple mais coûteuse serait d'utiliser la récursivité avec backtracking Tu essaies de te rendre à une sortie en calculant le nombre de murs interne. Si tu te rend à la sortie avec un pourcentage non approprié, tu sais que la solution n'est pas la bonne. Tu reviens en arrière et tu choisis une autre alternative à chaque niveau.
Au départ, tu fais la liste des alternatives à chaque niveau et tu mélanges aléatoirement (avec shuffle)
Tu les passes au niveau suivant dans l'ordre trouvé dans une boucle.
- Edité par PierrotLeFou 5 janvier 2022 à 18:02:21
Le Tout est souvent plus grand que la somme de ses parties.
Ca fait combien de murs 20% du labyrinthe pour commencer?
Si tu veux faire ce que tu veux, la génération du labyrinthe (je ne sais pas du comment tu t'y prends, j'espère avec une classe) doit prendre en argument le pourcentage voulu.
Ensuite une méthode qui peut-être intéressante consiste à générer le labyrinthe en introduisant une structure de pile (c'est pour ça que je parle de classe juste au dessus). A l'aide d'une pile, tu auras facilement quelque chose de "programmable", un exemple ici https://info-llg.fr/commun-mp/textes/laby.py
Indépendamment de la pile maintenant, pendant que tu génères ton labyrinthe, il faudrait tu aies accès à une sorte de compteur de murs sachant la dimension de labyrinthe. Je te laisse choisir la manière de le représenter mais par exemple : "oh non il me reste quatre cases à faire mais je n'ai plus que cinq murs sachant que j'en avais au départ 20% du labyrinthe, je vais donc faire un test aléatoire sur les quatre cases, et oh non les deux premières n'ont rien donné je vais donc mettre les cinq murs sur les deux dernières cases, et ceci aléatoirement et oh mince il reste quatre murs et une seule case, je dois donc remplir entièrement la case..."
Je ne sais pas si je t'aide beaucoup mais c'est l'idée. Programme d'abord un labyrinthe sans te soucier des murs ouverts ou fermés...
@LeMecSansNom: Une pile est sans doute préférable à la récursivité. La profondeur de la récursion est d'environ 1000 selon mes tests. Moi aussi je me suis demandé de quoi a l'air un labyrinthe avec 5% de murs ... J'empilerais la liste des déplacements possibles à un niveau donné (liste de tuples). Si je dois dépiler et réempiler, je supprime le déplacement que je viens d'essayer sans succès. Pour ne pas tourner en rond, je marquerais les endroits où je suis passé. Par exemple, audépart un mur vaut 1, un trou vaut 0, et un trou déjà parcouru vaudrait -1. Quand on dépile, il ne faut pas oublier de restaurer les cases.
Le Tout est souvent plus grand que la somme de ses parties.
Voici mon sujet, se sera peut être plus clair : "Generate random labyrinths with 5, 10, 20, 25, 30 percents of the space as "walls". You should count the number cells visited."
Merci de colorer votre code à l'aide du bouton Code
Les forums d'Openclassrooms disposent d'une fonctionnalité permettant de colorer et mettre en forme les codes source afin de les rendre plus lisibles et faciles à manipuler par les intervenants. Pour cela, il faut utiliser le bouton de l'éditeur, choisir un des langages proposés et coller votre code dans la zone prévue. Si vous utilisez l'éditeur de messages en mode Markdown, il faut utiliser les balises <pre class="brush: python;">Votre code ici</pre>.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.