Les membres ayant 30 points peuvent parler sur les canaux annonces, projets et hs du chat.
La shoutbox n'est pas chargée par défaut pour des raisons de performances. Cliquez pour charger.

Forum Casio - Autres questions


Index du Forum » Autres questions » Programme: labyrinthe aléatoire
Ringodu74 Hors ligne Membre Points: 39 Défis: 0 Message

Programme: labyrinthe aléatoire

Posté le 15/12/2012 12:27

Hello world,

J’aide besoin de votre aide pour mon programme en BASIC qui consiste à pouvoir créer un labyrinthe aléatoire et à y jouer. J
J’ai utilisé la méthode de fusion aléatoire des cellules présentée ici :
Wikipédia: modélisation mathématique d'un labyrinthe

Si vous voulez comprendre de quoi je parle ensuite, veuillez regarder le lien svp

Je vais rapidement vous présenter mon programme :
1) En premier, je dessine sur l’écran graphique un quadrillage de 15*31 cellules (de 4pixels chacune)
2) Je crée une matrice de 15*31 cases qui correspondent aux cellules sur l’écran graphique.
3) J’incrémente (attribue un numéro) toutes les cases de la matrice. (1,2,3 etc.)
4) Je définis 4 nombres aléatoires :
Tout d’abord pour sélectionner une cellule de façon aléatoire (je vais l’appeler C1), on crée deux nombres aléatoires qui correspondent aux coordonnées d’une cellule (X compris entre 1 et 31 et Y entre 1 et 15)
Ensuite une direction (donc compris entre 1 et 4 : D,G,H,B) qui sert à choisir avec quelle cellule adjacente (appelons la C2) on fusion la cellule (C1) de base.
5) Donc quand la direction=1, alors je supprime le mur entre la C1 et C2 sur l’écran graphique, et, au niveau de la matrice, je donne à C2 la même incrémentation que C1.
6) Si C2 à déjà la même incrémentation que C1, c’est qu’il y a un lien entre elles donc on ne supprime pas le mur.
7) Ensuite, il y a la partie du jeu, mais cela ne pose pas de problème pour l’instant.

Mon problème se situe lors de la partie 5.
En effet, la cellule C2 prend la même incrémentation que C1, mais seulement C2 alors que si on imagine un groupe de cellules autour de C2 ayant la même incrémentation, il faut que tout le groupe prenne l’incrémentation de C1, pour qu’il n’y ai pas « d’îles » dans le labyrinthe, ce qui le rendrai imparfait. (Si vous n’avez pas compris ce que j’explique, retournez voir le lien) D’ailleurs, au bout d’un petit moment, je n’obtiens plus que des points dans mon programme (essayez le vous verrez)..

J’ai essayé plusieurs façons de régler ce problème, certains ralentissent énormément le programme (quand on doit chercher deux nombres égaux dans une matrice de 15*31 par exemple) mais toujours aucun résultat…


Je vous laisse mon code ici, il est libre de droit, prenez le, modifiez le… Mais aidez- moi SVP pour résoudre ce problème.

Code complet:
Ouvrir le code:
Fermer le code:


Cls
ClrGraph
Axesoff
0->A˜Z
S-Windman
ViewWindow 1,127,0,1,63,0
1->T

On trace le quadrillage

While T≠129
Vertical T
Horizontal T
T+4->T
WhileEnd
1->T
1->X

While T≠127
PlotOff X,63
X+1->X
T+1->T
WhileEnd
1->T
1->X

While T≠127
PlotOff X,62
X+1->X
T+1->T
WhileEnd
1->T

While T≠63
PlotOff 127,T
T+1->T
WhileEnd
1->T

While T≠63
PlotOff 126,T
T+1->T
WhileEnd
0->A˜Z
61->A
3->B
PxlOn A,B

On crée la matrice

{15,31}->Dim Mat X
1->T
1->A

On fait l’incrémentation de chaque case

While T<32
T->Mat X[1,A]
T+1->T
A+1->A
WhileEnd
1->A

While T<63
T->Mat X[2,A]
T+1->T
A+1->A
WhileEnd
1->A

While T<94
T->Mat X[3,A]
T+1->T
A+1->A
WhileEnd
1->A

