`Line`

objects, which is in fact how that maze would be drawn. But if your maze is defined only by `Line`

s, you will find that it becomes rather difficult to figure out where the walls are (in order to keep the player from walking through them) or to write code that will automatically generate a larger and more interesting maze.A better approach would be to have the maze itself be defined by an array that lists out which walls are open and which are closed. There are several ways to do that, but the approach I chose was to have a two-dimensional

`boolean`

array `hwalls`

whose entries indicate whether a particular horizontal wall is there or not, and another array `vwalls`

for the vertical walls.Using this approach, I would first start out by creating the two arrays. If I am trying to represent the maze shown above, my

`hwalls`

will have to have a width of 3, but a height of 4, because there are actually four rows of horizontal walls (the top of the maze, the bottom, and two rows in between). Similarly, `vwalls`

will have a width of 4 and a height of 3:

hwalls = new boolean[3][4];

vwalls = new boolean[4][3];

I can set up the walls to match the maze above by setting individual entries of the arrays. Because a

`boolean`

array starts out full of `false`

, and I'm lazy and therefore want to set as few entries as possible, I decided to have a value of `true`

stand for an open wall. So, for example, if I am standing in the top left corner, the wall below me is open; this is in the first column of horizontal walls, but in the second row (since the top is a row). So, I would do this:

hwalls[0][1] = true;

I do the same sort of thing to set up all the other walls. Before you go on, check your understanding of this: make sure that you can look at each line below and match it up to one of the openings in the maze I showed you.

hwalls[0][2] = true;

hwalls[1][1] = true;

hwalls[2][1] = true;

hwalls[2][2] = true;

vwalls[1][1] = true;

vwalls[1][2] = true;

vwalls[2][0] = true;

`false`

. The code for that will look like this:

for(int x = 0; x < hwalls.length; x++) {

for(int y = 0; y < hwalls[x].length; y++) {

if(!hwalls[x][y]) {

drawLine(x, y, x + 1, y, canvas);

}

}

}

for(int x = 0; x < vwalls.length; x++) {

for(int y = 0; y < vwalls[x].length; y++) {

if(!vwalls[x][y]) {

drawLine(x, y, x, y + 1, canvas);

}

}

}

This code should be familiar enough to not need much explanation. I am simply looping through every (x, y) pair in each wall array, and drawing the wall only if the value there is false. Notice that the horizontal walls are drawn at a constant

`y`

, from one `x`

to the next, an vice versa for the vertical walls.The question here, then, is: how does that

`drawLine()`

method work? It takes a pair of end points in maze coordinates, and draws them on the screen, which means that it needs to convert those coordinates to pixels somehow. I chose to draw each wall of the maze as being 50 pixels long, starting at the point (25, 25); thus, any corner `(x, y)`

of the maze will be drawn at `(25 + 50 * x, 25 + 50 * y)`

on the screen.Using good programming practice, I defined constants to hold the values for the wall length and origin. I also defined a constant BasicStroke to use for the walls so that they will be drawn thicker and rounded, as you see above. My

`drawLine()`

method looks like this:

private static final int ORIGIN_X = 25;

private static final int ORIGIN_Y = 25;

private static final int WALL_LENGTH = 50;

private static final BasicStroke STROKE = new BasicStroke(7f, BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND);

private void drawLine(int x1, int y1, int x2, int y2, DrawingCanvas canvas) {

Line line = new Line(ORIGIN_X + WALL_LENGTH * x1, ORIGIN_Y + WALL_LENGTH * y1,

ORIGIN_X + WALL_LENGTH * x2, ORIGIN_Y + WALL_LENGTH * y2, canvas);

line.setStroke(STROKE);

}

`x`

goes down by 1 and my `y`

doesn't change. We will find that in the maze program we will make use of both ways of representing direction.In order to give names to the directions, we can just define integer constants representing the four directions in which it is possible to go:

private static final int UP = 0, LEFT = 1, DOWN = 2, RIGHT = 3;

I defined these in order going around the circle because that will be convenient later on. For example, if I want to turn left, all I need to do is add one to the direction number.

In order for these directions to be useful to us, we need some way to take one of these numbered directions and figure out the change in x and y corresponding to one step in that direction. The most straightforward way to do this would be with

`if..else`

statements:

private int dx(int direction) {

if(direction == UP) {

return 0;

} else if(direction == LEFT) {

return -1;

} else if(direction == DOWN) {

return 0;

} else { // direction == RIGHT

return 1;

}

}

