Archive for June, 2007
The Traveling Biologist Problem
cubed2D
June 06th, 2007.
Today i check my email and found a list of end of term challenge questions sent to us by our programming lecturer. Naturally, the traveling salesman was one of the challenges. I’ve never implemented a solution to it before, so I thought id give it a shot. I remembered reading an article on implementing a genetic algorithm to solve it, so I decided to give it a shot. I’m half way through at the moment and its brilliant fun! Anyone interested in AI and GA should give it a shot! only problem is that it has to be in java. I keep writing c# syntax!
ahh well, if it goes well I might post it! wish me luck.
Adventures in Pefromance 2: Profiling
cubed2D
June 05th, 2007.
Well, I’ve finished all my exams at uni now, so its back to playing around with XNA! Its high time for an article again, so I’m going to finish up my performance article I started weeks ago. During my first stab at performance monitering code, I wanted to include an in game profiler but I didn’t have enough time to try and implement one. Things are different now!
First of, whats a profiler? A profiler is a tool that can tell you what your code is actualy doing. It tells you how much time it spends in each piece of code. You can get external programs which can profile your .Net application. So why bother writing our own? because games are different to office applications! We want to know what our game is doing frame by frame. External profilers will sample your game application over a few seconds and tell you what happend over thoese seconds, we want to know what happend on a frame by frame basis.
So, what should the profiler be? The profiler component should collect every imaginable piece of data about how the game is currently running, it should include stuff we might want accessible in any game build (I always like to have FPS and Frame Time easily accessible in pc games) and stuff we might want to use in ‘profiling’ builds, like a print out of exactly which pieces of code are being called, how many times they get called and how they relate to another (execution hierarchy). Basically I want to be able to get code to compile into a build of my game which will print out what my game is doing.
How will the profiler know a piece of code is starting and stopping its execution? The constructor for the class registers all the counters to be used in that class and gets id numbers for each performance check, and then at the beginning and end of each method we want to measure we check in and out with the profiler. The code to do all this can be shoved inside a #IF statement so it only gets compiled in if we want a profile build. This means normal release and debug builds are not affected by the new code, and hopefully it will have a small enough footprint not to change the characteristics of the code too much when it is compled in. Is it just me or does this seem far too simple?
As it turns out, yes. Recently I’d been browsing Amazon for some game programming books to buy, and I remembered that some volumes of Game Programming Gems had articles on this very subject listed in their indeces. One quick check of the Durham University library website revelaed that they did in fact have all the books in the main library, on the 4th floor in the fine arts section for some odd reason, and the articles in the first two volumes of the books confirmed my suspicions. It really is that easy… if you have a good clock. The implementation I present to you implements some ideas from the articles mashed in with what I had been working on before I read them.
So first we tackle the problem of a clock. why not use XNAs gameTime I hear you ask? It’s not high res enough! That may sound silly, but gameTime only gives us millisecond resolution. We need a better clock. As discussed earlier, we need to draw every frame in about 16 miliseconds in order to get 60 fps. so we need a clock that can tell us the time in much smaller units than that in order to measure how long it takes each part of the update and drawing cycle to run. At the worst we want a clock that updates every 1 millisecond, better would be microsecond, jackpot would be nanoseconds (its not just how low it goes, but how quickly it updates, theres no point if it can tell us the time in nanoseconds if we can only read it every 4 milliseconds!).
Lucky for us System.Diagnostics.Stopwatch exists (it should work on the xbox as well but I haven’t tested it myself). This is a good and proper high res clock. I wrote a small test app to test it out, you can grab it here. from what I gather it is hardware dependant, so I built this test app and bullied a few people into running it, and the news is good: it doesn’t seem to differ much at all! Stopwatch has a base frequency, which is how many times the clock ticks a second. So the first test was to check if the frequency of the ticks was at all constant over different processors. I managed to test it on two different athlon 64, athlon 64 mobile, celeron m, PIII and an intel T2300. All of the had the same frequency of 3579545 ticks a second, which equates to about 1 tick every 279 nano seconds!
The second part of the test sees how quickly we can access the clock. I did this with a simple loop:
watch.Start();
for (int i = 0; i < 10000; i++)
{
 nano[i] = watch.ElapsedTicks;
}
watch.Stop();
 We just check the elapsed ticks 10,000 times and put the elapsed time into an array. I then found out the average time between the checks and it turned out to be about 5 ticks between every check, giving 1395 ns or 1.3 microsecond. Why did I do all this? Just to prove to myself that I was able to get a good reading from the clock. It’s unrealistic to presume we can check the clock every tick. Seeing as 1.3 microseconds is a good estimate for the smallest unit of time we can grab from the clock, and its allot smaller that 16 miliseconds, Stopwatch has passed the test and we can use it to time our game loop and hopefully I’ve proved to you that its quick enough for the task!
Just to let you know now, I won’t release the code for this componet myself, as what I have at the moment was written very quickly and is not fit to be released, but if you ask I’ll redo it and post it. Instead im going to describe how to implement a profiler. I decided to use performanceMan as a base for this component. First I cleaned up the code, pulling out all the unnecessary things in it so it just handled gametime and fps and printed it to the screen, no more GUI. Next up was adding an instance of stopwatch to the class and instancing it in the constructor. Now, one of the problems we wanted to tackle is if were not running a profiling build, we don’t even want the profile code to compile in to the game, we don’t want it there at all! How do we manage this? All the code to do with profiler we put in a #if preprocessor block. for example, this is what I have in my constructor.
#if profile
              watch = new System.Diagnostics.Stopwatch();
              watch.Start();
               nanosecondsPerTick = 1000000000 /System.Diagnostics.Stopwatch.Frequency; //1 tick in nanoseconds
