NeREIDS Live Protocol and plans

Hi there ! This posts follows up the one about FLNetwork architecture. Here I’ll try to review the current state of the networking aspects of the NeREIDS application, independently of the FLNetwork layer.
I will try to keep these matters open-ended, and discuss a list of planned features. Comments are then pretty much welcome 😉

Client to Server

A NeREIDS Client following the live protocol should send input data along with perceived avatar state, on each game tick (each 32ms), to the server. The client messaging strategy consists of sending its input 4 times redundantly (Meaning it consistently sends the input from the 3 previous ticks and the current). This allows for a 3-packet-lost-in-a-row resilience while still losing no input data, at the expense of more consumed bandwidth, and the requirement that even the input from 3 ticks ago is still valid when received by the server, adding around 100ms to the overall latency if server operates on a tight, non-negotiable schedule (as it is the case for NeREIDS). I am considering lowering this value by default to 3x redundant only, same value than what Tribes used, as is explained in this paper again.
In the future anyway, I’d like to try to dynamically change the redundancy number, depending on available bandwidth (estimated from variations in packet round-trip-time), switching from 4x or 3x redundant (which I call 4:1 or 3:1) to 2:1 or 1:1. A client 2:1 strategy would then require about 2 times less bandwidth than 4:1, while still providing some packet-loss resilience. 1:1 could be used when bandwidth is really tight, but jitter should be estimated also, as high jitter (resulting in high packet loss or out-of-order ratio, out-of-order packets being also considered lost) would make 1:1 a totally inefficient strategy anyway.

This special effort towards player input reliability has two reasons. First is client-side prediction, which would diverge in case of input loss, meaning that the server would need to send an correction, and the client would need to recompute its situation, imposing a bigger strain on the server-to-client bandwidth as well as more CPU requirements on the client. Second is simply a matter of human interface design : Losing a player’s input is pissing off a player.

Wtf ?! I pressed that fuc freak fffffffire button !

Big time.

Server to Client

Each tick, NereidsSrv sends, to each connected client currently in the live protocol, an UDP packet about the frame that was just computed.
This packet contains :

    – NeREIDS packet filter. (This is the same 32 bits value we saw previously)
    – Message type “FLNETWORK_LIVE_FROM_SERVER”. (8 bits)
    – The Sequence index of the frame that was computed. (16 bits index. Okay, so it wraps around every 2048 seconds, but it is wrap-checked)
    – The Sequence index of the last valid client frame we’ve received until then. (16 bits also)
    – The Calibration helper value (16 bits, see below).
    – The number N of submessages embedded into that frame message (8 bits)
    Then N times a bit-packed submessage as follows :
    – A submessage type (4 bits)
    – A whole different range of things depending on the submessage type

The calibration helper value is a server-side computation of the difference, in milliseconds, between the reception of last client frame and the time when a frame with the same seq index would be computed on the server. It is hopefully positive, as a client needs to notify a server of its intended moves for a frame before the server ever computes that frame : once computed on the server indeed, a frame cannot be rolled back, nor can any event be applied back in time.
The server tries quite hard to remove the effects of jitter from the calibration helper value, so that it gives a consistent value against which a client can recalibrate (Recalibration and filtering of frames with valid calibration input has become quite a hairy matter, to avoid self-sustained desynchronization spirals).

Current implemented submessages :

      OUT_OF_SEQ_WARNING

    This submessage indicates that last frame report from the client was stamped with a frame index which was out of the acceptable range when received. It contains the invalid frame index, and the frame index difference between client and server when received : Typical values are either < 0 (too late, frame already wrapped up) or > 32 (more than 1 sec in the future, not acceptable)

      ENTITY_DEFINITION

    This submessage indicates that an entity (a creature, another player’s avatar, anything…) has come in range of the client’s zone of knowledge. It contains an id for this entity as well as the current controller (=0 if AI controlled, same as the id for the connection of the controlling player otherwise). At the moment, a client recognizing his own connection id (given when login was accepted) on an entity definition knows that it is in control of that entity (it becomes the current player avatar), but maybe another system will be used in the future, when character creation/selection gets implemented. The definition should also in the future come along with an entity “template”, e.g. one-time-defined racial attributes, etc.

      ENTITY_UPDATE

    At the moment, this submessage contains every property related to a given entity state (first data is the entity id, then comes the current state such as position, velocity, orientation, etc). It is planned that it comes along with an update bitfield, each bit that is set would indicate than some data is to be expected for a given subset of the entity state.
    Planned update bitfield :

      – bit 7 : entity controller changed, or AI decision changed (when controller=0, an AI tactical decision may be embedded into the state, with its tick of application)
      – bit 6 : entity had a game-defined event applied to it (state will include further flags defining the events to be updated and the tick of event application)
      – bit 5 : entity had a game-defined value modified (state will include further flags defining the values to be updated)
      – bit 4 : entity non-moving action changed (state will include current timestamp into the action, so that a client can render a given animation)
      – bit 3 : entity velocity changed, or entity experienced a position snap (state will also include current position)
      – bit 2 : entity non-moving sub-action changed, entity emitted a sound, or should display an effect (state will include current timestamp into the subaction or sound or FX playback)
      – bit 1 : entity body orientation or movement style changed (state will include movement style as well as 1 bit flag indicating if head orientation should be kept constant to body). Movement style is a value such as “standing/jumping/smimming…” it is needed there because the serialization of orientation depends on it : typically, on-ground entities would define orientation as a rotation relative to the “up” axis only, while some other states such as swimming underwater could use full 3D rotations.
      – bit 0 : entity head orientation relative to body changed AND absolute value changed.

To my mind, this list as displayed here is sorted in some kind of decreasing order of importance. The server should sort the entity needing updates based on a priority value reflecting this importance, as well as taking into account the distance from said entity to the client’s avatar. It should then be able to write updates into the packet depending on the priority : a given packet may be full before all updates are written, so the remaining, lower priority entities would be updated at a later time.

Planned submessages :

      REQUEST_ACK

    Client should be able to send different kinds of requests to the server, and this submessage indicates that that request was acked, along with data answering to it when needed.

      CHAT_EVENT_OOC

    Out-Of-Character chat event. Contains the connection id for the sender (0 is server), the chat channel, and the text to be displayed in-chat

      CHAT_EVENT_IC

    In-character chat event. Contains the entity id for the avatar (PC or NPC) who just spoke, some values for chat-style (yelling, whispering…), maybe in-game language, and the text itself.

      ENTITY_REMOVAL

    This submessage indicates that an entity has gone out of scope for this client and should be removed from the client’s lists. (No further updates will be sent anyway)

And probably more…

Client Rendering

So, the client has some authoritative states from the server for a given tick, and a few ticks worth of registered inputs that he’s the only one to know about at the moment. Now, this is all good and well, but what to render ? Positions in the past when server said so, or positions in the client most recent input time ?

If we went for an all-out rendering of server positions, we would be back to what was made several years ago with Quake. This was the first client-server protocol ever been used for an action game. As such, it laid the basis for all future networked action games. But there was a noticeable delay between a user pressing the “up arrow” key to the avatar effectively moving on the screen. “Noticeable”, as in every immersive world when you get a feel from the real world (how about hearing people eating popcorn at the movie’s ?), means “Disturbing”.

Then came “Client-side prediction”, which is a technique to counter the perceived lag between user input and avatar move : The client becomes able to render the player avatar ahead of the server authoritative decisions. Most of the time indeed, the client and server will agree on the client moves, so the client just assumes, temporarily, that those moves will be accepted, and we can render the avatar position as if all our inputs have been validated.
When it occurs every so often that the server disagrees on a particular move (such as when the local player’s avatar bumps into the avatar for another player, that he did not expect to be there at that tick), well, here is what happens :
Starting from the last server decision, the client reapplies subsequent moves enqueued from that point. The character will be snapped to a (hopefully slightly) different position, but we can smooth out this snap effect so that the player doesn’t feel too much of a difference, and everything looks fine.

Client side prediction means that we always render the player avatar “somewhere in the future” from the last valid frame received from the server.
Alright, but what about the other things to render in the game ? The terrain, the other players avatars, that AI-controlled NPC there, or an apple falling from that tree ?

Well, very dumb objects such as the falling apple can be extrapolated from their last valid position quite easily : just apply some physics to that apple client side, and voila, the client now also knows its position at whatever point in the future, such as, in the same time-line than his local avatar. (Well, there are discrepancies at the time where the apple just *starts to fall* but they can be smoothed out with some tricks).

So, we could imagine that we’ll also “extrapolate” other players avatars positions just like we did with the apple : add velocity to the avatar state sent by the server, start from there, physically apply that velocity as in your elementary physics class to each tick since that last valid position, and render that avatar in the same time-line.

First problem is, other players are bitches.
They would always add some unpredictable events to their avatar trajectories, events that would make our extrapolated positions desynchronize quite frequently. You know, such as stopping when we thought they’d continue at the same pace, or even switching directions ! Damn them… oh, that’s why we provided them with a keyboard and a mouse in the first place, right, but from a network point of view, this is becoming a problem. Well, maybe we could turn this into an “acceptable” problem ? Smooth out the frequent snaps, cross fingers and hope for the best…

Second problem is, some events, like an animation or a jump, may be visually shorter than our Round-Trip-Time.
If a player wants his avatar to jump, obviously this would be a nice thing if we could also see his avatar jump on our screen. But the server notified us of his jump “in the past”. So even if we eventually get notified of that past jump event, when it’s time for us to render his extrapolated position, he very well may be on the ground again.
That avatar could jump in the air for half a second all day long, if our RTT is more than half a second, we would render him back on the ground. The resulting look being an avatar standing still. All day long.

Now THAT is a game breaker, and we need another solution.

Well, the solution is : The client doesn’t render every object in the same timeline.

– The player avatar has processed the player moves => it is rendered with the last moves registered
– The entities for which the client is able to predict behaviors may be advanced in the same timeline => they are rendered with the last decisions registered
– The entities that are controlled by unpredictable sources, such as the avatars of other players, are rendered using the last known authoritative states from the server.

So, inspired by this article about the Unreal engine, I’ve thought about that following list of categories for my renderable entities (Some categories will surely be merged together, this was a first shot) :

– Constant : are never modified, thus updates never need to be sent or waited for.
– SelfContained : once known, may be processed entirely on the client (e.g. playing a sound), thus never need to be sent or waited for except for initialization / destruction.
– Authoritative : last update from the server need to be always used as if it was the current state for rendering purposes. Typically used on avatars from other players. Maybe terrain and mounts/vehicles too (as Unreal guys stated, vehicle reactivity delays in real life may cover up for our network delays).
– Controlled : actions not yet acknowledged and known only client-side affecting the entity may be used for rendering purposes. This is the case of the local player’s avatar.
– Simulated : last update from the server may be extrapolated up to the current client time for rendering purposes.
– DeterministicAI : last update from the server contains enough high-level AI decision stuff, for the client to be able to extrapolate low-level AI reactions on the server timeline. Rendering of AI entities is done “in the past” just like Authoritative entities, but the client was able to deduce that past state from a tiny amount of data (high-level AI information).
– Reactive : last action known only client-side on the entity (such as shooting of an arrow, or cutting a tree branch) may be extrapolated up to the current client time for rendering.
– Inverted : last update from the server refers to the final state of the entity at a given point in the future (such as : this arrow WILL hit that guy). Rendering needs interpolation.

Maybe I should make these types assignable to any variable held by entities, instead of the whole entities :
An in-game stat on the player avatar may be “Authoritative” e.g. his current health level, or a current active aura… while the character position and animations are “Controlled”.

Moreover, maybe dissociate states from events : e.g. rendering a magical effect may be “Authoritative”, while the event of switching to that effect may be “Controlled” (playing animation and particles and sound FX associated with the activation)
-> if the event is later discarded by the server authority, simply cut the current sounds and animation associated with it, and don’t care about the snap effects
-> this will be as with most current MMO : a player activates a spell on his GUI, the animation for the spell-casting action begins to be rendered, and a sound played. Then the server authority kicks in, e.g. the target was too far and the cast event is invalidated, so all effects are cut abruptly. And nobody seems to resent that effect all that much.

Okay, it’s quite late already, and that post is far too long. Let’s wrap this up, and see you next time 😉

Leave a Reply

Your email address will not be published. Required fields are marked *