A* implementation glitchy

Started by d h k July 24, 2008 02:44 PM

2 comments, last by Kylotan 16 years, 3 months ago

Author

439

July 24, 2008 02:44 PM

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
		CTile adj_tile[8];

		for ( int _i = 0; _i < 8; ++_i )
		{
			adj_tile[_i].I = -1;
			adj_tile[_i].J = -1;
		}

		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 )
		{
			adj_tile[1] = tile[current_tile.I][current_tile.J - 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 )
		{
			adj_tile[3] = tile[current_tile.I - 1][current_tile.J];
			printf ( "%d, %d\n", current_tile.I - 1, current_tile.J );
		}

		if ( ( current_tile.I + 1 ) < TILES_X )
		{
			adj_tile[4] = tile[current_tile.I + 1][current_tile.J];
			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 )
		{
			adj_tile[6] = tile[current_tile.I][current_tile.J + 1];
			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 )
		// loop through adjacent tiles
		{
			if ( adj_tile[_i].I > -1 && adj_tile[_i].J > -1 )
			{
				if ( adj_tile[_i].State != Solid )
				// if adjacent tile is not a wall
				{
					bool adj_tile_on_closed_list = false;

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

						if ( temp_tile.I == adj_tile[_i].I && temp_tile.J == adj_tile[_i].J )
						// if adjacent tile is on closed list
						{
							// store result and end search
							adj_tile_on_closed_list = true;

							break;
						}
					}
					
					if ( !adj_tile_on_closed_list )
					// if adjacent tile is not on closed list
					{
						bool adj_tile_on_open_list = false;

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

							if ( temp_tile.I == adj_tile[_i].I && temp_tile.J == adj_tile[_i].J )
							// if adjacent tile is on open list
							{
								// store result and end search
								adj_tile_on_open_list = true;

								break;
							}
						}

						if ( !adj_tile_on_open_list )
						// if adjacent tile is not on open list
						{
							// add adjacent tile to open list
							open_list.push_back ( tile[adj_tile[_i].I][adj_tile[_i].J] );

							printf ( "Added adjacent tile %d, %d to open list...\n", adj_tile[_i].I, adj_tile[_i].J );

							// set parent-relation
							tile[adj_tile[_i].I][adj_tile[_i].J].ParentI = tile[current_tile.I][current_tile.J].I;
							tile[adj_tile[_i].I][adj_tile[_i].J].ParentJ = tile[current_tile.I][current_tile.J].J;

							printf ( "Adjacent tile %d, %d has a new parent: %d, %d...\n", adj_tile[_i].I, adj_tile[_i].J, tile[adj_tile[_i].I][adj_tile[_i].J].ParentI, tile[adj_tile[_i].I][adj_tile[_i].J].ParentJ );
						}
					}
				}
			}
		}
	}

	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
Added adjacent tile 1, 0 to open list...
Adjacent tile 1, 0 has a new parent: 2, 1...
Added adjacent tile 2, 0 to open list...
Adjacent tile 2, 0 has a new parent: 2, 1...
Added adjacent tile 3, 0 to open list...
Adjacent tile 3, 0 has a new parent: 2, 1...
Added adjacent tile 1, 1 to open list...
Adjacent tile 1, 1 has a new parent: 2, 1...
Added adjacent tile 3, 1 to open list...
Adjacent tile 3, 1 has a new parent: 2, 1...
Added adjacent tile 1, 2 to open list...
Adjacent tile 1, 2 has a new parent: 2, 1...
Added adjacent tile 2, 2 to open list...
Adjacent tile 2, 2 has a new parent: 2, 1...
Added adjacent tile 3, 2 to open list...
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
Added adjacent tile 1, 3 to open list...
Adjacent tile 1, 3 has a new parent: 2, 2...
Added adjacent tile 2, 3 to open list...
Adjacent tile 2, 3 has a new parent: 2, 2...
Added adjacent tile 3, 3 to open list...
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
Added adjacent tile 1, 4 to open list...
Adjacent tile 1, 4 has a new parent: 2, 3...
Added adjacent tile 2, 4 to open list...
Adjacent tile 2, 4 has a new parent: 2, 3...
Added adjacent tile 3, 4 to open list...
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
Added adjacent tile 0, 2 to open list...
Adjacent tile 0, 2 has a new parent: 0, 3...
Added adjacent tile 1, 2 to open list...
Adjacent tile 1, 2 has a new parent: 0, 3...
Added adjacent tile 1, 3 to open list...
Adjacent tile 1, 3 has a new parent: 0, 3...
Added adjacent tile 0, 4 to open list...
Adjacent tile 0, 4 has a new parent: 0, 3...
Added adjacent tile 1, 4 to open list...
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
Added adjacent tile 2, 2 to open list...
Adjacent tile 2, 2 has a new parent: 1, 3...
Added adjacent tile 2, 3 to open list...
Adjacent tile 2, 3 has a new parent: 1, 3...
Added adjacent tile 2, 4 to open list...
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
Added adjacent tile 3, 2 to open list...
Adjacent tile 3, 2 has a new parent: 2, 3...
Added adjacent tile 3, 3 to open list...
Adjacent tile 3, 3 has a new parent: 2, 3...
Added adjacent tile 3, 4 to open list...
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
Added adjacent tile 4, 2 to open list...
Adjacent tile 4, 2 has a new parent: 3, 3...
Added adjacent tile 4, 3 to open list...
Adjacent tile 4, 3 has a new parent: 3, 3...
Added adjacent tile 4, 4 to open list...
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...

