Three recent bugs

Airships
2014-02-07 18:30
As I'm getting ready to release the first alpha version of Airships, I'm going over the code and finding all kinds of entertaining bugs. In this post, I'm going to cover three kind of embarrassing ones, showing what was wrong, how this manifested itself, and how I fixed it.

Until a few days ago, Airships had no sound effects at all. This is not to say that sound isn't important, but I feel it's quite good to wait for a game to take shape for a bit before adding sound. I, uh, usually find that I start making the sounds for it in my mind as I play it, and that gives me a good guide.

Anyway, when I implemented the sound system, the results were really disappointing. Everything was really quiet, and sounds seemed to randomly not play. I started worrying that maybe there was some kind of issue with sound in Slick2D, the game library Airships uses. Eventually, I tracked down the issue to a single-letter mistake: I had written

double volume = 0.9 * random.nextDouble * 0.1;

where I had meant to write

double volume = 0.9 + random.nextDouble * 0.1;

This meant that sound effect volumes varied between 0% and 9% rather than between 90% and 100%. No wonder things had been so quiet and unreliable! At least the fix was easy.

The second problem I encountered was not so straightforward. I noticed that crewmen were taking suboptimal paths through ships, ignoring corridors that would allow them to move a lot faster.

For example, a crewman at fire point A trying to get to Suspendium chamber B should take something like the following path:

But instead, I found he would take this path:

Sure, it was a bit shorter in terms of number of tiles, but a tile of corridor takes 300ms to cross, while most modules' tiles take 800ms or more. So instead of taking that water bucket and running down the corridor, our crewman would make his way through a coal store and another suspendium chamber, taking much longer.

So what was the problem? Pathing in the game is calculated in batches: the optimal path to get to a module from any tile is calculated all in one go, by using a flood fill followed by gradient descent.

First, the distance between each tile and the target module is calculated. Then, the quickest path from each tile to the target module is the path where at each step, the remaining distance is reduced the most.

To determine the distances, a flood fill algorithm is used. First, the distance value for all tiles in the target module is set to zero, and the distance for all others is set to infinity. The module's tiles are added to a list of tiles to be processed.

Then, the algorithm picks a tile from the list to be processed and looks at the neighboring tiles. If the distance value of that tile is greater than the distance for the tile we're processing plus the amount of effort it takes to move from the one to the other, we update the distance value of that second tile to be that new, shorter distance. We then also add that second tile to the list of tiles to be processed.

We then simply keep on doing this: picking a tile, looking at its neighbors, and updating their distance if it can be improved - until there are no more improvements to be made, leaving the list of tiles to be processed empty.

At the start, all the non-module tiles have an infinite distance, so the tiles adjacent to the module will immediately have their distance values updated. As the process moves outwards, "flooding" the structure (hence the name), a new, shorter distance will occasionally be discovered. Concretely, because corridors increase the distance value by less than other modules, it turns out that tiles connected to the target module via a sequence of corridor tiles will have a smaller distance value than otherwise.

Finally, once that is done, the best paths can be discovered simply by following the path of quickest decrease in distance.

So what went wrong? Well, I thought I'd be efficient. The calculation for the distance of an adjacent tile ought to be the distance of the current tile plus the movement cost of the adjacent one. Instead, I used the distance of the current tile plus its movement cost. That's more efficient, you see, because that's the same value for all adjacent tiles!

It also happens to be wrong. In practice, this meant that the distance values for tiles adjacent to corridors were as low as if they were corridor tiles themselves. And this meant that the pathfinding system would treat those tiles as corridors, and route the crewmen through them!

So this was a tricky one to debug, but again an easy one to fix: simply calculating the distance values correctly has made things work a lot more smoothly on the airships.

The third bug I had to fight recently was one where guns would refuse to fire on anything further up than them. I fairly recently added a concept of fire arcs to the game, limiting the angles at which a given weapon can fire a shot. This makes a lot of sense, because a cannon pointing right can't suddenly decide to fire on something to its left.

But something had gone wrong with the calculation of the firing angle. Angles for shooting at targets below the gun's muzzle were calculated correctly, while angles to targets above were wrong, offset by 180 degrees. The basic problem? Trigonometry is hard. It's doubly hard when the y-axis points down, as is the case in the game's coordinate system.

The solution there was a bit more heavyweight. I knew that I didn't want to keep on running into errors involving angles, so I ended up writing two new classes, Direction and Arc, which encapsulate an angle and a firing arc respectively. These then do the heavy lifting for answering questions like "what's the angle from point A to point B?" and "is this angle inside this arc?".

Perhaps this solution was overkill, but I really did not want to keep on writing ad-hoc solutions to calculations involving angles.

In summary: as a game that grew out of a prototype I put together to distract myself, there's a fair amount of technical debt in the code that I'm now working to root out. This is going to be an ongoing process, and it does mean that when the alpha is released, additional developments are sometimes going to take longer than you'd expect, because I have to clean up some code before I can sanely add a new feature on top of it. That's life.