(tutoriel déjà paru sur mon forum, je ne cite pas son nom).
Bonjour à tous.
Ce tutoriel va porter sur le pathfinding.
Mais tout d'abord, qu'est-ce que c'est ?
Définition et portée
La recherche de chemin, couramment appelée pathfinding, est un problème d'intelligence artificielle très abordé dans la robotique et dans le botting. Il consiste à trouver comment se déplacer dans un environnement entre un point de départ et un point d'arrivée en prenant en compte différentes contraintes.
https://www.youtube.com/watch?v=Zf_ZRfJfE8c
Le pathfinding est généralement le casse-tête des codeurs de bots de combat, en particulier pour Dofus 2.0 dont le client doit retracer absolument tous les déplacements faits par le personnage botté. Si un seul des paquets de déplacement est mal formé, avec par exemple un saut de cases ou l'oubli d'une case dans le parcours, alors le compte risque plusieurs heures de bannissement voire si récidive un bannissement définitif avec suppression de compte. Mieux vaut donc être préparé et connaitre parfaitement ses techniques.
Algorithmes de Pathfinding
Comme pour chaque problème de programmation, plusieurs algorithmes sont utilisables.
Pour le pathfinding, deux son très connus, le Dijkstra qui ne sera pas abordé dans ce tutoriel, et l'AStar, le plus facile à utiliser.
Si vous désirez un tutoriel sur le Dijkstra, consultez ce lien : http://www.aromath.net/Page.php?IDP=624&IDD=0
Pour les autres, on continue ;)
Compréhension de l'algorithme
Commençons par nous mettre en jambe, avec un pitit schéma de départ :
Loading Image
Comme vous pouvez le voir, la carte comporte 7x5 carreaux, soit 35 carreaux en tout.
En vert, c'est la case de départ du "personnage", et en rouge, c'est la case d'arrivée.
Les cases bleues sont des obstacles, on ne peut pas sauter par dessus, ni leur passer dessus.
Mettons-nous dans la "tête" de l'algorithme A*Star, et réfléchissons comme lui.
Vous devez trouver un moyen fiable de caractériser chaque case par une chaîne de caractère ou un nombre en particulier.
Les coordonnées restent le moyen le plus courant (ex "1;3")
AStar fonctionne avec deux variables principales :
- La variable de "liste ouverte"
- La variable de "liste fermée"
Cet algorithme a besoin donc de ces deux variables pour effectuer le pathfinding.
L'algorithme commence par ajouter la case de départ à la liste ouverte. (ex : $open_list &= "x;y", soit ici "2;3")
Puis, il identifie chacune des cases adjacentes à la case de départ, comme ceci :
Loading Image
Et il ajoute à la liste ouverte toute ses cases en indiquant leur parent et leur poids.
AaAh ! Hé là, qu'est-ce que c'est que le poids ? Et le parent ?T'en as même pas parlé !
Oups :oops: , pardon ^^
Le poids F est la somme de la distance parcourue pour arriver à ce point depuis la case de départ (poids G) et de celle de la distance de restant jusqu'au point d'arrivée (poids H).
Il y a deux manières de calculer les distances en AStar :
1) La distance Manhattan (très chiant)
Déplacement en diagonale : 14 points
Déplacement horizontal, vertical : 10 points
En clair, par exemple, le poids de la case de coordonnées (1;2) par rapport à la case de départ a pour poids:
(G+H)= [(Déplacement diagonale) + (5 cases en abscisses + 1 case en ordonnées)] = [14 + (5(10)+1(10))]= (14 + 60) = 74.
(si c'est pas clair, relisez plusieurs fois, ça va finir par rentrer).
1) La distance Euclidienne (fastoche)
C'est le calcul de distance dans un repère issu du théorème de Pythagore :
Pour une distance d'un point A de coordonnées 2:5 à un point B de coordonnées 6:8, on fait :
√{(xB-xA)²+(yB-yA²)}
√: racine carrée
(2;3)
Par exemple, pour la case B (1;2) avec A (2;3) case de départ et C (6;3) case d'arrivée :
G = √{(xB-xA)²+(yB-yA)²} = √2
H = √{(xC-xB)²+(yC-yB)²} = √9
F = G+H = √2+√9
Et le parent, c'est tout simplement la case de départ par rapport à la case adjacente.
Vous devez donc trouver un moyen d'ajouter chaque case dans la variable de la liste ouverte, en vous débrouillant pour trouver une chaîne de caractères comprenant toutes ses caractéristiques (exemple, un système de blocks avec une variable string "[x;y/PoidsF/coordonnées_caseparente]").
Dès qu'il a terminé de calculer le poids de toutes les cases adjacentes, l'algorithme enlève la case de départ de la liste ouverte pour la mettre en liste fermée.
Puis l'algorithme choisit une case à étudier : ce sera la case adjacente à celle de départ qui a le poids le moins élevé.
Et on recommence avec cette case, en analysant ses cases adjacentes, etc...
Loading Image
Donc, on fait une boucle, et dès que une des cases à analyser est la case d'arrivée, l'algorithme s'arrête.
Et on reconstitue le chemin grâce aux cases parentes de la liste fermée.
Basique, non ?
Voila le schéma final :
Loading Image
Algorithme final
Voici donc l’algorithme final :
1) On ajoute la case de départ à la liste ouverte.
2) On ouvre une boucle Do-Until
a) On cherche la case avec le nombre F le plus petit dans la liste ouverte : c'est la case active
b) Puis on la met dans la liste fermée
c) Et pour chacune des huit cases adjacentes à la case active :
* Si la case est un obstacle ou est dans la liste fermée, on l'ignore.
* Si la case n'est pas dans la liste ouverte, ajoutez-la, en prenant soin de préciser son parent, la case actuelle. Puis on stocke le poids de la case.
* Si elle est déjà sur la liste ouverte, vérifiez si un nouveau G sera plus faible. S'il est plus faible, changez le parent de cette case pour la case courante, et recalculez les scores F et G.
d) Le script sort de la boucle si :
* Vous ajoutez la case d'arrivée à la liste fermée,
* Ou si la liste ouverte est vide (dans ce cas, il n'y a pas de solution).
3) Puis, reconstituez le chemin à partir des parents.
Il y a des données qu'on peut ne pas prendre en compte (par exemple les parents).
A vous de trouver la manière la plus simple de vous servir de cet algorithme.
Exemple de script en AutoIt :
J'ai développé un petit script de pathfinding avec distance euclidienne, adaptable en UDF assez facilement.
Il ne gère pas encore les faux paramètres, mais bon ce n'est pas vraiment nécessaire.
#include <Array.au3>
Global $end_pos[2] = [7, 2]
Global $xy[2] = [0, 4], $last
Global $path, $lastvar, $lowweight
Global $maplimit[2] = [7, 7] ;coordonnée_maximale x|coordonnée_maximale y
Global $mapbar[6] = ["2|1", "2|2", "2|3", "4|4", "5|1", "5|2"] ;coordonnées des cases obstacles
Global $barstring
_GetPath()
Func _GetPath()
Do
_Execute()
Until _IsEndPath()
MsgBox(0, "", $path)
EndFunc ;==>_GetPath
Func _IsEndPath()
If $xy[0] = $end_pos[0] And $xy[1] = $end_pos[1] Then
Return True
Else
Return False
EndIf
EndFunc ;==>_IsEndPath
Func _Execute()
$last = $xy
Global $coord[8] = ["", "", "", "", "", "", "", ""]
$coord[0] = ($xy[0] - 1) & "|" & $xy[1] ;gauche
$coord[1] = ($xy[0] + 1) & "|" & $xy[1] ;droite
$coord[2] = $xy[0] & "|" & ($xy[1] - 1) ;haut
$coord[3] = $xy[0] & "|" & ($xy[1] + 1) ;bas
$coord[4] = ($xy[0] + 1) & "|" & ($xy[1] + 1) ;diagonale droite basse
$coord[5] = ($xy[0] + 1) & "|" & ($xy[1] - 1) ;diagonale droite haute
$coord[6] = ($xy[0] - 1) & "|" & ($xy[1] - 1) ;diagonale gauche haute
$coord[7] = ($xy[0] - 1) & "|" & ($xy[1] + 1) ;diagonale gauche basse
For $i = 0 To 7
Global $x = _StringLeft($coord[$i], "|")
Global $y = _StringRight($coord[$i], "|")
If 0 <= $x And $x <= $maplimit[0] And 0 <= $y And $y <= $maplimit[1] Then
If Not _BlockedCase($x, $y) And Not _Crossed($x, $y) Then
$coord[$i] = $coord[$i] & "P" & _GetWeight($x, $y)
Else
$coord[$i] = $coord[$i] & "P" & (6 * 10 ^ 3)
EndIf
Else
$coord[$i] = $coord[$i] & "P" & (6 * 10 ^ 3)
EndIf
Next
$lastvar = $coord[0]
$lowweight = 0
For $i = 1 To 7
If Number(_StringRight($lastvar, "P")) > Number(_StringRight($coord[$i], "P")) Then
$lowweight = $i
$lastvar = $coord[$i]
EndIf
Next
$firstdub = _StringLeft($coord[$lowweight], "P")
$middub = StringSplit($firstdub, "|")
$xy[0] = $middub[1]
$xy[1] = $middub[2]
$path = $path & "|" & $xy[0] & ";" & $xy[1]
EndFunc ;==>_Execute
Func _Crossed($x, $y)
If StringInStr($path, $x & ";" & $y) Then
Return True
Else
Return False
EndIf
EndFunc ;==>_Crossed
Func _GetWeight($radx, $rady)
$calcrat = ($end_pos[0] - $radx) ^ 2 + ($end_pos[1] - $rady) ^ 2
$calcmid = Sqrt($calcrat)
$calxrat = (($xy[0] - $radx) ^ 2 + ($xy[1] - $rady) ^ 2)
$calxmid = Sqrt($calcrat)
Return ($calcmid + $calxmid)
EndFunc ;==>_GetWeight
Func _StringLeft($str, $limit)
$dstr = StringSplit($str, $limit)
Return $dstr[1]
EndFunc ;==>_StringLeft
Func _StringRight($str, $limit)
$dstr = StringSplit($str, $limit)
Return $dstr[2]
EndFunc ;==>_StringRight
Func _BlockedCase($xar, $yar)
_ArraySearch($mapbar, $xar & "|" & $yar)
If Not @error Then
Return True
Else
Return False
EndIf
EndFunc ;==>_BlockedCase
J'espère que vous avez tout compris.
Bonne chance pour appliquer cela à un script ;)