Results 1 to 4 of 4
  1. #1
    Zee Best is offline Member
    Join Date
    Oct 2011
    Posts
    1
    Rep Power
    0

    Default 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. #2
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default 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. #3
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    12,014
    Rep Power
    20

    Default 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. #4
    DiamondSoul is offline Member
    Join Date
    Oct 2011
    Posts
    83
    Rep Power
    0

    Default Re: Path solving algorithm/method help needed!

    Quote Originally Posted by Tolls View Post
    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-19-2011 at 11:09 PM.

Similar Threads

  1. Replies: 0
    Last Post: 03-20-2011, 01:17 AM
  2. Help Needed in Solving the Following Isuue.
    By raju.i in forum Advanced Java
    Replies: 3
    Last Post: 05-14-2010, 05:01 PM
  3. Help needed in setting the jdk path
    By ramachandran in forum Eclipse
    Replies: 2
    Last Post: 05-05-2010, 01:18 AM
  4. Replies: 0
    Last Post: 08-24-2008, 04:27 PM
  5. I need a help in solving this method using vectors
    By java_fun2007 in forum New To Java
    Replies: 2
    Last Post: 11-26-2007, 07:51 PM

Posting Permissions

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