Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: Help with traversing a maze recursively.

  1. #1
    Member
    Join Date
    Apr 2012
    Posts
    42
    Thanks
    8
    Thanked 4 Times in 4 Posts

    Default Help with traversing a maze recursively.

    Hi guys. I've been doing pretty good with my programming so its been awhile since my last post, but as the title suggests I am stuck on traversing my maze using recursion. I have a 2D array that is given a set value to represent my maze. My constructor creates a 2D array that is sized by given row and column values, and then the actual values themselves are passed after that. It appears that the problem lies when I come across the character that's supposed to represent the walls of the maze, which is a *. It gives me the following error:

    Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5
    	at recursivemaze.Maze.traverse(Maze.java:41)
    	at recursivemaze.Maze.traverse(Maze.java:52)
    	at recursivemaze.Maze.traverse(Maze.java:52)
    	at recursivemaze.Maze.traverse(Maze.java:52)
    	at recursivemaze.Maze.traverse(Maze.java:52)
    	at recursivemaze.Maze.traverse(Maze.java:51)
    	at recursivemaze.Maze.traverse(Maze.java:51)
    	at recursivemaze.RecursiveMaze.main(RecursiveMaze.java:26)
    Java Result: 1


    I'm not sure what the problem is, because my code is supposed to return nothing when it comes across a * and keep continuing the recursive method calls until it reaches the last possible part of the maze that it can travel, all the while placing a 'P' in areas where it has traveled. Any help would be appreciated in solving this. My code is as followed:


    public class Maze {
        private char[][] primeMaze = null;
        private int rows = 0;
        private int columns = 0;
        private final char PATH = 'P';
        private int total = 0;
     
        public Maze(){
     
        }
     
        public Maze(int x, int y){
            rows = x;
            columns = y;
            primeMaze = new char[x][y];
        }
     
        public int getDimensions(){
            return (rows * columns);
        }
     
        public void fillMaze(char[][] m){
            for (int i = 0; i < primeMaze.length; i++){
                for (int j = 0; j < primeMaze[i].length; j++){
                    primeMaze[i][j] = m[i][j];
                }
            }
        }
     
        public void traverse(int r, int c){
            if (primeMaze[r][c] == '*'){
                return;                                                                                     ****This is the source of the error****
            }
            if (primeMaze[r][c] == PATH){
                return;
            }
     
            primeMaze[r][c] = PATH;
            traverse(r + 1, c);
            traverse(r, c + 1);
            traverse(r - 1, c);
            traverse(r, c - 1);
            primeMaze[r][c] = ' ';
            return;
        }
     
        public String toString(){
            String answer = null;
     
            for (int i = 0; i < rows; i++){
                for (int j = 0; j < columns; j++){
                    answer += primeMaze[i][j] + " ";
                }
                answer += "\n";
            }
            return answer;
        }
    }

    public class RecursiveMaze {
     
        /**
         * @param args the command line arguments
         */
        public static void main(String[] args) {
            char[][] test = new char[][]{{'*', '*', '*', '*', '*'},
                {'*', ' ', ' ', '*', '*'},
                {'*', ' ', '*', '*', '*'},
                {'*', ' ', ' ', ' ', ' '},
                {'*', '*', '*', '*', '*'}};
     
     
            Maze m = new Maze(5, 5);
            m.fillMaze(test);
            m.traverse(1, 1);
            System.out.println(m.toString());
            }
    }


  2. #2
    Junior Member
    Join Date
    Feb 2013
    Location
    Germany
    Posts
    27
    Thanks
    0
    Thanked 5 Times in 5 Posts

    Default Re: Help with traversing a maze recursively.

    It happens at the exit of the maze. The exit condition doesnt work in this case becaus there is no wall.
    		char[][] test = new char[][] { 
    				{ '*', '*', '*', '*', '*' },
    				{ '*', ' ', ' ', '*', '*' }, 
    				{ '*', ' ', '*', '*', '*' },
    				{ '*', ' ', ' ', ' ', ' ' }, 
    				{ '*', '*', '*', '*', '*' } };
    You go out at row 3 and column 4. But the recursion doesnt break because it thinks it goes on....

  3. #3
    Member
    Join Date
    Apr 2012
    Posts
    42
    Thanks
    8
    Thanked 4 Times in 4 Posts

    Default Re: Help with traversing a maze recursively.

    Alright, so when I change the open space at the end to a * the the program seems to run just fine. Thanks for the help on that one. However, how would I go about making my program recognize that single opening in the wall as the exit without it crashing again. Basically, the format of the mazes my instructor will be providing us with has the entirety of the outer wall of the maze as *'s, with a single opening in the wall for an exit.

  4. #4
    Junior Member
    Join Date
    Feb 2013
    Location
    Germany
    Posts
    27
    Thanks
    0
    Thanked 5 Times in 5 Posts

    Default Re: Help with traversing a maze recursively.

    The simplest way should be an extra break condition where you compare the parameters r and c to the row and column class var. But I'm not sure if you will go through the maze the right way then.
    Maybe it's better you check befor each recursive call like
    if((r+1) <= row){
       traverse(r + 1, c);
    }
    But both proposals are without any guarantee. I didn't check it.

Similar Threads

  1. Delete a directory recursively
    By Rexshine in forum What's Wrong With My Code?
    Replies: 8
    Last Post: February 19th, 2013, 09:46 PM
  2. Having trouble figuring out how to recursively do this.
    By javapenguin in forum What's Wrong With My Code?
    Replies: 17
    Last Post: May 1st, 2012, 10:50 PM
  3. [SOLVED] Traversing a tree
    By IAmHere in forum Algorithms & Recursion
    Replies: 3
    Last Post: June 19th, 2011, 10:47 AM
  4. printing array recursively
    By kyros in forum Algorithms & Recursion
    Replies: 2
    Last Post: November 19th, 2010, 01:04 AM
  5. Problem in recursion for Solving Maze Recursively program
    By _Coder1985 in forum Algorithms & Recursion
    Replies: 1
    Last Post: April 29th, 2009, 05:37 AM