Page 1 of 2 12 LastLast
Results 1 to 20 of 31

Thread: Recursion.

  1. #1
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default Recursion.

    Java Code:
    public int findShortestPath (int fromx, int fromy, int tox, int toy)
        {
            squares [fromx] [fromy].check = false;
            if (isTouching (fromx, fromy, tox, toy))
            {
                System.out.println ("");
                return 1;
            }
            else
            {
                int[] paths = new int [4];
                if (fromx < 11 && squares [fromx + 1] [fromy].check)
                    paths [0] = findShortestPath (fromx + 1, fromy, tox, toy);
                else
                    paths [0] = 10000;
                if (fromx > 0 && squares [fromx - 1] [fromy].check)
                    paths [1] = findShortestPath (fromx - 1, fromy, tox, toy);
                else
                    paths [1] = 10000;
                if (fromy < 13 && squares [fromx] [fromy + 1].check)
                    paths [2] = findShortestPath (fromx, fromy + 1, tox, toy);
                else
                    paths [2] = 10000;
                if (fromy > 0 && squares [fromx] [fromy - 1].check)
                    paths [3] = findShortestPath (fromx, fromy - 1, tox, toy);
                else
                    paths [3] = 10000;
                System.out.println ("" + (smallest (paths) + 1));
                return smallest (paths) + 1;
            }
        }
    okay, if any of you have played Desktop Tower Defense you may be able to understand this easier.

    Basically it's a game and like any other tower defense the creeps move through the maze, however the maze isn't predifined, it needs to find it's way to the end.

    what this method is called it first checks if it's touching the destination square, if it is then return 1, because distance is 1. otherwise it calls this method again for every square around it that isn't outside of the grid, and hasn't been called already, or has a blocking object in that square.

    if i set all squares.check to false before hand, since my grid is 12x14, the shortest path should be 26, but it's returning 156(starting at 0,0)

    Recursive methods are hard to troubleshoot, any help?

  2. #2
    JavaRulez is offline Member
    Join Date
    May 2010
    Posts
    26
    Rep Power
    0

    Default

    Well, first off, if you set all your squares[][].check to false, shouldn't the method fail?

    Have you ever played Trade Wars 2002? Maybe not, but it's a similar problem, mapping a randomized network. I'd pass the path through as an argument, then return the path if you've reached the end or null if you've hit a dead-end (all neighboring squares checked already). Similarly, when you make the recursive calls, if they return null, ignore them, if they return a path to the end, compare them and return the shortest path. Should work.

    Edited to point out, setting check to false will cause you problems, you should use the path to determine where you've been (for that specific trail of recursion) as sometimes the shortest path may go through sectors which were part of a longer path but the shortest path may be in the last direction you check.
    Last edited by JavaRulez; 05-09-2010 at 10:20 AM.

  3. #3
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    sorry they all start at true.

    and if i didn't set the check to false after it had been checked, it would keep making method calls and stack overflow before it even reaches the end, i figured that the shortest path will get there the quickest so there would be no time for a differant path to check that square no?

    and tracing the actual path that the method follows was my next problem, haven't got there yet, kinda scared lol.

  4. #4
    JavaRulez is offline Member
    Join Date
    May 2010
    Posts
    26
    Rep Power
    0

    Default

    Quote Originally Posted by Cruncher View Post
    i figured that the shortest path will get there the quickest so there would be no time for a differant path to check that square no?
    That's not how recursion works, you check east first, so you'll end up checking all the way east to the edge before any other direction is tried. If you're working with a maze you risk building a wall of checked == true.

  5. #5
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    I can't think of how i would do that?

    keep calling east until hitting a wall? then keep calling south? then keep calling west? then north?

    that will get us to the end eventually i'm sure, but will it be the shortest path? and that seems more like a simple loop to me then a recursive method :S

  6. #6
    JavaRulez is offline Member
    Join Date
    May 2010
    Posts
    26
    Rep Power
    0

    Default

    Yes it will find the end, no it won't be the shortest path.
    This is exactly what you are doing now, running around the edge (finding the exit, how could you not?) but blocking the shortest path by setting checked == true.

  7. #7
    JavaRulez is offline Member
    Join Date
    May 2010
    Posts
    26
    Rep Power
    0

    Default

    This is why you get 156, it never returns the shortest path unless the shortest path is the first one it tries. It always returns the first path.

  8. #8
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    How can i get it to find the shortest path, that's really the key here, because although for testing nothing will be blocking, but there will be blockades and i do need to find the shortest path.

  9. #9
    JavaRulez is offline Member
    Join Date
    May 2010
    Posts
    26
    Rep Power
    0

    Default

    The way I described will work, also you could reset check back to true at the end of the method (make sure you do this before returning!)

    Although you said you need the path anyway, so use some Collection to store previous coordinates, add the coordinates of the room you're in and pass that collection to your recursive calls. Just don't go into rooms which are already in your path.

  10. #10
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    This could work, thanks i'll give'r a try.

    By the way, is Collection a class? never used it. is it similar to ArrayList where i can just add and remove? would an ArrayList work too? (used to them)

  11. #11
    JavaRulez is offline Member
    Join Date
    May 2010
    Posts
    26
    Rep Power
    0

    Default

    ArrayList is part of the Collections framework.
    Also, I think you'll want to make a copy of the list for your four recursive calls, to keep them separate.

  12. #12
    JavaRulez is offline Member
    Join Date
    May 2010
    Posts
    26
    Rep Power
    0

    Default

    I hope I have explained it well, and if so, it will work, as I have used it to map a network of 10,000 randomly connected "sectors"

  13. #13
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    Thanks, if i run into issues along the way i'll reply here, but for now, thanks a lot.

  14. #14
    JavaRulez is offline Member
    Join Date
    May 2010
    Posts
    26
    Rep Power
    0

    Default

    Here is a really old application of the idea, completely raw, I just copied it out of an old source file. This may not be optimal, but if you can read code, it might help.

    This isn't recursive by the way, so it does find the shortest path first. But notice how each Path object keeps track of where it's been so that it doesn't retrace it's steps, but each Path has no care about where the other Paths have been, that is the key.

    =Edit= Now that I look at it again, the Paths do care about where the other Paths have been, this was to speed up the process on very large maps. You're recursive approach will be easier to code and plenty fast enough for a small map.

    Java Code:
      public class PathFinder {
    
        private class Path {
          int distance;
          public int[] path;
          DataThread data;
          boolean foundit;
          boolean dead;
    
          public Path(DataThread dt, int[] prevpath) {
            distance = prevpath.length;
            data = dt;
            foundit = false;
            dead = false;
            path = new int[prevpath.length];
            for (int i = 0; i < path.length; i++) {
              path[i] = prevpath[i];
            }
          }
    
          public Path[] step(ArrayList<Integer> avoids, int destination) {
            if (dead) return new Path[0];
            SectorObject sobj = data.getSector(path[path.length-1]);
            if (sobj.id == destination) {
              foundit = true;
              return new Path[0];
            }
            int[] newpath = new int[path.length+1];
            int n = 0;
            for (n = 0; n < path.length; n ++) {
              newpath[n] = path[n];
            }
            Path[] temp = new Path[sobj.warps.length];
            for (int i = 0; i < temp.length; i ++) {
              newpath[newpath.length-1] = sobj.warps[i];
              temp[i] = new Path(data, newpath);
              if (avoids.contains(new Integer(newpath[newpath.length-1]))) temp[i].dead = true;
              else avoids.add(new Integer(newpath[newpath.length-1]));
            }
            return temp;
          }
    
        }
    
        private ArrayList<Integer> allvisited;
        private Path[] livepaths;
        public boolean nopath;
        public Path bestpath;
    
        public PathFinder(DataThread dt, int startsector, int endsector) {
          livepaths = new Path[1];
          nopath = true;
          allvisited = new ArrayList<Integer>();
          allvisited.add(new Integer(startsector));
          int[] temp = new int[1];
          temp[0] = startsector;
          livepaths[0] = new Path(dt, temp);
          boolean done = false;
          int jumpcount = 0;
          while (!done && jumpcount < NUMSECTORS) {
            jumpcount ++;
            Path[] newpaths = new Path[0];
            for (int i = 0; i < livepaths.length; i++) {
              Path[] paths = livepaths[i].step(allvisited, endsector);
              if (paths.length == 0) {
                if (livepaths[i].foundit) {
                  nopath = false;
                  bestpath = livepaths[i];
                  done = true;
                }
              } else {
                Path[] tempnewpaths = new Path[newpaths.length + paths.length];
                int n = 0;
                for (n = 0; n < newpaths.length; n ++) {
                  tempnewpaths[n] = newpaths[n];
                }
                for (int c = 0; c < paths.length; c ++) {
                  tempnewpaths[n+c] = paths[c];
                }
                newpaths = tempnewpaths;
              }
            }
            if (newpaths.length == 0) done = true;
            else livepaths = newpaths;
          }
        }
    
      }
    Last edited by JavaRulez; 05-09-2010 at 02:05 PM.

  15. #15
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    I'm having a hard time reading how your code works to be honest :/.

    But this was my attempt:

    Java Code:
        public ArrayList findShortestPath (int fromx, int fromy, int tox, int toy, ArrayList path)
        {
            ArrayList temp = path;
            ArrayList[] temps = new ArrayList [4];
            temp.add (squares [fromx] [fromy]);
            if (isTouching (fromx, fromy, tox, toy))
            {
                return temp;
            }
            else
            {
                int[] paths = new int [4];
                if (fromx < 11 && !squares [fromx + 1] [fromy].block && !temp.contains (squares [fromx + 1] [fromy]))
                    temps [0] = findShortestPath (fromx + 1, fromy, tox, toy, temp);
                else
                    temps [0] = null;
                if (fromy < 13 && !squares [fromx] [fromy + 1].block && !temp.contains (squares [fromx] [fromy + 1]))
                    temps [2] = findShortestPath (fromx, fromy + 1, tox, toy, temp);
                else
                    temps [2] = null;
                if (fromx > 0 && !squares [fromx - 1] [fromy].block && !temp.contains (squares [fromx - 1] [fromy]))
                    temps [1] = findShortestPath (fromx - 1, fromy, tox, toy, temp);
                else
                    temps [1] = null;
                if (fromy > 0 && !squares [fromx] [fromy - 1].block && !temp.contains (squares [fromx] [fromy - 1]))
                    temps [3] = findShortestPath (fromx, fromy - 1, tox, toy, temp);
                else
                    temps [3] = null;
                for (int i = 0 ; i < 3 ; i++)
                    if (temps [i] != null)
                        paths [i] = temps [i].size ();
                    else
                        paths [i] = 10000;
                return temps [smallest (paths)];
            }
        }
    But when i call it with

    ArrayList path = findShortestPath (0, 0, 11, 13, new ArrayList ());

    I get null.

  16. #16
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    Oh and i edited smallest to return the smallest numbers index, rather than the smallest number:

    Java Code:
    public int smallest (int[] nums)
        {
            int smallest = nums [0];
            int smallestIndex = 0;
            for (int i = 1 ; i < nums.length ; i++)
            {
                if (nums [i] < smallest)
                {
                    smallest = nums [i];
                    smallestIndex = i;
                }
            }
    
    
            return smallestIndex;
        }

  17. #17
    JavaRulez is offline Member
    Join Date
    May 2010
    Posts
    26
    Rep Power
    0

    Default

    I see one problem right off:
    Java Code:
    for (int i = 0 ; i < 3 ; i++)
                    if (temps [i] != null)
                        paths [i] = temps [i].size ();
                    else
                        paths [i] = 10000;
                return temps [smallest (paths)];
    Shouldn't taht i<3 be i<4?

  18. #18
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    it should be :| hold on... lol...

  19. #19
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    fixed that, i'm getting 167 for the ArrayList size now :/

  20. #20
    JavaRulez is offline Member
    Join Date
    May 2010
    Posts
    26
    Rep Power
    0

Page 1 of 2 12 LastLast

Similar Threads

  1. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 07:26 PM
  2. Recursion
    By kathyla18 in forum New To Java
    Replies: 2
    Last Post: 04-09-2009, 03:26 AM
  3. Recursion
    By Mika in forum New To Java
    Replies: 5
    Last Post: 01-04-2009, 02:13 AM
  4. Recursion help
    By rjg_2186 in forum New To Java
    Replies: 1
    Last Post: 01-02-2009, 09:03 AM
  5. Help With Recursion
    By andrew777 in forum New To Java
    Replies: 1
    Last Post: 03-29-2008, 01: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
  •