I have had a very busy Christmas break. I basically switched my day job schedule to coding this project. Not on purpose mind you, just every time I seem to sit down I am compelled to work on it just a little more. And then it’s lunch time, and then it’s time to work out… and then it’s dinner time… and then it’s shower time, etc.
I’ve decided to make these optimizations in increments as there’s a lot to be done and I want to do them in stages that I can understand.
It’s the danger zone!
The first step was splitting my map into more finer grained zones. We are exporting UE5’s landscapes which breaks the map into 126×126 meter meshes. Previously, I was creating two sensors per 126x126m chunk. One for a “local” sensor that was the same size as the 126x126m chunk, and another that spanned 3×3 of those.
I’ve now broken this into three zones of interest, each section of the landscape mesh is further broken into 3×3, so now we have 9 zones per 126x126m. I’ve also added a little bit of overlap so in the future we handle transitions between the zones smoother if necessary. Here’s what it looks like with some ascii art:
One constraint that these visibility zones have is that ranged attacks should not be greater than a single zone (42~48m) (for reasons I’ll get into below). But when we implement Field of View (FoV) culling, we will still want to probably keep all people in zone 2 visible, regardles of whether they are in our FoV.
Let’s use an example, say we are in Z1 cell [1,1], on the border of [1,0]. An attacker is in Z1 [1,2] on the border/edge of [1,1]. If we are facing the opposite way and we cull their information, they can still hit us if our range of attack is > 42~48 meters. This is probably not what we want, so we will want to keep our range of attacks in mind when culling players by distance and FoV.
Creating these additional zones was quite easy to do with the current setup and I only had to adjust splitting chunks further:
while(Landscape.NextLandscapeChunk(LandShape))
{
JPH::BodyCreationSettings LandSettings(LandShape, RVec3::sZero(), JPH::Quat::sIdentity(), EMotionType::Static, physics::Layers::NON_MOVING);
auto LandscapeBody = BodyInterface.CreateBody(LandSettings);
auto BodyID = LandscapeBody->GetID();
BodyInterface.AddBody(BodyID, EActivation::DontActivate);
JPH::Vec3 LandscapeCenter = LandscapeBody->GetShape()->GetLocalBounds().GetCenter();
JPH::Vec3 LandscapeSize = LandscapeBody->GetShape()->GetLocalBounds().GetExtent();
// Y might be a plane, so too small for the convex radius (.05)
if (LandscapeSize.GetY() < 20.f)
{
LandscapeSize.SetY(20.f);
}
BodyCreationSettings ZoneTwoSensorSettings(new BoxShape(LandscapeSize), LandscapeCenter, Quat::sIdentity(), EMotionType::Static, Layers::SENSOR);
ZoneTwoSensorSettings.mIsSensor = true;
auto ZoneTwoSensor = BodyInterface.CreateAndAddBody(ZoneTwoSensorSettings, EActivation::DontActivate);
BodyCreationSettings MultiSensorSettings(new BoxShape(LandscapeSize*3), LandscapeCenter, Quat::sIdentity(), EMotionType::Static, Layers::SENSOR);
MultiSensorSettings.mIsSensor = true;
auto ZoneThreeSensor = BodyInterface.CreateAndAddBody(MultiSensorSettings, EActivation::DontActivate);
const uint8_t LandscapeChunkCount = 3;
const float ChunkSize = LandscapeSize.GetX() / LandscapeChunkCount;
const float ZoneOneSize = 48.f; // 48m sensor to allow overlap of the 42m chunks
// we split landscapes into grid of 3x3 so we can have finer grained sensors with a little overlap.
for (uint8_t x = 0; x < LandscapeChunkCount; x++)
{
for (uint8_t z = 0; z < LandscapeChunkCount; z++)
{
JPH::Vec3 SensorOffset((x-1)*ChunkSize, 0.f, (z-1)*ChunkSize);
JPH::Vec3 ChunkCenter = LandscapeCenter + SensorOffset;
BodyCreationSettings ZoneOneSensorSettings(new BoxShape(JPH::Vec3Arg(ZoneOneSize, LandscapeSize.GetY(), ZoneOneSize)), ChunkCenter, Quat::sIdentity(), EMotionType::Static, Layers::SENSOR);
ZoneOneSensorSettings.mIsSensor = true;
auto ZoneOneSensor = BodyInterface.CreateAndAddBody(ZoneOneSensorSettings, EActivation::DontActivate);
// register the landscape chunk and it's AoI sensors with ECS Physics Systems
auto Chunk = GameWorld.entity()
.set<level::MapChunk>({LandscapeBody->GetID(), x, z})
.set<level::ZoneOneSensor>({ZoneOneSensor})
.set<level::ZoneTwoSensor>({ZoneTwoSensor})
.set<level::ZoneThreeSensor>({ZoneThreeSensor});
Chunk.child_of(MapEntity);
ChunkCount++;
}
}
}
With the sensors properly setup per landscape mesh, we can move onto adding players into their visibility zones using the sensor collision detection.
ServerAreaOfInterestQuery.each([&](flecs::iter &It, size_t Index, level::MapChunk &Chunk, level::ZoneOneSensor &ZoneOne, level::ZoneTwoSensor &ZoneTwo, level::ZoneThreeSensor &ZoneThree)
{
if (ZoneOne.Sensor == InBody1.GetID() || ZoneOne.Sensor == InBody2.GetID())
{
Logger->Debug("Found Character {} Adding to ZoneOne Sensor {}", Character.id(), ZoneOne.Sensor.GetIndexAndSequenceNumber());
ZoneOne.Characters.emplace(Character);
}
else if (ZoneTwo.Sensor == InBody1.GetID() || ZoneTwo.Sensor == InBody2.GetID())
{
Logger->Debug("Found Character {} Adding to ZoneTwo Sensor {}", Character.id(), ZoneTwo.Sensor.GetIndexAndSequenceNumber());
ZoneTwo.Characters.emplace(Character);
}
else if (ZoneThree.Sensor == InBody1.GetID() || ZoneThree.Sensor == InBody2.GetID())
{
Logger->Debug("Found Character {} Adding to ZoneThree Sensor {}", Character.id(), ZoneThree.Sensor.GetIndexAndSequenceNumber());
ZoneThree.Characters.emplace(Character);
}
});
When a player leaves a zone we also capture it:
ServerAreaOfInterestQuery.each([&](flecs::iter &It, size_t Index, level::MapChunk &Chunk, level::ZoneOneSensor &ZoneOne, level::ZoneTwoSensor &ZoneTwo, level::ZoneThreeSensor &ZoneThree)
{
if (ZoneOne.Sensor == InBody1 || ZoneOne.Sensor == InBody2)
{
ZoneOne.Characters.erase(Character);
}
else if (ZoneTwo.Sensor == InBody1 || ZoneTwo.Sensor == InBody2)
{
ZoneTwo.Characters.erase(Character);
}
else if (ZoneThree.Sensor == InBody1 || ZoneThree.Sensor == InBody2)
{
ZoneThree.Characters.erase(Character);
}
});
Where it becomes interesting is during each game tick on the server we need to update the players visibility. We also need to capture which players are visible across these zones for combat visibility checks (e.g. two other players attacking each other that we can see). For this we use, flecs run instead of each for our system so we can do one iteration over the zones but capture the visibility in an unordered map across ALL zones.
GameWorld.system<level::MapChunk, level::ZoneOneSensor, level::ZoneTwoSensor, level::ZoneThreeSensor>("UpdatePlayerVisibility")
.kind(flecs::PreStore)
.write<character::Visibility>()
.run([&](flecs::iter &It)
{
// For each character (entity) we will have a set of entities they can see, this map of sets will be used for determining combat visibility
// we need to do this across all map chunks hence why we are using run instead of each here.
std::unordered_map<flecs::entity, std::unordered_set<flecs::entity, units::FlecsEntityHash>, units::FlecsEntityHash> CanBeSeenBy;
while (It.next())
{
auto ZoneOnes = It.field<level::ZoneOneSensor>(1);
auto ZoneTwos = It.field<level::ZoneTwoSensor>(2);
auto ZoneThrees = It.field<level::ZoneThreeSensor>(3);
for (size_t i = 0; i < It.count(); i++)
{
auto& ZoneOne = ZoneOnes[i];
auto& ZoneTwo = ZoneTwos[i];
auto& ZoneThree = ZoneThrees[i];
for (auto Character : ZoneThree.Characters)
{
if (!Character.is_alive())
{
continue;
}
auto& Visibility = Character.get_mut<character::Visibility>();
Visibility.AllNeighbors.insert(ZoneThree.Characters.begin(), ZoneThree.Characters.end());
if (ZoneOne.Characters.contains(Character))
{
Visibility.HighPriority.insert(ZoneOne.Characters.begin(), ZoneOne.Characters.end());
// Notice since we limited our selves with the ZoneOne.Characters.contains(Character),
// we still need to look into ZoneTwo.Characters for combat visibility, hence why we iterate over zonetwo here.
for (auto VisibleCombatNeighbor : ZoneTwo.Characters)
{
CanBeSeenBy[VisibleCombatNeighbor].insert(Character);
}
}
else if (ZoneTwo.Characters.contains(Character))
{
Visibility.MediumPriority.insert(ZoneTwo.Characters.begin(), ZoneTwo.Characters.end());
for (auto VisibleCombatNeighbor : ZoneTwo.Characters)
{
CanBeSeenBy[VisibleCombatNeighbor].insert(Character);
}
}
else
{
Visibility.LowPriority.insert(ZoneThree.Characters.begin(), ZoneThree.Characters.end());
}
}
}
}
CombatQuery.each([&CanBeSeenBy](flecs::entity DamageEntity, combat::ApplyDamage &DamageEvent)
{
// Instigator sees it
if (DamageEvent.Instigator.has<character::Visibility>())
{
auto& Visibility = DamageEvent.Instigator.get_mut<character::Visibility>();
Visibility.DamageEvents.insert(DamageEntity);
}
// Target hit obviously sees it
if (DamageEvent.TargetHit.has<character::Visibility>())
{
auto& Visibility = DamageEvent.TargetHit.get_mut<character::Visibility>();
Visibility.DamageEvents.insert(DamageEntity);
}
auto& SeesInstigator = CanBeSeenBy[DamageEvent.Instigator];
auto& SeesTarget = CanBeSeenBy[DamageEvent.TargetHit];
auto& SmallerSet = SeesInstigator.size() < SeesTarget.size() ? SeesInstigator : SeesTarget;
auto& LargerSet = SeesInstigator.size() < SeesTarget.size() ? SeesTarget : SeesInstigator;
// Iterate over the smaller set since we are looking for the intersection.
// Add all characters (spectators not directly hit/instigating) who are in the vicinity who can see it
for (auto Character : SmallerSet)
{
if (!Character.has<character::Visibility>())
{
continue;
}
auto& Visibility = Character.get_mut<character::Visibility>();
if (LargerSet.contains(Character))
{
Visibility.DamageEvents.insert(DamageEntity);
}
}
});
});
The final stage of this change is to serialize this data and send it to our players, that is done in our now refactored server state handling code:
void PlayerWorldStates::ApplyPlayerVisibility(logging::Logger &Log, FrameEntityCache &FrameCache, character::Visibility &PlayerVisibility)
{
// clear out previous data
States.GetStateAt(States.SequenceId).KnownPlayerEntities.clear();
Log.Debug("OnStore: Cleared KnownPlayerEntities attacks seq id: {}", States.SequenceId);
// check if this character can even see anything first
if (PlayerVisibility.AllNeighbors.size() <= 0)
{
return;
}
for (auto Neighbor : PlayerVisibility.HighPriority)
{
AddPlayerToKnownPlayerEntities(Log, FrameCache, VisibilityPriority::High, Neighbor);
}
for (auto Neighbor : PlayerVisibility.MediumPriority)
{
AddPlayerToKnownPlayerEntities(Log, FrameCache, VisibilityPriority::Medium, Neighbor);
}
for (auto Neighbor : PlayerVisibility.LowPriority)
{
AddPlayerToKnownPlayerEntities(Log, FrameCache, VisibilityPriority::Low, Neighbor);
}
}
void PlayerWorldStates::AddPlayerToKnownPlayerEntities(logging::Logger &Log, FrameEntityCache &FrameCache, VisibilityPriority Priority, flecs::entity Neighbor)
{
if (!Neighbor.is_valid() || !Neighbor.is_alive())
{
return;
}
// Use cached data instead of extracting from ECS components
const auto *CachedData = FrameCache.GetOrCache(Neighbor, &Log);
if (CachedData == nullptr)
{
Log.Warn("OnStore: Failed to cache entity {}", Neighbor.id());
return;
}
Log.Debug("Neighbor {} Has {} outgoing attacks", CachedData->EntityId, CachedData->OutgoingAttacks.size());
for (auto& Attack : CachedData->OutgoingAttacks)
{
Log.Debug("Neighbor {} Has {} outgoing attacks Instigator: {} Target: {}", CachedData->EntityId, CachedData->OutgoingAttacks.size(), Attack.Instigator.id(), Attack.TargetHit.id());
}
auto KnownPlayer = PlayerEntity{
.EntityId = CachedData->EntityId,
.Priority = Priority,
.Attributes = CachedData->Attributes,
.Traits = CachedData->Traits,
.Position = CachedData->Position,
.Velocity = CachedData->Velocity,
.Rotation = CachedData->Rotation,
.Equipment = CachedData->Equipment,
.Action = CachedData->Action,
.OutgoingAttacks = CachedData->OutgoingAttacks};
// do not re-add players if they've already been added at a higher priority.
if (States.GetStateAt(States.SequenceId).KnownPlayerEntities.find(KnownPlayer) != States.GetStateAt(States.SequenceId).KnownPlayerEntities.end())
{
return;
}
// get their previous data and see if they've been sent recently, if not increase their frames since sent by 1.
auto StalePlayer = States.GetStateAt(States.PreviousSequenceId()).KnownPlayerEntities.find(KnownPlayer);
if (StalePlayer != States.GetStateAt(States.PreviousSequenceId()).KnownPlayerEntities.end())
{
KnownPlayer.FramesSinceSent += StalePlayer->FramesSinceSent + 1;
}
States.GetStateAt(States.SequenceId).KnownPlayerEntities.insert(KnownPlayer);
}
While we aren’t doing anything YET with culling or sequence handling, the infrastructure is there so further optimizations will allow me to send updates every Nth tick instead of every tick, or cull players who are not visible.
There we have it, we just have one major MAJOR problem, I can’t fit more than a few “new” players into a single update packet!
Tracking players over multiple ticks
This was by far the trickiest part of the refactor. We are limited to about 1024 bytes per packet, and worst case scenario a brand new player entering visibility will be an (unoptimized) 170 bytes. Which is calculated by the following:
const size_t EquipmentSize = ((static_cast<size_t>(items::EquipmentSlot::MAX)-1) * (sizeof(ItemEntity)-sizeof(uint64_t)));
const size_t PlayerEntityMaxSize =
sizeof(uint64_t) + // player entity
1 + // game message type (EntityType_Player)
(4 * sizeof(float)) + // attributes struct
1 + // action (uint8_t)
EquipmentSize + // equipment vector (minus uint64 server entity id)
sizeof(units::Vector3) + // pos
sizeof(units::Vector3) + // vel
sizeof(units::Quat); // rot
So what I ended up doing for now is create a single “update” packet of the player’s state (their pos/rotation etc). Then every visible player gets put into new packet(s) called view_state. This view state is a vector of new/updated/leaving player entities. Meaning each tick where there’s at least 1 visible player, we’ll send 2 packets, one for the player’s own data, and one full of what the player can see. I may change this in the future to merge in N number of visible players into the update packet, but for now I made them separate to reduce complexity for lookups.
As a refresher, we track and send only deltas of what the player already knows. This works fine when there’s a single sequence Id to compare. We just compared Server is at X, Client is at X-N and send any new updates or things that changed since that last acknowledged tick. For example, let’s say the client is 2 ticks behind the server and the server is at tick 10, client sends an ack of seeing world state at tick 8 so now we just take what’s changed between tick 10 and tick 8 and send only those things that changed to the client. Easy peasy.
But what happens if we have multiple packets? Our world state sequences are only tracked for 32 iterations, meaning we clear/overwrite known state after 32 ticks. If we are sending, say 4-5 packets per tick, we are going to roll those 32 sequence ids over pretty quick.
The solution I came up with is to create a mapping of these additional packet Ids to the world state sequence id. Let’s say the player has about 15 visible players around them. The server sends the delta to the client at sequence id 1 as usual, but creates 2 packets with these visible players data, these updates are on a new channel (view_state, instead of update) and this channel has its own sequence ids. Internally, we keep a map of which players data was sent at which view_state sequence id which had their state captured at this world state sequence.
This ends up looking something like this:
/**
* @brief tracks which players were sent / ackd in which corresponding primary sequence id
*/
struct OverflowPacketInfo
{
uint8_t SequenceId = 0; // Which primary SequenceId this overflow was created at
std::unordered_set<uint64_t> PlayerEntityIds; // Which players were sent in this overflow packet
bool Ackd = false;
};
struct EntityState
{
/**
* @brief Acknowleges the client recieved the additional packets from the client to track which version of the player
* updates we should send the delta from
*
* @brief OverflowIds a vector of packet ids from the client
*/
void AckOverflowIds(std::vector<uint8_t> &OverflowIds);
/**
* @brief Inserts our player entity id into our maps so we can loook them up for Delta's and acknowledge them
* also helps track when they were last 'sent'.
*
* @param PlayerEntityId Player the owner player can see and needs to track for delta compression
*/
void InsertPlayer(const uint64_t PlayerEntityId);
/**
* @brief Returns a pointer to the world state for the player in question, if the player does not exist in our state we
* return a nullptr
*
* @param PlayerEntityId the PlayerEntity we need to look up
*/
const WorldState* GetPlayerFrom(const uint64_t PlayerEntityId);
// ...
std::array<WorldState, network::MaxSequenceId> States{}; // Our world states that we can do differentials against
std::array<bool, network::MaxSequenceId> Acks{}; // Our primary sequence ids that track whether the client saw the world state at a certain sequence id
// Overflow packet tracking
std::array<OverflowPacketInfo, MaxOverflowSequenceId+1> OverflowPackets{}; // Track info about each overflow packet ( we bundle players into these updates )
std::unordered_map<uint64_t, uint8_t> PlayerLastAckedOverflowId{}; // Key = Player entity id, Value = Last acked OverflowSequenceId for this player
uint8_t SequenceId = 0;
uint8_t OverflowSequenceId = 0;
}
Now instead of a simple sequence id => world state mapping, we have a more complex player entity mapping => overflow sequence id => world state mapping.
Our state serialization code now has to look up the player entity by id, figure out if it was sent out in some overflow packet, and then what overflow packet state that was created at so we can do a proper differential.
This ends up looking like this for updated entities:
// Handle Updated Players
for (const auto& UpdatedPlayer : Current->KnownPlayerEntities)
{
// Pre-calculate some sizes
size_t CurrentBuilderSize = CurrentBuilder->GetSize();
size_t NextPlayerSizeEstimate = PlayerEntityMaxSize;
auto PreviousPlayerState = States.GetPlayerFrom(UpdatedPlayer.EntityId);
if (!PreviousPlayerState)
{
// if we didn't find them, this is a new player already handled in CollectNewEntities
continue;
}
// Gaurunteed to find the player since we check in States.GetPlayerFrom that this state contains a valid state + player that isn't stale.
auto PreviousPlayer = PreviousPlayerState->KnownPlayerEntities.find(UpdatedPlayer);
// ...
if (PreviousPlayer->Position != UpdatedPlayer.Position)
{
auto PlayerPos = Game::Message::Vec3(UpdatedPlayer.Position.vec3[0], UpdatedPlayer.Position.vec3[1], UpdatedPlayer.Position.vec3[2]);
PlayEnt.add_pos(&PlayerPos);
}
// ...
}
A few extra steps, but not too terrible. We can then compare PreviousPlayer with UpdatedPlayer to see what changed. As you can see however, we now have to track which player was sent out in which packet, making it harder to merge into the main “update” packet.
Dynamically creating new packets
This part is a bit annoying, and made me kind of hate some of flatbuffers design decisions. Namely, you can’t serialize objects using different builders. You have to know up front that your data will fit in the builder you created. This makes it hard to serialize things in a hot path. You either have to start serializing and keep track of sizes to allocate new builders as you go, or iterate over all your objects once, get their sizes, figure out how many builders you need, then re-iterate over them to place them in the correct builders.
I don’t like doing the same work twice so I opt’d for the serialize and check sizes as you go approach. Again this all happens in our delta state logic. Let’s assume a player has connected and has already started receiving deltas.
void PlayerWorldStates::DeltaKnownPlayers(logging::Logger *Log, std::vector<flatbuffers::FlatBufferBuilder> &Builders, const uint64_t ServerTime, const uint8_t CurrentSequenceId, const uint8_t LastAckdSequenceId)
{
auto Current = &States.GetStateAt(CurrentSequenceId);
auto Previous = &States.GetStateAt(LastAckdSequenceId);
Builders.emplace_back(flatbuffers::FlatBufferBuilder(network::MaxNetworkPacketSize)); // this Builder is specifically for the player update
CollectCurrentPlayerDelta(Log, Builders.back(), Current, Previous, ServerTime, CurrentSequenceId);
std::vector<flatbuffers::Offset<Game::Message::Entity>> NewEntities{};
std::vector<flatbuffers::Offset<Game::Message::Entity>> UpdatedEntities{};
std::vector<uint64_t> OutEntities{}; // we can only collect out entities here against our previous known state from our primary update packet, but we will add them
CollectOutEntities(Current, Previous, 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);
// create new builder for view_state packet
Builders.emplace_back(flatbuffers::FlatBufferBuilder(network::MaxNetworkPacketSize));
CollectNewEntities(Log, Builders, ServerTime, Current, NewEntities);
auto* CurrentBuilder = &Builders.back(); // CurrentBuilder MAY not be finalized yet
size_t CurrentBuilderSize = CurrentBuilder->GetSize();
// Check if we have room for at least one more player before we allocate a whole new packet (add +1 to entities size to see if that would put us over the limit)
auto BuilderPlusNextPlayerSize = CurrentBuilderSize + ((NewEntities.size() + 1) * PlayerEntityMaxSize) + (OutEntities.size() * sizeof(uint64_t));
if (BuilderPlusNextPlayerSize > network::MaxNetworkPacketSize)
{
auto VectorOfEntities = CurrentBuilder->CreateVector<Game::Message::Entity>(NewEntities.data(), NewEntities.size());
auto VectorOfOutEntities = CurrentBuilder->CreateVector<uint64_t>(OutEntities.data(), OutEntities.size());
ViewableStateBuilder ViewStateBuilder(*CurrentBuilder);
ViewStateBuilder.add_in_entities(VectorOfEntities.o);
ViewStateBuilder.add_out_entities(VectorOfOutEntities.o);
auto FinishedViewState = ViewStateBuilder.Finish();
Game::Message::ServerCommandBuilder ServerCommand(*CurrentBuilder);
ServerCommand.add_opcode(Game::Message::ServerOpCode_UpdateOverflow);
ServerCommand.add_sequence_id(States.OverflowSequenceId);
ServerCommand.add_server_time(ServerTime);
ServerCommand.add_view_state(FinishedViewState);
CurrentBuilder->Finish(ServerCommand.Finish());
States.IncrementOverflowSequence();
Builders.emplace_back(flatbuffers::FlatBufferBuilder(network::MaxNetworkPacketSize));
NewEntities.clear();
OutEntities.clear();
}
bool bCanThrowAway = CollectUpdatedEntities(Log, Builders, ServerTime, Current, NewEntities, OutEntities);
if (!bCanThrowAway)
{
Builders.pop_back(); // throw it away as it was unneeded due to loop conditions
}
}
We create a vector of builders and allocate them as we go. Our first builder is for the players state. CollectCurrentPlayerDelta can simply collect the state and finalize that builder in one go.
Next we move onto collecting deltas of players who left the players visibilty, CollectOutEntities does this and we actually only need a vector of uint64_t player entity values. So no builder required here.
Now we move on to CollectNewEntities, so we allocate a new builder before heading into that method.
// Handle never seen before players
auto* CurrentBuilder = &Builders.back();
for (const auto& NewlySeenPlayer : Current->KnownPlayerEntities)
{
// Since it's in our overflow state we need to find where we last sent it out.
const WorldState* Previous = States.GetPlayerFrom(NewlySeenPlayer.EntityId);
if (Previous)
{
auto PreviousPlayer = Previous->KnownPlayerEntities.find(NewlySeenPlayer);
if (PreviousPlayer != Previous->KnownPlayerEntities.end())
{
// we've already seen this player and updates will be handled as a diff, not a new entity
continue;
}
}
size_t PlayersDamageEventSize = DamageEventSize * NewlySeenPlayer.OutgoingAttacks.size();
// If we would overflow this builder, we will need to create a new buffer and update our index
const size_t ApproximatePlayerSize = PlayersDamageEventSize + PlayerEntityMaxSize;
Log->Debug("Approximate player msg size: {}, Current Buffer size: {}", ApproximatePlayerSize, CurrentBuilder->GetSize());
if (CurrentBuilder->GetSize() + ApproximatePlayerSize >= network::MaxNetworkPacketSize)
{
auto VectorOfEntities = CurrentBuilder->CreateVector<Game::Message::Entity>(NewEntities.data(), NewEntities.size());
ViewableStateBuilder ViewStateBuilder(*CurrentBuilder);
ViewStateBuilder.add_in_entities(VectorOfEntities.o);
auto FinishedViewState = ViewStateBuilder.Finish();
Game::Message::ServerCommandBuilder ServerCommand(*CurrentBuilder);
ServerCommand.add_opcode(Game::Message::ServerOpCode_UpdateOverflow);
ServerCommand.add_sequence_id(States.OverflowSequenceId);
ServerCommand.add_client_ack_id(States.ClientSequenceId);
ServerCommand.add_server_time(ServerTime);
ServerCommand.add_view_state(FinishedViewState);
// Log->Debug("Sending non-delta update to client");
CurrentBuilder->Finish(ServerCommand.Finish());
States.IncrementOverflowSequence();
NewEntities.clear(); // make sure we clear our entities so when we return we have the correct left over entities
Builders.emplace_back(flatbuffers::FlatBufferBuilder(network::MaxNetworkPacketSize));
CurrentBuilder = &Builders.back();
}
// serialize differences and go back to top of loop until no more players.
// ...
}
We have to check if our builder has enough room left, so we kind of guesstimate how much space is left, if we don’t have room we serialize our current list of new entities and finalize the builder. We then increment our overflow sequence number, clear out the entities, allocate a new builder and set CurrentBuilder to that and continue on with our loop.
Now, when we exit this method we still may have some unfinished entities, so we do a check in DeltaKnownPlayers to see what’s left over and whether we should finalize that buffer before going into CollectUpdatedEntities.
Inside of CollectUpdatedEntities we iterate over our updated entities and see if we need to handle the out entities / new entities that were left over. If we do, we finalize that builder and continue adding to our UpdatedEntities vector. Finally at the end when we exit the loop we do one last check to see if we have data left over to stuff into a builder that needs finalizing:
// see if we need to make a final packet
if (UpdatedEntities.size() + NewEntities.size() + OutEntities.size() == 0)
{
return bBuilderIsFinalized;
}
// Final packet, as we had either updated entities or left over new / out entities
Log->Debug("Final packet builder size: {} needs to add {} entities",CurrentBuilder->GetSize(), UpdatedEntities.size());
auto UpdatedEntityVector = CurrentBuilder->CreateVector<Game::Message::Entity>(UpdatedEntities.data(), UpdatedEntities.size());
if (bRequiresOutOrNew)
{
NewEntityVector = CurrentBuilder->CreateVector<Game::Message::Entity>(NewEntities.data(), NewEntities.size());
OutEntityVector = CurrentBuilder->CreateVector<uint64_t>(OutEntities.data(), OutEntities.size());
}
ViewableStateBuilder ViewStateBuilder(*CurrentBuilder);
ViewStateBuilder.add_updated_entities(UpdatedEntityVector.o);
if (bRequiresOutOrNew && NewEntities.size() > 0)
{
ViewStateBuilder.add_in_entities(NewEntityVector.o);
}
if (bRequiresOutOrNew && OutEntities.size() > 0)
{
ViewStateBuilder.add_out_entities(OutEntityVector.o);
}
auto FinishedViewState = ViewStateBuilder.Finish();
Game::Message::ServerCommandBuilder ServerCommand(*CurrentBuilder);
ServerCommand.add_opcode(Game::Message::ServerOpCode_UpdateOverflow);
ServerCommand.add_sequence_id(States.OverflowSequenceId);
ServerCommand.add_server_time(ServerTime);
ServerCommand.add_view_state(FinishedViewState);
CurrentBuilder->Finish(ServerCommand.Finish());
States.IncrementOverflowSequence();
bBuilderIsFinalized = true;
return bBuilderIsFinalized;
}
We return a boolean here because back in DeltaKnownPlayers we need to check if we allocated a builder but never put anything into it. If it was empty, we’d end up sending out a packet with no data, so we do a check here and discard it.
bool bCanThrowAway = CollectUpdatedEntities(Log, Builders, ServerTime, Current, NewEntities, OutEntities);
if (!bCanThrowAway)
{
Builders.pop_back(); // throw it away as it was unneeded due to loop conditions
}
Now we can send out multiple packets and the client can read them in, acknowledge which ones it recieved and send that back in it’s client to server update packet. We just added a field to our ClientStateBuffer and as they come in, add to the vector to keep track of which overflow/view_state packets the client saw. Then send that back to the server at the end of the frame.
Needless to say this was a massive amount of work, but in the end I’m able to get (at least!) 40 concurrent players running around. I started my server and 40 headless bots and connected my UE5 front end to watch them all run around (below is a video of 20 of them):
Next up is adding some culling and possibly optimizing my data structures to minimize the sizes.
One idea is to create a mapping of server entity ids to uint16_t values, that way we don’t need to send 8 bytes PER entity but only 2. Entity id’s show up a lot (new/updated/removed) as well as damage events. So if there’s 5 damage events, that’s 40 bytes right there, instead of 10 bytes if we just reference players by uint16_t.
I should also probably quantize my floats, and not send velocity for the players but just have clients calculate velocity directly as we are updating their position information anyways?
Anyways, lots of room for improvement but I’m so happy I can run 40 concurrent players, starting to feel a little more massive even if we are no where near there yet!
a place to jot 