Discussion :

[F0ul]

Bonjour
Je suis en train de coder un petit jeu : l'ancienne version du démineur (rlogic pour les connaisseurs).
Pour ceux qui ne connaissent pas, le but est en fait de se déplacer d'un coin d'une matrice et d'aller dans le coin opposé en évitant les mines sur le chemin.

Il ne me manque qu'une chose, je ne sais pas comment gérer un chemin aléatoire qui soit sans mines entre le départ et l'arrivée :

Le nombre de mine est réglable (au maximum égal à (largeur-1)*(longueur-1))

J'ai bien essayé de faire des déplacements aléatoires en interdisant les retours sur les mêmes cases, celà marche lorsqu'il y a un faible nombre de mines mais dès qu'il y en a un peu trop celà bloque.

Quelqu'un aurait-il une idée ?

Merci d'avance à ceux qui chercheront (ou qui ont la réponse déjà ^^)

[ram-0000]

Peut être que l'idée est de créer d'abord un chemin (pseudo) aléatoire sur un terrain vierge de mines et ensuite de poser les mines en s'interdisant de les poser sur le chemin aléatoire

[Emmanuel Delahaye]

Peut être que l'idée est de créer d'abord un chemin (pseudo) aléatoire sur un terrain vierge de mines et ensuite de poser les mines en s'interdisant de les poser sur le chemin aléatoire

+1 !

[F0ul]

Le problème étant justemment de faire ce chemin aléatoire (ou pseudo aléatoire).
Puisque, par exemple, si on part du haut à gauche et qu'on doit aller en bas à droite. Doit on limiter les déplacements vers la droite et le bas.
En fait il faudrait pouvoir trouver un algorithme qui calcule les chemins possibles en fonction du nombre de cases disponibles et en choisir un au hasard.

[ram-0000]

Si ton chemin part du haut à gauche et va vers le bas à droite, cela ne peut donc pas être un chemin aléatoire. Tout chemin aléatoire a peu de chance d'arriver là où tu veux.

Cela pourrait être en chemin direct (chemin le plus court entre 2 points) avec des variations aléatoires. Dans ce cas, on viole un peu le hasard en favorisant les directions "bas" et "droite". Mais là encore, je ne suis pas sûr d'arriver en bas à droite et en plus, le chemin obtenu risque de ressembler un peu trop à une diagonale, c'est trop facile.

En fait, je ne suis pas sûr que tracer un chemin soit la bonne idée.

Peut être que creuser un chemin est meilleur. Au départ, ta grille est le chemin complet et petit à petit, tu enlèves des cases à ce chemin. A chaque fois que tu enlèves une case, tu testes si le chemin n'est pas rompu.

Je suis bien conscient que ce n'est pas encore la solution mais je te donne mes idées au fur et à mesure

[progfou]

Pourquoi ne pas t'inspirer des méthodes de génération de labyrinthe ?
Ce site:
http://ilay.org/yann/articles/maze/

Présente le concept de manière détaillée, et tu remarqueras qu'à la fin, un exemple est donné, où il y a un chemin (unique) qui part d'en haut à gauche et finit en bas à droite.