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[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
if(aStarOpenList.size()>1)
{
for(unsigned int j=1; j
if(aStarOpenList[i]->TotalCostEstimateTotalCostEstimate)
{
currentSquare=aStarOpenList[i];
}
else
{
currentSquare=aStarOpenList[j];
}
}
}
else
{
currentSquare = aStarOpenList[i];
}
}
currentSquare->closed=true;
currentSquare->open=false;
for(unsigned int i=0; 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;
}
}
}
}
Answer
Here is a list of bugs I could spot on first check. I'm not sure which one will fix your problem or if any of them would actually fix them but here it goes:
startSquareis a simple pointer which you are allocating when your function begins. Later on line 13 you are reassigning another value to that pointer, which causes memory leak. Since you'll not be able to delete it's old value. The same goes fortargetSquare.Before returning on line 19 you need to deallocate all the memory you've got in the function. Note that it's C++ you are working with, it doesn't have fancy things like garbage collector so you need to keep track of everything you are not using and delete them manually.
All your
forstatements from line 30 to line 50 is just rubbish, if you want to find the minimum estimated cost it's a singleforloop iterating overaStarSquareListand checking which one has minimum value. Here is how you should have implemented it (with minimum change, also this one seems to be causing the problem):{
{
currentSqaure = aStarOpenList[0];
for(unsigned int j=1; j
if(aStarOpenList[i]->TotalCostEstimateTotalCostEstimate)
currentSquare=aStarOpenList[i];
}
}
}Instead of using an array and searching for minimum value yourself it's much better to use a priority queue. If you don't know what it is check C++ reference.
There is no need to keep both
closeandopenflag for all the sqaures. Justcloseis enough. Adding a state multiple times to theaStarOpenListdoesn't hurt anybody, just check everytime you choosecurrentSquarethat it's not already closed. So removeifstatement at line 69.At line 72
ifis not necessary, you simply know that no parent is NULL since you are assigning some value into it just beforeif. Note thatcurrentSquarealso can't be NULL.Also line 80 is a duplicate to line 74, just as in line 74 you are taking
startSquare->CostFromStartinto account which is completely irrelevant to path chosen. It only helps you to find minimum distant. You can add that value only once when you are returning.Also forget the
elsepart from line 90 line 111, as I said adding a value multiple times doesn't hurt anybody. It might look a bit slower at first sight but believe me, it'll prevent many possible implementation bugs.You should change the comment at line 117, change it from
//if emptyto//if there was no path, it makes more sense.At line 127 how can a parent be NULL unless it's the starting square? Every other square beside the starting square has a parent. In your case, also the second square in your path (for which the parent is
startSquare). So change thatifstatement to this oneif(currentSquare->parent==startSquare)This one also depends on your style but I prefer
returninstead ofbreakat line 133.Again I think you are leaking some memory both at line 121 and at function end.
I hope I've fixed everything but it's almost impossible, so don't worry if there are still some bugs in your code after these fixes.
EDIT
On the second check you are also leaking memory by allocating memory for both currentSquare and adjacentSquare. Just drop the new statements from their declarations and everything about them will be fixed.
No comments:
Post a Comment