Test Driving an algorithm is a tricky thing. Developers tend to get stuck in one of two ways:
- They see that they have the algorithm from Wikipedia, Stack Overflow, or a book, and don’t understand why they would write tests.
- Once they see the algorithm, they lose the ability to break it down. Commonly they’ll write the entire algorithm on the first or second test.
In case you haven’t already guessed, I don’t think it’s a good idea to skip the tests even when you know the algorithm, and I thought I’d demonstrate by test-driving a game loop.
The Game Loop
This isn’t an article on the Game Loop1, so I will try to be brief. Unlike many applications, video games don’t wait for user input to execute. Instead, they typically run in a loop, updating the state of the objects in the system and then drawing them to the screen. A very simple, and broken, game loop might look like this:
while (true) {
processInput();
update();
render();
}
The problem with the one up there is that it will run as fast as the machine it’s running on, which means that if your video game has a spinning hedgehog, that hedgehog will go faster on fast machines and slower on slow machines. Suddenly you’ll need to buy a crummy computer to get past the boss levels. The Game Loop we’ll be implementing looks like this:
double previous = getCurrentTime();
double lag = 0.0;
while (true) {
double current = getCurrentTime();
double elapsed = current - previous;
previous = current;
lag += elapsed;
processInput();
while (lag >= MS_PER_UPDATE) {
update();
lag -= MS_PER_UPDATE;
}
render();
}
This loop2 fixes the updates at a given rate (MS_PER_UPDATE) while allowing the render to occur as fast as possible. In the event that an update takes too long, we’ll catch up by running extra updates. This style of loop is common in many games, and will work well enough for our purposes.
Test Driving It
When Test Driving an algorithm you already know, the temptation is to copy-paste the algorithm into your code and then try to write tests around it. Doing so removes the design feedback that tests provide, and is likely to produce subtle holes in your tests. Instead, you’ll want to break it down into the various test cases. When looking at the above loop, the first thing I notice is this:
double previous = getCurrentTime();
double lag = 0.0;
while (true) {
// Your code goes here
}
Ignore the setting of the time for the moment—that’s just there for context—and let’s focus on the while(true). The pseudocode uses that to emphasize that the loop is infinite, but it’s really not. We really want to quit the game when it’s over. So with that in mind, I wrote my first test:
using System;
using NUnit.Framework;
namespace MyGame
{
[TestFixture]
public class GameLoopTest
{
[Test]
public void ItDoesNothingWhenTheGameIsStopped()
{
var game = new TestGame();
game.Running = false;
var gameLoop = new GameLoop(game);
gameLoop.Run();
Assert.IsFalse(game.Updated);
}
}
}
I’m using C# for this example because I think its syntax should be recognizable by pretty much any developer without too much explanation, and because it should annoy most of my Mac-loving co-workers. I wrote it in Xamarin on OSX because I don’t like using Visual Studio or Windows, which should annoy everybody else. Trolling complete.
I’ve called this my first failing test, but that’s not entirely accurate. Remember rule two of TDD:
“You are not allowed to write any more of a unit test than is sufficient to fail; and compilation failures are failures.”3
One of the advantages of using a compiled language is that you can see compiler errors the instant you type them in the IDE. When writing C# I use that to my advantage by creating each class/property/method/etc. the instant my IDE identifies them as a failure, rather than waiting until my test is complete. Since I know the algorithm and will be tempted to write the whole thing to pass one test, I follow my rules more pedantically than I might otherwise. After writing this test I have this code:
namespace MyGame
{
public class GameLoop
{
public GameLoop(Game game)
{
}
public void Run()
{
throw new NotImplementedException();
}
}
}
Upon review, and in spite of my desire to be pedantic, I realize that I’ve passed in the Game4 object to the constructor even though I don’t need it yet. Let’s see what it takes to make this test pass:
public void Run()
{
}
Oh hell. I’ve written an awful lot of code to make sure I do...nothing. I’m not reproducing it here, but I’ve also written an interface and a TestGame class that the GameLoop operates on. That TestGame has to have a Running property. Why write that much code to do nothing? Because I’ve already done some design. I’ve separated out the Game—which could be anything from Asteroids to Assassin’s Creed 92: Still Stuck in The Tube. In addition, I like writing the do-nothing cases first, because I can make sure those continue to pass as I write more tests.
Now we need a test that passes, so I suppose we should write one that forces us to do something:
[Test]
public void ItRunsUpdateOnceBeforeTheGameIsStopped()
{
var game = new TestGame
{
Running = true
};
var gameLoop = new GameLoop(game);
gameLoop.Run();
Assert.IsTrue(game.Updated);
}
The only real difference is that this game is running. Getting the test to pass is really simple:
public void Run()
{
if (Game.Running)
{
Game.Update();
}
}
If you compare our loop so far to the one in the pseudocode, you’ll see that we are far away from complete, but we are also diverging already. The described algorithm is written using a structured style, and as such would be extremely difficult to test or decouple from our actual game. By beginning with tests, we are pushed to start with an object-oriented solution.
At this point I should point out that I wrote this algorithm in one try. It’s not rehearsed or perfect, and you’ll see it as the tests change. With that said let’s see the next test:
[Test]
public void ItUpdatesUntilTheGameIsStopped()
{
var game = new TestGame();
var queue = new Queue<bool>();
queue.Enqueue(true);
queue.Enqueue(true);
queue.Enqueue(false);
game.RunningDelegate = () => {
return queue.Dequeue();
};
var gameLoop = new GameLoop(game);
gameLoop.Run();
Assert.AreEqual(2, game.UpdateCount);
}
As you probably already realized, our game loop doesn’t do any looping yet. This means our TestGame is gonna need to be able to return a list of values for Running. The first times through we’ll want to say we are running, then end with a false. Before you say there’s no test that does “true, false” for the running value, let’s look at an updated version of the second test:
[Test]
public void ItRunsUpdateOnceBeforeTheGameIsStopped()
{
var game = new TestGame();
var queue = new Queue<bool>();
queue.Enqueue(true);
queue.Enqueue(false);
game.RunningDelegate = () => {
return queue.Dequeue();
};
var gameLoop = new GameLoop(game);
gameLoop.Run();
Assert.IsTrue(game.Updated);
}
Simply returning true isn’t suitable anymore, I have to queue up the answers so that I eventually return false. It’s important to note that I changed all three tests to queue up the running “state” before modifying the production code. In this way I saw two passing tests and a third that failed, as I should, without running into an infinite loop.
Before I continue showing the test passing, it’s probably worth explaining what TestGame is. It’s easy to get confused here, we’re testing the game loop but the game itself is an abstraction. Any class can be a game if it implements Update and Running. Here is the interface (thus far):
public interface Game {
bool Running { get; }
void Update();
}
The Test class looks like this:
public class TestGame : Game
{
public TestGame()
{
UpdateCount = 0;
}
public bool Running { get { return RunningDelegate(); } }
public Func<bool> RunningDelegate { private get; set; }
public int UpdateCount { get; set; }
public bool Updated { get; set; }
public void Update()
{
Updated = true;
UpdateCount++;
}
}
As you can see, TestGame is pretty dumb. It returns the count of Updates and will return the return value from its RunningDelegate when you ask if it’s Running. Experienced TDD folks might be wondering why I’m not using a mocking framework like NSubstitue or Rhino Mocks or Moq or MSFakes... The point is that there are so many frameworks and syntaxes for those frameworks that for this example, it’s simpler to roll my own mock objects. In many cases it’s truly easier for me to do this in code that isn’t for teaching as well, as I’m now creating a template for what an example Game class might look like.
Returning to our architecture, we are testing a Game Loop, not a Game object, and we’ve decoupled the two things. This will pay huge benefits later when we can test our game objects outside the context of a game loop. Let’s finally make our third test pass:
public void Run()
{
while (Game.Running)
{
Game.Update();
}
}
Wow. We have written a lot of code to get to a while loop that doesn’t draw. It’s a fair criticism, but it’s code that will enhance my understanding of the game loop. Imagine you are using a game loop from a framework—you would probably write a little code to see how it works. I've already written something very much like the TestGame class.
Speaking of there not being a draw, let’s add draw:
[Test]
public void ItRunsADrawAfterUpdate()
{
var game = new TestGame();
var queue = new Queue<bool>();
queue.Enqueue(true);
queue.Enqueue(false);
game.RunningDelegate = () => {
return queue.Dequeue();
};
var gameLoop = new GameLoop(game);
gameLoop.Run();
Assert.AreEqual(1, game.DrawCount);
}
Interestingly, this test doesn’t address order, and order is important here. If we look back at the original pseudocode, we know that Update comes before Draw, and we know that happens so that the player isn’t seeing everything one frame too late. This case is rare enough that sometimes mocking frameworks don’t even support this order test, but I can embed it into my test game.
public void Draw()
{
if (DrawCount != UpdateCount - 1)
throw new InvalidDrawException();
DrawCount++;
}
The InvalidDrawException inherits from Exception, so we’ll get a clean error in the event that a draw came too early. This means this passes:
while (Game.Running)
{
Game.Update();
Game.Draw();
}
but this fails:
while (Game.Running)
{
Game.Draw();
Game.Update();
}
This means we now have a functioning game loop, provided we don’t want any input. That doesn’t sound like a fun game. In the next post, we’ll add input and fixed-step updates to the loop, then evaluate our solution. If you want to cheat ahead and see the code, take a look at it on github.
1 For an excellent article on Game Loops, see http://gameprogrammingpatterns.com/game-loop.html.
2 This loop is also taken from http://gameprogrammingpatterns.com/game-loop.html.
3 http://butunclebob.com/ArticleS.UncleBob.TheThreeRulesOfTdd.
4Game is an interface. I don’t prefix my interfaces with “I” because an interface is an abstraction, and the naming should be more generic than the implementation, so you won’t see GameImpl either.
