[R] Pathfinding

Aide et conseils concernant AutoIt et ses outils.
Règles du forum
.
Répondre
Avatar du membre
sozary
Niveau 6
Niveau 6
Messages : 274
Enregistré le : lun. 20 janv. 2014 19:17
Status : Hors ligne

[R] Pathfinding

#1

Message par sozary »

Bonjour à tous!
J'essaye actuellement de réaliser du pathfinding, grâce au site Open Classroom, avec la méthode de Dijkstra.
Voici la page: lien.
J'ai essayé de programmer l'algorithme pour réaliser un programme étant capable de trouver le chemin le plus court pour aller d'une ville à une autre, malheureusement, mon code à un problème ou deux, ou trois, voir plus :(!
Voici.
Merci d'avance!
Fichiers joints
pathfinding - modifs.au3
pathfinding
(4.46 Kio) Téléchargé 53 fois
Modifié en dernier par sozary le ven. 01 août 2014 22:33, modifié 1 fois.
"Là où la volonté est grande, les difficultés diminuent.", Niccolò Machiavelli
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2272
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [...] Pathfinding

#2

Message par jchd »

Effectivement.

Je te l'ai remis sur les rails en simplifiant bien des choses inutiles au passage. Kilomètres = poids, donc tu fais l'économie de cette complication. Aussi je ne manipule que les indices des villes.

J'ai tenté d'utiliser des noms parlants et une logique compréhensible en boucle donc sans récursion.
► Afficher le texte
Modifié en dernier par jchd le ven. 01 août 2014 23:50, modifié 3 fois.
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
sozary
Niveau 6
Niveau 6
Messages : 274
Enregistré le : lun. 20 janv. 2014 19:17
Status : Hors ligne

Re: [...] Pathfinding

#3

Message par sozary »

Merci bien!!! Juste une petite question: à quoi servent les doubles underscores (Global Enum $__Poids, $__Visite) svp?
"Là où la volonté est grande, les difficultés diminuent.", Niccolò Machiavelli
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2272
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [R] Pathfinding

#4

Message par jchd »

Convention perso, quand ça me prend. L'idée est de disposer de noms de colonnes à peu près parlants et point trop verbeux pour les indices de tableaux de dimension > 1.

Ainsi $aPoids[$i][$__Poids] ou $aPoids[$i][$__Visite] me parlent plus (sur le coup mais surtout au bout de trois ans) que $aPoids[$i][0] ou $aPoids[$i][1].

Le deux underscores me permettent de m'y retrouver dans des constantes qui peuvent s'avérer nombreuses. Un machin $__quelque_chose c'est une constante de faible signification, comme un nom de colonne.

Si tu remplaces ces constantes par leur valeur numérique, le code fonctionnera toujours mais sera bien moins clair.
Quand il n'y a que 2 ou 3 tableaux simples, on n'en a guère besoin mais dès lors que l'emploi d'indices dans tous les sens et dans de nombreux tableaux foisonnent dans le code, la différence est flagrante.
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
sozary
Niveau 6
Niveau 6
Messages : 274
Enregistré le : lun. 20 janv. 2014 19:17
Status : Hors ligne

Re: [R] Pathfinding

#5

Message par sozary »

donc si j'ai bien compris, "Global Enum $__Poids, $__Visite" attribut la valeur 0 à $__Poids et 1 à $__Visite?
"Là où la volonté est grande, les difficultés diminuent.", Niccolò Machiavelli
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2272
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [R] Pathfinding

#6

Message par jchd »

Exactement, c'est une énumération AutoIt tout ce qu'il y a de banal : Help > Keyword Reference > Enum
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
sozary
Niveau 6
Niveau 6
Messages : 274
Enregistré le : lun. 20 janv. 2014 19:17
Status : Hors ligne

Re: [R] Pathfinding

#7

Message par sozary »

Et pourquoi donc des "_ArrayBinarySearch" au lieu de "_ArraySearch"?
"Là où la volonté est grande, les difficultés diminuent.", Niccolò Machiavelli
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2272
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [R] Pathfinding

#8

Message par jchd »

Parce que cette fonction fait une recherche dichotomique (Google) au lieu de balayer tout le tableau. Si N lignes, on teste log2(N) entrées au maximum. Par contre il faut un tableau trié sur la colonne de recherche, sinon le résultat est indéterminé.

Recharge mon code, j'ai modifié quelques commentaires et viré quelques scories inutiles.
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
sozary
Niveau 6
Niveau 6
Messages : 274
Enregistré le : lun. 20 janv. 2014 19:17
Status : Hors ligne

Re: [R] Pathfinding

#9

Message par sozary »

