Procedural Names

I’m not quite ready to start talking about my current game project, but one thing I can say is that it requires the ability to generate names procedurally. Of the several methods I’ve researched, Markov Chains seem to be the most promising. Among other things they can be used to generate random music, text, and individual words. We’ll be concentrating on individual words.

A Markov Chain describes a state machine that can transition to the next state based only on the current state and probabilities. Stated simply, this method works by analyzing input data to build up a table of states and some probabilities. Given a current state, the next state is determined based on the probability of that state as found in the sample data.

Drilling in a little deeper, to use Markov Chains for generating random names we can use a large set of names as input data. Our system will analyze these names to determine the probability of a letter following another letter. We can then start with a random letter and pick the next letter based on those probabilities, and the next, and so on. Using a single letter like this is said to be first-order. We can also use two letters, or three or more for second-order and third-order systems. A higher order will produce random output that more closely resembles the input.

Let’s build a second-order probability table using the names “Domitrovich” and “Dombrowsky” as input.

Starting with domitrovich we grab the first two letters do and use that for a state. The next letter is m.  So far we know that when the state is do, there is a 100% chance that the next letter is an m.

The next two letters are om, and the letter following is i. So now we know that when the state is om there is a 100% chance that the next letter is an i.

Following this same process we end up with this table:

State Following Letter Probability
do m 1.0
om i 0.5
om b 0.5
mi t 1.0
it r 1.0
tr o 1.0
ro v 0.5
ro w 0.5
ov i 1.0
vi c 1.0
ic h 1.0
ch end_of_word 1.0
mb r 1.0
br o 1.0
ow s 1.0
ws k 1.0
sk y 1.0
ky end_of_word 1.0

 

Note that the om and ro states each have two instances with different following letters.

We can now use this table to build a random name. Our word starts with a random 2-letter state. We use that as a key into this table to grab a random following letter based on the probabilities. We add that letter to the end of our word and use the last 2 letters as our new state and repeat the process until we reach the end of the world. For example, starting with tr:

State Following Letters Word
tr o tro
ro v, w trow
ow s trows
ws k trowsk
sk y trowsky
ky end_of_word trowsky

 

With two names as input we won’t get much variety, but with a hundred or more we get some very good random output that strongly resembles the input.  Here is some example output using a list of 400 Ukrainian surnames as input.

Anovsky
Ragoniak
Stepkap
Stutkovich
Tulinovich
Vichuna
Buchalk
Rovichal
Pandamar
Popolek

 

We can expand this basic algorithm to improve the output quality:

  • Expand the probability table by including word beginnings and make sure the output words always start with one of the word beginnings from the input data
  • Identify consonant and vowel patterns in the input data and ensure the generated word follows one of those patterns.
  • Allow for minimum and maximum word lengths.

 

I’m not going to go through all of the code for implementing this, but it’s all included in the downloadable sample project.

Create a GameObject Image Using Render Textures

On occasion when making a video game there is a need to display a texture that contains an image of a 3D game object. For example, to display in a toolbar, or chat message or something similar. These images could be created statically by your artist, but sometimes the image needs to change based on something happening in the game, or there is some other compelling reason where runtime creation is required.

Render Textures are a straightforward method for creating an image like this at runtime. I’ll spend the rest of this post describing how I do this sort of thing. I’m not going to do a step by step tutorial. I’ll mostly just describe the actual rendering part, and you can look at the code for the rest.

First, we set up a camera that will be used to render the object. I usually make it orthographic and fill with a solid background color, but you can really do anything you want. I also set up a single light. The camera and the light all get their own layer to work on, and the main game camera has its culling mask set to ignore that layer.

Here are the settings I usually use. Note the layer and and culling mask. Also, you’ll need to remove the Audio Listener or you get complaints from Unity about having multiples.

ObjectImageCameraProperties

To render the object, we first want to clone it. This lets us change the object’s properties at will without messing with the original.

GameObject gameObject =
  GameObject.Instantiate(prefab, position, rotation) as GameObject;
gameObject.transform.localScale = scale;

We instantiate the object at the desired position and rotation, then set the scale. These values need to be set so the object is positioned in front of the rendering camera. You can really do whatever you want here, even add multiple objects and lights and set up a whole scene.

Now we need to make sure the cloned object, and any children, are in the layer that the camera renders. So we set the layer by calling this function, passing in the cloned object.

void SetLayerRecursively(GameObject o, int layer)
{
    foreach (Transform t in o.GetComponentsInChildren<Transform>(true))
        t.gameObject.layer = layer;
}

