Algorithmic error in java maze generator

Question

I'm trying to write a program that generates 2-d mazes. The body of the maze is a 2-d int array. The border cells have a value of 2. Blocked cells (walls) have a value of 1, and empty cells (paths) have a value of 0. Initially, I am setting the value of all cells to 1. Then, starting from a random column in the top row, I move through the maze setting the current cell to 0 until I reach the bottom row.

This all worked fine, except that, rather than a single-line path, I often ended up with wide areas of 0's. So, I tried to add to the if statements to prevent it from marking cells zero if the cells around it were already zero. Unfortunately there is some flaw in my logic, causing the program to run forever without printing anything when I run it. Please help me identify that flaw.

I'm fairly new to programming, and am doing this as a learning exercise, so I'm also open to other algorithmic suggestions. Thanks

My code:

package RoboProj;

import java.util.Random;


public class Maze {
public int[][] grid;
final int width, height;

public Maze() {
    width = 20;
    height = 20;
    grid = new int[width][height];

    makeMaze();
}


public void makeMaze() {
    //* empty = 0, wall = 1, border = 2, travelled =3;

    //mark borders
    for (int curr = 0; curr < height; curr++) {
        grid[0][curr] = 2;  //top
        grid[curr][0]=2; //left
        grid[height -1][curr] = 2; //bottom
        grid[curr][width-1] = 2; //right
    }
    //initially mark all cells as walls
    for (int row = 1; row < height-1; row++){
        for (int col = 1; col < width-1; col++){
            grid[row][col]=1;
        }      
    }

    int row = 0;
    Random r = new Random();
    int col =  r.nextInt(width);

    grid[row][col] = 0;

    while (row != height-1){
        int next = r.nextInt(4);
        if (next == 0 && row-1 > 0 && grid[row-1][col-1] == 1 && grid[row-1][col+1] == 1){
            grid[row-1][col]=0;
            row = row-1;
          //  System.out.print(next);
        }
        if (next == 1 && grid[row+1][col-1] == 1 && grid[row+1][col+1] == 1){
            grid[row+1][col]=0;
            row = row+1;
           // System.out.print(next);
        }      
        if (next == 2&& col-1 > 0 && grid[row+1][col-1] == 1 && grid[row-1][col-1] == 1){
            grid[row][col-1]=0;
            col = col-1;
                  //     System.out.print(next);
        } 
        if (next == 3 && col+1 < width-1 && grid[row-1][col+1] == 1 && grid[row+1][col+1] == 1){
            grid[row][col+1]=0;
            col = col+1;
                   //     System.out.print(next);
        } 
    }
}
}

@ Anupam Saini: I'm looking for something like this, where the "pathway" is never more than one cell wide.

1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

Answer 1

I have modified your code a bit to make it more readable. I am using switch case statement to indicate movement in the maze, 0 denotes left turn i denotes right turn and 2 denotes down movement. The

isValidTurn()

and

moveMouse()

are the methods of interest.

    import java.util.Random;

    public class Maze {
    private final int[][] grid;
    private final int width, height;

    public static void main(String args[]) {
        Maze mz = new Maze(20, 20);
        mz.moveMouse();
    }

    private void generateDefaultMaze() {
        System.out.println(this);
        // * empty = 0, wall = 1, border = 2, travelled =3;

        // mark borders
        for (int curr = 0; curr < height; curr++) {
            grid[0][curr] = 2; // top
            grid[curr][0] = 2; // left
            grid[height - 1][curr] = 2; // bottom
            grid[curr][width - 1] = 2; // right
        }
        // initially mark all cells as walls
        for (int row = 1; row < height - 1; row++) {
            for (int col = 1; col < width - 1; col++) {
                grid[row][col] = 1;
            }
        }

        System.out.println(this);
    }

    public Maze(int width, int height) {
        this.width = width;
        this.height = height;
        grid = new int[width][height];
        this.generateDefaultMaze();
    }

    /**
     * Overridden method to generate a human readable maze state.
     */
    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer(1024);
        for (int i = 0; i < this.width; i++) {
            for (int j = 0; j < this.height; j++) {
                sb.append(this.grid[i][j]).append(",");
            }
            sb.append("\n");
        }
        sb.append("\n");
        sb.append("**************");
        sb.append("\n");
        return sb.toString();
    }

    /**
     * Row pointer can either move left or right and it's value should be
     * between 0 and width. In case of 0 value at this grid[row][col] do not
     * move the pointer.
     * 
     * @param row The row pointer value.
     * @param col The column pointer value.
     * @return
     */
    private boolean isValidTurn(int row, int col) {
        if (row >= 0 && row < width && !(this.grid[col][row] == 0)) {
            return true;
        }
        return false;
    }

    public void moveMouse() {
        Random r = new Random();
        int row = r.nextInt(width);
        int col = 0;

        grid[col][row] = 0;
        // System.out.println(this);
        while (col < (this.height - 1)) {
            // Assuming the mouse moves in only 3 directions left right or down
            // in the maze. 0 indicates left turn 1 indicates right turn and
            // 2 indicates down movement in the maze.
            int nextDir = r.nextInt(3);
            switch (nextDir) {
            case 0: // left turn
                if (this.isValidTurn((row - 1), col)) {
                    --row;
                    this.grid[col][row] = 0;
                }
                break;
            case 1: // right turn
                if (this.isValidTurn((row + 1), col)) {
                    ++row;
                    this.grid[col][row] = 0;
                }
                break;
            case 2: // down movement
                ++col;
                this.grid[col][row] = 0;
                break;
            }
            System.out.println("turn : " + nextDir);
            // System.out.println(this);
        }
        System.out.println(this);
    }
 }