Optimizing large amounts of entities

So I have a case right now where I'm dealing with around 1,000 entities (testing for worst case) around the map. For the client, it takes around 0.5ms to deserialize the info from the server about these 1,000 entities (positions and rotations), and then another 1.5-2ms to apply transform.positions and transform.rotations for these 1,000 entities every single tick.

My question is, how can I optimize this? I'm thinking that every tick while the server is going through entities and serializing them, it could possibly check the distance between that player and the current entity it's serializing. If they're too far apart, just don't even bother serializing it. (so the player doesn't have to deserialize it and apply positions/rotations.)

Maybe I could also implement another thing where if the entity hasn't moved since the last tick, the server again won't even bother to serialize it for the client(s).

I'd like to hear some opinions about this before I go and implement something that could be garbage and create tons more problems than there already is.

(Ps. Most of these entities have rigidbodies on the server, not on the client. Server just sends position/rotation data to clients as mentioned above.)

 

You can and should implement something so each client will not receive the data for all entities.

Simplest would be, use the distance and based on it either serialize with less frequency or don't serialize at all.
More complex approach could be using line of sight and similar techniques or more complex grid types like hex grids/consider game map ...

Depending on your multiplayer library, I could give you pointers on how to achieve it. If you are using DOTS netcode then you should modify the serialization core.

On MLAPI there is a method to set visibility of objects for players and on uNet you could use something similar to the proximity checker however its performance is not the best.

Some additional pointers
GDC Vault - I Shot You First: Networking the Gameplay of HALO: REACH this describes how a complex priority system can be used. You probably don't need this.
Replication Graph | Unreal Engine Documentation this is the system Epic made for fortnite and there are many other examples so you are for sure not off the path at all.

 

My netcode is built from the ground-up.

so just to get an idea of what you're saying, some basic logic psuedo-code would look something like this?:


if (entityDistanceToPlayer <= maxDistance) {

if (!entityRigidBody.isSleeping()) {

SerializeToBuffer;
​

}​

}

something basic like this?

https://docs.unity3d.com/ScriptReference/Vector3-sqrMagnitude.html


Grid-based stuff also looks pretty cool, but I would really have no clue how to even implement that in the first place.

 

Yes if it is custom then I would suggest at minimum have something like what you had above but preferably have another distance which you send with a lower frequency to it so if you update 20 times a sec then update those further away with 10 times a sec. this said if you are interpolating physics objects, that might be more challenging in that situation.

Also grids are not that hard to implement if you are smart enough to do your own networking. Also other than this use a thin binary format for serialization of the data and quantize the values. gafferongames.com has a set of good articles if you are not already following them to synchronize rigidbodies on the network.

 

How does (de)serialization work? I hope you're not doing this through json like some geezers

It also depends on how the objects are identified in the array... For example, I assign the ID of a network entity as the array is filled (up to 1000), if the object is deleted, the reference to it in the array simply becomes null. For a new object, I just look for the first empty reference in the array and get the index (id).

When getting new information about an entity, I base it on the index (id) ( entities[net_id].NetworkUpdate() ), so it turns out to update the information without unnecessary cycles

I synchronized 1000 entities over the network with a frequency of 66 updates per second for each object with drawdowns of 15-20% of the norm (60 fps norm), then I added diff-compression (only changed entity data is sent) and this significantly reduced the amount of data sent and the fps drop

 

Unfortunately what I described might not be viable. Serializing 1,000 entities already takes around 1-2 milliseconds (because you have to grab positions and rotations and stuff). It would take way too long to do that same serialization looped for every player on the server since I still actually have to grab the positions of the entities to check the distance. Unless I'm just misunderstanding this concept?

 

Another question. If I'm only updating entities to the player, when the entity is modified/moved. Obviously I'm going to have to use TCP to send these messages, right?

 

You can use reliable UDP to update entities. See the replication graph in unreal engine's documentation to see how you can do this very efficiently.

Regarding how to decide what to send to which player , well yes this is a CPU intensive operation but if you don't do the most naive algorithm then it can be fast enough. Almost all MMOs do this and many multiplayer games do it as well. take a look at "I shot you first" video on GDC valut (it is free). That's a priority based system which is another way of doing it.

you don't have to reserialize every entity for every player so you serialize all of them once and then choose the entities each player needs. if the player cannot receive the data for all entities anyways you have to spend some even more CPU time on the server to make the experience possible to run. also keep in mind that serialization can happen in a parallel thread and sending selectively can happen by doing something like this as the easiest and probably ok enough performance-wise way.

Keep a list of interested players for each entity. once per second/few seconds depending on movement speed, update all entity interest lists based on an algorithm which can be say a KDTree of players which takes the players in distance x and then until the next interest selection, just send to all players in the interest list regarding the distance.

Something like this

each network tick
serialize all entities and send the all players in the interest list for the entity

with a much lower frequency update the interest list per entity by using a good spatial data structure like a grid/KDTree/any other area of interest management algorithm.

You can probably leverage burst and jobs for a good part of this too if you are not doing so already.

In this way the updates could be unreliable too. in the case of fortnite they have to be reliable with replication graphs because they try to only send something to you when you absolutely need to receive it. but they send updates from players to server in an unreliable manner too. but they send updates of x prev frame and the server sends acknowledgements back and says until which frame it received. This assumption of update sending from clients comes from unreal's networked character movement script in their docs and this is how many games in the FPS genre do this anyways which works well for too many updates sent too fast.

Many MMOs have lower tick rates exactly due to these things being process intensive and CPU heavy nature of the game logic in general and they limit their mechanics to cope with it.

 

So it wouldn't work if I only serialized an entity and sent it to a player if the entity was modified/moved that tick and it was within range of the player, because once the player comes back into update distance of that entity, but it hasn't moved since, then the client now has the wrong position for the entity.

How do you go about solving this? Do you literally need to update every entity to the players x times per second no matter what?

And how should I go about implementing a reduced tickrate like that? Since my code runs every fixedupdate. Should the client perform checks if the entity has moved or not, and if it hasn't moved since the last update, then don't perform a .position change on it?

 

What you want to do on the server is keep track of each entity which is currently in the area of interest of the player. If an entity enters the interst range of a player you add it to the tracked list and in addition mark it so that when your create your next message you include data about the new entity. For entities inside the interest range you can send them only if they were modified.

So your package will contain:
- Information about all entities which entered the interest range of the player
- Information about all entities inside the interest range which changed during the last tick.
- (optional) Ids of entities which left the interest range if you want to hide/disable them on the client.

 

So to clarify, right when an entity enters the interest range of a player, the server should automatically push an update to that specific player with that specific entity, in-case it was modified outside of the interest range when the player wasn't getting updates for it, right?

 

Correct

 

if you send updates as unreliable messages then sending only if they are modified increases the chance that they receive a change later than the case that you send it x times a second when in area of interest, but sending it as a reliable message and only when it really changed is not empty of costs too.

Sending it as unreliable means if it is not received then you don't keep it in any buffer and no other messages wait for it.
sending it as reliable without order only requires ack from the player and house keeping on the server and a buffer for reliable messages which are not sent.
sending as reliable ordered/sequenced means all packages after it will wait
sending it as a reliable message specific to state syncs which only sends the last version of something if for example a previous version is not delivered or more accurately its ack is not received (uNet transport has a channel for this which i forgot its name, maybe it was state sync) means you can send only when modified and the last version will be sent and a buffer of the message will not be kept so you'll not send old useless updates needlessly.