in which many rays are cast

The Lisp Game Jam is a semiannual tradition I enjoy participating in. This time around I created Spilljackers, a 3D cyberspace heist game with my friend Emma Bukacek. Rather than use Fennel with the LÖVE framework (my usual choice) we went back to TIC-80 which we had used previously on our last game collaboration.

There's a lot to say about the style and feel of the game; Emma's punchy writing and catchy tunes brought so much to the table, but for this post I want to focus on the technical aspects. This was the first time I tried writing a 3D game. Instead of doing "proper 3D" which requires a lot of matrix math. I took a much simpler approach and built it using raycasting which applies some limitations but results in much simpler and faster1 code.

Raycasting (not to be confused with ray-tracing) works by making each column of pixels on the screen cast a "ray" out to see what walls it encounters, and we use the information about walls to draw a column of pixels representing the wall. Some raycasting engines (like that of the famous Wolfenstein 3D) force all walls to be the same height, which means you can stop tracing when you hit the first wall, but we want to allow walls of various heights, so it traces the ray out to the distance limit, then tracks back and draws all the lines back-to-front so that the nearer lines cover the further ones.

The final jam version of Spilljackers was 1093 lines, but I had the basic rendering of the map nailed down after the first evening of coding, and in fact the core of the algorithm can be demoed in 43 lines of code. There is some trig used, but if you've ever built a 2D game that used trig to do movement or collision detection, the math here is no more complex than that. Let's take a look!

We start by defining some constants and variables, including screen size, player characteristics (speed, turn speed, width, and height), and position/rotation:

(local (W MW H MH tau) (values 240 136 140 68 (* math.pi 2)))
(local (spd tspd pw ph) (values 0.7 0.06 0.7 0.5))
(var (x y rotation) (values 12 12 0))

Next we have the movement code. This looks a lot like it would in a 2D TIC game—when we move, we check all four corners of the player's bounding box to see if the new position is valid based on whether the map coordinates for that position show an empty tile (zero) or not. In a real game we would have some momentum and sliding across walls, but that's omitted for clarity.