private int dy(int direction) {

if(direction == UP) {

return -1;

} else if(direction == LEFT) {

return 0;

} else if(direction == DOWN) {

return 1;

} else { // direction == RIGHT

return 0;

}

}

The idea here is that if I am given some

`direction`

and I want to move the player in that direction, I can add some multiple of `dx(direction)`

to his `x`

coordinate and some multiple of `dy(direction)`

to his `y`

coordinate. The names "dx" and "dy" are commonly used in math to stand for a little step in the `x`

or `y`

direction.`UP`

or `LEFT`

means, the next step is to have it listen for those arrow keys and move in the appropriate direction. First, we need something to move. In the constructor, I'll add in a line to create a red circle that will stand for the player:

player = new FilledOval(ORIGIN_X + .2 * WALL_LENGTH, ORIGIN_Y + .2 * WALL_LENGTH,

.6 * WALL_LENGTH, .6 * WALL_LENGTH, Color.RED, canvas);

Next, I'll create a method which, given a direction, will move the player one wall length in that direction. This is where we can make use of the

`dx()`

and `dy()`

methods:

private void tryToMove(int direction) {

player.move(dx(direction) * WALL_LENGTH, dy(direction) * WALL_LENGTH);

}

I called this method "try to move" because, in just a second, we'll change it so that if there is a wall in the way, nothing will happen.

Finally, we need to receive the various key events and try to move the player in response. I will create a KeyInterpreter in the constructor, telling it to send messages to

`this`

when a key is pressed:

new KeyInterpreter(this, canvas);

Lastly, we need to write methods to handle the four arrow keys. Since we already have the

`tryToMove()`

method, this is easy to do:

public void onUpPress() { tryToMove(UP); }

public void onLeftPress() { tryToMove(LEFT); }

public void onDownPress() { tryToMove(DOWN); }

public void onRightPress() { tryToMove(RIGHT); }

I want to change the

`tryToMove()`

method so that it will move only if there is no wall in the direction you are trying to move. A good first step, then, would be to write a method to answer the question, "Is there an opening in this `direction`

from this location in the maze?" If you remember how our walls work, you might realize that in order to do this, we need to check the `hwalls`

and `vwalls`

arrays.

private boolean isOpen(int x, int y, int direction) {

if(direction == UP) {

return hwalls[x][y];

} else if(direction == LEFT) {

return vwalls[x][y];

} else if(direction == DOWN) {

return hwalls[x][y + 1];

} else { // direction == RIGHT

return vwalls[x + 1][y];

}

}

Notice that here

`x`

and `y`

are the coordinates of a grid in the maze,

private void tryToMove(int direction) {

int x = (player.getX() - ORIGIN_X) / WALL_LENGTH;

int y = (player.getY() - ORIGIN_Y) / WALL_LENGTH;

if(isOpen(x, y, direction)) {

player.move(dx(direction) * WALL_LENGTH, dy(direction) * WALL_LENGTH);

}

}

Remember, when I subtract the origin position from the player's position, I get a number from 0 to 50 if the player is in the first cell, 50 to 100 in the next cell, and so on. Because of the way that integers divide in Java, ignoring the remainder, if I divide this by the wall length, I will get just 0 if the player is in the first cell, 1 in the next cell, and so on.

This section is not strictly necessary, so, if you like, you could skip it, and keep using the same little maze. However, I think this will make things a lot more interesting.

The applet shown above demonstrates two different maze generation algorithms. Clicking on the top half of the applet will generate a maze using what I call the "accretion" algorithm - starting with one cell in the middle, new cells adjacent to the connected part of the maze are added to the it by opening up walls to attach them in. Clicking on the bottom half will generate a maze using what I call the "deletion" algorithm: walls are deleted randomly, one by one, until everything is connected.

Here is a link to an applet that will allow you to see these two maze generation algorithms in action. Watching this might be a good idea to help you understand what follows.

In order to do this, we need to somehow label which cells are already part of the maze and which are next to it, and thus ready to be connected. The simplest way to do this is with an array of

`int`

values, one per cell; we'll let a particular value (say, -1) represent a cell that is already part of the maze; otherwise, the value will give the number of connected (-1) cells neighboring that cell.In order to attach another cell, we first set its value to -1, to denote that it is connected to the growing maze. Then, we first pick one of the -1 cells next to it, and erase the wall between the two. Finally, we add 1 to every cell next to it that is not already -1, since all those cells now have one more connected neighbor.

