a place to jot

Custom Movement, Inputs, and Compression

Published by

wirepair

on

Input

Today’s topic will be about how I plan on transmitting input/movement data to the server. Before we dive in, let’s discuss some constraints we have and some fundamentals.

At first I was planning on sending a series of ‘actions’ and magnitudes. Where magnitudes would be the amount of yaw or pitch the character was doing per frame. This will be hard to model on the server so I started to look at alternatives.

Luckily Quake III Arena source code is open and I could look to see what they do! Turns out they send angles of yaw/pitch see: here which is called from here. These usercmd_t objects are then sent over the network here. To be honest this makes way more sense. It will be trivial to reconstruct the players direction/facing by sending along the yaw/pitch angles with our keypress data.

This post covers a lot of bit masking and bitwise operations, if you’re like me and sometimes struggle with what bitwise ops are doing, I found this awesome page called BitwiseCmd that really helped me visualize what values should be.

Keypresses

Speaking of keypresses, I’ve decided to make a single uint32_t bitmap representation of keypresses. This way if multiple keys are pressed, I can encode this all into a single value. Before I had unique ‘actions’ be it’s own uint16_t value. This was bad because it didn’t account for multiple actions occurring in parallel. This new system does. Here’s the enum that encapsulates the possible actions/keypresses:

enum InputType : uint32_t
{
    NoOp = 0,
    Forward = 1,
    Backward = 1<<1,
    Left = 1<<2,
    Right = 1<<3,
    Jump = 1<<4,
    Shift = 1<<5,
    Ctrl = 1<<6,
    Alt = 1<<7,
    StrafeLeft = 1<<8,
    StrafeRight = 1<<9,
    ActionOne = 1<<10,
    ActionTwo = 1<<11,
    ActionThree = 1<<12,
    ActionFour = 1<<13,
    ActionFive = 1<<14,
    ActionSix = 1<<15,
    ActionSeven = 1<<16,
    ActionEight = 1<<17,
    ActionNine = 1<<18,
    ActionTen = 1<<19,
    MouseLeft = 1<<20,
    MouseRight = 1<<21,
    MouseMiddle = 1<<22,       
 };

I have a little bit of room left in possible bit values if I need to add more inputs, but this should suffice! Each frame iteration we read these inputs and create an Input object:

struct Input
{
	/**
	 * @brief Processes inputs and adds it to our key presses
	 * 
	 * @param Keys 
	 * @return true if inputs are same as they were last time we processed
	 * @return false at least one key press has changed
	 */
	bool ProcessInputs(std::vector<InputType> Keys)
	{
		KeyPresses = 0;
		for (auto Key : Keys)
		{
			KeyPresses |= Key;
		}

		if (PreviousKeyPresses == KeyPresses)
		{
			return true;
		}

		PreviousKeyPresses = KeyPresses;
		return false;
	}

	bool IsPressed(InputType Key)
	{
		return (KeyPresses & Key) != 0;
	}

	bool WasPressed(InputType Key)
	{
		return (PreviousKeyPresses & Key) != 0;
	}
	// ...
}

This object also lets us track the last key presses so we can do a diff to see if anything changed. So each game loop iteration we call ProcessInputs(...) with any keys that were pressed and capture it into a single KeyPresses uint32_t value.

Cool, so now I have my inputs, but I’ll need to send this over the wire.

Sending inputs

A common technique for dealing with the unreliability of UDP is to batch your inputs into a buffer of the last N number of inputs. Each entry into the history buffer is one frame tick. This way if we send four packets, and the middle two packets are dropped, the last and final packet and be used to re-construct what the client did for those two dropped packets.

While great for reliability, it’s not so great for bandwidth. Since we want to send the last 24 commands which, if we are running at 30fps/30hz, would be almost a seconds worth of data. 768ms to be exact. So this historical buffer ends up being pretty large when we take into account that each client message is uint32_t (input) + uint32_t (yaw) + uint32_t (pitch) x 24. We are now sending 288 bytes for just the movement data! Multiply this by say 1000 concurrent clients and you are sending 8,928 bytes per second per client or 8.92MB per second for all 1000 clients.

It should be noted that in most cases in MMORPGs, this input/movement data is repeated, like, A Lot. In most cases you are just moving forward at the same pitch/yaw value.

What we want to do is compress this data to not have to send repeated commands or values since they don’t change.

Compression

I decided to come up with my own compression algorithm (I mean why not!). To be fair I’m sure this exists already somewhere, but I don’t know what it’s called, drop me a message if you know!

Since most movement data will be repeated, and we have a history buffer of 24 commands, why not store the repeated values as 0’s, and any transitioned values as a 1 in an integer lookup table?

Let’s visualize this so it makes more sense, note this is only 8 historical commands instead of the expected 24.

In Order of pressed (changes in values should match compression key):
| Fwd | Fwd | Fwd | Right | Left | Left | Left | Back | 
-------------------------------------------------------
|  1  |  0  |  0  |   1   |   1  |   0  |   0  |   1

Given this table, we only need to transmit a vector of: {Fwd, Right, Left, Back}, and a uint32_t compression key of 0b10011001. We can then read in this compression key and vector and reproduce the original buffer.

This will save us a ton of transmitted data. On just input alone, if repeated, best case scenario it will only cost us (sizeof(input) + sizeof(key)) == 8 bytes, instead of 96 (4 bytes * 24) bytes!

I wrote the HistoryBuffer as a templated container so it will work with other data types too (pitch/yaw angles for example), as long as N is less than a uint32_t. I plan on making the template a bit better to support uint64_t if we want bigger history buffers.

HistoryBuffer internals

HistoryBuffer is a circular buffer that wraps around as it fills up.

 /**
 * @brief Push a value into our history, wrapping around if full
 * and tracking size until it's full
 * 
 * @param Value 
 */
void Push(const T Value)
{
	if (Idx == N-1)
	{
		Full = true;
	}
	Idx = (Idx + 1) % N;
	Buffer.at(Idx) = Value;
}

When working with the results, you want to call Get(...) and provide an array. This will write out the data in LIFO, I may change this order, but that should be easy with iterators anyways.

/**
 * @brief Get the history starting from index and reversed so it's Last-In-First-Out (LIFO)
 * LIFO helps with replaying the values.
 * 
 * @param OutHistory An array of N elements of our entire buffer history in order.
 */
void Get(std::array<T, N> &OutHistory)
{
	// ensure position is correct even if idx is zero
	size_t Pos = Idx;

	for (size_t i = 0; i < N; i++)
	{
		OutHistory.at(i) = Buffer.at(Pos);
		if (Pos == 0)
		{
			Pos = N;
		}
		Pos--;
	}
}

Compression was pretty tricky since our index can be anywhere, and we have to write out the bit depending on the location in the buffer:

/**
 * @brief Writes unique key presses to OutHistory, where repeating key presses are mapped to 
 * the CompressionKey, where the index of the unique value is a 1 and the repeating keys are 0
 * 
 * @return true if successful, false if the buffer isn't completely full 
 */
bool CompressBuffer(std::vector<T> &OutHistory, uint32_t &CompressionKey)
{
	if (!Full)
	{
		CompressionKey = -1;
		return false;
	}

	CompressionKey = 1;

	size_t Pos = Idx; 
	auto Prev = Pos == 0 ? N-1 : Pos-1;

	// always add first element
	OutHistory.push_back(Buffer.at(Pos));

	for (size_t i = 0; i < N-1; i++)
	{
		if (Buffer.at(Pos) != Buffer.at(Prev))
		{
			CompressionKey |= (1 << (i+1)); // mark this position in our bitmap
			OutHistory.push_back(Buffer.at(Prev)); // add this value that was transitioned to
		}
		
		// wrap around Pos, if Pos is zero
		Pos = (Pos == 0) ? N-1 : Pos - 1;
		// wrap around Prev, if Pos was _just_ set to 0
		Prev = (Pos == 0) ? N-1 : Pos - 1; 
	}

	return true;
}

I’ll admit it took quite a bit of work to get this to work correctly! The only reason I’m confident it’s correct is because I wrote tests that ensure every possible of Idx will produce the correct result.

The benefit of this is now I can have a custom constructor read in this smaller vector of values and a compression key and fill out the new history buffer:

/**
 * @brief Construct a new History object with the values and a CompressionKey
 * Note this will fill the entire buffer up to N elements, meaning we expect
 * a full range of values. 
 * 
 * @param Values A vector of values, in order of the CompressionKey
 * @param CompressionKey A bitmap of unique and repeating value indexes 
 */
HistoryBuffer(std::vector<T> &Values, const uint32_t CompressionKey) : Idx(N-1), Full(true)
{
	auto ValueIdx = 0;

	auto Pos = N-1; // start writing from end of buffer
	Buffer.at(Pos) = Values.at(ValueIdx); // always write first value
	Pos--;
	for (auto i = 1; i < N; i++)
	{
		if ( (CompressionKey & (1<<i)) ) 
		{
			ValueIdx++;
		}
		Buffer.at(Pos) = Values.at(ValueIdx);

		Pos = (Pos == 0) ? N - 1 : Pos - 1; // wrap around if Pos == 0
	}
}

So that’s it! I can now send over a compressed series of inputs/angles and recreate them on the server.

I’m not entirely sure this is a good idea yet, I’m sure I’ll find a better way to compress or send inputs/movement, but it was an interesting problem to solve. Dealing with inputs and movement is very new to me so I’m sure I’m doing something silly but I’ll know for sure once I try to get movement actually be processed correctly on the clients and server.

Previous Post
Next Post