[R] Realisation d'un labyrinthe

Aide et conseils concernant AutoIt et ses outils.
Règles du forum
.
Répondre
zarnergun
Niveau 3
Niveau 3
Messages : 46
Enregistré le : lun. 27 juin 2011 21:21
Status : Hors ligne

[R] Realisation d'un labyrinthe

#1

Message par zarnergun »

Bonjour à tous,
Je me lance dans la réalisation d'un générateur de labyrinthe en autoit, et malheureusement je débute en même temps (oui c'est une façon comme une autre d'apprendre), après les tutos sdz (plus ou moins et cryptage) ou je m'en suis très bien sorti en poussant le vice a fond, je me suis décidé a attaquer un peu plus gros et faire travailler mon cerveau.

Alors voila mon début de réalisation :

- Générer un tableau X-Y avec l'ensemble de ces cases a 0
- Partir d'un point et checker si les voisins sont disponibles pour être visités (passage de 0 a 1)
- Si le voisin est dispo, on le visite, on coche sa case d'un 1 et on recommence la routine.
- Si le voisin est indisponible, on re-check jusqu’à tomber sur une disponible.

Pour l'instant je me suis arrêter la mais je prévois de faire comme ceci :
- Historique du déplacement
- Retour arrière en cas de blocage

Voici le problème :

Pour je ne sais qu'elle raison (erreur de ma part), le script a tout d'abord l'air de fonctionner correctement puis d'un coup ne réagis pas normalement et ne poursuis pas un déplacement correcte dans les limites que je lui est imposé. De plus il se finit alors qu'ils restent des voisins disponibles.

je ne peux pas vous dire comment se produit le phénomène puisque j'utilise l'aléatoire, mais sur tout les tests effectués avant de poster, tous on foirés, donc vous devriez avoir des foirés également.

Voici le code :
► Afficher le texteNouveau code
je suis conscient de la taille du truc et que c'est un peu chiant a lire, j'ai essayé de faire le plus structurer possible et j'ai commenté chaque fonction.

Merci d'avance a celui ou ceux qui comprendra/comprendront le phénomène anormal
Modifié en dernier par zarnergun le mer. 29 juin 2011 15:19, modifié 3 fois.
Avatar du membre
ZDS
Membre émérite
Membre émérite
Messages : 554
Enregistré le : jeu. 10 juin 2010 10:35
Localisation : 22300 Cul-d'chouette Langue-de-vache
Status : Hors ligne

Re: [..] Realisation d'un labyrinthe

#2

Message par ZDS »

Bonjour,

Je pense que plusieurs choses ne vont pas de base. Déjà ta sdd (structure de données) ne me semble pas suffisante (une matrice booléenne MxN est très contraignante et ne sera jamais assez). Ensuite tu utilises un bouclage basé sur un aléatoire qui pourrait s'avérer catastrophique: Il existe des algos de parcours de graphe ultra puissant (en plus de récupérer ton chemin en question, tu pourrais chopper en plus le chemin le plus court).

