## Sunday, August 28, 2016

### PICO-8 cast.p8 Explanation

Today I’ll to try to explain how the cast.p8 demo works. The cart uses a kind of “raycasting” to render a first-person view of a simple level. Googling raycasting will give you a heap of fantastic tutorials, but Zep’s implementation is pretty different from what you tend to see.

If you’re gonna read the cast.p8 code concurrently with this post, keep in mind some code won’t match up exactly with Zep’s. I’ll explain the key differences later though.

## The Level

So we’ve got a player who moves around a 3D level, which is just a grid of tiles at different heights. It’s represented by a grid of sprites in the map. The height of the tile is given by the value of the sprite. `MGET(X,Y)` will give us the height of tile at x,y.

## The Player

`PL` is our player object which stores an x,y,z position, and the direction they’re facing `PL.D` as an angle. Player input is read during the `_UPDATE` function.

``````PL={}
PL.X = 12
PL.Y = 12
PL.Z = 12
PL.D = 0.25
``````

## Generating the Rays

In raycasting, we send out a ray from the player for each x-coordinate on the screen. We follow the path of the ray until it hits a wall. The distance that the ray travelled gives the height of the wall, which we draw as a vertical line.

At the start of `DRAW_3D()` we initialize two unit vectors (`V.X0`,`V.Y0`) and (`V.X1`,`V.Y1`) which are angled slightly left and slightly right of the player direction.

``````V.X0 = COS(PL.D+0.1)
V.Y0 = SIN(PL.D+0.1)
V.X1 = COS(PL.D-0.1)
V.Y1 = SIN(PL.D-0.1)
``````

These vectors represent the two outer sides of the viewing triangle. 0.1 is a magic number which determines the field of view. As we go from the left side of the screen to the right, we interpolate between these two vectors to find the corresponding ray vector (`VX`,`VY`):

``````FOR SX=0,127 DO
...
LOCAL T=SX/127
VX = V.X0 * (1-T) + V.X1 * T
VY = V.Y0 * (1-T) + V.Y1 * T
``````

## Edge Finding

Now that we’ve generated rays for each x-coordinate, we have to be able to find which tiles they pass through.

A simple way could be to test points separated by a constant distance along the ray. However this results in accidently skipping over some tiles that should have been checked. We could decrease the distance we move along the ray, but this becomes too inefficient.

Instead we’ll be clever and only check where the ray intersects with edges of tiles!

Here’s how we’ll do it: At any point on the ray, we want to jump to either the next column or the next row. We chose the one that is closest by distance along the ray’s path. We represent the distance to the next column and the next row (along the ray) as `DIST_X` and `DIST_Y`.

Let’s start by assuming that the ray originates from an integer position on the grid. What should `DIST_X` and `DIST_Y` be initialised to? I’ll refer to these specific initial values as `STEP_X` and `STEP_Y`.

For `STEP_X`, we need to move along one tile in the x-direction by moving `STEP_X` units in the diagonal. So let’s use a right-angle triangle of width 1 and hypotenuse `STEP_X`.

Since this is a similar triangle to our ray vector, we can find `STEP_X` using the ratio STEP_X / 1 = 1 / abs(VX). Doing the same for `STEP_Y`, we end up with:

``````SKIP_X = 1/ABS(VX)
SKIP_Y = 1/ABS(VY)
``````

Now what do we do when the ray starts in another position? We need to scale our initial values based on how close the ray starts to the edge it will next hit. Conveniently the scale factor we need is this exact distance, only in the horizontal or vertical direction (e.g. if the ray is 0.8 units away from the right edge, then `SKIP_X` should be scaled by 0.8). If the ray is going in the positive x-direction, `X%1` will give the horizontal distance from the ray to the closest left edge, so `1-(X%1)` will give the distance to the closest right edge. In the negative direction, `X%1` is what we want.

``````IF (SGN(VX) > 0) THEN
DIST_X = 1-(X%1) ELSE
DIST_X =   (X%1) END
IF (SGN(VY) > 0) THEN
DIST_Y = 1-(Y%1) ELSE
DIST_Y =   (Y%1) END

DIST_X = DIST_X * SKIP_X
DIST_Y = DIST_Y * SKIP_Y
``````

We can finally start moving down the ray! We go into a while loop, and on each iteration we choose between the next column or row. If `DIST_X < DIST_Y` then go to the next column, otherwise go to the next row.

If `DIST_X < DIST_Y`, we travel along the ray by distance `DIST_X`, so we need to decrease `DIST_Y` by `DIST_X`, and reset `DIST_X` to the initial value `SKIP_X`. We do the same for the vertical case:

