# A* implementation glitchy

This topic is 3824 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hey there, I just got my first-ever implementation of the A* path-finding algorithm to work, but it's glitchy and I'm not so sure why. I have been following this popular GameDev article. First of all, take a look at the code (I'm fully aware that this is not written elegantly or any more than a dirty hack for that matter, feel free to give advice on a cleaner implementation):
void calc_path ( void )
// calculates path
{
int start_x, start_y, end_x, end_y;

std::list < CTile > open_list, closed_list;

start_x = start_y = end_x = end_y = -1;

for ( int y = 0; y < TILES_Y; ++y )
// loop through columns of tiles
{
for ( int x = 0; x < TILES_X; ++x )
// loop through rows of tiles
{
if ( tile[x][y].State == Start )
{
start_x = x;
start_y = y;
}
else if ( tile[x][y].State == End )
{
end_x = x;
end_y = y;
}
else if ( tile[x][y].State == Path )
tile[x][y].Init ( tile[x][y].Sprite.X, tile[x][y].Sprite.Y, tile[x][y].I, tile[x][y].J, Empty );
}

}

if ( start_x == -1 || start_y == -1 || end_x == -1 || end_y == -1 )
// if not both start and end exist
return;

printf ( "Calculating path from %d, %d to %d, %d...\n", start_x, start_y, end_x, end_y );

printf ( "Printing costs...\n" );

// calculate cost for all tiles
for ( y = 0; y < TILES_Y; ++y )
// loop through columns of tiles
{
for ( int x = 0; x < TILES_X; ++x )
// loop through rows of tiles
{
if ( tile[x][y].State != Solid )
tile[x][y].Cost = calc_distance ( tile[x][y].Sprite.X, tile[x][y].Sprite.Y, tile[end_x][end_y].Sprite.X, tile[end_x][end_y].Sprite.Y );

// print cost for all tiles
printf ( "%f ", tile[x][y].Cost );
}
printf ( "\n" );
}

// add start tile to open list
open_list.push_back ( tile[start_x][start_y] );
printf ( "Start tile %d, %d added to open list...\n", start_x, start_y );

while ( !open_list.empty ( ) )
// while open list is filled
{
CTile current_tile;

current_tile.Cost = -1.0f;

// find the tile on the open list that has the least cost and store it as current tile
std::list < CTile > ::iterator i;
for ( i = open_list.begin ( ); i != open_list.end ( ); ++i )
// loop through open list
{
CTile temp_tile = *i;

if ( temp_tile.Cost < current_tile.Cost || current_tile.Cost == -1.0f )
// if this tile's cost is lower than the previous lowest cost or if this is the first tile
// store it
current_tile = tile[temp_tile.I][temp_tile.J];
}

printf ( "Current tile (with lowest cost on open list) is %d, %d with cost %f...\n", current_tile.I, current_tile.J, current_tile.Cost );

if ( current_tile.I == end_x && current_tile.J == end_y )
// if we have the end as current tile
{
printf ( "Path found...\n" );

printf ( "Printing parents...\n" );

// calculate cost for all tiles
for ( y = 0; y < TILES_Y; ++y )
// loop through columns of tiles
{
for ( int x = 0; x < TILES_X; ++x )
// loop through rows of tiles
{
// print parents for all tiles
printf ( "%d, %d | ", tile[x][y].ParentI, tile[x][y].ParentJ );
}
printf ( "\n" );
}

printf ( "Retracing path...\n" );

while ( true )
// forever
{
printf ( "%d, %d (parent: %d, %d)\n", current_tile.I, current_tile.J, tile[current_tile.I][current_tile.J].ParentI, tile[current_tile.I][current_tile.J].ParentJ );

tile[current_tile.I][current_tile.J].Init ( tile[current_tile.I][current_tile.J].Sprite.X, tile[current_tile.I][current_tile.J].Sprite.Y, tile[current_tile.I][current_tile.J].I, tile[current_tile.I][current_tile.J].J, Path );

if ( tile[current_tile.I][current_tile.J].I == start_x && tile[current_tile.I][current_tile.J].J == start_y )
// if we have retraced the path back to the start
{
printf ( "Done finding path...\n" );

return;
}

current_tile.I = tile[current_tile.I][current_tile.J].ParentI;
current_tile.J = tile[current_tile.I][current_tile.J].ParentJ;
}
}

// add current tile to closed list
closed_list.push_back ( current_tile );

// and take it off open list
for ( i = open_list.begin ( ); i != open_list.end ( ); ++i )
// loop through open list
{
CTile temp_tile = *i;

if ( temp_tile.I == current_tile.I && temp_tile.J == current_tile.J )
// get current tile
{
// take current tile off of open list and end search
open_list.erase ( i );

break;
}

}

printf ( "Current tile added to closed and taken off of open list...\n" );

// find and store adjacent tiles

for ( int _i = 0; _i < 8; ++_i )
{
}

printf ( "Printing adjacent tiles to current tile %d, %d...\n", current_tile.I, current_tile.J );

if ( ( current_tile.I - 1 ) > -1 && ( current_tile.J - 1 ) > -1 )
{
adj_tile[0] = tile[current_tile.I - 1][current_tile.J - 1];
printf ( "%d, %d\n", current_tile.I - 1, current_tile.J - 1 );
}

if ( ( current_tile.J - 1 ) > -1 )
{
printf ( "%d, %d\n", current_tile.I, current_tile.J - 1 );
}

if ( ( current_tile.I + 1 ) < TILES_X && ( current_tile.J - 1 ) > -1 )
{
adj_tile[2] = tile[current_tile.I + 1][current_tile.J - 1];
printf ( "%d, %d\n", current_tile.I + 1, current_tile.J - 1 );
}

if ( ( current_tile.I - 1 ) > -1 )
{
printf ( "%d, %d\n", current_tile.I - 1, current_tile.J );
}

if ( ( current_tile.I + 1 ) < TILES_X )
{
printf ( "%d, %d\n", current_tile.I + 1, current_tile.J );
}

if ( ( current_tile.I - 1 ) > -1 && ( current_tile.J + 1 ) < TILES_Y )
{
adj_tile[5] = tile[current_tile.I - 1][current_tile.J + 1];
printf ( "%d, %d\n", current_tile.I - 1, current_tile.J + 1 );
}

if ( ( current_tile.J + 1 ) < TILES_Y )
{
printf ( "%d, %d\n", current_tile.I, current_tile.J + 1 );
}

if ( ( current_tile.I + 1 ) < TILES_X && ( current_tile.J + 1 ) < TILES_Y )
{
adj_tile[7] = tile[current_tile.I + 1][current_tile.J + 1];
printf ( "%d, %d\n", current_tile.I + 1, current_tile.J + 1 );
}

for ( _i = 0; _i < 8; ++_i )
{
{
if ( adj_tile[_i].State != Solid )
// if adjacent tile is not a wall
{

for ( i = closed_list.begin ( ); i != closed_list.end ( ); ++i )
// loop through closed list
{
CTile temp_tile = *i;

// if adjacent tile is on closed list
{
// store result and end search

break;
}
}

// if adjacent tile is not on closed list
{

for ( i = open_list.begin ( ); i != open_list.end ( ); ++i )
// loop through closed list
{
CTile temp_tile = *i;

// if adjacent tile is on open list
{
// store result and end search

break;
}
}

// if adjacent tile is not on open list
{

// set parent-relation

}
}
}
}
}
}

printf ( "No possible path found...\n" );
}

Now, on a map of empty (all walkable, non-solid) tiles, this works fine as long as the start and end are not on a horizontal line, for some reason. Take a look at this debug-print:
Tiles initialized...
New start at 2, 1...
New end at 2, 4...
Calculating path from 2, 1 to 2, 4...
Printing costs...
71.554176 65.969688 64.000000 65.969688 71.554176 80.000000 90.509666 102.449989
57.688820 50.596443 48.000000 50.596443 57.688820 67.882248 80.000000 93.295227
45.254833 35.777088 32.000000 35.777088 45.254833 57.688820 71.554176 86.162636
35.777088 22.627417 16.000000 22.627417 35.777088 50.596443 65.969688 81.584312
32.000000 16.000000 0.000000 16.000000 32.000000 48.000000 64.000000 80.000000
35.777088 22.627417 16.000000 22.627417 35.777088 50.596443 65.969688 81.584312
45.254833 35.777088 32.000000 35.777088 45.254833 57.688820 71.554176 86.162636
57.688820 50.596443 48.000000 50.596443 57.688820 67.882248 80.000000 93.295227
Start tile 2, 1 added to open list...
Current tile (with lowest cost on open list) is 2, 1 with cost 48.000000...
Current tile added to closed and taken off of open list...
Printing adjacent tiles to current tile 2, 1...
1, 0
2, 0
3, 0
1, 1
3, 1
1, 2
2, 2
3, 2
Adjacent tile 1, 0 has a new parent: 2, 1...
Adjacent tile 2, 0 has a new parent: 2, 1...
Adjacent tile 3, 0 has a new parent: 2, 1...
Adjacent tile 1, 1 has a new parent: 2, 1...
Adjacent tile 3, 1 has a new parent: 2, 1...
Adjacent tile 1, 2 has a new parent: 2, 1...
Adjacent tile 2, 2 has a new parent: 2, 1...
Adjacent tile 3, 2 has a new parent: 2, 1...
Current tile (with lowest cost on open list) is 2, 2 with cost 32.000000...
Current tile added to closed and taken off of open list...
Printing adjacent tiles to current tile 2, 2...
1, 1
2, 1
3, 1
1, 2
3, 2
1, 3
2, 3
3, 3
Adjacent tile 1, 3 has a new parent: 2, 2...
Adjacent tile 2, 3 has a new parent: 2, 2...
Adjacent tile 3, 3 has a new parent: 2, 2...
Current tile (with lowest cost on open list) is 2, 3 with cost 16.000000...
Current tile added to closed and taken off of open list...
Printing adjacent tiles to current tile 2, 3...
1, 2
2, 2
3, 2
1, 3
3, 3
1, 4
2, 4
3, 4
Adjacent tile 1, 4 has a new parent: 2, 3...
Adjacent tile 2, 4 has a new parent: 2, 3...
Adjacent tile 3, 4 has a new parent: 2, 3...
Current tile (with lowest cost on open list) is 2, 4 with cost 0.000000...
Path found...
Printing parents...
0, 0 | 2, 1 | 2, 1 | 2, 1 | 0, 0 | 0, 0 | 0, 0 | 0, 0 |
0, 0 | 2, 1 | 0, 0 | 2, 1 | 0, 0 | 0, 0 | 0, 0 | 0, 0 |
0, 0 | 2, 1 | 2, 1 | 2, 1 | 0, 0 | 0, 0 | 0, 0 | 0, 0 |
0, 0 | 2, 2 | 2, 2 | 2, 2 | 0, 0 | 0, 0 | 0, 0 | 0, 0 |
0, 0 | 2, 3 | 2, 3 | 2, 3 | 0, 0 | 0, 0 | 0, 0 | 0, 0 |
0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 |
0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 |
0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 |
Retracing path...
2, 4 (parent: 2, 3)
2, 3 (parent: 2, 2)
2, 2 (parent: 2, 1)
2, 1 (parent: 0, 0)
Done finding path...
New start at 0, 3...
New end at 4, 3...
Calculating path from 0, 3 to 4, 3...
Printing costs...
80.000000 67.882248 57.688820 50.596443 48.000000 50.596443 57.688820 67.882248
71.554176 57.688820 45.254833 35.777088 32.000000 35.777088 45.254833 57.688820
65.969688 50.596443 35.777088 22.627417 16.000000 22.627417 35.777088 50.596443
64.000000 48.000000 32.000000 16.000000 0.000000 16.000000 32.000000 48.000000
65.969688 50.596443 35.777088 22.627417 16.000000 22.627417 35.777088 50.596443

71.554176 57.688820 45.254833 35.777088 32.000000 35.777088 45.254833 57.688820
80.000000 67.882248 57.688820 50.596443 48.000000 50.596443 57.688820 67.882248
90.509666 80.000000 71.554176 65.969688 64.000000 65.969688 71.554176 80.000000
Start tile 0, 3 added to open list...
Current tile (with lowest cost on open list) is 0, 3 with cost 64.000000...
Current tile added to closed and taken off of open list...
Printing adjacent tiles to current tile 0, 3...
0, 2
1, 2
1, 3
0, 4
1, 4
Adjacent tile 0, 2 has a new parent: 0, 3...
Adjacent tile 1, 2 has a new parent: 0, 3...
Adjacent tile 1, 3 has a new parent: 0, 3...
Adjacent tile 0, 4 has a new parent: 0, 3...
Adjacent tile 1, 4 has a new parent: 0, 3...
Current tile (with lowest cost on open list) is 1, 3 with cost 48.000000...
Current tile added to closed and taken off of open list...
Printing adjacent tiles to current tile 1, 3...
0, 2
1, 2
2, 2
0, 3
2, 3
0, 4
1, 4
2, 4
Adjacent tile 2, 2 has a new parent: 1, 3...
Adjacent tile 2, 3 has a new parent: 1, 3...
Adjacent tile 2, 4 has a new parent: 1, 3...
Current tile (with lowest cost on open list) is 2, 3 with cost 32.000000...
Current tile added to closed and taken off of open list...
Printing adjacent tiles to current tile 2, 3...
1, 2
2, 2
3, 2
1, 3
3, 3
1, 4
2, 4
3, 4
Adjacent tile 3, 2 has a new parent: 2, 3...
Adjacent tile 3, 3 has a new parent: 2, 3...
Adjacent tile 3, 4 has a new parent: 2, 3...
Current tile (with lowest cost on open list) is 3, 3 with cost 16.000000...
Current tile added to closed and taken off of open list...
Printing adjacent tiles to current tile 3, 3...
2, 2
3, 2
4, 2
2, 3
4, 3
2, 4
3, 4
4, 4
Adjacent tile 4, 2 has a new parent: 3, 3...
Adjacent tile 4, 3 has a new parent: 3, 3...
Adjacent tile 4, 4 has a new parent: 3, 3...
Current tile (with lowest cost on open list) is 4, 3 with cost 0.000000...
Path found...
Printing parents...
0, 0 | 2, 1 | 2, 1 | 2, 1 | 0, 0 | 0, 0 | 0, 0 | 0, 0 |
0, 0 | 2, 1 | 0, 0 | 2, 1 | 0, 0 | 0, 0 | 0, 0 | 0, 0 |
0, 3 | 0, 3 | 1, 3 | 2, 3 | 3, 3 | 0, 0 | 0, 0 | 0, 0 |
0, 0 | 0, 3 | 1, 3 | 2, 3 | 3, 3 | 0, 0 | 0, 0 | 0, 0 |
0, 3 | 0, 3 | 1, 3 | 2, 3 | 3, 3 | 0, 0 | 0, 0 | 0, 0 |
0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 |
0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 |
0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 | 0, 0 |
Retracing path...
4, 3 (parent: 3, 3)
3, 3 (parent: 2, 3)
2, 3 (parent: 1, 3)
1, 3 (parent: 0, 3)
0, 0 (parent: 0, 0)
0, 0 (parent: 0, 0)
0, 0 (parent: 0, 0)
0, 0 (parent: 0, 0)
[ keeps on looping ... ]

As you can see, first the start and end are exactly vertical (something like 4, 2 and 4, 6) - this works fine. But then, I set them on a horizontal-line (for example 2,4 and 6,4) and it freezes. Now, if I take a closer look at this problem, I find that the problem lies in the retracing of the path from end to finish. This piece of code...
printf ( "Retracing path...\n" );

while ( true )
// forever
{
printf ( "%d, %d (parent: %d, %d)\n", current_tile.I, current_tile.J, tile[current_tile.I][current_tile.J].ParentI, tile[current_tile.I][current_tile.J].ParentJ );

tile[current_tile.I][current_tile.J].Init ( tile[current_tile.I][current_tile.J].Sprite.X, tile[current_tile.I][current_tile.J].Sprite.Y, tile[current_tile.I][current_tile.J].I, tile[current_tile.I][current_tile.J].J, Path );

if ( tile[current_tile.I][current_tile.J].I == start_x && tile[current_tile.I][current_tile.J].J == start_y )
// if we have retraced the path back to the start
{

printf ( "Done finding path...\n" );

return;
}

current_tile.I = tile[current_tile.I][current_tile.J].ParentI;
current_tile.J = tile[current_tile.I][current_tile.J].ParentJ;
}
}

