Algorithme a*
Description
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).
Petite chose:
N'oublions pas de mirc reste mirc, et que cet algo aurait du mal a marcher si il y avait dans un jeu par exemple 4 intelligences artificielles cherchant leur chemin en même temps, et/ou si les grilles utilisées sont trop grandes.
Pour accélérer les choses, il est possible de définir certaines cases comme étant des points intermédiaires entre la position de départ et celle d'arrivée.
Ainsi au lieu de chercher par ex le chemin de 1 a 100 sur une grille 10 * 10, cherchez d'abord le chemin de 1 a 30 puis de 30 a 60 etc...
Ainsi il serait tout a fait possible que plusieures ia agissent en même temps avec un temps de calcul raisonnable.
Il faut bien sur placer ces points intermédiaires de manière intelligente, sous peine de voir votre ia faire de drôles de parcours.
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).
Source / Exemple :
;zip /* le zip contient un fichier lvl.txt ou chaque ligne est une case (de poid 0 ou 1) il y a un exemple avec ce fichier. Pour l'exécuter, placer le fichier .txt a la racine de mirc et taper la commande /test_astar on peut changer les pos de depart et d'arrivée en changeant les valeurs à ces lignes dans la methode /test_astar: var %deb 22 var %fin 120 (il faut bien sur que ces val soit dans l'intervalle 1 -> taille de la grille)
- /
Conclusion :
Petite chose:
N'oublions pas de mirc reste mirc, et que cet algo aurait du mal a marcher si il y avait dans un jeu par exemple 4 intelligences artificielles cherchant leur chemin en même temps, et/ou si les grilles utilisées sont trop grandes.
Pour accélérer les choses, il est possible de définir certaines cases comme étant des points intermédiaires entre la position de départ et celle d'arrivée.
Ainsi au lieu de chercher par ex le chemin de 1 a 100 sur une grille 10 * 10, cherchez d'abord le chemin de 1 a 30 puis de 30 a 60 etc...
Ainsi il serait tout a fait possible que plusieures ia agissent en même temps avec un temps de calcul raisonnable.
Il faut bien sur placer ces points intermédiaires de manière intelligente, sous peine de voir votre ia faire de drôles de parcours.
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.