Now we get to the fun part. We could create a render texture in the editor and assign it to the camera, but Unity provides a nice way to acquire a temporary render texture with code. I believe it was designed to simplify post processing effects, but it works equally well for our needs.

camera.targetTexture = RenderTexture.GetTemporary(128, 128, 16);

RenderTexture.GetTemporary allows us to acquire a temporary render texture from a pool maintained by Unity. Here, we’re asking for a small texture with a 16-bit depth buffer. You can check out the documentation for additional parameters and other information about how it works. It’s worth mentioning that if you ask for a format that isn’t supported the texture will come back as null without raising any errors (at least it did for me). So it’s a good idea to check for a null return value and deal with it accordingly.

We assign the temporary render texture to our camera’s target texture. This means that when we tell the camera to render, the results will go to our render texture instead of the screen.

And the render comes next.

camera.Render();

This will render everything the camera sees into our render texture. To recap:

  • We’ve set up a camera on its own layer.
  • We cloned the object we want to take a picture of.
  • We positioned the object in front of our camera, and changed the object to the render camera layer.
  • We acquired a temporary render texture and assigned it as the camera’s target texture.
  • We told the camera to render.

So at this point we should have our object rendered to the render texture. Now we need to get that object into a texture.

RenderTexture saveActive = RenderTexture.active;
RenderTexture.active = camera.targetTexture;
float width = camera.targetTexture.width;
float height = camera.targetTexture.height;

Texture2D texture = new Texture2D(width, height);
texture.ReadPixels(new Rect(0, 0, texture.width, texture.height), 0, 0);

texture.Apply();

This code saves the active render texture, makes our render texture active, creates a new Texture2D instance, then copies the pixels from the render texture to the Texture2D.

Finally, we call Texture2D.Apply to actually perforom the pixel copy.

All that’s left now is to clean up after ourselves by restoring the previously active render texture, releasing the temporary render texture we acquired earlier, and destroying the cloned game object.

RenderTexture.active = saveActive;
RenderTexture.ReleaseTemporary(objectImageCamera.targetTexture);
GameObject.DestroyImmediate(gameObject);

And that’s about it. The trickiest part is getting the object positioned and rotated properly in front of the camera so it looks good.

Here is a sample project that implements this. It includes a nice prefab for setting up the camera and everything.

So there you have it. Enjoy.

Animation With Timers

Last time I talked about using timers for scheduling events by simply keeping track of a time limit and how much time elapsed. Another good use for timers is performing some action over time, such as modifying alpha to fade an object in or out, or sliding an object from one location to another.

Let’s use the fading example. Fading is often done by animating transparency. The object starts out completely transparent, and gradually becomes less transparent until it’s fully opaque. An object is fully transparent when it’s drawn using alpha blending with an alpha of zero, and fully opaque when alpha is one. By quickly changing alpha from 0 to 1 over time, and redrawing the object  with the new alpha, it appears to fade into view.

You might say that when alpha is 0 the object is 0% visible, and when alpha is 1 it’s 100% visible. Thinking about the starting and ending values as percentages is very useful. For example, If you’re moving an object from one position to another, the object hasn’t moved at all at 0%, it’s moved halfway at 50%, and it’s moved all the way at 100%.  Another example, if you’re fading in a song, it’s completely silent at 0% volume, it’s medium loudness at 50% volume, and it’s full volume at 100%. Being able to animate a value from 0 to 1 has all kinds of applications in a video game.

So we need to be able to animate a value from 0 to 1, and we want it to take a specified amount of time. In the last post we already made a timer that can run for a specified amount of time.

In that timer, the variable Elapsed keeps track of how much time has elapsed since the timer started. Elapsed starts out at 0, and as the timer runs it progresses to Limit, which is when the timer expires. Looking at it another way, Elapsed has progressed 0% when it starts, and 100% when it ends. In order to calculate the progress as a percentage, we simply divide Elapsed by Limit.

Let’s change the SimpleTimer class so it calculates this percentage for us. We’ll save it in a field called Time. Here’s the class as it stood at the end of the last post.

public class SimpleTimer
{
  public float Limit;
  public float Elapsed;

  public SimpleTimer(float limit)
  {
    Limit = limit;
    Stop(); // make sure it's not running
  }

  public void Start()
  {
    Elapsed = 0.0f;
  }

  public void Stop()
  {
    Elapsed = -1.0f;
  }

