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
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.
Citer : Posté le 15/12/2012 13:19 | #
Les ≠ sont censés correspondre à quel caractère ?
Vitesse des fonctions en Basic Casio | 7 days CPC | Casio Universal Wiki | Tutoriel Basic Casio
>>> Give me a click Brother
>>> Random Youtube Video
Citer : Posté le 15/12/2012 13:41 | #
≠ (différent de)
Ils sont remplacés automatiquement..
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.
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)
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?
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.
Citer : Posté le 15/12/2012 20:30 | #
hmmm
Mais tu veux quoi d'aléatoire dans ta matrice alors?? juste des nombres de 1 à 30²??
explique moi un peu stp
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)
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
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!
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?
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
Citer : Posté le 16/12/2012 10:01 | #
J'essaie...
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...
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
Citer : Posté le 16/12/2012 14:28 | #
@Ray: ok
@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)
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!
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)
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
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