Fixing the Same Bug Three Times

At this point my game was not really a game. It could step forwards in time, and entities with a velocity would drift along endlessly in space, but there was nothing that could influence that, there was nothing to play.

The next logical thing was what I thought would be the small job of collecting user input and passing it into the engine so that the player entity could move, simples. Twenty minutes later the code was done, but it took me a lot longer to figure out why it did not work as I expected.

The warm-up

Like most games player input is via a set of buttons and I decided to store these buttons as bits in (currently) a single byte. Go does not have enums like you would find in c#, the standard way to replicate this is in a block of consts with a counter called iota that increments once per line, so you get 0, 1, 2, 3 and so on down the block. That is not what I want for flags though, I want each one to be a single bit, which means 1, 2, 4, 8, and the usual way to get there is to take the number 1 and shift it left by the counter.

So I went and implemented it like this:

go
const (
	InUp Input = iota << 1
	InRight
	InDown
	InLeft
)

Anyone having written this before may have noticed that I wrote this wrong, and it is wrong in a way the compiler is perfectly happy with. What I wanted was 1 << iota, the number one shifted left by the counter. What I typed was iota << 1, the counter shifted left by one, which is the same three pieces in a different order and nothing like the same thing. So instead of 1, 2, 4, 8, I get 0, 2, 4, 6.

This created two issues that I had not yet spotted. The first number being 0 rather than 1 meant that we could never detect up was pressed when checking bits, 0 is sent for both on and off. The second issue was an even bigger one, pressing left would output 6 which is two bits not one (110). Pressing down and right also came out as 6 (110), so pressing left actually sent the signal to move the character down and right. Less than ideal.

The reason we want the flags to be a power of two is that a number can only be created with a single fixed combination of these flags, but for the way I had implemented it this just was not the case.

The corrected version is the same block with two things swapped round.

go
const (
	InUp Input = 1 << iota
	InRight
	InDown
	InLeft
)

The real one

Then I needed the simulation to know which entity is the player.

Entities live in a slice, and I do not hold pointers to them, for reasons I wrote about when I built the storage. A slice can move in memory when it grows, and a pointer taken before that happens quietly refers to abandoned memory. Instead every entity has a handle, which is a pair of numbers, an index and a generation. The generation is bumped whenever a slot is freed, so an old handle to a reused slot no longer matches and can be spotted as stale.

So the player is just an entity, and the world holds its handle. The only question left is how to tell whether a player has been created yet.

My first attempt stored the player as a separate value and checked whether it was empty.

go
if e.playerEntity == (Entity{}) {

An entity is a position and a velocity. A player standing still at the origin has a position of zero and a velocity of zero, which is exactly what an empty entity looks like. So the check reported that no player existed at precisely the moment one did. Since my tests spawn the player at the origin, this was not a subtle case.

Fine, I thought. Use the handle instead.

go
if e.playerHandle == (Handle{}) {

An empty handle is index nought, generation nought. The first entity ever created goes into slot nought, and its generation starts at nought. So the empty handle was an exact match for the first entity in the world. Same bug, new location.

At this point I had a test that crashed, because it stepped a world in which nothing had been spawned at all, and the code went looking for entity nought in an empty slice. So I added a check that the handle referred to something alive, which is a check I already had.

go
if !e.IsAlive(e.playerHandle) {

The crash went away, and something considerably nastier arrived in its place.

Getting worse each time

There is an older test that spawns an ordinary entity, gives it a velocity, steps the world for a second, and checks it has moved. That test started failing, and it had nothing to do with the player.

The entity it spawns is the first one in the world, so it lands in slot nought with generation nought. The world has no player, so the player handle is empty, which is index nought and generation nought. Those are the same handle. My liveness check dutifully confirmed that the handle pointed at something alive, because it did, and the player movement code then reset that entity’s velocity to zero on every tick. The thing never moved.

Each fix had made the failure quieter. First a test that failed loudly, then a crash, then an unrelated entity being silently corrupted in a different test.

Where the actual problem was

I kept trying to pick a better value to mean “no player”, and there is no such value. The zero handle is a perfectly good handle. It refers to the first entity in the world, and there is nothing about it that says otherwise.

This is a gap I did not know I relied on C# to fill. In C# I would have written Entity player and left it null, and null works because it is not a valid instance of anything. It is a value the variable can hold that no real object can ever be. That is the whole job it does, and I have never had to think about it. And if Entity were a struct rather than a class, where null is not on offer either, I would have reached for Entity? and the compiler would have gone and manufactured the spare value on my behalf, which is a thing I have also never had to think about.

Go gives you neither. A Handle is two unsigned integers and every combination of two unsigned integers is a legitimate handle. There is no spare value hiding in the type. And the obvious escape hatch, holding a pointer and leaving it nil, is closed by a decision I had already made for good reasons, since pointers into a growable slice are the exact thing the handles exist to avoid.

So if I want an invalid handle, I have to manufacture one.

The fix is one word. Generations now start at 1 rather than 0.

go
e.generations = append(e.generations, 1)

No live entity ever has generation nought, so the empty handle can never match anything, and the liveness check rejects it without being asked to. There is no sentinel to choose, because the invalid value is now unreachable by construction. It also fixes this everywhere at once rather than just for the player, which is the part I like.

The test that caught it

Worth noting which test found the third version, because it was not the one I had just written.

The new test presses a direction and checks the player’s velocity comes out right. It was never going to catch this. Velocity is the thing the input code sets, and it was setting it perfectly well, on the entity it was pointed at. The entity getting wrecked belonged to a different test entirely.

What caught it was a test from weeks earlier, written for something else, which spawns an entity, gives it a velocity and checks where it has got to after a second. That test never looks at velocity being set. It only asks where the thing ended up, and where the thing ended up is the result of everything that ran that tick, including code that had no business touching it.

That is the second time this has bitten me on this project. When I built the entity storage I had a test sitting at full coverage that verified nothing at all. It despawned an entity and read it back through a function that returns an empty value for anything despawned, so the assertion held whether the code worked or not. Coverage tells you a line ran. It does not tell you anybody checked the result.

Where this leaves things

The simulation now takes input and the player moves, which sounds like very little for an evening, and it is. But it is the piece everything else was waiting on. The next job is recording a run and replaying it to prove it comes out identical the second time, and you cannot record what a player did in a world where the player cannot do anything.

There is a little issue with the player movement. If you press two directions at once you move diagonally across the grid, seems sensible, but the distance to the opposite corner of a square is greater than the length of its edges (approx 41% further). The real consequence is that the player covers more distance in the same amount of time, they move faster.

At the time I put it down to the grid that the puzzles will eventually sit on, a quirk if you will, and I wrote as much in my architecture doc and left a comment in the code saying the same. It stuck in the back of my head though as something I had to fix. In the next post I’ll cover the fix, it (again) turned out to be more than I expected, and to do it I had to call on our old friend Pythagoras.