Я успешно реализовал поиск путей A * в C #, но он очень медленный, и я не понимаю, почему. Я даже пытался не сортировать список openNodes, но он все тот же.
Карта имеет размер 80x80, и в ней 10-11 узлов.
Я взял псевдокод отсюда Википедия
И это моя реализация:
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;
}Вот эвристика, которую я использую:
private static double GetManhattanHeuristic(PGNode mStart, PGNode mEnd)
{
return Math.Abs(mStart.X - mEnd.X) + Math.Abs(mStart.Y - mEnd.Y);
}Что я делаю неправильно? Целый день я продолжаю смотреть на один и тот же код.
Ответы:
Я вижу три вещи, одну неправильную, две подозрительные.
1) Вы сортируете на каждой итерации. Не. Либо используйте приоритетную очередь, либо, по крайней мере, выполните линейный поиск, чтобы найти минимум. Вам на самом деле не нужно весь список сортировать все время!
2) openNodes.Contains (), вероятно, работает медленно (не уверен насчет специфики C #'s List, но я уверен, что он выполняет линейный поиск). Вы можете добавить флаг к каждому узлу и сделать это в O (1).
3) GetNeighborNodes () может быть медленным.
источник
В дополнение к уже высказанному замечанию, что вы должны использовать кучу приоритетов, вы неправильно поняли эвристику. У тебя есть
if (isCostBetter) { ... сосед. H = GetManhattanHeuristic (текущий, сосед); }Но эвристика должна быть оценкой расстояния до места назначения. Вы должны установить его один раз, когда вы впервые добавляете соседа:if (openNodes.Contains (сосед) == ложь) { сосед. H = GetHeuristic (сосед, mEnd); ... }И, как еще один дополнительный момент, вы можете упростить A *, отфильтровывая непроходимые узлы в
GetNeighbourNodes().источник
Мета-ответ: вы никогда не должны просто тратить день на разглядывание кода в поисках проблем с производительностью. Пять минут с профилировщиком покажут вам, где именно находятся узкие места. Вы можете скачать бесплатный журнал большинства профилировщиков и подключить его к своему приложению за несколько минут.
источник
Не понятно, что вы сравниваете, когда сравниваете F разных узлов. Является ли F свойством, определенным как G + H? Должен быть. (Side-rant: Это пример того, почему принцип единого доступа - это дерьмо.)
Более важно то, что вы сортируете узлы каждый кадр. A * требует использования очереди приоритетов , которая позволяет эффективно - O (lg n) - сортировать вставку одного элемента и набора, который позволяет быстро проверять наличие закрытых узлов. Как вы написали алгоритм, у вас есть O (n lg n) вставка + сортировка, которая увеличивает время выполнения до бесполезных пропорций.
(Вы можете получить O (n) insert + sort, если C # имеет хороший алгоритм сортировки. Это все еще слишком много. Используйте очередь с реальным приоритетом.)
источник
http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
Вы используете «ручное расстояние». Это почти всегда плохая эвристика. Кроме того, глядя на эту информацию со связанной страницы, вы можете догадаться, что ваша эвристика ниже реальной стоимости.
источник
В дополнение к другим основным ответам (которые, несомненно, более важны, чем это предложение), еще одной оптимизацией является изменение закрытого «списка» в своего рода хэш-таблицу. Вам не нужно, чтобы это была упорядоченная коллекция, просто чтобы иметь возможность быстро добавлять значения и быстро видеть, существуют ли они в коллекции.
источник
Ваша стоимость и ваша эвристика должны иметь отношения. Должно быть подсказка, что H рассчитывается в двух разных точках, но никогда не используется.
источник