...and this part from the debug-output...
Retracing path...
4, 3 (parent: 3, 3)
3, 3 (parent: 2, 3)
2, 3 (parent: 1, 3)
1, 3 (parent: 0, 3)
0, 0 (parent: 0, 0)
0, 0 (parent: 0, 0)
0, 0 (parent: 0, 0)
0, 0 (parent: 0, 0)
[ keeps on looping ... ]

...don't really make sense together. The debug-print tells me that retracing works fine (from 4,3 to 3,3 to 2,3 to 1,3 - always jumping to the parent of the successive tile) until it reaches the last one, where (although the parent is 0,3) it jumps to tile 0,0 and then logically keeps on looping eternally. However, the piece of code suggests that the two coordinates that I print as the parent are exactly the ones I use two lines below. How can this work always unless we're coming to the final tile? I'm severely confused. Anybody with a bit of experience on this algorithm could probably give me a few pointers as to where I'm messing what up. Any help is appreciated and don't hesitate to ask for more code or clarification if necessary. I have stared at it for way too long to see anything anymore...

##### Share on other sites
I didn't read most of your post unfortunately, as I got a bit bored of reading the code! It's ok saying, "this is just a hack", but one reason why we write clear code is so that it's easier to share with other people. You may not think you need to share your personal code with others, but that is exactly what you've done here. As for advice, factor it out into separate functions. Initialisation of the data should be in a separate place, for starters.

