As I mentioned in my 1 year anniversary post, I’ve completed the WorldState system. This system is based off the Quake 3 Arena delta compression technique and will hopefully allow me to efficiently transmit state updates to clients.
If you want a general understanding with visuals, I recommend reading the link I posted to Quake 3.
For a quick TLDR:
- Server keeps a series of states (in my case 24 snapshots) per character where state includes:
- Their visibility set (i.e. what the character can see, NPCs, “Dynamic” structures (think catapults), and of course other players).
- For each player the user can see we store:
- Player attributes (health etc.)
- Player position/rotation
- Player entity id as seen by the server
- An array of their item slots (these will be from a global list the client has stored locally so we only need to transmit uint16_t (2 bytes) per “slot”). On deltas we only need to send if the slot changed and only send that changed slot detail!
- An array of actions they are currently performing (attacking/running etc.)
- For each player the user can see we store:
- The player’s current position and rotation, as seen by the server
- The player’s attributes (health, mana, shield etc.)
- Sequence Id of last acknowledge Id seen from the client
- Every tick the state is updated for every character using a flecs system.
- After updating the state, a delta is made from the last client acknowledged state, meaning we only send what’s changed and nothing more!
- Client sends it’s state Ack Ids in every input tick
- Client receives the servers state command packet and updates it’s local state and creates new entities, updates known entities, and removes entities that are no longer visible or in it’s area of interest.
The rest of this post will assume you some what grasp how that all works!
Server
When a user is spawned into the world they are immediately set a flecs component called: state::PlayerWorldStates. This struct is the series of 24 snapshots in a rolling array. Each sequence Id is an index into this array, meaning every 24 sequence ids we roll over back to zero.
This array contains a WorldState struct:
struct WorldState
{
WorldState()
{
KnownPlayerEntities.reserve(500);
KnownNPCEntities.reserve(200);
KnownStructureEntities.reserve(200);
};
units::Position PlayerPosition{};
units::Quat PlayerRotation{};
units::Attributes Attributes{};
std::unordered_set<PlayerEntity, EntityHash<PlayerEntity>> KnownPlayerEntities{};
std::unordered_set<NPCEntity, EntityHash<NPCEntity>> KnownNPCEntities{};
std::unordered_set<StructureEntity, EntityHash<StructureEntity>> KnownStructureEntities{};
// entities which should be removed by clients
std::unordered_set<uint64_t> OutEntities{};
};
On creation we reserve space for players, NPCs, and entities. We do this so we only have to allocate once.
There are only two flecs systems which deal with the players PlayerWorldState component. The ServerUpdateState system is executed after our physics system has run for the tick, which means each characters Position and Rotation and their Visibility component’s will all be up to date.
GameWorld.system<state::PlayerWorldStates, character::Visibility, units::Attributes, units::Position, units::Quat>("ServerUpdateState")
.kind(flecs::PreStore)
.each([&](flecs::iter& It, size_t Index, state::PlayerWorldStates &States, character::Visibility &Visibility, units::Attributes &Attributes, units::Position &Pos, units::Quat &Rot)
{
Log->Debug("ServerUpdateState: SeqId: {} Pos Now: {} {} {}", States.SequenceId, Pos.vec3[0], Pos.vec3[1], Pos.vec3[2]);
States.UpdateState(Visibility, Attributes, Pos, Rot);
});
The UpdateState method does pretty much what you’d expect, with the ApplyPlayerVisibility method simply clearing out whatever was at the current sequence id for this character and inserting the known player entities from the Visibility.Neighbors set of visible players.
auto &Current = States.at(SequenceId);
Current.PlayerPosition = Position;
Current.PlayerRotation = Rotation;
Current.Attributes = Attributes;
ApplyPlayerVisibility(Visibility);
The other system deals with creating the deltas, this method is a bit more advanced as we have to construct our FlatBuffers data struct as we are calculating the Delta. It was important that FlatBuffers was chosen for this very reason, FlatBuffers will not send un-set fields, meaning we lose no space by declaring properties of a struct and not sending them. For example here’s the entire “State” message FlatBuffer we send for each character:
table State {
in_entities:[Entity];
updated_entities:[Entity];
out_entities:[uint64]; // used for deleting from client, so only need server's id
// players data
health:float;
pos:Vec3;
rot:Quat4;
}
table Entity {
id:uint64; // server entity id, need to do correlation on clientside
type:EntityType;
player:PlayerEntity;
npc:NPCEntity;
structure:StructureEntity;
item:ItemEntity;
}
// ...
// TODO: optimize sending angles for pitch/yaw instead of Quat4s!
table PlayerEntity {
health:float; // 4 bytes
actions:[ActionType]; // 2 * N bytes
items:[uint16]; // 2 * 9 bytes // each index is an item slot starting from 0 being the head, shoulders, arms, hands, ring left, ring right, neck, left hand, right hand
pos:Vec3; // 12 bytes
rot:Quat4; // 16 bytes
}
So the State table includes Entity’s as arrays which can be one of player/npc/structure/item. What’s great is we don’t “waste” space by defining these types and not assigning to them. It makes defining these structures much easier.
To generate these FlatBuffer messages we call State.Delta(Builder):
void PlayerWorldStates::Delta(flatbuffers::FlatBufferBuilder &Builder)
{
uint8_t LastAckdSequenceId = (SequenceId + MaxSequenceId - 1) % MaxSequenceId;
auto FoundAck = false;
if (!WasAckd(LastAckdSequenceId))
{
FoundAck = FindLastAckedSequence(LastAckdSequenceId);
}
auto CurrentSequenceId = SequenceId;
// Update our SequenceId here so we can exit early if first run
SequenceId = (SequenceId + 1) % MaxSequenceId;
// If this is the first check or we haven't recv'd any acks yet, we need to send everything we see as-is.
if (bFirstRun || !FoundAck)
{
auto Idx = 0;
// if we just haven't got an ack yet, we need to send whatever index we are at.
if (!bFirstRun && !FoundAck)
{
Idx = CurrentSequenceId;
}
bFirstRun = false;
// Iterate over all KnownPlayers and create Entity->PlayerEntity details
// ...
for (auto Player : States.at(Idx).KnownPlayerEntities)
{
Game::Message::PlayerEntityBuilder PlayEnt(Builder);
// fill out entity
// ...
auto EntityFinished = Ent.Finish();
NewEntities.push_back(EntityFinished);
}
// TODO: Serialize NPCs and Structures
auto AllNewEntities = Builder.CreateVector<Game::Message::Entity>(NewEntities.data(), NewEntities.size());
Game::Message::StateBuilder Diff(Builder);
Diff.add_in_entities(AllNewEntities.o);
auto Pos = States.at(Idx).PlayerPosition;
auto PlayerPos = Game::Message::Vec3(Pos.vec3[0], Pos.vec3[1], Pos.vec3[2]);
Diff.add_pos(&PlayerPos);
// TODO: Switch to using angles
auto Rot = States.at(Idx).PlayerRotation;
auto PlayerRot = Game::Message::Quat4(Rot.vec4[0], Rot.vec4[1], Rot.vec4[2], Rot.vec4[3]);
Diff.add_rot(&PlayerRot);
Diff.add_health(States.at(Idx).Attributes.Health);
auto DiffResult = Diff.Finish();
Game::Message::ServerCommandBuilder ServerCommand(Builder);
ServerCommand.add_opcode(Game::Message::ServerOpCode_Update);
ServerCommand.add_sequence_id(CurrentSequenceId);
ServerCommand.add_state(DiffResult);
Builder.Finish(ServerCommand.Finish());
return;
}
DeltaKnownPlayers(Builder, CurrentSequenceId, LastAckdSequenceId);
}
This method has to figure out first what the last acknowledged ID was, if it doesn’t find one we simply return everything we know by iterating over all the known players serializing their data and adding to a new entities vector. We then serialize all our other data, set an Opcode and set the current Sequence Id so the client knows what to “ack” when it receives this state data.
If we DO have an acknowledged Sequence Id we have a bit more processing to do:
auto Current = States.at(CurrentSequenceId);
auto Previous = States.at(PreviousSequenceId);
std::vector<flatbuffers::Offset<Game::Message::Entity>> UpdatedEntities{};
std::vector<flatbuffers::Offset<Game::Message::Entity>> NewEntities{};
std::vector<uint64_t> OutEntities{};
// Just assume we won't have more than whatever the largest is here.
auto Size = (Current.KnownPlayerEntities.size() > Previous.KnownPlayerEntities.size()) ? Current.KnownPlayerEntities.size() : Previous.KnownPlayerEntities.size();
UpdatedEntities.reserve(Size);
NewEntities.reserve(Size);
OutEntities.reserve(Size);
// Iterate over all KnownPlayers and Previously known players to determine what needs to be updated vs added.
for (auto PreviousPlayer : Previous.KnownPlayerEntities)
{
auto Player = Current.KnownPlayerEntities.find(PreviousPlayer);
// We still see the other player, check if we need to update or not
if (Player != Current.KnownPlayerEntities.end())
{
Game::Message::PlayerEntityBuilder PlayEnt(Builder);
if (Player->Position != PreviousPlayer.Position)
{
auto PlayerPos = Game::Message::Vec3(Player->Position.vec3[0], Player->Position.vec3[1], Player->Position.vec3[2]);
PlayEnt.add_pos(&PlayerPos);
}
// ... add other stuff ... //
Game::Message::EntityBuilder Ent(Builder);
Ent.add_player(PlayerEntFinished.o);
Ent.add_id(Player->EntityId);
Ent.add_type(Game::Message::EntityType_Player);
auto EntityFinished = Ent.Finish();
UpdatedEntities.push_back(EntityFinished);
}
else
{
// TODO: We want to actually cache outentites and only send it if it's "true" after a certain period of time
// for performance reasons.
OutEntities.push_back(PreviousPlayer.EntityId);
}
}
// Loop again for new players that don't exist in our previous known player list
for (auto CurrentPlayer : Current.KnownPlayerEntities)
{
auto PreviousPlayer = Previous.KnownPlayerEntities.find(CurrentPlayer);
// we have a new player, need to add them
if (PreviousPlayer == Previous.KnownPlayerEntities.end())
{
Game::Message::PlayerEntityBuilder PlayEnt(Builder);
// ... add other stuff ... //
auto EntityFinished = Ent.Finish();
NewEntities.push_back(EntityFinished);
}
}
// annoying we have to create vectores before we can init our StateBuilder other wise we get !nested asserts
auto AllNewEntities = Builder.CreateVector<Game::Message::Entity>(NewEntities.data(), NewEntities.size());
auto AllUpdatedEntities = Builder.CreateVector<Game::Message::Entity>(UpdatedEntities.data(), UpdatedEntities.size());
auto AllOutEntities = Builder.CreateVector<uint64_t>(OutEntities.data(), OutEntities.size());
Game::Message::StateBuilder Diff(Builder);
// Conditionally add if we have anything to add to keep our buffer sizes smaller
if (NewEntities.size() > 0)
{
Diff.add_in_entities(AllNewEntities.o);
}
if (UpdatedEntities.size() > 0)
{
Diff.add_updated_entities(AllUpdatedEntities.o);
}
// ...
if (Current.PlayerPosition != Previous.PlayerPosition)
{
auto PlayerPos = Game::Message::Vec3(Current.PlayerPosition.vec3[0], Current.PlayerPosition.vec3[1], Current.PlayerPosition.vec3[2]);
Diff.add_pos(&PlayerPos);
}
// ...
auto DiffResult = Diff.Finish();
Game::Message::ServerCommandBuilder ServerCommand(Builder);
ServerCommand.add_opcode(Game::Message::ServerOpCode_Update);
ServerCommand.add_sequence_id(CurrentSequenceId);
ServerCommand.add_state(DiffResult);
Builder.Finish(ServerCommand.Finish());
}
Since we are using sets, we can pretty easily do differentials and build out what’s new, what’s removed, and what’s updated. That’s pretty much the entire logic of this method along with conditionally setting fields only if they have changed since the last acknowledged sequence id.
The rest of the flecs SendClientUpdates system takes this buffer and pushes it onto our socket queue to be sent over the socket thread to the awaiting client.
Client
The client logic is pretty straight forward, in the client game loop we pull the recieved message off the queue and process the command:
void PMOWorld::ProcessServerCommand(const Game::Message::ServerCommand *Command)
{
// Update our last known server state ack id, to be sent in next input packet
Player.set<network::ServerStateSequenceId>({Command->sequence_id()});
// ... error checking .. //
// Update our character where the server thinks we are so we can validate, only if it's changed
if (Command->state()->pos() != nullptr)
{
units::Position Position{Command->state()->pos()->x(), Command->state()->pos()->y(), Command->state()->pos()->z()};
Player.set<network::ServerPosition>({Position});
Logger.Info("Server Sees client at: {} {} {} for SeqId: {}", Position.vec3[0], Position.vec3[1], Position.vec3[2], Command->sequence_id());
}
// same with rotation //
// Add
if (Command->state()->in_entities() != nullptr)
{
for (auto It = Command->state()->in_entities()->begin(); It != Command->state()->in_entities()->end(); ++It)
{
auto Entity = *It;
switch(Entity->type())
{
case Game::Message::EntityType_Player:
AddNetworkPlayer(Entity);
break;
case Game::Message::EntityType_NPC:
break;
case Game::Message::EntityType_Structure:
break;
case Game::Message::EntityType_Item:
break;
default:
break;
}
}
}
// Update
if (Command->state()->updated_entities() != nullptr)
{
for (auto It = Command->state()->updated_entities()->begin(); It != Command->state()->updated_entities()->end(); ++It)
{
auto Entity = *It;
switch(Entity->type())
{
case Game::Message::EntityType_Player:
UpdateNetworkPlayer(Entity);
break;
// ... other NPC/Structure/Item etc here ... //
default:
break;
}
}
}
// Delete
if (Command->state()->out_entities() != nullptr)
{
for (auto It = Command->state()->out_entities()->begin(); It != Command->state()->out_entities()->end(); ++It)
{
auto Entity = *It;
Logger.Info("Deleting player {} from users' world.", Entity);
GameWorld.delete_with(static_cast<flecs::id_t>(Entity));
}
}
}
The create logic just spawns a new entity in our flecs World and gives it a network::ServerId component which matches the entity id of the flecs entity on the server (that way we can correlate the two). The update logic just finds the entity using that same ServerId and updates only the fields/components that changed, and the delete is handled in line as you can see above, deleting the entity from the game.
Of course there’s many optimizations to do here, we probably don’t want to immediately delete entities that are no longer visible but just hide them, and I also need to send angles instead of Quat4s as they are huge (16 bytes!). But this was enough for me to start getting the server to actually send updates to the client:
[2024-07-06 13:05:36.410] [test] [info] UpdateVelocity: Processing 1 inputs delta: 0.033575304
[2024-07-06 13:05:36.411] [test] [info] Char State: OnGround
[2024-07-06 13:05:36.411] [test] [info] PrePhysicsUpdate complete.
[2024-07-06 13:05:36.411] [test] [info] OnNewInputs: Inputs: 1
[2024-07-06 13:05:36.411] [test] [info] Got Server Command
[2024-07-06 13:05:36.411] [test] [debug] ServerSeqId: 19
[2024-07-06 13:05:36.411] [test] [info] Server Sees client at: 27.104364 0.93831694 0 for SeqId: 19
[2024-07-06 13:05:36.411] [test] [info] Processing Message
[2024-07-06 13:05:36.411] [test] [debug] ReliableEndpoint::SendMessage 454130525 sent 228 bytes of type: EncClientCommand
As we can see above in the logfile, the client now knows where the server thinks it is and at what sequence id. Going forward we’ll want to correlate these and do physics rollbacks once client prediction is in. But for now I just want to see a few characters in Unreal Engine running around together!
Butttttttttttt before I can do that I need to do some performance and load testing. (Surprise I already started). I need to make sure my extremely minimal design and features can actually handle a 100~200 characters. I haven’t even done distance checking or added NPCs or anything else to the world, so now is a good time to make sure the foundation will be able to handle the load.
My next post will cover how I am doing some performance testing, some tooling I’ll need to create and a few bugs I already found and fixed.
a place to jot 