Maze Navigation using Recursion And Backtracking
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

Thread: Maze Navigation using Recursion And Backtracking

  1. #1
    Join Date
    Mar 2011
    Posts
    2

    Talking Maze Navigation using Recursion And Backtracking

    The task is simple, create a Maze class that can navigate any MxN maze, with a starting position of (0,0) and an exit at (m,n). Each space visited must be marked with a 3, and then when finished, the correct path should be labeled as a 7.

    Here is my Maze class.

    import java.util.*;
    import java.io.*;

    public class Maze
    {
    private int rows, cols;
    private char path;
    private char wall;
    private char[][] maze;

    //Constructor
    public Maze(int r, int c, char p, char w)
    {
    rows = r;
    cols = c;
    path = p;
    wall = w;
    maze = new char[rows][cols];
    }//end Constructor

    //Fills the maze by reading in a data file
    public void fillMaze() throws FileNotFoundException
    {
    Scanner scan = new Scanner(System.in);

    System.out.println("Enter the name of the maze file including the extension: ");
    String name = scan.next();
    File file = new File(name);

    Scanner infile = new Scanner(file);

    //int total = this.rows + this.cols;

    for(int x=0; x<this.rows; x++)
    {
    for(int y=0; y<this.cols; y++)
    this.maze[x][y] = infile.next().charAt(0);
    }


    }//End fillMaze

    //Prints the maze
    public void printMaze()
    {
    for(int x=0; x<this.rows; x++)
    {
    for(int y=0; y<this.cols; y++)
    System.out.print(maze[x][y] + " " );
    System.out.println();
    }
    }//End printMaze

    //Traverses the maze
    public Boolean traverseMaze(int row, int col)
    {
    Boolean move = false;

    //If attempted move is outside the maze
    if(row<0 || row>this.rows-1 || col<0 || col>this.cols-1)
    return false;

    //If current position is at the end of the maze
    if(row == this.rows && col == this.cols)
    {
    move = true;
    this.maze[row][col] = '7';
    return move;
    }

    //If attempted move is a wall
    if(this.maze[row][col] == this.wall)
    return false;

    //If already visited
    if(this.maze[row][col] == '3')
    return false;


    this.maze[row][col] = '3';


    move = traverseMaze(row+1, col); // down
    move = traverseMaze(row, col+1); // right
    move = traverseMaze(row-1, col); //up
    move = traverseMaze(row, col-1); //left

    this.maze[row][col] = '7';

    return move;
    }//end traverseMaze
    }



    Then here is the maze before and after the navigation.

    B A A A A A A A A A A A A A A
    B A B B B A A A A A A A A A A
    B A B A B B A B B B B B A A A
    B B B A A B A A A B A A A A A
    B A A A A B A A A B A A A A A
    B A A A A B A A A B A A A A A
    B A A A A B B B B B B B B A A
    B A A A A A B A A A A A B A A
    B B B A A A B A A A A A B A A
    A A B A A B B A A A A A B A A
    A A B A A B A A A A A A B A A
    A A B A A B B B A B A A B A A
    A A A A B B A B A B A A B A A
    A A A A B A A B B B A A B B A
    A A A A B A A A A A A A A B A
    A A A B B A A A A A A A A B A
    A A A A A A A A A A A A A B B
    A A A A A A A A A A A A A A B

    7 A A A A A A A A A A A A A A
    7 A 7 7 7 A A A A A A A A A A
    7 A 7 A 7 7 A 7 7 7 7 7 A A A
    7 7 7 A A 7 A A A 7 A A A A A
    7 A A A A 7 A A A 7 A A A A A
    7 A A A A 7 A A A 7 A A A A A
    7 A A A A 7 7 7 7 7 7 7 7 A A
    7 A A A A A 7 A A A A A 7 A A
    7 7 7 A A A 7 A A A A A 7 A A
    A A 7 A A 7 7 A A A A A 7 A A
    A A 7 A A 7 A A A A A A 7 A A
    A A 7 A A 7 7 7 A 7 A A 7 A A
    A A A A 7 7 A 7 A 7 A A 7 A A
    A A A A 7 A A 7 7 7 A A 7 7 A
    A A A A 7 A A A A A A A A 7 A
    A A A 7 7 A A A A A A A A 7 A
    A A A A A A A A A A A A A 7 7
    A A A A A A A A A A A A A A 7


    As you can see, the program successfully navigates the maze, but changes every possible path space to a 7, instead of just the solution. Any ideas on how to fix this? Thanks in advance!

  2. #2
    Join Date
    May 2006
    Location
    UK
    Posts
    4,474

    Re: Maze Navigation using Recursion And Backtracking

    First of all your test to see if you are at the end of the maze will always fail as you should be checking
    Code:
    if ( row == this.rows-1 && col == this.cols-1 )
    .
    The other problem is you aren't handling the backtracking. If any recursive call to traverseMaze() returns true you should immediately set the cell index you passed in to the recursive call to '7' and return true - do not continue checking other cells.
    Posting code? Use code tags like this: [code]...Your code here...[/code]
    Click here for examples of Java Code

  3. #3
    Join Date
    Mar 2011
    Posts
    2

    Re: Maze Navigation using Recursion And Backtracking

    Thank you very much, that's exactly what I needed. For some reason I thought I tried setting the value to 7 whenever move came back true before, but I guess not in the manner you said.

    Ps - sorry for not using the code tags...didn't read that thread until after my post haha.

Tags for this Thread

Posting Permissions

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


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center