Game data stream and related topics

[alight]

I've had rather a lot of ideas that never got put down in one place,
so I'm gonna attempt to post them here for review, discussion, and
availability.

The most recent one, which I spoke at length with Zircean about, has
to do with compact representation of playfields. I arrived at a way to
compress the playfield to an average of around 9 bytes (with
admittedly limited sample data - about 113 frames from a KoS game) -
but this compression should be sufficient to allow us to not bother
with sending field deltas, which could take almost as much space. This
opens up a number of possibilities for making Netplay more responsive.

First, the algorithm in question:

I take the upstack (lines that are not garbage, and lines that are not
empty) and process it left-to-right, top-to-bottom with a PNG-like
filter. Rather than predicting a value and taking a difference, as PNG
does, I instead maintain a move-to-front buffer and seed it with my
predictions in order of likelihood.

Say I initialize the buffer to "jizlots-" where - represents an empty
space; the other letters represent a mino of their particular kind.
For each cell, I move the specific values to the front of the buffer
in a particular order. Assume the cell under consideration is marked
with the asterisk:

234
1*

The order of values moved to the front of the buffer then is given by:
4, 2, 1, 3, (2==3), (1==2), (3==4)

For the last three values, the appropriate value is moved only if the
two cells are equal. If 1 is the same value as 2, for example, that
value is then moved to the front of the buffer. This means that if 3
and 4 are the same, that value will wind up at the front of the
buffer. I then encode the position in the buffer of the actual value
of the * cell; so if the buffer is now "toljizs-g", and the * is an o,
the encoded value is 2. The buffer carries forward to subsequent
cells.

Finally, I use a range encoder with predefined percentages based on my
sample data (and in release, would be based on a much larger set of
data, surely), to compress these values. This system can be expanded
to include type of data, and special rules can be included for the
prediction. For example, with Tetrinet style items, we can assume
safely that if an item is observed in the surrounding cells that it is
NOT likely to be the value of the cell under consideration - and can
be left alone, or moved to the back even.

As for the garbage, I found that a combination of truncated binary and
RLE was able to represent my sample data with an average of around 9
bits. The mechanism is as follows:

A single bit represents whether the current position is a new hole
position or a repeat of the previous one. A value of 0 is followed by
the new hole position represented in truncated binary (~3.4 bits),
while a value of 1 indicates no hole change. 1 values can be extended
indefinitely.

This naturally is a bit wasteful on games with 100% garbage, so the
RLE component could be made selectable when appropriate.

Finally, the issue of garbage coloring came up, though I'm not
entirely sure I like the feature in the first place. It's interesting,
but doesn't provide any information you can particularly act upon -
and may be distracting and confusing for players coming from pretty
much any other game. That discussion belongs in another thread,
though ;)

I believe a simple way to encode garbage coloring would be as a stream
separate to the garbage positioning. This has the potential to waste a
few bits of redundant RLE data, but has the benefit of being easy to
exclude as well as being very compact when the colors do not change
often (which is often the case after a game has gotten past the
opening). Move-to-front again comes in handy here, as we can then
represent the most common garbage colors with all of two bits. One
sample encoding might be: 00, 01, 100, 101, 110, 111 to represent
values from 1-6 (you will not receive garbage of your own color, but
gray takes its place). This could be extended or even decided on
programmatically using something like golomb codes, though I believe
it is beneficial to guarantee the first two values to be two bits.
Testing on actual game data will bear out the truth of all this.

I have some ideas about representing the active piece too, but no real
data to test it with. I am currently looking at representing the
current piece as one of pieces*rotationstates values; its position can
be given by an offset from the spawn location on the x-axis, and an
offset from either the spawn location or the ghost piece position on
the y-axis. This should enable both the x and y values to frequently
be small for many cases. In the x-axis case, many pieces cannot occupy
the full range of 10 squares, and so encoding as an offset from the
center naturally avoids the largest numbers for pieces that cannot use
them, saving bits. In the y-axis case, most of the time the piece will
either be at spawn height (0g) or near it (1g), or at the bottom (firm
drop), enabling those values to be small most times too. Statistical
data may help to decide on the most compact encoding for this use-
case.

------

How this all affects the game design and responsiveness in netplay...

Since it appears to be so cheap to represent a field's gamestate,
protocol overhead and even *TCP* overhead may in many cases add more
data to a packet than the packet contains. Delta encodings are
logically useful, but should we choose to broadcast entire gamestate
(because we can!) at a fast rate (~5kb/sec at 60fps, which is
unnecessary), certain advantages appear.

For one, TCP guarantees the ordering of packets, but that is not
useful to us if we aren't using deltas. Dropped packets will introduce
a delay of at least the round-trip time between client and server
before the data stream continues with TCP. Should we choose to use
something like UDP, with entire gamestate updates, it enables us to
recover faster from lost packets - since no negotiation need happen at
all. The combination of small data size and UDP streaming should make
for the most responsive remote stream of another player's Tetris field
that the game has ever seen.

The downside to UDP is that we would likely need to implement our own
congestion control. ECN-enabling the system would be useful, but we're
talking about, for best effect, re-implementing many features that TCP
already has. There are some other protocols which might have available
libraries that we can use. The important part is that we would not
require ordered packet delivery, nor would we care about packet loss.

In such a case, the game data would need to be streamed separately
from the actual control data. It would make sense to perhaps piggyback
notification of things like attacks sent in these messages, while
duplicating them across a reliable TCP connection. In this way, there
wouldn't be situations where attacks are added to your queue visibly
later than the opponent clearing the lines due to the TCP and UDP
streams not being in synch - but the TCP stream guarantees delivery in
case the packet containing the notification gets dropped. There is
much that could be done in the protocol to allow for some redundancy
in the interests of speed and response.

All in all, I think we should go this route. We can code it naively or
smartly, but in the end I imagine an extremely tight user experience
with the minimum possible network latency in the path.

---

I did brainstorm at length some time back in #nullpo about other
topics related to synchronizing and ordering player data to avoid
other latency-based issues such as garbage "passing in the middle" and
so on. I'll leave that for a separate post, if I can dig it up.