You are pulling tiles off the open list based on cost, where cost appears to be estimated distance to the destination. Where do you factor the path cost so far into that? I don't see any code for that, and if you don't do that, it's not A*.

##### Share on other sites
Thanks for the response - and you are absolutely right.

In this version, I have exported some functions, should make it a bit more understandable, I hope:

int start_x, start_y, end_x, end_y;
std::list < CTile > open_list, closed_list;

bool get_start_and_end ( void )
// gets the start and end for a path
{
for ( int y = 0; y < TILES_Y; ++y )
// loop through columns of tiles
{
for ( int x = 0; x < TILES_X; ++x )
// loop through rows of tiles
{
if ( tile[x][y].State == Start )
{
start_x = x;
start_y = y;
}
else if ( tile[x][y].State == End )
{
end_x = x;
end_y = y;
}
else if ( tile[x][y].State == Path )
tile[x][y].Init ( tile[x][y].Sprite.X, tile[x][y].Sprite.Y, tile[x][y].I, tile[x][y].J, Empty );
}

}

if ( start_x == -1 || start_y == -1 || end_x == -1 || end_y == -1 )
// if not both start and end exist
return false;

return true;
}

void calc_costs ( void )
// calculates costs
{
printf ( "Printing costs...\n" );

// calculate cost for all tiles
for ( int y = 0; y < TILES_Y; ++y )
// loop through columns of tiles
{
for ( int x = 0; x < TILES_X; ++x )
// loop through rows of tiles
{
if ( tile[x][y].State != Solid )
// take distance from this to end
tile[x][y].Cost = calc_distance ( tile[x][y].Sprite.X, tile[x][y].Sprite.Y, tile[end_x][end_y].Sprite.X, tile[end_x][end_y].Sprite.Y );

// print cost for all tiles
printf ( "%f ", tile[x][y].Cost );
}
printf ( "\n" );
}
}

