[Ex] A_Star

[sozary]

Bonjour!
Voilà je vais tout vous dire !
Il y a fort longtemps (1 an ou 2), je voulais réaliser l'algorithme de chemin le plus court, sauf que je n'y étais pas parvenu !

Bon, maintenant comme j'ai, je sais pas, plus d'expérience sur le sujet, j'ai voulu retenter ma chance en autoit avant de le traduire en C (oui car j'ai fais ça avec une ancienne fonction que j'avais codé, et c'est très intéressant!).

L'AutoIt me paraît plus simple a utiliser que le C++, bon de 1 parce que c'est vrai, et de 2 car j'ai passé plus de temps avec AutoIt que le C++...

Donc je suis parvenu a faire l'algorithme A* en 1h30 environ, temps qui inclus bien évidement la relecture!

Bon, je sais que c'est pas optimisé du tout !

Voilà :
Normal

► Afficher le texte

Code : Tout sélectionner

#include <array.au3>


Global $closedList[0][5]
Global $openList[0][5]
Global $map[5][5]
Global $depX = 0, $depY = 0, $arrX = 4, $arrY = 0
Global $current[1][5] = [[$depX, $depY, DistanceManhattan($depX, $depY, $arrX, $arrY), "NULL", "NULL"]], $path
Global $vois1 = $current, $vois2 = $current, $vois3 = $current, $vois4 = $current

$map[0][2] = 1
$map[1][2] = 1
$map[2][2] = 1
$map[3][1] = 1

_ArrayAdd($openList, $current)
_ArrayDisplay($map)

Do
    $openList = classeList($openList)

    $current[0][0] = $openList[0][0]
    $current[0][1] = $openList[0][1]
    $current[0][2] = $openList[0][2]
    $current[0][3] = $openList[0][3]
    $current[0][4] = $openList[0][4]

    If $current[0][0] = $arrX And $current[0][1] = $arrY Then
        MsgBox(0, "", "end")
        ExitLoop
    EndIf



    _ArrayDelete($openList, 0)
    _ArrayAdd($closedList, $current)

    ;pour chaque voisins
    verif($vois1, $current[0][0] + 1, $current[0][1], $current[0][0], $current[0][1])
    verif($vois2, $current[0][0] - 1, $current[0][1], $current[0][0], $current[0][1])
    verif($vois3, $current[0][0], $current[0][1] + 1, $current[0][0], $current[0][1])
    verif($vois4, $current[0][0], $current[0][1] - 1, $current[0][0], $current[0][1])

Until UBound($openList) = 0

if $current[0][0] <> $arrX And $current[0][1] <> $arrY Then
    MsgBox(0,"","pas de chemin valide")
Else

    $path = RefaisLechemin($closedList)

    $path = inverseTab($path)

    For $i = 0 To UBound($path) - 1
        $map[$path[$i][1]][$path[$i][0]] = "X"
    Next
    $map[$arrY][$arrX] = "X"
    $map[$depY][$depX] = "X"
    _ArrayDisplay($map)
    _ArrayDisplay($path)
EndIf



Func RefaisLechemin($list)
    $currX = $list[UBound($list) - 1][3]
    $currY = $list[UBound($list) - 1][4]
    Local $chemin[0][2], $index = 99, $node[1][2] = [[$list[UBound($list) - 1][0], $list[UBound($list) - 1][1]]]
    _ArrayAdd($chemin, $node)

    While $index > 0
        $index = retourneIndex($closedList, $currX, $currY)
        If $index <> -1 Then
            $node[0][0] = $list[$index][0]
            $node[0][1] = $list[$index][1]
            _ArrayAdd($chemin, $node)
            $currX = $list[$index][3]
            $currY = $list[$index][4]
        EndIf
    WEnd
    _ArrayAdd($chemin, $node)

    Return $chemin
EndFunc   ;==>RefaisLechemin

Func retourneIndex($list, $x, $y)
    For $i = 0 To UBound($list) - 1
        If $list[$i][0] = $x And $list[$i][1] = $y Then Return $i
    Next

    Return -1
EndFunc   ;==>retourneIndex


Func DistanceManhattan($xa, $ya, $xb, $yb)
    Return Abs($xb - $xa) + Abs($yb - $ya)
EndFunc   ;==>DistanceManhattan

