Gotta Go Fast

76 Days Until I Can Walk

It has been another very productive day, although a couple of frustrating bugs have popped up which I wasn’t able to resolve today.

Fixed Point Arithmetic

My initial goal was to try and implement fixed point arithmetic for the ray caster functions. I read about FPA in Larry Myers book, but never got the chance to use it. My implementation follows his quite closely in that I use an FP_SHIFT value of 16, which is apparently an acceptable compromise on precision in floating point values.

However, Myers’ sample code for these functions is in assembly, and I found his descriptions for the implementation of multiplication and division to be a little difficult to parse. He essentially relies on an understanding of how the imul and idiv instructions work in the Intel architecture. I found this lecture by Van Hunter Adams to be a little better, but he skips over the implementation of fixed point division far too quickly.

The issue is essentially this. If we want to implement addition and subtraction in fixed point, that’s easy. We can simply add and subtract our fixed point values and the maths will work out. For multiplication and division, however, we need to do some shifting before and after the operations. This is because multiplication and division will cause overflow in the binary representation of the fixed point number. We can deal with this by casting our values from 32 bit ints to 64 bit longs before we perform the operation, capturing the overflow in the larger datatype and then shifting things around to get our answer. But why does this work?

I found it easier to understand what was going on by thinking about the problem as an equality rather than as a programming problem. When switching from floating point to fixed point, we essentially multiply by some constant \(C\). This constant is the same for all values that we convert to fixed point. So if we have two floating point values \(a\) and \(b\), and we convert them both to fixed point values, the result will be \(aC\) and \(bC\).

Now if we think about a naive implementation of our four basic operations using these samples:

Addition:

\[aC + bC = C(a + b)\]

Subtraction:

\[aC - bC = C(a - b)\]

Multiplication:

\[aC \times bC = abC^2\]

Division:

\[\frac{aC}{bC} = \frac{a}{b}\]

Note how everything is fine for addition and subtraction. The result will be the sum or difference of \(a\) and \(b\) scaled by the same constant \(C\)

However this constant is squared during multiplication, and cancels out during division. Therefore, in order to implement fixed point multiplication and division we must divide the result of multiplication by \(C\), and multiply the result of division by \(C\). So the “correct” way to do multiplication and division in fixed point is:

Multiplication:

\[\frac{aC \times bC}{C} = \frac{abC^2}{C} = abC\]

Division:

\[C \times \frac{aC}{bC} = C \times \frac{a}{b}\]

In Rust, the implementation will look like this:

pub const fn add(a: i32, b: i32) -> i32 {
	a + b
}

pub const fn sub(a: i32, b: i32) -> i32 {
	a - b
}

pub const fn mul(a: i32, b: i32) -> i32 {
	((a as i64 * b as i64) >> FP_SHIFT) as i32
}

pub const fn div(a: i32, b: i32) -> i32 {
	(((a as i64)  << FP_SHIFT) / b as i64) as i32
}

With this done, I implemented conversion from f64 and i32 to fixed point using traits which I implemented on the built in types.

const FP_SHIFT: i32 = 16;
const FP_MULT: f64  = 65536.0;

pub trait ToFixedPoint {
	fn to_fp(&self) -> i32;
}

pub trait FromFixedPoint {
	fn to_f64(&self) -> f64;
	fn to_i32(&self) -> i32;
}

impl ToFixedPoint for f64 {
	fn to_fp(&self) -> i32 {
		(*self * FP_MULT) as i32
	}
}

impl ToFixedPoint for i32 {
	fn to_fp(&self) -> i32 {
		*self << FP_SHIFT
	}
}

impl FromFixedPoint for i32 {
	fn to_f64(&self) -> f64 {
		*self as f64 / FP_MULT
	}

	fn to_i32(&self) -> i32 {
		*self >> FP_SHIFT
	}
}

All of this would probably be better if I implemented it using macros, but I’m still struggling to fully understand the syntax, and given the number of things I wanted to get done today, studying macros did not feel like a good use of my time.

With fixed point implemented, I started swapping out all the floating point calculations from my ray cast implementation. I also properly dropped in my lookup tables, meaning that finding the result for many trigonometric operations is simply a case of indexing quickly into an array.

It took a little bit of fiddling, but but before long I had my ray cast function fully switched over, and I am very happy with the result. Just as a little bonus, I “borrowed” F. Permadi’s approach to shading and applied it to my ray caster so that my simple little test room would look a little better.

While I am very happy, there are bugs. The zero-width walls are causing problems. If the rays hit them at a certain angle, then is possible for the ray to miss the side of the zero-width wall and it will disappear. You’ll notice this if you walk around the demo level. I wasn’t able to fix this today, but I will come back to it.

Collision Detection

By the time I was finished with FPA, it was getting a little late, but I really wanted to try and implement collision detection on the walls, if only to improve the experience of the demo a little bit. Myers’ has a very detailed implementation of a collision detection function in Chapter 5 of his book which checks for adjacent walls in front, behind, beside, and diagonal to the camera. His implementation allows for sliding along walls too. Just to get the ball rolling, I ported his function from C to Rust and dropped it straight into my application. It works… OK?

If the camera is moving down or to the right, then everything seems to work fine, but when moving up or to the left (relative to the map, not the camera) we can clip through walls. Again, I didn’t have time to resolve this today, so I will come back to it on Monday. Myers’ code is also quite long, contains a fair bit of duplicate code, and several magic numbers. I’m pretty confident that I can tidy this up and make it more Rust-like. But for now, it’s an excellent start.

Other Happenings

I’ve got a lot done this week. Far more than I had initially set out to do on the code base, but I have neglected two tasks that were not related to writing code.

I want to write a longer form, better edited article for the site about my initial impressions of Rust and my understanding of how Rust and WebAssembly work together. I think this will be a good exercise for gaining a deeper understanding of Rust and what’s actually happening behind the scenes.

I also want to try and keep up with Tim McNamara’s Rust course, if I can. It is at the end of week 2, so I would like to catch up on the lectures and start following along properly.

Given that today is Friday, I think I will push pause on software development and spend the weekend dealing with these two outlying tasks. I will get back to coding on Monday. Hopefully first I will resolve these little graphical bugs, and then my next goal will be to get texturing working.

Have a good weekend folks!