# Maze: 3D

## 1. Introduction

So far, we have created a program that allows the player to navigate around a maze in a more-or-less "first person" way: the maze moves around the player, rather than the player moving around the maze. If we want the player to actually feel like they are "in" the maze, however, we need to do away with the little red circle representing the player, and instead show what the maze "looks like" from that perspective.
FloorMaze.java

## 2. Drawing in perspective

### 2.1. Projection So, here I am sitting in front of my computer, playing some sort of game. The computer wants to convince me that there is an ogre standing a few feet away, ready to stab me in the face with a spear. What should it draw on the screen to accomplish this?

It should be obvious that, in order for the illusion to be convincing, each part of the ogre ought to be drawn on the screen right at the point where a line drawn to my eye from that part of the imaginary ogre would go through the screen. So, for example, its foot appears near the bottom of the screen. If the screen were a window, I would have to draw a dot near the bottom of the window for that dot to appear over the ogre's foot. As the ogre moves closer to the screen, the line from its foot to my eye will intersect the screen closer to the bottom, while at the same time the line from its head to my eye will intersect closer to the top; hence, the ogre will appear to get larger, taking up more of the screen.

When perspective drawing was first discovered in Europe during the Renaissance, some painters actually tried to use this exact idea to figure out where to lay out the objects in a painting. They would set up a fixed eyepiece behind a glass window, and, while looking through the eyepiece at some scene through the window, would try to paint on the window in such a way that the paint covered the objects it was meant to depict. The eyepiece had to be fixed in place, because the whole point of perspective drawing is that if the point of view shifts, the objects in the picture shift as well.

How can we program a computer, then, to calculate where on the screen some imaginary object ought to be drawn? It should be clear that if we could just figure out how to take a point in the imaginary world and figure out where to draw it on the screen, that would be enough. Then, if we wanted to, for example, draw a line, we could do so by just "projecting" both end points onto the screen, and then drawing a line between them. Let's start with the problem of just trying to figure out the `sx`, the `x` position on the screen, of one of the corners of our maze. We know, for that corner, the distance `ty` that it is ahead of the player, which is another way of saying, how far into the screen it is. We also know the distance `tx` right or left of that.

The picture to the right shows an object positioned at (`tx`, `ty`) in the imaginary world, while the player, located at a fixed `DISTANCE` behind the screen, is suppose to be seeing that object at a position `sx` on the screen. Remember, we chose to make `sx` be measured from the center of the screen; this is why that turns out to be convenient.

It should be clear that the triangle defined by `tx` and `ty` is similar to the triangle defined by `sx` and `DISTANCE`. That is, although the triangles are different sizes, they are proportioned the same way. The ratio of `tx` to `ty` ought to be equal to the ratio of `sx` to `DISTANCE`. We can use this fact to get an equation for `sx`: The only thing we need to do before plugging this equation in as our new calculation for `sx` is to negate `ty`. Remember, before "in front of" the player was up on the screen - a negative `ty`. Now, we want `ty` to be positive for objects in front of the player, so that `sx` will be on the right side of the screen for objects to the right of the player and vice versa.
`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);        ty = -ty;    sx = tx * DISTANCE / ty;    sy = WALL_HEIGHT * DISTANCE / ty;}`
Notice that I calculated `sy` in exactly the same way as `sx`. The drawing we made for `sx` could be turned on its side and it would work for `sy` as well; the only difference is that instead of `tx` being the far side of the triangle, it would be some measure of how far up or down the corner is. Since all our corners are on the floor, I assumed them to be at a constant height.

### 2.2. Dealing with walls behind the player

If I were to run the game at this point, I would see a fairly convincing 3D maze laid out on the "floor" around me. Unfortunately, as I moved around, I would also start to see a maze of sorts forming on the "ceiling", and, worse, there would be some lines randomly jumping between the two.

The problem that I am having here is that our projection equation is quite happy to pick a point on the screen for a corner that is behind me. In that case, `ty` is negative, and hence, so is `sy`, because `WALL_HEIGHT` and `DISTANCE` are both positive constants.

Really, if a wall is behind the player, we don't want to draw it at all. We can make a temporary fix for this problem - although not a perfect one - by writing a new `drawWall()` method that will be called instead of `drawLine()`, and having it call `drawLine()` only if the two end points of the wall both have `sy` values greater than zero.
`private void drawWall(Corner start, Corner end) {    if(start.sy > 0 && end.sy > 0) {        drawLine(start.sx, start.sy, end.sx, end.sy);    }}`
The problem with this approach is that if either end of a wall is behind me, it will not be drawn. Thus, when I am just passing a wall, it may suddenly blink out of existence. We had to do it this way, because a point behind me projects to a point on the ceiling, and connecting that to a point on the floor would be senseless.

