Algorithme de pathfinding a star (a*)

Soyez le premier à donner votre avis sur cette source.

Vue 45 099 fois - Téléchargée 3 498 fois

Description

A Star (A*) Algorithme C# - Pathfinding

A* est un algorithme de type pathfinding. C'est à dire que c'est un algorithme qui est capable de trouver un chemin entre deux points, en prenant en compte certaines contraintes. Il existe plusieurs algorithmes de type pathfinding, mais AStar est un des meilleurs en termes de simplicité, performance et ressource.

Presque tous les jeux récents utilisent ce genre d'algorithme (avec bien entendu des améliorations faites maison). Pensez, par exemple, à un jeu où l'ordinateur qui est votre adversaire doit déplacer des unités: il doit les amener d'un point de la map à un autre, en respectant certaines contraintes telles que des unités ennemies, des montagnes où les unités avancent moins vites, peut-être des ruisseaux, etc.

A* est capable de prendre en compte ces différentes contraintes et de calculer le chemin le plus court pour aller de A à B. Le net grouille d'informations qui explique le fonctionnement (assez simple) de cet algorithme, je ne vais donc pas le réexpliquer ici. Vous trouverez néamoins un fichier html qui décrit de manière très simple le fonctionnement (j'ai implémenté l'algorithme grâce à ce document que j'ai trouvé sur le web).

La solution contient trois projets: un projet library qui contient A Star (A*) à proprement parlé, un autre qui contient les classes pour représenter graphiquement le résultat de l'algorithme (cf. capture) et un projet Windows qui utilise les deux autres projets pour qu'on puisse tester.

J'ai rajouté également des maps au projet pour qu'on puisse voir le résultat instantanément. Dans le cas de la map "laby" par exemple, vous verrez des cases bleues et rouges. Ces cases représentent des contraintes, c'est à dire qu'elles ont une certaine pondérations (x2 pour la case bleue, x5 pour la case rouge). Autrement dit, l'algorithme va calculer le chemin le plus adapté en partant du principe que s'il passe sur une case rouge ça lui prendra 5x plus de temps que de passer sur une case normale (pour reprendre la comparaison ci-dessus, ça pourrait être l'équivalent d'un passage dans du sable où les unités sont ralenties).

Il est naturellement possible d'améliorer ce projet, par exemple en gérant les déplacements diagonaux, en prenant en compte des contraintes plus complexes, en améliorant la rapidé de l'algorithme AStar, etc.
Le projet qui implémente l'algo A Star est donc pratiquement prêt à l'emplois tel quel, suffit de le rajouter à votre solution...

N'hésitez pas à soumettre vos remarques, je tâcherai de les prendre en compte dans une future version.

Source / Exemple :


public List<MapPoint> CalculateBestPath()
        {
            Node.Map = this._map;
            Node startNode = new Node(null, this._map.StartPoint);
            this._open.Add(startNode);

            while (this._open.Count > 0)
            {
                Node best = this._open.RemoveFirst();   // This is the best node
                if (best.MapPoint == _map.EndPoint)     // We are finished
                {
                    List<MapPoint> sol = new List<MapPoint>(); // The solution
                    while (best.Parent != null)
                    {
                        sol.Add(best.MapPoint);
                        best = best.Parent;
                    }
                    return sol; // Return the solution when the parent is null (the first point)
                }
                this._close.Add(best);
                this.AddToOpen(best, best.GetPossibleNode());
            }
            // No path found
            return null;
        }

Conclusion :


Remarquez qu'au niveau du Control qui s'occupe de représenter la map en cours, il y a actuellement un petit bug avec les threads que je n'ai pas encore réussi à résoudre, mais j'espère corriger dans une prochaine version.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

notavelido
Messages postés
2
Date d'inscription
vendredi 13 mars 2009
Statut
Membre
Dernière intervention
25 janvier 2010

Re-Bonjour,
Et merci pour la réponse rapide ;-)

Bonne fin de journée
cs_Bidou
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Modérateur
Dernière intervention
20 juin 2013
44
Bonjour,
Une fois le zip téléchargé et extrait, ouvrir la solution et sélectionner le bon projet comme projet de démarrage (AStarTester). C'est tout.
notavelido
Messages postés
2
Date d'inscription
vendredi 13 mars 2009
Statut
Membre
Dernière intervention
25 janvier 2010

Bonjour à tous,
Ce programme semble des plus intéressant et pourrait vraiment m'aider à la réalisation d'un de mes projets, cela dit j'ai un petit problème. Quand j'essaie de lancer la solution, une erreur survient en me disant que: "Le fichier projet ou le site Web a été déplacé ou ne se trouve pas sur mon ordinateur."
Quelqu'un saurait-il comment pallier à ce problème?

En vous remerciant d'avance
sebmafate
Messages postés
4936
Date d'inscription
lundi 17 février 2003
Statut
Modérateur
Dernière intervention
14 février 2014
32
sympa... ca me ramène quelques années en arrière... à l'époque où j'apprenais le LISP :)
c'était sympa la fac :p
cs_Bidou
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Modérateur
Dernière intervention
20 juin 2013
44
Merci pour la note ;-)
Le but est effectivement de présenter l'algorithme de manière agréable et comme je l'ai précisé il s'agit d'une version de base qui peut (qui doit) être améliorée. En tout cas merci pour les différentes idées, j'en tiendrai certainement compte pour les prochaines versions!

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.