Algorithme de pathfinding a star (a*)
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.
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.
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
- Algorithme de pathfinding a star (a*)
- Code maroc algorithme - Forum Visual Basic 6
- Algorithme d affectation - Forum Java
- Recherche d'un code ou de l'algorithme - Forum C / C++ / C++.NET
- Générateur nom star wars ✓ - Forum C# / .NET
- Conversion algorithme en code vba - Forum VB.NET
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.