1. Member
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;
}
}```
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. Member
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 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 09:20 AM.

3. Member
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.

4. Member
Join Date
May 2010
Posts
26
Rep Power
0
Originally Posted by Cruncher
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. Member
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

6. Member
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.

7. Member
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.

8. Member
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.

9. Member
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.

10. Member
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)

11. Member
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.

12. Member
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"

13. Member
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.

14. Member
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;
boolean foundit;

public Path(DataThread dt, int[] prevpath) {
distance = prevpath.length;
data = dt;
foundit = 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;
}
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>();
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 01:05 PM.

15. Member
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)];
}
}```
But when i call it with

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

I get null.

16. Member
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;
}```

17. Member
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)];```
Shouldn't taht i<3 be i<4?

18. Member
Join Date
Mar 2010
Posts
88
Rep Power
0
it should be :| hold on... lol...

19. Member
Join Date
Mar 2010
Posts
88
Rep Power
0
fixed that, i'm getting 167 for the ArrayList size now :/

20. Member
Join Date
May 2010
Posts
26
Rep Power
0
ArrayList temp = path.clone();

Page 1 of 2 12 Last

#### Posting Permissions

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