CTile get_current_tile ( void )
{
CTile current_tile;

current_tile.Cost = -1.0f;

// find the tile on the open list that has the least cost and store it as current tile
std::list < CTile > ::iterator i;
for ( i = open_list.begin ( ); i != open_list.end ( ); ++i )
// loop through open list
{
CTile temp_tile = *i;

if ( temp_tile.Cost < current_tile.Cost || current_tile.Cost == -1.0f )
// if this tile's cost is lower than the previous lowest cost or if this is the first tile
// store it
current_tile = tile[temp_tile.I][temp_tile.J];
}

return current_tile;
}

void check_for_success ( CTile current_tile )
{
if ( current_tile.I == end_x && current_tile.J == end_y )
// if we have the end as current tile
{
printf ( "Path found...\n" );

printf ( "Printing parents...\n" );

for ( int y = 0; y < TILES_Y; ++y )
// loop through columns of tiles
{
for ( int x = 0; x < TILES_X; ++x )
// loop through rows of tiles
{
// print parents for all tiles
printf ( "%d, %d | ", tile[x][y].ParentI, tile[x][y].ParentJ );
}
printf ( "\n" );
}

printf ( "Retracing path...\n" );

while ( true )
// forever
{
printf ( "%d, %d (parent: %d, %d)\n", current_tile.I, current_tile.J, tile[current_tile.I][current_tile.J].ParentI, tile[current_tile.I][current_tile.J].ParentJ );

tile[current_tile.I][current_tile.J].Init ( tile[current_tile.I][current_tile.J].Sprite.X, tile[current_tile.I][current_tile.J].Sprite.Y, tile[current_tile.I][current_tile.J].I, tile[current_tile.I][current_tile.J].J, Path );

if ( tile[current_tile.I][current_tile.J].I == start_x && tile[current_tile.I][current_tile.J].J == start_y )
// if we have retraced the path back to the start
{
printf ( "Done finding path...\n" );

return;
}

current_tile.I = tile[current_tile.I][current_tile.J].ParentI;
current_tile.J = tile[current_tile.I][current_tile.J].ParentJ;
}
}
}

