Well, It Casts Rays

79 Days Until I Can Walk

Implementation of the ray casting algorithm has officially started! A space has been defined, and rays are being cast about, but the resulting render is… not good.

Yeah, that image should be a view of a straight wall viewed from the middle of a square room.

Diagnosing these problems is a pain, and while I made progress tracking down the bugs, I’m going to defer to F. Permadi’s JavaScript implementation at this stage in an effort to figure out what I am missing.

There are two major points that I would like to mention based on today’s programming session. The first is in relation to how I am implementing walls in this engine, and the second is related to a minor challenge I faced with Rust.

Modelling Walls

Most implementations of the ray cast algorithm that I have seen online model their environment using an array (or similar data-structure) where each element denotes a tile in the map (usually 64x64 pixels in size). Below is an example in the format used by F. Permadi for his JavaScript implementation.

var map = 'WWWWWWW'+
          'WOOOOOW'+
          'WOOOOOW'+
          'WOOOOOW'+
          'WOOOOOW'+
          'WOOOOOW'+
          'WWWWWWW';

Each ‘W’ denotes a wall, while ‘O’ is open space. Each wall is a 64x64x64 pixel cube that is inserted into the environment and will be rendered by the ray caster. This is a simple approach that is easy to understand and makes it trivially simple to build environments without the need for a level editor.

However, in Larry L. Myers “Amazing 3-D Adventure Game Set”, he represents his levels using two separate arrays—one for horizontal walls and one for vertical walls. An equivalent map to the above in Myers’ notation (shown below in Rust) would be:

static H_WALLS: &'static[i32] = &[
    1, 1, 1, 1, 1, 1, 1,
    0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0,
    1, 1, 1, 1, 1, 1, 1,
];

static V_WALLS: &'static[i32] = &[
    1, 0, 0, 0, 0, 0, 1,
    1, 0, 0, 0, 0, 0, 1,
    1, 0, 0, 0, 0, 0, 1,
    1, 0, 0, 0, 0, 0, 1,
    1, 0, 0, 0, 0, 0, 1,
    1, 0, 0, 0, 0, 0, 1,
    1, 0, 0, 0, 0, 0, 1,
];

An interesting feature of this notation is that we do not need to place entire cubes into our environment. We can create zero-depth walls, potentially making better use of the space available to us in our environment. Moreover, when we implement transparency in our ray caster, this notation will enable us to include structures such as chain-link fences without the need to slap them down in large cubes. We can have cube shaped walls (just like Permadi’s notation), except each face can have a different texture. Pretty cool!

Admittedly, this is my first time working with this notation, so some of my expectations are speculative, but I am quite sure that these features will drop naturally into place as development progresses.

The trade-off from a development perspective is that we need twice as much space to store our level. Moreover, this notation is harder to follow than Permadi’s, so creating test maps is more laborious. I will probably write a level editor to help me in the near future.

Generating Look-Up Tables At Compile Time

A common optimisation that we apply in ray casting is to pre-compute values for all trigonometric operations we expect to perform when casting rays. We can pre-compute quite a lot of these values before we start casting rays. Not only can we predict values for cos, sin, tan, and their respective inverses, we can also compute an x and y step for each ray as it is cast, heights of walls based on distance, and fish-eye corrections for the image projected onto the projection plane.

This is done by defining our unit circle in terms of the size of our projection plane. The player usually has a viewing cone of 60 degrees, meaning we can say that an arc the length of our projection plane has an angle of 60 degrees. In my engine the projection plane is 320 pixels wide. So 30 degrees would have an arc of 160 pixels. An arc for 180 degrees would be 960 pixels.

Using this information, we can generate lookup tables for sin, cos, and tan where the index is an integer representation of an angle derived from the length of the arc it draws.

If I were working in C++ I could generate all of these lookup tables at compile time using constexpr as shown below.

int const PROJECTION_PLANE_WIDTH = 320;

int const ANGLE_60  = PROJECTION_PLANE_WIDTH;
int const ANGLE_180 = ANGLE_60 * 3;
int const ANGLE_360 = ANGLE_60 * 6;

static constexpr float degrees_to_radians(float const degree) {
    return ((float) (degree * M_PI) / (float) ANGLE_180);
}

constexpr std::array<float, ANGLE_360 + 1> const SIN = []{
    std::array<float, ANGLE_360 + 1> a{};

    for (int i = 0; i < a.size(); i++) {
        a[i] = sin(degrees_to_radians(i));
    }

    return a;
}();

This does result in a larger binary, but it also means that we don’t need to generate these tables on initialization by, say, calling an init function.

Rust, however, does not appear to have an equivalent feature that works like this. I have dropped some questions into Rust forums, but I have not got an answer yet. This is one of those problems that I will get back to later once I actually have a working ray caster. For now I have substituted my usual lookup tables with my own sin, cos, tan functions that use the circle defined in terms of the projection plane:

pub const PROJECTION_PLANE_WIDTH: i32 = 320;

pub const ANGLE_60:  i32 = PROJECTION_PLANE_WIDTH;
pub const ANGLE_180: i32 = ANGLE_60 * 3;
pub const ANGLE_360: i32 = ANGLE_60 * 6;

pub fn radian(angle: i32) -> f64 {
    angle as f64 * PI / ANGLE_180 as f64
}

pub fn cos(degrees: i32) -> f64 {
    radian(degrees).cos()
}

I maintain that there must be some way to achieve the equivalent behaviour to the C++ example in Rust, but for now I’ll keep ploughing ahead. Once I have a proper answer to this, I’ll discuss it in a future post.

Conclusion

So that’s it for today! I had hoped to have more done, but that’s OK. At this rate, I should have a functioning ray cast implementation in place by the end of tomorrow, and hopefully there will be enough time left in the day to animate a spinning camera so we can watch an environment render within the web page. I haven’t done any work on texturing yet, so the walls will be simple red blocks for now.

Have a good night folks and I’ll post another update tomorrow evening!