#endif
Now we need to tell Visual Studio how to build a profile build of our game. On the drop down box where you can select ‘debug’ or ‘release’ choose configuration manager. In here you can make a new configuration, call it profile and tell it to copy settings from release. This way we wont have the debug features in the profile build, but from my experience when you profile you game, you’re not checking for bugs, you’re finding out where it spends its time, so you want it to run as fast as possible. Next you have to open your project properties and go to the build tab and set the configuration to profile. In the ‘conditional compilation symbols’ box add ‘profile’. This lets us use profile as the switch in the preprocessor if’s.
Next we need an object to represent each counter. We can use a class because garbage should not be an problem here as we don’t allocate and deallocate loads of these every frame, we tend to keep our counters for the whole life cycle of the game. Now, what do we need to track in a counter? We definetly need to keep some identifiers, a string for the name of the counter and an integer to hold its id number. We also need some fields to hold the frame by frame action. Something like the following shall suffice.
public int calls; // number of times this counter has been used this frame
public bool open; // is this counter running
public long startTick; // the tick we started this counter on
public long accumulatedTicks; // ammount of ticks we have run this counter for this frame
So, the idea here is when we start a timer, we check if the counter is already open. If it is, throw an error or something. We only want each counter to be running once. If it’s free, we set open to false, increment calls and set startTick to ElapsedTicks (which we get from the stopwatch). When we finish the code and stop the counter, first we grab the current ElaspsedTicks and take away the start ticks, the remainder is the amount of ticks the code took to run. Add this to accumulatedTicks, oh and set open to close.
If we run a piece of code over and over, the calls stack up and the accumulatedTicks holds the combined time that the counter has been running, so we need some variables to handle some basic statistics. I decided to keep track of high and low points and the average running time over a frame. If we had 12 enemies in our game, there update code will run 12 times and obviously calls would be 12, so if we divide the accumulatedTicks by calls we get the amount of time (in ticks) it took on average for each update cycle to run, which is a good stat to print. We can also then test this against a variable holding the shortest and longest time it took to run, and update as appropriate. Remember before you draw them to multiply the number of tics by nanosecondsPerTick to get the amount of nanoseconds that passed. your probably then going to end up with some silly big times though, so you can divide you time in nanoseconds by 1000 to get it in microseconds or by 1000000 to get it in milliseconds. a simple if statement in your drawing code to decided which division to use and what unit to print will help, too. The last thing you should track in each counter is an integer to hold the id of a parent counter. In this we will store the id the counter that contains this counter.
 This allows us to print out counters in the correct order, as seen in this image (the nuber in the brackets is the id for each counter). I’ll describe how this works in a bit!
Ok so far we have a profiler class that has a stopwatch and keeps track of the fps and frametime, and a class to represnt a counter. We need to add the profiler logic to our profiler class, and define a interface for it to use so we can use it as a global service. Let’s look at the interface first.
interface Iprofile
{
       int AddCounter(string counterName);
        int GetCounterID(string counterName);
        void DeleteCounter(int id);
        void UnDeleteCounter(int id);
        void StartCounting(int counter);
        void StopCounting(int counter);
        string EndOfFrame();
}Anything of note here? Not really, everything acts as expected. Ive already discussed what start and stop counting do, add and get counter act as you would imagine. DeleteCounter doesn’t delete a counter, rather moves it to a different list of counters. This allows you to change the behavior of the profiler as it runs. You can stop a counter from being updated (start and stop should fail silently) so you can change the depth of the profiling as you want. undelete simply puts the counter back in the active counters list. Now, back to the relationship thing! We need a third list of counters, every time startCouning is called a counter is added to the runningCounters list. If there are any other counters in the list, the one at the top is assigned the parent of the new counter. StopCounting removes a counter from the running list aswell. This allows EndOfFrame to do its job. The draw method for the profiler calls EndOfFrame to gather all the information from the counters and format it in to a string. We have allread discussed most of its job so I won’t reiterate it, the only thing left to tackle what it does with related counters. First it iterates through the list counters for one which doesn’t have a parent. It adds this to the string first, then it looks for one that has the current counter as a parent. It now adds this one to the string (spritebatch.DrawString will use \n to draw on a new line, so remember to add them!). it keeps running through the list of counters, finding the children, adding to the list, fining the next parent and so on till all the counters are in the string, at which point we return it. Doing it like this puts the counters in the correct order, so AI update in the previous example would sort under update. It’s a good idea to add an indent to the children so you can see they are children. Format the output string like a table and it should be fairly pleasing to the eye.
As you can see, IÂ have some work to do on the output. The units are currently mixed up (average is in microseconds, the min and max are in miliseconds) and the table doesn’t line up stably, but it does demonstrate what we’re after. It doesn’t seem to have any effect on performance either, so that’s all good!
Well, there you have it, a description of how to implement a Profiler into your game. As it stands some things could be tweaked here and there, I’ve hardly touched on error detection, it won’t work with recursive methods and there are probably hundreds of ways you can tweak it to work better with your game. Well, have fun adding one to your game engine, and tell me how it goes!