Question

This lab will use 2D arrays, recursive algorithms, and logical thinking.

The following grid of hashes(#) and dots(.) is a 2D array representation of a maze

  # # # # # # # # # # # #
  # . . . # . . . . . . #
  . . # . # . # # # # . #
  # # # . # . . . . # . #
  # . . . . # # # . # . #
  # # # # . # F # . # . #
  # . . # . # . # . # . #
  # # . # . # . # . # . #
  # . . . . . . . . # . #
  # # # # # # . # # # . #
  # . . . . . . # . . . #
  # # # # # # # # # # # # 

The hashes represent the walls of the maze and the dots represent the possible paths through the maze. Moves can only be made to a location in the array that contains a dot.

Algorithm Explanation

There is a simple algorithm for walking through a maze that GUARANTEES finding the exit (assuming there is an exit). If there is not an exit, you will arrive at the starting location again. Place your right hand on the wall to your right and begin walking forward. Never remove your hand from the wall. If the maze turns to the right, you follow the wall to the right. As long as you do not remove your hand from the wall, eventually you will arrive at the exit of the maze. If you follow the algorithm.

What to do:

Write a program to walk through the maze. You must write a recursive function. The function should recieve as arguments 12-by-12 character array representing the maze and the starting point (x, y location in the maze).
As the function attempts to escape from the maze it should place an X for the current path taken. The program should display the maze at each step so you can watch as the maze is solved. Put an X where you have traveled and maybe an O where you currently are located. The end of the maze will be a capital 'F' (stands for finished).

This algorithm doesn't work for all mazes. Can you come up with a maze where this doesn't work?

Rules you must follow:

Recursive Algorithm, must use recursive method.

Method gets four parameters (maze, xLoc, YLoc, handLocationX, handLocationY) no instance fields needed.

Your method can only see one step, you can only see what's in front of you and what your hand is on......no teleporting, no looking beyond one step at a time.

Movement Rules

You can only see one step to the left, right and one step in front of you for each turn.

Each call to the recursive move method can only do one of three things......

Take a 90 degree turn to right and step one step, turn and step in one turn so you don't do a infinite loop.

Take one step forward.

Turn 90 degrees to the left.

Hints

Make a move, print out the maze and see where you are, make another move, print the maze. Don't try to solve the whole maze at once, get the different moves working first.

Think of it like this......"I am at x, y, my hand is at Hx, Hy which tells me the direction I'm facing based on Hx being less than or greater than x, and Hy being less than or greater than y. Based on on that logic I can check what my hand is touching and what is in front of me.

IF my hand is on a dot I will turn 90 degrees right and move to that dot. I will recursively call my method with a new x, y and a new hx, hy.

If my hand is not on a dot, I will look in front of me, if it is a . in front of me I'll move forward and then recursively call this method with my new x, y, and hx, hy, ........

If it's a # in front of me I can't go forward so I'll turn 90 degrees to left and call the same method recursively with the same x, y, and new hx, hy.

.........so on and so on.
Lots of if statements to figure out which way you are facing, where you need to check to see if you can move forward, of if you need to turn.

The maze should be put into a 2D array.

Also the starting point is always on the outside of the maze, you can search the outside of the input to find a . then you know your starting point. Do that last, wait until you have everything else working first......hard code in the starting point until you get the traversal working.

If you hit a dead end you must turn left, then turn left (2 recursive calls according to the rules) and then head back along the path you already travelled......but now instead of .'s you will see x's if you are showing the route you travelled with x's. Your if statements should handle that......example: if(maze[y+1][x] == '.' || maze[y+1][x] == 'x')

Answer 1

MazeMain.java

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Scanner;

public class MazeMain {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {

        char[][] mazeArray = new char[12][12];

    

        char[][] mazeArray1 = { {'#','#','#','#','#','#','#','#','#','#','#','#'},
                                {'#','.','.','.','#','.','.','.','.','.','.','#'},
                               {'O','.','#','.','#','.','#','#','#','#','.','#'},
                               {'#','#','#','.','#','.','.','.','.','#','.','#'},
                               {'#','.','.','.','.','#','#','#','.','#','.','#'},
                                {'#','#','#','#','.','#','F','#','.','#','.','#'},
                                {'#','.','.','#','.','#','.','#','.','#','.','#'},
                                {'#','#','.','#','.','#','.','#','.','#','.','#'},
                               {'#','.','.','.','.','.','.','.','.','#','.','#'},
                               {'#','#','#','#','#','#','.','#','#','#','.','#'},
                                {'#','.','.','.','.','.','.','#','.','.','.','#'},
                               {'#','#','#','#','#','#','#','#','#','#','#','#'}
                                };
        MazeSetup myMaze = new MazeSetup(mazeArray1);
        myMaze.print(mazeArray1);
        myMaze.run(mazeArray1, 0, 2, 0, 3);
        System.out.println(myMaze.run(mazeArray1, 0, 2, 0, 3));
    }
}

MazeSetup.java

import java.util.Scanner;

public class MazeSetup {
    String facing;
    boolean northOpen, southOpen, westOpen, eastOpen = false;
    Scanner user_input = new Scanner( System.in );
  
    public MazeSetup(char[][] array){  
    }
  
    public void print(char[][] myMaze){
        String output="";
        for(int y=0; y< myMaze.length; y++){
            output+="\n";
            for(int x=0; x<myMaze[y].length; x++){
                output+= myMaze[y][x];
            }
        }
       System.out.println(output);
    }
  
    public String run(char [][]maze, int xLoc, int yLoc, int handLocationX, int handLocationY){//recursive method

        if(maze[yLoc][xLoc]=='F'){
            return "Finished!";
        }
        else {
            facing = findDirection(xLoc, yLoc, handLocationX, handLocationY); //determines direction we are facing
      
            findOpening(maze, xLoc, yLoc, handLocationX, handLocationY);//determines if the direction we are facing is open
          
            if (facing.equals("East")){//FACING EAST

                if(eastOpen){//moves and faces EAST
                    placeX(maze, xLoc, yLoc);//places an X where I was
                    xLoc++;                  //moves forward 1
                    handLocationX++;
                    if(maze[yLoc][xLoc]!='F'){
                        placeO(maze, xLoc, yLoc);//places an O where I am now
                    }
                }
                else if(southOpen){//moves and rotates to face SOUTH
                    placeX(maze, xLoc, yLoc);
                    yLoc++;
                    handLocationX--;
                    if(maze[yLoc][xLoc]!='F'){
                        placeO(maze, xLoc, yLoc);//places an O where I am now
                    }                 
                }
                else{//rotates to the north
                    handLocationY--;
                    handLocationX++;
                }
            print(maze);
      

            }
            else if(facing.equals("North")){//FACING NORTH

                if(eastOpen){//moves and rotates to face EAST
                    placeX(maze, xLoc, yLoc);
                    xLoc++;
                    handLocationY++;
                    if(maze[yLoc][xLoc]!='F'){
                        placeO(maze, xLoc, yLoc);//places an O where I am now
                    }
                }
                else if(northOpen){//MOVE NORTH
                    placeX(maze, xLoc, yLoc);
                    yLoc--;
                    handLocationY--;
                    if(maze[yLoc][xLoc]!='F'){
                        placeO(maze, xLoc, yLoc);//places an O where I am now
                    }
                }         
                else{//rotates to the west
                    handLocationX--;
                    handLocationY--;

                }
            print(maze);

            }
            else if (facing.equals("South")){//FACING SOUTH

                    if(southOpen){//MOVES SOUTH
                        placeX(maze, xLoc, yLoc);//places an X where I was
                        yLoc++;                  //moves forward 1
                        handLocationY++;
                        if(maze[yLoc][xLoc]!='F'){
                            placeO(maze, xLoc, yLoc);//places an O where I am now
                        }
                    }
                    else if(westOpen){//moves and rotates to face WEST
                        placeX(maze, xLoc, yLoc);
                        xLoc--;
                        handLocationY--;
                        if(maze[yLoc][xLoc]!='F'){
                            placeO(maze, xLoc, yLoc);//places an O where I am now
                        }                
                    }
                    else{//rotates to the EAST
                        handLocationX++;
                        handLocationY++;
                    }
                print(maze);

            }
            else if (facing.equals("West")){//FACING WEST

                    if(westOpen){//MOVES WEST
                        placeX(maze, xLoc, yLoc);//places an X where I was
                        xLoc--;                  //moves forward 1
                        handLocationX--;
                        if(maze[yLoc][xLoc]!='F'){
                            placeO(maze, xLoc, yLoc);//places an O where I am now
                        }
                    }
                    else if(northOpen){//moves and rotates to face NORTH
                        placeX(maze, xLoc, yLoc);
                        yLoc--;
                        handLocationX++;
                        if(maze[yLoc][xLoc]!='F'){
                            placeO(maze, xLoc, yLoc);//places an O where I am now
                        }                  
                    }
                    else{//rotates to the SOUTH
                        handLocationX--;
                        handLocationY++;
                    }
                print(maze);

            }
        }
        return run(maze, xLoc, yLoc, handLocationX, handLocationY);
    }
  
    public char getData(char data){//returns the value in a location of the maze
        return data;
    }
  
    public char[][] placeX(char[][] array, int x, int y){//places an X value
        array[y][x] = 'X';
        return array;
    }
  
    public char[][] placeO(char[][] array, int x, int y){//places an O value
        array[y][x] = 'O';
        return array;
    }
  
    public String findDirection(int xLoc, int yLoc, int handLocationX, int handLocationY){
        String facing;
        if(xLoc == handLocationX && handLocationY > yLoc ){
            facing = "East";
        }else if(xLoc ==handLocationX && handLocationY < yLoc){
            facing = "West";
        }else if(yLoc == handLocationY && xLoc > handLocationX) {
            facing = "South";
        }else{ // facing North
            facing = "North";
        }
        return facing;
    }
  
    public void findOpening(char [][] maze, int xLoc, int yLoc, int handLocationX, int handLocationY){
        northOpen = false;
        southOpen = false;
        westOpen = false;
        eastOpen = false;
      
        if (facing.equals("East")){//facing EAST
          
            if(maze[handLocationY][handLocationX]=='.'||maze[handLocationY][handLocationX]=='X'||maze[handLocationY][handLocationX]=='F'){//open to South
                southOpen=true;
            }
            else if(maze[yLoc][xLoc+1]=='.'||maze[yLoc][xLoc+1]=='X'||maze[yLoc][xLoc+1]=='F'){//EAST path in front of us is clear
                eastOpen= true;             
            }
            else {//must turn to the North
                northOpen = true;
            }
        }
        else if(facing.equals("North")){//facing NORTH
          
            if(maze[handLocationY][handLocationX]=='.'||maze[handLocationY][handLocationX]=='X'||maze[handLocationY][handLocationX]=='F'){//open to the EAST
                eastOpen = true;
            }
            else if(maze[yLoc-1][xLoc]=='.'||maze[yLoc-1][xLoc]=='X'||maze[yLoc-1][xLoc]=='F'){//North is clear to take
                northOpen = true;
            }
            else{//must turn west
                westOpen = true;
            }
        }
        else if(facing.equals("South")){//facing SOUTH
          
            if(maze[handLocationY][handLocationX]=='.'||maze[handLocationY][handLocationX]=='X'||maze[handLocationY][handLocationX]=='F'){//open to the WEST
                westOpen = true;
            }
            else if(maze[yLoc+1][xLoc]=='.'||maze[yLoc+1][xLoc]=='X'||maze[yLoc+1][xLoc]=='F'){//SOUTH is clear to take
                southOpen = true;
              
            }
            else{//must turn EAST
                eastOpen = true;
            }
        }
        else{//facing WEST
            if(maze[handLocationY][handLocationX]=='.'||maze[handLocationY][handLocationX]=='X'||maze[handLocationY][handLocationX]=='F'){//open to the North
                northOpen = true;
            }
            else if(maze[yLoc][xLoc-1]=='.'||maze[yLoc][xLoc-1]=='X'||maze[yLoc][xLoc-1]=='F'){//WEST path in front of us is clear
                westOpen= true;
            }
            else{ //must turn to the South
                southOpen = true;
            }     
        }
    }
}

#排。拼排.#

拼排)(#000(#)(# #X# #00000(#00(# #00(#)00000(# 拼#### X###X# #00000(#00(# #00(#00000(# 拼####tX###X# #00000(#XXX# Finished!