Salut,
Je vous poste ici une petite implémentation de l'algo A* (ou A star), un algorithme de recherche de chemin dans un graphe ou la première solution proposée est l'une des meilleures existantes.
C'est un code que j'ai fait il y a bien longtemps, et que j'ai essayé d'optimiser au max pour qu'il soit utilisable pour du temps réel.
Je voulais illustrer ce code en faisant un petit pacman, mais je n'en n'ai jamais eu la motivation.
Bref, cet algo prend en entrée une hashmap ou chaque item est un nombre représentant le poid de la case correspondante.
Exemple la hashmap TEST contient ces données : 1 2 2 4 5 1 8 5 4 2 0 1 2 5 4 0 4 5 (18 items)
On charge le chemin a l'aide de la methode /Astar_load
Elle prend en paramètre la hashmap et la taille en largeur et en hauteur de la grille
ex: /Astar_load TEST 6 3
La carte sera donc représentée comme en rectangle de 6 * 3 :
1 2 2 4 5 1
8 5 4 2 0 1
2 5 4 0 4 5
Les 0 représentent des obstacles, et plus le nombre est grand, plus le "chemin" est long.
Par exemple, on pourrait dire que des 1 représentent le sol, des 2 de l'eau ou l'on marcherait moins vite etc..
Des poids négatifs peuvent également être rentrés (on ira encore plus vite).
Une fois chargée avec /Astar_load, la méthode $Astar_find(position depart, position arrivée) retourne la suite de "cases" qu'il faut parcourir pour atteindre le plus vite la position d'arrivée en partant de la position de départ. Si il n'y a pas de solution, rien n'est retourné.
A noter que la position de départ et celle d'arrivée sont a donner en imaginant que la carte est "a plat", donc sur une seule ligne.
Pour voir la liste des cases a parcourir, on peut par exemple faire ceci:
var %res = $Astar_find(2, 15)
var %i = 1
while ($gettok(%res, %i, 32)) { echo -a Etape %i : case $v1 | inc %i }
Pour terminer correctement votre script, lorsque vous n'avez plus besoin d'utiliser l'algo, utilisez la commande /Astar_clear
Dernière chose, le chemin ne prend pas en compte les diagonales, mais si vous voulez en tenir compte, il suffit de modifier l'alias Astar_getNeighbors en rajoutant les tests de diagonales. (dans ce code je ne teste que si il y a des cases au dessus, en dessous, a gauche et a droite d'une certaine case).