{
for ( int _i = 0; _i < 8; ++_i )
{
}

printf ( "Printing adjacent tiles to current tile %d, %d...\n", current_tile.I, current_tile.J );

if ( ( current_tile.I - 1 ) > -1 && ( current_tile.J - 1 ) > -1 )
{
adj_tile[0] = tile[current_tile.I - 1][current_tile.J - 1];
printf ( "%d, %d\n", current_tile.I - 1, current_tile.J - 1 );
}

if ( ( current_tile.J - 1 ) > -1 )
{
printf ( "%d, %d\n", current_tile.I, current_tile.J - 1 );
}

if ( ( current_tile.I + 1 ) < TILES_X && ( current_tile.J - 1 ) > -1 )
{
adj_tile[2] = tile[current_tile.I + 1][current_tile.J - 1];
printf ( "%d, %d\n", current_tile.I + 1, current_tile.J - 1 );
}

if ( ( current_tile.I - 1 ) > -1 )
{
printf ( "%d, %d\n", current_tile.I - 1, current_tile.J );
}

if ( ( current_tile.I + 1 ) < TILES_X )
{
printf ( "%d, %d\n", current_tile.I + 1, current_tile.J );
}

if ( ( current_tile.I - 1 ) > -1 && ( current_tile.J + 1 ) < TILES_Y )
{
adj_tile[5] = tile[current_tile.I - 1][current_tile.J + 1];
printf ( "%d, %d\n", current_tile.I - 1, current_tile.J + 1 );
}

if ( ( current_tile.J + 1 ) < TILES_Y )
{
printf ( "%d, %d\n", current_tile.I, current_tile.J + 1 );
}

if ( ( current_tile.I + 1 ) < TILES_X && ( current_tile.J + 1 ) < TILES_Y )
{
adj_tile[7] = tile[current_tile.I + 1][current_tile.J + 1];
printf ( "%d, %d\n", current_tile.I + 1, current_tile.J + 1 );
}
}

{
for ( std::list < CTile > ::iterator i = closed_list.begin ( ); i != closed_list.end ( ); ++i )
// loop through closed list
{
CTile temp_tile = *i;

// if adjacent tile is on closed list
// store result and end search
return true;
}

return false;
}

{
for ( std::list < CTile > ::iterator i = open_list.begin ( ); i != open_list.end ( ); ++i )
// loop through closed list
{
CTile temp_tile = *i;

// if adjacent tile is on open list
// store result and end search
return true;
}

return false;
}

void calc_path ( void )
// calculates path
{
// init start and end
start_x = start_y = end_x = end_y = -1;

// init open and close list
open_list.erase ( open_list.begin ( ), open_list.end ( ) );
closed_list.erase ( closed_list.begin ( ), closed_list.end ( ) );

if ( !get_start_and_end ( ) )
// if not both start and end exist
// do nothing
return;

printf ( "Calculating path from %d, %d to %d, %d...\n", start_x, start_y, end_x, end_y );

// calculate costs
calc_costs ( );

// add start tile to open list
open_list.push_back ( tile[start_x][start_y] );
printf ( "Start tile %d, %d added to open list...\n", start_x, start_y );

while ( !open_list.empty ( ) )
// while open list is filled
{
// get tile with lowest cost on open list
CTile current_tile = get_current_tile ( );
printf ( "Current tile (with lowest cost on open list) is %d, %d with cost %f...\n", current_tile.I, current_tile.J, current_tile.Cost );

// check whether we have found a path
check_for_success ( current_tile );

// add current tile to closed list
closed_list.push_back ( current_tile );

// and take it off open list
for ( std::list < CTile > ::iterator i = open_list.begin ( ); i != open_list.end ( ); ++i )
// loop through open list
{
CTile temp_tile = *i;

if ( temp_tile.I == current_tile.I && temp_tile.J == current_tile.J )
// get current tile
{
// take current tile off of open list and end search
open_list.erase ( i );
break;
}

}

printf ( "Current tile added to closed and taken off of open list...\n" );

// find and store adjacent tiles

for ( int _i = 0; _i < 8; ++_i )
{
{
if ( adj_tile[_i].State != Solid )
// if adjacent tile is not a wall
{
// if adjacent tile is not on closed list
{
// if adjacent tile is not on open list
{

// set parent-relation

}
/*else
{
// unsure here
}*/

}
}
}
}
}

printf ( "No possible path found...\n" );
}

Quote:
 You are pulling tiles off the open list based on cost, where cost appears to be estimated distance to the destination. Where do you factor the path cost so far into that? I don't see any code for that, and if you don't do that, it's not A*.

Could you be a bit more specific? I think I know what you mean, but I'm not that sure, I think that this is the exact same part that's also described quite hastily in the paper I linked to in the original post.

I don't think this could be causing my problem, though?

##### Share on other sites
A* picks the next node based on actual cost so far plus estimated cost to go. You often see this described as F = G + H. Without the cost so far it degenerates to a simple best-first search (which isn't guaranteed to get you the shortest path), and without the heuristic it degenerates to a breadth-first search (which is inefficient). This total of both is the sorting criteria for the open list. It also cannot be precomputed, as it necessarily includes the distance travelled so far (otherwise, you couldn't possibly know this was the shortest path).

I suggest you take a look at 2 or 3 A* tutorials, because often they are ambiguously worded and it's easier to understand the fundamentals when you cross references more than one source.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 14
• 46
• 22
• 27
• ### Forum Statistics

• Total Topics
634047
• Total Posts
3015230
×