Maze Algorithms

Overview

We developed several maze algorithms as a class, but here are the programs for just two: the "left-hand traversal" for solving a maze by running your hand along the left wall and going until you reach the exit, and the "wall off dead-ends" method, where you find the dead ends and replace them with walls until the only path is the correct one.

Left Had Traversal


class Test {

    // function which returns a (hard-coded) 2d maze
    public static char[][] getMaze() {
        return new char[][]{
            {'-', '#', '#', '#', '#', '-', '-', '-', '-', '-', '-', '#', '#', '#', '#', '#', '#', '#'},
            {'-', '-', '-', '-', '#', '-', '#', '#', '#', '#', '-', '-', '-', '-', '-', '-', '#', '#'},
            {'-', '#', '#', '-', '#', '-', '-', '-', '#', '#', '#', '#', '#', '#', '#', '-', '#', '#'},
            {'-', '#', '#', '#', '#', '-', '#', '-', '#', '#', '#', '-', '-', '-', '#', '-', '-', '-'},
            {'-', '-', '-', '-', '-', '-', '#', '-', '#', '#', '#', '-', '#', '#', '#', '-', '#', '#'},
            {'#', '#', '-', '#', '#', '#', '#', '-', '#', '#', '#', '-', '#', '#', '#', '-', '#', '#'},
            {'#', '#', '#', '#', '#', '#', '#', '-', '-', '-', '-', '-', '-', '-', '#', '-', '-', '-'},
            {'#', '#', '-', '-', '-', '-', '-', '-', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
            {'-', '-', '-', '#', '#', '#', '#', '#', '#', '#', '-', '-', '-', '-', '#', '#', '#', '#'},
            {'-', '#', '-', '-', '-', '-', '-', '-', '-', '-', '-', '#', '#', '-', '-', '-', '-', '#'},
            {'-', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '-', '#'},
            {'-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '#', '#', '#', '#', '#', '#'},
            {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '-', '-', '-', '-', '-', '-', '-'},};
    }


    // function which prints out a 2d maze
    public static void printMaze(char maze[][]) {
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[0].length; j++) {
                System.out.print(maze[i][j]);
            }
            System.out.print('\n');
        }
    }

    // definitions for each of the cardinal directions
    public static final int SOUTH = 0;
    public static final int EAST = 1;
    public static final int NORTH = 2;
    public static final int WEST = 3;

    // functions which move the runner left, right, straight or back
    public static int goLeft(int direction, int current[]) {
        int new_direction = (direction + 1) % 4;
        goStraight(new_direction, current);
        return new_direction;
    }
    public static int goRight(int direction, int current[]) {
        int new_direction = (direction + 3) % 4;
        goStraight(new_direction, current);
        return new_direction;
    }
    public static int goBack(int direction, int current[]) {
        int new_direction = (direction + 2) % 4;
        goStraight(new_direction, current);
        return new_direction;
    }
    // this one actually moves the runner
    public static int goStraight(int direction, int current[]) {
        switch (direction) {
            case NORTH:
                current[0]--;
                break;
            case SOUTH:
                current[0]++;
                break;
            case EAST:
                current[1]++;
                break;
            case WEST:
                current[1]--;
                break;
        }
        return direction;
    }

    // function to determine if the runner can go to a possible
    // location in the maze
    public static boolean canGo(char maze[][], int possible[]) {
        // if out of bounds, you cannot go there!
        if (possible[0] < 0) {
            return false;
        }
        if (possible[1] < 0) {
            return false;
        }
        if (possible[0] >= maze.length) {
            return false;
        }
        if (possible[1] >= maze[0].length) {
            return false;
        }
        
        // if it's a wall you cannot go there!
        if (maze[possible[0]][possible[1]] == '#') {
            return false;
        }

        // otherwise, you can!
        return true;
    }

    // function to solve the maze by left-handed traversal
    public static void solveLeftHandTraversal(char maze[][]) {
        // we start in the upper left, going south
        int current[] = new int[]{0, 0};
        int possible[] = new int[]{0, 0};
        int direction = SOUTH;

        // while we are not at the end of the maze
        while ((current[0] != (maze.length - 1))
                || (current[1] != (maze[0].length - 1))) {

            // reset the maze and put our runner at the current
            // location, then print the maze so we can see how
            // the algorithm is working
            maze = getMaze();
            maze[current[0]][current[1]] = '@';
            System.out.println("\n");
            printMaze(maze);
            System.out.println("\n");

            // if we can go left, do so
            possible[0] = current[0];
            possible[1] = current[1];
            int new_direction = goLeft(direction, possible);
            if (canGo(maze, possible)) {
                current[0] = possible[0];
                current[1] = possible[1];
                direction = new_direction;
                continue;
            }

            // if we can go forward do so
            possible[0] = current[0];
            possible[1] = current[1];
            new_direction = goStraight(direction, possible);
            if (canGo(maze, possible)) {
                current[0] = possible[0];
                current[1] = possible[1];
                direction = new_direction;
                continue;
            }

            // if we can go right do so
            possible[0] = current[0];
            possible[1] = current[1];
            new_direction = goRight(direction, possible);
            if (canGo(maze, possible)) {
                current[0] = possible[0];
                current[1] = possible[1];
                direction = new_direction;
                continue;
            }

            // else go back
            possible[0] = current[0];
            possible[1] = current[1];
            new_direction = goBack(direction, possible);
            if (canGo(maze, possible)) {
                current[0] = possible[0];
                current[1] = possible[1];
                direction = new_direction;
            }
        }

        // print it one last time with final state
        maze = getMaze();
        maze[current[0]][current[1]] = '@';
        System.out.println("\n");
        printMaze(maze);
    }

