Ausgabe
Ich wollte einen Algorithmus erstellen, um ein Labyrinth mit einem rekursiven Back-Tracker-Algorithmus zu erstellen. Ich bekomme dieses Problem beim Ausführen des Programms:
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)
und ehrlich gesagt, an diesem Punkt, nachdem ich ein paar Bugs und Fehler gefunden habe, habe ich keine Ahnung, was falsch sein könnte. Der einzige Hinweis, den ich habe, ist, dass im Schalter ein Fehler vorliegt, dass stack.firstElement() nicht aktualisiert wird und immer gleich ist und in den Fällen etwas falsch eingefügt wird.
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);
}
gesamten 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();
}
Also führe ich den Code einfach erneut aus, und die Fehlerzeile wurde in Zeile 131 geändert. Ich schaue mir auch ein Tutorial über den Intellij-Debugger rn an.
Lösung
EDIT: Problem behoben. Zeilen ändern musste:
int x = stack.firstElement().getKey();
int y = stack.firstElement().getValue();
hinein:
int x = stack.peek().getKey();
int y = stack.peek().getValue();
Es stellt sich heraus, dass die Methode .firstElement() Ihnen nicht das erste Element (das oberste Element des Stapels) gibt, sondern dasjenige, das zuerst eingefügt wurde (immer dasselbe Objekt), sodass am Ende alle Operationen an einem einzelnen Element ausgeführt wurden und nicht mehrere.
Beantwortet von – 22eragon22
Antwort geprüft von – Timothy Miller (FixError Admin)