Coding Challenge: Write Asteroids in 10 hours or less

Update 17-Jun-2012: Fixed some typos, the broken formatting in some of the code and the missing types after static_cast and dynamic_cast operators, and updated the code snippets to reflect two bug fixes.

Update 18-Jun-2012: Wrote the final section regarding the implementation of shields and waves.

The sun is shining brightly, it’s nice and warm outside and unbearably hot in the office, I didn’t manage to fall asleep til 7 this morning and people are asking me to go to the beach. This, of course, can only mean one thing: it’s time for another coding challenge!

Last time we managed to rattle through Tetris in a smooth 7 hours 59 minutes. Reader Jez Ward has upped the ante by issuing a challenge to write Asteroids in 10 hours or less. This is significantly more complex than Tetris for a few reasons:

1. It’s a free-form game world and not a grid, which requires the use of per-pixel collision detection
2. The ship has to accelerate and move in a way that roughly resembles basic physics
3. The ship and asteroids do not have rectangular shapes but are irregular geometric constructions

…all of which basically means that significant portions of the game have to be engineered using different techniques to Tetris, which I thought made it a good 2nd-stage challenge for beginning game programmers to follow along with.

Be prepared for some mathematics today: we are going to be needing some basic vector algebra and trigonometry. Yes, they say you don’t need to be good at math to be a good programmer, but unfortunately if you want to be a game programmer, you do need to have a decent grasp of it, there is no getting around it I’m afraid!

Note that DirectX provides a math library which handles this kind of stuff for you, and re-inventing the wheel is bad, however for the purposes of this demo I will code in the actual math so that beginners can see how it’s done, as it’s important to understand what is actually going on before you abstract it away.

Some ground rules: as with Tetris I will use my Simple2D graphics library for the rendering, and the game will have a similar kind of programmatic structure to Tetris, but I won’t copy and paste large chunks of code from Tetris as that would be cheating for the purposes of a challenge.

Once again you’ll need the Visual C++ 2010 Redistributable Package to follow along with each step, and as before I will post the source code and EXE after each step.

13:39 – Relax for 21 minutes before starting

Done.

14:00 – Set up project, create a ship that the player can rotate

Well without digging into too much boilerplate code, first we need a class for the spaceship. This could be included in the main game logic instead of its own class, but this way you can fairly simply extend the game to multiplayer co-op by replacing the ship object with an array of ship objects later and storing the score and number of remaining lives in said objects. Here’s a start:

class Player
{
...
	// The ship's center position in the game world
	int x, y;

	// The ship's current angle of rotation
	int angle;
...
	// The ship geometry
	Geometry shipGeometry;

public:
...	// Create ship geometry
	void Setup();

	// Reset the ship to its default settings
	void Reset();

	// Rotate the ship (user interaction)
	void Rotate(int);

	// Draw the ship in the game world
	void Draw();
};

Creating the ship geometry looks something like this:

	// Create ship geometry
	int xTop = 0;
	int xSize = 25;
	int ySize = 30;
	int yTop = -ySize / 2;
	int yIndent = 10;

	GeometryData gd = renderer->StartCreatePath(xTop, yTop);

	D2D1_POINT_2F sp[] = {
		{ xTop + xSize / 2,		yTop + ySize },
		{ xTop,					yTop + ySize - yIndent },
		{ xTop - xSize / 2,		yTop + ySize }
	};

	gd->AddLines(sp, 3);

	shipGeometry = renderer->EndCreatePath();

This creates a closed path geometry with 4 lines forming an arrowhead-type shape, starting with the tip of the arrow and going clockwise around the shape.

Drawing it is a snap with Simple2D:

shipGeometry.Draw(
		shipGeometry.Rotate(static_cast<int>(angle), Geometry::PointCenter) * shipGeometry.Move(x, y),
		Geometry::Center, renderer->MakeBrush(Colour::White));

Immediately we try to allow the player to rotate the ship though, there is a problem. You may initially try this (where OnKeyDown is called from the Windows WM_KEYDOWN message handler):

bool SimpleAsteroids::OnKeyDown(int key, int rc, bool prev)
{
	if (key == VK_LEFT)
		player.Rotate(-10);

	if (key == VK_RIGHT)
		player.Rotate(10);

	return true;
}

Unfortunately, this takes the user’s key repeat speed settings into account, meaning that you don’t get a smooth rotation of the ship until the repeat kicks in. If the user holds down an arrow key here, the ship will rotate slightly, then there will be a pause until the key starts to repeat, and the ship will then rotate in a discrete ‘jagged’ kind of motion on each repeat cycle.

Instead, we can use GetAsyncKeyState to poll the keyboard interrupt state in the portion of the code that does the physics work:

void SimpleAsteroids::UpdateObjects()
{
	if (GetAsyncKeyState(VK_LEFT))
		player.Rotate(-5);

	if (GetAsyncKeyState(VK_RIGHT))
		player.Rotate(5);
}

This works but now the problem is since we are checking the keyboard directly and not reading buffered keypresses from a queue, this makes ship rotation speed dependent upon the game’s frame rate. The real solution is to run this code in another thread in an infinite loop with a sleep timer to determine the speed of the rotation, however we are being quick and dirty here so we’ll casually ignore this problem for now. The game should not be so computationally intensive that the frame rate slows down anyway.

Download: Source code (.cpp) | Source code (.h) | Executable

15:12 – Break for lunch

I’m starving. I want BACON! Back soon.

16:19 – Lunch took longer than I realized. Let’s accelerate the ship

To allow the ship to accelerate, we give it a velocity vector which tracks the x and y movement speed of the ship. On each frame, the velocity vector is added to the ship’s position vector to get its new position. When you press the up arrow to make the ship accelerate, a normalized vector (magnitude of 1) representing the current direction of movement is added to the velocity vector, multiplied by a fixed scalar acceleration factor which lets us control how fast the ship should accelerate.

We could use polar co-ordinates to do this (two scalar values: an angle and a speed), but I have chosen to use Cartesian co-ordinates as described above (a vector). Both have their advantages and disadvantages. One of the great things about adding a vector with the direction of movement to the velocity vector is that adding two vectors pointing in the same direction increases the vector’s magnitude (“strength”), whereas adding vectors pointing in opposite directions cancel each other out. This allow us to simply code a very fluid ship movement.

// Accelerate the ship in the current direction
void Player::Accelerate()
{
	// Create a normalized vector in the direction of travel
	float xN = static_cast<float>(sin(2 * M_PI * (angle / 360)));
	float yN = static_cast<float>(cos(2 * M_PI * (angle / 360)));

	// Add to velocity vector (using minus for y because Direct2D uses 0,0 as the top-left corner instead of bottom-left)
	vX += xN * accFactor;
	vY -= yN * accFactor;
}

So far, the ship will continue to move indefinitely once it starts moving at all, until you accelerate in the opposite direction. Some Asteroids implementations are actually like this, however I prefer to bring the ship to a standstill if the accelerate key isn’t pressed for a while. Of course we can’t make the ship stop immediately when the user lets go of accelerate, it has to skid gradually to a stationary position. To do this we apply a per-frame deceleration (that is, acceleration in exactly the opposite direction of the velocity vector) which very loosely simulates air resistance.

For this I have used a simplified version of Stokes’ Law, which is appropriate for rigid bodies moving at relatively low speeds through fluid materials such as air or water. In Stokes’ Law, the rate of deceleration of a body is directly proportional to its velocity; in other words, the faster our ship is moving, the faster it will decelerate, which is exactly what we want. The amount of deceleration is chosen by a so-called drag co-efficient which is simply a constant scalar value which is multiplied to the velocity vector (and negated) to get the deceleration vector.

This might all sound complicated, but it isn’t:

// Update ship position
void Player::Update()
{
	// Update position based on movement speed (velocity vector)
	x += vX;
	y += vY;

	// Use Stokes' law to apply drag to the ship
	vX = vX - vX * dragFactor;
	vY = vY - vY * dragFactor;

	// Keep ship in game world (wrap-around borders)
	if (x < 0) x += renderer->ResolutionX;
	if (x >= renderer->ResolutionX) x -= renderer->ResolutionX;
	if (y < 0) y += renderer->ResolutionY;
	if (y >= renderer->ResolutionY) y -= renderer->ResolutionY;
}

Note that we apply the deceleration directly to the velocity vector so that on subsequent frames the movement of the ship becomes gradually less and less. It is not applied directly to the position of the ship as this would only give a fixed decrease in velocity that would be the same every frame.

We now have to address the problem of rendering the ship when it is partially off the edges or corners of the window. There are 8 possibilities and to ensure the ship doesn’t suddenly disappear and re-appear when its center point moves outside the rendering area, we have to render clones of the ship at the opposite edges or corners as follows:

// Draw the ship
void Player::Draw()
{
	Matrix shipLoc = shipGeometry.Rotate(angle, Geometry::PointCenter) * shipGeometry.Move(static_cast<int>(x), static_cast<int>(y));
	Paintbrush shipBrush = renderer->MakeBrush(Colour::White);

	// Draw the ship in its main position
	shipGeometry.Draw(shipLoc, Geometry::Center, shipBrush);

	// Check to see if any part of the bounding box is off the edge of the screen, in which case we want to render a wrapped copy too
	D2D1_RECT_F bounds = shipGeometry.GetBounds(shipLoc);

	// If the ship is partially beyond one edge...
	if (bounds.left < 0)
 		shipGeometry.Draw(shipLoc * shipGeometry.Move(renderer->ResolutionX, 0), Geometry::Center, shipBrush);

	if (bounds.right >= renderer->ResolutionX)
		shipGeometry.Draw(shipLoc * shipGeometry.Move(-renderer->ResolutionX, 0), Geometry::Center, shipBrush);

	if (bounds.top < 0)
 		shipGeometry.Draw(shipLoc * shipGeometry.Move(0, renderer->ResolutionY), Geometry::Center, shipBrush);

	if (bounds.bottom >= renderer->ResolutionY)
		shipGeometry.Draw(shipLoc * shipGeometry.Move(0, -renderer->ResolutionY), Geometry::Center, shipBrush);

	// If the ship is partially beyond two edges (corners)...
	if (bounds.left < 0 && bounds.top < 0)													// Top-left corner (redraw at bottom-right)
 		shipGeometry.Draw(shipLoc * shipGeometry.Move(renderer->ResolutionX, renderer->ResolutionY), Geometry::Center, shipBrush);

	if (bounds.right >= renderer->ResolutionX && bounds.top < 0)							// Top-right corner (redraw at bottom-left)
 		shipGeometry.Draw(shipLoc * shipGeometry.Move(-renderer->ResolutionX, renderer->ResolutionY), Geometry::Center, shipBrush);

	if (bounds.left < 0 && bounds.bottom >= renderer->ResolutionY)							// Bottom-left corner (redraw at top-right)
		shipGeometry.Draw(shipLoc * shipGeometry.Move(renderer->ResolutionX, -renderer->ResolutionY), Geometry::Center, shipBrush);

	if (bounds.right >= renderer->ResolutionX && bounds.bottom >= renderer->ResolutionY)	// Bottom-right corner (redraw at top-left)
		shipGeometry.Draw(shipLoc * shipGeometry.Move(-renderer->ResolutionX, -renderer->ResolutionY), Geometry::Center, shipBrush);
}

Note we use the rectangular bounding box of the ship after it has been rotated and positioned to determine whether copies must be drawn.

For reference, after some tinkering I chose the following values for ship movement:

• Rotational factor – 5.0
• Acceleration factor – 0.2
• Drag co-efficient – 0.02

Download: Source code (.cpp) | Source code (.h) | Executable

17:08 – Make asteroids

Since the game is written in an object-oriented way, we create an Asteroid class which is instanced one time for each asteroid in the game world. The asteroids are stored in a C++ standard library vector and initialized at the start of the game.

SimpleAsteroids::SimpleAsteroids()
{
	// Set up the player
	player = Player(this);

	// Set up the game
	SetResolution(800, 600);
	player.Reset();

	asteroids.clear();
	for (int i = 0; i < 3; i++)
		asteroids.push_back(Asteroid(this));
}

The description of the Asteroid class is remarkably similar to that of the ship, and once we start to see repeated code in the drawing, object updating, setup, pulldown functions and so on (as you will see in this version of the source code), and taking into consideration the shared characteristics and problems of each, together with the realization that bullets will also follow the same pattern, and this is a clear case for sub-classing, which I will perform as a re-factor in the next step.

class Asteroid
{
	// Pointer to renderer
	Simple2D *renderer;

	// The asteroid's center position in the game world
	float x, y;

	// The asteroid's current angle of rotation
	float angle;

	// The current velocity vector of the asteroid
	float vX, vY;

	// The rotation factor of the asteroid
	float rotFactor;

	// The asteroid geometry
	Geometry asteroidGeometry;

public:
	// Constructors
	Asteroid() {}
	Asteroid(Simple2D *r);

	// Update asteroid position
	void Update();

	// Draw the asteroid in the game world
	void Draw();

	// Return true if the asteroid is destroyed
	bool Remove();
};

The rendering problems of edge and corner detection are the same for asteroids as the ship, but I have not bothered to implement the fix in this version, instead I shall make a base class in the next version that handles it for all game objects.

The most interesting part about the asteroids is how to generate their initial shapes. The original Asteroids game uses shapes that are pre-defined but here I have gone for creating quasi-random geometric shapes dynamically. Here is the code:

// Create a new asteroid
Asteroid::Asteroid(Simple2D *r) : renderer(r)
{
	// Create asteroid geometry
	int minRadius = 30;
	int maxRadius = 50;
	int granularity = 20;
	int minVary = 25;
	int maxVary = 75;

	vector points;

	for (double ang = 0; ang < 2 * M_PI; ang += 2 * M_PI / granularity)
 	{
 		int angleVaryPc = SimpleAsteroids::Random(minVary, maxVary);
 		double angleVaryRadians = (2 * M_PI / granularity) * static_cast<double>(angleVaryPc) / 100;
 		double angleFinal = ang + angleVaryRadians - (M_PI / granularity);
 		int radius = SimpleAsteroids::Random(minRadius, maxRadius);
 		float x = static_cast<float>(sin(angleFinal) * radius);
 		float y = static_cast<float>(-cos(angleFinal) * radius);
 		points.push_back(D2D1::Point2F(x, y));
 	}

 	// Finalize asteroid geometry
 	GeometryData a = renderer->StartCreatePath(static_cast<int>(points[0].x), static_cast<int>(points[0].y), Geometry::Hollow);
	a->AddLines(&(*points.begin()), points.size() - 1);
	asteroidGeometry = renderer->EndCreatePath();

	// Set asteroid position, directional velocity and angular velocity
	x = SimpleAsteroids::Random(0, renderer->ResolutionX);
	y = SimpleAsteroids::Random(0, renderer->ResolutionY);
	angle = SimpleAsteroids::Random(0, 359);
	rotFactor = static_cast<float>(SimpleAsteroids::Random(0, 100)) / 100 - 0.5;
	vX = static_cast<float>(SimpleAsteroids::Random(0, 100)) / 100 - 0.5;
	vY = static_cast<float>(SimpleAsteroids::Random(0, 100)) / 100 - 0.5;
}

