Coding Challenge Postmortem And Analysis: Asteroids in 10 Hours

If you missed the live blog then check out Coding Challenge: Write Asteroids in 10 hours or less for the background. Let us now take a retrospective look at the results.

The latest version of the game and source code can be found here.

Motivation

Why code Asteroids when I’ve already done Tetris?

Asteroids lets you see a bunch of things that you can’t really demonstrate in Tetris, for example dynamic object creation, collision detection between irregular geometric objects, and to a point, unbuffered keyboard input. I also designed the game’s code to make it ripe for developing into a 2-player co-op game which I will (hopefully) demonstrate how to do in a later post. The mathematics in Asteroids, while still relatively simple, is also substantially more complicated for a beginner than in Tetris as it requires the use of vectors and trigonometry. If you sift through the Asteroids source code you will be able to pick up a few tricks that you won’t from the Tetris code (and vice versa of course).

Before The Session

I knew that Asteroids would be using irregular shapes so I spent some time implementing and testing geometry code in my Simple2D library. I also browsed the web to see what techniques other people had used to generate asteroid shapes. The original game has 3 sizes of asteroids and the shapes are pre-defined (and I’m told they don’t rotate although I don’t personally remember). I thought it would be nice to generate the asteroid shapes randomly and used a variation of the concentric circles idea (see original blog post) suggested by another programmer on a forum. I also refreshed myself on things like angular momentum on Wikipedia, but discarded that and most other things that really aren’t needed at all, and stripped the formulas down to the simplest possible forms. Asteroids is not a physics simulation and does not require an accurate or realistic physics engine, so there is no point regurgitating a bunch of complex math for the sake of moving a ship around.

Atari 2600 – Atari – Asteroids (Photo credit: Sascha Grant)

For the collision detection, I imagined using traditional 2D methods which for those not in the know I will explain briefly. On each frame:

• Take the bounding box of the player object (ship) and the bounding box of all enemy objects (asteroids) (a bounding box is the smallest rectangle that an irregular object will fit inside completely)
• Using simple subtraction, determine if any of the enemy bounding boxes intersect the player object bounding box.
• For those bounding boxes which intersect, do a pixel by pixel comparison of the intersecting parts only, using masks of the objects. An object mask is typically a black and white image where black represents empty space (or background) and white represents a pixel in the object itself. In other words, an object’s mask in this case is the outline of the object, filled in solid white, on a black background. If a pixel in the same relative location in both masks is white, the objects are in collision.

To my delight I found that this is unnecessary with Direct2D, as it provides interfaces which calculate whether or not two geometries intersect and are therefore colliding with each other. This cut down the time requirements of coding the game significantly, and I took this into account when making the estimate of how long it would take.

Note that while this works for shooters where it doesn’t matter what plane, side or surface the objects intersect on, for a platform game things are more complicated: it is not good enough to know that a player is intersecting with a platform, we must also know where so that the player’s position can be adjusted such that they appear to be walking smoothly on a potentially uneven or sloping surface.

During The Session

There is really not much to say about the coding session itself. Besides human factors, things went fairly smoothly and more or less as I expected. There were no big unexpected design or implementation problems although I did realize part-way through that there was a fundamental flaw in Simple2D that would cause geometric objects not to be freed from memory when they were finished with, causing a memory leak. This is particularly troublesome with the bullets since new ones can be created several times per second, however I knew I would not have time to fix that so I resolved to deal with it later (and the 1.0 version of Asteroids does indeed fix this bug).

The main mistake I made was in using a heterogeneous container for all the game world objects, which turned out to be a fairly serious design flaw by the end stages. I was also aware of the design flaw whereby the behaviour of some objects was time-dependent but others were frame-rate dependent, which meant it ran fine on my Core i7 but would behave bizarrely on slower machines, and indeed a colleague who tried it on a Windows 7 VM reported that it in fact ran way too fast.

The main dilemma I had was trying to decide whether a ship should own its bullets and maintain a list of them, or whether the game world should own the bullets. In the end I went for the latter option with a callback to the ship object when a bullet is removed from play. This was probably also a design mistake as it makes the code more entangled and the flow more complicated than it needs to be.

I didn’t try to hide or avoid the use of pointers this time but I’m not a fan of the way newly-generated bullets are returned as a pointer as I feel that it is messy compared to the rest of the code and there is likely a better solution.

The Human Element

For this particular challenge I had decided to start at midday, but having been up very late the previous night, I deferred the start to 2pm, which again left me with the undesirable finishing time of midnight as with Tetris. I was busy before the start and didn’t have time to eat a thing, although I did remember to take off my shoes and turn the lights on when I got to the office this time. Less than 2 hours into the challenge, hunger won over and I cooked some lunch, which ate a chunk of almost an hour out of my coding time.

My work speed wasn’t as fast as on Tetris at the beginning, probably due to tiredness, but it picked up eventually. There were some periods – particularly with the geometry collision – where it took quite a bit of time to come up with only a few lines of code, but those lines were crucial to the correct functioning of the game.

At about 9pm I stepped outside for a few minutes to stretch and have some fresh air in the warm Norwegian summer night – raining but still bright as right after morning sunrise. This was refreshing and helped me crack on, but 8 hours in around 10pm I got hit by the same wall of tiredness that hit me when I was coding Tetris, and in fact almost all of the bugs in the game came from the output during the last two hours of coding.

It was easy to take breaks during this challenge as I wanted to write the live blog in a more beginner-friendly tutorial-style format. Some of those blog entries took 20-30 minutes to write and actually became quite a time sink, but at least I had time away from the source code windows.

In the last half hour I got so blurry that I was typing things like “vool” instead of “virtual bool”. I forgot to add in “break” statements at the end of each case in a switch, and made lots of other silly mistakes.

Time

When I claimed I could code Tetris in under 8 hours, I was 80% sure that I could. I had no such confidence about the timing of Asteroids. Even though the finished code is ironically less lines than Tetris, the game itself is inherently more complicated from a coding point of view. My initial response when Jeremy gave me the challenge was “I’m not sure I can do that in 8 hours”. There was talk of 9, 12 etc. but I decided to settle on 10, knowing that I really wasn’t quite sure if it would take 6 or 16. So I gave myself an extra buffer of 2 hours and it’s lucky I did because I finished at precisely midnight. Having said that, if you substract an hour for lunch and all of the blogging, it may well have only taken 6 hours or in any case less than Tetris. But on the other hand again, during Tetris I was writing text rendering code for Simple2D, but for Asteroids all of that was already taken care of. I made some minor changes to the geometry code during the challenge and that was it.

Most Satisfying Moment

This was easily when I first got the ship to rotate and accelerate on its own on the screen. The movement was extremely fluid and satisfying and being able to adjust the acceleration, rotation and drag factors allowed me to tune it until the control mechanism was more or less perfect. It was such an elegant yet simple piece of math, the result was rewarding to see.

Bugs

Three of us playtested the game afterwards and found a number of bugs besides the ones I had already noticed. The full list of fixes in Asteroids 1.0 since the version posted at midnight on the day of the challenge is:

• The geometry memory leak is fixed (a change to Simple2D itself)
• The scoring for each asteroid was calculated incorrectly (I left break statements out of a switch, and have updated the code in the original post to correct this error)
• You were able to shoot when dead (and move and such although the ship is invisible and gets reset; this was due to a missing if statement to check if the ship was active or not)
• Calculation of speed, position and lifetime of some game objects was done per-frame instead of on a time basis. I mentioned this in the original blog post and said that the real solution is to run timers on a separate thread. In fact there is another way which is to measure the number of processor ticks between each call to the object update function in a single-threaded environment, and use the elapsed time divided into one second and multiplied by the ideal desired frame rate as a multiplier in each movement, speed and rotation calculation. Simple2D provides a function LinearMovement which is exactly for this purpose, and simply multiplying everything by LinearMovement(60.f) (for an ideal frame-rate of 60 fps) means that objects will behave in a time-based rather than frame-rate-based manner.
• Asteroids spawning on top of you at the start of a new wave would instantly kill you. This was the most obvious bug, and there are a variety of ways to fix it: deploy the ship somewhere else, make sure the asteroids aren’t generated at an intersecting location, wait for re-spawn when you lose a life until asteroids have moved out of the way, and so on. I went for the quick and dirty option: give 4 seconds of invulnerability right after you die, and 4 seconds of invulnerability right after a new wave of asteroids is generated.
• Keyboard input was being captured even when the game window didn’t have focus, thanks to the fact we were using GetAsyncKeyState instead of Windows keyboard messages to process keyboard input. This is readily solved by just adding in a check to see if the window has focus before calling GetAsyncKeyState. There are a few ways of checking which window has focus, but I simply modified Simple2D to keep a flag which is updated when the window receives WM_GETFOCUS or WM_KILLFOCUS.
• Asteroid splitting was meant to send smaller asteroid chunks off at right angles (orthogonally) but it didn’t as I had gotten some of the minus signs the wrong way round in the vector calculations. I fixed this and updated the code in the original blog to reflect the changes.

I also made a couple of changes:

• The number of points you get for destroying an asteroid is now multiplied by the current wave number.
• You gain an extra life at 100,000, 250,000, 500,000 and 1 million points, and every 1 million points thereafter.

Improvements

There are an absolute ton of changes and improvements that can be made, both in the code implementation and the gameplay itself, but rather than listing them all here, I will continue with new blog posts as the tweaks go into action!

The End

I hope you enjoyed this challenge and follow-up. Links to the game can be found at the top of this post and my current best score is 1,493,500. Enjoy!

Want to challenge me? Write your challenge suggestions below!

Advertisement