Forum

Catégorie : Programmes
Forum : Les programmes des internautes
Vues : 3487
Réponses : 22
Type : discussion
Etat : réponses autorisées
Avertissement :
Il s'agit d'une page optimisée pour la navigation mobile. Voir la page originale.

Algorithme générateur de labyrinthe.

ld le 13/11/2010 à 09:50
Programme Labyalgo 555 Ko... par davin...

Salut à tous ! Je suis parvenus à trouver un algoritheme générant des
labyrinthes plus que corrects.
J'ai coupler se prgm à un autre afin de pouvoir se deplacer dans ceux-cis.
Le but étant de rejoindre le petit point placer de façon aléatoire dans ce
dédale de murs...

Naturellement, ils ne sont pas "parfaits" selon la définition mathématique,
néanmois j'y travail et plusieurs personnes de mon entourage se son prit au
jeu (un menbre de ma fammille programmeur chez IBM et mon prof de maths entre
autres...),j'espère bien qu'on trouvera !

En attendant je vous propose d'aller visiter la page:
https://fr.wikipedia.org/wiki/[...]d'un_labyrinthe
Et de pouvoir ainsi comprendre ce qu'es un labyrinthe dit "parfait"...
_______________________________________________

Code
:Menu("LABYRINTHE","NEW",1,"REPET",2)

:Lbl 1
:0-)Xmin:0-)Ymin:94-)Xmax:62-)Ymax
:EffDessin:AxesNaff

:For(A,3,62,4):Ligne(0,A,94,A):End
:For(B,3,94,4):Ligne(B,0,B,62):End

:For(B,3,62,4):For(A,0,94,4)
:If entAléat(0,2)=0 ou entAléat(0,2)=0:Then
:Pxl-Off(B,A):Pxl-Off(B,A+1):Pxl-Off(B,A+2)
:End:End:End

:For(A,3,94,4):For(B,0,62,4)
:If entAléat(o,2)=0 ou entAléat(0,2)=0:Then
:Pxl-Off(B,A):Pxl-Off(B+1,A):Pxl-Off(B+2,A)
:End:End:End

:Lbl 2
:1-)A:1-)B:Pxl-On(A,B)
:While 1
:0-)X:0-)Y
:codeTouche-)K
:If K=45:Stop
:If k=24 ou K=25 ou K=26 ou K=34:Then
:Pxl-Off(A,B)
:If K=24:-4-)Y
:If K=26:4-)Y
:If K=25:-4-)X
:If K=34:4-)X
:If Pxl-Test(A+X/2,B+Y/2)=1:Then
:A-X-)A:B-Y-)B:End
:A+X-)A:B+Y-)B:Pxl-On(A,B)
:End:End

_______________________________________________
ld le 15/11/2010 à 10:22
La version 2 !

Code
:EffEcr:Disp "Pause (- -)","Stop Annul"
:Menu("LABYRINTHE","NEW",1,"REPET",2)

:Lbl 1
:0-)Xmin:0-)Ymin:94-)Xmax:62-)Ymax
:EffDessin:AxesNaff

:For(B,0,62,4):For(A,0,90,4)
:If entAléat(0,2)=0:Then *
:Pxl-On(B,A):Pxl-On(B,A+1):Pxl-On(B,A+2):Pxl-On(B,A+3):Pxl-On(B,A+4)
:End:End:End

:For(A,0,94,4):For(B,0,58,4)
:If entAléat(o,2)=0:Then *
:Pxl-Off(B,A):Pxl-On(B+1,A):Pxl-On(B+2,A):Pxl-On(B+3,A):Pxl-On(B+4,A)
:End:End:End

:Lbl 2
:4entAléat(1,15)+2-)C
:4entAléat(1,22)+2-)D
:Pxl-On(C,D):30-)A:30-)B
:While 1
:0-)X:0-)Y
:codeTouche-)K
:If K=45:Stop
:If k=24 ou K=25 ou K=26 ou K=34:Then
:Pxl-Off(A,B):Pxl-Off(A-1,B):Pxl-Off(A+1,B):Pxl-Off(A,B-1):Pxl-Off(A,B+1)
:If K=24:-4-)Y
:If K=26:4-)Y
:If K=25:-4-)X
:If K=34:4-)X
:If Pxl-Test(A+X/2,B+Y/2)=1:Then
:A-X-)A:B-Y-)B:End
:A+X-)A:B+Y-)B
:Pxl-On(A,B):Pxl-On(A-1,B):Pxl-On(A+1,B):Pxl-On(A,B-1):Pxl-On(A,B+1)
:If A=C et B=D:Then:Disp "GAGNE !":Stop:End
:End:End

_______________________________________________

Lorsque, après avoir séléctioner NEW, le prgm à terminer de
générer le labyrinthe, vous devez appuier sur l'une des touches directionelles
pour commancer à jouer...
REPET sert à en rejouer un... (une fois l'avoir générer, et si toutes fois vous
n'ayez pas éxécuter la commande NEW ou EffDessin après celui-ci)...

* (If entAléat(0,2)=0 ou (0,1)) Plus les chances sont grandes que entAléat=0, plus le
labyrinthe sera densse en murs. Attention ! Plus de chance aussi qu'il soit faux (infaisable).
Je vous conseil donc de faire attention si vous décider de changer la denssité...
ld le 15/11/2010 à 10:27
Euh... Je me sens un peu seul là, c'est une impression ? ahh.gif
Sangohan38 le 15/11/2010 à 12:50
Non, tu n'est pas seul, c'est juste que c'est la période un peu creuse de l'inspiration des gens.
Perso, je boss sur des progs de cours donc pas trop le temps de tester tes programmes.

Sangohan38
Persalteas le 15/11/2010 à 20:49
moi, j'ai pas de projet en ce moment (à part apprendre l'assembleur, et j'ai la flemme),alors je teste ton programme.

je l'ai donc testé, il est très bien quoique un peu lent, mais il y a 2 choses qui pourraient être améliorées:

quand on recommence le labyrinthe, la croix de la partie précédente reste affichée, et c'est moche.

deuxio, je décris les effets de ton prog, parce que je ne suis pas sur que c'est ça qu'il est censé faire:

tout d'abord, il se trace des petits traits horizontaux sur mon écran.
ensuite, ces petits traits raccourcissent par un bout ou l'autre, sous l'action d'un pixeloff je pense.

et ensuite on joue.

pas de barres horizontales?

(je vais quand même revérifier ce que j'ai recopié histoire d'éviter le coup classique de "oups je me plains d'un truc où c'est ma faute...")
linkakro le 15/11/2010 à 23:56
Moi ça marche bien.
J'avais surestimé ce que devait donner ce programme.
Mais c'est déjà bien.
desoutte le 24/11/2010 à 10:01
bonjour il me met err argument au niveau du menu


que faire???
ld le 24/11/2010 à 10:31
Je me suis amuser à tester toutes les erreurs possible du menu
pour avoir le même message que le tien...
RÉSULTAT :C'est certainement un oublie de parenthèse dans le menu...

Merci d'avoir tester mon prgm ! cupsmiley.gif
desoutte le 25/11/2010 à 15:34
NN Il y a toujours une erreur et il m'indique le 2 du menu.
J'ai une ti 82 stats.fr
J'ai aussi quelques autres programmes (7).

Aisse ma calcul qui déconne ???
sulexa le 25/11/2010 à 17:19
tu n'aurais pas oublier le Lbl 2 plus loin dans le programme.
desoutte le 25/11/2010 à 18:29
NN Il n'y a aucune erreur

j'ai tout reverifier pendant 2 H

aucune erreur de recopiage


toujours erreur argument

Menu("LABYRINTHE","NEW",1,"REPET",2)
metallica le 25/11/2010 à 18:47
Je pense que tu as oublié une virgule.
linkakro le 25/11/2010 à 19:20
Ou problème de guillemets.
desoutte le 26/11/2010 à 08:35
C'est bon j'ai trouvé c'etait une erreur de guillemets.

Un grand merci a vous tous de m'avoir aider.

godgrace.gif
ld le 26/11/2010 à 09:09
C'est super ! Enfin quelqu’un pour l'essaie !
C'est pas qu'il est génial à casser des briques mais, je suis convaincu
que si on affine un peu l’algorithme il pourrait le devenir... cupsmiley.gif
Surtout qu'il n'est pas nécessaire ici d’être un gros crac en programmation,
quelques idées comme coupler plusieurs images pour donner de grands labyrinthes,
y mètre des petites bêtes qui vous courant après pour compliquer le dédale, ou
encore pouvoir déplacer un nombre limiter de murs dans un enchevêtrement de murs où des zones son inaccessibles pourrait bien le rendre très plaisant...
Envoi moi t'es idées et je mis collerait. happy.gif
Au fait tu as recopier la version 1 ou 2 ?
linkakro le 26/11/2010 à 21:21
Cela dépend de si tu démarres sur la base actuelle ou sur une base topologiquement "parfaite".
En combinant les types d'algorithmes expliqués sur wikipédia, on doit pouvoir modifier les proportions des murs, obtenir des îles, ...
ld le 27/11/2010 à 09:35
Moouuais...
C'est pas con du tout, je dirai même que c'est intelligent...
Par contre je vois mal comment tu compte mélanger les algorithmes ?
Je vais y réfléchir, cette page Wiki est bien faite et je suis sur quant
cherchant un peu on peut trouver d'autres algos sur le Net à traduire en basic...

PS: Au fait; Çà veut dire quoi "Linkakro" ??? crazy.gif
linkakro le 27/11/2010 à 17:20
Moi non plus je ne sais pas encore comment mélanger les algos minied.gif
ps: Je suis accro à Link de la série "The Legend Of Zelda" godgrace.gif
ld le 29/11/2010 à 11:04
A OK ! je viens de comprendre ! LOL bigmouth.gif
A oui ! La version 3 prochainement...
Et, complètement remasteuriser, s'il vous plait ! glasses.gif
ld le 06/12/2010 à 10:34
Et voici comme promis la vertion 3 du Labygénérateur ! glasses.gif

LES LABYRINTHES SONT "PARFAITS" SELON LA DEFINITION MATHEMATHIQUE !!! bigmouth.gif

Ce prgm génére des labyrinthes des plus magnifiques, le principe n'a
rien en commain avec la première version, il en crée des "parfaits"
selon la définition mathématique (aucunes zones inaccéssibles, pas "d'ilôts").
Deplus je pense que même si le prgm est un peu long à générer les labys il est
suffisament optimiser pour tourner correctement... cupsmiley.gif

Vous allez en avoir plein les yeux ! J'ai réfléchis, j'ai écris, j'ai réussit glasses.gif !!!

Code
:Menu("LABYRINTHE","REPET",2,"NEW",1)
:Lbl 1
:AxesNaff:Zstandard:EffDessin
:RappelImage (le n° de votre image):Pause:EffDessin  ----(Ligne facultative).
:
:Vertical 9.8:Vertical -9.8
:Horizontale 9.8:Horizontale -9.8
:
:{0,4,0,-4}-)L1:{4,0,-4,0}-)L2
:0-)R
:Pxl-On(5,3):Pxl-On(3,89):Pxl-On(59,5):Pxl-On(57,91)
:Lbl 0
:
:5+4entAléat(0,13)-)A
:5+4entAléat(O,21)-)B
:Pxl-on(A,B)
:
:While 1
:
:entAléat(1,4)-)L
:L1(L)-)C:L2(L)-)D
:
:If pxl-Test(A+C,B+D)=0:Then
:A+C-)A:B+D-)A
:
:For(N,0,3)
:Pxl-On(A-C/4N,B-D/4N):End
:
:Else
:If pxl-Test(A+4,B)+Pxl-Test(A-4,B)+pxl-Test(A,B+4)+pxl-Test(A,B-4)=4
:Goto 0
:End:End
______________________________________________________________________
A métre à la suite du prgm si vous souhaitez pouvoir vous déplacer
à l'intérieur (le but est d'ateindre le point se placant de façon
alétoire sur le labyrinthe).
______________________________________________________________________
:Lbl 2
:
:4entAléat(1,14)+3-)C
:4entAléat(1,21)+3-)D
:Pxl-On(C,D)
:If R=0:Then:3-)A:3-)B:End:1-)R
:
:While A(différent de)C ou B(différent de)D
:codeTouche-)K
:
:If K=45:Stop
:If K=24:-4-)Y
:If K=26:4-)Y
:If K=25:-4-)X
:If K=34:4-)X
:
:If Pxl-Test(A+X/2,B+Y/2)=0:Then
:Pxl-Off(A,B):Pxl-Off(A-1,B):Pxl-Off(A+1,B):Pxl-Off(A,B-1):Pxl-Off(A,B+1)
:A+X-)A:B+Y-)B
:Pxl-On(A,B):Pxl-On(A-1,B):Pxl-On(A+1,B):Pxl-On(A,B-1):Pxl-On(A,B+1)
:End:0-)X:0-)Y
:
:End
:
:Menu("GAGNE !","REPET",2,"QUITTER",3)
:Lbl 3:EffListe L1:EffListe L2:AxesAff:EffEcr:Stop


