Category: Game Development

Here’s a class that given a predefined area of memory, allows you to allocate and deallocate areas of that memory. In other words, a custom memory manager.

Only partially done yet, but it’s already 25% or so faster than malloc and free
Header
CPP

Full alloc, then dealloc
Heap = 1304 us
malloc = 878256 us

Fragmentation
Heap = 3525 us
malloc = 4462 us

Most of the speedup comes from linked lists of buckets. There are 7 buckets, from 32 bytes to 2048 bytes, incrementing in powers of two. 20% of the given memory is dedicated to buckets. If an allocation is requested and a bucket is available, the allocation goes to that bucket instead. Because buckets are contiguous and reserved, those allocations cannot cause fragmentation.

The alignment boundary is 32 bytes, so all allocations returned to the user are aligned, and the average memory wasted per allocation is 32 bytes, excluding buckets.

The speeds shown are with a critical section lock. This is not necessary, and for single threads it would be even faster.

It’s been coming up a lot lately on how much I should ask for to work as a contractor, given a certain pay value as an employee. Every time I do this in my head, an hour later I kick myself because I realize I asked for too little. So I wrote a calculator in Javascript that will do all the calculations for you.

Contractor pay calculator

I’ll leave it up to the reader to write the inverse operation 🙂

First major game to show the RakNet logo prominently. There’s another AAA game out there that uses RakNet but they don’t show the logo.
http://www.us.playstation.com/PS3/Games/JEOPARDY

Unfortunately, they edited the middleware splash screen out of the video on the site.

The most difficult part of contracting on this project was working with 3rd party code. This is one of those cases where it would have been faster to write your own systems from scratch. In the end it did well though and the game is pretty much bug-free.

I’m almost done writing the new lobby system (Lobby2) for RakNet. The original design had a huge list of functions in a single class such as:

virtual void RegisterAccount(LobbyDBSpec::CreateUser_Data *input, SystemAddress lobbyServerAddr);
virtual void UpdateAccount(LobbyDBSpec::UpdateUser_Data *input);
virtual void ChangeHandle(const char *newHandle);

You would get back a callback with a result code, such as

virtual void RegisterAccount_Result(LobbyClientCBResult result){};
virtual void UpdateAccount_Result(LobbyClientCBResult result){};
virtual void ChangeHandle_Result(LobbyClientCBResult result){};

The mistakes I made were:

1. The database was designed to be more like a file system, storing the results of commands executed in C++, rather than processing the commands themselves. The problem was this was a huge amount of code. Sometimes it wasn’t really possible to synchronize the C++ and the database. Complex cases such as not allowing clan commands unless you were the clan leader were not handled well.
2. Result codes were generic and reused between commands. The problem was that this was imprecise. Sometimes more than one result code could apply, and you were never really sure which result codes could be returned.
3. You often didn’t have sufficient context about what the result is referring to. For example, if I got a change handle callback that failed because the name was already in use, what name had I been trying to change to?
4. The only way to extend the system was to derive a new class, understand the flow of the whole system, and write a huge amount of code.

On the positive side, having everything in one class did lead to good encapsulation and efficiency. All the systems could work together very smoothly with maximum performance efficiency.

In my own defense, a certain platform I have been programming on makes mistakes 2 and 3 as well.

Anyway, I’ve rewritten the system with those mistakes in mind.

1. The database performs the actual functionality, with almost no operative code in C++. This is more scalable, easier to extend, and can handle cases of any complexity.
2. Result codes are specific. There’s a small set of shared result codes, such as:

L2RC_SUCCESS,
L2RC_DATABASE_CONSTRAINT_FAILURE,
L2RC_PROFANITY_FILTER_CHECK_FAILED,

Besides that, the result codes directly apply to operations. So you know not only what codes you will get, but what codes you won’t get.

{REC_ENTER_ROOM_UNKNOWN_TITLE, “Failed to enter a room. Unknown title (Programmer error).”},
{REC_ENTER_ROOM_CURRENTLY_IN_QUICK_JOIN, “Failed to enter a room. You are currently in quick join. Leave quick join first.”},
{REC_ENTER_ROOM_CURRENTLY_IN_A_ROOM, “Failed to enter a room. You are already in a room.”},

3. What used to be function parameters are now structures. Structures have in and out parameters. The same structure is used to send the command, and to notify the user of the result of that command. So the system to a large extent is stateless, because the relevant state data is stored in the packet itself. This is less bandwidth efficient but much easier to use:

struct System_GetTitleRequiredAge : public Lobby2Message
{
__L2_MSG_BASE_IMPL(System_GetTitleRequiredAge)
virtual bool RequiresAdmin(void) const {return false;}
virtual bool CancelOnDisconnect(void) const {return true;}
virtual void Serialize( bool writeToBitstream, bool serializeOutput, RakNet::BitStream *bitStream );
virtual bool PrevalidateInput(void) {return true;}

// Input parameters
RakNet::RakString titleName;

// Output parameters
int requiredAge;
};

