J'ai réussi à implémenter A * pathfinding en C # mais c'est très lent, et je ne comprends pas pourquoi. J'ai même essayé de ne pas trier la liste openNodes mais c'est toujours la même chose.
La carte est de 80x80, et il y a 10-11 nœuds.
J'ai pris le pseudocode d'ici Wikipedia
Et voici ma mise en œuvre:
public static List<PGNode> Pathfind(PGMap mMap, PGNode mStart, PGNode mEnd)
{
mMap.ClearNodes();
mMap.GetTile(mStart.X, mStart.Y).Value = 0;
mMap.GetTile(mEnd.X, mEnd.Y).Value = 0;
List<PGNode> openNodes = new List<PGNode>();
List<PGNode> closedNodes = new List<PGNode>();
List<PGNode> solutionNodes = new List<PGNode>();
mStart.G = 0;
mStart.H = GetManhattanHeuristic(mStart, mEnd);
solutionNodes.Add(mStart);
solutionNodes.Add(mEnd);
openNodes.Add(mStart); // 1) Add the starting square (or node) to the open list.
while (openNodes.Count > 0) // 2) Repeat the following:
{
openNodes.Sort((p1, p2) => p1.F.CompareTo(p2.F));
PGNode current = openNodes[0]; // a) We refer to this as the current square.)
if (current == mEnd)
{
while (current != null)
{
solutionNodes.Add(current);
current = current.Parent;
}
return solutionNodes;
}
openNodes.Remove(current);
closedNodes.Add(current); // b) Switch it to the closed list.
List<PGNode> neighborNodes = current.GetNeighborNodes();
double cost = 0;
bool isCostBetter = false;
for (int i = 0; i < neighborNodes.Count; i++)
{
PGNode neighbor = neighborNodes[i];
cost = current.G + 10;
isCostBetter = false;
if (neighbor.Passable == false || closedNodes.Contains(neighbor))
continue; // If it is not walkable or if it is on the closed list, ignore it.
if (openNodes.Contains(neighbor) == false)
{
openNodes.Add(neighbor); // If it isn’t on the open list, add it to the open list.
isCostBetter = true;
}
else if (cost < neighbor.G)
{
isCostBetter = true;
}
if (isCostBetter)
{
neighbor.Parent = current; // Make the current square the parent of this square.
neighbor.G = cost;
neighbor.H = GetManhattanHeuristic(current, neighbor);
}
}
}
return null;
}
Voici l'heuristique que j'utilise:
private static double GetManhattanHeuristic(PGNode mStart, PGNode mEnd)
{
return Math.Abs(mStart.X - mEnd.X) + Math.Abs(mStart.Y - mEnd.Y);
}
Qu'est-ce que je fais mal? C'est une journée entière que je continue à regarder le même code.
Réponses:
Je vois trois choses, une mauvaise, deux suspectes.
1) Vous triez à chaque itération. Non. Soit utiliser une file d'attente prioritaire, soit tout au moins faire une recherche linéaire pour trouver le minimum. Vous n'avez en fait pas besoin que la liste entière soit triée à tout moment!
2) openNodes.Contains () est probablement lent (je ne suis pas sûr des spécificités de la liste de C #, mais je parie qu'il fait une recherche linéaire). Vous pouvez ajouter un indicateur à chaque nœud et le faire dans O (1).
3) GetNeighborNodes () peut être lent.
la source
En plus du point déjà dit que vous devez utiliser un tas prioritaire, vous avez mal compris l'heuristique. Vous avez
if (isCostBetter) { ... neighbour.H = GetManhattanHeuristic (actuel, voisin); }Mais l'heuristique est censée être une estimation de la distance jusqu'à la destination. Vous devez le définir une fois, lorsque vous ajoutez le voisin pour la première fois:if (openNodes.Contains (voisin) == false) { Neighbour.H = GetHeuristic (Neighbour, mEnd); ... }Et comme autre point mineur, vous pouvez simplifier l'A * en filtrant les nœuds infranchissables
GetNeighbourNodes().la source
La méta-réponse: vous ne devriez jamais passer une journée à regarder le code à la recherche de problèmes de performances. Cinq minutes avec un profileur vous montreraient exactement où se trouvent les goulots d'étranglement. Vous pouvez télécharger une trace gratuite de la plupart des profileurs et la connecter à votre application en quelques minutes.
la source
Ce que vous comparez n'est pas clair lorsque vous comparez le F de différents nœuds. F est-elle une propriété définie comme G + H? Ça devrait être. (Side-rant: C'est un exemple de la raison pour laquelle le principe d'accès uniforme est de la merde.)
Plus important cependant, vous triez à nouveau les nœuds à chaque image. A * demande l'utilisation d'une file d'attente prioritaire , qui permet l'insertion efficace - O (lg n) - triée d'un seul élément, et d'un ensemble, qui permet des vérifications rapides des nœuds fermés. Lorsque vous avez écrit l'algorithme, vous avez O (n lg n) insertion + tri, ce qui augmente le temps d'exécution à des proportions inutiles.
(Vous pouvez obtenir une insertion + tri O (n) si C # a un bon algorithme de tri. C'est encore trop. Utilisez une vraie file d'attente prioritaire.)
la source
http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
Vous utilisez «Manhatten distance». C'est presque toujours une mauvaise heuristique. De plus, en regardant ces informations sur la page liée, vous pouvez deviner que votre heuristique est inférieure au coût réel.
la source
En plus des autres meilleures réponses (qui sont sans aucun doute plus importantes que cette suggestion), une autre optimisation consiste à changer la «liste» fermée en une sorte de table de hachage. Vous n'avez pas besoin que ce soit une collection ordonnée, juste pour pouvoir ajouter rapidement des valeurs et voir rapidement si elles existent dans la collection.
la source
Votre coût et votre besoin heuristique doivent avoir une relation. Cela devrait être un indice que H est calculé à deux endroits différents mais n'a jamais été consulté.
la source