IMPORTANT !

Lorsque, après avoir séléctioner NEW, le prgm à terminer de
générer le labyrinthe, celui-ci ne peut malheuresement pas encore s'arreter seul
(sous paine de ralentir ce prgm déjà assez long...). Vous devez donc, une fois
que vous penser que toutes les cases ont étaient dessinées, appuyer sur "ON" et
choisir "Quitter". Puis redémarer le prgm et choisir cette fois la commande "REPET"
pour le voir réaparaître. Vous devez appuier sur l'une des touches directionelles
pour commancer à jouer...

REMARQUE:

--Une fois arriver sur le petit point, vous avez gagné, vous pouvez y
rejouer en réutilisant "REPET"
--Si un labyrinthe vous plait, pourquoi pas ne pas l'enregistrer avec la commande
"SauveImage" dans le menu Dessin de la calto. Il vous sufirat de faire un
"RappelImage" puis "REPET" dans le prgm pour y rejouer !
--"REPET" sert à en rejouer un... (une fois l'avoir générer, et si toutes fois vous
n'ayez pas éxécuter la commande NEW ou EffDessin après celui-ci)...
--"ANNUL" pour quitter pandant le jeu.

Et voici le lien pour télécharger la vidéo:
http://www.filedropper.com/dscn0214_1
Et l'image de fond:
http://www.filedropper.com/dscn0208
azaki44 le 06/12/2010 à 20:00
Bonjour. (oula, ça fait bien 3/4 ans que j'suis pas venu par ici, par faute de temps (j'ai le bac cette année, puis j'suis en L donc on touche plus aux calculatrices, a mon grand regret... enfin bref xD))

Tu pourrais rajouter des sortes d'évènements dans ton labyrinthe: par exemple des pièges etc, que tu pourrais faire apparaitre aléatoirement dessus (avec des goto, des lbl et une génération de chiffres ça doit être possible).

Ce genre de pièges, ça pourrait être des téléporteurs qui ramènent au point de départ, ou alors qui regénèrent le labyrinthe, etc.

Ya tellement de choses a faire avec ce genre de programmes!
(De plus si tu es très, très ambitieux et patient, tu pourrais t'inspirer des vieux RPGs type "j'me fais des donjons, je cherche des trésors et latte des monstres") ^^
ld le 07/12/2010 à 11:46
Salut Azaki44, content de te rencontrer ! moodforlove.gif

C'est avec un grand OUI, que je je te répond... bigmouth.gif
Oui ce prgm n'est là que le début, la base, la racine et la promesse d'un
grand jeu qui n'aspire qu'a être perfectionné ! happy.gif
Je t'avoue que trouver et optimiser un algorithme en basic assez rapide performant pour générer des labyrinthes dit "parfait" selon la définition mathématique m'a donner du fils à retordre et relevait du défit ! karate.gif

Ayant deviner quelques'unes de mais idées, je lâche le secret et lève le voile
sur c'elles-ci pour mes prochaines version du prgm...

Version 4:
-Point de téléportation (tunnel souterrains).
-Possibilité de déplacer/casser des murs.
-Ouvrir des portes à l'aide de clés ramasser le long du parcourt.
-Vitesse de génération des Laby X 2 (et çà c'est déjà sur papier !)

Version 5
-Un labyrinthe mouvant + extension de celui-ci de chaque côtes de l'écran.
-Un Minotor (monstre) evil.gif vous poursuivant dans ce dédale de murs...

Version 6
-Des pouvoir spéciaux.
-Et plein d'autres truc génial, çà peut parraitre optimiste mais c'est possible !

N'hésitez pas à me faire part de vos idées ! bigmouth.gif
Et ne me faite plus dévoiler mes intentions ! cupsmiley.gif
Salut à tous ! glasses.gif
ld le 09/12/2010 à 13:03
Bon bin... Je croit que çà à l'aire de plaire à pas grand monde. ahh.gif
J'ai terminer la version 4 (beaucoup plus rapide, des labys prenant tout l'écran,
encore plus jolis et avec un minotaure qui vous poursuit dans ce dédale de murs, des passages souterrains...)
Je me tâte encore pour le publier... angry.gif
Ça s’arrêtera peut'être là... cry.gif
Pour ma part, je finirait mon Bomrman, pi-ché-tout...
Avertissement :
Il s'agit d'une page optimisée pour la navigation mobile. Voir la page originale.