Обновите A * для поиска точки перехода

Я попытался интегрировать 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;
}

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

user1531971 04.07.2018 17:22

Да, самая медленная часть после запуска поиска перехода в примере кода, до интеграции JPS производительность от одной точки до другой на карте [100x100] заняла 0,100 с, после этого потребуется примерно секунда

Василий Пупкин 04.07.2018 17:23

Вы можете использовать тип коллекции, который больше подходит для частого удаления элементов, например LinkedList<>.

itsme86 04.07.2018 17:28

@ itsme86 Я использую этот раствор для удаления предметов github.com/BlueRaja/High-Speed-Priority-Queue-for-C-Sharp/tr‌ ee /… работает быстро

Василий Пупкин 04.07.2018 17:29

Да, было бы. :)

itsme86 04.07.2018 17:30

Вы должны сообщить нам, где вы обнаружили проблемы. Идея в том, чтобы показать, какое исследование вы провели, чтобы люди не повторяли работу без причины.

user1531971 04.07.2018 17:32

@jdv Я обнаружил проблему с различиями при проверке закрытых и открытых списков после запуска JPS. Список чек такой же, как в astar, или нет? Большое спасибо

Василий Пупкин 04.07.2018 17:41

Как выглядит ваш график? JPS работает быстрее только в 2D-сетках с большими открытыми площадями; если это что-то вроде лабиринта, JPS не принесет никакой пользы.

BlueRaja - Danny Pflughoeft 04.07.2018 17:42

@ BlueRaja-DannyPflughoeft Моя карта - это 2-мерный массив размером [108; 192], у которого есть отмеченные специальными цифрами границы с отмеченными прямоугольниками, вот и все. Матрица большая, алгоритм должен работать очень быстро. Я проверил демку в Github)

Василий Пупкин 04.07.2018 17:44
Стоит ли изучать PHP в 2026-2027 годах?
Стоит ли изучать PHP в 2026-2027 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
9
521
0

Другие вопросы по теме