(fn ok? [x y] (= 0 (mget (// x 8) (// y 8))))

(fn move [spd]
  (let [nx (+ x (* spd (math.cos rotation))) ny (+ y (* spd (math.sin rotation)))]
    (when (and (ok? (- nx pw) (- ny pw)) (ok? (- nx pw) (+ ny pw))
               (ok? (+ nx pw) (- ny pw)) (ok? (+ nx pw) (+ ny pw)))
      (set (x y) (values nx ny)))))

(fn input-update []
  (when (btn 0) (move spd))
  (when (btn 1) (move (- spd)))
  (when (btn 2) (set rotation (% (- rotation tspd) tau)))
  (when (btn 3) (set rotation (% (+ rotation tspd) tau))))

Now before we get to the actual raycasting, let's take a look at the map data. In TIC-80 each map position has a tile number in it which corresponds to a location on the sprite sheet. Rather than encoding complex tables of tile numbers to the visual properties of the map cells they describe, we encode properties about the tile in its sprite sheet position.

The color of the cell is determined by the sprite's column, and the height of the cell is determined by the its row. In this image tile #34 is selected. Since the sprites are arranged in a 16x16 grid, we calculate its column (and therefore its color) by taking the tile number and calculating modulo 16, getting 3. Likewise 34 divided by 16 (integer division) is 3, which gives us our height multiplier.

Back to the code—let's jump to the outermost function and work our way inwards. The TIC global function is called sixty times per second and ties everything together: reading input, updating state, and drawing. The for loop here steps thru every column to call draw-ray after precalculating a few things.

(fn _G.TIC []
  (input-update)
  (cls)
  (for [col 0 W] ; draw one column of the screen at a time
    (let [lens-r (math.atan (/ (- col MW) 100))]
      (draw-ray (math.sin (+ rotation lens-r)) (math.cos (+ rotation lens-r))
                (math.cos lens-r) col x y x y 16))))

If we calculate all distances as being from the single x,y point representing the player's position, (as is the case in the video here) then columns at the player's peripheral vision will look further away than columns near the center of the screen, resulting in a fisheye lens effect. The lens-r value above is used below to counteract that by calculating how far away the current column is from the midpoint of the screen. We also precalculate cos and sin once as an optimization to avoid having to do it repeatedly within draw-ray.

The draw-ray function below starts by calling the cast helper function to see where the ray will intersect with the next tile, and what tile number that is. The height of the wall is calculated based on the distance of that intersection point from the player, with the lens-factor applied as mentioned above to counteract the fisheye effect. Once we have the height factor, it's used to calculate the top and bottom of the "wall slice" line by offsetting it from MH (the vertical midpoint of the screen), the ph height of the player, and (// tile 16), which tells us which row in the sprite sheet we're looking at.

Because we have to draw some walls behind other walls, the draw-ray function must be recursive. The limit argument tells us how far to recurse; if we haven't hit our limit, keep casting the ray before calling line to actually render the wall we've just calculated. This ensures that more distant walls are drawn behind closer walls. Finally we only call line if the tile is nonzero, because the zeroth tile indicates empty space. The color of the line is (% tile 16) since as per above, the column in the 16-tile-wide sprite sheet determines wall color.

(fn draw-ray [sin cos lens-factor col rx ry x y limit]
  (let [(hit-x hit-y tile) (cast rx ry cos sin) ; where and what tile is hit?
        dist (math.sqrt (+ (math.pow (- hit-x x) 2) (math.pow (- hit-y y) 2)))
        height-factor (/ 800 (* dist lens-factor))
        top (- MH (* height-factor (+ (// tile 16) (- 1 ph))))
        bottom (+ MH (* height-factor ph))]
    (when (< 0 limit) ; draw behind the current wall first
      (draw-ray sin cos lens-factor col hit-x hit-y x y (- limit 1)))
    (when (not= tile 0) ; only draw nonzero tiles
      (line col top col bottom (% tile 16)))))

In order to determine which tile a ray hits next, the cast function must check whether the ray will hit a horizontal edge of the next map cell or a vertical edge. Once it determines this it can use the precalculated cos and sin values to pinpoint the coordinates at which the next cell is hit, and call mget to identify the tile of the cell.

(fn cast-n [n d]
  (- (* 8 (if (< 0 d) (+ 1 (// n 8)) (- (math.ceil (/ n 8)) 1) )) n))

(fn ray-hits-x? [nx ny nxy nyx]
  (< (+ (* nx nx) (* nxy nxy)) (+ (* ny ny) (* nyx nyx))))

(fn cast [x y cos sin]
  (let [nx (cast-n x cos) nxy (/ (* nx sin) cos)
        ny (cast-n y sin) nyx (/ (* ny cos) sin)]
    (if (ray-hits-x? nx ny nxy nyx)
        (let [cx (+ x nx) cy (+ y nxy)]
          (values cx cy (mget (// (+ cx cos) 8) (// cy 8))))
        (let [cx (+ x nyx) cy (+ y ny)]
          (values cx cy (mget (// cx 8) (// (+ cy sin) 8)))))))

And that's it! That's all you need2 for a minimal raycasting game in TIC-80. Below is an embedded HTML export of the game so you can try it out for yourself! Pressing ESC and clicking "close game" will bring you to the TIC console where you can press ESC again to see the code and map editors. Making changes to the code or map and entering RUN in the console will show you the effects of your changes!

---

I learned about raycasting from reading and modifying the source to the game Portal Caster which creates some neat puzzles using portals. I also found this write-up of FPS-80, a somewhat more elaborate TIC-80 raycaster that includes some impressive lighting effects. In the final version of Spilljackers, I used the interlaced rendering strategy from FPS-80. Every even tick, you render the even columns, and every odd tick you render the odd columns. This results in some "fuzzy" visuals, but it improves performance to the point where the game runs smoothly even with a long render distance even on an old Thinkpad from 2008.

---

[1] In this context, the reason raycasting is faster is that the platform I'm using (TIC-80) does not have any access to the GPU and does all its rendering on the CPU. If you have a GPU then things are different!

[2] You can see the full code on its own in a text file here. If you have TIC-80 downloaded, you can run tic80 mini.fnl to load up the game locally; the data for the map and palette are encoded as comments in the bottom of the text file.

« older | 2020-09-28 22:06:19