Skip to content
This repository has been archived by the owner on Feb 1, 2024. It is now read-only.

Jodi's Blog

Jump to bottom
JodiTheTigger edited this page Jan 7, 2013 · 18 revisions

Got stuck trying to figure out how to implement adaptive huffman encoding that's used in q3, only to discover that it isn't actually used!

This makes me happy as I couldn't understand how to reconcile dropped packets with keeping the huffman trees of the server and client in sync. Seems iD just seed the tree and then don't touch it. They don't adapt it on a per game state packet basis.

I'll still have to roll my own huffman tree though, as all the ones I find on the net imply a buffer copy.

I've been flip-flopping on how to return multiple values from a function. Use Tuples or argument references.

Tuples:

  • Clear what is returned by the function
  • Return value optimisation
  • It's not clear what which return values are what (only a problem if all the return values are the same type). Can get the "permute and baffle" anti-pattern
  • Argh! Functions cannot differ by return type alone! (boost uses error reference in arguments to return errors for functions instead of throwing exceptions if you want, can't do that here as the function would only differ by return type)
  • Arg, have to fiddle with splitting the values out again (not really an issue)

Function arguments

  • Functions can differ by return type alone
  • Ambiguous what arguments are in and out (although using const references (refering to) and values (for coping) for in, and non-const references by out could mitigate that if you had a consistent style)
  • Ambiguous what happens to out arguments during error
  • Really Ambiguous if you're also using smart pointers
  • have to create variables for all the return types, even if not used

Why this is an issue is because I'm using unique_ptr to prevent coping of buffers around. The case been the creation of a class that takes a buffer, I want to take the buffer, not copy it to the class. I do this by requiring a unique_ptr buffer. But this is a special case muddying the waters. I'm going to stick with function arguments because I use a consistent style for in/out, I can differ by return type, and I don't really like tuples due to "permute and baffle".

Got an issue with the pimpl idiom, unique_ptr and std::map. Basically I need to do what's described in:
http://www.cs.brown.edu/~jwicks/boost/libs/smart_ptr/sp_techniques.html#pimpl
but then I noticed something else: I need to combine
http://www.cs.brown.edu/~jwicks/boost/libs/smart_ptr/sp_techniques.html#abstract
with
http://www.gotw.ca/publications/mill18.htm
to get rid of the virtual destructor! Hmm, I'll need to investigate further.

Constant correctness
Ugh.

Got compiler warnings when trying to return a const vector<const string>. This forced me to re-read all about constant correctness, and I ended up reading about rvalues again.
http://cpptruths.blogspot.co.nz/2012/03/rvalue-references-in-constructor-when.html
http://stackoverflow.com/questions/10231349/are-the-days-of-passing-const-stdstring-as-a-parameter-over (read the top two answers)
http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/

Basically, if your functions needs to copy an argument passed to it for use, then don't pass in const references, just pass by value, and C++11's move semantic will optimise for you.
However if all you do is use the value, then by all means, const the heck of of it.

Investigating doing macro / interface based reflection for the cvar system landed me on this page:
http://www.gotw.ca/publications/mill18.htm

Which has some pretty good points regarding doing interfaces in c++. It has made me question doing public virtual methods.

Need to read
http://www.ra.is/unlagged/
to understand how to do unlagging

Ok, So I've made up my mind.

128 players.
2048 ents.
32 bytes / ent.
q3 encoding.

I'll have to run a worst case scenario to see if I can handle having 1 player surrounded by everyone else shooting rockets every which way.

Realised why a pure delta encoding is bad.

Assume you have an entity that didn't change. that's 32 bytes that delta to 32 zeros. Using huffman encoding, that would be four bytes, or two bytes using rle. It's one bit using the q3 method.

So I'll use the q3 style for encodng. 1 bit for changed (per entite member), 1 bit per centity changed, and 1 bit for entity deleted, rest for data.

Also, concerning the server bandwith. I took the hl2 numbers, assumed 32 bytes per entity at 2k entities, and deduced they expect a 97% compression ratio to get to 1.2MB/s. Right, if they can so can I (still at 18MB/s for 256 players though).

Right, sending bandwidth is dictated by the amount of entities the server handles. Q3 supports 1024 entities, HL2 supports 2048. I want to support 4096.

So, choices I've made:

  • 4096 entities
  • 32 Bytes / ent
  • 20 network snapshots per second
  • results in 40963220 = 2,621,440 bytes / second = 2.5 MB / second

I'm assuming that the delta compression will reduce the worst case. However it won't be enough to drop below 256k/second. For that some aggressive "area of interest" pruning needs to be done. For example, for units outside a sphere of interest, only update the first 8, 4 or 2 bytes depending on distance to keep bandwidth down.

Secondly the amount of memory used by the snapshot system will dictate how many players the server can support. so my answers there are:

  • 256 players
  • 32 snap shot buffer
  • memory needed = 40963232*256 = 1,073,741,824 bytes = 1GB of memory.

The only downside I have at the moment is the outgoing server bandwidth which is:

  • 256 * 2.5 = 640 MB/ second (uncompressed) or 64MB / second at 90% compression.

Bah too much! I need to revisit my calculations!

Argh, I'm sick of not writing code. I have figured out how to calculate my constrains. Only allow 1-2GB of memory for the snapshot system, and back figure the max count from that.

Also, I might implement two delta systems:
The q3 system for 1 bit for changed, 1 bit for removed, and transmit entire value if its different My system where I just xor past and present, but have 1 bit for object removed

1.1 packet is: command/state, time, last frame, area bytes, player state, entity state.
1.2 delta encode each class member. 1 bit == not changed, otherwise size+1 bit. entites are reference in an array (0 to x). Send a remove command if an entity is removed. each entity has an id member,but that isn't transmitted, only used for calculation.

5/11/2012
Things to do before I even get a building project commited to git:

  1. In depth read of q3 network code. I know the theory, time to find out exactly how they did it. (https://github.com/id-Software/Quake-III-Arena/tree/master/code/qcommon)
  2. How do they actually do the delta compression, get the packet format
  3. How do they store entities in the buffer, how do you recognise it's the same entity between snapshots

When I commit stuff to git, have a research directory full of projects doing stuff like:

  1. Get most basic ogre3d demo showing 1 box
  2. Get most basic ogre3d demo showing 100 boxes, with rotating camera in the middle rotating at 1 rev / 1 second
  3. Find max limit ogre3d can show 1000s of boxes, all moving
  4. research billbording as a solution to showing far away boxes
Clone this wiki locally