Maze: First Person

Table of Contents

1. Introduction

The program that we ended up in the last section is still a long way from what we eventually want, which is a program that will allow the player to move around freely in a three dimensional maze. To make the transition to three dimensional view as easy as possible, we will first try to change our program from "third person" to "first person." In other words, instead of having the player be an object that moves around a static maze, we will instead draw the maze from the "point of view" of the player, so that the player is always at the center of the screen moving up, and the maze moves and rotates about it.
Your browser doesn't do Java.
SmoothMaze.java

2. Smooth movement

Our current movement scheme has the player jump one step every time a key is pressed. We would like to have the player instead move smoothly in one direction as long as a key is held down.

2.1. Representing the player's position

To accomplish this, we first need a way to represent the player position that will allow the player to be positioned anywhere in the maze, not just at the center of a cell. I chose to use two double instance variables to represent the position of the player in maze coordinates; in other words, px = 3.9, py = 1.4 means that the player is near the middle right of the cell (3, 1) - on the right, because the x value is 3.9, very close to the next cell at 4, and in the middle vertically, because 1.4 is about halfway between 1 and 2.

These two variables will be the "official" record of the player's position; the player object will simply be moved to match px and py whenever they are changed. To do this, I wrote a method that uses px and py to set the position of the player:

private void positionPlayer() {
    player.moveTo(ORIGIN_X + (px - .3) * WALL_LENGTH, ORIGIN_Y + (py - .3) * WALL_LENGTH);
}

2.2. Moving the player smoothly

In order to move the player smoothly as long as a key is held down, there are actually two steps required. First, we need to have pressing and releasing the keys set some instance variable indicating what velocity the player ought to be moving with. Next, our maze object should be running as an active object, periodically adding that velocity to the player's position.

The key control is very straightforward; we will simply add methods to respond to key release events as well as key press events:

private double vx, vy;

private void press(int direction) {
    vx += dx(direction);
    vy += dy(direction);
}

private void release(int direction) {
    vx -= dx(direction);
    vy -= dy(direction);
}

public void onUpPress() { press(UP); }
public void onUpRelease() { release(UP); }

Moving the player while the key is held down is also not terribly complicated. We will make our class extends ActiveObject, and then write it a run() method that loops endlessly, adding whatever the current vx and vy are to px and py, then calling that positionPlayer() method we just wrote, then pausing for a while.

public void run() {
    while(true) {
        px += .04 * vx;
        py += .04 * vy;
        
        positionPlayer();
        
        pause(20);
    }
}

When I add the velocity, I multiply it by .04 to make the speed more reasonable. Pausing just 20 milliseconds means the player moves roughly 50 times per second, which means that each second it moves 50*.04 = 2 cells.
Your browser doesn't do Java.
CollisionMaze.java

3. Collision Detection

The tricky part of smooth movement is how to detect when the player has collided with the walls. We can no longer simply check the relevant wall once when a key is hit; we need to figure out first when the player is close enough to be in danger of hitting a wall if it is there.

It turns out that collision detection requires two steps: first, we will detect when the player is trying to move through the middle of a wall; then, we will detect when the player has collided with the corner of a wall.

3.1. Detecting wall collisions

Suppose that the player were in a cell that had walls on all four sides. How can we tell if the player is close enough to a wall that we need to check for a collision?

Remember that we said before that the decimal part of px and py indicates where the player is within its cell of the maze. So, if the player's circle has a radius of .3 of a cell, and a wall is about .1 of a cell thick, then, any time px is less than .4, the player is touching the left side of the cell, and any time py is greater than |.6|, the player is touching the right side.

In order to simply detect collisions, we can calculate the distance from each of the four walls; if any of those distances is less than .4, and the corresponding wall is not open, then a collision has happened:

private void checkWalls() {
    int x = (int)px, y = (int)py;
    double cx = px - x, cy = py - y;
    double rcx = 1 - cx, rcy = 1 - cy;
    
    if(cx < WALL_D && !isOpen(x, y, LEFT)) {
        px += (WALL_D - cx);
    } else if(rcx < WALL_D && !isOpen(x, y, RIGHT)) {
        px -= (WALL_D - rcx);
    }
    
    if(cy < WALL_D && !isOpen(x, y, UP)) {
        py += (WALL_D - cy);
    } else if(rcy < WALL_D && !isOpen(x, y, DOWN)) {
        py -= (WALL_D - rcy);
    }
}

Here, cx and rcx are the distance from the left and right sides of whatever cell the player is in, and WALL_D is a constant equal to .4.

Once we have detected collision, the next step is to "fix" the collision by moving the player back out of the wall. That is what is going on inside of each of the if statements. It should be clear that, for example, if we hit a wall because cx is less than WALL_D, then, to get out of the wall, we want to move the player to the point where cx is just equal to WALL_D. That means that moving the player to the right by a distance of WALL_D - cx, by adding that much to px.

3.2. Detecting corner collisions

Detecting corner collisions is somewhat simpler because all corners are solid; every corner is part of at least one wall. Thus, we need no check any walls to see if a corner should block the player. However, corner collision detection is also more complicated in that they are circular. So to figure out if the player has hit a corner, I need to find the distance between the player and the corner, using the Pythagorean Theorem, and check if it is less than .4 (the minimum distance we determined for the player to be away from the wall).

So, suppose, for example, that the player is at (3.2, 4.3). That means that it is in the cell (3, 4), .2 in from the left wall and .3 in from the top wall. The distance from the top left corner is then √(.22 + .32) = .36. This means that a collision happens; the player is closer than .4 to the corner.

Once I know that a collision happened, the next step is to "fix" it. We will move the player stright out from the corner until its distance is .4. The current distance from the center is .36, and we want it to be .4, so we have to move the player out another .04, or 1/9 of its current distance. It should be obvious how to do that:

3.2 + (1/9)(.2) = 3.222
4.3 + (1/9)(.3) = 4.333

To write code to do this, I recognize that I first divided WALL_D / d to find out that the desired distance is 1.111 times what it is currently, then subtracted 1 to find that I want to add .111 of the current offset, then multiplied the current offset from the corner by that and added it to the player's position.

The other corners can be handled in the same way, simply taking into account which direction each would push the player in:

private void checkCorners() {
    int x = (int)px, y = (int)py;
    double cx = px - x, cy = py - y;
    double rcx = 1 - cx, rcy = 1 - cy;
    double d;
    
    if((d = Math.sqrt(cx * cx + cy * cy)) < WALL_D) {
        // Hit top left corner
        px += (WALL_D / d - 1) * cx;
        py += (WALL_D / d - 1) * cy;
    } else if((d = Math.sqrt(rcx * rcx + cy * cy)) < WALL_D) {
        // Hit top right corner
        px -= (WALL_D / d - 1) * rcx;
        py += (WALL_D / d - 1) * cy;
    } else if((d = Math.sqrt(cx * cx + rcy * rcy)) < WALL_D) {
        // Hit bottom left corner
        px += (WALL_D / d - 1) * cx;
        py -= (WALL_D / d - 1) * rcy;
    } else if((d = Math.sqrt(rcx * rcx + rcy * rcy)) < WALL_D) {
        // Hit top left corner
        px -= (WALL_D / d - 1) * rcx;
        py -= (WALL_D / d - 1) * rcy;
    }
}

Now that we have written methods to detect and correct collisions with both walls and corners, we can add collision detection to our program by simply calling both of these methods after we have added the velocity to the player position, but before we call positionPlayer().
Your browser doesn't do Java.
CenterMaze.java

4. Centering the player

Our next step is to make the player appear always at the center of the screen, with the maze shifting around it as the player moves. This will bring us a lot closer to being a "first person" game. The problem is that in order to accomplish this, the entire maze will need to be redrawn every frame, because all the walls are constantly in motion.

4.1. Defining a class to represent a Corner