``````SKIP=TRUE
...
WHILE (SKIP) DO
IF (DIST_X < DIST_Y) THEN
...
DIST_Y = DIST_Y - DIST_X
DIST_X = SKIP_X
ELSE
...
DIST_X = DIST_X - DIST_Y
DIST_Y = SKIP_Y
END
END
``````

Rad! Now we also need to keep track of where we are along the ray. Before the loop let’s initialise some variables that we’ll use: `TDIST=0` to keep track of the total distance travelled along the ray, as well as `IX=FLR(PL.X)` and `IY=FLR(PL.Y)` to keep track of which cell we’re in. It also turns out to be useful to know if we’re checking a row or a column, so we’ll mark that with `LAST_DIR`.

Within the loop, we increase `TDIST` by the distance we travel, and increment `IX` and `IY` according to the direction the ray is going:

``````WHILE (SKIP) DO
IF (DIST_X < DIST_Y) THEN
...
TDIST = TDIST + DIST_X
IX=IX+SGN(VX)  --SGN(VX) RETURNS -1 OR 1 DEPENDING ON THE SIGN OF VX
LAST_DIR = 0
ELSE
...
TDIST = TDIST + DIST_Y
IY=IY+SGN(VY)
LAST_DIR = 1
END
END
``````

Our program now goes along every ray, correctly finding every grid intersection. Great, now it’s time to use this stuff to draw some lines!

## A Classic Raycaster

Before we finish off the code it’ll be useful to look at a simple raycaster, which uses 2D levels like in Wolfenstein 3D. What does the rendering code look like in this case?

Once a ray hits a wall, we want to find the position of the foot of the wall on the screen. We can do this with `SH/2 + K/TDIST`, where `SH` is the screen height, and `K` is some constant. Intuitively, as `TDIST` gets bigger (further away), the foot of the wall shrinks toward the horizon. Similarly the position of the top of the wall is `SH/2 - K/TDIST`.

Since close walls obscure further walls, we only need to draw one line per ray. In PICO-8 the end result could look something like this:

``````WHILE SKIP DO
...
LOCAL COL = MGET(IX,IY)
IF COL > 0 THEN
LOCAL H=50/TDIST
LINE(SX,64-H,SX,64+H)
SKIP = FALSE
END
END
``````

## Drawing the Tiles and the Walls

Now what do we do with our 3D level? Imagine a staircase that ascends in front of the player, we’ll need to draw all the different floor heights and numerous walls, spooky!

Let’s start by working out how to draw the ground of a tile. Note that the ground is just the space between the edges of the tile. We can think of these edges as the feet of some imaginary walls surrounding the tile. This is great since we know about walls from the 2D raytracer! So when a ray passes through a tile, we find where on the screen the feet of walls would be for the two points that the ray intersects. Then we just draw a vertical line between them!

Now that we can draw the tops of tiles, we’re going to use them to draw walls too (our 2D method won’t help us much anymore). Walls are just the space separating the edges of two tiles, so we just draw a vertical line between points calculated for the two tiles' edges.

So now we just need to implement a way to find the height of edges for different tiles.

To do this we just make a small change to the code from earlier: we scale render height `K` based on the tile’s height relative to the player. Tiles higher above the player should be scaled more. Tiles at the same height as the player’s head should be drawn at the horizon. So hopefully you can see that `TILE_HEIGHT-PLAYER_HEIGHT` is what we want:

``````TILEH = MGET(IX,IY)
Z = PL.Z+5
EDGE_Y = SH/2 - K*(TILEH-Z)/TDIST
``````

Notice that we use `PL.Z+5` for the ray height, which simulates our character having a torso.

## Putting it All Together

As we travel down a ray, we’ll draw the floor and walls of every tile we see, gradually filling the column of pixels from bottom to top. We’ll keep track of how far we’ve draw with `SY`, which is initialised to 127.

We should try to draw the ground for every tile on the ray, but only where we haven’t drawn on the screen yet (above `SY`). Similarly we’ll only draw walls when the ray moves to a higher tile, and only draw the section that is visible.

Let’s imagine how this could work out. For the first edge a ray finds, we’ll want to draw some ground from the bottom of the screen (`SY=127`) up to that edge. If you think about it this is the ground of the tile that the ray started in, not the tile that `IX` and `IY` point to currently! We still need the current tile though: if it happens that the previous is lower than the current, then we need to draw a wall between the edges of the two tiles.

Extrapolating this out, every iteration we need the position of two edges (`EDGE1` and `EDGE2`), one on the previous tile and the other on the current. We'll use these to draw floor from `SY` to `EDGE1`, and a wall from `EDGE1` to `EDGE2`. Hence we need to keep track of the height of the previous and current tile. We don’t need the previous `TDIST`, since both edges are located `TDIST` along the ray.

We’ll keep track of the previous tile with `COL0` and the current tile with `COL`, updating them on every iteration with:

``````COL0=COL
COL=MGET(IX,IY)
``````

For this to work on the first iteration we’ll need to initialise `COL` to `MGET(IX,IY)` before the loop begins.

Now let's use these two values to find the screen position of the two edges. Remember that the first edge `EDGE1` is associated with the previous tile `COL0`, and the second `EDGE2` is associated with the current tile `COL`, but both are `TDIST` along the ray.

``````LOCAL K=12.8
LOCAL Z=PL.Z + 5
EDGE1 = 64 - K*(COL0-Z)/TDIST
EDGE2 = 64 - K*(COL-Z)/TDIST
``````

We’re almost done! The last thing to take care of is making sure to break out of the loop. All we need to do is stop once we reach the outer walls, which have a special height of 15:

``````IF (COL==15) SKIP=FALSE
``````

## Our Baby is Ready

We can finally finish the `WHILE SKIP DO` loop! Here it is as a big chunk for you to mull over:

``````WHILE (SKIP) DO
IF (DIST_X < DIST_Y) THEN
...
ELSE
...
END

--PREV AND CURRENT TILE PROPERTIES
COL0=COL
COL=MGET(IX,IY)

--RAY HIT AN OUTER WALL
IF (COL==15) SKIP=FALSE

-- FIND SCREEN POSITIONS OF EDGES
LOCAL K=12.8
LOCAL Z=PL.Z + 5
EDGE1 = 64 - K*(COL0-Z)/TDIST
EDGE2 = 64 - K*(COL-Z)/TDIST

--DRAW FLOOR FROM SY TO EDGE1 (IF EDGE1 IS ABOVE SY)
IF EDGE1 < SY THEN
COLOR(11)
LINE(SX,SY,SX,EDGE1)
SY = EDGE1
END

--IF CURRENT EDGE IS HIGHER THAN THE PREVIOUS
--DRAW WALL FROM SY TO EDGE2
IF COL > COL0 THEN
IF EDGE2 < SY THEN
COLOR(7)
LINE(SX,SY,SX,EDGE2)
SY=EDGE2
END
END
END
``````

If we implement `_DRAW()` then we can give this baby a spin:

``````FUNCTION _DRAW()
RECTFILL(0,0,127,127,12) --THE BIG BLUE SKY
DRAW_3D()
END
``````

Here’s what it looks like!

Beautiful. Let’s add some final finishing touches.

First we’ll draw walls facing north or south as white (7) and walls facing east or west as gray (6). Remember `LAST_DIR` from before? (0 if edge is on east/west side, 1 if north/south side.) Let’s use that guy:

``````COLOR(6 + LAST_DIR) --TRICKY!
LINE(SX,SY,SX,EDGE2)
``````

Next we’ll draw the lowest tiles as dark green (3) instead of green (11):

``````COLOR(11)
IF (COL0 == 0) COLOR(3)
LINE(SX,SY,SX,EDGE1)
``````

Lastly, we need to put in a little something to stop a weird glitch from happening. If the player is super close to an edge then `EDGE1` just blows up since `TDIST` is so small, giving an unpleasant visual effect. We can fix this by wrapping the drawing block from the start of this section with `IF TDIST > 0.1 THEN ...`.

That’s it, we’re done! If you just wanted to learn how make something like cast.p8, then you’re good to stop reading now! However if you want to fully understand Zep’s code then you’ll need to read one last section.

## Zepludian Geometry

There is one key detail in Zep’s code that I conveniently haven’t explained: Zep chose to represent player and tile height very unconventionally. Rather than height being 0 for the floor and increasing by one for each tile height (as we’ve assumed in this tutorial), tile heights actually start at 16 and decrease by 0.2 for each tile. In other words, if you expected heights to be stored as `Z` they are actually stored as `16-0.2*Z`.

The Zepludian heights of tiles are represented by `CELZ=16-COL*0.2` and `CELZ0`, which are used in place of `COL` and `COL0`. The main effect of this swap is that signs and comparisons on these values are often reversed to compensate. For example `EDGE1 = 64 - K*(COL0-Z)/TDIST` becomes `SY1 = 64 + K*(CELZ0-Z)/TDIST`, and `IF COL > COL0` becomes `IF (CELZ < CELZ0)`. Additionally Zep’s `K` value is 5 times bigger (from 12.8 to 64) since the heights are now 0.2 units apart.

Lastly Zep expanded the calculation `SY1 = 64 + 64*(CELZ0-Z)/TDIST` across multiple lines, which might confuse you at first:

``````SY1 = CELZ0-Z
SY1 = (SY1 * 64)/TDIST
SY1 = SY1 + 64
``````

## Bye!

With that explained, I think we’ve covered everything! Hope you enjoyed this read. Feel free to contact me if you have any suggestions or corrections.