[FIXED] What is wrong with my recursive back-tracker

Issue

I wanted to make an algorithm to create a maze using recursive back-tracker algorithm. I get this problem when running the program:

Exception in thread "main" java.util.NoSuchElementException
    at java.base/java.util.Vector.firstElement(Vector.java:481)
    at DC_files.Maze.RBT(MazeAlgorithm.java:131)
    at DC_files.MazeAlgorithm.main(MazeAlgorithm.java:222)

and honestly, at this point after finding couple of bugs and error i have no idea what might be wrong. The only clue that i have, is that in the switch there is an error, that the stack.firstElement() doesn't update and is always the same and in the cases something is being inserted wrongly.

while(vis < toVis){
    Vector<Integer> neighbours = new Vector<>();
    int x = stack.firstElement().getKey();   (line 131 with the error.)
    int y = stack.firstElement().getValue();


            //North neighbour
            if(y-1 >= 0 && !matrix[y - 1][x].vis){
                neighbours.add(0);
            }

entire code

package DC_files;
import javafx.util.Pair;
import java.util.Random;
import java.io.*;
import java.util.*;

class Cell{

    /*
      each Cell holds information of:
        -the state of it's walls,
        -the value that the Cell holds(will be used later to customize rooms in the maze),
        -and information if the Cell was visited(will be used in the algorithm)
     */


    boolean[] walls;
    boolean vis;
    int value;


    public boolean isVis() {
        return vis;
    }

    public boolean[] getWalls() {
        return walls;
    }

    public int getValue() {
        return value;
    }


    /*
        by default, each Cell has the value of each wall set to true(they exist/there are no corridors),
        vis as visited set to false, because we weren't in the room yet,
        value set to zero, for further development phase (0 - not visited, 1 - visited, 2 - ??? (...))
     */

    Cell(){
        walls = new boolean[]{true, true, true, true}; // {N, S, E, W}
        vis = false;
        value = 0;
    }
}

class Maze{

    /*
        Maze class was created in order to generate an array of Cells,
        that will be later used in the algorithm.

        First we create integer ,,size,, to store size of the array, then
        we create a matrix, that will hold Cell objects.

        In the constructor of the class, we set the required integer s as size,
        allocate memory to the matrix, by setting its dimensions to size x size
        and we create Cell objects for each spot int the matrix, without any modifications.
     */



    int size;
    Cell[][] matrix;


    Maze(int s){
        size = s;
        matrix = new Cell[size][size];
        
        for(int y = 0; y < size; y++){
            for(int x = 0; x < size; x++){
                matrix[y][x] = new Cell();
                //System.out.print("1");
            }
        }
    }


    void showMaze(){
        for(int y = 0; y < size; y++){
            for(int x = 0; x < size; x++){
                System.out.print(matrix[y][x].getValue() + " ");
            }
            System.out.println();
        }
    }



    /*
        Class ,,MazeAlgorithm'' is responsible for creating connections between cells in matrix.
        It uses RBT, which stands for Recursive Back-Tracker, to achieve that goal.
        In order to use RBT, we need to give it starting point. After we do that,
        it will check, if there is any neighbour, that fulfills the required conditions,
        and then goes to that neighbour setting visited to true and value to 1.
        After that, it repeats the process, and constantly adds the cells coordinates
        on top of the stack, to keep track of the road it went through. If it gets stuck,
        it will go back to the previous cell, by removing the top coordinates of the stack,
        and going to NOW top coordinates (previous move), checking if that cell has any
        neighbours which can fulfill the conditions. If it cannot find any neighbour,
        it means the maze was created.
     */


    void RBT(int startX, int startY){

        //Setting cells to visit to size x size, and the value of visited cells to 0
        int toVis = size*size;
        int vis = 0;


        //Declaring a stack, that will hold the information about our road
        Stack<Pair<Integer, Integer>> stack = new Stack<>();


        //Setting starting position: pushing it onto the stack,
        //setting it's values as visited and 1,
        //incrementing visited rooms.
        stack.push(new Pair<>(startX, startY));

        matrix[startY][startX].vis = true;
        matrix[startY][startX].value = 1;
        vis += 1;

        //we will check, if our current node has any neighbours we can go to,
        //saving those neighbours inside a vector
        while(vis < toVis){
            Vector<Integer> neighbours = new Vector<>();
            int x = stack.firstElement().getKey();
            int y = stack.firstElement().getValue();


            //North neighbour
            if(y-1 >= 0 && !matrix[y - 1][x].vis){
                neighbours.add(0);
            }

            //South neighbour
            if(y+1 < size && !matrix[y + 1][x].vis){
                neighbours.add(1);
            }

            //East neighbour
            if(x+1 < size && !matrix[y][x + 1].vis){
                neighbours.add(2);
            }

            //West neighbour
            if(x-1 >= 0 && !matrix[y][x - 1].vis){
                neighbours.add(3);
            }


            //checking, if there are any neighbours we can visit
            //if yes, we do our job
            //if not, we pop our stack and repeat the process
            if(!neighbours.isEmpty()){
                Random rand = new Random();
                int randDir = neighbours.get(rand.nextInt(neighbours.size()));

                switch (randDir) {
//North
                    case 0 -> {

                        matrix[y][x].walls[0] = false;

                        stack.push(new Pair<>(x, y - 1));

                        matrix[y - 1][x].value = 1;
                        matrix[y - 1][x].vis = true;
                        matrix[y - 1][x].walls[1] = false;

                    }
//South
                    case 1 -> {
                        matrix[y][x].walls[1] = false;

                        stack.push(new Pair<>(x, y + 1));

                        matrix[y + 1][x].value = 1;
                        matrix[y + 1][x].vis = true;
                        matrix[y + 1][x].walls[0] = false;
                    }
//East
                    case 2 -> {
                        matrix[y][x].walls[2] = false;

                        stack.push(new Pair<>(x + 1, y));

                        matrix[y][x + 1].value = 1;
                        matrix[y][x + 1].vis = true;
                        matrix[y][x + 1].walls[3] = false;
                    }
//West
                    case 3 -> {
                        matrix[y][x].walls[3] = false;

                        stack.push(new Pair<>(x - 1, y));

                        matrix[y][x - 1].value = 1;
                        matrix[y][x - 1].vis = true;
                        matrix[y][x - 1].walls[2] = false;
                    }
                }

                vis += 1;
            }else{
                stack.pop();
            }
        }
    }
}

public class MazeAlgorithm {


    public static void main(String[] args){

        Maze m = new Maze(3);
        m.RBT(1, 1);
        m.showMaze();
    }

so i just run the code again, and the error line changed to line 131, i am also watching some tutorial about the Intellij debugger rn.

Solution

EDIT: Problem resolved. Had to change lines:

 int x = stack.firstElement().getKey();   
 int y = stack.firstElement().getValue();

into:

 int x = stack.peek().getKey();   
 int y = stack.peek().getValue();

Turns out method .firstElement() doesn't give you first element (the one on top of the stack) but the one that was first inserted (always the same object) so in the end all the operation were performed on one, single element and not multiple ones.

Answered By - 22eragon22

Answer Checked By - Dawn Plyler (PHPFixing Volunteer)