While T<125
T->Mat X[4,A]
T+1->T
A+1->A
WhileEnd
1->A

While T<156
T->Mat X[5,A]
T+1->T
A+1->A
WhileEnd
1->A

While T<187
T->Mat X[6,A]
T+1->T
A+1->A
WhileEnd
1->A

While T<218
T->Mat X[7,A]
T+1->T
A+1->A
WhileEnd
1->A

While T<249
T->Mat X[8,A]
T+1->T
A+1->A
WhileEnd
1->A

While T<280
T->Mat X[9,A]
T+1->T
A+1->A
WhileEnd
1->A

While T<311
T->Mat X[10,A]
T+1->T
A+1->A
WhileEnd
1->A

While T<342
T->Mat X[11,A]
T+1->T
A+1->A
WhileEnd
1->A

While T<373
T->Mat X[12,A]
T+1->T
A+1->A
WhileEnd
1->A

While T<404
T->Mat X[13,A]
T+1->T
A+1->A
WhileEnd
1->A

While T<435
T->Mat X[14,A]
T+1->T
A+1->A
WhileEnd
1->A

While T<466
T->Mat X[15,A]
T+1->T
A+1->A
WhileEnd
1->A
1->T

Lbl X
If T=300
Then Goto Y
IfEnd

On choisi les nombres aléatoires

