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