0
\$\begingroup\$

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;
            }
        }
    }
}
\$\endgroup\$
5
  • \$\begingroup\$ you could probably simplify this down quite a bit by just using a Point data type, but is the character able to move all other direction? \$\endgroup\$
    – gardian06
    Mar 31, 2012 at 0:27
  • 1
    \$\begingroup\$ Why not feed it an end position that is up and left to your start position and step through it with the debugger? See where it's exiting. \$\endgroup\$
    – House
    Mar 31, 2012 at 0:42
  • \$\begingroup\$ is it even generating the diagonals, and then does you heuristic even take diagonals into account when it generates a value? \$\endgroup\$
    – gardian06
    Mar 31, 2012 at 0:43
  • \$\begingroup\$ the old fashion "debug it" questions... \$\endgroup\$
    – Ali1S232
    Mar 31, 2012 at 0:53
  • \$\begingroup\$ i did debug, I found that the top left square (which was the goal) was considered as an adjacent node, but for some reason it wasn't set to the current node, instead the algorithm proceeds to consider literally every node on the map. This confused me as the top left square had a low cost, but the other squares it followed had ridiculous costs and 100s of parents \$\endgroup\$
    – Munezane
    Mar 31, 2012 at 15:13

1 Answer 1

7
\$\begingroup\$

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:

  1. startSquare is 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 for targetSquare.

  2. 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.

  3. All your for statements from line 30 to line 50 is just rubbish, if you want to find the minimum estimated cost it's a single for loop iterating over aStarSquareList and 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<aStarOpenList.size(); j++)
            {
                if(aStarOpenList[i]->TotalCostEstimate<currentSqaure->TotalCostEstimate)
                    currentSquare=aStarOpenList[i];
            }
        }
    }
    
  4. 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.

  5. There is no need to keep both close and open flag for all the sqaures. Just close is enough. Adding a state multiple times to the aStarOpenList doesn't hurt anybody, just check everytime you choose currentSquare that it's not already closed. So remove if statement at line 69.

  6. At line 72 if is not necessary, you simply know that no parent is NULL since you are assigning some value into it just before if. Note that currentSquare also can't be NULL.

  7. Also line 80 is a duplicate to line 74, just as in line 74 you are taking startSquare->CostFromStart into 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.

  8. Also forget the else part 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.

  9. You should change the comment at line 117, change it from //if empty to //if there was no path, it makes more sense.

  10. 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 that if statement to this one if(currentSquare->parent==startSquare)

  11. This one also depends on your style but I prefer return instead of break at line 133.

  12. 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.

\$\endgroup\$
3
  • \$\begingroup\$ Thank you soooooo much, i'm not entirely sure which fix helped, but it seems to be working now! :D \$\endgroup\$
    – Munezane
    Mar 31, 2012 at 15:31
  • \$\begingroup\$ by the way, how do i mark this question as answered? lol i'm new to stack exhange \$\endgroup\$
    – Munezane
    Mar 31, 2012 at 15:36
  • \$\begingroup\$ @Munezane seems you have found it yourself! \$\endgroup\$
    – Ali1S232
    Mar 31, 2012 at 17:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .