AutoIt Français

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!

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

Code : Tout sélectionner

#include <Array.au3>

; principe général : utiliser la représentation des données la plus véloce :
; False / True au lieu de "Non" / "Oui", Null pour "Aucun", entiers et non chaînes, etc.

; liste des villes-étapes.
Global $aVilles = [ _
    "Arras", _
    "Bordeaux", _
    "Brest", _
    "Lyon", _
    "Marseille", _
    "Montpellier", _
    "Nantes", _
    "Paris", _
    "Poitier", _
    "Strasbourg" _
]
; Cette liste doit être triée alphabétiquement, sinon on fait :
_ArraySort($aVilles)

Global $iNbVilles = UBound($aVilles)    ; un raccourci de langage bien commode

; tableau construit dynamiquement à partir de $aVilles
Global Enum $__Poids, $__Visite
Global $aPoids[$iNbVilles][2]       ; poids, parcouru
For $i = 0 To $iNbVilles - 1
    $aPoids[$i][$__Poids] = -1
    $aPoids[$i][$__Visite] = False
Next

; tableau construit dynamiquement à partir de $aVilles
Global $aAntecedant[$iNbVilles]     ; antécédant
For $i = 0 To $iNbVilles - 1
    $aAntecedant[$i] = Null
Next

; Cette présentation est un tableau où seules figurent les distances entre villes A et B
Global Enum $__Ville1, $__Ville2, $__Dist
Global $aDistance = [ _             ; départ, cible, distance
    [_ArrayBinarySearch($aVilles, "Arras"), _ArrayBinarySearch($aVilles, "Nantes"), 561], _
    [_ArrayBinarySearch($aVilles, "Arras"), _ArrayBinarySearch($aVilles, "Paris"), 185], _
    [_ArrayBinarySearch($aVilles, "Arras"), _ArrayBinarySearch($aVilles, "Strasbourg"), 522], _
    [_ArrayBinarySearch($aVilles, "Bordeaux"), _ArrayBinarySearch($aVilles, "Nantes"), 334], _
    [_ArrayBinarySearch($aVilles, "Bordeaux"), _ArrayBinarySearch($aVilles, "Poitier"), 237], _
    [_ArrayBinarySearch($aVilles, "Brest"), _ArrayBinarySearch($aVilles, "Nantes"), 298], _
    [_ArrayBinarySearch($aVilles, "Brest"), _ArrayBinarySearch($aVilles, "Paris"), 593], _
    [_ArrayBinarySearch($aVilles, "Lyon"), _ArrayBinarySearch($aVilles, "Marseille"), 315], _
    [_ArrayBinarySearch($aVilles, "Lyon"), _ArrayBinarySearch($aVilles, "Montpellier"), 303], _
    [_ArrayBinarySearch($aVilles, "Lyon"), _ArrayBinarySearch($aVilles, "Paris"), 465], _
    [_ArrayBinarySearch($aVilles, "Lyon"), _ArrayBinarySearch($aVilles, "Strasbourg"), 494], _
    [_ArrayBinarySearch($aVilles, "Marseille"), _ArrayBinarySearch($aVilles, "Montpellier"), 171], _
    [_ArrayBinarySearch($aVilles, "Marseille"), _ArrayBinarySearch($aVilles, "Strasbourg"), 809], _
    [_ArrayBinarySearch($aVilles, "Montpellier"), _ArrayBinarySearch($aVilles, "Poitier"), 557], _
    [_ArrayBinarySearch($aVilles, "Montpellier"), _ArrayBinarySearch($aVilles, "Strasbourg"), 797], _
    [_ArrayBinarySearch($aVilles, "Nantes"), _ArrayBinarySearch($aVilles, "Paris"), 386], _
    [_ArrayBinarySearch($aVilles, "Paris"), _ArrayBinarySearch($aVilles, "Poitier"), 338] _
]

Local $sDepart, $iDepart
Do
    $sDepart = InputBox("", "Ville de départ : ")
    $iDepart = _ArrayBinarySearch($aVilles, $sDepart)
Until $iDepart <> -1

Local $sArrivee, $iArrivee
Do
    $sArrivee = InputBox("", "Ville d'arrivée : ")
    $iArrivee = _ArrayBinarySearch($aVilles, $sArrivee)
Until $iArrivee <> -1

$aPoids[$iDepart][$__Poids] = 0 ; poids zéro de ville départ à ville départ

Local $PoidsMin, $iVilleEtape, $iVilleCible

