Author: rakkar

One problem I had a couple of years ago was how to write an accurate internet simulator feature for RakNet. What I have in there now is what you find in your average games – a user can intentionally add latency to outgoing messages and can randomly drop packets to simulate packetloss. But this is not accurate and not very full-featured.

Here’s a better design:

Maximum outgoing bandwidth – Represents your network card’s ability to send data through the wire.
Maximum incoming bandwidth – As above, but for incoming data
One-way trip time – The minimum time a datagram would take to get to a remote system; the base speed of the network
Per-message additional trip time – On the internet, many people are sending messages, so there will be some delay between each of your messages as other messages goes out. So this number represents the rest of the internet using the router’s bandwidth too. The effect to the sender is that as you flood the connection, your ping goes up. This is what actually happens and is how flow control is accomplished in modern reliable packet implementations (the old way used sliding windows which controlled throughput based on how fast the other system acked your messages).
Maximum router queue – This represents how much average memory each router has. Go beyond this and you start getting packetloss.
Randomly dropped packets – Due to noise on the wire
Out of order packets – As above

The problem with hardcoding this in the user level network layer is that you have to implement a control interface (changable at runtime), you have to do it on both systems, and it can be complex to implement in every circumstance. So I’m writing a layered transport service provider. This is sort of like RakNet’s plugin system, but for Winsock, and it gives you the ability to override various network events with a procedure table. This is stored as a system DLL, and installed and uninstalled by an EXE. I will have this EXE double as a control panel and will use interprocess communication to have the EXE control the invoked DLL.

By the way, to say this is complicated is understating the issue. It’s about 1000 lines of code for the installer, 10,000 lines of code to properly create a plugin that does nothing but pass the data through. You have to understand overlapped events, IO completion ports, support for versions of winsock, an entirely different set of code to install the driver on Vista (plus permission sets), you have to use .def files for export, and more. The article that I’m going by is 8,500 words long (about 20 pages) and takes hours of study to understand well enough to do anything.

After going through all this I think Shunra is justified in charging $500 for their simulator. The solution is hard to write. However, Shunra doesn’t support loopback last I contacted them. My implementation does, so I think I can sell mine to gave developers and others that want a loopback solution. Plus I can put a nice GUI on it, so you can control what is going on at runtime.

I was updating the manual for RakNet and was reminded of how many data structures I’ve written for it.

From the manual:

DS_BinarySearchTree.h – Binary search tree, and an AVL balanced binary search tree.
DS_BPlusTree.h – BPlus tree for fast lookup, delete, and insert.
DS_BytePool.h – Returns data blocks at certain size thresholds to reduce memory fragmentation.
DS_ByteQueue.h – A queue specialized for reading and writing bytes.
DS_Heap.h – Heap data structure, includes both minheap and maxheap.
DS_HuffmanEncodingTree.h – Huffman encoding tree, used to find the minimal bitwise representation given a frequency table.
DS_HuffmanEncodingTreeFactory.h – Creates instances of the Huffman encoding tree.
DS_HuffmanEncodingTreeNode.h – Node in the Huffman encoding tree.
DS_LinkedList.h – Standard linked list.
DS_List.h – Dynamic array (sometimes improperly called a vector). Also doubles as a stack.
DS_Map.h – (Associative array) Ordered list with an per-element sort key.
DS_MemoryPool.h – Allocate and free reused instances of a fixed size structure, used to reduce memory fragmentation.
DS_OrderedChannelHeap.h – Maxheap which returns a node based on the relative weight of the node’s associated channel. Used for task scheduling with priorities.
DS_OrderedList.h – List ordered by an arbitrary key via quicksort.
DS_Queue.h – Standard queue implemented with an array
DS_QueueLinkedList.h – Standard queue implemented with a linked list
DS_RangeList.h – Stores a list of numerical values, and when the values are sequential, represents them as a range rather than individual elements. Useful when storing many values that are usually sequential.
DS_Table.h – Table with columns and rows, and operations on that table.
DS_Tree.h – Noncyclic graph
DS_WeightedGraph.h – Graph with weighted edges, used for routing via Dijkstra’s algorithm

Data structures is one of the few classes in college that has a significant real-world bearing. It’s one of the cornerstones of good design and optimization.

A few times I’ve been asked why I don’t just use STL.