4. Because commands are encapsulated in a single structure, all you have to do to extend the system is write a new command and add that command to the class factory (which is one line of code). You can also override existing commands by passing your own class factory.

The C++ is essentially done at this point, except for clean-up and documentation. This system is much more complete than the old system:

1. System_CreateDatabase (Admin command)
2. System_DestroyDatabase (Admin command)
3. System_CreateTitle (Admin command)
4. System_DestroyTitle (Admin command)
5. System_GetTitleRequiredAge
6. System_GetTitleBinaryData
7. System_RegisterProfanity (Admin command)
8. System_BanUser (Admin command)
9. System_UnbanUser (Admin command)
10. CDKey_Add (Admin command)
11. CDKey_GetStatus (Admin command)
12. CDKey_Use (Admin command)
13. CDKey_FlagStolen (Admin command)
14. Client_Login
15. Client_Logoff
16. Client_RegisterAccount
17. System_SetEmailAddressValidated (Admin command)
18. Client_ValidateHandle
19. Client_DeleteAccount
20. System_PruneAccounts
21. Client_GetEmailAddress
22. Client_GetPasswordRecoveryQuestionByHandle
23. Client_GetPasswordRecoveryAnswerWithQuestion
24. Client_ChangeHandle
25. Client_UpdateAccount
26. Client_StartIgnore
27. Client_StopIgnore
28. Client_GetIgnoreList
29. Friends_SendInvite
30. Friends_AcceptInvite
31. Friends_RejectInvite
32. Friends_GetInvites
33. Friends_GetStatus
34. Friends_Remove
35. RecentUsers_Add
36. RecentUsers_Get
37. Emails_Send
38. Emails_Get
39. Emails_Delete
40. Emails_SetStatus
41. Emails_SetWasRead
42. Ranking_SubmitMatch
43. Ranking_GetMatches
44. Ranking_GetMatchBinaryData
45. Ranking_GetTotalScore
46. Ranking_WipeScoresForPlayer
47. Ranking_WipeMatches
48. Ranking_PruneMatches
49. Ranking_UpdateRating
50. Ranking_WipeRatings
51. Ranking_GetRating
52. Clans_Create
53. Clans_SetProperties
54. Clans_GetProperties
55. Clans_SetMyMemberProperties
56. Clans_GrantLeader
57. Clans_SetSubleaderStatus
58. Clans_SetMemberRank
59. Clans_GetMemberProperties
60. Clans_ChangeHandle
61. Clans_Leave
62. Clans_Get
63. Clans_SendJoinInvitation
64. Clans_WithdrawJoinInvitation
65. Clans_AcceptJoinInvitation
66. Clans_RejectJoinInvitation
67. Clans_DownloadInvitationList
68. Clans_SendJoinRequest
69. Clans_WithdrawJoinRequest
70. Clans_AcceptJoinRequest
71. Clans_RejectJoinRequest
72. Clans_DownloadRequestList
73. Clans_KickAndBlacklistUser
74. Clans_UnblacklistUser
75. Clans_GetBlacklist
76. Clans_GetMembers
77. Clans_CreateBoard
78. Clans_DestroyBoard
79. Clans_CreateNewTopic
80. Clans_ReplyToTopic
81. Clans_RemovePost
82. Clans_GetBoards
83. Clans_GetTopics
84. Clans_GetPosts
85. Notification_Client_IgnoreStatus (Admin command)
86. Notification_Friends_StatusChange (Admin command)
87. Notification_Friends_ChangedHandle (Admin command)
88. Notification_Friends_CreatedClan (Admin command)
89. Notification_Emails_Received (Admin command)
90. Notification_Clans_GrantLeader (Admin command)
91. Notification_Clans_SetSubleaderStatus (Admin command)
92. Notification_Clans_SetMemberRank (Admin command)
93. Notification_Clans_ChangeHandle (Admin command)
94. Notification_Clans_Leave (Admin command)
95. Notification_Clans_PendingJoinStatus (Admin command)
96. Notification_Clans_NewClanMember (Admin command)
97. Notification_Clans_KickAndBlacklistUser (Admin command)
98. Notification_Clans_UnblacklistUser (Admin command)

Now I’m just waiting for the DB programmer to write all the queries.

It takes 11 lines of code to do this query in PostgreSQL with binary parameters, such as non-escaped strings or binary data. Here, I pass a parameter as a string, so have to escape it to prevent SQL injection attacks.

char *outTemp[3];
int outLengths[3];
int formats[3];
formats[0]=PQEXECPARAM_FORMAT_TEXT;
formats[1]=PQEXECPARAM_FORMAT_BINARY; // Always happens to be binary
formats[2]=PQEXECPARAM_FORMAT_BINARY; // Always happens to be binary
sprintf(query, “INSERT INTO FileVersionHistory(applicationID, filename, createFile, changeSetID, userName) VALUES (%i, $1::text,FALSE,%i,’%s’);”, applicationID, changeSetId, GetEscapedString(userName).C_String());
outTemp[0]=deletedFiles.fileList[fileListIndex].filename;
outLengths[0]=(int)strlen(deletedFiles.fileList[fileListIndex].filename);
formats[0]=PQEXECPARAM_FORMAT_TEXT;
result = PQexecParams(pgConn, query,1,0,outTemp,outLengths,formats,PQEXECPARAM_FORMAT_BINARY);

With my new function, ExecVaridic, it’s one line of code.

result = ExecVaridic(“INSERT INTO FileVersionHistory(applicationID, filename, createFile, changeSetID, userName) VALUES (%i, %s, FALSE,%i,%s);”, applicationID, deletedFiles.fileList[fileListIndex].filename, changeSetId, userName.C_String());

Why has no one thought of this before?

I support binary data too.

result = ExecVaridic(“INSERT INTO fileVersionHistory(binaryData) VALUES (%c)”, binaryData, binaryDataLength);

%c is my own extension, to mean binary data followed by length.

No string escaping necessary.

Here’s the code:
AutopatcherPostgreRepository.cpp

See PostgreSQLInterface::ExecVaridic

I’m continuing work on my rewrite of RakNet’s Lobby system. The reason I’m rewriting it is because the original architecture over-duplicates functionality, resulting in a tremendous amount of work.

For every function I had to:

1. Expose an interface
2. Serialize the user’s parameters
3. Validate the user’s parameters on the client
4. Do the send call
5. Parse the received packet on the server.
6. Check incoming parameters
7. Do C++ processing before the database call. For example, checking that a user is a member of a clan before doing a clan operation.
8. Pack the parameters into a functor
9. Process the functor (which itself required writing, and a unit test).
10. Parse the results from the functor
11. Do more C++, such as notifications, and update state memory
12. Send the result to the client
13. Process the result on the client, updating state memory
14. Return the result to the user.

It takes like 15 minutes of concentrated typing and copy/paste to do all this. State memory was potentially duplicated in the database, the server, and the client. I was going to add a GUI on top of it, which is yet another level of processing for each function.

The new design packs pretty much all 14 of those steps into one structure. The same structure:

Holds input and output parameters
Serializes and deserializes those parameters
Has as a member function the database procedure.
It itself a callback
Has a factory class that can create instances of itself

It uses defines to automatically add in functionality where appropriate.

All of the functionality will be in a single thread, spawned and separate from the main thread. Only rooms will be stored and processed in memory – clans, email, message boards, etc. are all done as stored procedures. This is to avoid the need to duplicate data both in memory and in the database, which I had to do with clans and in various other cases.

Furthermore, I’ve split the rooms functionality into its own module, which I can unit test without the headache of trying to test it in the context of a larger system. Unlike my old system, both the client and the server will use this same module to represent rooms. The only difference is the server has more information, meaning that I don’t have to write custom rooms code for the client.

I think all these changes will drop the code size by 75%. Speed will theoretically be slower, as I’m doing some stuff in the database that I could have done in C++. However, with so much less code, the compiler may be able to optimize it better.

For improvements, I’ve learned a lot working on Jeopardy’s lobby system. I’m going to improve on their system as follows:

1. Support a command to automatically create a room if joining fails. Rather than requiring the user to join OR create.
2. Store which room you just left, and don’t rejoin that room if another room can be joined instead.
3. Quick join means join a room as soon as doing so with other quick join members will fill that room based on your search filters.
4. Spectator support (old system had this too)
5. Operation result callbacks always specify which room / user they are referring to, so you can reject the message if it is no longer relevant.
7. Room invitations are emails, but are automatically cleared when the room no longer exists.
8. Room specific operations are automatically canceled when you shut down the system or leave the room (this is just common sense).
9. Support for text-based chat between room members. The client has the ability to filter profanity. The client also has a persistent mute list.
10. Server based ready states for room members (old system had this too). Less useful for peer to peer, but good for client/server.

I was also thinking of an enemies list – people you don’t play with. The problem is while you can stay out of rooms that have your enemies, it’s not fair to keep your enemies out of rooms you are already in. Otherwise, if one player was hated enough he may never be able to join rooms. If the enemies list was one-way, you’d wonder why your enemies could still join your room. So I dropped that idea.

At work today I was investigating a bug where the system shuts down in random code when you quit. There was no information as to why it crashed, and it crashed past the point where the debugger could catch it.

