Reputation: 18572
Maze generation - ArrayIndexOutOfBoundsException
I tried generate maze with two entries at the opposite sides.
But when I trying to run this test program I catch ArrayIndexOutOfBoundsException:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at maze.variation.MyMaze.generateMaze(MyMaze.java:61)
at maze.variation.MyMaze.generateMaze(MyMaze.java:63)
at maze.variation.MyMaze.generateMaze(MyMaze.java:51)
at maze.variation.MyMaze.generateMaze(MyMaze.java:51)
at maze.variation.MyMaze.generateMaze(MyMaze.java:51)
at maze.variation.MyMaze.generateMaze(MyMaze.java:51)
at maze.variation.MyMaze.generateMaze(MyMaze.java:35)
at maze.variation.MyMaze.<init>(MyMaze.java:14)
at maze.variation.MyMaze.main(MyMaze.java:137)
I can't figure out what's wrong. It's some easy failures, but I can't find weak place.
Code:
public class MyMaze {
private int dimension; // dimension of maze
private char[][] grid;
private boolean[][] marked;
private boolean[][] visited;
private boolean done = false;
public MyMaze(int aDimension) {
dimension = aDimension;
grid = new char[dimension][dimension];
init();
generateMaze();
}
private void init() {
// initialize border cells as already visited
visited = new boolean[dimension + 2][dimension + 2];
for (int x = 0; x < dimension + 2; x++)
visited[x][0] = visited[x][dimension + 1] = true;
for (int y = 0; y < dimension + 2; y++)
visited[0][y] = visited[dimension + 1][y] = true;
// initialze all walls as present
visited = new boolean[dimension + 2][dimension + 2];
marked = new boolean[dimension + 2][dimension + 2];
for (int x = 0; x < dimension + 2; x++)
for (int y = 0; y < dimension + 2; y++)
marked[x][y] = true;
}
// generate the maze starting from lower left
private void generateMaze() {
generateMaze(1, 1);
}
// generate the maze
private void generateMaze(int x, int y) {
visited[x][y] = true;
// while there is an unvisited neighbor
while (!visited[x][y + 1] || !visited[x + 1][y] || !visited[x][y - 1]
|| !visited[x - 1][y]) {
// pick random neighbor
while (true) {
double r = Math.random();
if (r < 0.25 && !visited[x][y + 1]) {
marked[x][y] = marked[x][y + 1] = false;
generateMaze(x, y + 1); // 51 line
break;
} else if (r >= 0.25 && r < 0.50 && !visited[x + 1][y]) {
marked[x][y] = marked[x + 1][y] = false;
generateMaze(x + 1, y);
break;
} else if (r >= 0.5 && r < 0.75 && !visited[x][y - 1]) {
marked[x][y] = marked[x][y - 1] = false;
generateMaze(x, y - 1);
break;
} else if (r >= 0.75 && r < 1.00 && !visited[x - 1][y]) { // 61 line
marked[x][y] = marked[x - 1][y] = false;
generateMaze(x - 1, y);
break;
}
}
}
}
// solve the maze starting from the start state
public void solve() {
for (int x = 1; x <= dimension; x++)
for (int y = 1; y <= dimension; y++)
visited[x][y] = false;
done = false;
solve(1, 1);
}
// draw the maze
public void draw() {
for (int x = 1; x <= dimension; x++) {
for (int y = 1; y <= dimension; y++) {
if (marked[x][y]) {
grid[x][y] = '*';
}
}
}
System.out.print(this.grid);
}
/**
* Overridden method to generate a human readable maze state.
*/
@Override
public String toString() {
StringBuffer sb = new StringBuffer(1024);
for (int x = 0; x < this.dimension; x++) {
for (int y = 0; y < this.dimension; y++) {
sb.append(this.grid[x][y]);
}
sb.append("\n");
}
return sb.toString();
}
public static void main(String[] args) {
int userDimension = 40;
MyMaze maze = new MyMaze(userDimension);
maze.draw();
}
}
I don't know how to find solution for creating two entries at opposite sides (north and south) and they need to have connection to maze. Any suggestions?
- How to solve this error trouble?
Edit:
I added this check into while loop:
// pick random neighbor
while (true) {
if (x == 0 || x == 1 || y == 0 || y == 1) continue;
// method's rest
It looks ok now.If you running this code you'll find no output. But it should be.
Why this doesn't print maze correctly?
Upvotes: 1
Views: 2126
Answers (3)
Reputation: 2925
At line 30, in the very beginning of generateMaze(int x, int y), add a System.err.println("dimension is " + dimension + " x is " + x + " y is " + y);
In the error console you will probably see that x or y is outside or close to the boundary at some time. Note that you can't interate too close to the outer boundary since you do direct accesses to neighbors at lines 49, 50, 53, 54, 57, 58, 61 and 62.
Upvotes: 1
Reputation: 375
The first thing I notice in your script is in init() you initialize visited and use for loops to initialize it, and then immediately after you initialize again and don't set any values in it to true. This I think causes the walls to become eliminated. Then later on in the script during generation it becomes possible to be at a wall because none are marked visited initially. Then during maze generation since it's at the 'edge' of the array it may try to reference a cell outside the array which is your error. So remove the second initialization of visited
Another thing you should be wary of is the potential of an infinite while loop. The while loop after determining that there was a neighbor has the potential to continually not pick the right r to get the neighbor in theory, but it does have the potential to slow down tremendously. Instead, I would find all neighbors, put them into an `ArrayList and then pick a random one. See source below.
Another error exists in the draw method. The for loop should iterate with the conditions being x < this.dimension and y < this.dimension instead of <=. Otherwise you'll get ArrayIndexOutOfBounds error.
Finally the println method we'll print a less than valuable representation of the array that contains no information of its contents. Do this instead:
System.out.println(Arrays.deepToString(this.grid));
Here's my finalized version of the code. There is an inner class Cell and a field Cell[][] cells in MyMaze which replaced the need for bridges and the original variables for tracking the state of cells. The outer 2 rows and columns are removed because the ArrayIndexOutOfBoundsException is caught by getCell and returns null when out of bounds. The idea of generation has been altered to prevent excessive calling to avoid getting a stack overflow on large boards. Boards can be rectangular now. The solver is implemented based on A-star algorithm. The output has been updated to produce meaningful representation. The "X" are walls and the "*" is the solved path. It is commented so should be able to read through what's going on
Here is my finalized source :
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;
public class MyMaze {
private int dimensionX, dimensionY; // dimension of maze
private int gridDimensionX, gridDimensionY; // dimension of output grid
private char[][] grid; // output grid
private Cell[][] cells; // 2d array of Cells
private Random random = new Random(); // The random object
// initialize with x and y the same
public MyMaze(int aDimension) {
// Initialize
this(aDimension, aDimension);
}
// constructor
public MyMaze(int xDimension, int yDimension) {
dimensionX = xDimension;
dimensionY = yDimension;
gridDimensionX = xDimension * 4 + 1;
gridDimensionY = yDimension * 2 + 1;
grid = new char[gridDimensionX][gridDimensionY];
init();
generateMaze();
}
private void init() {
// create cells
cells = new Cell[dimensionX][dimensionY];
for (int x = 0; x < dimensionX; x++) {
for (int y = 0; y < dimensionY; y++) {
cells[x][y] = new Cell(x, y, false); // create cell (see Cell constructor)
}
}
}
// inner class to represent a cell
private class Cell {
int x, y; // coordinates
// cells this cell is connected to
ArrayList<Cell> neighbors = new ArrayList<>();
// solver: if already used
boolean visited = false;
// solver: the Cell before this one in the path
Cell parent = null;
// solver: if used in last attempt to solve path
boolean inPath = false;
// solver: distance travelled this far
double travelled;
// solver: projected distance to end
double projectedDist;
// impassable cell
boolean wall = true;
// if true, has yet to be used in generation
boolean open = true;
// construct Cell at x, y
Cell(int x, int y) {
this(x, y, true);
}
// construct Cell at x, y and with whether it isWall
Cell(int x, int y, boolean isWall) {
this.x = x;
this.y = y;
this.wall = isWall;
}
// add a neighbor to this cell, and this cell as a neighbor to the other
void addNeighbor(Cell other) {
if (!this.neighbors.contains(other)) { // avoid duplicates
this.neighbors.add(other);
}
if (!other.neighbors.contains(this)) { // avoid duplicates
other.neighbors.add(this);
}
}
// used in updateGrid()
boolean isCellBelowNeighbor() {
return this.neighbors.contains(new Cell(this.x, this.y + 1));
}
// used in updateGrid()
boolean isCellRightNeighbor() {
return this.neighbors.contains(new Cell(this.x + 1, this.y));
}
// useful Cell representation
@Override
public String toString() {
return String.format("Cell(%s, %s)", x, y);
}
// useful Cell equivalence
@Override
public boolean equals(Object other) {
if (!(other instanceof Cell)) return false;
Cell otherCell = (Cell) other;
return (this.x == otherCell.x && this.y == otherCell.y);
}
// should be overridden with equals
@Override
public int hashCode() {
// random hash code method designed to be usually unique
return this.x + this.y * 256;
}
}
// generate from upper left (In computing the y increases down often)
private void generateMaze() {
generateMaze(0, 0);
}
// generate the maze from coordinates x, y
private void generateMaze(int x, int y) {
generateMaze(getCell(x, y)); // generate from Cell
}
private void generateMaze(Cell startAt) {
// don't generate from cell not there
if (startAt == null) return;
startAt.open = false; // indicate cell closed for generation
ArrayList<Cell> cells = new ArrayList<>();
cells.add(startAt);
while (!cells.isEmpty()) {
Cell cell;
// this is to reduce but not completely eliminate the number
// of long twisting halls with short easy to detect branches
// which results in easy mazes
if (random.nextInt(10)==0)
cell = cells.remove(random.nextInt(cells.size()));
else cell = cells.remove(cells.size() - 1);
// for collection
ArrayList<Cell> neighbors = new ArrayList<>();
// cells that could potentially be neighbors
Cell[] potentialNeighbors = new Cell[]{
getCell(cell.x + 1, cell.y),
getCell(cell.x, cell.y + 1),
getCell(cell.x - 1, cell.y),
getCell(cell.x, cell.y - 1)
};
for (Cell other : potentialNeighbors) {
// skip if outside, is a wall or is not opened
if (other==null || other.wall || !other.open) continue;
neighbors.add(other);
}
if (neighbors.isEmpty()) continue;
// get random cell
Cell selected = neighbors.get(random.nextInt(neighbors.size()));
// add as neighbor
selected.open = false; // indicate cell closed for generation
cell.addNeighbor(selected);
cells.add(cell);
cells.add(selected);
}
}
// used to get a Cell at x, y; returns null out of bounds
public Cell getCell(int x, int y) {
try {
return cells[x][y];
} catch (ArrayIndexOutOfBoundsException e) { // catch out of bounds
return null;
}
}
public void solve() {
// default solve top left to bottom right
this.solve(0, 0, dimensionX - 1, dimensionY -1);
}
// solve the maze starting from the start state (A-star algorithm)
public void solve(int startX, int startY, int endX, int endY) {
// re initialize cells for path finding
for (Cell[] cellrow : this.cells) {
for (Cell cell : cellrow) {
cell.parent = null;
cell.visited = false;
cell.inPath = false;
cell.travelled = 0;
cell.projectedDist = -1;
}
}
// cells still being considered
ArrayList<Cell> openCells = new ArrayList<>();
// cell being considered
Cell endCell = getCell(endX, endY);
if (endCell == null) return; // quit if end out of bounds
{ // anonymous block to delete start, because not used later
Cell start = getCell(startX, startY);
if (start == null) return; // quit if start out of bounds
start.projectedDist = getProjectedDistance(start, 0, endCell);
start.visited = true;
openCells.add(start);
}
boolean solving = true;
while (solving) {
if (openCells.isEmpty()) return; // quit, no path
// sort openCells according to least projected distance
Collections.sort(openCells, new Comparator<Cell>(){
@Override
public int compare(Cell cell1, Cell cell2) {
double diff = cell1.projectedDist - cell2.projectedDist;
if (diff > 0) return 1;
else if (diff < 0) return -1;
else return 0;
}
});
Cell current = openCells.remove(0); // pop cell least projectedDist
if (current == endCell) break; // at end
for (Cell neighbor : current.neighbors) {
double projDist = getProjectedDistance(neighbor,
current.travelled + 1, endCell);
if (!neighbor.visited || // not visited yet
projDist < neighbor.projectedDist) { // better path
neighbor.parent = current;
neighbor.visited = true;
neighbor.projectedDist = projDist;
neighbor.travelled = current.travelled + 1;
if (!openCells.contains(neighbor))
openCells.add(neighbor);
}
}
}
// create path from end to beginning
Cell backtracking = endCell;
backtracking.inPath = true;
while (backtracking.parent != null) {
backtracking = backtracking.parent;
backtracking.inPath = true;
}
}
// get the projected distance
// (A star algorithm consistent)
public double getProjectedDistance(Cell current, double travelled, Cell end) {
return travelled + Math.abs(current.x - end.x) +
Math.abs(current.y - current.x);
}
// draw the maze
public void updateGrid() {
char backChar = ' ', wallChar = 'X', cellChar = ' ', pathChar = '*';
// fill background
for (int x = 0; x < gridDimensionX; x ++) {
for (int y = 0; y < gridDimensionY; y ++) {
grid[x][y] = backChar;
}
}
// build walls
for (int x = 0; x < gridDimensionX; x ++) {
for (int y = 0; y < gridDimensionY; y ++) {
if (x % 4 == 0 || y % 2 == 0)
grid[x][y] = wallChar;
}
}
// make meaningful representation
for (int x = 0; x < dimensionX; x++) {
for (int y = 0; y < dimensionY; y++) {
Cell current = getCell(x, y);
int gridX = x * 4 + 2, gridY = y * 2 + 1;
if (current.inPath) {
grid[gridX][gridY] = pathChar;
if (current.isCellBelowNeighbor())
if (getCell(x, y + 1).inPath) {
grid[gridX][gridY + 1] = pathChar;
grid[gridX + 1][gridY + 1] = backChar;
grid[gridX - 1][gridY + 1] = backChar;
} else {
grid[gridX][gridY + 1] = cellChar;
grid[gridX + 1][gridY + 1] = backChar;
grid[gridX - 1][gridY + 1] = backChar;
}
if (current.isCellRightNeighbor())
if (getCell(x + 1, y).inPath) {
grid[gridX + 2][gridY] = pathChar;
grid[gridX + 1][gridY] = pathChar;
grid[gridX + 3][gridY] = pathChar;
} else {
grid[gridX + 2][gridY] = cellChar;
grid[gridX + 1][gridY] = cellChar;
grid[gridX + 3][gridY] = cellChar;
}
} else {
grid[gridX][gridY] = cellChar;
if (current.isCellBelowNeighbor()) {
grid[gridX][gridY + 1] = cellChar;
grid[gridX + 1][gridY + 1] = backChar;
grid[gridX - 1][gridY + 1] = backChar;
}
if (current.isCellRightNeighbor()) {
grid[gridX + 2][gridY] = cellChar;
grid[gridX + 1][gridY] = cellChar;
grid[gridX + 3][gridY] = cellChar;
}
}
}
}
}
// simply prints the map
public void draw() {
System.out.print(this);
}
// forms a meaningful representation
@Override
public String toString() {
updateGrid();
String output = "";
for (int y = 0; y < gridDimensionY; y++) {
for (int x = 0; x < gridDimensionX; x++) {
output += grid[x][y];
}
output += "\n";
}
return output;
}
// run it
public static void main(String[] args) {
MyMaze maze = new MyMaze(20);
maze.solve();
System.out.print(maze);
}
}
Upvotes: 2
Reputation: 22241
Create a class which will store the maze, and write a getter that is protected against ArrayIndexOutOfBoundsException.
class Maze {
int maze[][];
int getValue(int x, int y){
if (x<0 || x>maze.length) {
return 0;
}
if (y<0 || y>maze[0].length) {
return 0;
}
return maze[x][y];
}
Also provide a setter working in a similar fashion.
Repeat the same work for each 2d array member of your maze.
BTW: consider using enums instead of chars - you'll find they're much more powerful. edit: enum usage code sample
enum Tile {
WALL('*', false), EMPTY(' ', true), WATER('~', false), GRASS('_', true);
private Tile (char representation, boolean passable) {
this.representation=representation;
this.passable=passable;
}
char representation;
boolean passable;
public char getRepresentation() { return representation; }
public boolean isPassable() { return passable; }
}
Tile maze[][];
Upvotes: 1
Related Questions
- Stack Overflow error when traversing through a maze
- Array index out of bounds while traversing edge members of array
- java maze game error going in one direction only, using array
- Array out of Bounds Exception when populating 2D Array maze
- Path Finding Maze-Error
- Maze Program Can't Finish
- Maze Solver ArrayIndexOutOfBoundsException
- Maze solver looping issue java
- Maze solver gets stuck in a loop at a dead-end
- Algorithmic error in java maze generator