Lag: The Bane Of Touch Screens

Lag in games is as inevitable as taxes. It’s something we can try to minimize, but we always need to live with it. Earlier this week, I noticed that input for my new iPad game was very laggy. Excessively so, to the point it was really detracting from the game, so I decided I had to look into it a bit more.

Lag In Games

got_lag.pngI’m defining lag as the time elapsed between the moment the player performs an input action (press a button, touch the screen, move his finger), until the game provides some feedback for that input (movement, flash behind a button, sound effect).

Mick West wrote a great article on the causes of lag in games, followed up by another one in how to measure it. I’m going to apply some of that to the lag I was experiencing in my game.

Lag can be introduced in games by many different factors:

  • Delay between gathering input and delivering it to the game.
  • Delay updating the simulation to reflect new inputs.

  • Delay rendering simulation state.
  • Delay displaying the latest rendered state on screen.

The new game runs on the iPad and involves moving objects around the screen with your finger. To make sure it wasn’t anything weird with the rest of the game code, I wrote a quick (and ugly!) program that draws a square with OpenGL that follows your finger on the screen. When you run the sample, the same lag becomes immediately obvious.

The iPad is a much larger device than the iPhone, and it encourages a physical metaphor even more. As soon as you attempt to move an “object” on screen, the lag kills that sense of physicality. Instead of moving an object around with your finger, you’re dragging it around with a rubber band. It moved the player from applying direct action on screen, to being removed and disassociated with the actions on screen.

Loop Structure

The place to start looking for lag is in my main loop. The main loop looks something like this:

	ProcessInput();
	UpdateSimulation();
	RenderWorld();
	PresentRenderBuffer();

So I was reading the input correctly before the simulation. Nothing weird there.

Touch input is delivered to the code as events from the OS. Whenever I received those events (outside of the main loop), I queue them, and then process them all whenever the main loop starts in ProcessInput().

The loop runs at 60Hz, so the lag here is at most 16.7 ms (if you’re running at 30Hz, then you’re looking at a delay up to 33.3ms). Unfortunately, the lag I was seeing in the game was way more than one frame, so there was to be something else.

Rendering

For some reason, I thought that iDevices were triple buffered. I ran some tests and fortunately it looks like it’s regular double buffering. That means that if I render a frame and call presentRenderBuffer(), the results of that render will be visible on screen at the next vertical sync interval. I’m sure there’s a slight lag with the iPad screen, but I’m willing to be is close to negligible when we’re talking about milliseconds, so we’ll call that zero.

Main Loop Calls

The game uses CADisplayLink with interval of 1, so the main loop is called once every 16.7 ms (give or take a fraction of ms). I thought that perhaps CADisplayLink wasn’t playing well with touch events, so I tried switching to NSTimer, and even to my old thread-driven main loop, but none of it seemed to make any difference. Lag was alive and well as always.

That the simulation and rendering in the game are very fast, probably just a few ms. That means the rest of the system has plenty of time to process events. If I had a full main loop, maybe one of the two other approaches would have made a difference.

It looks like the lag source had to be further upstream.

Input Processing

On the dashboard, press and hold on an icon, now move it around the screen. That’s the same kind of lag we have in the sample program! That’s not encouraging.

A touch screen works as a big matrix of touch sensors. The Apple OS processes that input grid and tries to make sense out of it by figuring out where the touches are. The iOS functions eventually process that grid, and send our programs the familiar touchesBegan, touchesMoved, etc events. That’s not easy task by any means. It’s certainly not like processing mouse input, which is discrete and very clearly defined. For example, you can put your whole palm down on the screen. Where are the touches exactly?

TouchesBegan is actually a reasonably easy one. That’s why you see very little lag associated with that one. Sensors go from having no touch values, to going over a certain threshold. I’m sure that as soon as one or two of them cross that threshold, the OS identifies that as a touch and sends up the began event.

TouchesMoved is a lot more problematic. What constitutes a touch moving? You need to detect the area in the sensor grid that is activated, and you need to detect a pattern of movement and find out a new center for it. In order to do that, you’ll need several samples and a fair amount of CPU cycles to perform some kind of signal processing on the inputs. That extra CPU usage is probably the reason why some games get choppier as soon as you touch the screen.

Measuring Lag

Measuring lag in a game is tricky. You usually can’t measure it from within the code, so you need to resort to external means like Mick did in his tests.

I decided to do something similar. I pulled out my digital video camera, and started recording my finger moving on the screen. The quality leaves much to be desired, but it’s good enough for the job. I can see how far my finger gets from the center of the square, but that’s not enough information to quantify the lag. How fast is my finger moving exactly? Fortunately, that’s something I can answer in code, so I added that information to the screen [1]. Now, for a given frame, I can see both how far the finger is from the center of the square and how fast it’s going.

lag_test.jpg

The square is 100 pixels wide. When I move my finger at about 500 pixels per second, the center of my finger is on the edge of the square. That makes a rough 100 ms total delay from input until it’s rendered. That’s a whopping 6 full frames at 60 fps!

What Can We Do About It

As iOS developers, there isn’t much we can do. Make sure your loops are set up correctly to avoid an extra frame delay. Make sure you provide feedback as soon as you can and don’t delay it any longer than you have to. Other than that, there’s nothing much we can do.

I’ve been saying this for a while, but I’m a big fan of layers as long as you can get to the underlying layers when you need to. Here’s a perfect case where it would be fantastic if Apple gave us raw access to the touch matrix input. Apart from being able to process the input faster (because I know what kind of input to expect for the game), can you imagine the possibilities that would open up? Input wouldn’t be limited to touch events, and we could even sense how “hard” the user is pushing, or the shape of the push.