So, with some application of similar triangles, we have made the great leap from 2D to 3D. Surprisingly, this required us to change only a few lines of code. All the code dealing with the player's motion can happily live inside its 2D world; we need only change how that world is projected onto the screen.
ClippedMaze.java

## 3. Clipping walls to fit in the view

Obviously, the next problem that we need to solve is how to display the part of a line that is visible, even if that line eventually runs behind the player. The solution to this is to trim off whatever part of the line goes outside the view, so that we can guarantee that whatever is being drawn is entirely visible. The image above shows the player in a maze, with all parts of walls that are outside the view drawn in grey. Some walls are entirely in view, and some are entirely out of view; these walls are already correctly drawn with our current `drawWall()` method. What we need to do is to deal with the walls that are partly in view and partly out; for walls like that, we want to cut off the part that is out of view and then draw them as if they were fully in view.

### 3.1. Finding where a wall intersects the edge of the view

The first mathematical challenge we will face is how to figure out the exact point on a wall where it intersects the edge of the view. As you can see in the picture above, this is essentially a matter of finding the intersection between two lines: the edge of the view, shown as blue lines, and the wall itself.

It will be convenient here to work in the transformed coordinate system, with the player at the origin facing up, because in that coordinate system the edges of the view are lines through the origin whose slope is `edgeX` / `DISTANCE`. This means that we can represent that line with a very simple equation: We want to find a point that belongs to this equation, and also to whatever equation defines the wall.

To define what points are part of the wall, we will parameterize it. To understand what this means, imagine that you are standing at the `start` of the wall, and you are going to walk along it to the `end`, doing this in exactly one minute. While you are doing that, your (`x`, `y`) position is determined simply by the time. In other words, instead of having two variables, `x` and `y`, to describe where you are along the wall, it is enough to know just one variable, `t`. Reducing things down to one variable is of course very convenient for us, because we want to solve an equation to find the intersection point, and you can only solve for one variable at a time. So, given some `t`, how do I find the point on the wall that that corresponds to? Obviously, the position at `t = 0` is the start, and the position at `t = 1` is the end. In order to find a position in between, I can calculate the total distance that I have to go to get from the start to the end, and then multiply that by what fraction of that distance I have covered. So, for example, in the example above, traveling from the start to the end means adding 10 to the start x, and subtracting 5 from the start y. Therefore, if `t = .2`, meaning that I have gone 1/5 of the distance, then I have only added 2 to the `x`, and -1 to the y, and I am at (7 + 2, 13 - 1) = (9, 12).

In general, I can find the `x` and `y` at a given `t` by doing this:
`double dx = end.tx - start.tx;double dy = end.ty - start.ty;double x = start.tx + t * dx;double y = start.ty + t * dy;`
Now, we don't actually want to calculate the `x` and `y` for some `t`; we instead want to solve for the `t` value where `y = (edgeX / DISTANCE) * x`. It is simple to set up and solve this equation: With a little bit of algebra, you can find that we can calculate `t` as:
`double t = (sx * start.ty - DISTANCE * start.tx) / (DISTANCE * dx - sx * dy);`
The convenient thing about this is that we can use it to calculate both the (`tx`, `ty`) and the (`wx`, `wy`) of the intersection point, since `t`, the fraction of the way along the line, has the same meaning in both coordinate systems. I added in another constructor for `Corner` that does this calculation and creates a new `Corner` representing the point on any given line that is at a particular screen `x`:
`public Corner(Corner start, Corner end, double sx) {    double dx = end.tx - start.tx;    double dy = end.ty - start.ty;    double t = (sx * start.ty - DISTANCE * start.tx) / (DISTANCE * dx - sx * dy);        tx = start.tx + t * dx;    ty = start.ty + t * dy;        wx = (1 - t) * start.wx + t * end.wx;    wy = (1 - t) * start.wy + t * end.wy;        this.sx = tx * DISTANCE / ty;    this.sy = WALL_HEIGHT * DISTANCE / ty;}`

### 3.2. Figuring out which walls to clip  Now that we have figured out the math to actually do the clipping, it is time to have `drawWall()` identify which ends of which walls need to be clipped. This would seem to be fairly straightforward: check if the `start` of the wall is out of view, and if it is, clip it to the edge; then, do the same for the `end` of the wall. The problem is, how do we know which side of the view the wall goes off of?

