This question on stackoverflow is about a two-dimensional array of ints, which is a 1/0 maze. The zeros are the “path”, and the 1s are the “wall”. For example:
1 0 1 1 1
1 0 0 0 1
1 0 1 0 1
1 1 1 0 1
1 1 1 0 1
The goal is to traverse the maze from start to finish, via a recursive function. I came up with the following classes to eliminate much of this problem’s complexity (the poster actually submitted four questions on this one problem within five hours), although I don’t believe it’s useful to the poster, since I think it’s an assignment that would forbid its use.
There are two classes, and an Enum.
Enum: Direction
First, the enum, which defines the direction you want to move in the grid and determines the new indexes (one-at-a-time) based on its movement.
enum Direction {
UP(-1, 0),
DOWN(1, 0),
LEFT(0, -1),
RIGHT(0, 1);
private final int rowSteps;
private final int colSteps;
private Direction(int rowSteps, int colSteps) {
this.rowSteps = rowSteps;
this.colSteps = colSteps;
}
public int getNewRowIdx(int currentRowIdx) {
return (currentRowIdx + getRowSteps());
}
public int getNewColIdx(int currentColIdx) {
return (currentColIdx + getColSteps());
}
public int getRowSteps() {
return rowSteps;
}
public int getColSteps() {
return colSteps;
}
};
Class: MazePosition
The main class is called MazePosition (below). First you set the maze-grid double-array into it, via its int[][] constructor, and store that instance statically:
private static final MazePosition MAZE_HOLDER = new MazePosition(MAZE_GRID);
(This step could be designed better, but it works.)
After setting the maze-grid (which is a one-time-only thing, per-execution), then the x/y constructor is used to declare an initial position:
MazePosition pos = new MazePosition(0, 0);
And after that, just move as necessary:
pos = pos.getNeighbor(Direction.RIGHT). getNeighbor(Direction.RIGHT). getNeighbor(Direction.DOWN);
The value of each position is retrieved by pos.getValue() or pos.isPath() —- 1 is the “wall” and 0 is the “path”. (As an aside: The huge 2d-array should really contain one-bit booleans, instead of 4-byte ints, but *looking* at the array’s code makes sense with ints, and doesn’t with booleans… Note that it should at least be changed to bytes.)
So regarding movement, if you attempt to get a neighbor when there is none, such as moving left at the left edge, an IllegalStateException is thrown. Use the is*Edge() functions to avoid this.
The MazePosition class also has a convenient debugging function called getNineByNine(), which returns a 9×9 grid of the array values (as a string), where the middle item is the current position.
import java.util.Arrays;
import java.util.Objects;
class MazePosition {
//state
private static int[][] MAZE_GRID;
private final int rowIdx;
private final int colIdx;
//internal
private final int rowIdxMinus1;
private final int colIdxMinus1;
public MazePosition(int[][] MAZE_GRID) {
if(this.MAZE_GRID != null) {
throw new IllegalStateException("Maze double-array already set. Use x/y constructor.");
}
MazePosition.MAZE_GRID = MAZE_GRID;
//TODO: Crash if null or empty, or sub-arrays null or empty, or unequal lengths, or contain anything but 0 or -1.
rowIdx = -1;
colIdx = -1;
rowIdxMinus1 = -1;
colIdxMinus1 = -1;
}
public MazePosition(int rowIdx, int colIdx) {
if(MazePosition.MAZE_GRID == null) {
throw new IllegalStateException("Must set maze double-array with: new MazePosition(int[][]).");
}
if(rowIdx < 0 || rowIdx >= MazePosition.getRowCount()) {
throw new IllegalArgumentException("rowIdx (" + rowIdx + ") is invalid.");
}
if(colIdx < 0 || colIdx >= MazePosition.getColumnCount()) {
throw new IllegalArgumentException("colIdx (" + colIdx + ") is invalid.");
}
this.rowIdx = rowIdx;
this.colIdx = colIdx;
rowIdxMinus1 = (rowIdx - 1);
colIdxMinus1 = (colIdx - 1);
}
public boolean isPath() {
return (getValue() == 0); //1???
}
public int getValue() {
return MazePosition.MAZE_GRID[getRowIdx()][getColumnIdx()];
}
public int getRowIdx() {
return rowIdx;
}
public int getColumnIdx() {
return colIdx;
}
public MazePosition getNeighbor(Direction dir) {
Objects.requireNonNull(dir, "dir");
return (new MazePosition(
dir.getNewRowIdx(getRowIdx()),
dir.getNewColIdx(getColumnIdx())));
}
public MazePosition getNeighborNullIfEdge(Direction dir) {
if(isEdgeForDirection(dir)) {
return null;
}
return getNeighbor(dir);
}
public int getNeighborValueNeg1IfEdge(Direction dir) {
MazePosition pos = getNeighborNullIfEdge(dir);
return ((pos == null) ? -1 : pos.getValue());
}
public static final int getRowCount() {
return MAZE_GRID.length;
}
public static final int getColumnCount() {
return MAZE_GRID[0].length;
}
public boolean isEdgeForDirection(Direction dir) {
Objects.requireNonNull(dir);
switch(dir) {
case UP: return isTopEdge();
case DOWN: return isBottomEdge();
case LEFT: return isLeftEdge();
case RIGHT: return isRightEdge();
}
throw new IllegalStateException(toString() + ", dir=" + dir);
}
public boolean isLeftEdge() {
return (getColumnIdx() == 0);
}
public boolean isTopEdge() {
return (getRowIdx() == 0);
}
public boolean isBottomEdge() {
return (getRowIdx() == rowIdxMinus1);
}
public boolean isRightEdge() {
return (getColumnIdx() == colIdxMinus1);
}
public String toString() {
return "[" + getRowIdx() + "," + getColumnIdx() + "]=" + getValue();
}
public String getNineByNine() {
int[][] nineByNine = new int[3][3];
//Middle row
nineByNine[1][1] = getValue();
nineByNine[1][0] = getNeighborValueNeg1IfEdge(Direction.LEFT);
nineByNine[1][2] = getNeighborValueNeg1IfEdge(Direction.RIGHT);
//Top
MazePosition posUp = getNeighborNullIfEdge(Direction.UP);
if(posUp != null) {
nineByNine[0][0] = posUp.getNeighborValueNeg1IfEdge(Direction.LEFT);
nineByNine[0][1] = posUp.getValue();
nineByNine[0][2] = posUp.getNeighborValueNeg1IfEdge(Direction.RIGHT);
}
//Bottom
MazePosition posDown = getNeighborNullIfEdge(Direction.DOWN);
if(posDown != null) {
nineByNine[2][0] = posDown.getNeighborValueNeg1IfEdge(Direction.LEFT);
nineByNine[2][1] = posDown.getValue();
nineByNine[2][2] = posDown.getNeighborValueNeg1IfEdge(Direction.RIGHT);
}
String sLS = System.getProperty("line.separator", "\r\n");
return "Middle position in 9x9 grid is *this*: " + toString() + sLS +
Arrays.toString(nineByNine[0]) + sLS +
Arrays.toString(nineByNine[1]) + sLS +
Arrays.toString(nineByNine[2]);
}
}
What this does not have, is “collision detection” or anything that actually figures out the maze-path for you. It just moves throughout the grid, regardless if it’s moving through walls or not. There could easily be some getNeighborIfNotWall(Direction) and isWallToLeft() functions added, but I’ll leave that to you. ;)
It would not take too much work to make this useable with any two-dimensional array, although I’d probably add diagonal directions, such as UP_LEFT, and the ability to move multiple steps, such as getNeighbor(3, Direction.DOWN).
Demo usage
public class MazePosDemo {
private static final int[][] MAZE_GRID = new int[][] {
//mega maze grid goes here...
};
private static final MazePosition MAZE_HOLDER = new MazePosition(MAZE_GRID);
public static final void main(String[] ignored) {
MazePosition pos = new MazePosition(0, 0);
System.out.println("start: " + pos);
pos = pos.getNeighbor(Direction.RIGHT);
System.out.println("right: " + pos);
pos = pos.getNeighbor(Direction.RIGHT);
System.out.println("right: " + pos);
pos = pos.getNeighbor(Direction.DOWN);
System.out.println("down: " + pos);
pos = pos.getNeighbor(Direction.DOWN);
System.out.println("down: " + pos);
pos = pos.getNeighbor(Direction.RIGHT);
System.out.println("right: " + pos);
pos = pos.getNeighbor(Direction.DOWN);
System.out.println("down: " + pos);
pos = pos.getNeighbor(Direction.LEFT);
System.out.println("left: " + pos);
pos = pos.getNeighbor(Direction.UP);
System.out.println("up: " + pos);
pos = pos.getNeighbor(Direction.UP);
System.out.println("up: " + pos);
System.out.println(pos.getNineByNine());
}
}
Output:
[C:\java_code\]java MazePosDemo
start: [0,0]=1
right: [0,1]=1
right: [0,2]=1
down: [1,2]=1
down: [2,2]=1
right: [2,3]=1
down: [3,3]=0
left: [3,2]=1
up: [2,2]=1
up: [1,2]=1
Middle position in 9×9 grid is *this*: [1,2]=1
[1, 1, 1]
[0, 1, 0]
[0, 1, 1]
Full source code
And here’s the entire source-code file, containing all of the above (including the mega-maze-array):
//Needed only by MazePosition
import java.util.Arrays;
import java.util.Objects;
enum Direction {
UP(-1, 0),
DOWN(1, 0),
LEFT(0, -1),
RIGHT(0, 1);
//config
private final int rowSteps;
private final int colSteps;
private Direction(int rowSteps, int colSteps) {
this.rowSteps = rowSteps;
this.colSteps = colSteps;
}
public int getNewRowIdx(int currentRowIdx) {
return (currentRowIdx + getRowSteps());
}
public int getNewColIdx(int currentColIdx) {
return (currentColIdx + getColSteps());
}
public int getRowSteps() {
return rowSteps;
}
public int getColSteps() {
return colSteps;
}
};
class MazePosition {
//config
private static int[][] MAZE_GRID;
private final int rowIdx;
private final int colIdx;
//internal
private final int rowIdxMinus1;
private final int colIdxMinus1;
public MazePosition(int[][] MAZE_GRID) {
if(this.MAZE_GRID != null) {
throw new IllegalStateException("Maze double-array already set. Use x/y constructor.");
}
MazePosition.MAZE_GRID = MAZE_GRID;
//TODO: Crash if null or empty, or sub-arrays null or empty, or unequal lengths, or contain anything but 0 or -1.
rowIdx = -1;
colIdx = -1;
rowIdxMinus1 = -1;
colIdxMinus1 = -1;
}
public MazePosition(int rowIdx, int colIdx) {
if(MazePosition.MAZE_GRID == null) {
throw new IllegalStateException("Must set maze double-array with: new MazePosition(int[][]).");
}
if(rowIdx < 0 || rowIdx >= MazePosition.getRowCount()) {
throw new IllegalArgumentException("rowIdx (" + rowIdx + ") is invalid.");
}
if(colIdx < 0 || colIdx >= MazePosition.getColumnCount()) {
throw new IllegalArgumentException("colIdx (" + colIdx + ") is invalid.");
}
this.rowIdx = rowIdx;
this.colIdx = colIdx;
rowIdxMinus1 = (rowIdx - 1);
colIdxMinus1 = (colIdx - 1);
}
public boolean isPath() {
return (getValue() == 0); //1???
}
public int getValue() {
return MazePosition.MAZE_GRID[getRowIdx()][getColumnIdx()];
}
public int getRowIdx() {
return rowIdx;
}
public int getColumnIdx() {
return colIdx;
}
public MazePosition getNeighbor(Direction dir) {
Objects.requireNonNull(dir, "dir");
return (new MazePosition(
dir.getNewRowIdx(getRowIdx()),
dir.getNewColIdx(getColumnIdx())));
}
public MazePosition getNeighborNullIfEdge(Direction dir) {
if(isEdgeForDirection(dir)) {
return null;
}
return getNeighbor(dir);
}
public int getNeighborValueNeg1IfEdge(Direction dir) {
MazePosition pos = getNeighborNullIfEdge(dir);
return ((pos == null) ? -1 : pos.getValue());
}
public static final int getRowCount() {
return MAZE_GRID.length;
}
public static final int getColumnCount() {
return MAZE_GRID[0].length;
}
public boolean isEdgeForDirection(Direction dir) {
Objects.requireNonNull(dir);
switch(dir) {
case UP: return isTopEdge();
case DOWN: return isBottomEdge();
case LEFT: return isLeftEdge();
case RIGHT: return isRightEdge();
}
throw new IllegalStateException(toString() + ", dir=" + dir);
}
public boolean isLeftEdge() {
return (getColumnIdx() == 0);
}
public boolean isTopEdge() {
return (getRowIdx() == 0);
}
public boolean isBottomEdge() {
return (getRowIdx() == rowIdxMinus1);
}
public boolean isRightEdge() {
return (getColumnIdx() == colIdxMinus1);
}
public String toString() {
return "[" + getRowIdx() + "," + getColumnIdx() + "]=" + getValue();
}
public String getNineByNine() {
int[][] nineByNine = new int[3][3];
//Middle row
nineByNine[1][1] = getValue();
nineByNine[1][0] = getNeighborValueNeg1IfEdge(Direction.LEFT);
nineByNine[1][2] = getNeighborValueNeg1IfEdge(Direction.RIGHT);
//Top
MazePosition posUp = getNeighborNullIfEdge(Direction.UP);
if(posUp != null) {
nineByNine[0][0] = posUp.getNeighborValueNeg1IfEdge(Direction.LEFT);
nineByNine[0][1] = posUp.getValue();
nineByNine[0][2] = posUp.getNeighborValueNeg1IfEdge(Direction.RIGHT);
}
//Bottom
MazePosition posDown = getNeighborNullIfEdge(Direction.DOWN);
if(posDown != null) {
nineByNine[2][0] = posDown.getNeighborValueNeg1IfEdge(Direction.LEFT);
nineByNine[2][1] = posDown.getValue();
nineByNine[2][2] = posDown.getNeighborValueNeg1IfEdge(Direction.RIGHT);
}
String sLS = System.getProperty("line.separator", "\r\n");
return "Middle position in 9x9 grid is *this*: " + toString() + sLS +
Arrays.toString(nineByNine[0]) + sLS +
Arrays.toString(nineByNine[1]) + sLS +
Arrays.toString(nineByNine[2]);
}
}
public class MazePosDemo {
private static final int[][] MAZE_GRID = new int[][] {
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1},
{1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1},
{1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
{1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1},
{1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1},
{1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1},
{1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
{1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1},
{1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1},
{1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1},
{1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1},
{1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1},
{1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
{1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1},
{1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1},
{1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1},
{1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1},
{1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1},
{1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
{1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1},
{1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1},
{1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1},
{1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
{1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1},
{1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
{1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1},
{1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1},
{1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1},
{1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1},
{1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1},
{1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
{1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1},
{1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1}};
private static final MazePosition MAZE_HOLDER = new MazePosition(MAZE_GRID);
public static final void main(String[] ignored) {
MazePosition pos = new MazePosition(0, 0);
System.out.println("start: " + pos);
pos = pos.getNeighbor(Direction.RIGHT);
System.out.println("right: " + pos);
pos = pos.getNeighbor(Direction.RIGHT);
System.out.println("right: " + pos);
pos = pos.getNeighbor(Direction.DOWN);
System.out.println("down: " + pos);
pos = pos.getNeighbor(Direction.DOWN);
System.out.println("down: " + pos);
pos = pos.getNeighbor(Direction.RIGHT);
System.out.println("right: " + pos);
pos = pos.getNeighbor(Direction.DOWN);
System.out.println("down: " + pos);
pos = pos.getNeighbor(Direction.LEFT);
System.out.println("left: " + pos);
pos = pos.getNeighbor(Direction.UP);
System.out.println("up: " + pos);
pos = pos.getNeighbor(Direction.UP);
System.out.println("up: " + pos);
System.out.println(pos.getNineByNine());
}
}
aliteralmind -- Computer Programming Blog 