Reputation: 49
I am attempting to make a random maze generator using Java and the recursive backtracking algorithm. I am getting stack overflow when I try to run this code. I know some about stack, I don't think this is infinite recursion. My guess is that I have a big logic error. Do I have to allocate more memory?
The stack trace:
Exception in thread "main" java.lang.StackOverflowError
at java.base/java.util.Vector.elementAt(Vector.java:499)
at java.base/java.util.Stack.peek(Stack.java:103)
at java.base/java.util.Stack.pop(Stack.java:84)
at mazeMaker.Maze.generateMaze(Maze.java:115)
at mazeMaker.Maze.generateMaze(Maze.java:115)
...
at mazeMaker.Maze.generateMaze(Maze.java:115)
at mazeMaker.Maze.generateMaze(Maze.java:115)
Main.java
package mazeMaker;
public class Main
{
public static void main(String[] args)
{
Maze mainMaze = new Maze(20, 30);
}
}
Maze.java
package mazeMaker;
import java.util.Random;
import java.util.Stack;
public class Maze
{
public int xSize = 0;
public int ySize = 0;
public int totalDimensions = 0;
Random randomGenerator = new Random();
public Cell[][] cellData;
public Stack<Cell> cellStack = new Stack<Cell>();
Cell tempCell; // Temporary variable used for maze generation
public Maze(int xSize, int ySize)
{
cellData = new Cell[xSize][ySize];
this.xSize = xSize;
this.ySize = ySize;
this.totalDimensions = this.xSize * this.ySize;
// Initialize array objects
for (int i = 0; i < this.xSize; i++)
{
for (int j = 0; j < this.ySize; j++)
{
cellData[i][j] = new Cell();
}
}
// Assign x and y positions
for (int i = 0; i < this.xSize; i++)
{
for (int j = 0; j < this.ySize; j++)
{
cellData[i][j].xPos = i;
cellData[i][j].yPos = j;
}
}
initBoundries();
generateMaze();
}
private void initBoundries()
{
// Initialize the border cells as visited so we don't go out of bounds
int m = this.xSize;
int n = this.ySize;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (i == 0 || j == 0 || i == n - 1 || j == n - 1)
cellData[i][j].hasBeenVisited = true;
}
}
}
private void generateMaze(int x, int y)
{
// Set current cell as visited
cellData[x][y].hasBeenVisited = true;
// While there are unvisited neighbors
while (!cellData[x][y+1].hasBeenVisited || !cellData[x+1][y].hasBeenVisited || !cellData[x][y-1].hasBeenVisited || !cellData[x-1][y].hasBeenVisited)
{
// Select a random neighbor
while (true)
{
int r = randomGenerator.nextInt(4);
if (r == 0 && !cellData[x][y+1].hasBeenVisited)
{
cellStack.push(cellData[x][y]);
cellData[x][y].hasNorthWall = false;
cellData[x][y+1].hasSouthWall = false;
generateMaze(x, y + 1);
break;
}
else if (r == 1 && !cellData[x+1][y].hasBeenVisited)
{
cellStack.push(cellData[x][y]);
cellData[x][y].hasEastWall = false;
cellData[x+1][y].hasWestWall = false;
generateMaze(x+1, y);
break;
}
else if (r == 2 && !cellData[x][y-1].hasBeenVisited)
{
cellStack.push(cellData[x][y]);
cellData[x][y].hasSouthWall = false;
cellData[x][y-1].hasNorthWall = false;
generateMaze(x, y-1);
break;
}
else if (r == 3 && !cellData[x-1][y].hasBeenVisited)
{
cellStack.push(cellData[x][y]);
cellData[x][y].hasWestWall = false;
cellData[x-1][y].hasEastWall = false;
generateMaze(x-1, y);
break;
}
}
}
// There are no unvisited neighbors
tempCell = cellStack.pop();
generateMaze(tempCell.xPos, tempCell.yPos);
}
// Begin generating maze at top left corner
private void generateMaze()
{
generateMaze(1,1);
}
}
Cell.java
package mazeMaker;
public class Cell
{
public boolean isCurrentCell;
public boolean hasBeenVisited;
public boolean hasNorthWall;
public boolean hasSouthWall;
public boolean hasEastWall;
public boolean hasWestWall;
public int xPos;
public int yPos;
}
Upvotes: 0
Views: 110
Reputation: 36
I tried to run your project on my own environment but unfortunately, I was not able to reproduce your issue.
However, I was facing an IndexOutOfBound
exception in the method generateMaze. While I was solving this, I figured out that there was an issue in the initBoudaries
method.
Indeed, when you set the boolean hasBeenVisited
to true, you do not use the right variable in the IF clause. Here is the version I tried instead :
private void initBoundries()
{
// Initialize the border cells as visited so we don't go out of bounds
for (int i = 0; i < this.xSize; i++)
{
for (int j = 0; j < ySize; j++)
{
if (i == 0 || j == 0 || i == xSize - 1 || j == ySize - 1)
cellData[i][j].hasBeenVisited = true;
}
}
}
Now about the emptyStackException
, I think that if this stack is empty, this means that there is no more cell to handle (as you mentioned in your comment) and the program must end. If I am right, just make sure to test if your stack is empty before call the method pop()
on it like this :
// There are no unvisited neighbors
if (!cellStack.isEmpty()) {
tempCell = cellStack.pop();
generateMaze(tempCell.xPos, tempCell.yPos);
}
Hope it will help.
Upvotes: 1
Reputation: 42829
The method generateMaze
can never terminate not even by chance for some simple reason:
For terminating the generateMaze
method would need to finish it's execution - it has to return.
There are no return
statements in this method, therefore it has to pass the while loops and then continue until the execution reaches and finishes the last statement of the method.
However the last statement is generateMaze(tempCell.xPos, tempCell.yPos);
which starts a new recursion, therefore your code can never ever terminate!
Upvotes: 2