Maze: Third Person

Table of Contents

1. Introduction

Our goal in this section will be to create a program that allows the player to move an object around in a maze. The walls of the maze should block movement. In doing this, we will develop and practice using a system for representing the walls using arrays; we will continue to use this same system even after we move on to more sophisticated movement and rendering options.
Your browser doesn't do Java.
DrawMaze.java

2. Drawing the maze

2.1. Using an array to represent walls

Our first task is to figure out how to simply draw the maze itself. Suppose that you are trying to write code to draw the maze shown to the right. You might start thinking about breaking it down into Line objects, which is in fact how that maze would be drawn. But if your maze is defined only by Lines, 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;

2.2. Drawing walls based on the array

At this point, I have an array that represents my desired maze, but I can't yet see it. The next step is to go through the wall arrays and draw a wall wherever I find a value of 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);
}

Your browser doesn't do Java.
MoveMaze.java

3. Moving around

Our next step will be to add an object representing the player, and make it possible for him to move around the maze using the arrow keys. There are two things we need to do to get this working: first, we need to get our program to understand the four directions (up, down, left, right) - it needs to somehow be able to translate a direction into a movement. Then, we need to have the program receive key events when the arrow keys are pressed, and respond by moving the player.

3.1. Representing the directions

There are two ways that we can talk about a direction. One is to use words like "up" or "right" or "north-north-west." But when we are dealing with something happening on a coordinate system, there is another, more natural way, to talk about a direction: we can say how much your x and y coordinates change by if you move in that direction. So, for example, going one step to the left means that my 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.

3.2. Moving the player

Now that our program "knows" what 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); }

Your browser doesn't do Java.
WallsMaze.java

3.3. Making the walls block the player

If you tried out the applet in the last section, you probably moved just through open spaces for a while, because you're used to walls being solid, but if you tried to move through a wall, you may have been surprised to discover that you were able to go right through walls, and even out of the maze entirely. That is the next thing that we want to fix.

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, not the pixel coordinates of the player on the screen. So, when we want to ask if a wall is open, we need to figure out what grid the player is in:

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.
Your browser doesn't do Java.
GenerateMaze.java

4. Maze generation

So far, we have used the same, small maze the whole time. Making a new maze, especially a much bigger one, would be difficult, because we need to carefully count where each opening is and code it in. It would be much better if we could simple have the computer randomly generate a maze for us.

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.

4.1. The accretion algorithm

In case you're wondering, for something to "accrete" means that it is growing by having new pieces attached to it. Cities tend to grow by accretion: new buildings are added on the edges, causing the city to gradually grow. If you stir up a few Cheerios in a bowl of milk, they will tend to accrete into a single clump in the middle or attached to the sides. Generating a maze by accretion, then, means to start out with a small maze (say, just one cell) and grow it by attaching new cells along the edges of the currently connected part.

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 not yet connected and forming a connection to one of those that is already connected.

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 nth 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)) { }
}

4.2. The deletion algorithm

If you click a few times on the top half of the applet above (4) to generate mazes by accretion, you will notice that they tend to be somewhat disappointingly simple. Since the maze grows from one point, the solution path tends to just go in to that center point, then back out to the end point. Also, there are a large number of single-cell dead ends. This makes sense when you remember that cells are attached one at a time.

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 ints, 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).

5. Maze solving

Your browser doesn't do Java.
SolveMaze.java

5.1. Following the left wall

One last, interesting thing we could do at this point is to write a program to automatically move through a maze. Probably the most famous maze-solving algorithm is to simply keep your hand on one wall as you walk; since all the walls are connected, you are guaranteed to reach every point in the maze, provided that there are no "loops" in the maze.

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.

6. Summary

At this point, we have created a program that will randomly generate a maze, and allow the player to navigate through it using the arrow keys. In doing this, we have gained experience with using arrays in various ways to represent the walls of the maze and to store the state of the maze while it is being generated. We have also written a program that will animate solving this maze. Using 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.
Your browser doesn't do Java.
MazePathFinder.java

6.1. Finding the minimum distance to each point

If you want to have the computer automatically find the solution path - perhaps to count how many steps it took and reject the maze if it is too easy - then moving along the left wall is not the most efficient way to do it, since that requires quite a lot of backtracking. A better approach is to calculate, for each cell, how far from the start it is, and continue this process recursively until you get to the end. In other words, label the top left corner "1", then label each cell you can reach from there "2", then label each cell you can reach from a 2, with the exception of the cells you have already marked, and so on. In the end, the bottom left cell will have a value equal to the minimum number of steps needed to get there, and you can find the path back to the start by simply tracing back from the end, always stepping in a direction that takes you to a lower numbered (closer to the start) cell.

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.

back to Maze.