Algorithme a*

Soyez le premier à donner votre avis sur cette source.

Vue 10 767 fois - Téléchargée 327 fois

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).

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.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

cs_wims
Messages postés
2466
Date d'inscription
vendredi 23 juillet 2004
Statut
Membre
Dernière intervention
1 août 2010
1 -
Ah ouais carrément quoi !? (je reposterai quand j'aurais testé, c'étais histoire de marqué le coup!) ça a l'air bien, mais difficile pour ceux qui débute :o
cs_PaDa
Messages postés
1804
Date d'inscription
mardi 15 juillet 2003
Statut
Membre
Dernière intervention
22 septembre 2009
1 -
Wow, très intéressant ;-)
J'avais implémenté Dijkstra pour un cours en matlab, puis pour le défi de l'ami Wims sur scriptsdb.org, mais c'est extrêmement lent parce que récursif et "exhaustif", alors que ton truc est vraiment très efficace dès lors qu'on sait où aller et que notre map est pas trop tordu (cf http://fr.wikipedia.org/wiki/Algorithme_A*).
Je n'ai pas regardé encore l'implémentation en détail, mais en tout cas félicitation pour avoir tout commenté, ça rend la lecture beaucoup plus aisée ! Ca vaut bien un 10/10 rien que pour l'originalité !
RCA ArKanis
Messages postés
1287
Date d'inscription
mercredi 21 avril 2004
Statut
Membre
Dernière intervention
21 février 2009
-
très sympathique :)
moins d'une seconde (700ms) pour trouver le chemin et l'afficher

Tu devrais juste remplacer ta ligne 4 par ça : var %file $scriptdir(lvl.txt), même si ça n'intervient que pour le test. Ca pourrait permettre à plus de personnes de le tester :p

Les aliases sont expliqués et leur syntaxe donnée, c'est agréable.
L'originalité et le résultat sont là. Il en est de même pour la propreté du code.
Donc, pour résumer, bravo :D
CsDarkman
Messages postés
24
Date d'inscription
samedi 12 avril 2008
Statut
Membre
Dernière intervention
16 mai 2008
-
interessant ta bien fai j'ai testé tn code et il fonctonne bien
voila plus 10 en attendant tn prochain code :D

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.