There are many ways to solve this problem, but the most widely accepted one is this: we will set up all our walls such that they go clockwise around the player, and then we can safely assume that the `start` of a wall can only go off the left edge of the view, and the `end` of a wall can only go off the right edge. Here, when I say that a wall is "clockwise" I mean that if the player were to spin around clockwise in place, with his finger pointed straight ahead of him, he would point to the `start` of the wall before he got to the `end`. You can see in the second picture above that I have made all the walls clockwise (by simply swapping `start` and `end` for any wall that was not clockwise), and this has indeed made it so that only the starts of walls are off the left, and only the ends are off the right.

How can I determine whether a wall is clockwise or not? You may remember that there is a mathematical operation called a cross product which, given two points (x1, y1) and (x2, y2), will find the area of the parallelogram which has as corners the origin and those two points. The area is actually uninteresting to us here, but what is interesting is that that area is either positive or negative depending on whether the second point is clockwise or counterclockwise from the first. The cross product is also very easy to calculate: We can use the cross product, then, to write a method to answer the question of "is this wall clockwise:"
`private boolean isWallClockwise(Corner left, Corner right) {    return left.tx * right.ty - left.ty * right.tx < 0;}`
The `drawWall()` method, then, will swap the two ends of the wall if it is not clockwise, then will trim the start to the left edge if necessary, and trim the end to the right if necessary:
`private void drawWall(Corner start, Corner end) {    if(start.sy < 0 && end.sy < 0) {        // Wall is entirely behind me - nothing to draw        return;    } else if(!isWallClockwise(start, end)) {        // Make sure that start ought to be to the left of end on the screen        Corner tmp = start;        start = end;        end = tmp;    }        if(start.sy < 0 || start.sx < -ORIGIN_X) {        // Start of wall is behind me or too far left to see; replace start        start = new Corner(start, end, -ORIGIN_X);    }        if(end.sy < 0 || end.sx > ORIGIN_X) {        // End of wall is behind me or too far right to see; replace end        end = new Corner(start, end, ORIGIN_X);    }        if(start.sy > 0 && end.sy > 0 && start.sx < end.sx) {        drawLine(start.sx, start.sy, end.sx, end.sy);    }`
With these changes, the floor maze draws correctly all the time. Now, we can start to think about extending those lines on the floor upwards to turn them into walls.
GlassMaze.java

## 4. Drawing walls

The first thing to notice, when we start thinking about drawing walls, is that the line defining the top of the wall is actually just a mirror image of the line we already have along the floor. So, actually, it is amazingly easy to draw these lines; we'll just add another call to `drawLine()` in `drawWall()` that draws the same line, but making both `sy` values negative.

If we just do this, though, what we end up with is two copies of the maze, one on the ceiling and one on the floor, with no clear impression that they actually connect. The problem is that for each wall, we have drawn only the top and bottom edges; we need to draw the right and left edges as well.

Each edge of a wall is simply a straight line up and down at one of our `Corner`s of the maze. We even know, already, where on the screen it wants to be drawn; it should go from its `sy` to -`sy`, for the same reason that making the `sy` values for a wall negative puts it on the ceiling. All that we need to do, then, is to add an extra loop in `drawMaze()` that draws all the corners:
`for(int x = 0; x < vwalls.length; x++) {    for(int y = 0; y < hwalls.length; y++) {        drawCorner(new Corner(x, y));    }}`
Like `drawWall()`, the `drawCorner()` method will have to check that the corner is in view. Fortunately, it is much simpler in this case, because we have only one `Corner` to deal with, and it is either in view or not:
`private void drawCorner(Corner corner) {    if(corner.sy > 0) {        drawLine(corner.sx, corner.sy, corner.sx, -corner.sy);    }}`
Since all the information needed to draw walls was already in our `Corner` objects, it was really very easy to make the maze have walls instead of just floor lines!
OpaqueMaze.java

## 5. Opaque walls

Now comes the more conceptually difficult part of this project. So far, the maze looks like all the walls are made of glass, because all the walls are visible all the time. We would really like the walls to be opaque. But if we do that, it will no longer work to always draw all the walls; we will have to somehow only draw those walls that can be seen.

