Sign in to follow this  
Ozymandias43

Storing Game State Efficiently

Recommended Posts

I understand the mechanics of what game engines do. I get all the basic steps, the main loop, the updating, the rendering, the physics. I've finally got my head around networking, especially as it applies to prediction, interpolation, and extrapolation. My question relates to storing the game state for maximum efficiency. Let's say I'm writing an MMO server. I think about the world in terms of zones, and let's ignore the possibility of in-between zones for simplicity. For delta compression over the network, I need to remember the current game state as well as the last 20 or so game states. What's the right way to store the game states? Do I just do something like this:
typedef struct Player {
   long playerID;
   Location position;
   Direction facing;
   Velocity velocity;
   Modifier buffs[MAX_NUMBER_BUFFS];
   char name[MAX_NAME_LETTERS];
} Player;

typedef struct GameState {
   long stateNumber;

   Player players[MAX_PLAYERS_PER_ZONE];
   OtherZoneThings things[MAX_NUMBER_THINGS];
} GameState;

typedef struct CircularBuffer {
   GameState* current, *prev, *oldest;
   GameState states[NUM_STATES_IN_BUFFER];
} CircularBuffer;

onTick() {
   //make prev current, current advances and oldest advances

   memcpy( buffer->prev, buffer->current, sizeof(GameState));
   buffer->next->stateNumber++;
   doSomeGameLogic( buffer->next );
}
Now, this seems wrong to me. I can't exactly express how, but I feel that it's not quite Right. I hear a lot of things about paying attention to cache sizes, and this seems like a lot of unnecessary copying, and I wonder about whether or not I'm being inefficient by keeping around as much information as possible. I think this data structure will WORK, but I don't want what works. I want what's, well, professional. So my question, then, is this: What's the standard, professional, solid game engine way to store state?

Share this post


Link to post
Share on other sites
Its difficult to say if its right or wrong based on the code snippet. The idea behind delta compression is that most of the world state doesn't change that often. Stuff like player position and velocity will change almost every frame (if not every frame), so you have to resend that data as much as possible (cubic splines are your friend here).

Where delta compression works is for stuff like inventory, stats, etc. Keeping with your MMO idea, you'd send your entire inventory and stats at login, and then have special messages to update as you played. So delta compression wouldn't be appropriate for stuff like player position, but would be useful for something like the players in a zone, or the stat of the quest your in.

Share this post


Link to post
Share on other sites
First, what kind of network delta compression are you going to do?

Probably between the server and each player, right?

Why not store, locally, what the world that you have broadcast to each player looks like? Then when the world changes, you can examine the perceptions of each player and determine what parts of the world need to change for that player.

So:

AbsoluteWorld: what is actually going on.
PlayerWorld: what you have told a particular player what is going on.

The amount of information in the PlayerWorld won't be that large: locations, velocities, and appearance of mobile objects, actions of nearby mobile objects, and the current location and state of the player.

The client sends action requests to the server. The server validates these actions, and either accepts them, modifies them, or refuses them. The server sends world changes to the client, and the client acknowledges them (if the ack doesn't come, the server has to resend, or be aware that some information is out of date).

When something happens in the AbsoluteWorld, it propogates to the PlayerWorlds. When the PlayerWorlds are notified of a change that the player needs to learn about, they propogate the information to the Clients over the Network.

When the Player does an action (move, activate a telescope, etc), this can change what parts of the AbsoluteWorld it needs to know about. This means that extra data can be moved from the AbsoluteWorld to the PlayerWorld.

The wonderful thing about the above design is that the Client should never be told anything that isn't in the PlayerWorld: so you can vette for information leaks at both the PlayerWorld or at the ClientCommunication levels.

PlayerWorlds need to keep track of multiple possible states for many of the variables: when a change is broadcast to a client, the acknowledgement may take time to arrive, and during that time the PlayerWorld cannot commit the change.

The AbsoluteWorld never needs to be history-versioned, as it is never communicated directly over the network. Then again, one might want to keep around old versions of it long enough that communication delayed player-actions can be evaluated in the nominal context that the player-action actually took place in. Or you could be draconian, and not allow retroactive player action: if the player's "I want to run through the door" communication arrives after the door closes, the player fails to run through the door. This closes a set of possible cheats, but makes playing the game under a large communication lag harder.

...

Meh, that was less useful for you than I'd hoped. :)

Might I suggest writing your code in "C++ without fancy-dancy objects"? The advantages of using some C++ syntax can be significant.

Share this post


Link to post
Share on other sites
Well, the way I was thinking of it was last confirmed state. The interactions would work like this:

1.) Server communicates an initial game state to the clients.
2.) Server frequently sends world updates to the clients, which the clients acknowledge receiving. The data transmitted is a compressed delta from the last confirmed state the client acknowledged receiving and the current one true state.
3.) Clients acknowledge every incoming state and remember the last states back to the last one the server sent them an update for, so they can decompress further ones.