Kylotan

10,513

July 25, 2008 04:32 AM

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

d h k

Author

439

July 25, 2008 09:58 AM

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;		}	}}void get_adj_tiles ( CTile current_tile, CTile adj_tile[8] ){	for ( int _i = 0; _i < 8; ++_i )	{		adj_tile[_i].I = -1;		adj_tile[_i].J = -1;	}	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 )	{		adj_tile[1] = tile[current_tile.I][current_tile.J - 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 )	{		adj_tile[3] = tile[current_tile.I - 1][current_tile.J];		printf ( "%d, %d\n", current_tile.I - 1, current_tile.J );	}	if ( ( current_tile.I + 1 ) < TILES_X )	{		adj_tile[4] = tile[current_tile.I + 1][current_tile.J];		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 )	{		adj_tile[6] = tile[current_tile.I][current_tile.J + 1];		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 );	}}bool adj_tile_on_closed_list ( CTile adj_tile[8], int _i ){	for ( std::list < CTile > ::iterator i = closed_list.begin ( ); i != closed_list.end ( ); ++i )	// loop through closed list	{		CTile temp_tile = *i;		if ( temp_tile.I == adj_tile[_i].I && temp_tile.J == adj_tile[_i].J )		// if adjacent tile is on closed list			// store result and end search			return true;	}	return false;}bool adj_tile_on_open_list ( CTile adj_tile[8], int _i ){	for ( std::list < CTile > ::iterator i = open_list.begin ( ); i != open_list.end ( ); ++i )	// loop through closed list	{		CTile temp_tile = *i;		if ( temp_tile.I == adj_tile[_i].I && temp_tile.J == adj_tile[_i].J )		// 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 ( ) );	// read start and 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		CTile adj_tile[8];		get_adj_tiles ( current_tile, adj_tile );				for ( int _i = 0; _i < 8; ++_i )		// loop through adjacent tiles		{			if ( adj_tile[_i].I > -1 && adj_tile[_i].J > -1 )			{				if ( adj_tile[_i].State != Solid )				// if adjacent tile is not a wall				{					if ( !adj_tile_on_closed_list ( adj_tile, _i ) )					// if adjacent tile is not on closed list					{						if ( !adj_tile_on_open_list ( adj_tile, _i ) )						// if adjacent tile is not on open list						{							// add adjacent tile to open list							open_list.push_back ( tile[adj_tile[_i].I][adj_tile[_i].J] );							printf ( "Added adjacent tile %d, %d to open list...\n", adj_tile[_i].I, adj_tile[_i].J );							// set parent-relation							tile[adj_tile[_i].I][adj_tile[_i].J].ParentI = tile[current_tile.I][current_tile.J].I;							tile[adj_tile[_i].I][adj_tile[_i].J].ParentJ = tile[current_tile.I][current_tile.J].J;							printf ( "Adjacent tile %d, %d has a new parent: %d, %d...\n", adj_tile[_i].I, adj_tile[_i].J, tile[adj_tile[_i].I][adj_tile[_i].J].ParentI, tile[adj_tile[_i].I][adj_tile[_i].J].ParentJ );						}						/*else						// if adjacent tile is on the open list already						{							// 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?

Kylotan

10,513

July 28, 2008 10:28 AM

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.

A* implementation glitchy

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

A* implementation glitchy

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines