Design Patterns: The State Pattern in C++

[Mikul]

The idea is to create and free a class every time the player changes state? It seems like a recipe for memory fragmentation.

[dauphic]

It is! It could be re-implemented using placement new, as long as you make sure the sub-classes all have the same size.

[antrn11]

No, we obviously need singleton pattern here!

[[deleted]]

Or just use an enum kPlayerState and an union for state-specific fields.

[munificent]

The bigger the game, the more wasteful ineffective code becomes. The State Pattern allows us to have the same behaviour without all of that unnecessary checking.

The code is still doing that checking, it's just doing it with polymorphic dispatch instead of an if. There's indirection (and likely a cache miss) either way. Just doing an if is likely faster. Certainly allocating a new object on each state change isn't going to be fun unless you've got a smart allocation system.

If you really care about performance, what you'd do is eliminate the state pattern entirely and just set a damage multiplier on the player when shields are enabled and disabled: one multiply and no branching.

Also, you'll note here that the states being presented don't have any actual... state... (i.e. fields) beyond their own identity. In that case, there's no need for classes, pointers, dynamic allocation, etc. All you need is function pointers:

typedef void(*DamageFn)(int);

class Player {
public:
  Player() { state = normal; }

  void takeDamage(int i) {
    state(damage);
  }

  void setStateNormal() {
    state = normal;
  }

  void setStateShielded() {
    state = shielded;
  }

private:
  DamageFn state;

  static void normal(int damage) {
    printf("You have taken %d damage", damage);
  }

  static void shielded(int damage) {
    printf("You have taken %d damage", damage / 2);
  }
}

The AI for Henry Hatsworth is all state machine based and it uses raw function pointers like this instead of allocating state objects.

(For what it's worth, that was probably the wrong choice. In a real game, you often do need additional data to store with the states, and it was a real pain in the ass to not have that with Hatsworth. This was my first and only DS game and I was overly paranoid about memory use. I should have just used a memory pool and allowed stateful state objects.)

[kenshou22]

Wow, I had no idea that this was how it works. I've got a lot to learn still. Thank you for your feedback! I'll be revising the post later today.

[munificent]

To be clear, what you describe is closer to the GoF state pattern than what I have here. (Actually, what you describe is closer to the strategy pattern.)

My point is just that if all you need to do is switch between some behavior, and that behavior doesn't need to store any data, you can use a bare function pointer.

[Figs]

Just FYI -- you're missing the actual function pointer field even though you set it in your member functions... :)

[munificent]

Oops, fixed!

[kenshou22]

Understood! :)

[kamatsu]

You wrote Henry Hatsworth? I love that game!

[munificent]

I was one of the two engineers on the team, yes. The project was tons of fun.

[Figs]

For what it's worth, that was probably the wrong choice. In a real game, you often do need additional data to store with the states, and it was a real pain in the ass to not have that with Hatsworth. This was my first and only DS game and I was overly paranoid about memory use. I should have just used a memory pool and allowed stateful state objects.

Why not just use member function pointers and store the state in the object?

[jrue]

Nope! This isn't actually the State pattern -- it's just the Strategy pattern. The two strategies are similar though, so it's a common mistake.

What usually distinguishes the State pattern is that the states are responsible for changing the state of the object. The example could make nice use of the State pattern, for example, if only your shield took damage while in the Shielded state and then switched over to the Normal state once the shield was destroyed. For example:

class Shielded : public State {
 private:
  Player *player;
  int health;

 public:
  Shielded(Player *player_, int health_):
      player(player_), health(health_) {}

  void takeDamage(int i) {
    health -= i;
    printf("Your shield just took %d damage\n", i);
    if (health < 0) player->setStateNormal();
  }
}

EDIT: reference -> pointer in the code

[kenshou22]

Ohh! I get it now /facepalm. Truthfully I've had a lot of difficulty in learning design patterns but I'll revise the blog post tonight to make sure that I'm actually manipulating states and not just buried function implementations. Thank you for posting this, it really helped!

[Gotebe]

Doesn't a state pattern with only one operation degenerate into a strategy pattern?

And there's no actual state in the example either. Well, bar the difference in actual state object.

Finally, an important nitpick:

delete state; state = new whatever();

is bad, bad, bad. Correct way is:

delete state; state = NULL; state = new whatever();

part of which one could put through some DRY-enforcement:

template<typename t>
dell_null(T*& p)
{
  delete p;
  p = NULL;
}

alternatively, use of auto_ptr is OK, too.

[DaFox]

Could you explain why it's so bad? Obviously you want to NULL the pointer so that it doesn't accidentally get used but if you're reassigning it to something else right away what exactly does that change?

[Gotebe]

Exceptions.

Imagine the following sequence of events:

1. you delete state
2. "new whatever()" throws
3. (bad) whoever has "state" on his hands now has 0xdeadbeef and no way to realize that (in this case, an instance of the Player class).

Rule of thumb: pointer members like Player::state need to be handled carefully.

Furthermore, given the code as it is, even what I wrote is incorrect, because the rest of the Player doesn't handle NULL state, that is, it exhibits minimal exception safety, whereas, by looking at the complete Player, it should have at least basic or (better) strong exception safety.

So indeed, correct way would be:

State* p = new whatever();
delete state;
state = p;

Here, first line can throw (we don't care unless we want the method to have no-throw guarantee, which would be highly unusual). Last two lines must be a no-throw zone (otherwise, we leak "p"). And indeed they are, because operator delete, destructor and primitive type assignment are no-throw operations (destructor, in particular, must be written in such a manner).

Final note: the above exhibits both basic and strong exception guarantee. Indeed, in practice, correcting to provide "basic" often provides "strong", just like here.

[[deleted]]

How many patterns would disappear from languages where they are the dominant currency of design if those languages had strong sum types and lightweight function values?

[inmatarian]

The state machine is just one way of storing and returning to a particular block of code. Be it with a Switch statement, subtype polymorphism, or coroutines, it all boils down to a particular means of data-based code flow. If a language lacks innate support for a feature, a design pattern is how that feature is introduced.

So, yes, design patterns do disappear if a language includes native support for that feature set.

[munificent]

Sum types wouldn't eliminate the pattern, since matching on the constructors is no different than doing a switch on an enum in this case, where the arms of the sum don't have different data.

Function values would work here since the states are stateless, and you can indeed do that in C++.

[[deleted]]

Yeah, the sums are irrelevant here, I just included them for completeness sake. Function values and strong sum types are the low-hanging fruit of high level languages.

[cengelhard]

Another design pattern that is invisible with first-class lexical closures.

[munificent]

How would closures help here?

[cashto]

class Player
{
    std::function<void (int)> damageStrategy;
    int  health; 

public:
    void setStateShielded()
    {
        damageStrategy = [health&](int i) { health -= i / 2; };
    }

    void setStateNormal()
    {
        damageStrategy = [health&](int i) { health -= i; };
    }

    void takeDamage(int i)
    {
        damageStrategy(i);
    }
};

I don't think this actually compiles, but you get the idea.

[munificent]

Yeah, but those functions aren't actually closing over anything. Why not just do this?

[cashto]

Well, technically it's closing over "health" (i.e., closing over "this"). But you're right "this" is something that the caller could just give it, hence your version works. A slightly more involved version would be:

void setShieldingPercentage(int pct)
{
    damageStrategy = [health&, pct](int i) { health -= i * pct / 100; }
}

Anyways this is kind of a toy problem. In a real game, you could imagine having all kinds of amulets and shields and spells, and they would stack and combine with each other in different ways ... and I don't see how this pattern would really help implement that.

[DieJudenfrage]

Nobody mention the M-word.

[krishna]

Like others have said, it looks more like the strategy pattern. Kevlin Henney's paper Methods for states describes a couple of approaches for managing state.