Constructing Mazes in java using 2D array and stacks

Question

I need to construct a maze using a 2D array and stacks. The array size is fixed. the starting point is (0,0). The array should be read from a file but in this example, I am assuming values just to make things clear.

I can't seem to find a proper algorithm that lets me go through the 2D array and saves my path to the stack. And that gets me back to the upper row if I am stuck in the current row. PS: 1 is a wall and 0 is a path. The question requires an array input by the user but I provided one for simplicity

Heres the array:

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

I need to start from position (0,0) and the exit should be in the last row. If I got stuck I need to go up and find another path; that is pop the stack.

Here's what I came up with:

public class Maze {

  Maze currentPos = new Maze();

  int position = maze[0][0];

  public Maze() 
  {
  }

  public Maze(Maze currentPos) 
  {
    this.currentPos = currentPos;
    position = maze[0][0];
  }
  Stack stack = new Stack ();

  public static int[][] maze = new int[][] {
    {0,1,0,0,0},
    {0,1,0,0,0},
    {0,0,0,0,0},
    {1,1,1,0,0},
    {0,1,0,0,0}
  };

  public boolean UP (int i, int j)
  {
    if (maze [i-1][j] == 0)
      return true;
    return false;
  }

  public boolean DOWN (int i, int j)
  {
    if (maze [i+1][j] == 0)
      return true;
    return false;
  }

  public boolean RIGHT(int i,int j)
  {
    if (maze [i][j+1] == 0)
      return true;
    return false;
  }

  public boolean LEFT(int i,int j)   
  {
    if (maze [i][j-1] == 0)
      return true;
    return false;
  }

  public boolean isExit (int i, int j)
  {
    if (j == 6)
      return true;
    return false;
  }

  public void setPosition(int i , int j)
  {
    position = maze[i][j];
  }

  public void solve()
  { 
    for (int i=0; i<maze.length; i++) 
    {
      for (int j=0; j<maze.length; j++) 
      {
        while(! currentPos.isExit(i,j)); 
        {
          if ( currentPos.DOWN(i,j)) stack.push(i+1,j);     
          if ( currentPos.LEFT(i,j)) stack.push(i,j-1);                     
          if ( currentPos.RIGHT(i,j)) stack.push(i,i+1);
          if ( currentPos.UP(i,j)) stack.push(i-1,j);
        }                   
      }         
    }
  }
}

The class stack is the same as the one in java.util.stack and with the same methods included (pop, push)

Answer 1

Here is something to get you started :

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Maze {

    //keep reference to start point
    int startRow, startCol;

    //keep reference to addresses (row, col) that has been checked
    List<Integer[]> visited;

    //a stack that represents the path (solution)
    Stack<Integer[]> path;

    public Maze(int startRow, int startCol) {

        this.startRow = startRow; //add: check input validity
        this.startCol = startCol;
        visited = new ArrayList<>();
        path = new Stack<>();
    }

    public static int[][] mazeValues = new int[][] {
        {0,1,0,0,0},
        {0,0,0,1,0},
        {1,1,1,0,0},
        {1,1,1,0,1},
        {0,0,0,0,0}
    };

    void solve(){

        boolean isSolved = solve(startRow, startCol);
        if( isSolved ) {
            pathFound();
        } else {
            noPathFound();
        }
    }


    private boolean solve(int row, int col) {

        //check if target found
        if(isTargert(row,col)) {
            //add target to path
            path.push(new Integer[]{row,col});
            return true;
        }

        //check if address is a wall
        if(isWall(row,col)) {
            return false;
        }

        //check if visited before
        if(isVisited(row, col)) {
            return false;
        }

        //mark as visited
        visited.add(new Integer[]{row,col});

        //add to path
        path.push(new Integer[]{row,col});

        //check all neighbors (allows diagonal move)
        for (int rowIndex = row-1; rowIndex <= (row+1) ; rowIndex++ ) {

            for (int colIndex = col-1; colIndex <= (col+1) ; colIndex++ ) {

                if( (rowIndex == row) && (colIndex == col)) {//skip current address
                    continue;
                }

                if( ! withInMaze(rowIndex, colIndex)) {
                    continue;
                }

                if( solve(rowIndex, colIndex)) {
                    return true; //solution found
                }
            }
        }

        //solution not found after checking all neighbors
        path.pop(); //remove last from stack;
        return false;
    }

    //check if address is a target
    private boolean isTargert(int row, int col) {
        //target set to last row / col. Change taget as needed
        return (row == (mazeValues.length-1))&& (col == (mazeValues[0].length -1)) ;
    }

    //check if address is a wall
    private boolean isWall(int row, int col) {

        return mazeValues[row][col] == 1;
    }

    private boolean isVisited(int row, int col) {

        for (Integer[] address : visited ) {

            if((address[0]==row) && (address[1]==col)) {
                return true;
            }
        }
        return false;
    }

    //return true if rowIndex, colIndex are with in mazeValues
    private boolean withInMaze(int rowIndex, int colIndex) {

        return (rowIndex < mazeValues.length)&& (rowIndex >= 0)
                &&(colIndex < mazeValues[0].length) && (colIndex >=0);
    }

    private void noPathFound() {
        System.out.println("No path found............");

    }

    private void pathFound() {

        System.out.println("Path found");
        for (Integer[] address : path) {
            int row = address[0]; int col = address[1];
            System.out.println("Address: "+ row +"-"+ col
                                +" value: "+ mazeValues[row][col]);
        }
    }

    public static void main(String[] args) {

        Maze maze = new Maze(0,0);
        maze.solve();
    }
}

For generic maze path finding algorithms I would suggest to start with Breadth-first search