Path solving algorithm/method help needed!

[Zee Best]

Basically, im trying to create a method which solves a path for a Rectangle to move to get to a specific location.

For example;

Here is a sample grid;



I need to get the pink rectangle to the blue tile, however, the red tiles are blocked, meaning the path would have to go around the red tiles.

I don't know the easiest way to work this out... I have tried many times to try and figure out a way but it doesn't seem to work.

If anyone could help i would really appreciate it.

[sunde887]

I'm probably not the best person to help out with this, but I'll give you some advice while you wait, and if it is poor, hopefully others will correct me. You can try a Breadth-first search - Wikipedia, the free encyclopedia

Basically generate each possible move, determine if it is legal or if you reached the desired position, then recursively call the method on each of the possible methods.

[Tolls]

I'm thinking a modified form of A*.
Modified because the basic A* has an object that's the same size as the squares it's moving through, and your object is bigger...so each move will have to check that none of the 4 obect squares are in a red square. Shouldn't be too hard.

[DiamondSoul]

I'm thinking a modified form of A*.
Modified because the basic A* has an object that's the same size as the squares it's moving through, and your object is bigger...so each move will have to check that none of the 4 obect squares are in a red square. Shouldn't be too hard.

Yep, and the modification wouldn't be too hard. What I would do is generate a sort of "meta map" of all the spots on the grid that the upper left corner of the object can occupy.

For example, suppose your main map is a 2d array of ints where 0-walkable, 1-target, 2-blocked, 3-object. The meta map would be generated as follows:

//find the minimum size rectangle containing the object
int minx=0,maxx=0,miny=0,maxy=0;
boolean foundobj=false;
for(int x=0;x<map.length;x++){
    for(int y=0;y<map[0].length;y++){
        if(map[x][y]==3){
            if(foundobj){
                if(x<minx) minx=x;
                if(x>maxx) maxx=x;
                if(y<miny) miny=y;
                if(y>maxy) maxy=y;
            }else{
                foundobj=true;
                minx=maxx=x;
                miny=maxy=y;
            }
        }
    }
}

//store the object's shape in a 2d boolean array
boolean[][] obj=new boolean[1+maxx-minx][1+maxy-miny];
for(int x=minx;x<=maxx;x++) for(int y=miny;y<=maxy;y++) obj[x-minx][y-miny]=map[x][y]==3;

//make the metamap
int[][] meta=new int[map.length+maxx-minx][map[0].length+maxy-miny];
for(int x=0;x<meta.length;x++){
    for(int y=0;y<meta[0].length;y++){
        meta[x][y]=0;
        for(int xx=0;xx<obj.length;xx++)
            for(int yy=0;yy<obj[0].length;yy++)
                if(map[x+xx][y+yy]>meta[x][y] && map[x+xx][y+yy]<3 && obj[xx][yy])
                    meta[x][y]=map[x+xx][y+yy];
    }
}

Now use A* on the metamap to navigate from (minx,miny) to one of the target squares on the metamap.


edit: just realized I was inconsistent in my use of "main" and "map" to describe the original map array. Changed them all to "map" now.