1. STL can cause linker errors
2. STL uses exceptions.
3. STL doesn’t have every feature I need.
4. I don’t know how well STL is optimized, but I know exactly how well my code is optimized.
5. In college I was confused for months before I figured out when people said ‘vector’ they meant ‘dynamic array.’ It became a pet-peeve of mine.
6. In college I started writing my own data structures before I knew STL existed. None of my classes ever covered it And once I started I had momentum to keep going.
5. It’s something I find interesting and enjoy writing.

Aside from STL, of the game companies I’ve worked at, I’ve never seen any of them with as sophisticated a set of data structures as what I have in RakNet. When you need to process and track 30,000 messages a second you need heavy duty data structures like my memory-pool optimized B+ tree. Being able to support 30,000 messages vs. your standard game’s 20-30 messages a second is part of the polish you get with a dedicated mature library.

Back when I started RakNet 5 years ago I was talking to a marketing guy. He something like “You’ll get a sale here and there, but to really be successful you have to approach the companies directly.” My reply was “That’s fine, but I want to add these features first before I start having big companies look at it.”

I didn’t even get a sale here and there, so maybe I was right, but I did go a bit overboard. Not until last week really did I sit down, ask myself “What feature should I add next to be more competitive?” and just couldn’t think of anything.

It’s time to switch to marketing, and hopefully this time it won’t take 5 years to reach my destination.

The first thing I can think to do is partnerships. 9 months ago the tech director at SOE told me if they didn’t already know me, they would have just used Quazal, because Quazal is a featured partner of Gamebryo. But the funny thing Gamebryo doesn’t have networking. The partnership is essentially an advertisement to look at Quazal if you need a networking solution. I’m not complaining, but pointing out the importance of partnerships and alliances. People will go with what they think works, and a featured partner is more likely to work than some library on the net you’ve never worked with before.

As much as I’d like to, I don’t have the connections or clout (yet) to get RakNet into Gamebryo. But where I do have a better chance is in the open source and small game community. If the competitor’s forums are any indication, RakNet is pretty much dominant in this market, even if it’s a market that doesn’t pay very well. But more users is always better, one can always monetize later.

Step 1: Ally more closely with Ogre 3D.

Ogre 3D is a great library not just for its features but because it has a massive userbase. Any forum post gets a response nearly immediately, and that is good not just for its own sake but the support level generated by that draws even more users. I’ve had a good relationship with that community from Galactic Melee so it’s a first draw to get more eyes looking at RakNet.

In that regard, yesterday I wrote a sample that uses Ogre 3D along with RakNet to demonstrate how to do graphical network interpolation code. The users seem to appreciate it. Some people in my own forum have been asking how to do what I did there so it solves two problems.

Step 2: Irrlicht

Irrlicht seems to be the next big graphics engine. I used it back when I was writing a web based shooter. I like it better than Ogre because the style reminds me more of RakNet. I contacted the author of Irrlicht, and he agreed to add RakNet to the toolset page if I were to do add native support, which I will do in a similar fashion. I’ll do this in the upcoming week

Step 3: Partner with smaller commercial game engines

Most game engines that I searched for already had networking. While I think a dedicated library like RakNet will be more advanced than what a game engine will offer as networking on the side, it’s probably a lost cause in most cases. However, I did find a few game engines that didn’t already have networking. Maybe none of my emails will get a response, but if they do this can be a good additional revenue stream as well as benefit for said game engine. This will require a lot more work since I’d actually be learning and supporting new engines, but is also a good opportunity.

Step 4: Pursue connections

(Coincidentally) I had lunch with a very well-connected friend today and he offered to help me get my foot in the door in several big opportunities. I won’t say what, since it may not pan out anyway, but it’s really great having friends to help you out or even just discuss ideas over.

The major money comes from friends and connections. Tip to the new guys: Never burn your bridges and make an effort to make friends with people. You never know who will help you out in the future, and of course you get to return the favor.

Anyway, I’m optimistic about the next 6 months. If RakNet can get a few big partners I think things can finally take off.

I spent an entire day on Sunday thinking about the architecture on how to write a generic system to create, destroy, serialize, and control scope over networked objects in C++. It’s a very hard problem to solve because you know nothing about the game objects themselves, or what complexities the end-users might introduce with their specific architecture.

In the end I decided on 3 classes. One class, ReplicaManager2, is the base plugin for the system. All it does is essentially serialization, deserialization, transmission, and bookkeeping. Stuff you wouldn’t normally care about. I have the user pass a class factory that generates connection instances, one per connection. This controls high-level and non-object specific functionality such as how to create object instances. Lastly, there is the base class Replica2, which game objects should derive from.