Je n'aurai pas le temps de t'aider aujourd'hui, mais déjà je peux t'aiguiller sur trois points :
  • Reprend ta façon de créer ton "graphe" (labyrinthe, graphe, matrice, tableau, fichier texte, ...). Choisis mieux selon ton besoin, et surtout améliore ta structure :
    exemple, un labyrinthe carré ou rectangulaire, où chaque case est carré avec 0, 1, 2, 3 ou 4 murs (un truc classique quoi), de 15 cases de large sur 10 cases de haut, la façon de modéliser le labyrinthe est une matrice $tab [15] [10], mais où chaque case peut prendre une valeur entre 0 et 15.
    • valeur de base : 0
    • si il y a un mur en haut, on ajoute 1
    • si il y a un mur en gauche, on ajoute 2
    • si il y a un mur à gauche, on ajoute 4
    • si il y a un mur à droite, on ajoute 8
    Ensuite pour savoir si tu peux monter quand tu es sur la case (X,Y), tu n'as plus qu'à travailler sur des modulos, ou une décomposition du résultat en binaire. $val = $tab[X][Y] = 10 => 10 = 8 + 2 = mur droite + mur gauche, on peut aller en haut
    Bref, je te laisse réfléchir à ça.
  • Choisis un meilleur algo, genre l'algorithme de Dijkstra, pour parcourir ton graphe. Au moins tu te planteras pas avec un script bancal qu'on peut comparer à un aveugle sous LSD, il court partout, mais sans savoir où, et il risque de faire très longtemps les même conneries, surtout si il tourne toujours du même coté.
  • Et enfin pour un souci de clarté, évite ce genre de fonction (une fonction se doit de se suffire à elle même, et non dans un contexte bizarre et obligatoire) :

    Code : Tout sélectionner

    Func cocher_case()
    ;~  Coche la case d'un 1 une fois visite
        $tableau_general[$position_X][$position_Y] = 1
    EndFunc
    Car dans ce cas là, je suppose qu'un appel potable se fait ainsi,

    Code : Tout sélectionner

    Global $tableau_general, $position_X, $position_Y
    [...]
    $position_X = 4
    $position_Y = 7
    cocher_case()
    , non? (avoue que c'est pas génial) Utilise plutôt quelque chose de concret :

    Code : Tout sélectionner

    Func cocher_case(ByRef $tab, $X, $Y)
        $tab[$X][$Y] = 1
    EndFunc
    et appelle ta fonction avec un simple : cocher_case($tableau_general, 4, 7)
Voila, j'essayerai de t'aider demain ou ce soir.

A bientôt !
ZDS : Chef de projet du nAiO (logiciel AutoIt gratuit sous licence CC 4.0 BY-NC-SA)
Tout problème a une solution, donc si il y a pas d'solution, c'est qu'il y a pas d'problème !
zarnergun
Niveau 3
Niveau 3
Messages : 46
Enregistré le : lun. 27 juin 2011 21:21
Status : Hors ligne

Re: [..] Realisation d'un labyrinthe

#3

Message par zarnergun »

Merci beaucoup pour toutes ces informations, il est vrai que mon script est un peu bancale et la solution n'est pas des plus optimal. La raison est que je désire faire la génération selon deux méthodes :

- http://fr.wikipedia.org/wiki/Mod%C3%A9l ... exhaustive

- http://fr.wikipedia.org/wiki/Mod%C3%A9l ... de_chemins

pour réalisé la méthode dite d'exploration exhaustive, je crains n'avoir guère d'autre choix que le burinage pourrie que j'ai entamé ?

Par contre je prend en considération les critiques et conseils pour m'améliorer, merci.
Je retient la méthode dijkstra pour faire l'algo complémentaire : La résolution.

Je m'attelle a la correction du style, si quelqu'un a une idée quand au problème, je suis tout ouï
zarnergun
Niveau 3
Niveau 3
Messages : 46
Enregistré le : lun. 27 juin 2011 21:21
Status : Hors ligne

Re: [..] Realisation d'un labyrinthe

#4

Message par zarnergun »

Voila j'ai mis a jour le programme(code dans le premier post), la syntaxe est bien plus simple, une seule fonction pour le déplacement ca simplifie grandement la compréhension, par contre je suis face un problème :

avant de me déplacer je vérifie si je suis pas coincé (=plus de 0 dans le voisinage), hors cette vérification pose véritablement problème lorsque l'on se trouve a proximité d'un bord du tableau, en effet je check une cellule du tableau qui n'existe pas et le programme plante misérablement. J'ai fouillé un peu la doc sur les _array je n'ai pas trouvé de fonction permettant de "vérifier" l’existence d'une cellule/variable un peu comme on a les isset en php je ne trouve pas ce genre de fonction en autoit.
Il y a toujours la possibilité de faire une fonction particulière pour chaque cas particulier mais on est pas arrivé et la je sèche, merci

J'ai pas encore implanté ton idée de nombre pour déterminer les murs mais c'est l'étape d’après quand ça sera fonctionnel mon petit problème
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2284
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [..] Realisation d'un labyrinthe

#5

Message par jchd »

Quand tu es contre un bord, tu as un (ou deux) indice de ton tableau 2D à une borne, soit 0 soit UBound(*) - 1. Du coup si tu es à 0 et que tu fais -1, ou si tu est au dernier indice et que tu fais +1, ça explose.
Il suffit de faire le test dans chaque cas.
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
ZDS
Membre émérite
Membre émérite
Messages : 554
Enregistré le : jeu. 10 juin 2010 10:35
Localisation : 22300 Cul-d'chouette Langue-de-vache
Status : Hors ligne

Re: [..] Realisation d'un labyrinthe

#6

Message par ZDS »

Ou bien de rajouter un bord à ta matrice de chaque coté. bord où il est impossible de modifier la valeur ou même d'aller, juste consulter.

La méthode de JCHD est la plus simple, tu n'as qu'à changer ta fonction cocher_case(ByRef $tab, $i, $j)

Code : Tout sélectionner

Func cocher_case(ByRef $tab, $i, $j)
    Local $x = Ubound($tab,1), $y = Ubound($tab,2)
    If $i<0 Or $i>=$x Or $j<0 Or $j>=$y Then Return 0 ; 0 est un retour disant que la procédure a échoué
    $tab[$i][$j] = 1
    Return 1 ; 1 est un retour disant que la procédure a réussi
EndFunc
et ajouter une fonction lire_case($tab, $i, $j), le ByRef est inutile car aucune écriture est prévue dans $tab

Code : Tout sélectionner

Func lire_case($tab, $i, $j)
    Local $x = Ubound($tab,1), $y = Ubound($tab,2)
    If $i<0 Or $i>=$x Or $j<0 Or $j>=$y Then Return -1 ; Si la case est en dehors du tableau, on renvoye le résultat qu'on a prévu pour une case inaccessible
    Return $tab[$i][$j]
EndFunc
Ensuite, il n'y a plus qu'à remplacer les $tableau[$x][$y] de ton code par des lire_case($tableau, $x, $y), ce qui empèchera les plantages. Voici une version modifiée de ton dernier code :
► Afficher le texteScript (version sécurisée)
PS: J'ai modifié pas mal de chose, dont ton generer_tableau(...), j'ai notamment enlevé le $name, car tu fournissais en entrée une variable (une chaine de caractères en l'occurrence) et tu la "modifiais" en un tableau : D'une part une cohérence des données pouvant s'avérer catastrophique, et de l'autre une variable d'entrée qui au final n'était ni lue ni travaillée. J'ai aussi modifié ton switch final (il y avait une erreur concernant le $var=4, tout comme le $var=3 tu décrémentais Y, je suppose qu'il fallait l'incrémenter cette fois, non? ^^), et j'en ai fait un select, plus facile pour la compréhension à mon avis (surtout que les And et Or sont des coupe-circuits en AutoIt, pas besoin de se prendre la tête ^^).

Bref, bonne lecture à bientôt !

PS: Au final dans ta matrice :
- 1 = case cochée
- 0 = case libre
- -1 = case inaccessible => valeur non présente dans le tableau, mais pouvant être retournée par la fonction lire_case(...)
Modifié en dernier par ZDS le mer. 29 juin 2011 15:10, modifié 1 fois.
ZDS : Chef de projet du nAiO (logiciel AutoIt gratuit sous licence CC 4.0 BY-NC-SA)
Tout problème a une solution, donc si il y a pas d'solution, c'est qu'il y a pas d'problème !
zarnergun
Niveau 3
Niveau 3
Messages : 46
Enregistré le : lun. 27 juin 2011 21:21
Status : Hors ligne

Re: [..] Realisation d'un labyrinthe

#7

Message par zarnergun »

Hum oui votre solution est plus simple que celle que j'avais imaginer, je n'ai plus qu'a l'adapter, pour que le voisin qui est hors bornes ne soit pas considérer comme voisin.

Edit : Merci énormément ZDS, Effectivement votre méthode est beaucoup plus claire, en fait je m'y prenais comme un manche a balai. Vous me permettez de progresser, j’apprécie, le système fonctionne parfaitement, je n'ai plus qu'a continuer et essayer de faire structuré et intelligent par la suite.

Je vous remercie encore énormément, vous êtes super et très a l'écoute.
Avatar du membre
ZDS
Membre émérite
Membre émérite
Messages : 554
Enregistré le : jeu. 10 juin 2010 10:35
Localisation : 22300 Cul-d'chouette Langue-de-vache
Status : Hors ligne

Re: [R] Realisation d'un labyrinthe

#8

Message par ZDS »

Y a pas de souci, perso ça me fait plaisir de participer à de l'algo, personnellement c'est ce que je préfère :D (Besoin d'une preuve? http://www.autoitscript.fr/forum/viewto ... f=8&t=5392) Si tu as besoin d'aide par la suite pour la partie résolution du labyrinthe (l'algo dont je t'ai parlé, plus court chemin, couverture globale d'un graphe et compagnie), n'hésite pas !

A bientôt !

PS : Le vouvoyement me fait prendre un coup de vieux, merci, super sympa... Grrrr! ^^
ZDS : Chef de projet du nAiO (logiciel AutoIt gratuit sous licence CC 4.0 BY-NC-SA)
Tout problème a une solution, donc si il y a pas d'solution, c'est qu'il y a pas d'problème !
Avatar du membre
timmalos
Niveau 11
Niveau 11
Messages : 1970
Enregistré le : dim. 18 mai 2008 15:16
Status : Hors ligne

Re: [R] Realisation d'un labyrinthe

#9

Message par timmalos »

Tu peux également jeter un coup d'oeil sur le superbe programme de Tolf, mais pas trop car toutes les informations te seraient données ;)

http://www.siteduzero.com/concours-657- ... tages.html
zarnergun
Niveau 3
Niveau 3
Messages : 46
Enregistré le : lun. 27 juin 2011 21:21
Status : Hors ligne

Re: [R] Realisation d'un labyrinthe

#10

Message par zarnergun »

Merci a vous deux, je préfère essayer tout seul, c'est le meilleur moyen de progresser, si on a un modèle on est tenté de s'en servir. Si je peux te tutoyer, alors aucun soucis, je trouve que le vouvoiement dans l'entraide c'est pas terrible, alors merci a toi :)
j'ai commencer a lire l'algo que tu m'as présenté, il est vrai que ce n'est pas de toute facilité mais je vais le lire en profondeur puis mettre se que j'ai compris sur papier. Je n'hésiterais pas a faire part de mes petits soucis c'est d'accord.

A bientôt :)
Avatar du membre
timmalos
Niveau 11
Niveau 11
Messages : 1970
Enregistré le : dim. 18 mai 2008 15:16
Status : Hors ligne

Re: [R] Realisation d'un labyrinthe

#11

Message par timmalos »

Si ca peut t'aider, Voici la page que j'utilise à chaque fois que je dois me referer à la génération d'un labyrinthe :

http://ilay.org/yann/articles/maze/
zarnergun
Niveau 3
Niveau 3
Messages : 46
Enregistré le : lun. 27 juin 2011 21:21
Status : Hors ligne

Re: [R] Realisation d'un labyrinthe

#12

Message par zarnergun »

Super merci je vais le lire :)
Euh dernière petite question, y a t'il assez de fonctionnalités "graphiques" dans les lib par défauts ou je dois e tourner vers ce que j'ai cru voir : "GDIplus" pour faire les murs et tout ca ?

Ignorer cette question je vais m'en sortir normalement avec _GDIPlus_GraphicsDrawLine d'apres la doc
Répondre