There are five variables at play here and tuning them can have dramatic effects on the appearance of the shapes generated (see screenshots below).

So how does it work? First we imagine each asteroid as a circle. Then we imagine a series of concentric circles inside and outside of this (ie. with radii both smaller and larger). We then want to deform (move) a number of points on our circular asteroid to intersect (lie on) one of the inner or outer concentric circles at random. We then join these points up with straight lines to form the final shape.

First we select how many points to deform with the granularity variable: the more points, the more geometrically complex the final shape will look. The values minRadius and maxRadius determine the smallest and largest possible radii of the imaginary concentric circles onto which points will be deformed. If these are the same, all of the asteroids will be circular; consequently, the more they differ, the more sharp and jagged the object will look.

While we pick precisely granularity points to deform, we do not necessarily want them to be evenly spaced along the circumference (an equal angle between each point on the circle). The variables minVary and maxVary have percentage values from 0-100 which choose how far the actual chosen point can deviate from the point that would have been chosen if they were all equidistant along the circumference (before deformation). 50 is half-way along the segment in which a point is being chosen to deform, and represents the equidistant point. Therefore if minVary and maxVary are both 50, all the points will be equidistant. Values of 0-49 represent anti-clockwise movement of the point and 51-100 represent clockwise movement. A chosen value of 100 on a given segment the same point as a chosen value of 0 on the next segment, and it is for this reason that 0 and 100 are not good choices for the two variables, as they can cause weird overlapping vertices (see the first screenshot below). The values shown above are the ones I eventually settled on after some trial and error.

The remainder of the code stores the geometry (joins the points together), and gives the asteroid random initial position, velocity, angle and rotational speed.

Asteroids with minRadius = 30, maxRadius = 50, granularity = 10, minVary = 0, maxVary = 100 – notice the unwanted vertex overlapping on the two right-hand asteroids caused by minVary and maxVary being too low and high respectively

Asteroids with minRadius = 20, maxRadius = 60, granularity = 30, minVary = 0, maxVary = 100 – these look more like explosions than asteroids

Asteroids with minRadius = 30, maxRadius = 50, granularity = 20, minVary = 25, maxVary = 75 – the final chosen values

Download: Source code (.cpp) | Source code (.h) | Executable

18:23 – Code churn

First of all I have re-factored the code as promised so Players, Asteroids and now Bullets all derive from GameWorldObject which handles all the motion updates and rendering (this probably took about 30 minutes).

I have also had to modify Simple2D to work with elliptical geometries for the circular bullet shape (this took about another 30 minutes).

The benefits of using OOP inheritance can be seen immediately:

void SimpleAsteroids::DrawScene()
{
	// Draw the game world objects
	for (auto it = worldObjects.begin(); it != worldObjects.end(); it++)
		it->Draw();
}

This draws the ship, the asteroids and any active bullets. Compare that to the carnage of SimpleTetris’s main drawing function.

Setting up the game now looks like this:

SimpleAsteroids::SimpleAsteroids()
{
	// New game world
	worldObjects.clear();

	// Set up the player
	player = new Player(this);
	worldObjects.push_back(player);
	player->Reset();

	// Set resolution
	SetResolution(800, 600);

	// Set up asteroids
	for (int i = 0; i < 3; i++)
		worldObjects.push_back(new Asteroid(this));
}

19:23-ish – Bullet Time

Bullets are essentially nothing more than small pieces of geometry that come into existence, moved at a fixed speed and direction for a while, then are removed from the scene. The duration a bullet can stay active without colliding with anything before it is removed is called its TTL or Time-To-Live (ironic eh?).

The actual bullet code is simple, in fact now we have GameWorldObject doing the dirty work, there is almost nothing to it:

// Create a new bullet
Bullet::Bullet(Simple2D *r, Player &p, float shipX, float shipY, float shipAngle) : GameWorldObject(r, r->MakeBrush(Colour::CornflowerBlue), 0.0f, 0.0f), player(p)
{
	// Create bullet geometry
	geometry = renderer->EllipseGeometry(1);

	// The direction of the bullet should be the direction in which the ship is facing
	vX = static_cast<float>(sin(2 * M_PI * (shipAngle / 360)));
	vY = static_cast<float>(-cos(2 * M_PI * (shipAngle / 360)));

	// The initial position of the bullet should be the ship's center point
	x = shipX;
	y = shipY;

	// Move the bullet along artificially a bit so it doesn't render inside the ship (we want it at the ship's front edge tip)
	x += vX * 20;
	y += vY * 20;

	// Bullet movement speed factor
	vX *= 5;
	vY *= 5;

	// No rotation or rotational speed
	angle = 0;
	rotationalSpeed = 0;

	// Bullet was created now
	createdTime = GetTickCount();

	// Bullet time-to-live
	ttl = 2000;
}

// Remove a bullet if its TTL has expired
bool Bullet::Remove()
{
	return (GetTickCount() - createdTime >= ttl);
}

To accommodate removal of items (and we can use this for the asteroids and ship too later), we make Remove virtual in GameWorldObject and alter the game object update code hence:

// Update game object positions
for (auto it = worldObjects.begin(); it != worldObjects.end(); it++)
	it->Update();

// Remove no longer needed objects
for (auto it = worldObjects.begin(); it != worldObjects.end(); it++)
	if (it->Remove())
	{
		worldObjects.erase(it);
		break;
	}

Note this is a bit fudgy: only one item at most will be removed per frame. Vector iterators become invalid when you delete something, and even naively resetting it to worldObjects.begin() inside the if block will trigger an exception (even if it worked that’s not a good idea for any sizable game by the way, because every single object in the game world will be iterated over again, possibly multiple times if there are several objects to remove). There is probably a lesson here about selecting the right container type in the first place (ie. one that has non-invalidating iterators on erase), but we don’t have time to be pedantic!

This is all well and good, but bullets have a few constraints on them that make things more tricky, namely:

1. When the player holds down fire we don’t want an insta-stream of bullets, there needs to be a gap between them.
2. As in classic Asteroids, there should be a maximum number of bullets on-screen at once.

To solve the first problem, we can think of firing like a spell in an RPG: once cast, the cooldown timer must expire before it can be cast again. The exception is if the user releases the fire button, then we want the cooldown to expire instantly so they can hammer the fire button to fire faster than if they just held it down – a mechanic traditionally found in these sorts of games.

The second problem is more subtle. As I mentioned earlier, I’m trying to keep all player-related data in the Player class so that it is easy to add multiplayer later. This means each Player object should have its own count of how many bullets have been used and when the last one was fired, and the main game logic class SimpleAsteroids shouldn’t know anything about it: it should simply figure out whose fire button has been pressed and ask that player’s object for a new bullet.

The issue with storing this per Player object is that we then have to consider whether we want the Bullets to belong to each Player or to the main class with all the other GameWorldObjects. The former is more logical, however it leads to then duplicating a bunch of object update and drawing code (for loops, at least). The latter keeps all rendering and physics iteration logic in one place, but necessitates that a Bullet has the ability to track which Player it belongs to (since the Players aren’t keeping a list of Bullets they own) so that when it expires it can inform that Player that one less bullet is now being used than before.

Clear as crystal, right? 🙂

Here is the code, first to check whether the fire button (space bar here) is pressed down or not:

void SimpleAsteroids::UpdateObjects()
{
...
	if (GetAsyncKeyState(' '))
	{
		Bullet *newBullet = player->Fire();

		if (newBullet)
			worldObjects.push_back(newBullet);
	}

	if (!GetAsyncKeyState(' '))
		player->ResetBulletCooldown();
}

When fire is pressed, we call it repeatedly (once per frame) until it isn’t:

// Fire a bullet
Bullet *Player::Fire()
{
	// Don't fire unless the cooldown period has expired
	if (GetTickCount() - lastBulletTime >= bulletCooldown)
	{
		// Don't fire if the maximum number of bullets are already on screen
		if (bulletsUsed < maxBullets)
		{
			// Make new bullet
			Bullet *bullet = new Bullet(renderer, *this, x, y, angle);

			// Last bullet fired now
			lastBulletTime = GetTickCount();
			bulletsUsed++;

			return bullet;
		}
	}
	return NULL;
}

…then we reset the cooldown when they let go:

// Reset cooldown (used when fire key is released)
void Player::ResetBulletCooldown()
{
	lastBulletTime = 0;
}

When the Bullet is removed from the list of objects in the game world, its destructor is called, which triggers a notification back to the ship that fired it to say that one less bullet is being used:

// Delete a bullet
Bullet::~Bullet()
{
	player.EndFire();
}
...
// Stop firing a bullet (called back when a Bullet object is destroyed)
void Player::EndFire()
{
	bulletsUsed = max(bulletsUsed - 1, 0);
}

Three things to note here. Firstly, I’m not a big fan of allocating dynamic memory and returning a pointer to it in the context I have used here. There are other ways to do it and I avoided this kind of thing in Tetris, it feels fragile to me, but, it does work for now.

