How do I make A* check all diagonal and orthogonal directions?
- by Munezane
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;
}
}
}
}