  public bool Update(float elapsedTime)
  {
    bool result = false;

    if (Elapsed >= 0.0f)
    {
      Elapsed += elapsedTime;
      result = Elapsed >= Limit;
    }

    return result;
  }
}

First, add our Time field right after Elapsed:

public float Limit;
public float Elapsed;
public float Time;    // <-- add this

Next, add an UpdateTime method that does the percentage calculation and saves it to the Time field:

private void UpdateTime()
{
  Time = Elapsed / Limit;
}

Now, every time we modify Elapsed we need to call UpdateTime so Time is recalculated. We set Elapsed to 0 in the Start method, so we need an UpdateTime call there:

public void Start()
{
  Elapsed = 0.0f;
  UpdateTime();  // <-- add this
}

We also modify Elapsed in the Update method:

if (Elapsed >= 0.0f)
{
  Elapsed += elapsedTime;
  result = Elapsed >= Limit;
  UpdateTime();  // <-- add this
}

And that’s it.  Here’s the full class:

public class SimpleTimer
{
  public float Limit;
  public float Elapsed;
  public float Time;

  public SimpleTimer(float limit)
  {
    Limit = limit;
    Stop();
  }
  public void Start()
  {
    Elapsed = 0.0f;
    UpdateTime();
  }
  public void Stop()
  {
    Elapsed = -1.0f;
  }
  private void UpdateTime()
  {
    Time = Elapsed / Limit;
  }
  public bool Update(float elapsedTime)
  {
    bool result = false;
    if (Elapsed >= 0.0f)
    {
      Elapsed += elapsedTime;
      result = Elapsed >= Limit;
      UpdateTime();
    }
    return result;
  }
}

Now, as our timer is running, it’s always calculating how far it’s gone towards Limit as a percentage, which gives us a value between 0 and 1.  If we’re animating something like alpha that already takes a value between 0 and 1 then we can just use Time directly. But what if we need to change from one color to another, or move an object from one position on the screen to another?

This is where interpolation comes into play. The dictionary defines interpolation as “the process of determining the value of a function between two points at which it has prescribed values”. The “prescribed values” are our starting and ending colors, or our starting and ending positions. There are multiple ways to do the interpolation depending on your needs. A common one is Linear Interpolation, and that’s what we’ll use here. I’m just going to describe a couple of methods supplied by the XNA framework. If you want to learn how linear interpolation works you should be able to find the information on the web pretty easily.

XNA provides several Lerp (Linear intERPolation) methods:

MathHelper.Lerp
Vector2.Lerp
Vector3.Lerp
Matrix.Lerp
Color.Lerp
Quaternion.Lerp

Each of these takes starting and ending values of the appropriate data type, an amount value between 0 and 1, and returns a new value that’s amount percent between the starting and ending values. For example, MathHelper.Lerp performs linear interpolation on float values. Here are some sample values and what the function returns:

MathHelper.Lerp(10, 20, 0.0f);  // returns 10
MathHelper.Lerp(10, 20, 0.2f);  // returns 12
MathHelper.Lerp(10, 20, 0.5f);  // returns 15
MathHelper.Lerp(10, 20, 0.8f);  // returns 18
MathHelper.Lerp(10, 20, 1.0f);  // returns 20

To move an object you can use the Vector2.Lerp method and pass in Time from our timer class as amount. In this example position will start at <50, 50> and work its way in a straight line towards <750, 400> as timer.Time changes from 0 to 1.

Vector2 start = new Vector2(50, 50);
Vector2 end = new Vector2(750, 400);
Vector2 position = Vector2.Lerp(start, end timer.Time);

Similarly, color can be interpolated between two values like this:

color = Color.Lerp(Color.CornflowerBlue, Color.White, timer.Time);

I’ve included a sample project that contains the timer class as well as a simple demonstration that moves a square across the screen and cycles colors using the timer and linear interpolation.

There are many more useful things you can add to your timers, such as pausing, reversing, auto-reversing, auto-restarting. It’s also very useful to add events that fire when the Time value updates, when the timer ends, and so on.

Download SimpleTimer.zip

Make Your Time!

It’s going on seven months since my last post, which is kind of pathetic. When finishing a large project, like the WP7 port of Guardian, my brain tends to shut down for awhile for recharging. That, on top of starting a new job back in November, lead to a much longer blogging hiatus than intended. So, how about something simple to get back into the swing of things. And since we’re talking about time…

