Results 1 to 20 of 31
Thread: Recursion.
 05092010, 01:36 AM #1Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
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; } }
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?
 05092010, 09:06 AM #2Member
 Join Date
 May 2010
 Posts
 26
 Rep Power
 0
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 deadend (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; 05092010 at 09:20 AM.
 05092010, 11:47 AM #3Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
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.
 05092010, 12:06 PM #4Member
 Join Date
 May 2010
 Posts
 26
 Rep Power
 0
 05092010, 12:10 PM #5Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
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
 05092010, 12:17 PM #6Member
 Join Date
 May 2010
 Posts
 26
 Rep Power
 0
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.
 05092010, 12:20 PM #7Member
 Join Date
 May 2010
 Posts
 26
 Rep Power
 0
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.
 05092010, 12:20 PM #8Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
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.
 05092010, 12:26 PM #9Member
 Join Date
 May 2010
 Posts
 26
 Rep Power
 0
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.
 05092010, 12:30 PM #10Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
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)
 05092010, 12:33 PM #11Member
 Join Date
 May 2010
 Posts
 26
 Rep Power
 0
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.
 05092010, 12:36 PM #12Member
 Join Date
 May 2010
 Posts
 26
 Rep Power
 0
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"
 05092010, 12:37 PM #13Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
Thanks, if i run into issues along the way i'll reply here, but for now, thanks a lot.
 05092010, 12:40 PM #14Member
 Join Date
 May 2010
 Posts
 26
 Rep Power
 0
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.length1]); 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.length1] = sobj.warps[i]; temp[i] = new Path(data, newpath); if (avoids.contains(new Integer(newpath[newpath.length1]))) temp[i].dead = true; else avoids.add(new Integer(newpath[newpath.length1])); } 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; 05092010 at 01:05 PM.
 05092010, 01:13 PM #15Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
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)]; } }
ArrayList path = findShortestPath (0, 0, 11, 13, new ArrayList ());
I get null.
 05092010, 01:15 PM #16Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
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; }
 05092010, 01:23 PM #17Member
 Join Date
 May 2010
 Posts
 26
 Rep Power
 0
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)];
 05092010, 01:24 PM #18Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
it should be : hold on... lol...
 05092010, 01:25 PM #19Member
 Join Date
 Mar 2010
 Posts
 88
 Rep Power
 0
fixed that, i'm getting 167 for the ArrayList size now :/
 05092010, 01:28 PM #20Member
 Join Date
 May 2010
 Posts
 26
 Rep Power
 0
Similar Threads

recursion and tailrecursion differences
By OptimusPrime in forum New To JavaReplies: 2Last Post: 12282009, 06:26 PM 
Recursion
By kathyla18 in forum New To JavaReplies: 2Last Post: 04092009, 02:26 AM 
Recursion
By Mika in forum New To JavaReplies: 5Last Post: 01042009, 01:13 AM 
Recursion help
By rjg_2186 in forum New To JavaReplies: 1Last Post: 01022009, 08:03 AM 
Help With Recursion
By andrew777 in forum New To JavaReplies: 1Last Post: 03292008, 12:51 PM
Bookmarks