ÎæÇÑÒãíÉ ÇáÈÍË A*:
åí ÎæÇÑÒãíÉ ÊÍÓÈ ÇáãÓÇÝÉ ÇáÃÞÕÑ ãä äÞØÉ Çáì äÞØÉ ÃÎÑì ÂÎÐÉ ÈÚíä ÇáÅÚÊÈÇÑ ÇáÍæÇÌÒ Ýí ØÑíÞåÇ æåí ÊÚÊÈÑ ãä ÃÝÖá ÇáÎæÇÑÒãíÇÊ Ýí åÐÇ ÇáãÌÇá .
æáÊÓåíá ÚãáíÉ ÇáÈÍË íÌÈ ÊÞÓíã ÇáãäØÞÉ Çæ ÇáÃÑÖíÉ ÇáÊí ÊÈÍË ÝíåÇ ÇáÎæÇÑÒãíÉ Çáì ãäÇØÞ æíÝÖá Çä Êßæä ãÑÈÚÉ æÇáÃãÑ ÑÇÌÚ Çáíß .
ÊÃÎÐ ÇáÚãáíÉ ÇæÞÇÊ ãÊÝÇæÊÉ ÍÓÈ Øæá ÇáãÓÇÑ æßËÑÉ ÇáÍæÇÌÒ æãæÇÖÚåÇ æáßäåÇ ãÚ Ðáß ÝÅäåÇ ÓÑíÚÉ ÌÏÇ æáÇÊÒíÏ Ýí ÇáÛÇáÈ Úä æÇÍÏ ãä ÇáÝ ãä ÇáËÇäíÉ áÅíÌÇÏ ÇáãÓÇÑ ÇáÃÞÕÑ æÇáÎÇáí ãä ÇáÚæÇÆÞ .
ãßæäÇÊ ÇáÎæÇÑÒãíÉ:
1- ãäÇØÞ ÇáÈíÆÉ ÇáÊí ÊÚãá ÚáíåÇ A* .
ßá ãäØÞÉ áåÇ ÇÍÏÇËíÇÊ ÊãËáåÇ Úáì ÇáÎÑíØÉ äÝÊÑÖ ÇäåÇ x æy ÇÐÇ ÇÎÐäÇ ÈÇáÅÚÊÈÇÑ ÇäåÇ ËäÇÆíÉ ÇáÃÈÚÇÏ ÈÇáÅÖÇÝÉ Çáì ÇáÅÍÏÇËíÇÊ ÝÅäåÇ ÊÊßæä ãä ËáÇË ãÚÇáíã ãåãÉ Ýí ÚãáíÉ ÇáÈÍË …
Ã‌- ÇáÞíãÉ g æÊÚäí ãæÞÚ åÐå ÇáãäØÞÉ Úä ãäØÞÉ ÇáÈÏÇíÉ äÃÎÐ ÈÚíä ÇáÅÚÊÈÇÑ ÇáÍæÇÌÒ Ýí ãäØÞÉ ÇáÈÏÇíÉ ÊÃÎÐ g ÇáÞíãÉ 0.
È‌- ÇáÞíãÉ h æÊÚäí ãæÞÚ ÇáãäØÞÉ Úä ÇáåÏÝ ãÊÌÇåáÉ ÇáÍæÇÌÒ Ýí ãäØÞÉ ÇáäåÇíÉ ÊÃÎÐ h ÇáÞíãÉ 0 .
Ê‌- ÇáÞíãÉ f æÊÓÇæí g+h æÇáãäØÞÉ ÇáÃÞá ÞíãÉ åí ÇáÃæáì ÈÇÎÊÈÇÑåÇ ÇæáÇ .
Ë‌- ÇáÞíãÉ From Çæ Parent áß ÇáÍÑíÉ Ýí ÊÓãíÊå æÊÚäí ÇáãäØÞÉ ÇáÊí ÇÊíÊ ãäåÇ Çáì åÐå ÇáãäØÞÉ .
Ì‌- ÇáÞíãÉ pos Çæ place áÅÍÏÇËíÇÊ ÇáãäØÞÉ.
2- ãäØÞÉ ÇáÈÏÇíÉ .
3- ãäØÞÉ ÇáäåÇíÉ.
4- ÇáÍæÇÌÒ.

ãáÇÍÙÉ: ÌãíÚ ÕæÑ ÇáÔÑÍ ãÃÎæÐÉ ãä ÈÑäÇãÌ ÞãÊ ÈÊÕãíãå ÈæÇÓØÉ Qt .

