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

2. I am familiar with the A* alg. If you post the code i'll take a look if you like.

3. ## 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;

ClosedListCnt++;

//even tiles are shifted one position to the left

/******************************************************************************
*******************************************************************************/

int mincost;
int mincosttile;
bool FoundPath = false;

while (!FoundPath)
{
if(ClosedList[ClosedListCnt].y % 2)
{
}
else
{
}
for (int i = 0; i < 8; i++)
{
// 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;
{
//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))
{
break;
}

//if not on the closed list, check if it's on the open list
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))
{
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
{
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];
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
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++)
{
ToPath = ToPath->parent;
}

i--;
for (;i>=0;i--)
{
}

return true;
}

4. ## Sure ;)

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

5. 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) &&

6. ## 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 .

7. Run it in debug mode and find out what line it crashes (if you havn't already), it may help to trace the bug.

8. ## 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?

#### Posting Permissions

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