Func classeList($list)
    Local $tmp, $tmp2, $tmp3, $tmp4, $tmp5
    For $i = 0 To UBound($list) - 1
        For $j = $i + 1 To UBound($list) - 1
            If $list[$i][2] > $list[$j][2] Then
                $tmp = $list[$i][4]
                $tmp2 = $list[$i][3]
                $tmp3 = $list[$i][2]
                $tmp4 = $list[$i][1]
                $tmp5 = $list[$i][0]
                $list[$i][4] = $list[$j][4]
                $list[$i][3] = $list[$j][3]
                $list[$i][2] = $list[$j][2]
                $list[$i][1] = $list[$j][1]
                $list[$i][0] = $list[$j][0]
                $list[$j][4] = $tmp
                $list[$j][3] = $tmp2
                $list[$j][2] = $tmp3
                $list[$j][1] = $tmp4
                $list[$j][0] = $tmp5
            EndIf
        Next
    Next

    Return $list
EndFunc   ;==>classeList
Func verif($voisin, $x, $y, $xParent, $yParent)
    If $y < UBound($map) And $x < UBound($map, 2) And $y >= 0 And $x >= 0 Then
        If $map[$y][$x] <> 1 And Not _Search($closedList, $x, $y) Then
            $voisin[0][0] = $x
            $voisin[0][1] = $y
            $voisin[0][2] = DistanceManhattan($x, $y, $arrX, $arrY)
            $voisin[0][3] = $xParent
            $voisin[0][4] = $yParent
            _ArrayAdd($openList, $voisin)
        EndIf
    EndIf

EndFunc   ;==>verif
Func _Search($list, $x, $y)
    For $i = 0 To UBound($list) - 1
        If $list[$i][0] = $x And $list[$i][1] = $y Then Return 1
    Next

    Return 0
EndFunc   ;==>_Search

Func inverseTab($tab)
    Local $tmp, $tmp1
    Switch Mod(UBound($tab), 2)
        Case 0
            For $i = 0 To UBound($tab) / 2
                $tmp = $tab[$i][0]
                $tmp1 = $tab[$i][1]
                $tab[$i][0] = $tab[UBound($tab) - 1 - $i][0]
                $tab[$i][1] = $tab[UBound($tab) - 1 - $i][1]
                $tab[UBound($tab) - 1 - $i][0] = $tmp
                $tab[UBound($tab) - 1 - $i][1] = $tmp1
            Next
        Case Else
            For $i = 0 To (UBound($tab) - 1) / 2
                $tmp = $tab[$i][0]
                $tmp1 = $tab[$i][1]
                $tab[$i][0] = $tab[UBound($tab) - 1 - $i][0]
                $tab[$i][1] = $tab[UBound($tab) - 1 - $i][1]
                $tab[UBound($tab) - 1 - $i][0] = $tmp
                $tab[UBound($tab) - 1 - $i][1] = $tmp1
            Next
    EndSwitch

    Return $tab
EndFunc   ;==>inverseTab

 

Récursif:

► Afficher le texte

Code : Tout sélectionner

#include <array.au3>


Global $closedList[0][5]
Global $openList[0][5]
Global $map[5][5]
Global $depX = 0, $depY = 0, $arrX = 4, $arrY = 0
Global $current[1][5] = [[$depX, $depY, DistanceManhattan($depX, $depY, $arrX, $arrY), "NULL", "NULL"]], $path
Global $vois1 = $current, $vois2 = $current, $vois3 = $current, $vois4 = $current

$map[0][2] = 1
$map[1][2] = 1
$map[2][2] = 1
$map[3][1] = 1
$map[4][3] = 1


_ArrayAdd($openList, $current)
_ArrayDisplay($map)

Cherche($map,$openList,$closedList,$current)


func Cherche(ByRef $carte, ByRef $listeOuverte, ByRef $listeFermee, ByRef $courrant )
    if UBound($openList)>0 Then

        $openList = classeList($openList)

        $courrant[0][0] = $listeOuverte[0][0]
        $courrant[0][1] = $listeOuverte[0][1]
        $courrant[0][2] = $listeOuverte[0][2]
        $courrant[0][3] = $listeOuverte[0][3]
        $courrant[0][4] = $listeOuverte[0][4]
        If $courrant[0][1]<>$arrY or $courrant[0][0]<>$arrX Then
            _ArrayDelete($listeOuverte, 0)
            _ArrayAdd($listeFermee, $courrant)

            ;pour chaque voisins
            verif($vois1, $courrant[0][0] + 1, $courrant[0][1], $courrant[0][0], $courrant[0][1])
            verif($vois2, $courrant[0][0] - 1, $courrant[0][1], $courrant[0][0], $courrant[0][1])
            verif($vois3, $courrant[0][0], $courrant[0][1] + 1, $courrant[0][0], $courrant[0][1])
            verif($vois4, $courrant[0][0], $courrant[0][1] - 1, $courrant[0][0], $courrant[0][1])

            Cherche($carte,$listeOuverte,$listeFermee,$courrant)
        EndIf


    EndIf
    Return


EndFunc



