To put transparent images in games, we usually use images that contain an alpha channel specifying the transparency of each pixel. Here's an example of an image being composited onto a new background using an alpha channel:

There are several reasons why we would need to downscale an image. In 3D games, the most common reason is to create mipmap chains. A mipmap chain stores copies of the image recursively downsampled by 50% each time, until it reaches a single pixel. These smaller images allow us to draw distant objects and glancing angles more accurately and efficiently.

Scaling down images with alpha channels can cause a significant problem. For example, if we try to compose the downscaled example image, we get this:

The background color starts 'bleeding' into the image. The usual way to fix this is to manually make the background color as similar as possible to the image, so that it doesn't matter if it bleeds in. Here's an example of that technique, created by layering the image onto blurred copies of itself.

This can take a lot of time for the artists, and is also made impossible by some image exporters. For example, when Photoshop exports .png files it automatically makes all transparent pixels white. Fortunately, there's a more elegant solution that doesn't require any extra effort on the artist's part. Usually the image is scaled down by averaging every group of four pixels to find the color of each new pixel:

Instead of doing a straight average, we can perform a weighted average of each new pixel based on the alpha weights. This means that transparent pixels will have very little effect on the color. The opaque colors will bleed out into the background instead of vice versa.

The final result is that the composition will look correct at any level of scaling, regardless of the initial background color.

Please let me know if you've encountered this problem before, or if you have an alternate solution!

We've got some pretty cool stuff in Overgrowth this week.

As mentioned yesterday, we now have fancy texture compression. This will let Overgrowth run on many more computers, because it will use a fraction of the VRAM it previously used. Starting up Overgrowth is also much, much faster now.

As usual, we have fixed a number of bugs, tweaked some stuff, and implemented some new features. Aubrey has created even more art.

- We have a nifty camera panel that lets you change the FOV and such with a slider
- We now support a number of different texture formats and improved our .obj support, so it is even easier to add new stuff
- The cursor gets updated to reflect the tool that will be used (for the omni tool)
- Map editor groups are colored according to a color wheel
- Hierarchical groups have been implemented
- Graphical editor feedback
- A grid is drawn to show plane of movement for some tools

P.S. we will be migrating the blog, forums, and IRC to a new server soon, so if there is some downtime, that's why!

Why do we need compression?

To achieve our target level of detail in Overgrowth, we have to use some very high-resolution textures. We would like the game to run smoothly on older graphics cards, which often have less than 128 MB of video RAM. This is a problem for texture storage: just one uncompressed 2048*2048 RGBA texture uses 16 MB of RAM, and we may have dozens of them. One of the techniques we're using to solve this problem is DXTC texture compression.

What is DXTC?

Most common image compression formats like PNG and JPEG aren't directly supported on the graphics card. We can use them to make smaller files on the hard disk, but as soon as they're loaded into the game they're decompressed to their full size. However, a few formats can actually be loaded and processed by the graphics card in their compressed form. The oldest and most widely supported of these is DXTC (previously known as S3TC). Here's a closeup of a compressed and uncompressed version of a cat concept by Aubrey.

As you can see, the compressed version looks almost the same as the uncompressed version, and uses 128 KB of memory instead of 768 KB. It's a form of lossy compression, so some of the subtle color gradients are simplified. To put this into perspective, here's what an uncompressed 128 KB image looks like.

How do we use DXTC in OpenGL?

I spent a long time looking for the best way to do this, and ended up using the .dds (DirectDraw Surface) file format, loaded with the NVImage class included with their OpenGL SDK. To create these .dds files, we load up the old .tga textures using FreeImage and automatically convert them in-engine using Nvidia's Texture Tools code. We choose the type of DXTC compression based on the suffix of the file. For example, rabbit_head_dxt5.tga would be converted to rabbit_head.dds using DXT5 compression.

What do the different types of DXTC mean?

There are many different kinds of DXTC compression, and it can be overwhelming at first to figure out which ones to use. The only really important ones are DXT1, DXT3, and DXT5. They all handle color compression in the same way, but the key difference is how they handle the alpha channel. Here's the alpha channel of a smoke sprite compressed with each type:

DXT1 has a binary alpha, and is basically unsuitable for anything that will be rendered with alpha blending (it might be ok for simple alpha testing). DXT3 stores an uncompressed 4-bit alpha for each pixel. This means that the colors are all in the right place, but there are only 16 levels to choose from, causing severe banding artifacts on long gradients. DXT5 stores an interpolated 4-bit alpha. This means that there are the same kind of block compression artifacts as in the color channel, but smooth gradients look pretty good. It's safe to say that DXT5 alpha channels look the best for most images.

Does that mean we should always use DXT5? There are two cases where we shouldn't. First, if there's no alpha channel, we should use DXT1, because it's half as big as DXT5. Second, if there are only sharp edges, DXT3 is actually slightly more accurate than DXT5. Here is an example image with sharp alpha edges.

It's impossible to tell the difference between the uncompressed, DXT3 and DXT5 images here just by looking at the alpha, but by subtracting the compressed images from the TGA and amplifying it 16x, we can see which is more accurate (darker is better):

This shows that DXT3 is more accurate for hard anti-aliased edges than DXT5.

The last question is which DXTC format to use for normal maps. This is too complicated to get into here in detail; you can find whole articles on this subject. However, the consensus seems to be that we should use DXT5 and put one of the directional channels in the alpha channel. Unfortunately, that means we can't use the alpha channel for specularity like we do now; we'll need a whole new texture. On the bright side, using two DXT5 textures is still only half as much VRAM as an uncompressed texture!

Finding out how to use DXTC compression effectively in our game took a few days of research on my part, so I wrote this post to save some time for other graphics programmers out there. Please let me know if there are any tricks or best practices that I am missing!

Many games have combat, but it's usually treated as an obstacle in your path to something else. You have to kill enemies to get where you need to go, or to accumulate enough skill points. When writers make an attempt to justify it, they usually pick reasons that are unrelated to the fighting itself. Usually you're following orders, trying to get revenge, saving the world, or rescuing the damsel in distress. For example, in Gears of War 2, you've been ordered to save the world from the aliens who tortured your squadmates and kidnapped your best friend's wife. Similarly, the enemies usually are just following orders, or are so evil they apparently don't need motivation to attack you.

Sometimes when playing games like this, these goals actually make the game less fun for me. When they hammer into my head that the goal is to get from point A to point B as fast as possible, the combat just seems like a chore that I have to plow through. Surely we can create motivations that are more related to the fighting itself! Portal did a great job crafting a story that was all about learning to use the portal gun, and I think that idea can be extended to other genres as well.

Lugaru had a pretty standard action game story, so I'm working on ideas to improve on that with Overgrowth. From looking at great scenes in kung fu movies, one idea that keeps coming up is that fighting is often a performance. For example, here is my favorite scene from Legend of Drunken Master:

I found this scene interesting because not only is it one of the best fight scenes ever made, with brilliant choreography and very little special effect fakery, but there's a lot going on in the story at the same time. As Jackie Chan recovers his stepmom's bag from the thugs who stole it, she realizes that he's easily defeating these thugs in front of a large audience, and turns it into an exhibition for his new drunken boxing techniques to attract business to their fighting school. Exhibition matches would be an interesting way to add more drama to easier fights: you know that you can win, but that's not the point. How impressively can you win? This ties into the gameplay a lot more directly, because the fighting is the whole focus, and not an obstacle to some other goal. Along those same lines:

Since players are playing the game to be entertained by the fighting, I think we need new kinds of stories that can complement the gameplay without distracting from it. Here are some of the questions I'm thinking of exploring with the Overgrowth story to keep it focused on fighting:

• Is it better to win a fight dishonorably or to lose honorably?
• What are the consequences of sparing someone's life in a fight to the death, or killing in a fight just meant to establish status?
• Who would dare to attack a rabbit who has killed wolves with his bare hands?
• Does a reputation for great fighting skill make you safer or less safe?
• What does it mean to be a fighter in a culture that hates fighting?
• When is lethal force more effective than a show of strength?

Every modern real-time game has some form of rock, paper, scissor mechanics. As gamers we subconsciously know that such mechanics are there and that they work pretty well but no one ever explains why. With a little bit of game theory I can show you why but first I'll need to give you some brief game theory definitions.