At the very least, it would be very useful if we had the option to allocate extra CPU cycles to input recognition. I’m not doing much in my game while this is going on, so I’d happily give the input recognition code 95% of the frame time if it means it can give me those events in half the time.

I’m hoping that in a not very far distant, iDevices come with multiple cores, and maybe one of those cores is dedicated to the OS and to do input recognition without affecting the game. Or maybe, since that’s such a specialized, data-intensive task, some custom hardware could do the job much faster.

Until then, we’ll just have to deal with massive input lag.

How about you? Do you have some technique that can reduce the touch event lag?

LagTest source code. Released under the MIT License, yadda, yadda, yadda…

[1] I actually shrank the OpenGL view to make sure the label wasn’t on top if it because I was getting choppier input than usual. Even moving it there caused some choppiness. This is exactly what I saw last year with OpenGL performance dropping when a label is updated every frame!

This post is part of iDevBlogADay, a group of indie iPhone development blogs featuring two posts per day. You can keep up with iDevBlogADay through the web site, RSS feed, or Twitter.

Google App Engine As Back End For iPhone Apps

As soon as a game involves servers, there’s no such a thing anymore as “ship and forget”. Flower Garden put this in evidence about a month ago when I started getting complaints from users that the Flower Shop kept going down. Sometimes they weren’t even getting the items they were purchasing! (fortunately they can always do a free re-download, but they don’t always know that).

Flower Garden was using a shared Dreamhost server to upload bouquets, host in-game news, and, most importantly, to serve the Flower Shop (which involves hosting the static shop files, redeeming promo codes, recording transactions, verifying receipts with Apple’s server, and delivering purchased content). All the Flower Shop functionality was implement in PHP and using a mySQL database.

After some stressful sorting through the logs, it looked like the server was running out of memory and killing PHP processes. Dreamhost’s technical support didn’t help much and just claimed that I was simply something that happened and they would be happy to sell me a virtual private server. I was surprised to hear it was using up a lot of memory, and certainly nothing I could see with the tools available to me showed that. I certainly hadn’t done any changes in a while and traffic was constant. Doing some Googling at the time brought up lots of other angry Dreamhost users in a similar situation, so I suspected server configuration problems.

Whatever the case, I couldn’t let it be that way and I had to fix it somehow. I briefly considered a virtual private server, or even a dedicated host in some highly recommended providers. But in the end, the simplicity, scalability, and affordability of the Google App Engine won me over.

Now that Flower Garden has been using the Google App Engine for several weeks, I still think it’s fantastic. I wish someone had whacked me on the head when I started writing server code and forced me to use it. Hopefully this post will be more pleasant than a hit to the head and will still have a similar (good) effect.

Google App Engine Overview

appengine_lowres.gifEven though I was pretty much completely new to the Google App Engine (I had looked into it briefly before the launch of Flower Garden but dismissed it because they couldn’t support the amount of email traffic I needed), it took me two days to port over everything. Actually flipping the switch from the old system to the new one took a while longer, but that required more courage than work. More on that later.

This is not a Google App Engine tutorial. Instead, it’s going to be an overview of what it can do and why you should consider it as a backend for your iPhone app instead of using a shared or even dedicated server.

The first shock (at least for me) when looking into the Google App Engine is that you can’t run PHP. You’re limited to Java or Python. It turns out Python is my go-to scripting language, so I was thrilled at the idea. PHP is fine, but Python is a whole class above.

Next, it took a bit of adjusting to the fact that the environment to run anything on the Google App Engine has to be carefully controlled. You need to create a configuration file indicating the entry points and their handlers. Fortunately, all of that is well covered in the extensive online documentation.

This is what the Flower Garden config file looks like, indicating both static files and several execution entry points:

application: st-flowershop
version: 1
runtime: python
api_version: 1

handlers:
- url: /catalog
  static_dir: catalog

- url: /emailassets
  static_dir: emailassets

- url: /news
  static_dir: news

- url: /moregames
  static_dir: moregames

- url: /.*
  script: purchase.py

If you hit one of the URLs listed as static_dir, you get those files directly (like the in-game news). Anything else is handled by the Python script purchase.py. Google even provides the webapp framework that easily allows you to connect different parts of the script to handle different requests and easily get to the input parameters.

Once you’re past that and you have the requisite “Hello World” up and running, then it’s all fun and games.

One of the great features of the Google App Engine is that it comes with a fully-featured, local environment. This environment is installed automatically with the Google App Engine SDK, and there’s nothing to configure. It’s certainly nothing like setting up Apache + mySQL + PHP in your dev station! That way, you can do all your work locally, and only update the servers when you’re confident everything is working.

Beyond this, the only other thing that is different from what you may be used to is the datastore. They provide a query language called GQL, which is not exactly SQL, but it’s very similar. Close enough that I had no trouble porting over my very simple queries anyway.

Adding data to a data store couldn’t be simpler. For example, to add a promo code, I need the following class definition:

class PromoCode(db.Model):
	code = db.StringProperty()
	productid = db.StringProperty()
	amount = db.IntegerProperty(default=1)
	singleuse = db.BooleanProperty(default=True)
	enabled = db.BooleanProperty(default=True)

And then I can add it this way:

	promocode = PromoCode()
	# fill it up here
	promocode.put()

How do I check if a promocode is valid? I can use the SQL-like syntax, or something even simpler:

	q = PromoCode.all()
	q.filter("code =", code)
	return q.get()

Once you know that, you can go to town with your Python programs.

Google App Engine Advantages

Scalability
This was the big reason that forced me to move away from Dreamhost. I have no way of testing how scalable it really is, but I’m going to take Google’s word for it. They know a tiny little bit about scalability. And besides, Flower Garden is nothing compared to other apps (it serves about 1.5 requests per second on average).

Since I don’t know how things are implemented under the hood in the Google App Engine, I don’t have a good feel for performance best practices. So I’m hoping that my very simple queries (add to the end of a table, or see if a record is present) are just fine. If not, I can do some tuning down the line (and I won’t have to wait for any approval to make the code go live!).

Local environment
The local environment is simply great. It makes developing a pleasure. You can add any test data you want to the local datastore through a web interface without affecting the live server. Probably my favorite feature is the console: Since the server is running locally, you can print out any debug info in the server code and you can see it live as you perform some action. That saved me hours of debugging compared to doing it on a remote server with php!

Server synching
In the past, I’ve synced my server scripts through ftp and I kept meaning to write an automated script to do that. In this case, Google provides a script (and a GUI tool) to do the actual synching with the servers, which is great. It even waits a few seconds until it can verify that the new version is live on the server.

Python
I’m not a big Java fan (although I used it a bit way back in the day when it first came out), but I do love Python. For a program with some complexity like this, it’s definitely a much better choice than PHP.

Real-time stats
The Google App Engine web console displays real-time stats of access to your site. You see it expressed in requests per second and you can visualize it in the past few hours, days, or even month. You also have access to all the logs, and you can filter by type of log message (debug, info, warning, error).

Price
This is one category where the Google App Engine definitely shines. Every day you’re given a free quota of bandwidth, disk usage, and CPU usage. If you stay under that quota you don’t pay anything. If you go over, you pay per unit as you go (at very reasonable prices). You can even set a maximum cap on daily spending so you don’t encounter any nasty surprises at the end of the month.

So far, Flower Garden has been hovering right at the edge of the outgoing bandwidth free quota (the rest of the metrics it doesn’t even come close). So even if traffic were to double, expenses would be very reasonable.

Development Tricks

Along the way, I figured out a couple of interesting tricks that helped me during development.

Bypass the App store for testing
For me, few things are more annoying than doing development in the actual device. Iteration is slow and stepping with the debugger is mostly impossible (seems to depend on the mood of the debugger that day). So I try to do the bulk of the development on the simulator and just test on the device when things are ready.

Unfortunately, the device can’t access the App Store, which makes testing all the server functionality dealing with the App Store painful. What I did was to add a define that, when present, the program bypasses the App Store but still functions as usual.

Local server
During development, you want to be using your local server. In my case, I set it up so that Debug versions of the code access the local server, but Release and Distribution ones access the live one.

There is one problem: The Google App Engine server, by default, binds itself to localhost, not to the IP address of your network card. That meant I was able to hit it from the simulator just fine accessing http://localhost:8080, but not from the device. In order to access the development server from the device, I had to explicitly tell the server to bind itself to another address like this:

dev_appserver.py --address 192.168.1.150 FlowerShop

Now I can access the server at 192.168.1.150:8080 from both the simulator and any device.

Switching servers
Porting the code took just a couple of days. Making the switch on the live server was a lot scarier though. I couldn’t wait for a new update to be released because that seems to take over a week these days, so I forwarded requests from the old server to the new one.

I did it one system every day, avoiding weekends which is when there’s the most traffic. News was easy, and so was the web view with more games. But I ran into a snag with promo codes and Flower Shop purchases.

Initially, I was just redirecting requests in .htaccess this way:

Redirect permanent /Shop/catalog http://st-flowershop.appspot.com/catalog
Redirect 301 /Shop/catalog http://st-flowershop.appspot.com/catalog

As I learned the hard way, POST variables aren’t preserved in a redirect of that kind (I guess to avoid state being changed in multiple servers). I tried a bunch of things, but in the end, I wrote a quick php script that gathered all POST variables and re-posted them to the new request. A bit ugly, but it did the trick:

<?php
function PostRequest($url, $_data) {

    $data = array();    
    while(list($n,$v) = each($_data)){
        $data[] = "$n=" . urlencode($v);
    }    
    $data = implode('&', $data);
    // format --> test1=a&test2=b etc.

    $url = parse_url($url);
    if ($url['scheme'] != 'http') { 
        die('Only HTTP request are supported !');
    }

    $host = $url['host'];
    $path = $url['path'];

    $fp = fsockopen($host, 80);

    fputs($fp, "POST $path HTTP/1.1\r\n");
    fputs($fp, "Host: $host\r\n");
    fputs($fp, "Content-type: application/x-www-form-urlencoded\r\n");
    fputs($fp, "Content-length: ". strlen($data) ."\r\n");
    fputs($fp, "Connection: close\r\n\r\n");
    fputs($fp, $data);

    $result = ''; 
    while(!feof($fp)) {
        $result .= fgets($fp, 128);
    }
    fclose($fp);

    $result = explode("\r\n\r\n", $result, 2);
    $header = isset($result[0]) ? $result[0] : '';
    $content = isset($result[1]) ? $result[1] : '';
    return $content;
}


print PostRequest("http://st-flowershop.appspot.com/purchase", $_POST);
?>

Conclusion

I hope this post is enough to at least make you interested in checking out the Google App Engine and help you get over a couple of the initial hurdles. I’ll definitely be using it in any future projects.

This post is part of iDevBlogADay, a group of indie iPhone development blogs featuring two posts per day. You can keep up with iDevBlogADay through the web site, RSS feed, or Twitter.

Prototyping: You’re (Probably) Doing It Wrong

You’re not alone, I was also doing prototyping wrong until a few years ago. There are probably many different ways of prototyping games correctly, and maybe your way works great for you. In that case, a more accurate title for this post could have been “Prototyping: I Was Doing It Wrong”.

A good game prototype is something fast/cheap that allows you to answer a specific question about your game. The key points there are fast/cheap and specific question. It’s not a level of a game, it’s not a “vertical slice”, and it’s certainly not an engine for the game.

Chris Hecker and Chaim Gingold gave one of the best presentations on the subject of rapid prototyping. It was hugely influential for me, and it made me re-think the way I do prototypes. If you get a chance, find the audio for the presentation, it’s definitely worth it.

Mistake #1: Going With The First Idea

proto_2.jpgEvery company I’ve ever worked at has done this mistake. The team hashes out a bunch of ideas, and somehow they pick one (or create it by committee). Maybe they’ll create a prototype to show something about the game, or maybe they’ll dive straight and start writing a design document and developing technology. If you’re lucky, or you have an extremely talented game director, the game that comes out of the other end might be fantastic. In most cases, it’s just a so-so idea and the team only realizes it when the first level comes together, years later, at around alpha time. At this point the choice is canning a project after spending millions of dollars, or patching it up to try to salvage something. Neither idea is particularly appealing.

Creating a prototype for a game you know you’ve already committed to is pointless. It’s nothing more than an exercise to keep management happy. Frankly, I even made that same mistake at Power of Two, when we prototyped the game idea we had in mind and immediately moved on into pre-production (and yes, later we realized we had to change things to make it more interesting).

What I do now is to force myself to prototype several of my top ideas before committing to any one project. I have a page (actually, a wiki page) with every game idea or thought I have. That page has way over a hundred entries, and every so often I cull and reorganize it, bringing up the most promising ideas towards the top. Whenever I’m in prototyping mode, I start grabbing them from the top and prototype them.

proto_1.jpgWith a good prototype it’s easy to see if an idea is worthwhile. If it’s not, I discard it and move on to the next one. If it has potential but it’s just so-so, I either choose to continue just a bit longer (to ask another, better question) or I shelve it back in the list of potential game ideas. Maybe at some later time, things might click in or I might have a new inspiration and the game idea might become a lot stronger.

Also, often times, after doing one prototype and deciding against it, a new idea will come up. Usually a variation on the original prototype or something directly sparked from it, so I’ll find myself jumping to that idea instead of one of the ones I had saved in my list.

Eventually, one idea will click and you’ll know that’s “the one”. If you’re lucky (or unlucky) enough to have that happen with the first one you try, I still recommend doing a few more prototypes. If nothing else, you might be prototyping future projects, so it’s certainly not wasted time. For my current project, I went through eight prototypes before finding “the one” (several of them were a collaboration with Miguel). Eight to ten prototypes per project is roughly what I’m hearing from other indies with this approach.

Mistake #2: Not having a good question

A good prototype attempts to answer a question about the game. But not all questions are created equal. First of all, a question needs to be relevant and crucial to the project. “Can I have a pretty settings screen?” isn’t a particularly difficult question to answer, so it doesn’t deserve its own prototype. “Can I control little planes by drawing smooth lines on the screen?” is a much bigger unknown (before Flight Control anyway, today you can just download the game and immediately answer yes).

proto_3.jpgAlso, a good question is concise and can be answered in a fairly unambiguous way. “Is this game awesome?” isn’t a good question because “awesome” is very vague. A better question might be “Can I come up with a tilt control scheme that is responsive and feels good?”. Feels good is a very subjective question, but it’s concrete enough that people can answer that pretty easily after playing your prototype for a bit.

Even though most questions are about game design, they can also be about any other aspect of the game. Maybe you’re doing something tricky with technology and you want to make sure it’s feasible. If not, there’s no point in even starting. It’s more uncommon to think of prototyping art, but it’s also a very valid approach: “Will this art style allow foreground objects to stand out enough?” “Will the lighting approach allow the player to see important features in enough detail?”. Often you can do these art “prototypes” directly in Photoshop or a 3D modeling package.

In the case of Flower Garden, the main unknown was the technology behind the procedural flowers. So I created a prototype to answer the question “Can I create compelling procedural flowers that grow in real-time and the user can interact with them?”. The prototype had several parts to answer that question: the geometry generation, the animation, the simulation, and the rendering. There isn’t anything else particularly ground-breaking in the rest of the Flower Garden code, so as soon as I was able to answer “yes” to that question, I green-lighted the project and started production on it.

For larger projects, you might have several major, outstanding questions, so you’ll need to do multiple prototypes. Unless they’re very closely related, I find it easier to keep them separate instead of building on top of the same prototype.

Without a good question, it’s too easy for a prototype to go on for a long time. You feel you’re making progress because new things are added, but you have no real sense of when to stop or when it’s done. You really have to focus on the question, ignore everything else, and be merciless in your approach.

Mistake #3: Taking too long

proto_4.jpgOne of the key concepts in the definition of a prototype was that it has to be fast/cheap (which are two sides of the same coin). What’s fast enough? It depends on the length of the project itself. It’s not the same thing to do a prototype for a two-month iPhone game, than for a three-year console game. Also, a larger, more expensive project probably has more complex questions to answer with a prototype than a simple iPhone game.

In my case, I shoot for one-day prototypes. If you already have the tech to create games with, one day allows you to focus 100% on answering the question. By the end of the day, or even before, I have a pretty good idea how the game is going to work out. My shortest prototype ever was a 2-hour one. I thought it was going to be longer, but I managed to complete everything to answer the question in two hours (for the record, I didn’t can that idea, but I shelved it for a possible future project).

