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 ?

[sebus]

autre chose qui me viens à l'eesprit:

Si tu veux en faire un site (donc un truc + ou - sérieux), vaut peut etre mieux sortir l'artillerie lourde est configuré tes laby comme tu veux plutot qu'enlever des murs au hasards sans savoir forcement le nombre de cycles que cela cré....... De plus tu maitriserais mieux le niveau de difficulté je pense !!!!

[sourivore]

Oui mais les joueurs se donneraient la solution.
De plus, l'utilisation de XML/Fichier plat ne me semble pas conseillée étant donnée que j'ai déjà une BDD et que celle-ci est indexée et donc plus facile à maitriser lors des requêtes.

[khayyam90]

le simple fait de casser un mur va créer un cycle.

Prenons le cas extrème : 4 cases disposées en carré avec juste un mur qui sépare 2 cases (donc le mur est long comme une case). Si tu casses le mur, tu crées un cycle de 4 cases. Il est évident qu'un humain aura vite fait de comprendre ce mini cycle.
Ce cas est très rare, et dépend bien sûr de la taille de ton labyrinthe.

Pour stocker efficacement ces données, je pense qu'il va falloir résonner en quadtree . Ceci permettra de rapidement repérer les cases voisines de la case où se situe le joueur sans avoir à charger tout le labyrinthe.

[sebus]

* *******
* *** **
* *** ***
** *** **
** £ ***
*** ******

Si je casse le £ je ne cré pas de cycle ........

[sourivore]

J'aurais du trouver ça moi-même.

Sinon j'ai un peu de mal à saisir la notion de quadtree.
Qu'est-ce que ça donne dans la BDD avec un exemple de labyrinthe 4x4?

PS : Sebus : forcément que ça ne crée pas de cycle ton laby n'est pas parfait à l'origine.

[khayyam90]

@Sebus : le labyrinthe que tu proposes n'est pas parfait. Des murs font plus d'une case d'épaisseur. De plus, pour reprendre ton exemple, la case sous le £ n'est accessible par aucun chemin, à moins de casser £, ce n'est donc pas non plus un labyrinthe parfait de ce point de vue là.

L'idée du quadtree est d'utiliser la position d'un objet pour l'adresser, qui finalement revient au même qu'un tableau si on se place en domaine discret Donc fausse bonne idée.

[sebus]

Pour mon laby, on voit mal les chemins car un espace ne prend pas la meme place qu'une *

Ce que je veux dire, c'est que si il y a un chemin + une impasse pas encore accessible :

Si tu casses le mur qui permet d'acceder à l'impasse, tu ne cré pas de cycle.

Sinon laby parfait = forcement un mur fait 1 d'épaisseur ? (ca a jamais été dit depuis le debut, la seule condition était un seul chemin qui va de l'entré à la sortie + ramifications ne créant pas de cycle)

[khayyam90]

donc je propose que sourivore nous mette une photo/dessin de son labyrinthe parfait
sebus et moi avons l'air de bien camper sur nos positions.

[sebus]

Nan nan, c pas que je campe, mais c juste qu'il nous manque un détail !!!

Par contre si un mur fait 1 de large au max, je chercherais un contre exemple a ce ke tu avances....

En attente de précition de sourivor alors

[Sivrît]

Pour mon laby, on voit mal les chemins car un espace ne prend pas la meme place qu'une *

Sinon laby parfait = forcement un mur fait 1 d'épaisseur ? (ca a jamais été dit depuis le debut, la seule condition était un seul chemin qui va de l'entré à la sortie + ramifications ne créant pas de cycle)

Disons que par "casser un mur" on sous-entend un peu autoriser le passage entre deux cases du laby, et une zone morte (inaccessible) ne fait pas vraiment parti du laby. Suivant la représentation du laby (suivant si les murs sont des cases pleines ou plutôt des séparations entre les cases), casser un mur ne se fait pas tout à fait pareil.


Par contre, si supprimer un mur d'un laby parfait crée systématiquement un cycle, il ne met pas systématiquement la main courante en échèque. Notamment, si l'entrée et la sortie sont situées toutes deux sur le bord du laby alors faire des cycles en supprimant des murs n'empèche pas la main courrante de marcher. Il faudrait que l'une ou l'autre (ou une clef) soit sur un "ilot". Je crois que pour déterminer cela il faudrait considérer les murs comme un graphe. La sortie et l'entrée devraient être sur des murs non connexes.

Autre détail, s'il y a des portes et que l'on supprime des murs, il faudra faire attention à ne pas contourner une porte. Par exemeple donner des numéros aux zones que délimitent les portes (avec des parcours) et faire attention de ne supprimer que des murs entre deux cases de la même zone. Ces numéros pourraient aussi servir à placer les clefs.

[sourivore]

Tout à fait d'accord.

Et si vous voulez des exemples de labyrinthes parfaits aléatoire il faut aller sur le début de mon site ICI

Bien sûr le laby est vu en entier et n'est pas très bon mais pour le moment ce qui m'importe plus c'est la génération du labyrinthe.
Tu peux casser n'importe quel mur et la tu créeras forcément un cycle.

En effet un labyrinthe parfait c'est un arbre.
Si tu casses un mur, tu ne pourras pas créer d'arbres!

[sourivore]

Le contournement des portes quant à lui n'est pas un souci car qui dit contourner dit faire plus de pas qu'en utilisant une clé.
De plus le chemin de contournement n'est pas toujours évident.
Dans les portes et les clés ce qui m'intéresse ce n'est pas d'obliger de passer par une porte mais de laisser le choix entre aller ou pas dans une porte (Des portes mèneront à des impasses et oui!)