How do I make A* check all diagonal and orthogonal directions?

Posted by Munezane on Game Development See other posts from Game Development or by Munezane
Published on 2012-03-31T00:18:27Z Indexed on 2012/03/31 11:43 UTC
Read the original article Hit count: 239

Filed under:
|

I'm making a turn-based tactical game and I'm trying to implement the A* algorithm. I've been following a tutorial and got to this point, but my characters can't move diagonally up and left.

Can anyone help me with this? The return x and y are int pointers which the characters are using to move towards the target.

void level::aStar(int startx, int starty, int targetx, int targety, int* returnx, int* returny)
{
    aStarGridSquare* currentSquare = new aStarGridSquare();
    aStarGridSquare* startSquare = new aStarGridSquare();
    aStarGridSquare* targetSquare = new aStarGridSquare();
    aStarGridSquare* adjacentSquare = new aStarGridSquare();
    aStarOpenList.clear();
    for(unsigned int i=0; i<aStarGridSquareList.size(); i++)
    {
        aStarGridSquareList[i]->open=false;
        aStarGridSquareList[i]->closed=false;
    }
    startSquare=getaStarGridSquare(startx, starty);
    targetSquare=getaStarGridSquare(targetx, targety);
    if(startSquare==targetSquare)
    {
        *returnx=startx;
        *returny=starty;
        return;
    }
    startSquare->CostFromStart=0;
    startSquare->CostToTraverse=0;
    startSquare->parent = NULL;
    currentSquare=startSquare;
    aStarOpenList.push_back(currentSquare);
    while(currentSquare!=targetSquare && aStarOpenList.size()>0)
    {    
        //unsigned int totalCostEstimate=aStarOpenList[0]->TotalCostEstimate;
        //currentSquare=aStarOpenList[0];
        for(unsigned int i=0; i<aStarOpenList.size(); i++)
        {
            if(aStarOpenList.size()>1)
            {
                for(unsigned int j=1; j<aStarOpenList.size()-1; j++)
                {
                    if(aStarOpenList[i]->TotalCostEstimate<aStarOpenList[j]->TotalCostEstimate)
                    {
                        currentSquare=aStarOpenList[i];
                    }
                    else
                    {
                        currentSquare=aStarOpenList[j];
                    }
                }
            }
            else
            {
                currentSquare = aStarOpenList[i];
            }
        }
        currentSquare->closed=true;
        currentSquare->open=false;
        for(unsigned int i=0; i<aStarOpenList.size(); i++)
        {
            if(aStarOpenList[i]==currentSquare)
            {
                aStarOpenList.erase(aStarOpenList.begin()+i);
            }
        }
        for(unsigned int i = currentSquare->blocky - 32; i <= currentSquare->blocky + 32; i+=32)
        {
            for(unsigned int j = currentSquare->blockx - 32; j<= currentSquare->blockx + 32; j+=32)
            {
                adjacentSquare=getaStarGridSquare(j/32, i/32);
                if(adjacentSquare!=NULL)
                {
                    if(adjacentSquare->blocked==false && adjacentSquare->closed==false)
                    {
                        if(adjacentSquare->open==false)
                        {
                            adjacentSquare->parent=currentSquare;
                            if(currentSquare->parent!=NULL)
                            {
                                currentSquare->CostFromStart = currentSquare->parent->CostFromStart + currentSquare->CostToTraverse + startSquare->CostFromStart;
                            }
                            else
                            {
                                currentSquare->CostFromStart=0;
                            }
                            adjacentSquare->CostFromStart =currentSquare->CostFromStart + adjacentSquare->CostToTraverse;// adjacentSquare->parent->CostFromStart + adjacentSquare->CostToTraverse;
                            //currentSquare->CostToEndEstimate = abs(currentSquare->blockx - targetSquare->blockx) + abs(currentSquare->blocky - targetSquare->blocky);
                            //currentSquare->TotalCostEstimate = currentSquare->CostFromStart + currentSquare->CostToEndEstimate;
                            adjacentSquare->open = true;

                            adjacentSquare->CostToEndEstimate=abs(adjacentSquare->blockx- targetSquare->blockx) + abs(adjacentSquare->blocky-targetSquare->blocky);
                            adjacentSquare->TotalCostEstimate = adjacentSquare->CostFromStart+adjacentSquare->CostToEndEstimate;
                            //adjacentSquare->open=true;*/
                            aStarOpenList.push_back(adjacentSquare);
                        }
                        else
                        {
                            if(adjacentSquare->parent->CostFromStart > currentSquare->CostFromStart)
                            {
                                adjacentSquare->parent=currentSquare;
                                if(currentSquare->parent!=NULL)
                                {
                                    currentSquare->CostFromStart = currentSquare->parent->CostFromStart + currentSquare->CostToTraverse + startSquare->CostFromStart;
                                }
                                else
                                {
                                    currentSquare->CostFromStart=0;
                                }
                                adjacentSquare->CostFromStart =currentSquare->CostFromStart + adjacentSquare->CostToTraverse;// adjacentSquare->parent->CostFromStart + adjacentSquare->CostToTraverse;
                                //currentSquare->CostToEndEstimate = abs(currentSquare->blockx - targetSquare->blockx) + abs(currentSquare->blocky - targetSquare->blocky);
                                //currentSquare->TotalCostEstimate = currentSquare->CostFromStart + currentSquare->CostToEndEstimate;

                                adjacentSquare->CostFromStart = adjacentSquare->parent->CostFromStart + adjacentSquare->CostToTraverse;
                                adjacentSquare->CostToEndEstimate=abs(adjacentSquare->blockx - targetSquare->blockx) + abs(adjacentSquare->blocky - targetSquare->blocky);
                                adjacentSquare->TotalCostEstimate = adjacentSquare->CostFromStart+adjacentSquare->CostToEndEstimate;
                            }
                        }
                    }
                }
            }
        }
    }
    if(aStarOpenList.size()==0)//if empty
    {
        *returnx =startx;
        *returny =starty;
        return;
    }
    else
    {
        for(unsigned int i=0; i< aStarOpenList.size(); i++)
        {
            if(currentSquare->parent==NULL)
            {
                //int tempX = targetSquare->blockx;
                //int tempY = targetSquare->blocky;
                *returnx=targetSquare->blockx;
                *returny=targetSquare->blocky;
                break;
            }
            else
            {
                currentSquare=currentSquare->parent;
            }
        }
    }
}

© Game Development or respective owner

Related posts about c++

Related posts about path-finding