Çááæä ÇáÃÓæÏ ááÍæÇÌÒ æÇáÃÎÖÑ ááÈÏÇíÉ æÇáÃÕÝÑ ááäåÇíÉ æÇáÎáÇíÇ ÇáãÑÈÚÉ ÚÈÇÑÉ Úä ãäÇØÞ ÇÍÏÇËíÇÊåÇ ãä ÇáØÑÝ ÇáÃíÓÑ ÇáÚáæí (0,0) æÊÒÏÇÏÇ ÈãÞÏÇÑ æÇÍÏ ÚäÏ ÊÍÑßäÇ ááíãíä Çæ ááÃÓÝá .

ßíÝ ÊÚãá ÇáÎæÇÑÒãíÉ:
ÊÈÏà ÚãáíÉ ÇáÈÍË ãä äÞØÉ ÇáÈÏÇíÉ æÊÊÍÑß ÈÇÑÈÚ ÇÊÌÇåÇÊ ÔãÇá ÌäæÈ ÔÑÞ ÛÑÈ
1 – åäÇß ÞÇÆãÊÇä openList æ closedList
openList ÊÍÊæí Úáì ÇáãäÇØÞ ÇáÊí áã íÊã ÇÎÊÈÇÑåÇ Ãí áã ÊÊÝÑÚ ãäåÇ ãäÇØÞåÇ ÇáãÌÇæÑÉ áåÇ æ closedList ÊÍÊæí Úáì ÇáãäÇØÞ ÇáÊí Êã ÇÎÊÈÇÑåÇ Ãí ÊÝÑÚÊ ãäåÇ ÇáãäÇØÞ ÇáãÌÇæÑÉ áåÇ .
2- Ëã äÖíÝ ãäØÞÉ ÇáÈÏÇíÉ Çáì openList .
3- ÊÈÏà ÚãáíÉ ÇáÊßÑÇÑ while ãÇÏÇãÊ ÊÊæÝÑ ãäÇØÞ Ýí openList
Ã‌- ÇáÈÍË Úä ÃÞá ÞíãÉ á f Ýí ÇáãäÇØÞ ÇáãÊæÝÑÉ Ýí openList ãáÇÍÙÉ:Ýí ÇáÈÏÇíÉ áä ÊÊæÝÑ ÇáÇ ãäØÞÉ ÇáÈÏÇíÉ áÐÇ ÓæÝ íÊã ÅÎÊíÇÑåÇ .
È‌- äÌÚá ÇáãäØÞÉ ÇáÊí ÞíãÉ f áåÇ åí ÇáÃÞá (ÇáÎØæ Ã) ÇáãäØÞÉ ÇáÍÇáíÉ currentRegion æäÖÚåÇ Ýí closedList æäÍÐÝåÇ ãä openList .
Ê‌- ÇáÊÃßÏ ãä Çä ÇáãäØÞÉ ÇáÍÇáíÉ currentRegion åí ãäØÞÉ ÇáäåÇíÉ Ýí ÍÇá ßÇäÊ áíÓÊ åí ãäØÞÉ ÇáäåÇíÉ äßãá æÅáÇ ÝÅääÇ äÊÊÈÚ ÓáÓáÉ from ááãäÇØÞ áäÑÓá ÞÇÆãÉ ÈÇáãäÇØÞ ÇáÊí äãÑ ÈåÇ æÇáÊí ÊÚÊÈÑ ÇáÃÞÕÑ æÇáÊí áíÓÊ ÈåÇ ÍæÇÌÒ .
Ë‌- äÈÍË Úä ÇáÌíÑÇä ááãäØÞÉ ÇáÍÇáíÉ ÈÍíË áÇíßæä ÇáÌÇÑ ÚÈÇÑÉ Úä ÍÇÌÒ æÇä áÇíßæä Ýí ÇáÞÇÆãÉ ÇáãÛáÞÉ closedList æÝí ÍÇá ßÇä Ýí ÇáÞÇÆãÉ ÇáãÝÊæÍÉ äÖíÝ ÇáíåÇ ãÚáæãÇÊ g æ h æ f æäÌÚá ÞíãÉ From ÊÔíÑ Çáì ÇáãäØÞÉ ÇáÍÇáíÉ æÇÐÇ ßÇä ÛíÑ ãÊæÝÑ Ýí ÇáÞÇÆãÉ openList äÖíÝå Çáì ÇáÞÇÆãÉ æäÖÚ áå ÇáãÚáæãÇÊ g æ h æ f æäÌÚá ÞíãÉ From ÊÔíÑ Çáì ÇáãäØÞÉ ÇáÍÇáíÉ .


Ì‌- äÑÌÚ áÈÏÇíÉ ÇáÊßÑÇÑ
ÃãæÑ ÎÝíÉ :
1- ÓæÝ ÊÔãá ÚãáíÉ ÇáÈÍË ãäÇØÞ ãÛáÞÉ æãäÇØÞ ÈÚíÏÉ æÇáãÓÇÑ ÇáÐí íÕá Çæá Çáì ãäØÞÉ ÇáäåÇíÉ åæ ÇáÃÞÑÈ áÐáß Êã ÇíÌÇÏ ÇáÞíãÉ From áÊÕáäÇ Çáì ÇáãÓÇÑ ÇáÃÞÕÑ ááãäØÞÉ ÇáÊí äÝÐäÇ ãäåÇ Çáì ãäØÞÉ ÇáäåÇíÉ.

áÇÍÙ Ýí åÐå ÇáÑÓãÉ áÞÏ ÔãáÊ ÚãáíÉ ÇáÈÍË ÌãíÚ ÇáãäÇØÞ (áíÓ åÐÇ ÏÇÆãÇ ãÇíÍÏË) ÍÊì áÇãÓäÇ ÎØ ÇáäåÇíÉ Ëã ÊÊÈÚäÇ ÇáÞíãÉ From ÈÇáÔßá ÇáÊÇáí ãä ÇáäåÇíÉ (ÇáãäØÞÉ ÇáÍÇáíÉ ÈÇáäÓÈÉ ááÊØÈíÞ ÇáÝÚáí) Çáì ÇáÈÏÇíÉ .

ÇáÔíÝÑÉ ÇáÝÚáíÉ ááÎæÇÑÒãíÉ Ýí ÇáÈÑäÇãÌ ÇáÐí ÃÎÐäÇ ãäå ÇáÕæÑ ÇáÔíÝÑÉ ÇáÝÚáíÉ ááÎæÇÑÒãíÉ Ýí ÇáÈÑäÇãÌ ÇáÐí ÃÎÐäÇ ãäå ÇáÕæÑ æÓæÝ ÇÖÚ ÇáÔíÝÑÉ ÇáãÕÏÑíÉ ááÈÑäÇãÌ ßÇãáÇ Ýí æÞÊ áÇÍÞ ÈÅÐä Çááå

QList<NodeItem*> Widget::AStar()
{
    QList<NodeItem*> openList;
    QList<NodeItem*> closedList;
    openList<<Start;
    while(openList.count())    {
        int mini=0;
        NodeItem* currentNode;
        for(int i=0;i<openList.count();i++)
        {
            if(openList.at(i)->F<openList.at(mini)->F)
                mini=i;
        }
        currentNode=openList.at(mini);        
        if(currentNode==End)
        {
            NodeItem* cu=currentNode;
            QList<NodeItem*> Nodes;
            while(cu->From)
            {
                Nodes<<cu->From;
                cu=cu->From;
            }
            Nodes.removeAt(Nodes.length()-1);
            return Nodes;
        }
        openList.removeOne(currentNode);
        closedList<<currentNode;
        QList<NodeItem*> jeeran=getJeerans(currentNode);
        for(int i=0;i<jeeran.count();i++)
        {
            NodeItem* nn=jeeran.at(i);
            if(closedList.contains(nn))continue;
            int g=currentNode->G+1;
            bool gm=0;
            if(!openList.contains(nn))
            {
                gm=true;
                nn->H=abs(End->getPlace().x()-nn->getPlace().x())+
                      abs(End->getPlace().y()-nn->getPlace().y());
                openList<<nn;
            }
            else if(g<nn->G)
            {
                gm=true;
            }
            if(gm)
            {
                nn->From=currentNode;
                nn->G=g;
                nn->F=nn->G+nn->H;
            }
        }
 
 
    }
    QList<NodeItem*> v;    return v;
}
QList<NodeItem*> Widget::getJeerans(NodeItem* from)
{
    QList<NodeItem*> nodes;
    int x=from->getPlace().x();
    int y=from->getPlace().y();
    foreach(NodeItem* n,this->NIS)
    {
        if(n->getPlace()==QPoint(x+1,y))
        {
            if(n->isEmpty())
                nodes<<n;
        }
        if(n->getPlace()==QPoint(x-1,y))
        {
            if(n->isEmpty())
                nodes<<n;
        }
        if(n->getPlace()==QPoint(x,y+1))
        {
            if(n->isEmpty())
                nodes<<n;
        }
        if(n->getPlace()==QPoint(x,y-1))
        {
            if(n->isEmpty())
                nodes<<n;
        }
    }
    return nodes;
}