Pathfinding?

Contests 4K Game Competition - 2009
#1

I want to use Dijkstra for my game. I tried BFS but it returned me ugly paths. Yes, I know, I’m very picky :-\

I do have Dijkstra implemented already, but my implementation is way too big for a 4K game, 180 lines…which I could probably optimize down to 140 lines quite easily as I’ve not done any optimization on it.

The data structures is really what is taking up lots of space. Having to maintain a sorted open list and also a closed list takes up some space. Not to mention performing operations on those! (check if in open/closed, add, remove).

So, what I wanted to discuss here are good ways to implement something like a 4K-pathfinder (Dijkstra preferred) that can be applied on a tile[cols][rows] map.

What have people done here in the past?

#2

Can’t you get away with floodfill? It’s extremely small to implement and ‘fast enough’.

Walk over an int[w*h] for every iteration, and set the value of the empty cells next to the ‘last age’ to ‘current age’. Extremely inefficient, but maybe 3 or 4 lines of code to find the target - then a few lines to trace back. :slight_smile:

#3

For my game the path quality does matter. Flood-fills doesn’t return me the shortest path. ?

#4

BFS will find optimal paths. Since you’ve a relatively small grid, I can’t see why you wouldn’t want to use that?

#5

Yes it does. As Riven said, once the fill has found the destination, you backtrack to find the path. I.E. from the destination square, move to an adjacent square with the lowest iteration (or cost) number. Keep doing this until you get back to the start. You’ve just followed one of the shortest paths.

BTW, what criteria are you using to define which path is shortest through the grid? For instance do you prefer diagonal movements over up/down? Can you move at different speeds along the path?

If we knew a bit more about the path finding problem you want to solve maybe we’d be able to give some more specific help.

Cheers, Tim.

#6

Ok, I’ll take a look at it.

I prefer diagonal movement where it applies, e.g. going from bottom-left to top-right.

#7

Here’s a quick example implementation of using a flood fill to find the shortest path. It’s not been optimised for size. :slight_smile:


class PathFinder
{
	public static void main( String[] args )
	{
		final int W = 20;
		final int H = 15;
		final int SIZE = W * H;

		int[]	grid = new int[SIZE];

		// mark edges of grid.
		for( int i = 0; i < W; i++ )
			grid[i] = grid[SIZE - W + i] = -1;
		for( int i = 0; i < H; i++ )
			grid[i * W] = grid[W - 1 + i * W] = -1;

		int START = 1 + 1 * W;	// bottom left.
		int END   = (W - 2) + (H - 2) * W;	// top right.

		// grid offsets for the 8 main directions.
		final int[] OFFS = { -1, 1, -W, W, -1-W, 1-W, -1+W, 1+W };

		// add in some random obstacles...
		for( int i = 0; i < SIZE / 4; i++ )
			grid[(int)(Math.random() * SIZE)] = -1;

		// initialise dist for start.
		grid[START] = 1;
		grid[END]	= 0;

		// flood fill
		boolean changed = true;
		int count;
		for( count = 2; changed; count++ )
		{
			changed = false;
			for( int from = 0; from < SIZE; from++ )
			{
				if( grid[from] == count - 1 )
				{
					for( int dir = 0; dir < 8; dir++ )
					{
						int to = from + OFFS[dir];

						if( grid[to] == 0 || count < grid[to] )
						{
							grid[to] = count;
							changed = true;
						}
					}
				}
			}
		}

		// adjust count (started from 1, counted 1 extra -- need to subtract 2)
		count -= 2;

		if( grid[END] == 0 )
		{
			// failed to reach end.
			System.out.println( "Failed to find a path from START to END" );
		}
		else
		{
			// backtrack to get one of the shortest paths.
			int[] path = new int[count];
			int from = END;
			path[--count] = from;
			while( count > 0 )
			{
				// search for lowest value.
				int best = END;
				for( int dir = 0; dir < 8; dir++ )
				{
					int to = from + OFFS[dir];
	
					if( grid[to] > 0 && grid[best] > grid[to] )
					{
						best = to;
					}
				}
	
				from = best;
				path[--count] = from;
			}

			// dump path.
			for( int i = 0; i < path.length; i++ )
			{
				System.out.format( "%02d: (%2d, %2d)\n", i, path[i] % W, path[i] / W );

				// update grid to show path.
				grid[path[i]] = 99;
			}
		}

		// dump grid.
		System.out.println();
		for( int y = H - 1; y >= 0; y-- )
		{
			System.out.printf( "%2d ", y );
			for( int x = 0; x < W; x++ )
			{
				int i = x + y * W;
				if( i == START )
					System.out.print( " S " );
				else if( i == END )
					System.out.print( " E " );
				else if( grid[i] == 99 )
					System.out.print( " @ " );
				else if( grid[i] < 0 )
					System.out.print( "###" );
				else
					System.out.print( " - " );
//					System.out.printf( "[%02d]", grid[i] );
			}
			System.out.println();
		}
		System.out.print( "  " );
		for( int x = 0; x < W; x++ )
		{
			System.out.printf( " %02d", x );
		}
		System.out.println();
	}
}
#8

If a diagonal step is as fast as a straight step, floodfill will do the trick.

I’ll try to post a minimalistic floodfill impl tonight.

#9

From what I’ve read it seems to be BFS with visit-cost added. And then a slightly different traversal code to return the path once goal is found.

The default flood-fill algorithm is DFS, which is not good for pathfinding. I’ll need a queue, to explore on breadth.