Game jams are a great way to get over the mental block of doing quick prototypes. There you are focused on making the game on a very short time, surrounded by people trying to do the same thing. I can’t think of a more fun way to prototype than that!

Also, think beyond programming. Is there a faster way you can answer the prototype question? Maybe you can use the modding capabilities of an existing game, or even do a mockup with paper moving pieces around. Don’t fall in the trap of thinking you have to code a prototype if something simpler and faster will do.

If you find that a day is not enough, take a step back and really ask yourself why you need more time. Were you getting side-tracked on things that were irrelevant to the prototype (menus, tech, art, etc)? Are you asking a question that the prototype can’t answer? Do you have the game idea clearly defined in your head?

Mistake #4: Building a system, not a game

proto_5.jpgWhen you’re making a prototype, if you ever find yourself working on something that isn’t directly moving your forward, stop right there. As programmers, we have a tendency to try to generalize our code, and make it elegant and be able to handle every situation. We find that an itch terribly hard not scratch, but we need to learn how. It took me many years to realize that it’s not about the code, it’s about the game you ship in the end.

Don’t write an elegant game component system, skip the editor completely and hardwire the state in code, avoid the data-driven, self-parsing, XML craziness, and just code the damned thing.

When you’re prototyping, it’s a race to answer the main prototype question. Everything is expendable. Don’t even worry about memory leaks, hardwired numbers, or how you load resources. Just get stuff on the screen as quickly as you can.

And don’t ever, ever, use the argument “if we take some extra time and do this the right way, we can reuse it in the game”. EVER.

This post is part of iDevBlogADay, a group of indie iPhone development blogs featuring two posts per day. You can keep up with iDevBlogADay through the web site, RSS feed, or Twitter.

Remote Game Editing

I’ve long been a fan of minimal game runtimes. Anything that can be done offline or in a separate tool, should be out of the runtime. That leaves the game architecture and code very lean and simple.

One of the things you potentially give up by keeping the game runtime to a minimum is an editor built in the game itself. But that’s one of those things that sounds a lot better than it really is. From a technical point of view, having an editor in the game usually complicates the code a huge amount. All of a sudden you need to deal with objects being created and destroyed randomly (instead of through clearly defined events in the game), and you have to deal with all sorts of crazy inputs and configurations.

The worse part though, is having to implement some sort of GUI editing system in every platform. Creating the GUI to run on top of the game is not easy, requiring that you create custom GUI code or try to use some of the OpenGL/DirectX libraries available. And even then, a complex in-game GUI might not be a big deal on a PC, but wait and try to use that interface on a PS3 or iPhone. After all, making games is already complicated and time-consuming enough to waste more time reinventing the widget wheel.

Remote game editing manages to keep a minimal runtime and allow you to quickly create native GUIs that run on a PC. It’s the best of both worlds, and although it’s not quite a perfect solution, it’s the best approach I know.

Debug Server

Miguel Ángel Friginal already covered the basics of the debug server, so I’m not going to get in details there.

The idea is that you run a very simple socket server on the game, listening in a particular port. This server implements the basic telnet protocol, which pretty much means that it’s a line-based, plain-text communication.

The main difference between my debug server and Miguel’s (other than mine is written in cross-platform C/C++ instead of ObjC), is that I’m not using Lua to execute commands. Using Lua for that purpose is a pretty great idea, but goes against the philosophy of keeping the runtime as lean and mean as possible.

Instead, I register variables with the server by hand. For each variable, I specify its memory address, it’s type, any restrictions (such as minimum and maximum values), and a “pretty name” to display in the client. Sounds like a lot of work, but it’s just one line with the help of a template:

registry.Add(Tweak(&plantOptions.renderGloss, "render/gloss", "Render gloss"));
registry.Add(Tweak(&BouquetParams::FovY, "bouquet/fov", "FOV", Pi/32, Pi/3))

And yes, if I were to implement this today, I would probably get rid of the templates and make it all explicit instead (ah, the follies of youth 🙂

TweakUtils::AddBool(registry, &plantOptions.renderGloss, "render/gloss", "Render gloss");
TweakUtils::AddFloat(registry, &BouquetParams::FovY, "bouquet/fov", "FOV", Pi/32, Pi/3);

The debug server itself responds to three simple commands:

  • list. Lists all the variables registered in the server.
  • set varname value. Sets a value.
  • print varname. Gets the value for that variable.

For example, whenever the server receives a set command, it parses the value, verifies that it’s within the acceptable range, and applies it to the variable at the given memory location.

Telnet Clients

telnet.pngBecause we used the standard telnet protocol, we can start playing with it right away. Launch the game, telnet into the right port, and you can start typing away.

However, most telnet clients leave much to be desired for this. They all rely on the history and cursor manipulation being handled by the shell they assume you’re connected to. Here we aren’t connected to much of anything, but I’d like to be able to push up arrow and get my last command, and be able to move to the beginning of the line or the previous word like I would do in any text editor. The easiest solution I found for that was to use a telnet client prepared for that kind of thing: A MUD client! Just about any will do, but one that works well for me is Atlantis.

So far, we’ve implemented the equivalent of a FPS console, but working remotely. And because the code is fully portable, our game can be in just about any platform and we can always access it from our PC. Not just that, but we can even open multiple simultaneous connections to various development devices if you need to run them all at once.

Custom Clients

Game parameter tweaking is something that is OK through a text-based console, but really comes into its own when you add a GUI. That’s exactly what we did at Power of Two Games. We created a generic GUI tool (based on WinForms since we were on Windows at the time), that would connect to the server, ask for a list of variables, and generate a GUI on the fly to represent those variables. Since we knew type and name of each variable, it was really easy to construct the GUI elements on the fly: A slider with a text field for floats and ints, a checkbox for bools, four text fields for vectors, and even a color picker for variables of the type color.

It worked beautifully, and adjusting different values by moving sliders around was fantastic. We quickly ran into two problems through.

The first one is that we added so many different tweaks to the game, that it quickly became unmanageable to find each one we wanted to tweak. So, in the spirit of keeping things as simple as possible (and pushing the complexity onto the client), we decided that the / symbol in a name would separate group name and variable name. That way we could group all related variables together and make everything usable again.

The second problem was realizing that some variables were changing on the runtime without us knowing it on the client. That created weird situations when moving sliders around. We decided that any time a registed variable changes on the server, it should notify any connected clients. That worked fine, but, as you can imagine, it became prohibitively expensive very quickly. To get around that, we added a fourth command: monitor varname. This way clients need to explicitly register themselves to receive notifications whenever a variable changes, and the GUI client only did it for the variables currently displayed on the screen.

tweaker.png

During this process, it was extremely useful to be able to display a log console to see what kind of traffic there was going back and forth. It helped me track down a few instances of bugs where changing a variable in the client would update it in the server, sending an update back to the client, which would send it again back to the server, getting stuck in an infinite loop.

You don’t need to stop at a totally generic tool like this either. You could create a more custom tool, like a level editor, that still communicates with the runtime through this channel.

Flower Garden Example

For Flower Garden, I knew I was going to need a lot of knobs to tweak all those plant DNA parameters, so I initially looked into more traditional GUI libraries that worked on OpenGL. The sad truth is that they all fell way short, even for development purposes. So I decided to grab what I had at hand: My trusty tweaking system from Power of Two Games.

I’m glad I did. It saved a lot of time and scaled pretty well to deal with the hundreds of parameters in an individual flower, as well as the miscellaneous tweaks for the game itself (rendering settings, infinite fertilizer, fast-forwarding time, etc).

Unfortunately, there was one very annoying thing: The tweaker GUI was written in .Net. Sure, it would take me a couple of days to re-write it in Cocoa (faster if I actually knew any Cocoa), but as an indie, I never feel I can take two days to do something tangential like that. So instead, I just launched it from VMWare Fusion running Windows XP and… it worked. Amazingly enough, I’m able to connect from the tweaker running in VMWare Fusion to the iPhone running in the simulator. Kind of mind boggling when you stop and think about it. It also connects directly to the iPhone hardware without a problem.

VMWare Fusion uses up a lot of memory, so I briefly looked into running the tweaker client in Mono. Unfortunately Mono for the Mac didn’t seem mature enough to handle it, and not only was the rendering of the GUI not refreshing correctly, but events were triggered in a slightly different order than in Windows, causing even more chaos with the variable updates.

Here’s a time-lapse video of the creation of a Flower Garden seed from the tweaker:

Drawbacks

As I mentioned earlier, I love this system and it’s better than anything else I’ve tried, but it’s not without its share of problems.

Tweaking data is great, but once you find that set of values that balances the level to perfection… then what? You write those numbers down and enter them in code or in the level data file? That gets old fast. Ideally you want a way to automatically write those values back. That’s easy if the tool itself is the editor, but if it’s just a generic tweaker, it’s a bit more difficult.

One thing that helped was adding a Save/Load feature to the tweaker GUI. It would simply write out a large text-based file with all the variables and their current values. Whenever you load one of those, it would attempt to apply those same values to the current registered variables. In the end, I ended up making the Flower Garden offline seed file format match with what the tweaker saved out, so that process went pretty smoothly.

Another problem is if you want lots of real-time (or close to real time) updates from the server. For example, you might want to monitor a bunch of data points and plot them on the client (fps, memory usage, number of collisions per frame, etc). Since those values change every frame, it can quickly overwhelm the simple text channel. For those cases, I created side binary socket channels that can simply send real-time data without any overhead.

Finally, the last drawback is that this tweaking system makes editing variables very easy, but calling functions is not quite as simple. For the most part, I’ve learned to live without function calls, but sometimes you really want to do it. You can extend the server to register function pointers and map those to buttons in the client GUI, but that will only work for functions without any parameters. What if you wanted to call any arbitrary function? At that point you might be better off integrating Lua in your server.

Future Directions

This is a topic I’ve been interested in for a long time, but the current implementation of the system I’m using was written 3-4 years ago. As you all know by now, my coding style and programming philosophy changes quite a bit over time. If I were to implement a system like this today, I would do it quite differently.

For all I said about keeping the server lean and minimal, it could be even more minimal. Right now the server is receiving text commands, parsing them, validating them, and interpreting them. Instead, I would push all that work on the client, and all the server would receive would be a memory address, and some data to blast at that location. All of that information would be sent in binary (not text) format over a socket channel, so it would be much more efficient too. The only drawback is that we would lose the ability to connect with a simple telnet client, but it would probably be worth it in the long run.

This post is part of iDevBlogADay, a group of indie iPhone development blogs featuring two posts per day. You can keep up with iDevBlogADay through the web site, RSS feed, or Twitter.

Managing Data Relationships

I’ve been meaning to put up the rest of the Inner Product columns I wrote for Game Developer Magazine, but I wasn’t finding the time. With all the recent discussion on data-oriented design, I figured it was time to dust some of them off.

This was one of the first columns I wrote. At first glance it might seem a completely introductory topic, not worth spending that much time on it. After all, all experience programmers know about pointers and indices, right? True, but I don’t think all programmers really take the time to think about the advantages and disadvantages of each approach, and how it affects architecture decisions, data organization, and memory traversal.

It should provide a good background for this coming Thursday’s #iDevBlogADay post on how to deal with heterogeneous objects in a data-oriented way.

From a 10,000-Foot view, all video games are just a sequence of bytes. Those bytes can be divided into code and data. Code is executed by the hardware and it performs operations on the data. This code is generated by the compiler and linker from the source code in our favorite computer language. Data is just about everything else. [1]

As programmers, we’re obsessed with code: beautiful algorithms, clean logic, and efficient execution. We spend most of our time thinking about it and make most decisions based on a code-centric view of the game.

Modern hardware architectures have turned things around. A data-centric approach can make much better use of hardware resources, and can produce code that is much simpler to implement, easier to test, and easier to understand. In the next few months, we’ll be looking at different aspects of game data and how everything affects the game. This month we start by looking at how to manage data relationships.

Data Relationships

Data is everything that is not code: meshes and textures, animations and skeletons, game entities and pathfinding networks, sounds and text, cut scene descriptions and dialog trees. Our lives would be made simpler if data simply lived in memory, each bit totally isolated from the rest, but that’s not the case. In a game, just about all the data is intertwined in some way. A model refers to the meshes it contains, a character needs to know about its skeleton and its animations, and a special effect points to textures and sounds.

How are those relationships between different parts of data described? There are many approaches we can use, each with its own set of advantages and drawbacks. There isn’t a one-size-fits-all solution. What’s important is choosing the right tool for the job.

Pointing The Way

In C++, regular pointers (as opposed to “smart pointers” which we’ll discuss later on) are the easiest and most straightforward way to refer to other data. Following a pointer is a very fast operation, and pointers are strongly typed, so it’s always clear what type of data they’re pointing to.

However, they have their share of shortcomings. The biggest drawback is that a pointer is just the memory address where the data happens to be located. We often have no control over that location, so pointer values usually change from run to run. This means if we attempt to save a game checkpoint which contains a pointer to other parts of the data, the pointer value will be incorrect when we restore it.

Pointers represent a many-to-one relationship. You can only follow a pointer one way, and it is possible to have many pointers pointing to the same piece of data (for example, many models pointing to the same texture). All of this means that it is not easy to relocate a piece of data that is referred to by pointers. Unless we do some extra bookkeeping, we have no way of knowing what pointers are pointing to the data we want to relocate. And if we move or delete that data, all those pointers won’t just be invalid, they’ll be dangling pointers. They will point to a place in memory that contains something else, but the program will still think it has the original data in it, causing horrible bugs that are no fun to debug.

One last drawback of pointers is that even though they’re easy to use, somewhere, somehow, they need to be set. Because the actual memory location addresses change from run to run, they can’t be computed offline as part of the data build. So we need to have some extra step in the runtime to set the pointers after loading the data so the code can use them. This is usually done either by explicit creation and linking of objects at runtime, by using other methods of identifying data, such as resource UIDs created from hashes, or through pointer fixup tables converting data offsets into real memory addresses. All of it adds some work and complexity to using pointers.

Given those characteristics, pointers are a good fit to model relationships to data that is never deleted or relocated, from data that does not need to be serialized. For example, a character loaded from disk can safely contain pointers to its meshes, skeletons, and animations if we know we’re never going to be moving them around.

Indexing

One way to get around the limitation of not being able to save and restore pointer values is to use offsets into a block of data. The problem with plain offsets is that the memory location pointed to by the offset then needs to be cast to the correct data type, which is cumbersome and prone to error.

The more common approach is to use indices into an array of data. Indices, in addition to being safe to save and restore, have the same advantage as pointers in that they’re very fast, with no extra indirections or possible cache misses.

Unfortunately, they still suffer from the same problem as pointers of being strictly a many-to-one relationship and making it difficult to relocate or delete the data pointed to by the index. Additionally, arrays can only be used to store data of the same type (or different types but of the same size with some extra trickery on our part), which might be too restrictive for some uses.

A good use of indices into an array are particle system descriptions. The game can create instances of particle systems by referring to their description by index into that array. On the other hand, the particle system instances themselves would not be a good candidate to refer to with indices because their lifetimes vary considerably and they will be constantly created and destroyed.

It’s tempting to try and extend this approach to holding pointers in the array instead of the actual data values. That way, we would be able to deal with different types of data. Unfortunately, storing pointers means that we have to go through an extra indirection to reach our data, which incurs a small performance hit. Although this performance hit is something that we’re going to have to live with for any system that allows us to relocate data, the important thing is to keep the performance hit as small as possible.

An even bigger problem is that, if the data is truly heterogeneous, we still need to cast it to the correct type before we use it. Unless all data referred to by the pointers inherits from a common base class that we can use to query for its derived type, we have no easy way to find out what type the data really is.
On the positive side, now that we’ve added an indirection (index to pointer, pointer to data), we could relocate the data, update the pointer in the array, and all the indices would still be valid. We could even delete the data and null the pointer out to indicate it is gone. Unfortunately, what we can’t do is reuse a slot in the array since we don’t know if there’s any data out there using that particular index still referring to the old data.

Because of these drawbacks, indices into an array of pointers is usually not an effective way to keep references to data. It’s usually better to stick with indices into an array of data, or extend the idea a bit further into a handle system, which is much safer and more versatile.

Handle-Ing The Problem

Handles are small units of data (32 bits typically) that uniquely identify some other part of data. Unlike pointers, however, handles can be safely serialized and remain valid after they’re restored. They also have the advantages of being updatable to refer to data that has been relocated or deleted, and can be implemented with minimal performance overhead.

The handle is used as a key into a handle manager, which associates handles with their data. The simplest possible implementation of a handle manager is a list of handle-pointer pairs and every lookup simply traverses the list looking for the handle. This would work but it’s clearly very inefficient. Even sorting the handles and doing a binary search is slow and we can do much better than that.

Here’s an efficient implementation of a handle manager (released under the usual MIT license, so go to town with it). The handle manager is implemented as an array of pointers, and handles are indices into that array. However, to get around the drawbacks of plain indices, handles are enhanced in a couple of ways.

In order to make handles more useful than pointers, we’re going to use up different bits for different purposes. We have a full 32 bits to play with, so this is how we’re going to carve them out:

Handle.png

  • The index field. These bits will make up the actual index into the handle manager, so going from a handle to the pointer is a very fast operation. We should make this field as large as we need to, depending on how many handles we plan on having active at once. 14 bits give us over 16,000 handles, which seems plenty for most applications. But if you really need more, you can always use up a couple more bits and get up to 65,000 handles.
  • The counter field. This is the key to making this type of handle implementation work. We want to make sure we can delete handles and reuse their indices when we need to. But if some part of the game is holding on to a handle that gets deleted—and eventually that slot gets reused with a new handle—how can we detect that the old handle is invalid? The counter field is the answer. This field contains a number that goes up every time the index slot is reused. Whenever the handle manager tries to convert a handle into a pointer, it first checks that the counter field matches with the stored entry. Otherwise, it knows the handle is expired and returns null.
  • The type field. This field indicates what type of data the pointer is pointing to. There are usually not that many different data types in the same handle manager, so 6–8 bits are usually enough. If you’re storing homogeneous data, or all your data inherits from a common base class, then you might not need a type field at all.
struct Handle
{
    Handle() : m_index(0), m_counter(0), m_type(0)
    {}

    Handle(uint32 index, uint32 counter, uint32 type)
        : m_index(index), m_counter(counter), m_type(type)
    {}

    inline operator uint32() const;
    
    uint32 m_index : 12;
    uint32 m_counter : 15;
    uint32 m_type : 5;
};

Handle::operator uint32() const
{
    return m_type << 27 | m_counter << 12 | m_index;
}

The workings of the handle manager itself are pretty simple. It contains an array of HandleEntry types, and each HandleEntry has a pointer to the data and a few other bookkeeping fields: freelist indices for efficient addition to the array, the counter field corresponding to each entry, and some flags indicating whether an entry is in use or it’s the end of the freelist.

struct HandleEntry
{
	HandleEntry();
	explicit HandleEntry(uint32 nextFreeIndex);
	
	uint32 m_nextFreeIndex : 12;
	uint32 m_counter : 15;
	uint32 m_active : 1;
	uint32 m_endOfList : 1;
	void* m_entry;
};

Accessing data from a handle is just a matter of getting the index from the handle, verifying that the counters in the handle and the handle manager entry are the same, and accessing the pointer. Just one level of indirection and very fast performance.

We can also easily relocate or invalidate existing handles just by updating the entry in the handle manager to point to a new location or to flag it as removed.

Handles are the perfect reference to data that can change locations or even be removed, from data that needs to be serialized. Game entities are usually very dynamic, and are created and destroyed frequently (such as enemies spawning and being destroyed, or projectiles). So any references to game entities would be a good fit for handles, especially if this reference is held from another game entity and its state needs to be saved and restored. Examples of these types of relationships are the object a player is currently holding, or the target an enemy AI has locked onto.

Getting Smarter

The term smart pointers encompasses many different classes that give pointer-like syntax to reference data, but offer some extra features on top of “raw” pointers.

A common type of smart pointer deals with object lifetime. Smart pointers keep track of how many references there are to a particular piece of data, and free it when nobody is using it. For the runtime of games, I prefer to have very explicit object lifetime management, so I’m not a big fan of this kind of pointers. They can be of great help in development for tools written in C++ though.

Another kind of smart pointers insert an indirection between the data holding the pointer and the data being pointed. This allows data to be relocated, like we could do with handles. However, implementations of these pointers are often non- serializable, so they can be quite limiting.

If you consider using smart pointers from some of the popular libraries (STL, Boost) in your game, you should be very careful about the impact they can have on your build times. Including a single header file from one of those libraries will often pull in numerous other header files. Additionally, smart pointers are often templated, so the compiler will do some extra work generating code for each data type you instantiated templates on. All in all, templated smart pointers can have a significant impact in build times unless they are managed very carefully.

It’s possible to implement a smart pointer that wraps handles, provides a syntax like a regular pointer, and it still consists of a handle underneath, which can be serialized without any problem. But is the extra complexity of that layer worth the syntax benefits it provides? It will depend on your team and what you’re used to, but it’s always an option if the team is more comfortable dealing with pointers instead of handles.

Conclusion

There are many different approaches to expressing data relationships. It’s important to remember that different data types are better suited to some approaches than others. Pick the right method for your data and make sure it’s clear which one you’re using.

In the next few months, we’ll continue talking about data, and maybe even convince you that putting some love into your data can pay off big time with your code and the game as a whole.

This article was originally printed in the September 2008 issue of Game Developer.

[1] I'm not too happy about the strong distinction I was making between code and data. Really, data is any byte in memory, and that includes code. Most of the time programs are going to be managing references to non-code data, but sometimes to other code as well: function pointers, compiled shaders, compiled scripts, etc. So just ignore that distinction and think of data in a more generic way.