Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > .NET > C# (си шарп)
Регистрация

Восстановить пароль
Повторная активизация e-mail

Ответ
 
Опции темы
Старый 10.07.2018, 14:24   #1
Alex_detect
Новичок
 
Регистрация: 10.07.2018
Сообщений: 1
Репутация: 10
По умолчанию Алгоритм Astar периодически падает

Добрый день, уважаемые форумчане! Кто-нибудь имел дела с алгоритмом Astar? В качестве номинала выбрал такое решение https://www.codeguru.com/csharp/csha...PathFinder.htm, которое показалось мне самым простым и эффективным. Повесил приоритетную очередь из библиотеки C5. Но столкнулся с проблемами, в том числе стокового алгоритма. Имея такую карту
Map.jpg

по -1 гуляет алгоритм (ниже прикрепляю), но в каких-то случаях он работает коряво (лимит точек превышает SearchLimit в 2000 значений, для карты 180x94 очень много). Буду благодарен, если поможете разобраться.

Код:

public List<Point> FindPath(Point start, Point end, List<Point> ResultPoints)
        {
            PathFinderNode parentNode = new PathFinderNode();
            bool found  = false;
            int  gridX  = mGrid[0].Count-1;
            int  gridY  = mGrid.Count-1;
            mOpen = new IntervalHeap<PathFinderNode>();
            mClose.Clear();
            parentNode.G         = 0;
            parentNode.H         = 0/*mHEstimate*/;
            parentNode.F         = 0/*parentNode.G + parentNode.H*/;
            parentNode.X         = start.X;
            parentNode.Y         = start.Y;
            parentNode.PX        = parentNode.X;
            parentNode.PY        = parentNode.Y;
            mOpen.Add(parentNode);
            mClose.Add(parentNode);
            while(mOpen.Count > 0 )
            {
                parentNode = mOpen.DeleteMin();
                
                if (parentNode.X == end.X && parentNode.Y == end.Y)
                {
                    mClose.Add(parentNode);
                    found = true;
                    break;
                }

                if (mClose.Count > mSearchLimit)
                {
                    return null;
                }

                if (mPunishChangeDirection)
                { 
                    mHoriz = (parentNode.X - parentNode.PX);
                }

                
                //Calculating Neighbours
                for (int i=0; i< 4; i++)
                {
                    PathFinderNode newNode = new PathFinderNode();
                    newNode.X = parentNode.X + direction[i,0];
                    newNode.Y = parentNode.Y + direction[i,1];

                    if (newNode.X < 0 || newNode.Y < 0 || newNode.X > gridX || newNode.Y > gridY)
                    { 
                        continue;
                    }

                    if (mGrid[newNode.Y][newNode.X] < -1 || mGrid[newNode.Y][newNode.X] == int.MaxValue) //Ставим препятствия
                    {
                        continue;
                    }

                    int newG = parentNode.G - mGrid[newNode.Y][newNode.X]; //так как ходим вверх/вниз, и пустые ячейка на карте равны -1, то просто вычитаем, для сложения
                    
                    if (newG == parentNode.G)
                    {
                        continue;
                    }

                    if (mPunishChangeDirection)
                    {
                        if ((newNode.X - parentNode.X) != 0)
                        {
                            if (mHoriz == 0)
                                newG += 20;
                        }
                        if ((newNode.Y - parentNode.Y) != 0)
                        {
                            if (mHoriz != 0)
                                newG += 20;

                        }
                    }
                    
                    /* 
                     int     foundInOpenIndex = -1;
                     for(int j=0; j<mOpen.Count; j++)
                     {
                         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++)
                    {
                        if (mClose[j].X == newNode.X && mClose[j].Y == newNode.Y)
                        {
                            foundInCloseIndex = j;
                            break;
                        }
                    }

                    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)); //Манхэттен
                        newNode.F       = newNode.G + newNode.H;
                        mOpen.Add(newNode);
                }
                mClose.Add(parentNode);
            }

Alex_detect вне форума   Ответить с цитированием
Ответ

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Зависает ноутбук(периодически) maya2 Железо 3 04.06.2015 11:15
Зависает ноутбук(периодически) maya2 Операционные системы общие вопросы 0 20.05.2015 22:38
Периодически щёлкает жёсткий диск Cruzel Железо 5 30.11.2013 07:11
Периодически Access violation в XE3 furstenberg Общие вопросы Delphi 9 28.06.2013 23:58
Периодически запускать програму. Chudo4258 Помощь студентам 9 05.03.2010 13:02


16:43.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru