Menu State Management in Games

I've written about high-level game state management before, but I didn't provide any direct code. I got a couple questions about this recently, so I decided to put a post together.

Menu management is a very clear example of the State pattern. Each different page in the menu is a different concrete subclass derived from a common State base class and managed by a Context. There's a few tricks that make this a bit easier.

For example, menus are often nested. This suggests using a Stack pattern for the context. I generally have a GameContext class that has Push, Pop, and Switch methods. They can either take a State subclass instance as a parameter, or some sort of identifier. I think this choice is 50-50; I don't have a clear preference for either one.

There's two ways of doing identifiers. Again, I don't have a clear preference here either. I tend to switch back & forth between these two solutions. (1) Add an ID in the class itself, e.g.

  public static const MainMenu::kMenuId = 'main';

This tends to be the less error-prone, although it does mean that you've got to add an extra #include (in C++), and whatever language you use it means another dependency. (2) Use a string constant. C++ compilers tend to tolerate four-character codes, ie

  Context.Switch( 'main' ); 

The downside is that if you change the identifiers or add a new menu or have a typo, you run the risk of the system blowing up at runtime. However you might choose to do the identifiers, you also need a way to register them with the Context, and that adds another layer of complexity. So your choice is: that complexity, or require any class that requests a menu state change to refer to the new menu class -- which can get messy itself. Meh? All coding is tradeoffs. Pick one. Whatever your feelings on Good and Proper Coding Practices, neither one has been proven to cause cancer in lab rats.

The Context itself also tends to be an instance of the Singleton pattern, with some public, global access. Pop, Push, and Switch might be static methods, for example; I find that means less code and complexity on the client side. (Never trust anyone using your class to be able to code their way out of a paper bag! Simpler interfaces are better.)

I usually start with a simple, copy-n-pasted examples of the different Menu classes. For example, they'll have their own Scenes for 3D objects and 2D UI bits. This is usually easier, faster, and more reliable than trying to develop the Most Awesomest Generic Menu Class Ever. The UI manager will take button clicks, and then call Context.Switch() or Pop() as needed, or Push() if the user hits the 'previous menu' button.

Game startup, then, will do stuff like initialize the 3D environment, game asset libraries, sound, etc, then start up the game state context and tell it which State to start with, which is often a CompanyLogoState. Usually I have game startup then call Context.Run, which does a simple loop of CurrentState.HandlePendingEvents, CurrentState.Draw, and CurrentState.Tick. There's some complexity there with handling events, being able to handle Push and Pop, updating the state at the right time, etc.

CompanyLogoState.Tick() will usually draw a 2D company logo, gradually brightening from black to white, holding, then back to black. When it gets to black, Tick() will call Context.Switch( GameTitleState.kStateId ), which pops the CompanyLogo off the stack and puts GameTitle in its place. That state does the same thing -- bring up the lights, so the title screen, then switch to the Main Menu state. Both the CompanyLogo and GameTitle states will move on to the next state if a key is pressed; that's done in their HandlePendingEvents() method. Eventually, one of the various Menu states (MainMenu, PlayGameMenu, LoadSavedGameMenu / StartNewGameMenu, etc etc) will need to actually start the game. That's cake: just have it call Context.Push( GameState.kMenuId ). And if the game needs to switch to a full-screen menu at some point, it can pause itself and push a new state onto the stack: Context.Push( SaveGameMenu.kMenuId ). Of course it will be important to plan out all of your various menus and states, and make sure you don't have any recursive loops.

Using this pattern, all of the various high-level states in the game are handled through the Context, which also does event handling and rendering. I've even once modified the process to work in a nested window as well - such as when you bring up the 'game menu' while a game is in progress, which doesn't back out into a full-screen menu but instead shows the game in the background, paused & faded.

As with any code, start simple. Copy n paste as needed. When you need more complexity, well-written code is easy to extend.

Loading XML data from a config file using XmlDocument

Part 1: where to save application config data under Vista
Part 2: how to save data in an XML file using XmlDocument
Part 3: this part, how to load (parse) an XML file using XmlDocument

All code samples in C#, cuz it's my drug of choice.

In the previous two parts, I covered where to save data to, and provided some sample code for creating an XmlDocument that can then be written to disk. The idea here is loading and saving application config data. For games, stuff like the user's preferred screen resolution -- which is the specific purpose I had when I dug up this code.

So let me just get straight to the code. That's why you're here, right?

const string kIntId = "ints";
const string kStrId = "strs";
const string kConfigFile = "config.xml";
private void LoadData()
{
string myAppFile = GetConfigPath() + "/" + kConfigFile;
if (!File.Exists(myAppFile))
return;

try
{
XmlDocument doc = new XmlDocument();
doc.Load(myAppFile);
XmlNode root = doc.DocumentElement;

XmlNode intsNode = root.SelectSingleNode(kIntId);
foreach (XmlNode child in intsNode.ChildNodes)
{
string key = child.LocalName;
int value = Convert.ToInt32(child.Attributes["value"].Value);
_intList[key] = value;
}

XmlNode strsNode = root.SelectSingleNode(kStrId);
foreach (XmlNode child in strsNode.ChildNodes)
{
string key = child.LocalName;
string value = child.Attributes["value"].Value;
_stringList[key] = value;
}
}
catch
{
// feh
}
}

The try/catch is there cuz you should be worried about your users being dumbasses and manually editing your config files. And/or you being a dumbass and screwing it up. Cuz that's what I did. Plus, when I changed formats, some of this stopped working.

Note that I'm using a couple constants to specify the names of the groups that I'm looking for. I do that because of Once and Only Once: mostly to keep myself from mistyping data.

I covered a way to obtain the name for the directory in which to store application data back in part 1, but here's the relevant snippet here:

private static string GetConfigPath()
{
string appData = Environment.GetFolderPath(Environment.SpecialFolder.ApplicationData);
string myAppData = appData + "/MyAppName";
return myAppData;
}

This is for per-user app config data, as opposed to shared (common) config data -- both described back there in part 1.

How to save config data into an XML file

Part 1: where to save application config data
Part 2: this part, how to save data in an XML file (using XmlDocument)
Part 3: how to load (parse) an XML file

There are many different ways of working with XML files under .NET. You can hand-roll your own code, use XmlReader, use XmlDocument, use someone's third-party library, and who knows what else. I find using XmlDocument the most sensible approach -- why write my own code? I'll let someone else worry about that.

I'll just dump the code here:

public void SaveData()
{
XmlDocument doc = CreateSaveDoc();
string myAppPath = GetConfigPath();
string myAppFile = myAppPath + "/" + kConfigFile;
if (!File.Exists(myAppFile))
{
Directory.CreateDirectory(myAppPath);
}
doc.Save(myAppFile);
}

private XmlDocument CreateSaveDoc()
{
XmlDocument doc = new XmlDocument();
XmlElement root = doc.CreateElement("root");
XmlElement ints = doc.CreateElement(kIntId);
int idNum = 0;
foreach (KeyValuePair kvp in _intList)
{
string id = "int" + idNum.ToString();
++idNum;
XmlElement node = doc.CreateElement(id);
node.SetAttribute("key", kvp.Key);
node.SetAttribute("value", kvp.Value.ToString());
ints.AppendChild(node);
}
root.AppendChild(ints);
XmlElement strs = doc.CreateElement(kStrId);
int strNum = 0;
foreach (KeyValuePair kvp in _stringList)
{
string id = "str" + strNum.ToString();
++strNum;
XmlElement node = doc.CreateElement(id);
node.SetAttribute("key", kvp.Key);
node.SetAttribute("value", kvp.Value);
strs.AppendChild(node);
}
root.AppendChild(strs);
doc.AppendChild(root);
return doc;
}

I used attributes to store info, and ignored the tag names for the contained data. I think the whole 6bytes part of XML is poopy. Yes, I said it, poopy. Attributes work better for me, cuz then you get XML that looks like:

This could be shortened to:

but, well, I got it working and I stopped caring. If you implement this yourself, feel free to take that extra step.

Hmm, I say that now... ok, I went back and changed my code. This complicates loading a bit, because I now care about tags, but you'll see that in the next section. For completeness, those inner loops are now:

{
string id = kvp.Key;
XmlElement node = doc.CreateElement(id);
node.SetAttribute("value", kvp.Value);
strs.AppendChild(node);
}

Much cleaner!

Saving application config data under Vista

Part 1: this part, where to save application config data
Part 2: how to save config data in an XML file using XmlDocument
Part 3: how to load (parse) XML-based config data using XmlDocument

I was a bit frustrated at finding this info on the net. It required a bunch of searches to pull it all together. I finally got what I needed, but, you know, bitch/moan/whine and all that. So here's everything in one place!

I'm assuming you're coding in C# (or at least can read it), and using .NET. And, like, Windows? Yeah.

So, part 1 of a 3-part series: where do I put my config data?

In the olden days (ie, under XP), you could just create a "config.ini" file in the current directory, ie with no path info, and it would save it in the same location that your application's exe was located. Under Vista and User Access Control (UAC), applications by default do not have write access to the Program Files folder. Plus, that folder might not be on the C: drive, and it might not be called "Program Files". So where do you save stuff now?

The correct location is in the AppData folder for the current user -- or, if you don't want to store user-specific data, in the common AppData folder. You can get these paths using the following code:

string userAppData = Environment.GetFolderPath(
Environment.SpecialFolder.ApplicationData);
string commonAppData = Envrionment.GetFolderPath(
Environment.SpecialFolder.CommonApplicationData);

You can also hunt for the environment variable %AppData% if you want. The above is .NET friendly, so it's what I used.

I encapsulated the above into a function, which I use a couple places in my config save/load code:

private static string GetConfigPath()
{
string appData = Environment.GetFolderPath(Environment.SpecialFolder.ApplicationData);
string myAppData = appData + "/MyAppName";
return myAppData;
}

Loading it requires the following:

string myAppFile = GetConfigPath() + "/" + kConfigFile;
if (!File.Exists(myAppFile))
return;
XmlDocument doc = new XmlDocument();
doc.Load(myAppFile);
// insert parsing here, see part 3

and saving it requires just a bit more work:

public void SaveData()
{
XmlDocument doc = CreateSaveDoc();
string myAppPath = GetConfigPath();
string myAppFile = myAppPath + "/" + kConfigFile;
if (!File.Exists(myAppFile))
{
Directory.CreateDirectory(myAppPath);
}
doc.Save(myAppFile);
}

In part 2, I cover storing data in an XmlDocument, and in part 3 I cover parsing data back out of an XmlDocument and into some local format.

(Apologies for the poor code formatting. Me and Blogger don't get along.)

Bit Haxorz

You can change code like:

if (accumulator >= test)
{
accumulator -= test;
x += stepx;
}

into

int subtract = accumulator - test;
int hibit = 1 - (subtract >> 31) & 1;
accumulator -= test * hibit;
x += stepx * hibit;

Magic! No conditionals! You might use something like this if you're working on a REAL inner-loop, such as code that'll run on a GPU or likewise run many times on a mobile or handheld CPU.

Efficient Ellipse Drawing - Part 1

This is the first in a multi-part series on drawing ellipses, pixel by pixel. Part 1 (this part) covers the basics of shape rendering, using lines as an example. Part 2 covers drawing circles. Following parts will cover ellipses.

My thesis is that any programmer can learn the math and tricks to write shape-drawing code. That's the point of this series -- to show you how to write your own code. If you just want code to copy-n-paste, go to the bottom of this post.

WARNING: Blogger.com likes to eat my code. I've reviewed this a few times, but there's no promise that it hasn't suddenly gotten hungry again. If something looks screwy, drop a comment and I'll take a look.

Background

I needed to implement efficient ellipse-drawing code in the tile editor I'm making, and I searched the net for some sample code but was thwarted. I vaguely remembered the algorithm, but I knew there was some math involved and some tricky stuff to make it fast, so I wanted to get it right. I looked at some sample code, converted it, but it didn't work. I wound up having to re-derive the equations by hand.

Part of the problem is a general problem with all sample code -- you have a specific purpose which may or may not match the sample. In my case, I was working in C# and had to clip the ellipse to the small tile. Plus little stuff, like how you specify the ellipse. A corner-to-corner definition (a bounding rect) can define an ellipse whose center is a pixel, the point between four pixels, or possibly even a point on the midpoint of an edge between two pixels. How do you adapt ellipse-drawing code to those situations?

The answer, really, is that you have to understand the algorithm itself. If you just want a library to do it for you, you can do that. In this case, that's not what I needed. I didn't want to spend an hour or two finding, downloading, installing, and integrating some third-party library -- or even just a single function -- to get something that I could do by myself in the same amount of time. What I wound up coding isn't actually an "efficient ellipse-drawing algorithm" -- I used a subfunction to calculate the error value for each pixel, with no strength-reduction accumulation code to make it faster. For what I was doing, that was fast enough, and the extra work to optimize the function wasn't necessary.

Goal

My thesis is this: line and ellipse (and circle) drawing is simple enough to learn.

Once you understand the basics, implementing your own code is straightforward.

Drawing a Line

Let's say you want to draw a line on a bitmap. If it's a straight vertical or horizontal line, the code is simple enough:

for (int x=0; x<length; ++x)
{
PlotPixel( x, y );
}

When you implement this algorithm in your own code, changes are it's gonna change to something like this:

int data = bitmap->GetDataPointer();
int offset = x + y * bitmap->GetRowStride();
for (int i=0; i<length; ++i)
data[offset+i] = pixelColor;

This is an example of what I meant above when I mentioned rolling your own. Most likely, any time you take an algorithm like this, you're going to change it enough that it won't look like the sample code you're using as a reference. That's why it's important to understand the algorithm. Straight lines are pretty simple, and you might not see much point here, but ellipses are much more complex.

Let's say you want to draw a diagonal line. That's also pretty easy.

for (int x=0; x<length; ++x)
PlotPixel( x, x );

That's kinda cheating, tho. When you adapt that bit of sample code, more likely you'll do something like this:

for (int i=0; i<length; ++i)
{
x = x1 + i;
y = y1 + i;
PlotPixel( x, y );
}

But that just draws a diagonal line. What if you want to draw a horizontal line, or a vertical one, or a diagonal that's at an angle other than 45º? Usually, you have a routine like "draw a line between these two points," and you have no idea where those two points are relative to each other. The complications pile up.

Let me start with changing that function to one that will draw a 45º line in any direction, including vertical and horizontal lines. Say that x2 and x1 are forty pixels apart. I'm going to draw forty pixels; one at each X coordinate. This means I start at X1, draw a pixel, move one pixel to the right, and repeat. This code handles going left or right with a loop:
for (x = x1; x!=x2; x+=inc)
The trick there is that 'inc' variable. If x2 is to the right (greater than) x1, then the increment is positive (+1). If x2 is to the left (less than) x1, then the increment is negative. I actually do the same thing with y.

Another option is to check to see if x2 is to the right of x1; if it's not, then swap the two points.

Anyway, this function will draw a line between two points, either flat (horizontal or vertical) or at a 45º diagonal.

DrawLine45or90( int x1, int y1, int x2, int y2 )
{
int dx = x2 - x1;
int dy = y2 - y1;
int stepx = (dx < 0) ? -1 : 1;
int stepy = (dy < 0) ? -1 : 1;
int len = dx * stepx;
if (dx==0)
{
stepx = 0;
len = dy * stepy;
}
else if (dy==0)
stepy = 0;
int x = x1;
int y = y1;
for (int i=0; i<len; +=i)
{
PlotPixel( x, y );
x += stepx;
y += stepy;
}
}

On modern machines, conditional code is expensive. Whether you're working on a PC, a modern console, a mobile device, or writing code for a GPU, if statements should be avoided in inner loops. That's why I do this business with stepx and stepy. Those increments also mean you don't need separate implementations for vertical lines, horizontal lines, and diagonals -- this loop does them all. Once you've got len, stepx, and stepy set up, just let it run.

Next: What if you want to draw a line at a different angle, something other than 0° or 45°? That's really the heart of a line-drawing algorithm -- handling lines between two arbitrary points.

From here on (except for the last sample, which is the final working algo), I'll assume that you're drawing a line where dx is greater than dy, ie a mostly-horizontal line.

Here's a simple implementation:

DrawLine( int x1, int y1, int x2, int y2 )
{
int dx = x2 - x1;
int dy = y2 - y1;
int stepx = (dx<0) ? -1 : 1;
int length = dx * stepx;
int x = x1;
int y = y1;
for (int i=0; i<length; ++i)
{
PlotPixel( x, y );
x += stepx;
y += stepx * (dy / dx);
}
}

This doesn't work, though. If dy is less than dx, then you wind up with a horizontal line (image on the left). If dy is greater than dx, then the line doesn't end at your target point -- it climbs at a constant rate and doesn't match what you want (image on the right).





The y value needs to be calculated in the loop:

DrawLine( int x1, int y1, int x2, int y2 )
{
int dx = x2 - x1;
int dy = y2 - y1;
int stepx = (dx<0) ? -1 : 1;
int length = dx * stepx;
int x = x1;
for (int i=0; i<length; ++i)
{
int y = y1 + stepx * (i * dy) / dx;
PlotPixel( x, y );
x += stepx;
}
}

The next trick is to get rid of that division in the inner loop. The way we do that is by conditionally incrementing y. This is why we assume a mostly-horizontal line. Since Y will change by either 0 or 1 each time through the loop, we can always change X but only sometimes change Y. For a finished implementation here, you will probably want two functions -- one for steep (mostly-vertical) lines and a separate function for shallow (mostly-horizontal) lines. The code samples will still be able to handle cases where point one is above, below, to the left, or to the right of point two.

OK, so to get rid of the division, we just keep an accumulator, adding dy every time, and check to see if it's greater than dx. We're going to have to watch the signs, tho.

DrawHorizontalishLine( int x1, int y1, int x2, int y2 )
{
int dx = x2 - x1;
int dy = y2 - y1;
int stepx = (dx<0) ? -1 : 1;
int stepy = (dy<0) ? -1 : 1;
int length = dx * stepx;
int x = x1;
int y = y1;
int yAccumulator = 0;
int yIncrement = dy * stepy;
int yTest = dx * stepx;
for (int i=0; i<length; ++i)
{
PlotPixel( x, y );
x += stepx;
yAccumulator += yIncrement;
if (yAccumulator >= yTest)
{
yAccumulator -= yTest;
y += stepy;
}
}
}

Final Algorithm

DrawLine( int x1, int y1, int x2, int y2 )
{
int dx = x2 - x1;
int dy = y2 - y1;
int stepx = (dx<0) ? -1 : 1;
int stepy = (dy<0) ? -1 : 1;
int lenx = dx * stepx;
int leny = dy * stepy;
int x = x1;
int y = y1;
int accumulator = 0;
if (lenx >= leny)
{
int increment = leny; // note the substitution here
int test = lenx;
for (int i=0; i<lenx; ++i)
{
PlotPixel( x, y );
x += stepx;
accumulator += increment;
if (accumulator >= test)
{
accumulator -= test;
y += stepy;
}
}
}
else
{
int increment = lenx;
int test = leny;
for (int i=0; i<leny; ++i)
{
PlotPixel( x, y );
y += stepy;
accumulator += increment;
if (accumulator >= test)
{
accumulator -= test;
x += stepx;
}
}
}
}

Further Parts

Part 2 - Drawing a circle
Part 3 - pending; circle complications
Part 4 - ellipses

Ownership, Aggregation, and Composition

Object Oriented Programming has a lot of associated jargon. You don't need to know the jargon to be a good architect, but understanding the concepts is important.

Short Form: composition is when class A owns an instance of class B; aggregation is when class A contains a pointer to class B (ie as a member variable), but doesn't own it. (Ownership implies that when the owner is destroyed, it will delete its ownees.)

Problem

There's lots of other sites that explain these things. Do they do a good job? I don't think so. I think most of them are targeted at either someone that knows nothing about OO, or someone that knows it fairly well but just wants a refresher. Like me. What's the difference between aggregation and composition again? Oh, composition is when you own the object, yeah, ok... If you aren't familiar with these concepts, then go read up on OO. I'm assuming that you've run across them before, and most likely distinguish between these two when you're writing code.

It's the sort of thing that's almost automatic, if you've learned to avoid pitfalls. Ownership is an important concept because of memory leaks. In C++, you've also got to be wary of dangling pointers and double-deletion. Back (in the olden days) when I was writing C++, I was always very careful to mark which class owned a given object.

In complex projects (especially games) you often have a ton of different objects which each have to reference the same thing. Bullets are fired by players, need to be drawn, create visual effects, collide with world geometry, etc. And in order to optimize several subsystems -- graphics and physics being two time-intensive subsystems -- you might have arcane container types. So how do you keep everything in order?

Solution

The answer is explicit ownership. Make it clear, to yourself and to whomever else is using the code. Put it in comments in the code, probably at the variable declaration and also in the header file for the contained class. If you scribble a diagram up on your whiteboard, make sure you're marking ownership clearly. Have only one owner.

Stay away from two owners. Good architectures would be having one clear owner, or having many owners -- like five, or twenty. In the latter case, you'd use reference counting or some other scheme to control deletion, such as using a globally-accessible (ie Singleton) container or manager or cache for those objects.

Sometimes the problem is something like this: bullets belong to players, but are aggregated within some class in the graphics system. But then a player logs out, the player object gets deleted, and now the graphics system has an empty pointer. Do you reference count this object? Do you keep the player object around (even after the player has logged) until all associated objects are deleted? This latter solution is why you often see players still in the game after their connection has died -- it's not so much an issue of the game not noticing the player has disconnected as the code doesn't want to delete the object yet.

Usually the cleanest solutions I've found to these my-two-dads sort of problems comes from thinking laterally. Do something completely different with bullets. Maybe a custom "reference count" used only by those two systems (although I think this is a hacky solution). Maybe bullets aren't owned by players at all, but contain a reference to a player ID allowing whatever system deals with the bullets to back-track to the player without having to worry about the player object still being around.

Jargon

The are two reasons to learn standard OO concepts. One is to help you become a better programmer. The other is so that you can communicate these concepts to other programmers. For any given concept that you learn, it's important to have a tag, a name, a label by which to refer to that concept. Having to say "that thing where you own this object that then has a pointer to a base class" is messy, when you could just say "bridge" -- which also captures a bit of intention, as well as architecture.

Say someone comes up to you and asks you what the difference between Aggregation and Containment is. Do you know? Can you explain it clearly? Probably only if you use those names a lot. I think ownership is an important concept and I use that word a lot in my code -- but I don't say // this object is aggregated or // contained. That would be lame.

I know the difference between the two. I don't think I'd be able to explain which one is which next week. Maybe, because I spent the time to write a post about it -- but that would be why, not because I use those words all the time. I think they're an awkward way to look at a more fundamental issue -- ownership.

Game State Management : Finite State Machines

I've added a subsequent post on state management in game menus. My previous post on game state covered high-level game state management. I next tried writing this post, but felt that covering feature creep was first up. I'll explain that first.

The whole trick to writing a game state management system is figuring out where you need flexibility. A system that's too complex winds up being buggy and a pain to use. Stable, easy-to-use systems generally allow you to add more richness to a project, say by extending the system, and that's something that doesn't happen when you have buggy or painful code. Simple systems lead to power.

Game state systems are used to implement game AI or mechanics. For example, a building in an RTS might start in a Construction state, then transition into an Idle state, then move into a Production state then back to Idle. A Creature AI might use states like Patrol, Guard, Hunt, Attack, Move, or Sleep. Programmers usually implement these systems using finite state machines, and that's what I'll be talking about here.

Finite State Machines (FSMs) are easy to code. The major element is the State object; everything else is optional. That else includes Transitions & Transition Conditions, Events, and Actions.

So what's a state? Take the RTS example above. When a building is in the Construction state, it might cycle through several different stages, ie have several different images (for a 2D game) or models (for a 3D game) that represents that partial construction. Maybe the phase is one long animation; maybe it's a set of several different animations. Even for a 2D, non-animated game, you might display a progress bar or particle effect or something else indicating construction progress. Is each 'step' along that progress a different State?

And that's the decision to make. Why are you storing the state? I mentioned several different states for a building in an RTS, and these suggest the state that the building is considered to be in for the purposes of gameplay, not for animation. It doesn't matter how far along construction is, the player only has two choices: either leave it alone to continue construction, or cancel the construction. This is a good level to model the state. Leave the problem of animating the building to some other system; a useful state management system in this game will deal with "Under Construction" as one entire state. A building might have four states: Construction, Idle, Production, and Under Attack (a building under attack can't be repaired or start production).

Do you need a class to store this state? Another option is to store the state as an enum. Every game tick, you tell the building to draw itself, and it can switch depending on that enum, just as easily as looking at a state class. So why would you have a State class?

One reason would be to implement the Strategy pattern. The building object itself could hold a State object, where State is an abstract base class. Subclasses would implement virtual functions, which could be Events (User_Requested_Production, User_Cancels_Construction, etc) or queries (Can_Start_Production) or maybe even a Tick or Render function. This means creating new subclasses not just for each state that buildings could share (like Idle) but also per building and per game object. The question is, what behavior do different buildings share in their Idle states, and would different game objects (like Buildings and Infantry and Missiles) all have Production or Under Attack states? What's the shared code?

This is putting the cart before the horse. Don't be led into thinking that you need to implement a Finite State Machine class because lots of games use finite state machines. I recommend implementing (say) one game object (like Buildings) first, and one Building before the rest, and then see where you can pull common code out. Implement some simple method using a bunch of switch statements and enums and see, for your game genre and design, where you need flexibility. When you're writing the code for a particular building, you might wind up writing a bunch of switch statements, and when you see yourself doing that, that is a good time to decide to implement some kind of FSM abstraction into the code.

Do all game objects render themselves? Do all game objects share a common base class (maybe they don't!)? Maybe there's common code to render a game object. Maybe all Buildings share rendering code among themselves that isn't used by other game objects. Most likely, you're not going to want custom Render methods for each individual building, or worse, each state that each building can be in.

Let's go back to the Building interface. Other gameplay objects don't really care how buildings render themselves, or really even what state the building is in. They have specific questions: can you start production right now? Should I be displaying a Cancel button? Is the building damaged? There's lots of other state I'm skipping over, too, like how many hit points the building has. I reckon there's some OO nutball out there that thinks that hit points should be encapsulated into a state object, but you and me can laugh at him. My god, man, no way. Hit points are 'state', but there's no reason to have a state object there. An int is fine. Hit points are such a primary concept in a game like an RTS that your base Game Object (or Building) class should have an accessor for that value.

So the external interface that a Building object exposes doesn't contain any State-like abstract object. A State object might be useful for a Building to manage itself internally, but it's not something it tells its friends about.

The place to put flexibility in your code is where there's a lot of traffic. Buildings don't get a lot of traffic. There's not much that can be done to them -- they get attacked, they get repaired -- but they don't usually observe their environment. Buildings don't behave different when their hitpoints get low, or when an enemy comes into range, or if they see a friendly unit nearby. Maybe yours do, but at least they're far more "stable" when compared to other units (like infantry). A complex state management system with transitions and events getting fired and scriptable transition conditionals and substates and enter actions and exit actions and all that... not that useful for game objects that don't do a lot of those things.

Mobile AI units, like infantry in an RTS or mobs in a real-time RPG or enemies in a FPS, will do a lot of those things. A fancy state management system makes more sense for those kinds of AI units, and I'll cover them in more depth next time.

Creeping Featuritis

This post was going to be on state management, but it turned into a discussion on featuritis.

My previous post on state management covered high-level game state. While rummaging around the web this week I ran across a few sites that offered finite state machines and whatnot. That's generally what people mean when they talk about state management, so I thought it'd make a good topic.

When designing a new class or building a tool to help build a game or when refactoring, one of your first questions should be, "where do I want flexibility?" Making code flexible in ways that you aren't (and won't) use means it'll take longer to get the code written and working, it'll be harder to use, and it's that much longer until you actually get something working.

So before I get into the FSM discussion, I thought I'd discuss flexibility for a bit.

One of the programmers pitfalls is gold-plating. Creeping featuritis. Whatever you call it, the tendency to make the bestest evar lies somewhere between pride and sloth on the road to hell. I believe strongly in YAGNI (see Wikipedia too): You Aren't Gonna Need It. YAGNI is a way of life, as all good principles are. It's not something you think about once in a while; it should guide a lot of your coding decisions.

For example, I'm working on editors for a game right now. My #1 goal is to get the game shipped. To have a decent, working game with a working combat and advancement system that I can use as experience when developing my next game. Whenever I think of adding some new feature to the engine, or making some system more complex and ever more awesome, I stop myself, and then figure out if that feature belongs in version 2, or 3, or 7. I write down my choice, and then go back to getting the current game working.

In fact, working on the editors is kinda backwards. The main reason I didn't start with a simple game engine is because I'm planning on using XNA, and I know way less about XNA than I do about WinForms. I figured I'd read up on XNA while building the editors, and by the time the editors were done, I'd be ready to jump into XNA coding. I like top-down coding: get something simple working, and progressively add more features. Some programmers think you should start at the bottom, making awesome libraries, but the problem there is that you never really know what you actually need.

I've learned a lot about WinForms while building the RPG4 editor (where 'RPG4' is the working title on the game). If I read a few more books first, chances are I'd still be farting around, trying to learn the framework better. I bunch of stuff I did early on was just stupid. At least, looking back, the design is bad. But I know that in part because I learned what I needed to learn as I went. Whenever I found myself adding yet another function into the main Form.cs file, I knew there had to be a better approach. Of course I knew why it was a bad idea; I knew that years ago. A decade ago. But here I had very explicit evidence about how much extra baggage you can add to a form until it becomes unwieldy.

There's a difference between too many methods in a class and too many features in a project.

I think it's a mistake to make one game (or tool or even a day-job work project) and keep adding more and more features. There's a difference between adding icing and adding cruft, and it's really a question of scale. I think it's better to err on the side of caution, of too little rather than too much. With too much, you've wasted time and energy. If you have too few features, you can always add more later.

But too many features in one class (instead of refactoring) is a different beast. I'm planning on a sequel. This is kinda like Fred Brooks' advice to "build one to throw away." I'm not worried if there's some cruft in my current project, for two reasons: (1) the design purity isn't a sign of my worth as a human being, and (2) I'm learning here! I don't need to refactor mercilessly, because in games you code it, ship it, then burn the source code. Being able to reuse systems next time is great, but being able to build a bigger, better, and faster widget next time is worth alot, too. Especially if you're going to be at a different company...

Technology changes quickly. Every year, there's new video cards out. New pixel shader standards. New consoles to consider. Phones and mobile platforms get more complex every year. It's very difficult to change a complex system to handle data in a fundamentally different way. Trying to add 3D into a 2D game engine is... blech. Besides being difficult, the solution is gonna be clunky at best.

If you build clean, tight systems, you can build them quickly. They do what you want to do, they're easy to work with, easy to change, and when you need to throw them away, you're not throwing away a lot of time and effort. I remember deciding to rebuild a 3D engine at one company, and the artists were shitting their pants. They'd seen engineers before, and what usually happened was the engineers would build, and build, and build, and then two years were passed and the thing still wasn't working.

That's what you get when you build from the bottom up. You spend time adding features you don't need, you add classes that wind up never getting used, and the whole thing is difficult to work with, too, because it's so huge. And then that hugeness starts producing bugs that are difficult to find. And then you work all weekend digging through code to find the bug, and you get it fixed, and everybody thinks you're a genius -- but two years are passed and funding ran out and the project gets cancelled.

A genius doesn't build a house of cards and then impress people by replacing one of the cards in the middle of the house. That takes a lot of talent, but the house of cards isn't what the company wanted. They just want to ship a game! Any fool can make a complex system. The smart programmers are the ones that know that a simple system with all the features that you actually need does more for the project.

High-Level Game State Management

By 'state management' I mean high-level game state. For example, when a game starts up, it might display a sequence of loading screens, including company logos, a game title screen, and intro cinematics. Then the main menu; then the game proper. Within the game itself, the game might have different screens that it displays and moves among, from character info to world view to options, etc.

I've seen some weird state management systems in my time. Almost all of the "systems" I've seen other people use aren't really systems; they were just hand-coded transitions, often involving a lot of global variables, a bunch of free functions, large switch statements, etc. Or maybe just a bunch of nested function calls, meaning that, when you quit the game, it backs out all the way through the main menu, past the title screen, the company logo, and the intro loading screen...

A programmer that's used to doing something one way, and satisfied that the approach is efficient, is unlikely to do something different. So here's something new.

I use a class-based state management system, cuz I'm a C++/C# programmer. State is managed through a 2-level inheritance hierarchy -- no complex class relationships, just one base class and one subclass for each different state. The main loop calls a static singleton to do whatever needs to be done in the current state; that singleton calls the current state subclass (of course, through a virtual function) to do its thing.

Each call through the system renders one frame. Usually; the current state can spend a bunch of time if it wants, which really only happens when loading new content. Even then, I sometimes leave the loading work to a different thread and continue rendering frames. This is one instance where the specifics aren't important; how you handle loading is independent of the idea of using a State parent class and its children to switch between different high-level states.

When a State has figured out that the game needs to move to a different state, it tells the state manager. I stick an enum for the different states in a header file. (Note that this means a bunch of recompilation "every time" I add a new State subclass. The thing is, that doesn't happen that often. There'll be maybe eight or ten states in the entire game, and over the lifetime of the project, ten extra recompiles is no big deal.) Since each run through the state manager generates one frame, the state manager can do cleanup and transition to the new state cleanly on a frame boundary.

I typically use an event model for controller/keyboard/mouse input. The events are grabbed at a high level and fed through the state manager. Abstracting input is a handy thing, and this structure solves that problem.

I've sometimes built complex stuff like preloading and caching into the state system. Separating out each game screen makes a bunch of stuff easier. Since the state objects aren't unloaded when state changes, a "level" can keep itself in memory, cached provided there's enough memory for it, meaning no lengthy load when the user (say) backs out to the main menu then reloads from a save point.

The State parent class has, over time, morphed into a Screen class. The different 'states' that this system models are often the major screens in a game: the loading screen, the company logo, the game title, the main menu, submenus, and the game proper. If save/load is handled through a fullscreen interface, that's a chance to move that code into its own class.

It doesn't matter to me if you use this structure, of course. I hope it's given you some ideas for structuring the high-level bits of your game differently.

Note: I've made a followup post on state management in game menus.

Agile Development

I'm an agile developer, but I don't use XP or Scrum. "Agile" is the umbrella term that includes XP, Scrum, and a host of other practices. "Agile Development" isn't a methodology unto itself.

To me, the heart of Agile is adapting to change; being flexible; being able to change quickly. Citing "continuous attention to technical excellence and good design" as a principle sounds disingenuous to me. That's not what separates Agile methods from other approaches. Likewise, citing Simplicity isn't very useful unless you make it clear what you think Complexity is. Yeah, messy code is bad. I'm not sure who you're going to find that's going to disagree with that.

The key observation that leads developers to agile methods is that, as programmers, we learn much more about a problem and its solution by solving it than by staring at it. Agile is the opposite of Big Design Up Front. Planning is a good exercise, and I think any competent dev team has a plan -- but when they learn more about what they're building, they'll be more willing to change that plan (and come up with better changes to boot). The core argument here is that solving a problem produces information about a problem faster and more effectively than planning alone.

There are three major practices central to agile methods. They are iterative development, top-down development, and flexible code.

Iterative development means making frequent releases. If you want to adapt to change, then you need to adapt; to change. Grossly, there are two approaches here: (1) build the whole thing, then stand back and see what you need to do different, or (2) build some of it, then stand back and assess what your next step is. Iterative development breaks up a big project into small chunks so that you can get something finished -- to make progress -- before you go gallivanting off in another direction.

An agile developer can shuffle priorities around at each iteration. Quick iterations also means more visibility up the management chain; they know where you are because you released something recently that shows where you are. Iterations also give your customers a chance to give feedback before you've gone "too far," and it provides a chance to reign in a wayward developer who has gone too long without contributing to an iteration.

I think most of the benefit of frequent iterations is incorporating feedback. To me, a big up-front design that calls for frequent releases seems squirrelly. Why are you releasing if you're not going to listen to feedback? If you're using a waterfall model, then your interim releases are going to be full of bugs, untested, and probably won't have a cohesive set of useful features.

I like planning using something small and physical; I haven't been too happy with any of the automated tools I've seen. I write down features on index cards, and sort them by priority. Every time someone completes a task, they go to the table-o-index-cards to grab their next task. (Usually they know ahead of time which set of cards are going to be theirs.) When too many features show up and/or developing an important feature takes too long, it is real fucking easy to see what tasks fall off at the back end.

Top-down development is making something simple that runs and slowly adding new features to it. I think one of the great bugaboos in software development is YAGNI, and top-down development is its cure.

In games, it's fun to get something working quickly. Plus, something working quickly gives your team more time to figure out what works and what doesn't, to see models and animations in action, and to start playtesting and thinking about balance.

Adding new features can be difficult if your code is a mess. Working around that is my third pillar today:

Flexible Code. It's hard for me to explain what this is, because unflexible code just looks so alien to me that it makes my brain hurt. The bad practices that hurt the worst here are hidden side-effects, large functions, blob classes, opaque data structures, and automation.

Automation makes a lot of things easier, but it's horribly inflexible. By "automation" I mean code structures that encapsulate some set of features into a magic little opaque blob. (You're not detecting any bias here, are you?) "Automated" code magically sticks items into queues, deletes items, changes variables, etc etc, usually in ways that someone debugging code would never know about. "Automation" often makes systems significantly easier to build, once you've learned your way around the code. But bugs can be a nightmare to remove, and god forbid someone new has to learn the system. Or its original developer leaves.

Ultimately, the goal of agile methods is to increase productivity. The two main ways this happen is by only writing code that you actually need -- by prioritizing up front and coding top-down -- and by making it easy to add new features. Some of the most frustrating experiences I've had while coding have been when I've been faced with a system that violates some of these rules. 3rd-party systems are often the worst, because (for contractual reasons) you can't see their source code, so the whole thing becomes magic. How does it work? Who knows! Plus they never bothered to document anything! Grrr.

There's tons of resources out there on agile development, but my favorite is the c2 wiki, aka WardsWiki, the firstest Wiki evar. I learn a lot more from reading both sides of an issue and making up my own mind. The C2 wiki is a great place for that. :)

Naming Conventions

Hungarian is lame. Foolish. Using Hungarian is saying "knowing the type of this variable is sofa king important that I must encode it in the variable name."

Typing isn't a major part of programming. Being able to type quickly helps, but short names don't save you that much. If you have to spend just one second trying to figure out what a variable is, that short name just cost you more time than you gained. So I'm not complaining about typing the extra characters in the name.

Source code is for the programmer, not the compiler. Compilers are easy to satisfy. They tell you if you did anything wrong. If you need to make sure you have the types right... don't. The compiler will tell you. In C#, you can't mistakenly treat an int like a char, or a bool like an int, or even mix your pointer types transparently. With warnings cranked up, C++ is just as type-strict. Back in the olden days of C, when pointers could go to void* or int or any other type without letting you know, the programmer had to be careful with variable types. We don't need to do that any more. It's a bad justification for variable-name cruft.

But correctness, that's a different kettle of fish. Your code should be easy to understand, by you, by your coworkers, by yourself in six months. That's my standard here: variable names should help you understand the code.

One analogy I frequently make is to say the brain is like a CPU. You've got 7 (plus or minus two) registers to play with. Time that you spend parsing a Hungarian prefix (and then discarding it) is still time spent, plus processing all that will consume one or two of your registers -- meaning that you'll either have to dump some registers into long-term storage or, more likely, discard them. When you're looking at a function, you've got to keep a lot of stuff in mind. What should the function do? If you're debugging, what is it actually doing? You might be thinking about a calling function's needs. The algorithm itself might be complex. The more complex the algorithm, or even dealing with special cases, the more registers you need to understand it. If you're wasting registers dealing with cruft, then it'll take you longer to make the function correct.

Forget typing it in the first place. You want to minimize the time you spend on a function while still making sure it is correct, which means satisfying yourself about correctness as efficiently as possible.

Words are tags; labels. Their written (and spoken) forms serve as anchors for the underlying concepts. Those concepts are mental entities. When you're thinking about an algorithm, you want to be working with simple tags. If a tag is something long like "previousWorldStateIndex", or, worse, "wsidxPrevious", then you've got to blow registers parsing all those keywords. When thinking about the algorithm at hand, "previous" works just fine. When you're in deep thought, all you need is a simple handle, not an accurate one.

Your functions shouldn't be long, either. Most of mine are around 7 (plus or minus two) lines long. There's a good number that are shorter, plus some that are over 9 lines. If you can abstract a line into one thought, then you can grasp a whole function at once, rolling your mind back and forth over it, like you'd probe a strange object with your fingers.

A variable declaration defines an object type just fine. If the function is only 7 lines long, you don't need to repeat the variable declaration over and over. When I'm debugging, I need to read that declaration just once, and then I've loaded that concept into one of my mental registers and I can ignore the declaration from then on. Because the compiler will catch gross type incompatibilities, and your thinking about the algorithm should catch others, all you need is a one-word tag for the variable.