# Thread: Path solving algorithm/method help needed!

1. Member
Join Date
Oct 2011
Posts
1
Rep Power
0

## Path solving algorithm/method help needed!

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.

2. ## Re: Path solving algorithm/method help needed!

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.

3. Moderator
Join Date
Apr 2009
Posts
11,302
Rep Power
18

## Re: Path solving algorithm/method help needed!

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.

4. Member
Join Date
Oct 2011
Posts
83
Rep Power
0

## Re: Path solving algorithm/method help needed!

Originally Posted by 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.
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:

Java Code:
```//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.
Last edited by DiamondSoul; 10-20-2011 at 12:09 AM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•