So, for example, if I were in a cell of the maze that was completely surrounded by walls, all that I should see is those four walls. If one of the walls is open, I would be able to see the cell beyond that opening, but only as much as appears through the gap. In other words, the view through an open wall ought to be clipped to the size of the opening.

In the image above, you can see this idea at work. The cell the player is in is drawn first, which really means that two little ends of walls - all that fits within the view - are drawn. Then, I draw everything seen through the top wall of that cell, which is open. In drawing that part of the maze, the edges that I clip to are now defined by the corners of the open wall. It turns out that more cells are visible beyond that one, but again, in looking into them I clip what is visible to the size of the opening that I am looking through. In the end, it turns out that only a few pieces of wall - those drawn in black - are actually visible to the player.

Our drawing process, now, is going to introduce a new method: `drawCell()`, which draws just the four walls of a single cell. We will also introduce a new method to draw what is visible through an opening, by calculating the new edges of the view and then calling `drawCell()`. The program flow is going to look like this:
1. `drawCell()` loops through all four directions for a given cell.
1. If there is a wall in that direction, `drawCell()` calls `drawWall()`
2. If there is an opening, `drawCell()` calls `drawOpening()`
1. `drawOpening()` calculates the edges of the view visible through the opening
2. `drawOpening()` calls `drawCell()` for the cell visible through the opening
Let's look first at what the `drawCell()` method ought to do. It will loop through the four directions, and for each direction, check if there ought to be a wall or an opening there. It will also draw the four corners as it goes:
`private void drawCell(int x, int y, double left, double right) {    for(int direction = 0; direction < 4; direction++) {        Corner leftCorner = getLeftCorner(x, y, direction);        Corner rightCorner = getRightCorner(x, y, direction);                if(isOpen(x, y, direction)) {            drawOpening(leftCorner, rightCorner, left, right, x, y, direction);        } else {            drawWall(leftCorner, rightCorner, left, right);        }                drawCorner(leftCorner, left, right);    }}`
Here, the parameters `left` and `right` are the screen coordinates of the left and right edge of the view. You will notice that I pass along these values to `drawWall()` and `drawCorner()`; this allows them to clip their drawing to the current view. So, for example, `drawCorner()` simply has a somewhat more complex condition in its `if`:
`private void drawCorner(Corner corner, double left, double right) {    if(corner.sy > 0 && corner.sx >= left && corner.sx <= right) {        drawLine(corner.sx, corner.sy, corner.sx, -corner.sy);    }}`
The methods `getLeftCorner()` and `getRightCorner()` that you see above answer the question, "If I am standing at (`x`, `y`) looking in `direction`, what corner is to my left (or right)?" They work by simply starting from the middle of the cell, and moving .5 toward `direction`, and then |.5| toward `left(direction)` or `right(direction)`:
`private Corner getRightCorner(int x, int y, int direction) {    return new Corner(x + .5 + .5 * (dx(direction) + dx(right(direction))),                      y + .5 + .5 * (dy(direction) + dy(right(direction))));}`
One convenient result of how we are now drawing walls is that every visible wall should always be clockwise already, since we are looking at the corners in clockwise order around the cell. So, if `drawWalll()` encounters an edge that is not clockwise, it can decide immediately not to draw it, without needing to try to clip it first.

The `drawOpening()` method, now, is all that we have left to do. Like `drawWall()`, it can immediately reject any opening that is entirely behind the player, or that is not clockwise. This second constraint is particularly important, because it prevents our drawing from getting into an infinite loop: when I am drawing the cell seen through an open wall, the program won't try to draw what is seen looking back from that cell into the cell where I am, because if the wall looking out from my cell went clockwise around the player, the one looking back goes counterclockwise.

After checking whether the opening is visible at all, `drawOpening()` should narrow down the left and right of the view if either edge of the opening is in view. Then, it should call `drawCell()` with this narrowed view only if the view has not yet been completely closed off:
`private void drawOpening(Corner leftCorner, Corner rightCorner, double left, double right, int x, int y, int direction) {    if((leftCorner.sy < 0 && rightCorner.sy < 0) || !isWallClockwise(leftCorner, rightCorner)) return;        // Figure out the left and right to use in drawing this opening.    if(leftCorner.sy > 0 && leftCorner.sx > left) left = leftCorner.sx;    if(rightCorner.sy > 0 && rightCorner.sx < right) right = rightCorner.sx;        if(left < right) {        drawCell(x + dx(direction), y + dy(direction), left, right);    }}`
There is one last nicety that we can add in at this point. It is really not necessary to draw vertical lines at all the corners. If there is a long, straight wall made up of edges of several adjacent cells, there need not be lines in the middle of it. We can add a condition in `drawCell()` that draws a corner only if the wall to one side of it is open and the other is closed.
SolidMaze.java