If $current[0][0] <> $arrX and $current[0][1] <> $arrY Then
    MsgBox(0, "", "aucun chemin n'a été trouvé")
Else
    $path = RefaisLechemin($closedList)

    $path = inverseTab($path)

    For $i = 0 To UBound($path) - 1
        $map[$path[$i][1]][$path[$i][0]] = "X"
    Next
    $map[$arrY][$arrX] = "X"
    $map[$depY][$depX] = "X"
    _ArrayDisplay($map)
    _ArrayDisplay($path)

EndIf


Func RefaisLechemin($list)
    $currX = $list[UBound($list) - 1][3]
    $currY = $list[UBound($list) - 1][4]
    Local $chemin[0][2], $index = 99, $node[1][2] = [[$list[UBound($list) - 1][0], $list[UBound($list) - 1][1]]]
    _ArrayAdd($chemin, $node)

    While $index > 0
        $index = retourneIndex($closedList, $currX, $currY)
        If $index <> -1 Then
            $node[0][0] = $list[$index][0]
            $node[0][1] = $list[$index][1]
            _ArrayAdd($chemin, $node)
            $currX = $list[$index][3]
            $currY = $list[$index][4]
        EndIf
    WEnd
    _ArrayAdd($chemin, $node)

    Return $chemin
EndFunc   ;==>RefaisLechemin

Func retourneIndex($list, $x, $y)
    For $i = 0 To UBound($list) - 1
        If $list[$i][0] = $x And $list[$i][1] = $y Then Return $i
    Next

    Return -1
EndFunc   ;==>retourneIndex


Func DistanceManhattan($xa, $ya, $xb, $yb)
    Return Abs($xb - $xa) + Abs($yb - $ya)
EndFunc   ;==>DistanceManhattan

Func classeList($list)
    Local $tmp, $tmp2, $tmp3, $tmp4, $tmp5
    For $i = 0 To UBound($list) - 1
        For $j = $i + 1 To UBound($list) - 1
            If $list[$i][2] > $list[$j][2] Then
                $tmp = $list[$i][4]
                $tmp2 = $list[$i][3]
                $tmp3 = $list[$i][2]
                $tmp4 = $list[$i][1]
                $tmp5 = $list[$i][0]
                $list[$i][4] = $list[$j][4]
                $list[$i][3] = $list[$j][3]
                $list[$i][2] = $list[$j][2]
                $list[$i][1] = $list[$j][1]
                $list[$i][0] = $list[$j][0]
                $list[$j][4] = $tmp
                $list[$j][3] = $tmp2
                $list[$j][2] = $tmp3
                $list[$j][1] = $tmp4
                $list[$j][0] = $tmp5
            EndIf
        Next
    Next

    Return $list
EndFunc   ;==>classeList
Func verif($voisin, $x, $y, $xParent, $yParent)
    If $y < UBound($map) And $x < UBound($map, 2) And $y >= 0 And $x >= 0 Then
        If $map[$y][$x] <> 1 And Not _Search($closedList, $x, $y) Then
            $voisin[0][0] = $x
            $voisin[0][1] = $y
            $voisin[0][2] = DistanceManhattan($x, $y, $arrX, $arrY)
            $voisin[0][3] = $xParent
            $voisin[0][4] = $yParent
            _ArrayAdd($openList, $voisin)
        EndIf
    EndIf

EndFunc   ;==>verif
Func _Search($list, $x, $y)
    For $i = 0 To UBound($list) - 1
        If $list[$i][0] = $x And $list[$i][1] = $y Then Return 1
    Next

    Return 0
EndFunc   ;==>_Search

Func inverseTab($tab)
    Local $tmp, $tmp1
    Switch Mod(UBound($tab), 2)
        Case 0
            For $i = 0 To UBound($tab) / 2
                $tmp = $tab[$i][0]
                $tmp1 = $tab[$i][1]
                $tab[$i][0] = $tab[UBound($tab) - 1 - $i][0]
                $tab[$i][1] = $tab[UBound($tab) - 1 - $i][1]
                $tab[UBound($tab) - 1 - $i][0] = $tmp
                $tab[UBound($tab) - 1 - $i][1] = $tmp1
            Next
        Case Else
            For $i = 0 To (UBound($tab) - 1) / 2
                $tmp = $tab[$i][0]
                $tmp1 = $tab[$i][1]
                $tab[$i][0] = $tab[UBound($tab) - 1 - $i][0]
                $tab[$i][1] = $tab[UBound($tab) - 1 - $i][1]
                $tab[UBound($tab) - 1 - $i][0] = $tmp
                $tab[UBound($tab) - 1 - $i][1] = $tmp1
            Next
    EndSwitch

    Return $tab
EndFunc   ;==>inverseTab