After a day of binary searching and logging, I found the culprit. The API provides a very slow asynchronous function. If you stop the relevant library before the function completes, it causes the shutdown crash noted above. It also causes the library to fail to reload after you shut it down. I actually was waiting for the asynchronous function, but my code to prevent blocking forever wasn’t waiting long enough:

DoAsynchFunction();
while (IsCompleted() && ElapsedTime() < 500)
Block();

This is like the 3rd time I’ve run into similar issues with this API. These kinds of design flaws (originally with DirectPlay) are what inspired me to write RakNet – a library that exposes functionality at the level users care about, rather than at the level the computer cares about.

Lessons that could be learned here

1. Libraries need to clean up after themselves. If an asynchronous function is still processing, memory is still allocated, a dialog is visible, or whatever, just clean it up. It’s not acceptable to just crash instead, especially not at some random pointer later on.
2. If an asynch function is going to take a longer than one would expect for what it does, it needs to be documented and the timeout controllable.
3. If a library fails to load or reload, the error code needs to be specific and indicate how to solve the problem. This is about the 5th time with this API that I’ve gotten error messages such as “BUSY” or “INVALID STATE”
4. If a function or library is going to fail, it should fail consistently. Failing half the time depending on irrelevant factors such as calls to other functions makes it very difficult to find the root of the problem.
5. Functions should take care of their own dependencies when possible.

Examples of what RakNet does

1. If you call Shutdown() at the same time you have an asynchronous send, disconnect, or connect pending, RakNet will block for the amount of time you specify, and then shut down, cleaning up these asynchronous functions for you. If you call CloseConnection(), you have the option to leave the connection open until pending messages are sent, and can also cancel at any time. RakNet has a specific test that calls every function at random for as long as you want, and it will run without crashing.
2. Every asynch function in RakNet is fast – connecting takes on average 4 X your ping, disconnection takes from no time to 2 X your ping. The time to disconnect on no data sent is controllable, and you can cancel every asynch function.
3. Most RakNet functions that can fail never do so in practice. This because RakNet will take care of dependencies for you, because it follows the principle that even if it’s 10X harder for RakNet to take care of than the user, it’s still worthwhile. Functions that can fail return specific codes – for example if you call an RPC with the wrong number of parameters, it will return this exact error, as well as the function called that caused this error.
4. All RakNet functions that can fail do so consistently. RakNet does not make state assumptions about preconditions, which if untrue, cause inconsistent behavior
5. If you call Connect() to a system you are already connected to, it will take over the existing connection. If you call it at the same time as the other system, both will complete. If the other system starts up later than your system, it will still complete. RakNet does everything it can to honor your request.

RakNet isn’t perfect and it would be easy to pick holes in cases where it doesn’t do these things. But I think the principle stands. It’s worthwhile for an API author to spend a week implementing a feature that would take the user 5 minutes to work around. The API author only has to spend the week once, but several hundred users may have to spend 5 minutes each.

You can call functions on remote systems, with automatically serialized parameters, with a large range of supported types.

Video

Based on forum suggestions I’m looking into boost::bind and boost::function to do RPC calls rather than my current assembly code based system.

I may be misunderstanding what it does, but I believe that boost::function is a way to store function pointers (regular or object member). And boost::bind allows you to bind parameters to function pointers. Using templates, you can pass complex object types on the stack. My existing assembly implementation can only pass simple structures.

If I’m correct, I can do something like this:

void DoSomething(MyObject myObject) {…}
Call(“DoSomething”, myObject);
(On the remote system)
boost::function ptrToDoSomething;
(use boost::bind to bind a stack based instance of MyObject to DoSomething)
(Somehow call DoSomething)

I’m a bit vague on the details now but if it works it will compile out to what is essentially a native function call.

Another problem with my existing implementation of RPC is I am using memcpy for the parameter list. This won’t work with complex types that have custom serialization – even including strings. But by overloading < < and >> I can add support for this.

Normal types get a general template.

template <class templateType>
BitStream& operator<<(BitStream& out, const templateType& c)
{
out.Write(c);
return out;
}
template <class templateType>
BitStream& operator>>(BitStream& in, templateType& c)
{
bool success = in.Read(c);
assert(success);
return in;
}

The user can then overload types for a particular class, just replace tempateType with the name of the relevant class.

If this all works out I will finally have the ultimate implementation of RPC calls.

1. Works with C functions and object member functions, including those that use multiple inheritance, with an arbitrary inheritance order
2. Can pass types that use complex serialization (such as my string compression).
3. Can call functions that take complex types in the parameter list, types that cannot fit in a single register.
4. I think I can even do automatic object pointer lookups within parameter lists

In other words, the ability to call any authorized function on a remote system, using any type of parameter, including referenced pointers, with any type of data. Pretty exciting 🙂