Game Networking Schemes

#21 True, with one socket, almost anything works :) Certainly the Tribes approach would not work well on large numbers of TCP connections. I remembered one of the other reasons for using the wasync API, which was to support async DNS without having to use a blocking thread. I wish the "standard" BSD socket API supported async DNS.

Anyway as you say, the NDP protocol as well as the stream, ghost and event managers are the interesting part :)

#22 Wow, good stuff. I'll have to read some more on completion sockets, etc. I'm still using non-blocking sockets for my project.

Anyway, I wanted to mention that for those interested in taking a gander at an implementation of the Tribes networking model, I have a (very preliminary) version posted on my website. http://www.fractalscape.org

I was interested in building a fully-scalable hierarchichal peer to peer system, but needed a good object oriented protocol. The Tribes GDC presentation was excellent! I've implemented the Connection, Stream, Event, and Ghost managers.

After hearing about V12, I put the source up on my site to avoid any legal complications in the future. The project is not done (and doesn't even compile at the moment), but it works and I've tested it over LAN/WAN in both good and poor conditions.

Now that V12 is coming out, I may move my research to it instead of blazing trails alone. Who knows..
--Bryan

#23 What advantage is there to writing your own "reliable" UDP algorithm over using TCP? My networking scheme is based on the fact that a lot of the data my game would send with high frequency can lose packets and it won't effect gameplay but certain events need to be garaunteed to happen on all the machines to ensure synchronization. For example, if I miss seeing Bob, who is playing on a different computer, rotate his turret one degree it is not a big deal but when he fires my client needs to know the exact angles and power so it can replicate the event correctly for me. So I am using the much higher speed UDP packets to send the data I don't worry about losing (unreliable packets) but I need some method of garaunteeing the delivery of certain data and events. The common consensus among game networking programmers seems to be that you should write your own "reliable" UDP protocol. Yet a lot of the things they are doing (the Tribes Netowrking doc for example) is already fully implemented in TCP (sliding windows and such) and are implemented with optimizations I probably can't even imagine adding to my custom protocol. Now, I haven't had the chance to test my "reliable" UDP protocol against TCP so I can't say how big of a slowdown/speedup it might give me. The only inherent disadvantages I can see is that it will complicate managing client connections a little and will require more than one port. Also, you would have to switch from a packet-based line of thought to a stream-based. Are there other things I am missing?

#24 Matthew,

The really basic reasons for using a protocol over UDP is control. TCP doesn't let you decide what data gets re-sent. It resends everything, all the time, until the other side has the exact same copy of the data. This is not desirable for game programming.

Like you said, you don't care if you miss some of the data, but you really must get other bits. This brings a simple "Reliable" for one type of data and a simple "Unreliable" for the other.

But there's more to it than that. For instance, what if I must have a piece of data, but I don't care about every update to it, I only want the most recent version? If I sent this data over TCP, then the data changed, and a packet got lost, it would resend the OLD state before sending the updated state. Wouldn't it be better to just send the updated state in it's place?

This is why the Tribes model works really well. You choose whether the data you're sending is Ordered Reliable, Most-Recent, Unreliable, or Fastest Possible. Then it sends the data, guaranteeing the selected features.

Does that make sense?
--Bryan

#25 I just reread the Tribes Networking Model doc again. It is amazing how much more I get out of it now that I have implemented a networking scheme myself =) What you said about needing gauranteed delivery of only the latest data makes a lot of sense! I guess the reason that this did not occur to me is that my game isn't nearly as fast paced as a fps and will never have to worry about something like that. I only need distinctions between "unreliable" and "reliable" for my current game. Probably what I will do is use TCP for the time being (the natives are restless for multiplayer) while I implement something like the Tribes networking scheme for myself (its going to take a little time =). For the game I am working on now I may not need more than "reliable" and "unreliable" but I would like a powerful and flexible networking scheme to build later games on which I know will require networking more like Tribes =). There is a good possibility that we will use the V12 engine but I want to know how to build game networking on a level only gained by doing it yourself. It will also help me to figure out how to improve the V12's net code.

#26 Hey Matt.

For what its worth, TCP worked fine for Worms, but it was turn based, I dont know if your doing your tank thing turn based or not?

Almost all other games Ive come across use UDP and thier own protocol. I wrote a guaranteed protocol for directplay 3 (I didnt learn until the
last month of the project but the docs were wrong in saying they had implemented guaranteed IPX, so basically NEVER trust microsoft docs on API's in beta :))

Phil.

#27 Hi,

Here's my take on the whole network thing, plus source code to boot. :) I've written several different network libraries over the years for various game companies over directplay, winsock1.1, and 2.0. When it comes down to it they're all work reasonably well for 90% of the applications out there. Although i havn't re-evaluated directplay lately, sockets are still the way to go for massively multiplayer titles. But for smaller projects, either of those should work just fine.

As for UDP vs TCP. UDP is good for certain situations, TCP for others. There nowhere that says only one can be used, there is no need to choose. Have both open and connected to the other machines if you need to. Don't try to re-event the wheel when TCP has been shown to be a scalable, and a reasonably efficient guaranteed protocol. TCP has been refined and improved for many years, and few people would be able to write anythign that comes close to it's rubustness without alot of development time.

To be 1.1 compiliant, i've stuck to using the WSAAsyncSelects. Personally it's worked fairly well for me. The windows message pump handles normally handles of hundreds of messages during regular windows usage. It's more than effecient enough to handle what the messages associated with incoming network traffic for 90% of the games out there. Unless it's the next 10,000 user massively multiplayer title out there. Async selects are fine for windows projects aside from cross platform issues.

I'm not a huge fan of threads in the networking library in games. It is to be honest it is fairly pointless. One of the few valid reasons i've found to use threads is that the run time of your application is so high that you can't read the incoming data buffer fast enough before the data is lost. Your processing time would have to be in a tight loop for over a minute for this to occur under high bandwidth conditions. Otherwise you're just replicating code that the OS is already doing and is probably doing much better than you. Lets say your networking library is threaded... all you'll be doing is copying the data from the IP stack to your own buffers untill your application reads it. You might as well set the size of the on the IP stack larger.

Even with the network library is threaded, chances are, the reading and handling of the data probalby won't be. If the handling and processing the data is done in a threaded scheme then, then i suggest it be re-designed or be prepared to deal with the joy of semphores and the pain of debugging them. Don't use do this unless you're absolutly sure you need to and even if you do, think it over again. The debugging costs are not worthwhile. The costs in developing multithreaded code is well documented to be a order of magnitude more higher in terms of designing, testing and implementing.

If writing alot of network code for the first time, it helps to think of it in terms of low level network services, high level network services and the various layers of actual game protocol. The OSI network layers that are commonly refered to in networking textbooks would a good place to start.

http://www.labmice.net/networking/OSI.htm

I've got a decent network library working in Cratered, a free game i'm working on. Examine, steal, or do whatever with the code, it's free. It's works independent of the game except for the utility library.
The game can be run over the net currently, it's works fairly well even over extremly high pings, and is fairly robust and secure.

http://www.cratered.com

The CVS repository, just click on the network link.

http://cvs.sourceforge.net/cgi-bin/cvsweb.cgi/cratered/?cvsroot=cratered

Thomas

#28 Just a few points I would like to debate....

1. Threaded networking code is hard. While there are some applications where multiple threads can get you in trouble, this is definitely not one of them. Read bytes, lock buffer, insert bytes, unlock buffer. Not much there.

2. The OS is more efficient. I am not convinced of this fact, although I have no proof otherwise. I have no idea what the system does to get packets off the IP stack and no one has given me a good answer yet. My main objection with the message queue approach is that there are a bunch of other messages coming in that need to be processed that may prevent the app from servicing the network in a timely fashion, a point you raised yourself. It also does not allow for overlapped IO (next point).

3. If you use overlapped IO, there is no buffer copying at all since it will write directly into the buffers you provide it. This is the only way to prevent a buffer copy using winsock.

All that being said... It probably does not matter how you do it in 95% of the cases. If the goal is to write a server though, then I would use overlapped IO.

--Brandon (Defender of the thread)

#29 I agree, that threading the basic, read/send queue is trivial but it accomplishes very little. But as i mentioned in the eariler, what's difficult is threading the processing of that data in order to be able to deal with incoming packets in a timely manner. And in most games, this ability is rarely needed since most games run at high frame rates.

If you use overlapped IO, there's even less reason to write a threaded library. The ip stack is already running in a separate thread copying the data in to your pointers as it reads the data in. Then it's a matter of when polling when the data has been copied in to your buffers.

There's just always been a assumption that your networking library absoultly must be threaded, and i believe the opposite to be true. You're better off keeping it nice and simple, and thread it only if you're absolutly sure you need it. You don't gain any more CPU cycles by spawning off a thread, you get the same amount of processing done with 0 thread or 20 threads. It's a choice to process data in parallel or serially, but a realatively similar amount of processing is going to be done in that amount of time just as long as you're not blocking on any particular operation.

Thomas

#30 Actually, I seem to find, at least among game developers, a lot of bias against using threads.

Personally, I find the simple read/write queue much simpler to program with threads than handling the async messages coming off the message queue. It keeps all the socket handling code in one place and doesn't require mixing it with all the other message handling. It is also a much more portable implementation.

** The rest of this post is targeting a server meant to be high performance/highly scalable. **

While I understand your argument about their being no difference between the IP stacks buffer and your own, it is best if their is no buffering at all and the stack is writing directly into your buffers. Using threads is a better method to make sure you are feeding it buffers in a timely fashion and not dropping packets. Ideally, you should just set the receive buffer to 0 and make sure it is being serviced with enough buffers.

I am not sure why you would use overlapped IO without using additional threads. That means that your main thread has to poll with getoverlappedresult and can only poll as often as your main thread gets to that section of code. For this to work and not drop packets, you will probably need a huge buffer for the stack and your back to memcpy on all the packets coming in. And this does not scale to multiple CPUs either, which would be a requirement for any server meant to handle a MMG. Using threads, you can very efficiently be blocking on an event or GetQueuedCompletionStatus if using IO Completion Ports. And according to the MSDN Library at least, IOCPs is THE thing to use if you want to write a scalable app under NT/2000.

Of course, using the overlapped stuff kills any portability options, but I guess you have to pick your poison there. I've read that some of the flavors of unix out there also provide overlapped io but I think they will all be doing it differently from each other and windows.

I must be up to 8 or 10 cents by now:)

--Brandon

#31 Heh it just means we get to throw bigger coins back. At this point we're violently agreeing. :) Threads are good for big, huge, scalable stuff. Your game may not need it.

hmm last thing. :) You can have the your socketlib create it's own hWnd, and have it's own private message pump. Completely separate from the game one, so the code isn't going anywhere. ;)

