Representing a Maze

The most direct representation for a rectangular maze is a two-dimensional array. Each row of the maze is one row of the array, and each cell stores what is at that position.

For example, consider this 2D array in Java:

char[][] maze = {
  {'S', '.', '.', '#'},
  {'#', '#', '.', '#'},
  {'.', '.', '.', 'E'}
};

The above array represents the maze shown below:

┌───┬───┬───┬───┐
│ S │   │   │ █ │
├───┼───┼───┼───┤
│ █ │ █ │   │ █ │
├───┼───┼───┼───┤
│   │   │   │ E │
└───┴───┴───┴───┘

The cell in the top-left corner is maze[0][0]. The cell one row below it is maze[1][0]. The cell one column to the right is maze[0][1]. This is why a two-dimensional array fits the problem: the row and column already give us the position.

For this chapter, we will use these characters:

We use . for an open cell because a Java char cannot be empty, and a space is hard to see in code.

In the code, we will not need to treat S, E, and . very differently. They are all cells we are allowed to stand on. The wall is different: a move into # is not legal.

There is another reasonable representation. We could make each cell an object with references to the four adjacent cells:

private static class MazeCell {
  int row, col;
  boolean wall;
  MazeCell up, right, down, left;
}

Then moving right means following the right reference. Moving down means following the down reference. This representation makes the connections between cells explicit, in the same way a linked list makes the next node explicit.

That representation is useful in some settings, especially when the maze is not rectangular. But for a rectangular maze, the array is simpler. We do not need to store four references per cell. If we are at (row, col), then the four adjacent positions are easy to compute:

up:    (row - 1, col)
right: (row, col + 1)
down:  (row + 1, col)
left:  (row, col - 1)

So we will use the two-dimensional array as our main representation.