"Automata Animation"
PC Techniques, Vol. 6, No. 1
Apr/May 1995, page 44

What appears here is the original manuscript, as submitted to Jeff Duntemann. Any changes in the published version are due to Jeff's expert editing.

Finite State Automata, also known as finite state machines or FSMs, are a thereotical device used to describe the evolution of an object based on its current state and outside influences. The present state of the object, its history, and the forces acting upon it can be analyzed to determine the future state of the object. Usually, finite state machines are represented in terms of state transition tables. While theoretically interesting, in general there do not seem to be very many real world applications that take advantage of the properties of finite state automata.

In this article, we will talk about finite state machines, and their associated diagrams, in terms of how they can be used to model sprite animation in a computer game. The FSM model will give us a method for designing the code that controls the sprite animation. The question that concerns us is, given the position of a sprite in the game and the forces acting upon the sprite, what happens next? This is exactly the sort of question finite state automata are well suited to answering, and we will see shortly how to do it.

Basic Sprite Animation

First, though, let's review the basic techniques of sprite animation. We visited this topic once before, in the June/July 1994 issue of PC Techniques (Breathing Life Into Your Arcade Game Sprite, page 89). In that article, we looked at a very simple sprite, an airplane which moves horizontally on a scrolling background, and occasionally changes speed and spins about a horizontal axis.

Such a simplistic sprite would not be very interesting in a modern computer game. In modern games, we want to look at sprites that have a wider range of motion: a hero sprite, for example, who runs, jumps, kicks, and shoots; or an enemy robot sprite that rolls, bumps into walls, and emits electrical charges. In order for a game to be competitive in the current market, the sprite animation needs to be creative and sophisticated. Maintaining control of such sophisticated sprite action can be a challenge.

My favorite technique for controlling sprite animation is through a combination of data structures and action functions. The data structures define both the nature of the sprite image, and its position in the game. Let's take a quick look at the data structures before we focus our attention on the action functions, which is where the real work of sprite animation takes place.

The basic building block of the sprite is the sprite structure, which is defined like this:

/* sprite structure */
typedef struct _sprite
{
  char *bitmap;
  int width;
  int height;
  int xoffset;
  int yoffset;
} SPRITE;

This structure holds the information necessary to display the sprite, including its width and height, the bitmap that defines the image, and the offset values. The offsets are used to adjust the position of the sprite, and are useful with things like explosions, which must be centered around a midpoint, rather than displayed from a corner.

The sprite structure is a member of the object structure, which is defined like this:

/* forward declarations */
struct OBJstruct;
typedef struct OBJstruct OBJ, near *OBJp;

/* pointer to object action function */
typedef void near ACTION (OBJp objp);
typedef ACTION *ACTIONp;

/* data structure for objects */
typedef struct OBJstruct
{
  OBJp next;
  OBJp prev;
  int x;
  int y;
  int xspeed;
  int max_xspeed;
  int yspeed;
  int direction;
  int frame;
  int tile_xmin;
  int tile_xmax;
  int tile_ymin;
  int tile_ymax;

  SPRITE *image;
  ACTIONp action;
};

This data structure contains all the information about a particular object in the game, including its position (x and y coordinates), its vertical and horizontal speed, the direction it is facing, the frame of animation (for example, which stage of a six-stage walk), the tile extents (how close the sprite may approach the edge of the screen), and a pointer to the sprite image, which was defined earlier. The sprite image changes as the sprite moves, and may represent a sprite as walking, running, or shooting, for example.

Defining Action Functions

The last member of the object structure is the pointer to the action function, which is where all the interesting work takes place. The action function is a function which is executed once each frame for each sprite. It performs several tasks. It causes the sprite to move (by changing the object's x and y coordinates), it checks for collisions, it may spawn new objects or kill off old ones, but most importantly, the action function determines what the object will do in the next frame. It does this by specifying the next action function.

Here is an example of an action function in its simplest form:

void near sprite_stand(OBJp objp)
{
  if (fg_kbtest(LEFT_ARROW))
    objp->action = sprite_walk;
}

This is the action function for a sprite standing still. As you can see, the sprite does nothing. Its x and y coordinates do not change, and its sprite image does not change. Also, as long as no key is pressed, the sprite's action function does not change. As long as the sprite continues to stand still, this action function will continue to be called once each frame.

The state of the sprite changes from standing to walking when the left arrow key is pressed. When this happens, the sprite_stand() function is abandoned, and the sprite_walk() function takes over. This transition happens very simply: a pointer in the object structure is reassigned to point to a new action function.

The difficult part in programming sprite animation is deciding what should go in the action functions. Since a sprite can do more than one thing at a time (shooting while jumping, for example), the programmer must make decisions about which action function should be called. The choice would be calling the sprite_shoot() function, with the jumping action being an incidental action happening within the shooting function, or calling the sprite_jump() function, with the shooting action incidentally happening within the jumping function.

Action Functions As Finite State Machines

As we mentioned at the beginning of this article, a finite state machine can be defined as an object whose past history affects its future behavior in a finite number of ways. This is exactly what is happening with the action functions. The current state of the object, combined with the forces and environmental variables acting upon it, determines the future state of the object. This can be summarized in the formula shown here:

current state + input + environment = action + future state

Usually, finite state machines are represented by transition state diagrams. These simple little diagrams can be helpful in making decisions about what goes in an action function. Suppose, for example, you have a simple sprite that does only four things: it stands still, it moves forward, it jumps, and it falls. These actions depend on the keyboard input. No input causes the sprite to stand still, an arrow key pressed causes the sprite to move laterally, and the CTRL key causes the sprite to jump. When the sprite stops jumping, he will fall. The transition state diagram will then look like this:

This state transition table easily categorizes the sprite motion for the simple sprite. By looking at this table, it is easy to see how the action functions should be constructed. Each action function is simply an if-else construction based on a row in the table. For example, the code for the sprite_stand() function would look like this:

void near sprite_stand(OBJp objp)
{
  if (fg_kbtest(LEFT_ARROW) || fg_kbtest(RIGHT_ARROW))
    objp->action = sprite_walk;
  else if (fg_kbtest(CTRL))
    objp->action = sprite_jump;
  else
    objp->action = sprite_stand;
}

The other functions, sprite_walk(), sprite_jump(), and sprite_fall() would similarly be coded by consulting the entries in the corresponding row in the state transition table.

While the state transition table easily categorizes the sprite motion for a simple sprite, it unfortunately does not tell the whole story. Look at state 4, for example. It appears that once the sprite starts falling, it continues doing so indefinitely. That is no good! Our sprite would fall right through the floor. We need to include information about the environment in our finite state machine.

It would be quite simple if we could simply put the environmental factors in another table. It would perhaps look something like this:

From this table, it is clear if you are falling and you hit the floor, you must stop falling. Similarly, if you are walking and you are not on a floor, you must be prepared to begin falling. This table still does not tell the whole story, however, because it contains no information about the keyboard inputs.

To completely tell the story of the sprite animation, you need to add another dimension to the state transition table. This is done by allowing different tables for each state. You can then compare environmental variables to inputs, and generate new states, as follows:

Now we have a way to chart out the sprite action based on both environmental factors and keyboard inputs. A typical game will have perhaps dozens of action functions, each one requiring a state transition table. It can be time consuming to chart out all these tables, and in the simpler cases, it will be an unnecessary exercise. But in the more convoluted and difficult action functions, taking the time to build a state transition table can greatly aid your coding work. It will also eliminate bugs caused by "forgotten" inputs or environment variables. All possible sprite states will be accounted for.