Poster un nouveau sujet Poster une réponse
Generateur de labyrinthe PARFAIT ?! [TP]
Auteur Message
Paolo972



Autorisation : Membre
Nb de messages : 14
Inscrit le : Dim 11 Jan 2015, 17:13
Posté le : Jeu 05 Fév 2015, 0:08   Citer 

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 ;

Labyrinthe IMPARFAIT :

Labyrinthe PARFAIT :



Je pense qu'il y a suffisament de renseignement.

Les sources : Le WIKI
http://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_d'un_labyrinthe

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.

Voilà, donc si vous êtes intéressé, faites le !

 Adresse email Haut de page Bas de page 
 
Paolo972



Autorisation : Membre
Nb de messages : 14
Inscrit le : Dim 11 Jan 2015, 17:13
Posté le : Jeu 05 Fév 2015, 0:11   Citer 

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 !

 Adresse email Haut de page Bas de page 
 
linkakro



Autorisation : Membre
Nb de messages : 3767
Inscrit le : Lun 19 Oct 2009, 21:25
Posté le : Jeu 05 Fév 2015, 10:37   Citer 

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)

Pour tout le monde et surtout les débutants, quelques-uns des articles courants :
*Traductions Algorithmie/Ti-Basic.
*Caractères spéciaux sur Tout82
Les défauts du TI-Basic : Goto_versus_algo et DelVar/End/Lbl/guillemet/store
 Adresse email Haut de page Bas de page 
 
Google_AdSense



Publicité    



 
m@thieu41



Autorisation : Membre
Nb de messages : 856
Inscrit le : Mer 18 Juil 2012, 18:44
Posté le : Jeu 05 Fév 2015, 14:34   Citer 

C'est un algorithme intéressant en effet mais une plate forme inappropriée comme le souligne linka.

----------------------
Pour vous aidez dans vos débuts (et même ensuite ^^) :
*Tuto Algo->Ti Basic (par Linkakro) : Traduisez vos algo (de type algobox) en prgm pour votre TI!
*Catalogue des emplacements et traductions (anglais/français) des fonctions sur la TI.
*Faites vos propres programmes de maths (par ash)

Et au fait: la politesse n'a jamais tué personne winkle.gif
 Adresse email Haut de page Bas de page 
 
ld
Avatar

Autorisation : Membre
Nb de messages : 373
Inscrit le : Jeu 23 Sep 2010, 16:05
Posté le : Jeu 05 Fév 2015, 20:11   Citer 

Si on y réfléchit d'un peu plus près :

Sur la page qu'il donne :
https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_d'un_labyrinthe

Au paragraphe :
Fusion aléatoire de chemins

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 !! bigmouth.gif
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.

----------------------
Note Éphéméride Chrono Bombrman BlueFishEncryptor Labygénérateur Nord BandeauDeTexte LunarPhase Syracuse Papy-Jump Convertisseur ! SolveurDeSudoku VérificateurDeCodesBanquaire PrgmADiviser CryptageDeVigenere MiniSolv Reed-Solomon Code128Géodésie
 Adresse email Haut de page Bas de page 
 
Paolo972



Autorisation : Membre
Nb de messages : 14
Inscrit le : Dim 11 Jan 2015, 17:13
Posté le : Jeu 05 Fév 2015, 22:19   Citer 

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é

 Adresse email Haut de page Bas de page 
 
linkakro



Autorisation : Membre
Nb de messages : 3767
Inscrit le : Lun 19 Oct 2009, 21:25
Posté le : Ven 06 Fév 2015, 8:30   Citer 

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. clown.gif

----------------------
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)

Pour tout le monde et surtout les débutants, quelques-uns des articles courants :
*Traductions Algorithmie/Ti-Basic.
*Caractères spéciaux sur Tout82
Les défauts du TI-Basic : Goto_versus_algo et DelVar/End/Lbl/guillemet/store
 Adresse email Haut de page Bas de page 
 
ld
Avatar

Autorisation : Membre
Nb de messages : 373
Inscrit le : Jeu 23 Sep 2010, 16:05
Posté le : Ven 06 Fév 2015, 17:58   Citer 

Voilà, en résumé il faudrait tenir une liste des murs restants, et choisir aléatoirement parmi eux.
La tête de clown te va très bien Linkakro laugh.gif

----------------------
Note Éphéméride Chrono Bombrman BlueFishEncryptor Labygénérateur Nord BandeauDeTexte LunarPhase Syracuse Papy-Jump Convertisseur ! SolveurDeSudoku VérificateurDeCodesBanquaire PrgmADiviser CryptageDeVigenere MiniSolv Reed-Solomon Code128Géodésie
 Adresse email Haut de page Bas de page 
 
snap



Autorisation : Membre
Nb de messages : 369
Inscrit le : Dim 13 Fév 2011, 14:17
Posté le : Sam 11 Avr 2015, 7:01   Citer 

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 cry.gif

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 ^^

Bisous tout le monde kiss.gif

----------------------
Commence un monopoly non graphique et compte bien le finir!
Lycée de l'escaut Valenciennes happy.gif
Fan de reflets d'acide!
le meilleur jeu du monde
http://snap-le-terrible.minitroopers.fr
 Adresse email Haut de page Bas de page 
 
Poster un nouveau sujet Poster une réponse





  Powered by Fire-Soft-Board v1.0.10 © 2004 - 2024 Groupe FSB
Page générée en 9 requêtes
BlackOne par Grimmlink