Я попытался интегрировать JPS в свой алгоритм A *, но производительность упала. Читая документацию и примеры в GitHub, в настоящее время не понимаю, почему он работает медленно. Что нужно исправить при проверке или добавлении в некоторые списки? Возможно, я не понимал всего смысла этого алгоритма.
Вот моя модифицированная функция Astar:
public List<PathFinderNode> FindPath(Point start, Point end, List<Point> ResultPoints)
{
PathFinderNode parentNode;
bool found = false;
int gridX = mGrid[0].Count - 1;//horizontal size of grid
int gridY = mGrid.Count - 1; //vertical size of grid
mStopped = false;
mOpen.Clear();
mClose.Clear();
parentNode.G = 0;
parentNode.H = mHEstimate; //Equals 2
parentNode.F = parentNode.G + parentNode.H;
parentNode.X = start.X;
parentNode.Y = start.Y;
parentNode.PX = parentNode.X;
parentNode.PY = parentNode.Y;
mOpen.Push(parentNode); //Add a ParentNode First
while (mOpen.Count > 0)
{
parentNode = mOpen.Pop();
if (parentNode.X == end.X && parentNode.Y == end.Y)
{
mClose.Add(parentNode);
found = true;
break;
}
if (mClose.Count > mSearchLimit)
{
mStopped = true;
return null;
}
//Checking Neibours
for (int i = 0; i < 4; i++)
{
PathFinderNode newNode;
newNode.X = parentNode.X + direction[i, 0];
newNode.Y = parentNode.Y + direction[i, 1];
var tmpXY = jump(newNode.X, newNode.Y, parentNode.X, parentNode.Y, start,end); //doing a jump action
if (tmpXY[0] != -1) //if jump returns more than -1
{
int newG;
newNode.X = tmpXY[0];
newNode.Y = tmpXY[1];
newG = parentNode.G + (-1) * mGrid[newNode.Y][newNode.X];
if (newG == parentNode.G)
{
continue;
}
int foundInOpenIndex = -1;
for (int j = 0; j < mOpen.Count; j++) //openList check
{
if (mOpen[j].X == newNode.X && mOpen[j].Y == newNode.Y)
{
foundInOpenIndex = j;
break;
}
}
if (foundInOpenIndex != -1 && mOpen[foundInOpenIndex].G <= newG)
continue;
int foundInCloseIndex = -1;
for (int j = 0; j < mClose.Count; j++) //ClosedListCheck
{
if (mClose[j].X == newNode.X && mClose[j].Y == newNode.Y)
{
foundInCloseIndex = j;
continue;
}
}
if (foundInCloseIndex != -1 && mClose[foundInCloseIndex].G <= newG)
continue;
newNode.PX = parentNode.X;
newNode.PY = parentNode.Y;
newNode.G = newG;
newNode.H = mHEstimate * (Math.Abs(newNode.X - end.X) + Math.Abs(newNode.Y - end.Y)); //Manhattan
newNode.F = newNode.G + newNode.H;
mOpen.Push(newNode);
}
}
mClose.Add(parentNode);
}
if (found)
{
PathFinderNode fNode = mClose[mClose.Count - 1];
for (int i = mClose.Count - 1; i >= 0; i--)
{
if (fNode.PX == mClose[i].X && fNode.PY == mClose[i].Y || i == mClose.Count - 1)
{
fNode = mClose[i];
ResultPoints.Add(new Point(fNode.X * 10, fNode.Y * 10));
}
else
mClose.RemoveAt(i);
}
mStopped = true;
return mClose;
}
mStopped = true;
return null;
}
Да, самая медленная часть после запуска поиска перехода в примере кода, до интеграции JPS производительность от одной точки до другой на карте [100x100] заняла 0,100 с, после этого потребуется примерно секунда
Вы можете использовать тип коллекции, который больше подходит для частого удаления элементов, например LinkedList<>.
@ itsme86 Я использую этот раствор для удаления предметов github.com/BlueRaja/High-Speed-Priority-Queue-for-C-Sharp/tr ee /… работает быстро
Да, было бы. :)
Вы должны сообщить нам, где вы обнаружили проблемы. Идея в том, чтобы показать, какое исследование вы провели, чтобы люди не повторяли работу без причины.
@jdv Я обнаружил проблему с различиями при проверке закрытых и открытых списков после запуска JPS. Список чек такой же, как в astar, или нет? Большое спасибо
Как выглядит ваш график? JPS работает быстрее только в 2D-сетках с большими открытыми площадями; если это что-то вроде лабиринта, JPS не принесет никакой пользы.
@ BlueRaja-DannyPflughoeft Моя карта - это 2-мерный массив размером [108; 192], у которого есть отмеченные специальными цифрами границы с отмеченными прямоугольниками, вот и все. Матрица большая, алгоритм должен работать очень быстро. Я проверил демку в Github)





Вы собрали какие-нибудь тесты? Какая часть медленная?