Who is this article for?[]
This article is for people that have a lot of entities in their networked game. Their server might be sending a lot of redundant information, like player health or position data, which costs bandwidth. This article focuses on 2D games with a limited view range, but the concepts can be used for 3D games.
Assumptions[]
This article assumes a client-server model where the server is authoritative with state and runs a fixed update loop. It also assumes that you have a decent protocol already in place for sending packets back and forth between the server and clients. Since these methods are designed to cut bandwidth down massively, it's recommended that you also read the Binary Packet article which covers a packet writer/reader with minimum bandwidth in mind. This article assumes that the server has a reliable protocol to send data to the clients, either TCP or reliable UDP. This will become obvious later.
The examples will use C#.
Introduction[]
In a multiplayer game, if a tree falls in a forest and no one is around to hear it, does it cost bandwidth? The ideal answer is no. So what does a client need to know about? In a 2D game, a client needs state for everything in their viewport and sometimes just outside their viewport. A spatial partitioning system on the server solves that problem by querying for entities that are within the area of interest.
So once we have a list of entities how do we decide what to send to a player? Often in games entities have state that doesn't change or changes infrequently. For instance, in an RPG game a player's name, equipment, stats, and current stat modifiers either don't change or they change only after specific actions or time limits. Sending this information to clients every update would be wasteful.
So when does a client need to know about all this state? I'm going to introduce you to Bob. You've never met Bob. As he walks through the door you notice he has black hair and a red shirt. You didn't need this information (state) before that point. The same rules apply in a multiplayer game. As entities get close to a player the server sends a full state packet. This gets the client up to date with the entity. As the entity stays within range the server needs to inform the client of any changes to that entity. If the entity leaves the range of interest it's forgotten about. That's all there is to it. The rest of this article will explain a possible approach to achieving that.
Full and Delta State Packets[]
You can ignore this Entity class for now. It's quick overview of methods that we'll be filling in later.
public class Entity {
public void SerializeFull(Packet packet) { }
public void SerializeDelta(Packet packet) { }
public bool HasDeltaState() { }
}
As mentioned in the introduction clients only need the full state when they first see an entity. After that point they need the information that changes known as the delta state.
In order to track if a client needs a full state or a delta state for an entity we can use two sets.
private HashSet<Entity> knownEntities = new HashSet<Entity>();
private HashSet<Entity> fullStateEntities = new HashSet<Entity>();
The first set is all the entities the client has the full state for. The second set is entities the client has just been introduced to and hasn't gotten a full state for. When building packets for a client you serialize the full state for all the entities in the fullStateEntities set then you serialize the delta state for all the knownEntities. You then move all the fullStateEntities into the knownEntities set and clear the fullStateEntities.
packet.WriteEventID(ServerEvents.EntityUpdate);
packet.WriteByte(fullStateEntities.Count + knownEntities.Count(e => e.HasDeltaState()));
packet.WriteByte(forgetEntities.Count);
foreach (Entity entity in fullStateEntities) { entity.SerializeFull(packet); }
foreach (Entity entity in knownEntities) { if (entity.HasDeltaState()) { entity.SerializeDelta(packet); } }
foreach (Entity entity in forgetEntities) { packet.WriteUInt(entity.ID); }
knownEntities.UnionWith(fullStateEntities);
fullStateEntities.Clear();
How do we decide what entities to insert into the fullStateEntities set though? For each of your clients you need to query for which entities are of interest. In the most basic sense this is the entities within range of the player or camera and usually involves querying a spatial partitioning system. For each of the returned entities check if it's a known entity. If you're not using a spatial partitioning system then you merely iterate over all the entities and perform the check. If it's not a known entity then you need to insert it into the fullStateEntities set. This operation is normally a method called LearnEntity in the client class.
public void LearnEntity(Entity entity) {
if (forgetEntities.Contains(entity)) {
forgetEntities.Remove(entity);
knownEntities.Add(entity);
return;
}
if (knownEntities.Contains(entity)) { return; }
fullStateEntities.Add(entity);
}
On the flipside how does the client forget about entities? Obviously if an entity travels away from the client or the client moves away from an entity after a while it's not useful to know about. Since clients have a list of known entities you can iterate them and do a test to see if they're outside the clients area of interest then remove them. This operation is normally a method called ForgetEntities in the client class.
private HashSet<Entity> forgetEntities = new HashSet<Entity>();
public void ForgetEntity(Entity entity) {
if (fullStateEntities.Contains(entity)) {
fullStateEntities.Remove(entity);
return;
}
forgetEntities.Add(entity);
}
public void ForgetEntities() {
foreach (Entity entity in knownEntity) {
if (entity.MinX > aabb.MaxX || entity.MaxX < aabb.MinX || entity.MinY > aabb.MaxY || entity.MaxY < aabb.MinY) {
ForgetEntity(entity);
}
}
}
The axis-aligned boundary box (AABB) in the last code snippet refers to the area a unit would have to leave in order to be forgotten about. It's often slightly larger than the area of interest so that units can't quickly come into view causing a full state packet then immediately leave. This stop full state packets from getting sent under circumstances where a player might simply be strafing back and forth in and out of the client's interest.
Since these operations, learning and forgetting entities, don't rely on the update loop of the server they can be ran at any given interval. They can even be ran separately of one another. You could make clients run the learn entities algorithm every second then run the forget entity function every five seconds. Or you can do batches, like 20 clients, at a time. The examples listed are designed so they can run separately of one another. For this reason the full implementation rarely has any performance impact and is essentially free even with thousands of entities.
Serialize Full[]
When serializing an entity you normally have a unique identifier, often an integer. This is followed by other special data related to that individual entity. It might have a position, a velocity, health, or other data. The full state is all that information written to a packet.
public void SerializeFull(Packet packet)
{
packet.WriteUInt(id);
packet.WriteByte(entityType);
packet.WriteString(name);
packet.WriteSingle(position.X);
packet.WriteSingle(position.Y);
// ...
packet.WriteByte(health);
}
When a client receives this data they'll perform a lookup on the unique identifier. So on the client-side you'll have:
Dictionary<uint, Entity> idToEntity = new Dictionary<uint, Entity>();
public void KnownEntity(uint id)
{
return idToEntity.ContainsKey(id);
}
public void LearnEntity(uint id, Entity entity)
{
idToEntity.Add(id, entity);
}
public void ForgetEntity(uint id)
{
idToEntity.Remove(id);
}
public Entity GetEntityByID(uint id)
{
return idToEntity[id];
}
Ignoring the error handling for processing the packet on the clients you'll have something that resembles:
public void ProcessPacket(Packet packet)
{
// ...
uint eventID;
packet.ReadEventID(out eventID);
switch (eventID)
{
// ...
case ServerEvents.UpdateEntities:
uint numberOfEntities = packet.ReadByte();
uint numberOfEntitiesToForget = packet.ReadByte();
for (uint i = 0; i < numberOfEntities; ++i)
{
uint id;
packet.ReadUInt(out id);
if (!KnownEntity(id))
{
// Full state
byte entityType;
packet.ReadByte(out entityType);
// Use an object factory to create the new entity given entity type and pass in the id
entity.DeserializeFull(packet);
LearnEntity(id, entity);
}
else
{
// Delta State
entity = GetEntityByID(id);
entity.DeserializeDelta(packet);
}
}
for (uint i = 0; i < numberOfEntitiesToForget; ++i)
{
uint id;
packet.ReadUInt(out id);
ForgetEntity(id);
}
break;
}
// ...
}
Basically in the ProcessPacket method it's checking if the entity doesn't exist in the known entities collection then it's a new entity and thus a full state update. A new entity is created and the packet is passed off so that the entity can read its information. Then at the end the entity is learned about by inserting it into the known entities collection. If it's already in the collection of known entities then it'll simply lookup the object with the unique identifier and run the DeserializeDelta method.
Serialize Delta[]
If your intention is to send only what changes with each entity then you have to keep track of them. This can be done for all the properties an entity might have or it can be done for a select few. A technique is to store a boolean indicating if the value changed. So when serializing the data you write a boolean before writing the data to say if it's needed. If you're not using a bit based binary packet you might use a bit flag in a single byte in order to save space.
public void SerializeDelta(Packet packet)
{
packet.WriteUInt(id);
...
packet.WriteBool(healthChanged);
if (healthChanged) packet.WriteByte(health);
packet.WriteBool(equipmentChanged);
if (equipmentChanged)
{
// Serialize all the equipment data
}
}
On the client side when this packet is read in it'll see the bool for health and if it's true it'll read the health value. The equipment change example shows how a single Boolean can encompass a large set of values that rarely change. Remember this is all in an effort to save bandwidth.
Example[]
Pretend your game was completely generated on the server and the client just got the entity data and placed it in the game world. This is the most extreme case where these algorithms would help. Full state data would update the whole game world including static objects then moving objects and other dynamic objects would get updated with the included delta data. The player could move around and entities would be loaded and removed as they moved around. Pretend other players in the game had customized characters. The full state would contain all that data then only their position, velocity and actions would be transmitted after that point.
Other Concepts[]
The algorithms described here also have another use that's often forgotten about. Pretend a unit teleports to an area they've never been to before. It's possible that there's a lot of full state data to send over. Imagine you set the area of interest very small around a player then every tick on the server expanded it to its normal range. For a 3D game or even a 2D game this would cause the closest objects in the game to be updated and synchronized first before any of the objects further away.
Conclusion[]
This article has described an approach for handling full and delta states using mostly O(1) algorithms in order to make it an almost free addition to any network game. It's just a quick introduction though. The concepts here can be expanded to lower bandwidth even further. A topic not covered, but often discussed is line of sight. That is sending clients only the data for entities they can directly see and not just ones around them. It's possible for an entity in a game to be up a floor or on the other side of a wall where knowing that they're there isn't really that important, but the actions they perform that generate sounds are. It's hoped that this article gives a basis though for venturing into those kinds of ideas.
Also if you really want to minimize the data sent you'll want to read that binary packet article linked in the introduction since sending large data types is often going to hurt a lot even with this optimization.