The method that joins a cell in this way is shown below. It marks the cell as connected, then loops through the four adjacent cells, incrementing their value if they are

private void join(int x, int y, int[][] connected) {

int join = 1 + (int)(Math.random() * connected[x][y]);

connected[x][y] = -1;

for(int direction = 0; direction < 4; direction++) {

int endX = x + dx(direction);

int endY = y + dy(direction);

// Check to make sure that (endX, endY) is inside the maze

if(endX >= 0 && endX < connected.length && endY >= 0 && endY < connected[x].length) {

if(connected[endX][endY] == -1) {

// This neighbor is one of the already-connected neighbors. Check if it

// is the one we chose to join this cell to.

join--;

if(join == 0) {

setOpen(x, y, direction);

}

} else {

// This neighbor could now be connected to this cell. Add to its

// count of possible connections.

connected[endX][endY]++;

}

}

}

}

Notice how I choose which cell to link this one to. I know how many possible links there are, since this is just the value of

`connected[x][y]`

. So, I pick a number from 1 to that value, and every time I see a possible link, I count down. When I get to zero, I choose that cell to link to.Here I am making use of a method called

`setOpen()`

. It is designed the same way as `isOpen()`

except that, instead of checking an entry in the walls array, it sets that entry to `true`

.Our next job is to write a method that will randomly pick one of the cells that has a value greater than zero, and call

`join()`

for it. To choose a cell, we can use the same trick we did for choosing a direction to attach. If we know how many cells there are left to join, we can choose a random number from 1 to that number, then scan through the whole array, count down by one every time we find a candidate cell, and connect whatever cell we are at when the count reaches zero.The first problem here, then, is figuring out how many cells are available to connect. I separated this out into another method:

private int countConnectableCells(int[][] connected) {

int count = 0;

for(int x = 0; x < connected.length; x++) {

for(int y = 0; y < connected[x].length; y++) {

if(connected[x][y] > 0) count++;

}

}

return count;

}

Now, connecting a random cell is just a matter of picking a random number

`n`

up to that count, then searching through the grid again and connecting the `n`

th connectable cell that we find. We also want this method to signal somehow if it discovers that there are no cells left to connect; I did this by having it return `true`

or `false`

.

private boolean connectRandomCell(int[][] connected) {

// As we search through the whole maze, we will find a total of (toConnect)

// cells available to be connected. We want to choose a random one of those.

// So, start with a number from 1 to (toConnect), count down every time we

// find a valid cell, and when we get to zero, use that cell.

int connectableCount = countConnectableCells(connected);

if(connectableCount == 0) return false;

int cell = 1 + (int)(Math.random() * connectableCount);

for(int x = 0; x < connected.length; x++) {

for(int y = 0; y < connected[x].length; y++) {

if(connected[x][y] > 0) {

cell--;

if(cell == 0) join(x, y, connected);

}

}

}

return true;

}

With that method done, creating the method to generate the whole maze is actually very simple. It will call

`join()`

once to connect up one random "seed" cell, then it will keep calling `connectRandomCell()`

until it returns `false`

.

private void accretionMaze(int width, int height) {

hwalls = new boolean[width][height + 1];

vwalls = new boolean[width + 1][height];

int[][] connected = new int[width][height];

join((int)(Math.random() * width), (int)(Math.random() * height), connected);

while(connectRandomCell(connected)) { }

}

Another possible maze generation algorithm, one that doesn't have the biases we see here, would be to randomly delete walls until everything is connected. With this algorithm, there will be several connected parts of the maze growing in different places, which then join with each other as walls are removed. The only rule we need is that, in order to avoid forming a loop, a wall cannot be removed if the two cells on either side of it are already part of the same connected group.

As with the accretion algorithm, we will keep track of how the maze is progressing using an array of

`int`

s, one for each cell. But this time, the values in that array will denote what group each cell is part of. Originally, each cell is in its own group, but every time a wall is removed, the cells in the group on one side of the wall are added into the group they were just joined to.The first method that I will write does the simple job of locating all cells that belong to a particular group, and assigning them to a different group. This will be done every time that a wall is deleted:

private void renumber(int startGroup, int endGroup, int[][] groups) {

for(int x = 0; x < groups.length; x++) {

for(int y = 0; y < groups[x].length; y++) {

if(groups[x][y] == startGroup) {

groups[x][y] = endGroup;

}

}

}

}