Very often in video games there is a need to perform some action after a certain amount of time elapses. Examples include deciding when to show the next frame of an animation, deciding when to spawn the next enemy, hiding a message after it’s been displayed for awhile, and so on. For a most basic implementation of this we need two values: something to describe how long we want to wait, and something to track how long we’ve been waiting.

float timerLimit = 2.0f;
float timerElapsed = 0.0f;

We also need to pick a unit of time to work with. Seconds seem to be pretty convenient, and that’s what we’ll use here. So the value of 2.0 for timerLimit means we want to wait 2 seconds before doing something.

Once we have these values established it’s a matter of updating timerElapsed each frame and checking it against timerLimit to see if the desired amount of time has passed. Since the game programming API of choice here is XNA, the proper place to do this updating is in the game’s Update() method.

protected override void Update(GameTime gameTime)
{
  // grab the number of seconds that have elapsed since the last
  // frame, including fractional seconds, so if you're running
  // at 60fps this value will be 0.0166667 more or less, or
  // 1/60th of a second.
  float elapsedTime = (float)gameTime.ElapsedGameTime.TotalSeconds;

  // add the elapsed time to our timer
  timerElapsed += elapsedTime;

  // if the timer has exceed our limit then do something
  if (timerElapsed >= timerLimit)
  {
    // TODO : do something
  }
}

Once timerElapsed passes timerLimit then we can perform our action. There’s a problem with this code though. Once the timer exceeds our limit it will keep executing the action every frame thereafter. While this may be what we want sometimes, in many cases, if not most, it isn’t. So we need a way to turn off the timer, or restart it.

To restart it we can simply reset timerElapsed back to zero if we want to the event to fire again in the same amount of time. To stop the timer we can use timerElapsed as a flag and set to -1 to indicate that the timer is inactive. Our timer code now looks like this:

// update the timer if it's enabled
if (timerElapsed != -1)
{
  // add the elapsed time to our timer
  timerElapsed += elapsedTime;

  // if the timer has exceed our limit then do something
  if (timerElapsed >= timerLimit)
  {
    // TODO : do something

    // set the elapsed time back to 0 to schedule the event again,
    // otherwise set it to -1 to disable the timer
    timerElapsed = -1.0f;
  }
}

To start the timer initially our code needs to set timerElapsed to 0 which will being the process of tracking elapsed time until timerLimit is reached.

This code practically begs to become a class, so let’s not disappoint it.

public class SimpleTimer
{
  public float Limit;
  public float Elapsed;

  public SimpleTimer(float limit)
  {
    Limit = limit;
    Stop(); // make sure it's not running
  }

  public void Start()
  {
    Elapsed = 0.0f;
  }

  public void Stop()
  {
    Elapsed = -1.0f;
  }

  public bool Update(float elapsedTime)
  {
    bool result = false;

    if (Elapsed >= 0.0f)
    {
      Elapsed += elapsedTime;
      result = Elapsed >= Limit;
    }

    return result;
  }
}

Our previous example now looks like this:

SimpleTimer timer = new SimpleTimer(2.0f);
protected override void Update(GameTime gameTime)
{
  // grab the number of seconds that have elapsed since the last
  // frame, including fractional seconds, so if you're running
  // at 60fps this value will be 0.0166667 more or less, or
  // 1/60th of a second.
  float elapsedTime = (float)gameTime.ElapsedGameTime.TotalSeconds;

  if (timer.Update(elapsedTime))
  {
    // TODO : do something

    timer.Stop(); // or use timer.Start() to restart it
  }
}

Somewhat less crappy.

Scheduling events like this is one use for a timer. Another thing that’s often needed is the ability to perform an action over time, such as fading out text. The next post will cover that.

Guardian Menus

Spruced up the menus quite a bit with some floaty asteroids instead of just the raw text. Looks much nicer I think. The todo list is pretty much empty now. Mostly some final balancing and play testing left to go, and some art work for the various icons and other app store images. If all goes well over the next couple of days it’ll be complete and ready to test when I hopefully get my hardware on Monday.

User Interface for Guardian High Scores and Challenges

Here is my attempt at using XNA to duplicate some of the UI functionality on WP7. Well, not really duplicate so much as “create a passing resemblance to”.

The menu is pretty boring. I’ve been trying to come up with a good idea to make it interesting, and think I finally have something that will be worth the effort. That’ll probably be the next movie.

The first WP7 phones are supposed to be released in the U.S. on November 8th – just one week away. Here’s hoping Guardian works well on the hardware without needing too many optimizations.