The main reason I did it this way, rather than putting everything in the ReplicaManager2 plugin (as I did in its predecessor) was so that the functionality can be easily overridden. This should solve a problem I had with the old system, where I ended up passing a ton of data to the callbacks in order to force it to get it to do what I wanted. By assuming users will override functions, this also gives me the ability to make assumptions and thus much more elaborate functions.

Improvements it has over the old system are:

1. Relay across systems actually works correctly. So you could have a server cluster, with n clients on each server, and everything would just get sent out properly. It automatically deals with cyclical connection graphs up to a depth of 1 away from the source node.

2. Defaults to polling for changes. Each tick, if an object is now constructable, or in scope, and it was not in the last tick (or vice-versa) the object is created or destroyed appropriately. The object is also serialized every n milliseconds, and if it serializes differently under the same context, the newly serialized value is transmitted. This is easier to use than event-based updates (which are also supported) so the user has to write less code.

3. Downloads construct all objects first, then deserializes them, and in the order they were originally created. This is likely what a user would do were they to hand-write the download system, and maximizes the chance that pointers and other dependencies will be valid on deserialization. This also allows you to have objects that cross-reference each other when deserializing, each both have already been created anyway.

4. It’s easier to modify events and more information is given about what triggered those events. For example, it’s now trivial to send using different reliability types based on the context of what is being sent, something that was hard to do before.

5. Changes are easier to initiate on the client, especially construction, which before would have taken custom game code.

Here’s a video that goes over the system. I start out too fast because I was tired of starting over when I made mistakes, but later on it gets better.
http://www.rakkarsoft.com/raknet/manual/ReplicaManager2.html

I’m working on the second iteration of the Replica Manager class. For those that don’t know it, this class is supposed to handle the details of sending and synchronizing objects across the network as new systems connect.

My first approach was data based. All the code was in the Replica Manager itself, and it would query an interface to get the data it needed to perform operations, such as serializing objects. In most cases, this worked OK. However, the problem with games is there is always complexity to work around, especially with existing systems, and if cases came up that I didn’t anticipate it was hard to go around the system. One example in particular was the initial object download. The first system would gather up all objects, serialize, and send them to you. However, this didn’t work if objects already existed globally (such as created when the map loaded). It also didn’t work if you cared about what order objects were downloaded in, which you would if they had dependencies on each other (such as cross referencing pointers).

My new approach is more code based, with data queries exposed only for very common or unlikely to change operations. So now the Replica Manager class itself mostly just encodes and decodes queries, and holds the data structures, with the actual functionality in the Replica class, the class you derive your own game objects from. This gave me a degree of flexibility I didn’t have before, because now I can implement complex operations since I know the user can override the code if necessary. One example is having a client locally create an object which is verified by the server, and deleted or synchronized on the client accordingly. Another example is automatically scoping objects with a simple callback, where before you had to do this by writing your own system.

The test case I’m solving is:

// Preexists on all systems, has objectID, still want to register it so I can call serialize automatically
class World {
int totalKills;
}

class Player : public Participant {
Soldier *soldier;
char name[256];
int teamNumber;
char killMessage[256];
int gameInstanceId; // Players may be spread out between multiple game instances
};

class Soldier {
Player *owningPlayer, *lastDamagingPlayer;
Gun gun;
float health; // Sent reliable ordered
float positionX, positionY; // Sent unreliable sequenced
bool isCloaked; // If cloaked, do not send position to non-teammates
};

class Gun {
Soldier *owningSoldier;
Player *owningPlayer;
int ammo;
};

class Bullet {
Gun *firingGun;
Player *owningPlayer;
RakNetTime timeFired;
};

So you have:

1. Classes that have pointers to classes that have pointers to themselves in return
2. The world object is assumed to preexist, so should not be dynamically downloaded, yet still needs to be updated
3. Cloaking, where an object either won’t be serialized at all, or only partly serialized (if a teammate)
4. Pointers which may be NULL
5. Object composition with serialized objects (so their parents should be dynamically downloaded, but not the objects themselves).
6. Serializing the object using a different send type, depending on what part is serialized.

These could all be solved with the old system too, but it was much harder and you had to really understand the code to know what to disable. If I do my job this test case should be solvable trivially.

Quick note: I’m really glad a service like Sourceforge exists. After all the trouble recently with source control providers it is really awesome that I can update RakNet without having to think about if the server is up or down, or security for my code, or paying for it. Plus you get a mailing list. It’s hard to set up but I’m glad I did.