That done, we can now write the method that creates the maze. First, it assigns every cell in the maze a unique number. Then, as long as there is more than one group present, it will randomly pick and remove a wall.

Choosing what wall to remove is somewhat complicated. First we will make a choice between deleting a vertical wall or a horizontal one. We can represent the wall we chose to delete in terms of the (x, y) of a cell and the direction of the wall. Next, we have to check whether that wall has already been opened up. Finally, we also have to check whether the two cells on either side of that wall are part of the same group; if they are, we can't delete that wall.

private void deletionMaze(int width, int height) {

hwalls = new boolean[width][height + 1];

vwalls = new boolean[width + 1][height];

int totalGroups = 0;

int[][] groups = new int[width][height];

for(int x = 0; x < width; x++) {

for(int y = 0; y < height; y++) {

groups[x][y] = totalGroups++;

}

}

while(totalGroups > 1) {

int x, y, direction;

if(Math.random() < .5) {

// delete a vertical wall

x = (int)(Math.random() * (width - 1));

y = (int)(Math.random() * height);

direction = RIGHT;

} else {

// delete a horizontal wall

x = (int)(Math.random() * width);

y = (int)(Math.random() * height - 1);

direction = DOWN;

}

if(!isOpen(x, y, direction)) {

// There is a wall here to delete; check if it joins a group to itself

int startGroup = groups[x][y];

int endGroup = groups[x + dx(direction)][y + dy(direction)];

if(startGroup != endGroup) {

setOpen(x, y, direction);

renumber(startGroup, endGroup, groups);

totalGroups--;

}

}

}

}

You can see this generator in action by clicking the lower half of the applet above (4).

It turns out that it is very easy to describe how to move to solve a maze in this way. If the space in front of you is blocked, you turn to the right; otherwise, you turn to the left. We could write this very simply in code:

int direction = UP;

while(true) {

if(tryToMove(direction)) {

direction = left(direction);

} else {

direction = right(direction);

}

}

Here, I have changed the

`tryToMove()`

method so that it returns a `boolean`

indicating whether it was able to move. I have also written some simple methods to find the direction that is right, left, or reverse from a given direction:

private int right(int direction) {

return (direction + 3) % 4;

}

// etc.

The interesting question is: how can we make this maze solver animate what it is doing as it goes along? To do that, we can convert our maze class into an ActiveObject, then put the code above into the

`run()`

method, with a short pause after every time that the "player" successfully moves.`ActiveObject`

to produce animation will come in useful in the next section, when we try to make it possible for the player to move smoothly around in the maze.The code would look something like this:

private void solveMaze() {

int width = hwalls.length;

int height = vwalls[0].length;

int[][] distances = new int[width][height];

setDistance(0, 0, 1, distances);

solveMaze(width - 1, height - 1, distances);

}

private void setDistance(int x, int y, int distance, int[][] distances) {

if(distances[x][y] != 0) return;

distances[x][y] = distance;

for(int direction = 0; direction < 4; direction++) {

if(isOpen(x, y, direction)) {

setDistance(x + dx(direction), y + dy(direction), distance + 1, distances);

}

}

}

private void solveMaze(int x, int y, int[][] distances) {

int distance = distances[x][y];

for(int direction = 0; direction < 4; direction++) {

if(isOpen(x, y, direction)) {

int nx = x + dx(direction);

int ny = y + dy(direction);

if(distances[nx][ny] < distance) {

new Line(ORIGIN_X + WALL_LENGTH * (x + .5), ORIGIN_Y + WALL_LENGTH * (y + .5),

ORIGIN_X + WALL_LENGTH * (nx + .5), ORIGIN_Y + WALL_LENGTH * (ny + .5),

Color.RED, canvas);

solveMaze(nx, ny, distances);

}

}

}

}

The idea here is that

`setDistance()`

marks a cell only if it has not yet been marked - to avoid doubling back on itself - and then marks all cells that can be reached from that cell as being at one greater distance. Once it is done marking everything, `solveMaze()`

takes over: starting from the end cell, it tracks backwards to the start by only going in a direction such that the distance counts down.Using this solver, you can easily see that the deletion algorithm (clicking the lower half of the applet) tends to make more difficult mazes than the accretion algorithm (clicking the upper half). If you wanted to, you could also use a solver like this to try to make the maze more difficult, by regenerating the maze if the solution path was too short. Or, you could use the distance array to place valuable objects - say, a key that lets you get to the next level - in less accessible parts of the maze.