Sign in to follow this  
Dead6re

IOCP and Bit Packets

Recommended Posts

I'm looking at doing scaleable networking that you often see within MMORPGs. I'm not attempting to write an MMO but rather looking into the networking. One problem is, what data do you send to everyone. Searching a list against every known entity would be time consuming, I guess you could limit this to a "region" and having lists for this. Of course if you have big regions, you may have to split this down further but then the problem of boundries arise. There would be a point in the game at the edge of a region where you can't see further. It would go from a NPC land to nothing. Perhaps loading both region lists would help at this point to reduce this problem? How do you assign proirity to certain events. For example if you recieve a death command, you would instantly process this and remove any outstanding messages waiting? Or more a first in, first out. Lastly, I'm confused about bit packets. I understand it is to cut bytes down so that messages use less bandwidth. Does anyone have a working example and some sample messages they can help me with?

Share this post


Link to post
Share on other sites
Search around for "Area of Interest management". There is no quick answer, it depends on many factors.

Quote:
Lastly, I'm confused about bit packets. I understand it is to cut bytes down so that messages use less bandwidth. Does anyone have a working example and some sample messages they can help me with?


Game Programming Gems books cover this in several chapters. There's a C# implementation of bit packet floating around this site, but I don't have the link. See also forum FAQ Q23.

Note that AOI algorithm will be the real bandwidth saver. Those often have capability of discarding the packets, or affecting the speed of simulation when something gets overloaded.

Share this post


Link to post
Share on other sites
About the binary packet here:
Binary Packet Tutorial
Basic idea should get you started. This isn't the only way to set up packets, so you might want to research before making a choice.
has an old C++ one I wrote
here's a development bit packet I use. (needs a lot of work but works) (it doesn't use generics or anything since it's easier to maintain my flash client version without it)
C# Development Packet

A big idea behind them is that you can structure the data and save data in a format that is very small (even smaller than the actual bits in RAM, see the fractional float, also explained here: Forum FAQ ) When you start storing whether variables have changed and setting up delta packets it can get a little more complex. Like if positions or velocities don't change on enemies then sending them to certain players is pointless. Normally you end up with an Object.DeltaPacket(packet); where the object serializes its delta information into the packet and an Object.FullState(packet); where the full state is written. This part can get complex especially if you want to keep it maintainable.

A solid spatial partitioning system is needed to cull down what each player sees and whether it's new and requires a full state or the player knows about it and can get away with just getting the delta packet version. If you'd never learned or written a spatial partitioning system then you have to learn one (quadtree, octree, grid, nested grid) because while serializing the data for 100-200 delta packets might not be a problem it can get really costly later on especially if you pull out a calculator and figure out how much bandwidth you need to run an mmo scale server.

//edit I just realized something. You didn't say what language you were using. IOCP is built into .NET so using a language like C# can make things fairly easy especially if you already understand threads.

[Edited by - Sirisian on April 23, 2008 6:58:01 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Sirisian
oh in that case look at Boost:Asio. I believe it's a very good for C++ or that's what I've heard.


ASIO is socket and async callback abstraction. It doesn't even provide serialization.

But yes, to avoid lots of boiler-plate code required by IOCP, as well as some potentially annoying concurrency issues, it's a good choice.

Share this post


Link to post
Share on other sites
Depending on your game, worrying about saving a few bits here and there might be one of those "premature optimisations" you hear so much about. :) Most network games will be sending many small frequent updates, and in that case a lot of your overhead will come from the packet headers. If you're using UDP/IP it'll be about 28 bytes of header data per packet, and if you're using TCP/IP it'll be a ton more. That's without *any* data, and if you're sending frequent small packets (e.g. input or move deltas) you're probably not being very efficient in terms of your ratio of bandwidth used vs. actual game data sent.

If it's possible for your game it might be better to buffer some updates and send them out in slightly larger but less frequent updates so that protocol overheads don't waste a ton of your bandwidth. If frequent updates *are* necessary, you'll still probably save more by doing higher-level savings, e.g. less frequent updates for game entities that are further away (if possible), or compressing the data before sending it over the network (I mean some kind of RLE for example, rather than trimming individual bits from bools and integers).

A lot of these things can be tweaked for your particular application though, so if you're sending 500 booleans in an update then yeah I guess bit packing will save you something. :)

What was my point again?

Share this post


Link to post
Share on other sites
input from the clients is never important it's the serializing of the data when it leaves the server. Sure for random situations where a player is running around by themselves the data for that player might be very small, but if there's 20 people around you and some NPC's it's usually wise to get a solid packet system up before hand so you don't have to worry about it later. I mean the most I ever worry about is the formatting. Really high optimization contains a lot of booleans.

You end up with things like:
EntityUpdates server packet ID, dynamic sized int
Number of entities, dynamic sized int
uint ID, dynamic sized int //players reserved from 0 to 20,000 and such. The server keeps records of what entities the player knows about a C# hashset<uint> works very well for this purpose
//we are going to assume this ID is already know to the client and thus it knows the entity type and it's a player so it looks for a certain format for a player like:
1 bit position vector follows
if positionNeeded then 3 floats custom resolution
//same for velocity
1 bit extra information
//custom flags that are passed into the entity class to be dealt with like states
//rest of entities in same format

I've found this system is pretty good. Tons of easy optimizations and once a format is set up it's normally very scalable. I mean you can imagine a format like the above might take 5+ bits for the ID, 5+ bits for number of entities, then 6 bit resolution for custom resolution floats you end up with:
bitsPerSecond = (packetHeaderBits + 10 + (1+18+1+18+1) * numberOfPlayers) * numberOfPacketsPerSecond
saying that entities are constantly changing direction with no state updates. I hate writing out these hypothetical calculations because someone might read them and poke holes in them, but that's the basic extrapolation method.

You'll notice that when doing multiplayer games unless the player is hardcore and never stops moving many times players stop moving and stand there talking to NPCs or stop to talk so you end up with a lot of saved data by doing a lot of delta packet calculations for what data has changed. Also a lot of RPGs force players to stop moving to cast spells offsetting the cost for sending a spell ID. You can probably think of hundreds of random optimizations or situations. (especially health and mana and other statistics. Full state then delta packet method really fits the mmo genre).

Also something I've never even thought much about (but I have been looking for books on compression theory) is the idea that binary packets due to their random structure can be compressed. I imagine that if you wanted to waste the CPU to order the ID's in such a way that you get optimal ordering for compression then a compression algorithm could crush the data down further, but it's theory so you kind of have to take the time to research it.

Also I mention this a lot to people and it might not always sink in. If you know an entity is going to need a fullState or delta update and a lot of players need that information. Create one packet for the delta information and splice it into place into the outgoing packets. Example: Say you're fighting a boss in an MMO and it changes state and fires 20 fireballs. If for every player you serialize that boss and put it into the player's outgoing packets then you lose CPU speed when it's probably optimal to detect how many people need the update then generate the packet in the entity and when calling the SerializeDelta just put that packet into the players packets instead of going through the huge process of serializing it for each player. Hope that makes sense. These are random optimizations and there's tons of them that you're bound to figure out if you think really hard about the situations.

Share this post


Link to post
Share on other sites
Quote:
I'm looking at doing scaleable networking


Note that all the things you've been talking about -- IOCP, bit packing, etc -- all have to do with simple efficiency improvements. They do not improve the scalability of the system. A system that is scalable has a know path to add capacity to meet load.

For example, if one system is totally optimized, and can do 1,000 connected clients per machine, but won't be helped by adding more machines, then that system is not scalable. A system that does 100 connected clients per machine, but you can add as many machines as you want to meet load, is scalable. The difference is that the second system can scale to, say, 100,000 clients (at the cost of 1,000 machines). Meanwhile, if your load will never be more than 1,000 users, it would be cheaper for you to go with the first hypotehetical system in this comparision. You just have to make very sure that your business won't implode if you suddenly need to serve 1,001 users.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this