Results 1 to 8 of 8

Thread: A* help. please

  1. #1

    Thread Starter
    Addicted Member CodeRonin's Avatar
    Join Date
    Jul 2002
    Location
    Vienna, Austria
    Posts
    233

    A* help. please

    Hi there,
    I've just recently finished my A* algo for my iso game and it works just fine for short paths. It does not work, however, for longer paths (paths which require to scroll the map) and it crushes if the path doesn't exist....

    Those fellow coders out there how had the "pleasure" of dealing with a star and those who just know the principles I kindly ask to take a look at this code and tell me wheter you can see the error.

    As always, any help is appreciated...
    Code Ronin

  2. #2
    Not NoteMe SLH's Avatar
    Join Date
    Mar 2002
    Location
    192.168.0.1 Preferred Animal: Penguin Reason for errors: Line#38
    Posts
    3,051
    I am familiar with the A* alg. If you post the code i'll take a look if you like.
    Quotes:
    "I am getting better then you guys.." NoteMe, on his leet english skills.
    "And I am going to meat her again later on tonight." NoteMe
    "I think you should change your name to QuoteMe" Shaggy Hiker, regarding NoteMe
    "my sweet lord jesus. I've decided never to have breast implants" Tom Gibbons
    Have I helped you? Please Rate my posts.


  3. #3

    Thread Starter
    Addicted Member CodeRonin's Avatar
    Join Date
    Jul 2002
    Location
    Vienna, Austria
    Posts
    233

    The code

    bool Unit::FindPath(int x1, int y1, int x2, int y2, GameTile GTMAP[MAP_HEIGHT][MAP_WIDTH])
    {
    int OpenListCnt = -1;
    int ClosedListCnt = -1;

    AList OpenList;
    AList ClosedList;

    //vector<ANode>::iterator from;
    //vector<ANode>::iterator to;

    ANode node;
    node.g = 0;
    node.h = 10 * (abs(x1 - x2) + abs(y1 - y2));
    node.f = node.h;
    node.parent = NULL;
    node.ref_GT = &GTMAP[y1][x1];
    node.x = x1;
    node.y = y1;

    ClosedList.Add (node);
    ClosedListCnt++;

    //even tiles are shifted one position to the left

    /******************************************************************************
    * Adjacent square coordinate addition / substraction ( = negative addition)
    *******************************************************************************/
    PointOverLoad EvenAdjacentSquare[8];
    PointOverLoad OddAdjacentSquare[8];
    PointOverLoad *AdjacentSquare;

    EvenAdjacentSquare[0].x = 0;
    EvenAdjacentSquare[1].x = 0;
    EvenAdjacentSquare[2].x = 1;
    EvenAdjacentSquare[3].x = 0;
    EvenAdjacentSquare[4].x = 0;
    EvenAdjacentSquare[5].x = -1;
    EvenAdjacentSquare[6].x = -1;
    EvenAdjacentSquare[7].x = -1;

    OddAdjacentSquare[0].x = 0;
    OddAdjacentSquare[1].x = 1;
    OddAdjacentSquare[2].x = 1;
    OddAdjacentSquare[3].x = 1;
    OddAdjacentSquare[4].x = 0;
    OddAdjacentSquare[5].x = 0;
    OddAdjacentSquare[6].x = -1;
    OddAdjacentSquare[7].x = 0;

    EvenAdjacentSquare[0].y = -2;
    EvenAdjacentSquare[1].y = -1;
    EvenAdjacentSquare[2].y = 0;
    EvenAdjacentSquare[3].y = +1;
    EvenAdjacentSquare[4].y = +2;
    EvenAdjacentSquare[5].y = +1;
    EvenAdjacentSquare[6].y = 0;
    EvenAdjacentSquare[7].y = -1;

    OddAdjacentSquare[0].y = -2;
    OddAdjacentSquare[1].y = -1;
    OddAdjacentSquare[2].y = 0;
    OddAdjacentSquare[3].y = +1;
    OddAdjacentSquare[4].y = +2;
    OddAdjacentSquare[5].y = +1;
    OddAdjacentSquare[6].y = 0;
    OddAdjacentSquare[7].y = -1;

    int mincost;
    int mincosttile;
    bool alreadyfound;
    bool FoundPath = false;

    while (!FoundPath)
    {
    if(ClosedList[ClosedListCnt].y % 2)
    {
    AdjacentSquare = OddAdjacentSquare;
    }
    else
    {
    AdjacentSquare = EvenAdjacentSquare;
    }
    for (int i = 0; i < 8; i++)
    {
    alreadyfound = false;
    // check for passability
    if (!((ClosedList[ClosedListCnt].y + AdjacentSquare[i].y >= 0) && (ClosedList[ClosedListCnt].y + AdjacentSquare[i].y < MAP_WIDTH) && (ClosedList[ClosedListCnt].x + AdjacentSquare[i].x >= 0) && (ClosedList[ClosedListCnt].x + AdjacentSquare[i].x < MAP_HEIGHT)))
    continue;
    if (GTMAP[ClosedList[ClosedListCnt].y + AdjacentSquare[i].y][ClosedList[ClosedListCnt].x + AdjacentSquare[i].x].IsPassable())
    {
    //check if the element is on the list already...
    for (int h=0; h <= ClosedListCnt; h++)
    if ((ClosedList[h].x == ClosedList[ClosedListCnt].x + AdjacentSquare[i].x) && (ClosedList[h].y == ClosedList[ClosedListCnt].y + AdjacentSquare[i].y))
    {
    alreadyfound = true;
    break;
    }

    //if not on the closed list, check if it's on the open list
    if (!alreadyfound)
    for(int h = 0;h <= OpenListCnt; h++)
    {
    if ((OpenList[h].x == ClosedList[ClosedListCnt].x + AdjacentSquare[i].x) && (OpenList[h].y == ClosedList[ClosedListCnt].y + AdjacentSquare[i].y))
    {
    alreadyfound=true;
    if(ClosedList[ClosedListCnt].g < OpenList[h].parent->g)
    {
    OpenList[h].parent = &ClosedList[ClosedListCnt];
    OpenList[h].g = ClosedList[ClosedListCnt].g + GTMAP[OpenList[OpenListCnt].y][OpenList[OpenListCnt].x].GetMC();
    OpenList[h].f = OpenList[h].g + OpenList[h].h;
    }
    }
    }

    //Element in keiner Liste und passierbar
    if(!alreadyfound)
    {
    node.x = ClosedList[ClosedListCnt].x + AdjacentSquare[i].x;
    node.y = ClosedList[ClosedListCnt].y + AdjacentSquare[i].y;
    node.g = ClosedList[ClosedListCnt].g + GTMAP[node.y][node.x].GetMC();
    //OpenList[OpenListCnt].h = heuristic()
    //H = 10*(abs(currentX-targetX) + abs(currentY-targetY))
    node.h = 10 * (abs(node.x - x2) + abs(node.y - y2));
    node.f = node.g + node.h;
    node.parent = &ClosedList[ClosedListCnt];
    node.ref_GT= &GTMAP[node.y][node.x];
    OpenList.Add (node);
    OpenListCnt++;
    }
    }
    }

    if (OpenListCnt < 0)
    return false;

    mincost = OpenList[0].f;
    mincosttile = 0;
    for (i=0; i <= OpenListCnt; i++)
    {
    if (OpenList[i].x == x2 && OpenList[i].y == y2)
    {
    mincost = OpenList[i].f;
    mincosttile = i;
    FoundPath = true;
    break;
    }
    if (OpenList[i].f < mincost)
    {
    mincost = OpenList[i].f;
    mincosttile = i;
    }
    }

    //"billigstes" Element auf die ClosedList setzen
    ClosedList.Add (OpenList[mincosttile]);
    ClosedListCnt++;
    OpenList.erase (mincosttile);
    OpenListCnt--;

    }

    /*for (int i = 0; i < ClosedListCnt - 1; i++)
    {
    Path[i] = ClosedList[i];
    }*/

    AList tmpPath;
    ANode *ToPath = ClosedList.last;
    int i;
    Path.clear ();

    for (i=0; ToPath; i++)
    {
    tmpPath.Add (*ToPath);
    ToPath = ToPath->parent;
    }

    i--;
    for (;i>=0;i--)
    {
    Path.Add (tmpPath[i]);
    }

    return true;
    }
    Code Ronin

  4. #4

    Thread Starter
    Addicted Member CodeRonin's Avatar
    Join Date
    Jul 2002
    Location
    Vienna, Austria
    Posts
    233

    Sure ;)

    Just took me a moment to rewrite the commernts from german to english
    Code Ronin

  5. #5
    Not NoteMe SLH's Avatar
    Join Date
    Mar 2002
    Location
    192.168.0.1 Preferred Animal: Penguin Reason for errors: Line#38
    Posts
    3,051
    Next time you may want to use the [code][/code] tag.
    I got round it by quoting you, and pasteing it into notepad though.


    Anyway, i looked through your code pretty thoroughly and couldn't find anything wrong with it.

    The only think i think that could be wrong is your AList class, or your ANode class. Other than that it seems fine.

    Have you checked that the crash actually occurs in the pathfinding code, as opposed to once it's returned false (for the No-Path posibility)?



    EDIT: Have just noticed that i think when you check your adjacent tile is within the map, you've got WIDTH and HEIGHT the wrong way round:

    if (!((ClosedList[ClosedListCnt].y + AdjacentSquare[i].y >= 0) && (ClosedList[ClosedListCnt].y + AdjacentSquare[i].y < MAP_WIDTH) &&
    (ClosedList[ClosedListCnt].x + AdjacentSquare[i].x >= 0) && (ClosedList[ClosedListCnt].x + AdjacentSquare[i].x < MAP_HEIGHT)))
    Quotes:
    "I am getting better then you guys.." NoteMe, on his leet english skills.
    "And I am going to meat her again later on tonight." NoteMe
    "I think you should change your name to QuoteMe" Shaggy Hiker, regarding NoteMe
    "my sweet lord jesus. I've decided never to have breast implants" Tom Gibbons
    Have I helped you? Please Rate my posts.


  6. #6

    Thread Starter
    Addicted Member CodeRonin's Avatar
    Join Date
    Jul 2002
    Location
    Vienna, Austria
    Posts
    233

    Thanks a lot

    You were right, SLH, I've messed up with the width and height... now, the scrolling-problem is resolved, thank you very much, I really appreciate your help.

    If there's no possible way the program still crushes, but I'll take a look at the list and node and should I fail to find any error, I guess I'll just solve it with a timer... something like if the path isn't found after 5 seconds, there's no way... I know it's not the best solution, but hey, I guess it's the fastest .
    Code Ronin

  7. #7
    Not NoteMe SLH's Avatar
    Join Date
    Mar 2002
    Location
    192.168.0.1 Preferred Animal: Penguin Reason for errors: Line#38
    Posts
    3,051
    Run it in debug mode and find out what line it crashes (if you havn't already), it may help to trace the bug.
    Quotes:
    "I am getting better then you guys.." NoteMe, on his leet english skills.
    "And I am going to meat her again later on tonight." NoteMe
    "I think you should change your name to QuoteMe" Shaggy Hiker, regarding NoteMe
    "my sweet lord jesus. I've decided never to have breast implants" Tom Gibbons
    Have I helped you? Please Rate my posts.


  8. #8

    Thread Starter
    Addicted Member CodeRonin's Avatar
    Join Date
    Jul 2002
    Location
    Vienna, Austria
    Posts
    233

    Well...

    It appears the algo is just searching forever, caught in a loop that checks every single tile if no way is found... do you have any idea how i could speed up the search / determine when he should ccancel it?
    Code Ronin

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width