Secondly, you may wonder why I used max instead of just subtracting one from bulletsUsed. Consider the scenario when you lose a life: the ship will be reset, including having its bulletsUsed changed to zero, but there may still be un-expired bullets on the screen. One solution is to remove them all, but I prefer to temporarily allow more than the maximum. The upshot of this is that when bullets expire very soon after the ship is reset, you would end up with a negative value for bulletsUsed without the max trick.

Thirdly, attention all you C++ newbies! You have to use a virtual destructor for the ~Bullet() code above, since it is stored as a pointer to GameWorldObject and if you don’t make the destructor virtual it won’t be called and your bulletsUsed counter will never go down! Be warned!

Bang bang!

Download: Source code (.cpp) | Source code (.h) | Executable

20:52 – It took me 30 minutes to blog that last section. I’m not even considering starting on collision detection til I’ve had some fresh air and a smoke.

Okay, we have about 95 minutes left to go in the challenge as I write. The collision detection between bullets and asteroids is done, and asteroids now have a Size flag which stores a number from 1 to 3 determining how big to make the asteroid. When an asteroid and a bullet collide, both are erased from the game world object list, and if the asteroid wasn’t the smallest possible version, two asteroids of the next smallest size are created, starting at the original asteroid’s position but with their velocity vectors orthogonal and multiplied so the two chunks fly off at right angles to the original direction of movement, and faster. Here is the game logic for this:

// Check for collisions
bool collision = false;

for (auto it = worldObjects.begin(); it != worldObjects.end(); it++)
{
	// Compare each bullet against each asteroid
	if (typeid(*it) == typeid(Bullet))
		for (auto it2 = worldObjects.begin(); it2 != worldObjects.end() && !collision; it2++)
			if (typeid(*it2) == typeid(Asteroid))
				if (it->IsCollision(*it2))
				{
					// Get asteroid object
					Asteroid &asteroid = *dynamic_cast<Asteroid *>(&(*it2));

					// Spawn two new asteroids if needed
					if (asteroid.Size < 3)
					{
						worldObjects.push_back(new Asteroid(this, asteroid.Size + 1, asteroid.GetX(), asteroid.GetY(), -asteroid.GetVY() * 2, asteroid.GetVX() * 2));
						worldObjects.push_back(new Asteroid(this, asteroid.Size + 1, asteroid.GetX(), asteroid.GetY(), asteroid.GetVY() * 2, -asteroid.GetVX() * 2));
					}

					// Kill asteroid
					worldObjects.erase(it2);

					// Kill bullet
					worldObjects.erase(it);

					collision = true;
					break;
				}

	if (collision)
		break;
}

Note that extra parameters have been added to Asteroid‘s constructor to enable the position and velocity to be pre-set.

But, as we see here, both the strengths and flaws of heterogeneous containers are highlighted. Yes, they made looping over everything easy when we didn’t need to know what the derived type was, but when we do, not only do things get messy with unwanted run-time type reflection, but in a larger game we could be iterating through thousands of objects we don’t want of the wrong type just to find a few that we do. Lesson: just because it was a good class hierarchy to have a basic game world object that everything else derives from, doesn’t necessarily mean that they should then all be stored in a single heterogeneous container when a family of homogenous containers may be better (and in this case probably is).

On the other hand, I have changed the game world object map from a ptr_vector to a ptr_list – this doesn’t invalidate any iterator on erase except that for the erased item, but more importantly it allows constant-time insertions and deletions in the list in exchange for sacrificing random access, which is a boon. YMMV.

I abstracted away collision detection between two pieces of geometry into my Simple2D library, so in Asteroids the only collision detection code is a meagre:

// Collision detection
bool GameWorldObject::IsCollision(GameWorldObject &o)
{
	Matrix loc1 = geometry.Rotate(angle, Geometry::PointCenter) * geometry.Move(static_cast<int>(x), static_cast<int>(y));
	Matrix loc2 = o.geometry.Rotate(o.angle, Geometry::PointCenter) * o.geometry.Move(static_cast<int>(o.x), static_cast<int>(o.y));

	return renderer->GeometryCollision(geometry, o.geometry, loc1, loc2);
}

In Simple2D itself, we have something like this:

bool Simple2D::GeometryCollision(Geometry &o1, Geometry &o2, Matrix &m1, Matrix &m2)
{
	D2D1_GEOMETRY_RELATION rel;

	ID2D1TransformedGeometry *t = o1.Transform(m1);
	HRESULT hr = t->CompareWithGeometry(o2.GetGeometry(), m2, &rel);
	SafeRelease(&t);

	return (hr == S_OK && rel != D2D1_GEOMETRY_RELATION_DISJOINT);
}

and:

// NOTE: It is the responsibility of the application to free this geometry!
// Should generally be for internal use only
ID2D1TransformedGeometry *Geometry::Transform(Matrix &transform, Geometry::DrawStart relPos, FLOAT strokeWidth, ID2D1StrokeStyle *strokeStyle)
{
	ID2D1TransformedGeometry *t;
	D2D1_MATRIX_3X2_F fullTransform;

	D2D1_RECT_F bounds = GetBounds(strokeWidth, strokeStyle);

	if (relPos == Default)
		fullTransform = transform;

	else if (relPos == TopLeft)
		fullTransform = transform * D2D1::Matrix3x2F::Translation(-bounds.left, -bounds.top);

	else if (relPos == Center)
		fullTransform = transform * D2D1::Matrix3x2F::Translation((bounds.left - bounds.right) / 2 - bounds.left, (bounds.top - bounds.bottom) / 2 - bounds.top);

	renderer->Direct2D->CreateTransformedGeometry(GetGeometry(), fullTransform, &t);

	return t;
}

and:

D2D1_RECT_F Geometry::GetBounds(Matrix &transform, FLOAT strokeWidth, ID2D1StrokeStyle *strokeStyle)
{
	D2D1_MATRIX_3X2_F wt;
	renderer->Screen->GetTransform(&wt);

	D2D1_RECT_F bounds;
	if (fillType == Filled)
		geom->GetBounds(transform * wt, &bounds);
	else
		geom->GetWidenedBounds(strokeWidth, strokeStyle, transform * wt, &bounds);

	return bounds;
}

Note that these various transforms relative to the objects, game world co-ordinates and render target have to be done before using Direct2D’s CompareWithGeometry interface bceause the geometries themselves are stored unrotated, unscaled and untranslated in our Asteroids code – the transformations are only applied at render time, so we have to repeat them for off-screen use when performing the collision detection.

Download: Source code (.cpp) | Source code (.h) | Executable

22:38 – Don’t kill the compiler, kill the player.

45 minutes left as I write (23:15).

Collision with the ship and the asteroids basically works the same as collisions between bullets and asteroids – a smart and sly reason to use Direct2D geometries for everything instead of just points or little circles for the bullets which would have to be handled differently.

A few things have to happen when the ship is hit by an asteroid:

The ship must disappear from the game world temporarily. In some implementations the asteroid also gets destroyed (or split into two smaller chunks where applicable) but I have not gone for that approach tonight due to the obvious time constraints.

You must lose one life. Therefore we need to add in a system that gives some lives in the first place. Once again we will tie this with the ship and not to the core game, so that in a multiplayer scenario each player can have a different number of lives remaining.

If there are no lives left, the game must stop. This means we have to alter the part of the game that updates all the objects and checks for keypresses to only do so if the game is still in progress.

After a short interval, the ship should re-appear in the middle in its default orientation and not moving.

This update includes all of these things. A state flag is kept to check for the game over condition and is updated whenever the player loses a life. A basic scoring system is also added whereby you get 10 points for shooting a big asteroid, 50 for a medium-sized one and 100 for a small one. We also need to render an overlay showing the player’s lives and score of course.

I won’t go over all the small details as much of the code is fairly trivial, but here is how the high-level game logic looks now for asteroid/bullet and asteroid/player collisions:

// Check for collisions
bool collision = false;

for (auto it = worldObjects.begin(); it != worldObjects.end(); it++)
{
	// Compare each bullet against each asteroid
	if (typeid(*it) == typeid(Bullet))
		for (auto it2 = worldObjects.begin(); it2 != worldObjects.end(); it2++)
			if (typeid(*it2) == typeid(Asteroid))
				if (it->IsCollision(*it2))
				{
					// Get asteroid object
					Asteroid &asteroid = *dynamic_cast<Asteroid *>(&(*it2));

					// Spawn two new asteroids if needed
					if (asteroid.Size < 3)
 					{
 						worldObjects.push_back(new Asteroid(this, asteroid.Size + 1, asteroid.GetX(), asteroid.GetY(), -asteroid.GetVY() * 2, asteroid.GetVX() * 2));
 						worldObjects.push_back(new Asteroid(this, asteroid.Size + 1, asteroid.GetX(), asteroid.GetY(), asteroid.GetVY() * 2, -asteroid.GetVX() * 2));
 					}

 					// Update score
 					switch (asteroid.Size) {
 						case 1: player->Score += 10; break;
						case 2: player->Score += 50; break;
						case 3: player->Score += 100; break;
					}

					// Kill asteroid
					worldObjects.erase(it2);

					// Kill bullet
					worldObjects.erase(it);

					collision = true;
					break;
				}

	// Compare ship against each asteroid
	if (!collision)
		if (typeid(*it) == typeid(Player))
			for (auto it2 = worldObjects.begin(); it2 != worldObjects.end(); it2++)
				if (typeid(*it2) == typeid(Asteroid))
					if (it->IsCollision(*it2))
					{
						// Kill player
						it->MakeInactiveFor(1000);

						// If they had no lives left, it's game over
						if (!player->Lives)
							gameOver = true;
					}

	if (collision)
		break;
}

The most interesting part about this iteration is how the inactivity of the ship between death and re-spawning is handled. You can’t simply erase the ship from the game world as the object map is retaining the only pointer to it, plus the Player object which controls the ship also stores the number of lives that ship has remaining. Instead, we want to simply “turn it off” for a period of time, and MakeInactiveFor() initiates a simple timer which does exactly that. Upon re-activation, the virtual function Reset() is called so any object that is temporarily removed can be re-positioned etc. as desired. Only the ship uses this for the moment, of course. Let’s have a look at the code:

// Make inactive for X ms
void GameWorldObject::MakeInactiveFor(int x)
{
	active = false;
	reactivateTime = GetTickCount() + x;
}

And in the physics update code:

// Update game world object position
void GameWorldObject::Update()
{
	// Re-activate if the inactive timer has expired
	if (!active)
	{
		if (GetTickCount() < reactivateTime)
			return;

		active = true;

		// Set up object position, speed etc.
		Reset();
	}
...

The drawing and collision detection functions are modified to do nothing if the object is currently inactive. The only change to Reset() in the ship code from before is that the number of lives remaining is decremented each time it is called.

So far so good, but when you destroy all the asteroids you’re now just left with a ship and a blank screen! Plus, what if you re-spawn while there is an asteroid in the middle of the screen? You’ll die instantly. These are the remaining two problems to address in the challenge.

Download: Source code (.cpp) | Source code (.h) | Executable

23:28 – Waves and Shields

In Asteroids the player can usually press a key to activated a time-limited shield which then becomes unusable until its cooldown timer has expired. For this we need to add some bits and pieces to our Player object:

private:
	// Currently invincible
	bool invincibility;

	// Time invincibility lasts (ms)
	unsigned int shieldDuration;

	// Minimum time between each shield use (ms)
	unsigned int shieldCooldown;

	// Time shield was last used
	unsigned int lastShieldTime;
...
public:
	// Update movement, status etc.
	virtual void Update();

	// Activate invincibility if cooldown has passed
	void ActivateShield();

	// Return true if player is currently invincible
	bool IsInvincible() { return invincibility; }

We set the default values in Player‘s constructor, and turn the shields on each time the player loses a life and when the game starts in the Reset() function:

// Make invincible
invincibility = true;
lastShieldTime = GetTickCount();

We override the virtual Update() function in GameWorldObject to update the shield status each frame:

// Update player status
void Player::Update()
{
	// Update shield flag
	invincibility = (GetTickCount() - lastShieldTime) < shieldDuration;

	// Do normal update
	GameWorldObject::Update();
}

Note the call to the base function at the end to ensure the ship’s speed and position is still updated.

When the player presses a certain key, we activate the shield if it isn’t already activated, and if the cooldown time has passed:

if (GetAsyncKeyState(VK_SHIFT))
	player->ActivateShield();

...

// Try to activate shield
void Player::ActivateShield()
{
	if (GetTickCount() - lastShieldTime > shieldCooldown && !invincibility)
	{
		invincibility = true;
		lastShieldTime = GetTickCount();
	}
}

To actually make the shields work requires an extremely simple change to one line, where the check for collision against all the asteroids starts:

// Compare ship against each asteroid unless player is invincible
if (!collision && !player->IsInvincible())
    ...

Finally, in the drawing function, we just draw a circle round the ship if the shields are on:

// Draw a circle around the ship if currently invincible (shields)
if (active && invincibility)
	renderer->DrawRoundedRectangleWH(static_cast<int>(x) - 30, static_cast<int>(y) - 30, 60, 60, 30, 30, Colour::Red);

Creating levels (waves) is pretty simple too. We just store a level variable in the main game class and create a function to make each new wave:

SimpleAsteroids::SimpleAsteroids()
{
...
	// Wave 1
	level = 1;
	CreateNewWave();
}

void SimpleAsteroids::CreateNewWave()
{
	// Set up asteroids (2 plus the level number)
	for (int i = 0; i < level + 2; i++)
		worldObjects.push_back(new Asteroid(this));
}

Each frame we count how many asteroids are left and if the count falls to zero, we advance to the next wave (ideally this should have been done only on frames where an asteroid is destroyed, for efficiency):

// Count how many asterids are left. If zero, advance to the next wave
int asteroidCount = 0;

for (auto it = worldObjects.begin(); it != worldObjects.end(); it++)
	if (typeid(*it) == typeid(Asteroid))
		asteroidCount++;

if (!asteroidCount)
{
	level++;
	CreateNewWave();
}

Note once again that this for loop is a hideously bad way for checking how many asteroids are left, a result of poor design, and again indicates that a family of homogeneous containers would have been better than a single heterogeneous one – or alternatively, that we should keep a separate variable with a running count of how many asteroids are left and only update it when an asteroid is destroyed or a new one spawned.

00:00 – DONE!!!

Yowzer that was what we call cutting it fine. VERY fine.

Download: Source code (.cpp) | Source code (.h) | Executable

And there we have it, a fully functioning Asteroids game coded in one day. Enjoy!