Purely Functional Retrogames, Part 3

(Read Part 1 if you missed it.)

Every entity in a game needs some data to define where it is and what it's doing. At first thought, a ghost in Pac-Man might be defined by:

{X, Y, Color}

which looks easy enough, but it's naive. There needs to be a lot more data than that: direction of movement, behavior state, some base clock values for animation, etc. And this is just simplistic Pac-Man. In an imperative or OO language this topic barely deserves thought. Just create a structure or object for each entity type and add fields as the situation arises. If the structure eventually contains 50 fields, who cares? But...

In a functional language, the worst thing you can do is create a large "struct" containing all the data you think you might need for an entity.

First, this doesn't scale well. Each time you want to "change" a field value, a whole new structure is created. For Pac-Man it's irrelevant--there are only a handful of entities. But the key is that if you add a single field, then you're adding overhead across the board to all of the entity processing in your entire program. The second reason this is a bad idea is that it hides the flow of data. You no longer know what values are important to a function. You're just passing in everything, and that makes it harder to experiment with writing simple, obviously correct primitives. Which is less opaque:

step_toward({X,Y}, TargetX, TargetY, Speed) ->
   ...

step_toward(EntityData, TargetX, TargetY, Speed) ->
   ...

The advantage of the first one is that you don't need to know what an entity looks like. You might not have thought that far ahead, which is fine. You've got a simple function for operating on coordinate pairs which can be used in a variety of places, not just for entity movement.

If we can't use a big struct, what does an entity look like? There are undoubtedly many ways to approach this, but I came up with the following scheme. Fundamentally, an entity is defined by an ID of some sort ("I am one of those fast moving spinning things in Robotron"), movement data (a position and maybe velocity), and the current behavioral state. At the highest level:

{Id, Position, State}

Each of these has more data behind it, and that data varies based on the entity type, the current behavior, and so on. Position might be one of the following:

{X, Y}
{X, Y, XVelocity, YVelocity}

State might look like:

{Name, StartTime, EndTime}
{Name, StartTime, EndTime, SomeStateSpecificData}

StartTime is so there's a base clock to use for animation or to know how long the current state has been running. EndTime is the time in the future when the state should end; it isn't needed for all states.

In my experiments, this scheme got me pretty far. Everything is very clean at a high level--a three element tuple--and below that there's still the absolute minimum amount of data not only per entity type, but for the exact state that the entity is in. Compare that to the normal "put everything in a struct" approach, where fields needed only for the "return to center of maze" ghost logic are always sitting there, unused in most states.

But wait, what about additional state information, such as indicating that a Pac-Man ghost is invulnerable (which is true when a ghost has been reduced to a pair of eyes returning to the center of the maze)? If you remember Part 2, then the parenthetical note in the previous sentence should give it away. If the ghost is invulnerable when in a specific state, then there's no need for a separate flag. Just check the state.

Part 4

permalink May 3, 2008

Purely Functional Retrogames, Part 3

previously

archives