My name is Crappy Coding Guy, and I use Texture2D.GetData

In a previous post about texture modification, I mentioned the evils of transferring data from the GPU to the CPU, and then presented an example showing one way to avoid doing it.  The post wasn’t really about deformable 2D terrain or collision detection, but was intended to help newer game programmers open up a new way of thinking when it comes to using the GPU to accomplish tasks.

Since that post, and the one showing a video of my WP7 game, I’ve received a couple of questions about how I do the collision detection in Guardian, which would seem to require the use of Texture2D.GetData.

As it turns out, I am evil, and I do use GetData.  But, my evilness is optimized based on information from here, here, and here.

  • Crater drawing is batched, meaning that rather than draw each one as it’s created, I add them to a list and draw all of them every few frames. This reduces the number of GetData calls – one per batch of craters rather than one per crater.
  • After drawing craters to the render target, I wait a few frames before calling GetData to make sure the GPU has processed all of the drawing commands. This minimizes pipeline stalls.
  • If I have a pending GetData call to make and more craters come in, the craters will stay batched until the GetData call is complete.  In other words, the drawing and getting are synchronized so that a GetData call always happens several frames after drawing a batch of craters, and any new crater draw requests wait until after a pending GetData.

If there are a lot of craters being created the built-in delays can cause some slightly inaccurate collision detection since we may be looking at collision data that’s outdated by several frames. At least in this particular game there are never huge numbers of crater adds going on so this isn’t a problem. If there are more than several crater adds they tend to be bunched close together, so the explosion animation hides any visual oddities.

There is one other optimization that I have available but haven’t needed to use.  The collision data doesn’t need to be at the same resolution as the drawing data.  Basically have two sets of render targets – one for the visual texture, and a lower resolution set for the collision data.  Do the GetData on the collision texture and scale everything appropriately when doing the collision check. You have to draw twice – once for the visual data and once for the collision data – but you’re pulling much less data from the GPU which would possibly offset the extra drawing time (this isn’t something I’ve tested yet). You won’t be pixel perfect, but for this type of game that isn’t necessary. As I write this it seems using multiple render targets would eliminate the “draw twice” issue here, but I’ve never done that so some research would be required.

So there you have it. Is this the best or most efficient way?  I don’t know – I’m far from an expert on any of this. To be honest, I never actually tested doing this just on the CPU, so it’s entirely possible that that approach is better if there are collision detection requirements. There are also other considerations, such as whether your game is CPU or GPU bound, which would go into determining which method is better suited to your needs. Ultimately, whatever works in your situation is the right method.

WP7 Planet Defender Progress Video

I’ve been working on a Windows Phone 7 port of Guardian and finally have something to show for it. All of the systems are in place now, just need to do a lot of tuning and game play tweaking. Of course, at this point I have no idea how it’s going to perform on an actual phone, but it should do fairly well. Hopefully there won’t be too much optimization required after I get my hands on some hardware.

I recorded the video using Fraps while running the version compiled for Windows. Keeping a version working in Windows has made testing and debugging work much more smoothly than having to deploy to the simulator each time I make a change. It’s also a fairly simple matter to simulate the touch functionality using the mouse.

Using CLR Profiler 2.0 with XNA 4.0

By default (at least on my computer, running Windows 7), CLR Profiler 2 won’t work with new XNA apps since they utilize the new .NET framework. It looks like it’s working when you try it, but when it shows the final statistics window it’s empty. Fortunately, it’s possible to enable support using the new profiler compatibility settings functionality, which for this case involves simply setting the COMPLUS_ProfAPI_ProfilerCompatibilitySetting environment variable before running CLR Profiler.

Here’s what I did:

Create a batch file called start_clr_profiler.bat with this content, save it in Documents or wherever:

c:
cd "program files (x86)clrprofilerbinariesx86
set COMPLUS_ProfAPI_ProfilerCompatibilitySetting=EnableV2Profiler
clrprofiler

It goes without saying that you’ll need to change the drive and path to where you have CLR Profiler installed.

Once you have this file, create a shortcut to it on your desktop. Right click on the shortcut, select Properties, click the Advanced button and check “Run as Administrator”. Click OK a couple of times, and you’re good to go. Just start the profiler with the batch file and the environment variable will be set, and the profiling magic will happen.

You could also set that environment variable at the user or machine level so it’s set all the time, but I don’t know what ramifications that has so prefer setting it just when needed. Happy garbage collecting!