What is a game?
A game is a framework involving two or more players where each player's success is determined not only by his own strategy, but by the strategies of all the other players in the game.

What is a strategy?
A strategy is a complete plan of action for a player that explains how he will behave.

What is a dominant strategy?
A dominant strategy is a strategy that does at least as well as every other strategy in all situations but does strictly better than every other strategy in at least one situation. (In a game of rock, paper, shotgun, the shotgun would probably be the dominant strategy.)

One Way To Win

Let's stitch this together in a computer game example. Let's say there are 2 people playing an RTS called Lugaru Wars. Each player has just enough resources to either make one wolf unit or one rabbit unit. Let's assume that winning the game earns the winner one point. Let's also assume that wolves always beat rabbits (the rabbits are not like Turner). Finally let's assume that the result of a wolf fighting a wolf or a rabbit fighting a rabbit is a 50/50 toss up where each player's expected winnings are half a point. Here's what the game would look like in normal form:

Payoffs are represented in the form (X,Y) where X is what Player 1 has won and Y is the winnings for Player 2. For more information on how to read and understand normal form games click here.

From looking at the payoff matrix, it becomes clear that building a wolf is the strictly dominant strategy. If my opponent builds a rabbit and I counter with a wolf, I get 1 point whereas countering with a rabbit gives me an expected value of 1/2. If my opponent builds a wolf and I counter with a rabbit I am guaranteed to lose and get 0 points whereas countering with a wolf, I can expect 1/2. Choosing to build a wolf makes me better off in every scenario. This game is not balanced because any player who is trying to win, builds the wolf unit all the time every time and the rabbits might as well not be in the game at all. (Bonus Fact: the "Nash Equilibrium" of this game occurs when each player builds a wolf.)

Balanced But Boring

How can this be fixed? Let's pretend that wolves are twice as powerful as rabbits, so that when two rabbits meet one wolf, it's a 50/50 toss up as to who will win. A quick fix for balancing this RTS is to make the rabbit cost half as many resource points as the wolf. So now with the same resources each player can build either one wolf or two rabbits. Now the payoff matrix looks like this:

In this game the strategy of building 2 rabbits is just as effective as building one wolf. One could try to argue that our work is done and we will now see a healthy mix of both units being built. However, this game is still very boring because the players don't care at all what they build or what their opponent builds. Each person says, "Hey as long as I spend all my resources building something, I can always expect half a point no matter what."

Mixing It Up

Ok, enough boring examples. Let's spice this up by adding another character. Let's say that players can again only build one unit each but now they can choose among a rat, a wolf and a rabbit. In this game assume wolves always beat rabbits but rats are sneaky enough that they can always ambush and kill wolves. Finally, the rabbits have such good hearing that the rats can not sneak up on them and rabbits can destroy rats every time. Here's what the game's payoffs would look like:

Now is there one dominant unit type that is always the best to build? No. Do players still feel indifferent about what they build relative to what their opponent is building? No, quite the opposite. Now each player really wants to know what the other player is up to so that he can build the right counter unit. The game is again balanced (each unit has equal merit) but there is no obvious strategy. (Bonus Fact: This balance here coincides with the fact that there is no pure strategy Nash Equilibrium in this game, only a mixed strategy Nash Equilibrium where both players are equally likely to pick any of the three units).

If you're going to allow the player a super-strategy, make its cost to the player proportional to its power so they can't execute it frequently. More importantly, make sure that the player can't derive a super-strategy that works in every situation. Game designers have an obligation to combine some weaknesses with the strengths for a given course of action so that instead of dooming the player to repeat his same old dominant strategy again and again he finds himself forced into situations where a new strategy must be derived.

One of the reasons I like Lugaru so much is that not only is it structured to have no dominant strategy, no move to beat all moves, but David actually programmed the AI to punish users that repeat one type of attack too many times in a row. Players are thus forced to experiment and become comfortable with a lot of different moves.

Can you think of any games that are famous for embracing mixed strategies with their careful balance? Do you have any thoughts on how to take these game design concepts further?