Autorisation : Membre
Nb de messages : 14
Inscrit le : Dim 11 Jan 2015, 17:13
Posté le : Jeu 05 Fév 2015, 0:08
Salut, pour relancer le forum, et pour vous aidez, et perfectionner votre connaissance en programmation je vous propose de créer :
Un generateur de labyrinthe parfait.
-PourQuoi parfait et qu'est ce que c'est ?? :
C'est un labyrinthe n'ayant qu'une issue permettant d'aller d'un point A a u un point B.
-Avec quelle methode ?? :
Avec cette methode:
Cette méthode permet de savoir quelles cases font partie du même chemin.
on peut dire que c'est un genre d'infection : c'est-à-dire que toutes les cases de mon chemin prennent le même numéro.
Grâce à cela on peut éviter les cas comme celui-ci ;
Sachez que j'ai déjà réalisé cet algorithme mais pas encore sur Ti.
Celui déjà fait est en python et fonction plutôt très bien !
Je pense que sur Ti cela va être lent mais au bout de 2 min on pourrait obtenir un beau labyrinthe parfait d'une bonne taille.
Autorisation : Membre
Nb de messages : 14
Inscrit le : Dim 11 Jan 2015, 17:13
Posté le : Jeu 05 Fév 2015, 0:11
Oups, Dis sur le wiki et qui peut aider :
Citer
Différentes structures de données sont envisageables pour la représentation du labyrinthe dans un programme.
La plus simple consiste à définir deux matrices de valeurs booléennes, l'une de taille (m+1) x n qui va définir l'existence des murs verticaux entre les différentes cases de la grille, l'autre de taille m x (n+1) qui va représenter les murs horizontaux de manière similaire. Avec cette structure de données, le tracé de la grille devient un jeu d'enfant.
Et d’après moi une troisième pour stocker la valeur des cases
Et oui votre calculatrice ne va plus avoir de mémoire avec tout ça !
Autorisation : Membre
Nb de messages : 3767
Inscrit le : Lun 19 Oct 2009, 21:25
Posté le : Jeu 05 Fév 2015, 10:37
Il est possible d'utiliser l'écran lui-même en guise de mémoire. Ce n'est pas un gros problème dans une calculatrice TI.
Songe que la structure de données à choisir doit dépendre aussi de l'implémentation. Le langage TI-Basic est particulièrement démuni.
Utiliser une matrice par type de mur n'est pas une excellente idée en TI-Basic car cela imposera de différencier les types de murs par des alternatives car le TI-Basic n'a pas de pointeur et donc pas de troisième dimension. Ainsi stocker les deux murs d'une cellule est préférable en TI-Basic.
Le membre LD a déjà posté un programme générant des labyrinthes parfaits sur ce forum, il utilise un autre algorithme qui consiste à dessiner les murs comme un réseau en partant de l'extérieur et des murs déjà dessinés.
Je ne suis jamais passé à l'acte mais faire de même m'intéresse.
Utilise a balise bbcode quote pour citer plutôt que quatre guillemets. (quote=citer) (j'édite moi-même en tant que modérateur)
Tu peux éditer ton propre message en tant que membre plutôt que dupliquer un message, surtout peu de temps après.
---------------------- ti82statfr: 2008, inscrit: 2009, ti84pocketfr: noël2011, ti30xbmultiview: iut 2012-2014
Perfectionniste, manque tact. Pas le temps de tout publier depuis 2011. Répond toujours aux questions. (rédigé juin 2014)
Il est dit :
"À chaque itération, on choisit un mur à ouvrir de manière aléatoire."
Or il faut imaginer que la calto va très souvent essayer d'ouvrir des murs déjà ouverts, et que plus l’algorithme avancera, moins il y aura de murs à ouvrir, moins la calto aura aléatoirement la chance d'en proposer un fermé, et plus le programme ralentira...
Aussi, je ne pense pas qu'il soit possible de modifier les valeurs d'une matrice comme sur l'image.
Le miens, (dans ma signature), fonctionne comme celui au paragraphe : Exploration exhaustive
Mais je pense qu'on peut le faire évoluer.
En générant d'abord un labyrinthe, puis en le faisant se décaler qu'en ont s'approche des borts. Ils se générerait ainsi en continu.
On décale l'image, un blanc se créé d'un coté, et on y génère des murs.
Evidemment la parie opposée effacée sera perdue et on aurait autre chose en y revenant. Mais ce serait drôle !!
Je pense que que combiné au prgm ASM Zscroll c'est possible. Il fait déjà défiler les image de haut en bas. Il ne manque plus que de droite à gauche.
Autorisation : Membre
Nb de messages : 14
Inscrit le : Dim 11 Jan 2015, 17:13
Posté le : Jeu 05 Fév 2015, 22:19
Je suis entierement d'accord avec toi, surtout que une ti-82 met 3 heures a faire un nombre aleatoire entre 1 et 10 donc...
Mais c'est pour cela que j'ai bien dis :
Citer
Au bout de 2min on pourra obtenir un beau petit labyrinthe
bien sur 2 min c'est exagéré mais 30 sec parai déjà plus censé
Autorisation : Membre
Nb de messages : 3767
Inscrit le : Lun 19 Oct 2009, 21:25
Posté le : Ven 06 Fév 2015, 8:30
En ce qui concerne le fait de trouver des espaces à remplir aléatoirement sans être limité par la difficulté de trouver les dernières cases, j'ai des solutions à proposer, que ce soit la génération des chemins ou la génération des murs.
Je pense que le plus simple serait de cribler les cases en retenant une Nième case libre pour N un nombre pseudo-aléatoire. L'exploration exhaustive de l'article semble meilleur en terme de complexité mais je n'en suis pas certain.
Tandis que si on retient une liste des cases d'une catégorie (soit libre soit occupée), cela prendra bien sûr des ressources de base de donnée mais éviterait de cribler inutilement toutes les cases ou un chemin. J'avais choisi la plus compliquée et abandonné quand j'ai envisagé de m'en mêler la dernière fois suite au programme de LD.
---------------------- ti82statfr: 2008, inscrit: 2009, ti84pocketfr: noël2011, ti30xbmultiview: iut 2012-2014
Perfectionniste, manque tact. Pas le temps de tout publier depuis 2011. Répond toujours aux questions. (rédigé juin 2014)
Autorisation : Membre
Nb de messages : 369
Inscrit le : Dim 13 Fév 2011, 14:17
Posté le : Sam 11 Avr 2015, 7:01
Salut les gens ! Pfiou, ça faisait longtemps que j'avais pas poster sur ce forum ! Vous vous demandez tous "qu'est-il devenu??" Et bien je poursuis ma route en licence informatique, tranquillement, et d'ailleurs, je me dis bien souvent que je n'aurait pas pu y arriver sans avoir commencer sur calculette, alors merci tout82 et les gens dedans <3
Sinon, pourquoi je poste ici? Parce que déjà je ne m'étais jamais vraiment penché sur les labyrinthes, par peur de tomber dedans (humour), et quand j'ai vu le ptit gif je me suis dit que c'était vraiment pas con, et que ça venait de m'apprendre un truc très efficace ;p Du coup, j'ai fait un programme en SDL pour faire des labyrinthe avec cette méthode. Bien sur vous allez me dire : "Mais enfin, ce n'est pas un site de SDL ici !" Et vous avez tout à fait raison ! Mais je me suis dit que tant qu'a faire autant vous le faire partager ! Je vous rassure, j'ai tout perdu de ce que j'avais appris, du coup, si y a des trucs chelou, dites le moi ! Mais normalement le code doit être bon, vu qu'il marche en SDL :p
Bon sans plus attendre le voila, je ne l'ai pas testé sur calculette, d'une part parce que je ne l'ai plus (les joies d'avoir une soeur qui en a besoin), et d'autres part, je n'avais vraiment pas envie de le faire avec wabbitemu, pardonnez moi
Bon, ok, le voila !
Code
46->X
30->Y
(X-1)Y+X(Y-1)->N
for(I,1,XY)
I-1->L1(I)
end
for(I,1,(X-1)Y+X(Y-1))
I-1->L2(I)
1->L3(I)
end
repeat(S!=0)
entalea(1,N)->A
0->L3(L2(A)+1)
if(L2(A)mod(2X-1)<X-1)
then
L1(XL2(A)/(2X-1)+L2(A)mod(2X-1)+1)->C
L1(XL2(A)/(2X-1)+L2(A)mod(2X-1)+2)->V
else
L1(XL2(A)/(2X-1)+L2(A)mod(2X-1)-X+2)->C
L1(XL2(A)/(2X-1)+L2(A)mod(2X-1)+2)->V
end
if(C<V)
then
C->R
V->C
R->V
end
for(I,N,1,-1)
if(L2(I)mod(2X-1)<X-1)
then
if((L1(XL2(I)/(2X-1)+L2(I)mod(2X-1)+1)=C AND V=L1(XL2(I)/(2X-1)+L2(I)mod(2X-1)+2)) OR ((L1(XL2(I)/(2X-1)+L2(I)mod(2X-1)+1)=V AND L1(XL2(I)/(2X-1)+L2(I)mod(2X-1)+2)=C))
for(J,I,N-1)
L2(J+1)->L2(J)
end
N-1->N
end
else
if((C=L1(XL2(I)/(2X-1)+L2(I)mod(2X-1)-X+2) AND V=L1(XL2(I)/(2X-1)+L2(I)mod(2X-1)+2)) OR (V=L1(XL2(I)/(2X-1)+L2(I)mod(2X-1)-X+2) AND C=L1(XL2(I)/(2X-1)+L2(I)mod(2X-1)+2))
for(J,I,N-1)
L2(J+1)->L2(J)
end
N-1->N
end
end
end
for(I,1,XY)
if(L1(I)=C)
V->L1(I)
end
0->S
for(I,1,XY)
S+L1(I)->S
end
for(I,1,(X-1)Y+X(Y-1))
if(L1(I)=1)
Pxl-On((2(I/(2X-1))+(Imod(2X-1)>X-2),(2*(Imod(2X-1)-(X-1)*(Imod(2X-1)>X-2))+(Imod(2X-1)<X-1)))
end
for(I,1,Y)
for(J,1,X)
Pxl-On(2*I-1,2*J-1)
end
end
Oui, il est indenté, je n'arrive plus à coder sans, je trouve que c'est trop bordélique..
Y a surement une erreur avec pxl-on, je sais plus comment il s'utilise, du coup je suis parti du fait qu'il commence en haut a gauche en 0,0 ^^