Recursion.

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?

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.

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.

Quote:

---

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.

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

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.

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.

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.

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.

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)

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.

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"

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

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.

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;
      }
    }

  }

---

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

But this was my attempt:

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.

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

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;
    }

---

I see one problem right off:

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?

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

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

ArrayList temp = path.clone();