In order to draw a wall now, I will need to somehow convert the positions of its corners in the maze into positions on the screen. In fact, there are three sets of coordinates that I need to work with for each corner:So, for example, suppose that the player is at (3.2, 4.3) and we want to draw the corner at world position (6, 2). That corner is 2.8 cells to the right of the player (6 - 3.2 = 2.8), and 2.3 cells up (2 - 4.3 = -2.3), so its transformed position is (2.8, -2.3). If the screen is centered at (100, 100) and we are drawing walls to be 20 pixels long, then the screen position of that corner is (100 + 2.8 * 20, 100 - 2.3 * 20) = (156, 54).

Sine every corner now needs six numbers in order to describe its position in multiple different coordinate systems, it makes sense to create a Corner class that will wrap up all this information into just one object. This class can also handle the calculations for deriving the transformed and screen coordinates from the world coordinates. I will define this class inside the Maze class so that it will have access to useful instance variables like px and py, and constants like WALL_LENGTH:

// Inside my Maze class:
private class Corner {
    private double wx, wy, tx, ty, sx, sy;
    
    public Corner(double wx, double wy) {
        this.wx = wx;
        this.wy = wy;
        
        tx = wx - px;
        ty = wy - py;
        
        sx = WALL_LENGTH * tx;
        sy = WALL_LENGTH * ty;
    }
}

You might notice that I didn't add ORIGIN_X and ORIGIN_Y to the screen coordinates. This will mean that (0, 0) screen coordinates for a Corner is the middle of the screen, where the player is. As the game gets more complicated, it will be useful not to have to think about ORIGIN_X ad ORIGIN_Y every time we look at screen coordinates. The only place we will need to know where the screen origin is is in our drawLine() method, which we can update to take two Corners as parameters:

private void drawLine(Corner start, Corner end) {
    Line line = new Line(ORIGIN_X + start.sx, ORIGIN_Y + start.sy,
    ORIGIN_X + end.sx, ORIGIN_Y + end.sy, canvas);
    line.setStroke(STROKE);
}

4.2. Drawing using Corner

Now, all that I need to do to get the maze drawing centered on the player is to take the drawing code that we created to draw the maze at the start, and pull it out into its own method so that we can call it every frame:

private void drawMaze() {
    canvas.clear();
    player.addToCanvas(canvas);
    
    for(int x = 0; x < hwalls.length; x++) {
        for(int y = 0; y < hwalls[x].length; y++) {
            if(!hwalls[x][y]) {
                drawLine(new Corner(x, y), new Corner(x + 1, y));
            }
        }
    }
    
    for(int x = 0; x < vwalls.length; x++) {
        for(int y = 0; y < vwalls[x].length; y++) {
            if(!vwalls[x][y]) {
                drawLine(new Corner(x, y), new Corner(x, y + 1));
            }
        }
    }
}

I have also, of course, changed how I call drawLine(). Formerly, I would have passed along the four coordinates as numbers:

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

Now, I wrap up those coordinates in Corner objects and pass them along instead:

drawLine(new Corner(x, y), new Corner(x + 1, y));

Notice that I clear the canvas at the start of the drawMaze() method. Otherwise, we would keep piling up new walls on top of the old ones, and end up with a big mess.

The last step is to rewrite my run() method so that it calls drawMaze() after every time that it moves the player. We will also tell the canvas to repaint only when we are done drawing the maze, so that the canvas never gets drawn with only half the walls in place.
Your browser doesn't do Java.
TurnMaze.java

5. Turning the player

Using the arrow keys to move in the four directions makes sense in this top down view, but once we make it "first person" we will want the controls to work differently: we will want the left and right arrow keys to turn to the left and right, and the up and down arrow keys to move forward and backwards along whatever direction the player is facing.

Clearly, in order to do this we have to introduce another instance variable representing the angle the player is facing in. We will also replace vx and vy with an angularVelocity and a forward speed:

public void onUpPress() { speed++; }
public void onLeftPress() { angularVelocity++; }
public void onDownPress() { speed--; }
public void onRightPress() { angularVelocity--; }
public void onUpRelease() { speed--; }
public void onLeftRelease() { angularVelocity--; }
public void onDownRelease() { speed++; }
public void onRightRelease() { angularVelocity++; }

Now, our big problem is to figure out how to convert a speed and angle into a vx and a vy. (If you've done any trigonometry, you probably can guess where we're going with this.) Think about what will happen to the player's vx as the player starts out facing up, and turns to the left:So, to summarize, the player's vx goes 0 -> -1 -> 0 -> 1 as the player turns. If we think through the same process for vy, we will find that it goes -1 -> 0 -> 1 -> 0.

There are two mathematical functions that are specially designed for converting an angle into an x or y distance. These functions are called sine and cosine. In the graph below, the red curve shows the value of Math.sin(angle) and the blue curve shows the value of Math.cos(angle) as angle goes from 0 to 2π:

Any time you want to map an angle to coordinates, you should look at the pattern the coordinates take as the angle changes, and try to map it to one of these two curves. The values we found for vx were the negative of what we see for the sine curve; the values for vy were the negative of the cosine curve. So, we can say:

double vx = -speed * Math.sin(angle);
double vy = -speed * Math.cos(angle);

Your browser doesn't do Java.
RotateMaze.java

6. Rotating the maze around the player

In order to show the maze from the point of view of the player, we really need to rotate the maze around the player, so that up is always forward. This is shown in the applet to the right.

Getting this to work will just be a matter of changing how Corner calculates the "transformed" coordinates. A corner that is directly in front of the player at a distance of 2 spaces ought to have "transformed" coordinates of (0, -2). If the player is at (4, 5), this might mean that he is looking UP at a corner at (4, 3), or looking LEFT at a corner at (2, 5), or looking DOWN at a corner at (4, 7), or looking RIGHT at a corner at (6, 5).

For clarity, let's calls the x and y distance to a corner from the player dx and dy:

double dx = wx - px;
double dy = wy - py;

In the image above, the blue dot has just a dx and no dy; the green has just a dy and no dx. So, we can use these two dots to determine how dx and dy contribute to the transformed position of a corner.

We see that the blue dot's contribution to tx rotates in a pattern that looks like Math.cos(angle). In other words, since the blue dot is dx:

tx = dx * Math.cos(angle);

However, the green dot, dy, can also contribute to the tx, so we need to add that in as well:

tx = dx * Math.cos(angle) - dy * Math.sin(angle);

We can do the same thing for the ways that the two dots, dx and dy, contribute to the ty:

tx = dx * Math.sin(angle) + dy * Math.cos(angle);

These two equations allow us to simply update how Corner calculates tx and ty in order to cause the maze to rotate around the player:

public Corner(double wx, double wy) {
    this.wx = wx;
    this.wy = wy;
    
    double dx = wx - px;
    double dy = wy - py;
    
    tx = dx * Math.cos(angle) - dy * Math.sin(angle);
    ty = dx * Math.sin(angle) + dy * Math.cos(angle);
    
    sx = WALL_LENGTH * tx;
    sy = WALL_LENGTH * ty;
}

The important thing to read through and remember here is the process that we went through to figure out how to use sine and cosine to convert an angle into x and y distances. Notice how we first reasoned about how an object ought to appear to move as the player rotates, then extracted from the the pattern of what something in each direction contributes to the x and y as the angle rotates, then matched that pattern to one of the four "waves" sin(a), cos(a), |-sin(a)|, or |-cos(a)|.

7. Summary

In this section, we changed our maze game to display the player marker at the center of the screen, with the maze moving and rotating around it. In order to do this, we need to think about three different ways of representing the position of a corner: the world coordinates (which never change), the transformed coordinates (calculated to reflect the position of that corner relative to that player), and the screen coordinates (where the corner is actually drawn.

In the next section, we will make our maze draw itself in 3D. As it turns out, this is very easy to do: we will only have to change a few lines of code to have the screen position appear on a "floor" around the player in a three dimensional world.

back to Maze