Int (Ran# 31)+1->R
Int (Ran# 15)+1->S
Int (Ran# 4)+1->M

If M=1  Si la direction est la droite
Then If R=31
Then Goto X
IfEnd
If Mat X[S,R]= Mat X[S,R+1]   Si C1 a le même num que C2, on arrête
Then Goto X
IfEnd
Mat X[S,R]->Mat X[S,R+1] on attribue à C2 le numéro de C1
PxlOff S*4,R*4+1    On supprime le mur sur l’écran
PxlOff S*4+1,R*4+1
PxlOff S*4+2,R*4+1
IfEnd

If M=2
Then If S=1
Then Goto X
IfEnd
If Mat X[S,R]= Mat X[S-1,R]
Then Goto X
IfEnd
Mat X[S,R]->Mat X[S-1,R]
PxlOff S*4-1,R*4
PxlOff S*4-1,R*4-1
PxlOff S*4-1,R*4-2
IfEnd

If M=3
Then If R=1
Then Goto X
IfEnd
If Mat X[S,R]= Mat X[S,R-1]
Then Goto X
IfEnd
Mat X[S,R]->Mat X[S,R-1]
PxlOff S*4,R*4-3
PxlOff S*4+1,R*4-3
PxlOff S*4+2,R*4-3
IfEnd

If M=4
Then If S=15
Then Goto X
IfEnd
If Mat X[S,R]= Mat X[S+1,R]
Then Goto X
IfEnd
Mat X[S,R]->Mat X[S+1,R]
PxlOff S*4+3,R*4-2
PxlOff S*4+3,R*4-1
PxlOff S*4+3,R*4
IfEnd

Lbl Y
PARTIE JEU






1, 2 Suivante
Ray Hors ligne Membre Points: 1338 Défis: 18 Message

Citer : Posté le 15/12/2012 12:59 | #


Hey ! si ton générateur de labyrinthe fonctionne, tu pourrais essayer d'en créer un pour mon Labyrinthe 3D ?
Je n'hésiterai pas à citer ton pseudo quand je posterai le programme !
PS : Le programme utilise des pictures, je vais voir pour améliorer un point qui peut être gênant : la matrice qui fait 30x30 dont 4 lignes et 4 colones ne servent à rien.
Projets que je soutiens
Masquer
Totoyo Hors ligne Membre d'honneur Points: 16093 Défis: 102 Message
Ziqumu Hors ligne Membre d'honneur Points: 3055 Défis: 9 Message

Citer : Posté le 15/12/2012 13:41 | #


&#8800; (différent de)

Ils sont remplacés automatiquement..
Siapran Hors ligne Membre Points: 3248 Défis: 17 Message

Citer : Posté le 15/12/2012 15:58 | #


ton code fait combien d'octets
ta méthode me paraît bien longue pour pas grand chose
voici mon code en moins de 600 octets
En gros j'utilise une méthode par backtracking avec une pile bricolée à partir d'une liste et d'un pointeur.

Quand je me fais chier je laisse tourner ça en boucle en cours de math SP.

Code déroulable
Code déroulable

ViewWindow 1,127,0,1,63,0     //Initialisation de l'écran
BG-None

Do    //boucle optionnelle pour faire générer en boucle

For 1->A To 63    //Remplissage de l'écran
Horizontal 64-A
Next
RanInt#(1,63)*2->A   //Graine aléatoire
RanInt#(1,21)*2->B
ClrList 1                   //Initialisation Pile
0->L

Do                           //Boucle principale
ClrList 2                   //Liste de directions
0->E
B->D
A-2->C                     //Gauche
If C>0
Then If PxlTest(D,C)
Then E+1->E
1->List 2[E]
IfEnd
IfEnd
A+2->C                     //Droite
If 127>C
Then If PxlTest(D,C)
Then E+1->E
2->List 2[E]
IfEnd
IfEnd
A->C
B-2->D                       //Haut
If D>0
Then If PxlTest(D,C)
Then E+1->E
3->List 2[E]
IfEnd
IfEnd
B+2->D                       //Bas
If 63>D
Then If PxlTest(D,C)
Then E+1->E
4->List 2[E]
IfEnd
IfEnd

If E                             //Si on a encore une direction sans couloir
Then 1->F
If E>1                         //Si on en a plusieur
Then RanInt#(1,E)->F   //On choisis aléatoirement dans la liste de directions
L+1->L                        //On met les coordonnées sur le haut de la pile
100*A+B->List 1[L]       //(notez l'optimisation faite ici)
IfEnd
List 2[F]->F                 //Direction aléatoire choisie
A->C
B->D
F=1=>A-2->C
F=2=>A+2->C
F=3=>B-2->B
F=4=>B+2->B
If (F=1)+(F=2)        //Dessin du couloir
Then For A->I To C Step (C-A)/2
PxlOff D,I
Next
Else For B->J To C Step (D-B)/2
PxlOff J,C
Next
IfEnd
C->A                 //nouvelles coordonnées
D->B

Else List 1[L]->K  //Si on ne peut plus créer de couloir sans créer un deuxième chemin, alors on reviens jusqu'à la dernière position où on avait le choix
Int (K/100)->A
K-A*100->B
L-1->L
IfEnd
LpWhile L  // On fait ça tant qu'il y a des valeurs dans la pile

//Fin de la génération

ClrList 1   //Vidage de la Pile
ClrList 2

StoPict 1 //Enregistrement dans une Pict


LpWhile 1 //Recommencer la génération (Optionnel)



Ringodu74 Hors ligne Membre Points: 39 Défis: 0 Message

Citer : Posté le 15/12/2012 19:04 | #


Salut tout le monde;
merci pour vos réponses
@ray: Bien sûr je pourrais essayer (les cours de maths en 1ere c'est chiant) mais alors là comment gérer le 3D et tout j'ai bien peur que cela dépasse amplement mon niveau de débutant.

@Siapran: je ne comprends pas trop ton programme: tu utilises une autre méthode de génération aléatoire non?
en effet mon code est long, mais la génération est rapide, c'est juste que la partie pour la matrice est important dans le code, mais ca prend pas plus de 5secondes.
par contre pour le quadrillage ca prend trop de temps faut que j'utilise plutot le drawstat.

Néanmoins, quelqu'un pourrait il m'aider dans mon code svp?
Ray Hors ligne Membre Points: 1338 Défis: 18 Message

Citer : Posté le 15/12/2012 19:25 | #


@Ringodu74 : C'est simple, tout ce je te demande, c'est de créer un programme qui va créer un labyrinthe dans une matrice, la "3D" sera gérée par mon programme.
Projets que je soutiens
Masquer
Ringodu74 Hors ligne Membre Points: 39 Défis: 0 Message

Citer : Posté le 15/12/2012 20:30 | #


hmmm ok sic'est ue matrice ca je peux voir
Mais tu veux quoi d'aléatoire dans ta matrice alors?? juste des nombres de 1 à 30²??
explique moi un peu stp
Siapran Hors ligne Membre Points: 3248 Défis: 17 Message

Citer : Posté le 15/12/2012 20:44 | #


@Ringodu: C'est une génération aléatoire à partir d'une fonction récursive bricolée
l'avantage est que le code est bien plus léger
là ce code dessine directement le labyrinthe sur l'écran (avec des couloirs de 1*1 pixel, mais sur la totalité de l'écran)
pour une génération sur une matrice de 15*31, il te suffit d'adapter les bornes et de remplacer les fonctions graphiques par des affectations et tests sur la matrice

En gros pour expliquer comment l'algorithme procède:
On remplit la matrice de murs
On met une graine aléatoire (un point sur la matrice)
On cherche les directions où il n'y a pas de couloirs
On choisis aléatoirement une direction disponible, puis on créé un couloir dans cette direction
Si on est déjà entouré de couloirs, alors on reviens au dernier point où on avait encore le choix
On répète l'algorithme jusqu'à ce que toute la matrice soit pleine de couloirs

Ajouté le 15/12/2012 à 20:51 :
alors j\'ai regardé l\'article de wikipedia, et en fait mon algorithme correspond à l\'exploration exhaustive

l\'avantage c\'est que du coup il est bien plus rapide (et il prends moins de place en RAM comme en ROM)
Ringodu74 Hors ligne Membre Points: 39 Défis: 0 Message

Citer : Posté le 15/12/2012 21:03 | #


Ok c'est bien ca oui
Bien sûr, ton code est très simple.
Mais je suis parti sur ma base, après j'essaierais une autre méthode comme la tienne (sans la recopier bien sûr).
J'ai volontairement choisi la méthode qu'ils décrivaient comme "un peu plus dure" mais seulement pour progresser (ce qui ne veut pas dire que la tienne est plus simple, bien que moins longue).

Si tu peut néanmoins résoudre mon problème, je te serais reconnaissant

Ajouté le 15/12/2012 à 21:06 :
\"pour une génération sur une matrice de 15*31, il te suffit d\'adapter les bornes et de remplacer les fonctions graphiques par des affectations et tests sur la matrice\"
-> cela n\'est pas un problème lit encore une fois mon premier post
Siapran Hors ligne Membre Points: 3248 Défis: 17 Message

Citer : Posté le 15/12/2012 22:47 | #


et bah pour l'étape 5 il suffit de prendre l'incrémentation de C1 et de C2, puis tu explore toute ta matrice et tu remplace par C1 quand tu vois C2, je ne vois pas où est le problème

après tu as tout à fait le droit de recopier mon programme mot pour mot (ça ne me gènerait pas du tout, même essaye de l'optimiser tant qu'à faire)

en tout cas, j'oubliais, mais bienvenue à bord!
Ringodu74 Hors ligne Membre Points: 39 Défis: 0 Message

Citer : Posté le 15/12/2012 22:55 | #


@Siapan: Merci
J'ai déja essayé d'explorer toute la matrice pour retrouver les cellules avec la même incrémentation mais ca prend trop de temps...bcp trop de temps... on a une matrice de 465 cases donc pour chaque fusion ca fait des heures.
En plus j'avais fait une erreur. J'ai laissé tourner le programme toute la nuit avant d'arriver à un résultat.. pas top

Ajouté le 16/12/2012 à 08:30 :
Quelqu\'un aurait t il une autre astuce?
Siapran Hors ligne Membre Points: 3248 Défis: 17 Message

Citer : Posté le 16/12/2012 09:04 | #


alors dans ce cas tu peux essayer d'explorer la matrice à partir de C2 avec un algorithme de pot de peinture, ce qui sera légèrement moins coûteux que d'explorer toute la matrice

sinon je ne vois vraiment pas

Remplissage par diffusion
Ringodu74 Hors ligne Membre Points: 39 Défis: 0 Message

Citer : Posté le 16/12/2012 10:01 | #


J'essaie... je te tiens au courant si ca marche.
Ray Hors ligne Membre Points: 1338 Défis: 18 Message

Citer : Posté le 16/12/2012 11:44 | #


@Ringodu74 : c'est simple, le but du programme est de générer des labyrinthes ? bah en fait la matrice de la taille que tu veut (pas trop petit quand même) tu met un 1 dans une case pour placer un mur et un 0 pour mettre une zone vide.
Pour la sortie tu met dans la case un..... en fait je viens de me rendre compte que pour la sortie c'est une histoire de variables..... faudra que je regarde d'un peu plus près comment je générais les niveaux parce que là c'est un peu n'importe quoi...
Projets que je soutiens
Masquer
Siapran Hors ligne Membre Points: 3248 Défis: 17 Message

Citer : Posté le 16/12/2012 12:23 | #


mais vraiment en basic t'auras plutot intérêt à utiliser ma méthode
ça prend aux alentours de 5 minutes pour générer un labyrinthe de 127*63

Ajouté le 16/12/2012 à 12:33 :
d\'ailleurs je t\'invite à regarder les vidéos sur ce lien
Maze Generation Algorithms
Ringodu74 Hors ligne Membre Points: 39 Défis: 0 Message

Citer : Posté le 16/12/2012 14:28 | #


@Ray: ok tu m'explique ce que tu veux et j'essaierais de te pondre un bon algorithme au moins ca m'occupe pendant les maths

@Siapran: Je finis cet algorithme comme je le voulais depuis le début et si j'y arrive ou si je suis définitivement bloqué je te promets d'essayer celui que tu me conseille (bien sûr, à ma sauce)
Eiyeron Hors ligne Ancien modérateur Points: 5525 Défis: 57 Message

Citer : Posté le 16/12/2012 17:25 | #


Cool Siapran qui me remplace sur un truc que j'aime bien, ça montre qu'il a progressé le bougre!

Le Backtracker es tune solution quasi universelle : non seulement dans les labyrinthes elle est utilisée, mais aussi dans le pathfinding (recherche de chemin), ou même dans les algos de remplissage!
Siapran Hors ligne Membre Points: 3248 Défis: 17 Message

Citer : Posté le 16/12/2012 19:39 | #


j'avais prévu de faire un tuto sur le principe et l'utilisation d'une pile dans un programme

j'ai pas encore assez d'applications pour qu'il soit consistant (j'ai le pot de peinture, le démineur, et le laby pour l'instant)
Ringodu74 Hors ligne Membre Points: 39 Défis: 0 Message

Citer : Posté le 16/12/2012 21:08 | #


Oai, vas y siapran, a vrai dire je ne comprends pas trop ce qu'est un "pile" donc si tu fais un tuto c super

Ps: wow je galère trop avec le prog, mais au moins ca me fait progresser
Dark storm Hors ligne Labélisateur Points: 11634 Défis: 176 Message

Citer : Posté le 16/12/2012 23:04 | #


On commence avec le plus ou moins et on finit par faire de la simulation de tactile en C ou un début de moteur 3D
C'est le challenge qui nous motiv' tous ! Je ne peux que t'encourage à continuer comme ça !
Au fait, bienvenue à toi


Finir est souvent bien plus difficile que commencer. — Jack Beauregard
1, 2 Suivante

LienAjouter une imageAjouter une vidéoAjouter un lien vers un profilAjouter du codeCiterAjouter un spoiler(texte affichable/masquable par un clic)Ajouter une barre de progressionItaliqueGrasSoulignéAfficher du texte barréCentréJustifiéPlus petitPlus grandPlus de smileys !
Cliquez pour épingler Cliquez pour détacher Cliquez pour fermer
Alignement de l'image: Redimensionnement de l'image (en pixel):
Afficher la liste des membres
:bow: :cool: :good: :love: ^^
:omg: :fusil: :aie: :argh: :mdr:
:boulet2: :thx: :champ: :whistle: :bounce:
valider
 :)  ;)  :D  :p
 :lol:  8)  :(  :@
 0_0  :oops:  :grr:  :E
 :O  :sry:  :mmm:  :waza:
 :'(  :here:  ^^  >:)

Σ π θ ± α β γ δ Δ σ λ
Veuillez donner la réponse en chiffre
Vous devez activer le Javascript dans votre navigateur pour pouvoir valider ce formulaire.

Si vous n'avez pas volontairement désactivé cette fonctionnalité de votre navigateur, il s'agit probablement d'un bug : contactez l'équipe de Planète Casio.

Planète Casio v4.3 © créé par Neuronix et Muelsaco 2004 - 2024 | Il y a 47 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd