"Perfect" Netplay

[alight]

The biggest thing we can offer players of other games is "no lag" -
but we can only do this with careful consideration of each problem.
I'm going to leave the idea of "input lag" and a locally responsive
game to other posts and focus in this post on what can be done to make
network latency unlikely to exert an unfair influence on players. Also
necessary to take into consideration is cheating, to the extent that
certain decisions made will make it easier or more difficult. These
are tied together so I'm going to address them both here. (For those
of you who say "we don't have to worry about cheating yet, the game is
too small" I reply: this same attitude has resulted in various bad
behaviors being executed with no recourse even within our current
small community. Time to be proactive.)

Right from the start, we have synchronization - players beginning
their games at the same time as each other, or as close to it as
possible. We also have data transit - the fact that there is a space
of time where individual clients are sending data without knowledge of
what's happening at the same time. We also want players to receive the
garbage they should receive, place the pieces they should have been
dealt, and so on. Finally, we want to reduce the round trip reaction
time by as much as possible. We of course can't reduce this any
farther than the end-to-end round trip time between two players
through the server.

Some time back in #nullpo I proposed a system that would have many of
the desired properties, but not all. Specifically, I was aiming to
prevent the server from needing to keep a game state, since doing this
for many players is likely to be taxing on the CPU. Depending on the
level of cheat-prevention, this may be necessary, and whether we want
to go that far should be discussed; the idea I am going to lay forth
can be implemented with or without the server maintaining a game state
to validate client inputs, however.

First of all, the server should attempt to determine a mean transit
time to each client. It can do this via statistical sampling over a
period of time.

Clients should timestamp ALL messages with their local timer. Client
timer can be useful for two things. One, it can illustrate clock drift
and possible speed hacking, and two, it can be used for
synchronization.

The difference between the client timer and the server timer should be
the same so long as they are running at the same rate. In practice,
some clients will drift at varying rates, but it's a pretty slow
drift, on the order of milliseconds per some number of seconds. As
long as that difference is the same, then, the packets took the same
amount of time to arrive at the server from the client. This
information can be used to discard outlier pings while maintaining an
estimated average transit time. Once a baseline is reached, should the
C2S ping increase, some skew can be detected. (Say the round trip ping
increases by 100ms, but the C2S increases by 20ms - you know that the
S2C leg took 80ms.) This is predicated on the assumption that our
initial baseline was ideal, but there's no way to determine that so
any further error is out of our hands.

How does this information help us?

First of all, we can start games at very close to the same time. Since
the server knows the timer difference and the approximate transit time
of a packet, the server can tell the client when, based on the
client's local time, to begin the game. The client then needs only
wait until the appropriate timer mark passes. Since clients may vary
in their transit time, a choice must be made about whether to include
the transit time in the countdown or not. If so, then the server would
send out messages to begin the game <start timer> seconds from the
time the server sent the messages. If not, the server should instead
send the messages to begin the game <start timer + largest estimated
ping> from the time the server sent the messages.

Sounds complicated, but really it's not so bad. Let's move on to the
game messages.

When things happen like sending garbage, it takes a while for the
message to get to the other clients. What should happen if two players
send attacks at the same absolute time? In the naive implementation,
these packets will pass each other in the internet, and both clients
will receive the full attack. In a perfect, 0-latency system, one
client would receive the garbage and the other client would cancel (if
applicable with the game settings). In order to simulate the 0-latency
system, there needs to be one authoritative source for the order in
which things happen. The server makes an obvious choice.

So, by having the server timestamp all relayed game messages, we are
able to locally determine the order that things happened in and
therefore decide how to act. This will also require the server to echo
back messages so that clients will know the order of the message they
sent in relation to other happenings.

Let's take a case in point. Alice sends 4 lines while Bob sends 5. If
Alice sent the lines fast enough, Bob should receive all 4 and then
Alice would receive 5. For this to happen, Bob would need to receive
messages from the server indicating that Alice sent the 4 garbage,
followed by a message indicating that Bob dropped a piece without
clearing a line, all before Bob receives the message saying he sent 5
lines. If instead Bob sees that he sent the 5 lines immediately after
the 4, or through a valid garbage blocking combo, he knows that he
does not have to accept the garbage. In the same case, Alice would see
that she sent 4 lines, and that Bob canceled those lines and sent her
back one, and she would only accept one line of garbage.

We can see that ordering game messages enables us to understand what
behavior should have happened and act on it. This requires some trust
of the client, but we can impose a time threshold (perhaps based on
the setting that controls how long you can float / juggle a piece)
that imposes death when the client hasn't sent any messages for enough
time.

In the particular case of topping out/being KOed, the server should
also have the last word on the order of death. By basing it on the
client timestamp difference with the known latency, people who have
lag spikes won't "lose late" and gain more rating than they should.

We are faced with a choice. If we decide to trust the clients enough,
then all the server must do is send attack messages along, adjusted
for the client's local timestamp, and the client can perform the
appropriate calculations. If we decide not to trust the client at all,
then the clients must send information for placed pieces for the
server to validate, and the server must keep a game engine for all
participating players. Whichever is chosen, the same mechanism can be
used to keep games synchronized.

This method does introduce a problem, however. Because of its nature,
clients are constantly going "back in time" in order to accept
garbage, by which I mean that a client may have wound up accepting
garbage before it knew the garbage was coming. This is handled nicely
by implementation of a feature I think we should implement anyway -
namely, a time buffer when receiving garbage. Tetris Friends
implements something of this sort by way of the animated squares that
indicate an attack (which visual cue we could also do well to make use
of). In short, players would receive a free second (or two, or
whatever) after receiving garbage before they can accept it by
dropping. They can still cancel in this buffer time.

This accomplishes two things. One: it prevents the "back in time
garbage acceptance", giving players proper notice. Two: it allows
players time to react, and punishes laggers, not everybody else. If
you have a 500ms ping, you will consistently receive less warning
time, but you will still receive some. The lower your ping, the closer
to the full warning time you receive. I recommend 1 second of buffer
time, since that is enough to allow players to react appropriately and
will also easily encompass most end-to-end transit times with some
portion of a second to spare.

There is one more case to cover. In the case that player experiencing
a lag spike sends an attack, that attack might take longer than a
second to reach its destination. (Note: players that are constantly
laggy will actually be playing sooner than the other players, so
constant lag is not a problem - only sudden lag delaying specific
packets). In such a case, other players may receive "time travel"
garbage as described, with no ability to block it. If we choose here,
we can break game "fairness" and assign such packets a later attack
time that will give recipients some portion of their time in which to
deal with it. Or, we can ignore the garbage entirely. Finally, we
might "retain" the garbage and use it to cancel incoming attacks,
allowing the laggy player to recover while not unduly punishing the
other players. I think I like this last option the best. Bear in mind
that should we be using a data stream broadcast for the gamestate of
each player, we ought to have some concept of when lag spikes are
occurring since we should be expecting regular game data packets and
they would be timestamped as well. This enables us to discern when to
begin and end the spike-damping behavior. Should the client exceed
some thresholds for reliable play, it should be removed from the game.
This could be some measure of the inconsistency of that player's
packets over time, or a single spike that goes on for too long in
duration.

---

With this system, or some variant of it, I believe we can create a
Netplay experience that is both fair and latency-tolerant. When lag
rears its ugly head, it will affect only the lagging player, as
opposed to the other players. Games will start as close to
synchronized as possible, experience no strange behaviors as a result
of network latency and precisely timed game events, and result in a
win/loss order that more accurately reflects the game, as opposed to
who could "hold out" the longest with the slowest connection.