so here is my C++ code.
void find_path( int width, int height, int x, int y, char** &grid, int path_count, char** &path, int &shortest)
{
// base case: found 'E' return the path_count-1
if( grid[y][x] == 'E' )
{
if( shortest > path_count )
{
shortest = path_count-1;
copy_gridArray( width, height, grid, path );
return;
}
}
if( grid[y][x] == '-' || grid[y][x] == '*' )
return;
// go right
if( x+1 < width )
{
grid[y][x] = '-';
find_path( width, height, x+1, y, grid, path_count+1, path, shortest );
grid[y][x] = ' ';
}
// go up
if( y-1 >= 0 )
{
grid[y][x] = '-';
find_path( width, height, x, y-1, grid, path_count+1, path, shortest );
grid[y][x] = ' ';
}
// go left
if( x-1 >= 0 )
{
grid[y][x] = '-';
find_path( width, height, x-1, y, grid, path_count+1, path, shortest );
grid[y][x] = ' ';
}
// go down
if( y+1 < height )
{
grid[y][x] = '-';
find_path( width, height, x, y+1, grid, path_count+1, path, shortest );
grid[y][x] = ' ';
}
}
this is native C++ fyi... so, the idea is that we read in this file that represents a maze using string of characters '*' represents a wall and 'E' represents end point. given a starting position we find ALL possible routes and determine the shortest. we determine the shortest path for like 8 mazes in one file and this is all done in under a second (not sure the actual time)! so this is much faster than some would think. but there is optimizing that can be done im sure. but basically, as you traverse the 2d grid, if you have been in that spot before, you mark it with a '-'. when you reach the shortest path, you print out the path.
here is the step i take:
1) base case: (each recursive function MUST have a base case of some sort so it can exit out properly) if current position = 'E' and if shortest path is > than the current steps counted, shortest path = current steps counted. copy the grid array(or, the solution... this should be programmed differently. im copying the grid array because i am printing it out, you should not though..)
2) base case has not been met: if current position = '-' or '*' then return.
3) check all directions. if next move does not exceed array bounds, then mark that spot as taken or in this case '-'. call itself with new position. when function returns, take out the '-'. this is so it permeates all possibilities.
and that is pretty much how it works. i know it can be kind of a mind sore but its really efficient for what it does. so you can have a complex 3d level with complex geometry and the works but if you have a collision layer of the level representing primitives, like 16x16x16 unit cubes say, and store it into a 2d array. this will work.
questions? i know this is kind of hard to understand...it was for me.
If at first you dont succeed, call it version 1.0.