## 6. Solid walls

There is one last thing that I would like to change. The walls in the maze still seem somewhat unreal, because they are infinitely thin. Giving them some width would make it feel much more realistic.

It would seem to be very simple to implement this: we simply need to inset each corner slightly into the cell. Since each cell calls `getRightCorner()` to retrieve its corners, I can simply have that method return a corner that is, say, .05 in from both edges of the cell:
`private Corner getRightCorner(int x, int y, int direction) {    return new Corner(x + .5 + .5 * (1 - WALL_WIDTH) * (dx(direction) + dx(right(direction))),                      y + .5 + .5 * (1 - WALL_WIDTH) * (dy(direction) + dy(right(direction))));}`
This turns out to work very well; the walls definitely start to look like they have a width. However, there are several problems that I still notice:
• There is now a blank gap between cells, since the walls no longer stretch from cell edge to cell edge.
• As I walk through that gap, occasionally the entire view goes white
• Sometimes, one of the vertical lines for a corner does not draw where it should.
The third problem is the easiest to fix. When drawing a corner, we checked to make sure that |corner.sx >= left && corner.sy <= right|. The problem is that, because of floating-point round-off errors, a corner at the very edge of the view - like, for example, the corner in a cell that is just to the right or the left of the opening into that cell - might actually have its screen posiiton calculated to be very slightly outside the view. We can fix this by allowing a little extra leeway; say, drawing any corner that is within .1 pixels of the edge:
`private void drawCorner(Corner corner, double left, double right) {    if(corner.sy > 0 && corner.sx >= left - .1 && corner.sx <= right + .1) {        drawLine(corner.sx, corner.sy, corner.sx, -corner.sy);    }}`
The second problem will require that we change `drawOpening()`. Previously, `drawOpening()` didn't actually draw anything itself, since its job was to draw a wall that isn't there. But now, there is something visible in the opening: the edges of the two walls on either side. We need to draw these short little walls so that walls will still appear to connect between cells.

We can use `getRightCorner()` and `getLeftCorner()` to get the ends of these little walls, except that now, we want the corners when looking back from the cell this opening leads into. Once we find where those edges are, we also might need to narrow the view somewhat to fit them in. In other words, the "window" through which I am looking into the next cell is actually defined by the far corners of the wall, not the near ones.
`private void drawOpening(Corner leftCorner, Corner rightCorner, double left, double right, int x, int y, int direction) {    // Figure out the left and right to use in drawing this opening.    if(leftCorner.sy > 0 && leftCorner.sx > left) left = leftCorner.sx;    if(rightCorner.sy > 0 && rightCorner.sx < right) right = rightCorner.sx;        int nx = x + dx(direction);    int ny = y + dy(direction);        // Draw short walls showing the thickness of the wall    Corner leftEdge = getRightCorner(nx, ny, reverse(direction));    Corner rightEdge = getLeftCorner(nx, ny, reverse(direction));        drawWall(leftCorner, leftEdge, left, right);    drawWall(rightEdge, rightCorner, left, right);        if(leftEdge.sy > 0 && leftEdge.sx > left) left = leftEdge.sx;    if(rightEdge.sy > 0 && rightEdge.sx < right) right = rightEdge.sx;        if(isWallClockwise(leftEdge, rightEdge) && left + 1 < right && (leftEdge.sy > 0 || rightEdge.sy > 0)) {        drawCell(nx, ny, left, right);    }}`
Once I have updated `drawOpening()` like this, the other problem I was having, that the view goes white as I step between cells, suddenly fixes itself. What happened? It turns out that the problem that I was having had to do with the fact that I had been using the corners on the near side of the wall to figure out if I could see through the view. When I'm standing within the opening, this opening is actually behind me, and hence counterclockwise, so `drawOpening()` had been deciding not to draw anything.

## 7. Summary

We now have a very convincing, 3D version of the maze program. In creating it, you have learned several techniques that are used in nearly all modern 3D games: the equations for projecting points, the concept of "clipping" objects that go outside the view, and the idea of narrowing down the view to fit only what is visible through an opening into another area. Of course, modern games aren't restricted to vertical walls and flat floors, and so the clipping shape needs to be a more complex polygon, instead of just a left and right edge; however, the concept is very similar.

back to Maze