Discussion :

[sourivore]

Bonjour à tous,

A l'aide d'un algorithme j'ai obtenu un labyrinthe parfait.
Donc entre 2 cases il y a un et un seul chemin.
Maintenant j'aimerais pouvoir éviter la résolution à la main gauche ("Je tourne toujours à gauche").
Ainsi à partir de mon labyrinthe parfait j'aimerais créer un labyrinthe "imparfait" (avec quelques cycles).

Quelle est le meilleur algorithme possible pour effectuer cela?

[khayyam90]

Bien le bonjour,

A première vue, je dirais que tu dois casser quelques murs de ton labyrinthe. S'il est parfait, (construit à partir d'un ensemble de Tarjan, non ?), il y a un seul chemin pour aller de n'importe quel endroit à n'importe quel autre endroit.
Tu as donc le nombre maximal de murs pour ta configuration.
Toute suppression de mur va créer des chemins doublons.

Deux chemins pour aller de A à B tu peux tourner en rond.

Tu choisis les murs à casser aléatoirement, ça marchera très bien. Le nombre de murs à casser dépend de la taile de ton labyrinthe et du niveau d'imperfection que tu veux ajouter.

[sebus]

oui casser des murs et la solution la plus simple !!

Par contre il y a des cas ou tu risques de ne créer que des impasses.....et pas de cycle !!! Donc le résultat ne peut etre efficace qui si tu casses un certain nombre de mur...

Solution bourinne : t'enlèves tout les murs !!! (bon ok le mec en main gauche vas trouver la sortie en suivant les bords....)

Si tu veux etre super vicieux : l'entrée ou la sortie du labyrinthe n'est pas forcement sur un bord !!! Pourquoi ne pas en avoir un qui a une sortie par les sous sols ?

Bon sinon revnons sérieux sur ta demande de base (quoique les 2 techniques décrites surtout la 2ème fait bien chier un main gauche )

Je pense qu'il faut que tu te tournes vers la théorie des arbres et graphes pour résoudre ton probleme....
C'est ptet sortir un peu les grands moyen, mais si on regarde de plus pres, un labyrinthe parfait correspond a un arbre, un labyrinthe non parfait à un graphe avec des cycles....
Donc l'idée serait de schématiser ton laby parfait en arbre, puis de faire en sorte par construction de le transformer en graphe avec des cycles...

Je me souviens plus trop des algos, mais ca doit pouvoir se retrouver qqpart !!

[sebus]

sinon au fait tu sais sortir de la maniere la plus courte de ton labyrinthe parfait (bon ok la plus courte c pas dur, y'a k'une maniere de sortir !!)

Et pour un labyrinthe vicieux, sais tu le faire?

Si c non, les graphes t'aideront grandement.....

Sinon il existe une maniere simple et intuitive qui se ramène à la théorie des graphes mais qui marche tres bien (si tu connais pas de solution, cherches un peu tu devrais pouvoir trouver une idée efficace assez rapidement)

[sourivore]

Merci pour vos réponses,

Je vais essayer de casser quelques murs (par contre combien pour un labyrinthe nxn je ne sais pas encore)

En ce qui concerne la solution de plus courte chemin en fait elle m'importe peu étant donné que tout ce que je veux c'est qu'il y ait au moins une solution.

Sebus l'idée du sous-sol en fait est ce à quoi je pensais.
Tu démarres en haut à gauche et tu dois aller jusqu'à une case sous conditions.

En fait tout ceci est pour le site que je fais je vais vous expliquer les grandes lignes ainsi que les questions qui restent en suspens.

Ce site est un site avec authentification. Ainsi chaque joueur aura son propre personnage.
A la connexion ainsi qu'à la fin d'un labyrinthe, un nouveau labyrinthe est créé.
Le joueur se retrouve dans ce labyrinthe et son but est d'aller vers la sortie.
Le joueur aura un certain nombre de déplacement par heure.

A ceci s'ajoute plusieurs principes :

- Des portes qui ne peuvent s'ouvrir qu'avec des cles qui se trouvent dans le labyrinthe.
- Des trappes qui ouvrent des murs du labyrinthe
- Pour pouvoir sortir, il faudra trouver la sortie + 3 objets disséminés dans le labyrinthe.
- D'autres options à déterminer comme les pièges, des marchands, des combats, des rencontres avec d'autres joueurs...

Question en suspens :

- Comment stocker efficacement dans ma BDD MySQL un labyrinthe (en effet un labyrinthe est nominatif pour éviter que les joueurs se filent des tuyaux)?
Mon labyrinthe doit faire 30x30 et je voudrais trouver une manière plus efficace que de stocker des chaines de 900 caractères pour chaque joueur.

[sebus]

Si tu utilises la technique de casser des murs, il va falloir que tu tests tes labyrinthes pour savoir si tu as bien un cycle ou non...

L'idée du sous sol c'est en gros ben la sortie au milieu du labyrinthe comme si on trouvait la trappe providentielle...

Pour stocker en base, apart stocker une chaine de caracteres ou des bits (ca je ne pense pas que ce soit faisable) ba y'a pas grand chose d'autre a faire ......
Fo bien de toute facon stocker chaque case en sachant si cette case est un mur ou non ......

Mais sinon a koi te sert ta base? tu pourrais pas utiliser du XML ou des fichiers plat ?