Merci bien encore! Ce code, il vous a demandé un certain effort de réflexion ou c'était plutôt facile? Car j'avoue que j'arrive à peine à m'en dépatouiller!
"Là où la volonté est grande, les difficultés diminuent.", Niccolò Machiavelli
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2272
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [R] Pathfinding

#10

Message par jchd »

Sur un tableau des communes de France, environ 36248 d'après ma petite base de données, on fait log2(36248) = 15.1456 essais au pire avant de trouver une commune avec _ArrayBinarySearch(). Avec _ArraySearch() on en fait en moyenne 18124.
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2272
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [R] Pathfinding

#11

Message par jchd »

Une fois que les structures de données sont déterminées et adaptées au contexte, l'algorithme n'est pas compliqué. Il suit exactement le site que tu cites.
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
sozary
Niveau 6
Niveau 6
Messages : 274
Enregistré le : lun. 20 janv. 2014 19:17
Status : Hors ligne

Re: [R] Pathfinding

#12

Message par sozary »

Très bien, je vous remercie pour votre aide, je crois que je structure pas assez le problème pour savoir les étapes pertinentes à coder. Sa viendra!
Bonne soirée.
"Là où la volonté est grande, les difficultés diminuent.", Niccolò Machiavelli
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2272
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [R] Pathfinding

#13

Message par jchd »

Tu peux aussi implémenter l'algorithme de Ford pour trouver le plus court chemin dans un graphe pondéré.

Motivation + concentration + ténacité !
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
sozary
Niveau 6
Niveau 6
Messages : 274
Enregistré le : lun. 20 janv. 2014 19:17
Status : Hors ligne

Re: [R] Pathfinding

#14

Message par sozary »

+1 :D! Merci pour tout!!!
"Là où la volonté est grande, les difficultés diminuent.", Niccolò Machiavelli
Avatar du membre
sozary
Niveau 6
Niveau 6
Messages : 274
Enregistré le : lun. 20 janv. 2014 19:17
Status : Hors ligne

Re: [R] Pathfinding

#15

Message par sozary »

Une toute dernière question jchd! Je ne comprends pas:
"Until False" pour la boucle principale, false pour quoi?
Et enfin:
"Local $sEtapes = $aVilles[$iArrivee]
Local $iVille = $iArrivee
Do
$iVille = $aAntecedant[$iVille]
$sEtapes = $aVilles[$iVille] & ', ' & $sEtapes
Until $iVille = $iDepart"
Je n'arrive pas à comprendre ce que cela fait!
Sinon j'ai compris tout le code!
"Là où la volonté est grande, les difficultés diminuent.", Niccolò Machiavelli
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2272
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [R] Pathfinding

#16

Message par jchd »

Pour le
Do
...
Until False
j'aurais aussi bien pu faire :
While True
...
WEnd
C'est une boucle infinie, dont on sort par ExitLoop sur la condition ville-étape = ville d'arrivée.

La dernière partie permet de reconstituer l'itinéraire depuis l'arrivée jusqu'au départ en parcourant le tableau $aAntecedant à l'envers, car ce tableau qui renferme ces informations est un tableau ... d'antécédants. On part donc de la fin (ville d'arrivée) et on récupère l'étape antérieure (précédante) grâce à ce tableau. Comme je ne stocke là que les indices des villes connues dans la table $aVilles, il me faut aller pêcher le nom en clair dans ce tableau-là. C'est ainsi que je construit ma chaîne d'itinéraire, dans le sens départ --> arrivée, ce qui me semble plus intuitif que dans le sens inverse.

N'hésite pas à demander si quelque chose n'est pas limpide. C'est quand même plus instructif que les foultitudes de "mon bot de jeu marche pô" qui peuplent l'été sur nos forums (fora !).
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
mikell
Spammer !
Spammer !
Messages : 6292
Enregistré le : dim. 29 mai 2011 17:32
Localisation : Deep Cévennes
Status : Hors ligne

Re: [R] Pathfinding

#17

Message par mikell »

Dans le genre il y a un code sympa ici qui utilise l'algorithme A*
Enfin y avait, parce qu'il ne marche bien qu'avec l'include Array.au3 de la 3.3.8.1 (et pas seulement à cause de la fonction _ArrayCreate , mais je sais pas pourquoi)
" L'échec est le fondement de la réussite. " (Lao-Tseu )
" Plus ça rate, plus on a de chances que ça marche " (les Shadoks )
Avatar du membre
sozary
Niveau 6
Niveau 6
Messages : 274
Enregistré le : lun. 20 janv. 2014 19:17
Status : Hors ligne

Re: [R] Pathfinding

#18

Message par sozary »

D'accord merci! Et mikell, merci aussi!!
"Là où la volonté est grande, les difficultés diminuent.", Niccolò Machiavelli
Répondre