Results 1 to 4 of 4
 10172011, 02:00 AM #1Member
 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.
 10172011, 02:31 AM #2
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,069
 Blog Entries
 3
 Rep Power
 9
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 Breadthfirst 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.
 10172011, 10:25 AM #3Moderator
 Join Date
 Apr 2009
 Posts
 12,318
 Rep Power
 20
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.
 10182011, 01:32 AM #4Member
 Join Date
 Oct 2011
 Posts
 83
 Rep Power
 0
Re: Path solving algorithm/method help needed!
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 0walkable, 1target, 2blocked, 3object. 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+maxxminx][1+maxyminy]; for(int x=minx;x<=maxx;x++) for(int y=miny;y<=maxy;y++) obj[xminx][yminy]=map[x][y]==3; //make the metamap int[][] meta=new int[map.length+maxxminx][map[0].length+maxyminy]; 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]; } }
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; 10192011 at 11:09 PM.
Similar Threads

implementing an algorithm for shortest path problem in java
By thorobred in forum New To JavaReplies: 0Last Post: 03202011, 02:17 AM 
Help Needed in Solving the Following Isuue.
By raju.i in forum Advanced JavaReplies: 3Last Post: 05142010, 05:01 PM 
Help needed in setting the jdk path
By ramachandran in forum EclipseReplies: 2Last Post: 05052010, 01:18 AM 
[SOLVED] Algorithm for solving 2 equations, 2 unknowns
By Norm in forum Advanced JavaReplies: 0Last Post: 08242008, 04:27 PM 
I need a help in solving this method using vectors
By java_fun2007 in forum New To JavaReplies: 2Last Post: 11262007, 08:51 PM
Bookmarks