    // the main function just creates the maze, and the calls
    // the function to solve it
    public static void main(String args[]) {
        char maze[][] = getMaze();
        printMaze(maze);
        solveLeftHandTraversal(maze);
    }
}

Wall off Dead Ends


class Test {

    // function which returns a (hard-coded) 2d maze
    public static char[][] getMaze() {
        return new char[][]{
            {'-', '#', '#', '#', '#', '-', '-', '-', '-', '-', '-', '#', '#', '#', '#', '#', '#', '#'},
            {'-', '-', '-', '-', '#', '-', '#', '#', '#', '#', '-', '-', '-', '-', '-', '-', '#', '#'},
            {'-', '#', '#', '-', '#', '-', '-', '-', '#', '#', '#', '#', '#', '#', '#', '-', '#', '#'},
            {'-', '#', '#', '#', '#', '-', '#', '-', '#', '#', '#', '-', '-', '-', '#', '-', '-', '-'},
            {'-', '-', '-', '-', '-', '-', '#', '-', '#', '#', '#', '-', '#', '#', '#', '-', '#', '#'},
            {'#', '#', '-', '#', '#', '#', '#', '-', '#', '#', '#', '-', '#', '#', '#', '-', '#', '#'},
            {'#', '#', '#', '#', '#', '#', '#', '-', '-', '-', '-', '-', '-', '-', '#', '-', '-', '-'},
            {'#', '#', '-', '-', '-', '-', '-', '-', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
            {'-', '-', '-', '#', '#', '#', '#', '#', '#', '#', '-', '-', '-', '-', '#', '#', '#', '#'},
            {'-', '#', '-', '-', '-', '-', '-', '-', '-', '-', '-', '#', '#', '-', '-', '-', '-', '#'},
            {'-', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '-', '#'},
            {'-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '#', '#', '#', '#', '#', '#'},
            {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '-', '-', '-', '-', '-', '-', '-'},};
    }

    // function which prints out a 2d maze
    public static void printMaze(char maze[][]) {
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[0].length; j++) {
                System.out.print(maze[i][j]);
            }
            System.out.print('\n');
        }
    }

    // function which tests if a position in the maze is open or not
    public static boolean open(char maze[][], int row, int col) {
        // if it's out of bounds, it is not open
        if (row < 0) {
            return false;
        }
        if (col < 0) {
            return false;
        }
        if (row >= maze.length) {
            return false;
        }
        if (col >= maze[0].length) {
            return false;
        }
        
        // if it's a wall, it is not open
        if (maze[row][col] == '#') {
            return false;
        }

        // otherwise, it is open
        return true;
    }

    // function which removes all dead ends from the maze
    public static void removeDeadEnds(char maze[][]) {

        // keep track of whether each "pass" of the algorithm has made a change
        boolean change;
        do {
            // assume no change;
            change = false;
            
            // loop through each maze location
            for (int row = 0; row < maze.length; row++) {
                for (int col = 0; col < maze[0].length; col++) {

                    // if it's the start of the maze, or the end, don't wall it off!
                    if ((row == 0 && col == 0)
                     || (row == (maze.length - 1)) && (col == (maze[0].length - 1))) {
                        continue;
                    }

                    // count the number of openings out of this location
                    int num_open = 4;
                    if (!open(maze, row, col - 1)) {
                        num_open--;
                    }
                    if (!open(maze, row, col + 1)) {
                        num_open--;
                    }
                    if (!open(maze, row - 1, col)) {
                        num_open--;
                    }
                    if (!open(maze, row + 1, col)) {
                        num_open--;
                    }

                    // if there is exactly one opening, and it's not already a wall
                    if ((num_open == 1) && (maze[row][col] != '#')) {
                        // wall it off and indicate that this pass has made a change
                        maze[row][col] = '#';
                        change = true;
                    }
                }
            }
        } while (change);
    }

    // main prints the initial maze, then removes the dead ends and prints it again
    public static void main(String args[]) {
        char maze[][] = getMaze();
        printMaze(maze);
        removeDeadEnds(maze);
        System.out.println("\n\n");
        printMaze(maze);
    }
}