dimanche 29 mai 2016

A* Pathfind wrong checked tiles

I want to implement A* pathfind (C++ & Qt). this is my result: A* Pathfind by wrong checkings

as you can see, there are some wrong tiles that are checked (opened). in my image, red tiles are opened tiles and you can see there are some tiles inside the blue rectangle area that should not be checked because they are far from target. so if I want to have more than 250 pathfinder soldiers in my game, I must optimize soldiers calculations, so I want to know my bug and also some optimizing suggestions. here is my code:

struct asNode
{
        QPoint pos;
        QPoint parent;
        int g;
        int h;
        bool opened;
        bool closed;
        asNode() :
                pos(QPoint(0, 0)), parent(QPoint(-1, -1)), g(0), h(0), opened(false), closed(false)
        {}
        int F()
        {
                return g + h;
        }
        const int distance(const QPoint _Dest) const
        {
                int xd = _Dest.x() - pos.x();
                int yd = _Dest.y() - pos.y();

                // Euclidian Distance
                //int d=static_cast<int>(sqrt(xd*xd+yd*yd));

                // Manhattan distance
                int d = (abs(xd) + abs(yd))*10;
                // Chebyshev distance
                //int d=max(abs(xd), abs(yd));

                return(d);
        }
        bool hasParent()
        {
                return (parent != QPoint(-1, -1));
        }
};


class a_star
{
public:
    a_star(bool _Diagonal=false)
        {
                SetDigonal(_Diagonal);
        }
    void SetDigonal(bool _Value)
        {
                _diagnoal=_Value;
                neighborsLevels.clear();
                if(_diagnoal)
                {
                        neighborsLevels.push_back(QPoint(1,0));
                        neighborsLevels.push_back(QPoint(1,1));
                        neighborsLevels.push_back(QPoint(0,1));
                        neighborsLevels.push_back(QPoint(-1,1));
                        neighborsLevels.push_back(QPoint(-1,0));
                        neighborsLevels.push_back(QPoint(-1,-1));
                        neighborsLevels.push_back(QPoint(0,-1));
                        neighborsLevels.push_back(QPoint(1,-1));
                }
                else
                {
                        neighborsLevels.push_back(QPoint(1,0));
                        neighborsLevels.push_back(QPoint(0,1));
                        neighborsLevels.push_back(QPoint(-1,0));
                        neighborsLevels.push_back(QPoint(0,-1));
                }
        }
    std::list<QPoint> a_star_path_find(std::vector<std::vector<int> > _Grid, QPoint _StartPoint, QPoint _EndPoint)
        {
                //Grid item -1 is blocked tile,0 is movable tile
                std::list<QPoint> finalpath;
                
                const int n = _Grid.size();
                const int m = _Grid[0].size();
                asNode modelMap[n][m];
                std::list<asNode*> opened;
                auto current=&modelMap[_StartPoint.x()][_StartPoint.y()];
                current->pos=_StartPoint;
                current->g = 0;
                current->h = current->distance(QPoint(_EndPoint.x(),_EndPoint.y()));

                current->opened = true;
                opened.push_front(current);
                blueTiles.push_back(current->pos);
                while (!opened.empty())
                {
                        auto itr=opened.begin();
                        current = *(itr);
                        itr++;
                        while( itr!=opened.end())
                        {
                                if((*itr)->F()<current->F())
                                {
                                        current=*(itr);
                                }
                                itr++;
                        }
                        current->closed = true;
                        opened.remove(current);

                        if (current == &modelMap[_EndPoint.x()][_EndPoint.y()])
                        {
                                while (current->hasParent())
                                {
                                        QPoint newStep= current->pos;                                        
                                        finalpath.push_back(newStep);
                                         current = &modelMap[current->parent.x()][current->parent.y()];
                                }
                                std::reverse(finalpath.begin(), finalpath.end());
                                return finalpath;
                        }
                        for (int i = 0; i<neighborsLevels.size(); i++)
                        {
                                int newX = current->pos.x() + neighborsLevels[i].x();
                                int newY = current->pos.y() + neighborsLevels[i].y();
                                if (newX >= 0 && newX<n)
                                {
                                        if (newY >= 0 && newY<m)
                                        {
                                                if (modelMap[newX][newY].closed || _Grid[newX][newY]==-1)//Grid item -1 is blocked tile,0 is movable tile
                                                {
                                                        continue;
                                                }
                                                modelMap[newX][newY].h = modelMap[newX][newY].distance(_EndPoint);
                                                int gScore = current->g + ((newX - current->pos.x() == 0 || newY - current->pos.y() == 0) ? 10 : 14);
                                                if (!modelMap[newX][newY].opened || gScore<modelMap[newX][newY].g)
                                                {
                                                        modelMap[newX][newY].g = gScore;
                                                        modelMap[newX][newY].parent = current->pos;

                                                        if (!modelMap[newX][newY].opened)
                                                        {
                                                                modelMap[newX][newY].pos=QPoint(newX,newY);
                                                                modelMap[newX][newY].opened = true;
                                                                opened.push_front(&modelMap[newX][newY]);
                                                        }
                                                }
                                        }
                                }
                        }
                }
                return finalpath;
        }
private:
    bool _diagnoal;
    std::vector<QPoint> neighborsLevels;
};

thanks...

Aucun commentaire:

Enregistrer un commentaire