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 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
Citer : Posté le 17/12/2012 12:13 | #
Merci
Citer : Posté le 17/12/2012 21:22 | #
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
Que de souvenirs... C'est bien vrai ce que tu nous dis la Dark storm!
-en C:
-Un pong.
-Un projet en pause. Je compte le reprendre de temps en temps: Summer Cursed
-mon tuto sur les Str
Mes calto: G25+, G75
Mon minecraft en dévelopement
-Portal2D de JavierXD
-CalCraft de Wime
-GeekBros du groupe GeekBrothers (Eiyeron,Siapran,KevKevVTT,Adbook,LIMachi)
Citer : Posté le 17/12/2012 21:55 | #
moi j'avais commencé direct au mastermind mais bon
mais effectivement on est tous passé par ce genre de trucs.
après j'ai toujours tenu à découvrir tous les secrets de la programmation tout seul (sauf au niveau syntaxe etc)
un des premiers trucs que j'ai voulu faire quand j'ai appris qu'on pouvais programmer sur les calculatrices, c'est essayer de faire un démineur
j'ai fini par le terminer il y a six mois, après avoir découvert le concept du remplissage par diffusion
puis après j'ai fait un snake, un tetris, et deux trois autres bricoles
le labyrinthe je l'ai créé sans aucune aide (même si Eiyeron m'en avait beaucoup parlé)
en tous cas, bienvenue dans le monde de la programmation, et bon courage pour la suite
Citer : Posté le 17/12/2012 22:04 | #
remplissage par diffusion c'est la recursivité?
envie de plonger dans la mer pour ramasser des tresors? => ballon sea
envie de sauver l'univers dans un jeu avec une longue durée de vie? => saviors of the future
un add-in addictif avec plein de secret et de trophées => evasion survival
un shmup bien dur et sadique => saviors 2
merci a tout le monde pour son soutien
zelda prizm de smashmaster (en esperant qu'il puisse le finir)
les tests de marmotti
un RPG de dark storm
(dont je connais le nom, mais pas vous
)Arcuz !Citer : Posté le 17/12/2012 22:32 | #
c'est une application de la récursivité (parmis d'autres)
c'est ce qui est à l'origine de l'outil pot de peinture dans un éditeur d'images entre autres
Citer : Posté le 18/12/2012 12:09 | #
salut,
bon j'abandonne mon essai sur le laby, je vais maintenant me concentrer sur l'autre méthode (utilisée par Siapran) car la mienne est trop compliquée à gérer et je n'ai pas résolu mon problème, ca pose trop de problèmes.
Je commence tout de suite une autre méthode et je vous tiens informé de l'avancement et si j'ai des problèmes
PS: je poste un ptit mot dans les présentations
Ajouté le 18/12/2012 à 16:08 :
Re,
J\'ai commencé la deuxième méthode mais j\'ai un problème dont je ne vois vraiment pas là cause (ca me met un \"erreur argument\" alors je comprend pas...)
Voila mon nouveau code (pas fini):
1->T
While T<=32
F-line 1+A,1,1+A,60
F-Line 1,1+A,125,1+A petit MAJ: plus rapide ;)
A+4->A
T+1->T
WhileEnd
0->A-Z
{15,31}->Dim Mat A
Seq(0,W,1,465,1)->List 1
Seq(0,V,1,465,1)->List 2
Int (15Ran# 1)+1->X
Int (31Ran# 1)+1->Y
1->T
1->R
X->List 1[T]
Y->List 2[T]
If X>=2
Then If pxlTest(X*4-1,Y*4-1)=1 And Mat A[X-1,Y]=0
Then R->H
R+1->R
IfEnd
IfEnd
If Y<=30
Then If pxlTest(X*4+1,Y*4+1)=1 And Mat A[X,Y+1]=0
Then R->D
R+1->R
IfEnd
IfEnd
If X<=14
Then If pxlTest(X*4+3,Y*4-1)=1 And Mat A[X+1,Y]=0
Then R->B
R+1->R
IfEnd
IfEnd
If Y>=2
Then If pxlTest(X*4+1,Y*4-3)=1 And Mat A[X,Y-1]=0
Then R->G
R+1->R
IfEnd
IfEnd
...autreschoses...
Int ((R-1)*Ran# 1)+1->N
If H=N
Then 1->Z
IfEnd
If D=N
Then 2->Z
IfEnd
If B=N
Then 3->Z
IfEnd
If G=N
Then 4->Z
IfEnd
If Z=1
Then PxlOff ((X*4)-1),(Y*4) Cette ligne passe
PxlOff ((X*4)-1),((Y*4)-1) Celle la bug \"erreur argument
...etc..
X-1->X
IfEnd
La même chose pour Z=1,2,3,4...
Ou est l\'erreur??? si besoin je peux rajouter le code enlevé, mais rien qui puisse faire bugger ca...
Help pls :!:
Citer : Posté le 18/12/2012 22:58 | #
manifestement, pour une raison assez obscure, Y se retrouve compris entre 0.25 et 0.5
il faudrait voir quand est-ce que X est modifié, et si les bornes que tu as mises avant les affectations correspondent
vérifie les valeurs de tes variables après le bug (dans le menu run, tu tapes X et si besoin est d'autres variables que tu utilises, puis tu essaye d'interpréter les valeurs)
Citer : Posté le 19/12/2012 16:08 | #
salut,
J'ai contourné le problème sans l'avoir résolu en faisant X->J et F->Y mais je n'ai toujours pas compris le pb...
J'ai continué le code qui ne marche toujours pas, je vous explique ca tout de suite avec le code et les explications..
Ajouté le 19/12/2012 à 17:15 :
Voila le code:
1->T
While T<=32
F-line 1+A,1,1+A,60
F-Line 1,1+A,125,1+A petit MAJ: plus rapide
A+4->A
T+1->T
WhileEnd
0->A-Z
{15,31}->Dim Mat A
Seq(0,W,1,465,1)->List 1
Seq(0,V,1,465,1)->List 2
Int (15Ran# 1)+1->X
Int (31Ran# 1)+1->Y
0->T
Lbl 1 (bon ben oui je l\'utilise, on verra apres si je peux l\'enlever)
Text 1,1,T
0->F
0->J
0->N
0->Z
0->B
0->H
0->G
0->D
T+1->T
If X>=2 (pour le haut) (Var H représente ici Haut)
Then If Mat A[X-1,Y]=0 (si la case du haut est libre)
Then R->H (R correspond au nombre de case dans lequel on peut aller; cela incrémente donc H)
R+1->R
IfEnd
IfEnd
If Y<=2 (pour la droite) (Var D représente ici Droite)
Then If Mat A[X,Y+1]=0 (si la case de droite est libre)
Then R->D (R correspond au nombre de case dans lequel on peut aller; cela incrémente donc D)
R+1->R
IfEnd
IfEnd
If X<=14 (pour le bas) (Var B représente ici Bas)
Then If Mat A[X+1,Y]=0 (si la case du bas est libre)
Then R->B (R correspond au nombre de case dans lequel on peut aller; cela incrémente donc B)
R+1->R
IfEnd
IfEnd
If Y>=2 (pour la gauche) (Var G représente ici Gauche)
Then If Mat A[X,Y-1]=0 (si la case du haut est libre)
Then R->G (R correspond au nombre de case dans lequel on peut aller; cela incrémente donc G)
R+1->R
IfEnd
IfEnd
/*jusque la pas de nouveauté, juste des petites améliorations et plus de pxltest */
If X>=2 And X<=14 And Y>=2 And Y<=30 (pour les case qui ne sont pas sur les bords sinon on peut pas faire X-1...)
Then If Mat A[X-1,Y]=0 Or Mat A[X,Y+1]=0 Or Mat [X+1,Y]=0 Or Mat A[X,Y-1]=0 (si une case adjacente est libre)
Then (je sais c\'est pas propre mais plus simple...)
Else 1->Mat A[X,Y]
Lbl O (bon alors la le code est cauchemardesque, je vais le retravailler... :sry: )
If X<=14 And X>=2 And Y<=30 And Y>=2 (on vérifie qu\'on part pas sur les bords)
Then While Mat A[X,Y-1]=1 And Mat A[X,Y+1]=1 And Mat A[X+1,Y]=1 And Mat A[X-1,Y]=1 (on va en arrière tant que les cases adjacentes ont été visitées)
List 1[T-1]->X
List 2[T-1]->Y
T-1->T
Goto O
WhileEnd
IfEnd
Goto 1
IfEnd
IfEnd
/*bon jusque la c\'est pt le code le plus sale jamais fait mais ca marche.. la suite ne marche pas*/
If X=1 And Y=1 (dans le coin en haut à gauche
The If Mat A [X+1,Y]=0 Or Mat A[X,Y+1]=0
Then
Else 1->Mat A[X,Y]
List 1[T-1]->X
List 2[T-1]->Y
T-1->T
IfEnd
Goto 1
IfEnd
If X=1 And Y=31 (dans le coin en haut à droite
The If Mat A [X+1,Y]=0 Or Mat A[X,Y-1]=0
Then
Else 1->Mat A[X,Y]
List 1[T-1]->X
List 2[T-1]->Y
T-1->T
IfEnd
Goto 1
IfEnd
If X=31 And Y=1 (dans le coin en bas à gauche
The If Mat A [X-1,Y]=0 Or Mat A[X,Y+1]=0
Then
Else 1->Mat A[X,Y]
List 1[T-1]->X
List 2[T-1]->Y
T-1->T
IfEnd
Goto 1
IfEnd
If X=31 And Y=31 (dans le coin en haut à Doite
The If Mat A [X-1,Y]=0 Or Mat A[X,Y-1]=0
Then
Else 1->Mat A[X,Y]
List 1[T-1]->X
List 2[T-1]->Y
T-1->T
IfEnd
Goto 1
IfEnd
If X=1 And Y>=2 And Y<=30
Then If Mat A[X,Y-1]=0 Or Mat A[X+1,Y]=0 Or Mat A[X,Y+1]=0
Then
Else 1->Mat A[X,Y]
While Mat A[X,Y-1]=1 And Mat A[X+1,Y]=1 And Mat A[X,Y+1]=1
List 1[T-1]->X
List 2[T-1]->Y
T-1>T
WhileEnd
Goto 1
IfEnd
IfEnd
If X=31 And Y>=2 And Y<=30
Then If Mat A[X,Y-1]=0 Or Mat A[X-1,Y]=0 Or Mat A[X,Y+1]=0
Then
Else 1->Mat A[X,Y]
While Mat A[X,Y-1]=1 And Mat A[X-1,Y]=1 And Mat A[X,Y+1]=1
List 1[T-1]->X
List 2[T-1]->Y
T-1>T
WhileEnd
Goto 1
IfEnd
IfEnd
If Y=1 And X>=2 And X<=30
Then If Mat A[X,Y+1]=0 Or Mat A[X+1,Y]=0 Or Mat A[X-1,Y]=0
Then
Else 1->Mat A[X,Y]
While Mat A[X-1,Y]=1 And Mat A[X+1,Y]=1 And Mat A[X,Y+1]=1
List 1[T-1]->X
List 2[T-1]->Y
T-1>T
WhileEnd
Goto 1
IfEnd
IfEnd
If Y=31 And X>=2 And X<=30
Then If Mat A[X,Y-1]=0 Or Mat A[X+1,Y]=0 Or Mat A[X-1,Y]=0
Then
Else 1->Mat A[X,Y]
While Mat A[X-1,Y]=1 And Mat A[X+1,Y]=1 And Mat A[X,Y-1]=1
List 1[T-1]->X
List 2[T-1]->Y
T-1>T
WhileEnd
Goto 1
IfEnd
IfEnd
1->Mat A[X,Y]
Int ((R-1)*Ran# 1)+1->N
If H=N
Then 1->Z
IfEnd
If D=N
Then 2->Z
IfEnd
If B=N
Then 3->Z
IfEnd
If G=N
Then 4->Z
IfEnd
If Z=1
Then X->F
Y->J
PxlOff ((X*4)-1),(Y*4)
J->Y
F->X
PxlOff ((X*4)-1),((Y*4)-1)
...etc..
X-1->X
IfEnd
SVP est ce que quelqu\'un veut bien essayer de trouver les erreurs dans ce code... Sans trop changer la méthode qui reste compréhensible pour moi..
Alors j\'attends vos réponses
Arthur
Citer : Posté le 19/12/2012 18:36 | #
ah oui j'oubliais...
quand tu utilises l'écran graphique, évite À TOUT PRIX d'utiliser X et Y
explication: ces variables sont utilisées par les fonctions graphiques, et sont donc modifiées à chaque fois que tu dessines quelquechose (ou une merde du genre)
bref, essaye de modifier ton code et d'utiliser d'autres variables que X et Y
Citer : Posté le 20/12/2012 11:40 | #
ah!!!! merci siapran
J'ai enfin terminé le programme (enfin la partie génération, car il me reste un ptit détail à régler: la fin du laby.. mais je peux déjà y jouer, même si ça ne reconnait pas la fin.).
Ajouté le 20/12/2012 à 11:46 :
Ce qui est dommage avec la deuxième technique (je viens de le faire tester à un de mes amis) c\'est que le labyrinthe est trop facile car l\'arbre n\'est pas équilibré (le chemin est trop évidant)... alors que dans une fusion aléatoire plusieurs chemins apparaissent...
Ici le chemin central se devine très facilement et on jette juste un coup d\'oeil et on sait où aller...
Mais bon au moins j\'ai réussit
Merci encore à siapran pour son aide
Est ce que vous voulez le code final?
Avec la partie jeu?
Citer : Posté le 20/12/2012 19:14 | #
Tu peux le poster sur le site si tu veux
Avec tout les commentaires et explications qui vont avec.
Si tu poste une version jouable, tu pourra concourir pour le Jeu du Mois
Citer : Posté le 20/12/2012 21:30 | #
ravi de t'avoir aidé Ringo
c'est vrai que pour le coup j'avais fait cette génération de labyrinthe avec but quasi exclusivement esthétique, le labyrinthe a un gros facteur de "rivière" (les ramifications sont très petites)
fait ce que tu veux avec ton code (c'est le tiens à présent) et bonne chance pour la suite
Citer : Posté le 21/12/2012 12:38 | #
Oui je peux le poster sur le site mais bon faut que je sois chez moi et que je télécharge le logiciel.. Encore une ou deux modifs et ce sera bon
Pour le jeu du mois je suis pas sûr haha
Nan pt un jour je me lancerais dans un gros projet, pour l'instant j'ai: un puissance 4, un morpion (pas un 3*3, plus gros) le jeu des allumettes mais tout ca sans IA.. :/
Citer : Posté le 22/12/2012 00:36 | #
essaye de te pencher sur le concept de récursivité, et tente de faire un démineur (avec l'algo de diffusion pour ouvrir les cases vides
Citer : Posté le 22/12/2012 23:08 | #