I'm going for a quake 3 sort of model.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ozymandias43
I'm going for a quake 3 sort of model.


For an MMO?

How big is the world state? 1 Mb? 10Mb? 1000Mb? (the last one is very likely)

Most MMOs transmit data on per-client bases, possibly in a semi-lossy manner (not all updates need to arrive, some are ignored altogether), with variable update rates. Even at that, overloading the network is easy.

Keep in mind that rules are different for MMOs. You'll have 500 clients. No cache optimization is going to save you there.

Most of the practical solutions these days work with area of interest management. When a client moves around the world it subscribes to objects in range. As these objects change, the delta state of that object is sent to subscribed clients.

As players move around the world, they are dynamically subscribed and unsubscribed to these objects, so each clients receives only a tiny fraction of entire world.

Just do the math: 500 players, 100 items per player, 50,000 creatures, 50,000 world objects, 50 attributes per object - almost 40 million values. 20 times for past state - a very big state. Distributed over several machines in a cluster.

Today's systems scale up to some 100-200 active users in same area of interest (large battle for example). But updating 150,000 is simply impossible.

Even at that, servers often spawn objects on demand to reduce load (if nobody is around to see it, the mobs don't exist).

The intra-zone problem is also crucial to consider at design stage - it implies core state storage since you'll need to provide ghosting (object shared across different cluster nodes), and solve authority problem (who may change an object, whos change to consider, which one wrote first).

From visual observation, in WoW, a player only receives around 50-100m of surroundings, thereby seeing 50-150 objects at any one time. GuildWars is fully instanced, but has a limit of some 100-150 players for non-combat zones, around 30-40 for combat zones. Combat zones have around 500 NPC mobs, and those are only sent to clients on demand, so a player only sees 20-30 of them at any given time.

This may seem little, but the 100 players in an area is pushing it for any given game - so all efforts are focused at reducing world state into that tiny narrow window a client can handle.

Share this post


Link to post
Share on other sites
Okay, let me ask a different question, then. Ignoring MMOs, let's say I'm writing a smaller, quake 3 sort of game, one where it would make sense to remember a few previous gamestates. What would be my strategy then?


Unrelated question, now my interest is piqued in the object subscription model. How do you go about crafting an update for that? Does every object maintain a list of interested listeners? If so, what does a game update look like? I imagine each player would get a little buffer of update information, then you cycle through each object and if the object has changed, you add its changes to the subscribed players' buffers, then when you finish iterating through objects, you fire off the buffers to each player? Is that more or less how it'd work?

Share this post


Link to post
Share on other sites
The process is described in Graphic Gems 3 (and elsewhere).

Each object comprised out of key-value pairs.

When player subscribes to an object, that objects full state is sent to client - all of that object's kay-value pairs (visible to client, not full server state) are serialized.

After that, each time that object's state changes, that change is sent to all subscribed clients.

Simply put:

// First update
{ health = 100, energy = 100, apearance = 228574, name = "Willy" }

// In combat, only partial updates are sent, possibly accumulated
{ health = 80 }
{ health = 60 }
{ health = 40 }
{ health = 80, energy = 50 } // player healed themself using energy, restoring health



The encoding is irrelevant, as well as the actual format. The greatest savings come from very fine-grained control over subscription.

Owner of an object might, for example, receive more properties than other players. Server side ghosting would also receive internal state (logic, AI), but wouldn't care about apearance.

This aproach might not be suitable if you require extremly frequent updates (not present in MMO) at a rate of 5 - 50Hz.

In addition, you do not need to send updates as they happen. You can delay them for a bit (possibly just send response back every 250ms). In this case, if a player takes damage 5 times, only one update will be sent, not 5 decrements.

This is probably the only way to deal with truly scalable worlds. Everything else is simply too taxing on the network.

With this model, you don't need previous states. Client is dumb, it'll render what the server says. And if there are any previous states, client can cache them for itself.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this