; Tant que le noeud ayant le poids le plus faible n'est pas le noeud d'arrivée.
Do
    $PoidsMin = 3e300       ; poids inatteignable

    ; On cherche le noeud non parcouru avec le poids minimum mais >= 0
    For $i = 0 To $iNbVilles - 1
        If Not $aPoids[$i][$__Visite] And $aPoids[$i][$__Poids] >= 0 And $aPoids[$i][$__Poids] < $PoidsMin Then
            $PoidsMin = $aPoids[$i][$__Poids]
            $iVilleEtape = $i
        EndIf
    Next
    $aPoids[$iVilleEtape][$__Visite] = True ; parcouru

    If $iVilleEtape = $iArrivee Then ExitLoop

ConsoleWrite(@LF & "Etape de " & $aVilles[$iVilleEtape] & ", " & $aPoids[$iVilleEtape][$__Poids] & " km parcourus." & @LF)

    ; on explore toutes les liaisons possibles depuis la ville étape où l'on n'est pas déjà allé
    For $i = 0 To UBound($aDistance) - 1
        $iVilleCible = -1
        If $aDistance[$i][$__Ville1] = $iVilleEtape Then $iVilleCible = $aDistance[$i][$__Ville2]
        If $aDistance[$i][$__Ville2] = $iVilleEtape Then $iVilleCible = $aDistance[$i][$__Ville1]
        If $iVilleCible >= 0 Then
ConsoleWrite("Liaison " & $aVilles[$iVilleEtape] & ' --> ' & $aVilles[$iVilleCible] & " : ")
            ; les noeuds fils de notre ville-étape défilent
            ; pour chacun, on vérifie qu'on n'est pas déjà passé par là
            ; ET que
            ; (poids de noeud fils non défini OU
            ; poids de noeud fils > poids de noeud père + distance noeud père-noeud fils)
            If Not $aPoids[$iVilleCible][$__Visite] Then
                If ($aPoids[$iVilleCible][$__Poids] < 0 Or _
                $aPoids[$iVilleCible][$__Poids] > $aPoids[$iVilleEtape][$__Poids] + $aDistance[$i][$__Dist]) Then
                    ; alors poids de noeud fils = poids de noeud père + distance noeud père-noeud fils et l'antécédant de noeud fils est noeud père
                    $aPoids[$iVilleCible][$__Poids] = $aPoids[$iVilleEtape][$__Poids] + $aDistance[$i][$__Dist]
                    $aAntecedant[$iVilleCible] = $iVilleEtape
ConsoleWrite("étape potentielle." & @LF)
ConsoleWrite("Poids " & $aVilles[$iVilleCible] & " = " & $aPoids[$iVilleCible][$__Poids] & " # " & $aPoids[$iVilleEtape][$__Poids] + $aDistance[$i][$__Dist] & @LF)
                Else
ConsoleWrite("ville trop éloignée." & @LF)
ConsoleWrite("Poids " & $aVilles[$iVilleCible] & " = " & $aPoids[$iVilleCible][$__Poids] & " # " & $aPoids[$iVilleEtape][$__Poids] + $aDistance[$i][$__Dist] & @LF)
                EndIf
            Else
ConsoleWrite("ville déjà parcourue." & @LF)
            EndIf
        EndIf
    Next
; sortie de boucle si l'on est arrivés
Until False

Local $sEtapes = $aVilles[$iArrivee]
Local $iVille = $iArrivee
Do
    $iVille = $aAntecedant[$iVille]
    $sEtapes = $aVilles[$iVille] & ', ' & $sEtapes
Until $iVille = $iDepart

ConsoleWrite(@LF & "Le plus court itinéraire (" & $aPoids[$iArrivee][$__Poids] & " km) de " & $aVilles[$iDepart] & " à " & $aVilles[$iArrivee] & " est : " & $sEtapes & @LF)

Merci bien!!! Juste une petite question: à quoi servent les doubles underscores (Global Enum $__Poids, $__Visite) svp?

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.

donc si j'ai bien compris, "Global Enum $__Poids, $__Visite" attribut la valeur 0 à $__Poids et 1 à $__Visite?

Exactement, c'est une énumération AutoIt tout ce qu'il y a de banal : Help > Keyword Reference > Enum

Et pourquoi donc des "_ArrayBinarySearch" au lieu de "_ArraySearch"?

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.

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!

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.

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.

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.

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

Motivation + concentration + ténacité !

+1

! Merci pour tout!!!

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!

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

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)

D'accord merci! Et mikell, merci aussi!!

AutoIt Français

[R] Pathfinding

[R] Pathfinding

Re: [...] Pathfinding

Re: [...] Pathfinding

Re: [R] Pathfinding

Re: [R] Pathfinding

Re: [R] Pathfinding

Re: [R] Pathfinding

Re: [R] Pathfinding

Re: [R] Pathfinding

Re: [R] Pathfinding

Re: [R] Pathfinding

Re: [R] Pathfinding

Re: [R] Pathfinding

Re: [R] Pathfinding

Re: [R] Pathfinding

Re: [R] Pathfinding

Re: [R] Pathfinding

Re: [R] Pathfinding