Thomas

#32 Good point about the private hwnd.

I guess the best thing to do is just pick whats comfortable. But for any newbies out there... Threads are not evil!

--Brandon

#33 Just thought I would post some basics of the networking code behind our game Avoyd from EnkiSoftware.

Our game is unusual in that the entire map (or world, as it's truely 3D not a landscape) is downloaded from the server by each client, and as the game world can be modified in real time each client must be kept up to date with the world changes.

As a first person shooter, we require UDP (TCP is useless for anything which requires latency of less than a second, due to it's implementation). We thus had to write reliable UDP networking code in addition to the unreliable.

The low level classes are:

A Socket Class.
A derived UDP Socket Class. (Could also have a TCP Socket class).
A WaitSet Class (uses Select to wait for socket in/out data).
A Packet Class for the actual data, with a memory allocation friendly PacketRental class which tries to use allocated but unused packets rather than creating new ones (like an intelligent pointer).

all of which work under win32 and UNIX/Linux, and as they are abstractions of the standard socket type communications they can be easily written for other OSes.

I have had no problems with select, which we use to poll our sockets rather than actually wait for data (ie the timeout is 0 - not a NULL pointer as this waits forever). This is used rather than the Tribes style polling of recv as we have multiple sockets for a variety of reasons, as follows:

Multiple sockets allows you to avoid some denial of service attacks, as other than one known socket which is used for contacting the server the other sockets are not know to the public, only to each client.
Mulitple sockets lets you easily use a seperate class to handle all transactions with the client (a proxy client).

For people behind firewalls, all client communications can be routed through a single socket which you can get the firewall to open up.

On top of this low level layer is the game protocol layer, which implements reliable and unreliable ordered networking. For network IDs used to distinguish packets we use a class which is designed to get around the problem of numbers rolling around (ie an unsigned byte of 255+1=0).

On top of the game protocol layer is the high level entity handling layer, which generates all the communications based on what requires sending.

We might be able to make the low level layer code available as completely free source, but will need to clean up some hooks to more sensitive parts of our code otherwise I'd have posted it up on our site today.

Feel free to email me on douglas.binks@enkisoftware.com with any questions.

A few warnings:
Don't use win32 specific methods as many of the better servers out there will be linux boxes (though we have kept our servers running on win32 for as long as the OS stays up).
Be very carefull using threads, particularily if you want to remain OS indepenent.
Don't spend too long designing the high level network protocols etc, get a small scale prototype up and running first (how about a simple 2D game over the net for a test?).

Much of this won't apply to V12, but there are services your game may need that V12 doesn't yet have.

Cheers,

Doug. EnkiSoftware Limited

#34 I would disagree that TCP can't be used to make an action game. If you can get the bandwidth consumption down enough and with some additional techniques it is possible to make a TCP only action game.

Looking forward to checking out your network code.

-ddn

#35 I use TCP for alot of event stuff as well. I find it usually works just fine for alot game updates that don't need to be timely but must be in sequence.

Thomas

#36 I have been writing network code recently, and decided that synchronous network calls will work the best.
The advantages are:
1. You are not forced in to a messaging framework.
2. You may build you own messaging framework that is optimized for your needs, if you want.
3. You can define your network thread priority.
4. This type of code will be the most portable.
5. No MFC.
Here is the interface to my Streaming Socket class:
class StreamSocket : private Socket{
public:
StreamSocket()
:m_sSocket(~0),
m_uSocketState(Socket_State_Invalid)
{}
virtual ~StreamSocket();
virtual bool Create();
virtual bool Destroy();
virtual bool Connect(const InetAddress& LocalAddress, const int& LocalPort, const InetAddress& TargetAddress, const int& TargetPort);
virtual bool Connect(const int& LocalPort, const InetAddress& TargetAddress, const int& TargetPort);
virtual bool Connect(const InetAddress& TargetAddress,const int& TargetPort);
virtual bool Send(const char * sMessage, const int& nMessageLength);
virtual bool Receive(int& MessageSize, char * sMessage, const int& nMaximumMessageLength);
virtual bool Listen();
virtual bool Listen(const int& LocalPort);
virtual bool Listen(const InetAddress& LocalAddress, const int& LocalPort);
virtual bool Accept(StreamSocket& sConnection, InetAddress& RemoteAddress, int& RemotePort);
virtual bool Accept(StreamSocket& sConnection); // for those who don't care
private:
bool Bind(const InetAddress& LocalAddress, const int& LocalPort);
bool Bind(const int& LocalPort);
private:
unsigned int m_sSocket; // SOCKET
unsigned int m_uSocketState;
InetAddress m_LocalAddress;
int m_LocalPort;
};

I'm building an HTTP 1.1 client class that uses this. I'll use that to download PNG, GIF, BMP, and JPG files for the game textures.