Learning to Raycast in Haskell

Posted on March 3, 2019 by Jack Kelly
Tags: coding

I built a raycaster in Haskell using codeworld-api over the weekend, and put the code up on sr.ht. Raycasting is not a particularly impressive technique these days: John Carmack did it 17 years ago in a cave! With a box of scraps! with texture mapping, while wrangling the IBM VGA, and while getting acceptable performance out of an 80386. (Aside: the Wolfenstein 3D Black Book is a fantastic read.)

Despite being obsolete, raycasting is a fun first step. I mostly followed F. Permadi’s tutorial from 1996, which does a pretty good job of deriving the maths, not just hitting you with walls of C. I was struggling to get the actual ray casting to work right, and eventually found the Algorithm of Amanatides and Woo. This post is about reaching that success, and reflecting on the thought processes that got me there.

Computer graphics seems to be one of those areas where you can get things almost right and yet end up with total garbage. Which is what I was getting after I’d set up all the data structures and dove into trying to render a first-person image. After a while, I ceased shotgun debugging and did what I should have done from the start: systematically verified my assumptions.

I stepped back and wrote a top-down visualiser, to show the map and the player’s location and facing. It showed me the map upside-down and back-to-front and the player marker somewhere totally unexpected. I had made several bogus assumptions, but the most critical was that CodeWorld’s screen coordinates go up with increasing y, but just about every graphics tutorial uses coordinate systems which go down with increasing y. I had also decided that increasing θ meant left turns in some parts of the code, and right turns in others.

After ironing out all the coordinate systems (world, map grid, camera) so they pointed in the same directions, I still had a lot of trouble getting sensible raycasting working. I didn’t know whether my renderer was dodgy or whether the rays I was casting were being funky, and both were reasonably fiddly pieces of code to get right. How can I bisect this problem?

Ancient Unix Wisdom: Make it work, make it right, make it fast.

I commented out my failed attempts at fancy raycasting algorithms, and did the simplest thing I could think of: cast rays by stepping them forward 0.01 units until they hit a wall. The result looks a bit dodgy, but its errors are predictable and easily understood:

Basic Raycasting

Having reasonably sound raycasting gave me the confidence to vary the renderer until it was right, and I took a little detour to add basic shading based on z-distance. Even with dodgy walls, it adds a lot to the scene:

Basic Shading

Now that I had a working renderer, I could go back and fix up the ray casting. It turns out there’s a real difference between reading an algorithm in a paper, versus implementing it, versus grokking it. I “knew” that already, but it was instructive to live through a fresh lesson about it.

Trying to describe the extra knowledge in grokking isn’t easy. It’s something like the difference between knowing what the implementation says versus what the implementation means. Amanatides’ algorithm doesn’t use abs, but it makes a good example: abs (x2 - x1) says “compute the absolute value of the difference between x2 and x1”. Grokking that means something like looking at it and thinking “distance”, without any conscious intermediates.

A ray from an origin point p⃗ in a direction v⃗ has the equation r⃗ = p⃗ + tv⃗, where t ∈ [0, ∞). Amanatides’ algorithm implicitly steps through the values of t that intersect grid lines, making it faster and more precise than my naive version. Implementing the algorithm meant I could find the grid cell that the ray hits; grokking the algorithm meant I could reconstruct the value of t that hit the wall. Once I had that, I had proper distances, and the rendered scene looked a lot better (you can see on the map that rays no longer penetrate the walls):

Amanatides Raycasting

What did I learn from all this, beyond how to cast rays like it’s 1992?

All told, it was a lot of fun, and I’m looking forward to doing more.

Previous Post
All Posts | RSS | Atom
Next Post
Copyright © 2019 Jack Kelly
Site generated by Hakyll (source)