The Joshua Tree

1 in 600,000

noreply@blogger.com (Joshua Kriegshauser) — Fri, 06 Jan 2012 06:03:00 +0000

For Christmas this year, my wife gave me (among other things) Another Tough Puzzle. This puzzle claims that "with millions of wrong solutions, the chance of solving this puzzle is ONE in 600,000!"

There are 16 triangular pieces and each piece has three connections each being one of four possible shapes. The completed puzzle should be a pyramid with six connections on the edges pointing in and six pointed out.

The puzzle also claims that "it looks easy...but just when you think you've solved it, the last piece proves you wrong." This is very true and very frustrating. I (and others) played around with the puzzle for a while always ending up with one piece that didn't fit.

Then I thought, "I write software for a living; why don't I do that here?" I've enjoyed writing solvers in the past (my Minesweeper solver would actually play the GUI for you on previous Windows versions). I mostly use C++, so I decided to use it here as well. Certainly there are languages more suited to rapid development, but I'm a glutton for punishment.

The first step was to describe the pieces. We noticed pretty quickly that half of the pieces have two outward-facing connectors (outputs) and one inward-facing connector (input) and the other half are opposite (two inputs and one output). There are no pieces with three inputs or outputs.

enum FaceType
{
    eFaceTypeClover = 0,
    eFaceTypeHeart,
    eFaceTypeSpade,
    eFaceTypeDiamond,
};

enum Direction
{
    eDirIn = 0,
    eDirOut,
};

struct Node
{
    FaceType face;
    Direction dir;

    bool fits(const Node& rhs) const
    {
        return face == rhs.face && dir != rhs.dir;
    }
};
struct Piece
{
    Node node[eNumSides];

    Piece(FaceType in, FaceType out1, FaceType out2, bool)
    {
        node[0].face = in;
        node[1].face = out1;
        node[2].face = out2;
        node[0].dir = eDirIn;
        node[1].dir = node[2].dir = eDirOut;
    }
    Piece(FaceType in1, FaceType in2, FaceType out)
    {
        node[0].face = in1;
        node[1].face = in2;
        node[2].face = out;
        node[0].dir = node[1].dir = eDirIn;
        node[2].dir = eDirOut;
    }
};

Using these structures, all of the pieces can be declared:

Piece pieces[eNumPieces] =
{
// one input, two outputs
Piece(eFaceTypeSpade, eFaceTypeDiamond, eFaceTypeHeart),        // 0
Piece(eFaceTypeHeart, eFaceTypeDiamond, eFaceTypeSpade),        // 1
Piece(eFaceTypeDiamond, eFaceTypeClover, eFaceTypeSpade),       // 2
Piece(eFaceTypeClover, eFaceTypeSpade, eFaceTypeHeart),         // 3
Piece(eFaceTypeSpade, eFaceTypeHeart, eFaceTypeClover),         // 4
Piece(eFaceTypeHeart, eFaceTypeSpade, eFaceTypeClover),         // 5
Piece(eFaceTypeSpade, eFaceTypeClover, eFaceTypeDiamond),       // 6
Piece(eFaceTypeDiamond, eFaceTypeClover, eFaceTypeHeart),       // 7

// two inputs, one output
Piece(eFaceTypeClover, eFaceTypeDiamond, eFaceTypeHeart, true), // 8
Piece(eFaceTypeClover, eFaceTypeDiamond, eFaceTypeSpade, true), // 9
Piece(eFaceTypeHeart, eFaceTypeDiamond, eFaceTypeSpade, true),  // a
Piece(eFaceTypeHeart, eFaceTypeClover, eFaceTypeDiamond, true), // b
Piece(eFaceTypeHeart, eFaceTypeClover, eFaceTypeSpade, true),   // c
Piece(eFaceTypeDiamond, eFaceTypeClover, eFaceTypeHeart, true), // d
Piece(eFaceTypeDiamond, eFaceTypeClover, eFaceTypeSpade, true), // e
Piece(eFaceTypeSpade, eFaceTypeHeart, eFaceTypeDiamond, true)   // f
};

Now that the pieces are all set up, the gameboard must be described. The end result should be a pyramid made up of all 16 pieces (see diagram). Therefore, I had to describe how the pieces relate to each other in the gameboard. This will allow the solver algorithm to test that a piece 'fits' if its connectors match the adjacent pieces. In order to do this, each position in the desired puzzle shape is marked with a number and each side of the triangular pieces are numbered as well. The sides are always numbered clockwise starting at the horizontal side so that adjacent pieces in the puzzle have sides matching (for instance, pieces 7 and 8 both share their side number 2).

The array of PieceLoc structures define how each piece relates to adjacent pieces:

PieceLoc locs[eNumPieces] =
{
// Sides:     0               1               2          // Pieces
PieceLoc(eInvalidPiece,  eInvalidPiece,              1), // 0
PieceLoc(            7,              2,              0), // 1
PieceLoc(eInvalidPiece,              1,              3), // 2
PieceLoc(            9,              4,              2), // 3
PieceLoc(eInvalidPiece,              3,              5), // 4
PieceLoc(           11,              6,              4), // 5
PieceLoc(eInvalidPiece,              5,  eInvalidPiece), // 6
PieceLoc(            1,  eInvalidPiece,              8), // 7
PieceLoc(           12,              9,              7), // 8
PieceLoc(            3,              8,             10), // 9
PieceLoc(           14,             11,              9), // a
PieceLoc(            5,             10,  eInvalidPiece), // b
PieceLoc(            8,  eInvalidPiece,             13), // c
PieceLoc(           15,             14,             12), // d
PieceLoc(           10,             13,  eInvalidPiece), // e
PieceLoc(           13,  eInvalidPiece,  eInvalidPiece)  // f
};

The fitting function is recursive. The first time it is called it has all 16 pieces remaining to try and fit. It loops through all remaining pieces rotating them in all possible positions each time checking to see if the piece fits. If the piece fits, it calls itself again this time with 15 pieces remaining. When a pieces is found that fits, it calls itself again with 14 pieces remaining. And so on, and so forth until all pieces have been used. If a piece doesn't fit, it goes on to the next piece. If a solution is found or no more pieces fit, the function returns and tries the next piece.

Since we only have 16 pieces, I use a bitmask to determine which pieces are already used.

void FitRemaining(int remain)
{
    if (remain <= 0)
    {
        ShowSolution();
    }
    else
    {
        int index = eNumPieces-remain;
        for (int i = 0; i < eNumPieces; ++i)
        {
            if ((used & (1 << i)) == 0)
            {
                used |= (1 << i); // Mark in-use
                pieces[index] = i;
                for (int r = 0; r < eNumRotations; ++r)
                {
                    rotation[index] = r;
                    if (validate(index))
                    {
                        FitRemaining(remain - 1);
                    }
                }
                pieces[index] = eInvalidPiece;
                used &= ~(1 << i); // No longer in-use
            }
        }
    }
}

The last part is the validation function. We really only need to validate the most recent piece added. Figuring out which sides are facing each other is the most difficult part, but even that is pretty easy. Because of how the gameboard is organized we already know that side indexes on adjacent pieces always face each other. All we need to do is take the rotation into account and ensure that the shapes match:

bool validate(int piece) const
{
    assert(piece >= 0 && piece < eNumPieces);
    const Piece* cur = Get(piece);
    int rot1 = rotation[piece];
    const PieceLoc& fit = locs[piece];
    for (int f = 0; f < eNumSides; ++f)
    {
        const Piece* p = Get(fit.neighbors[f]);
        if (p)
        {
            int rot2 = rotation[fit.neighbors[f]];
            if (!cur->node[(rot1 + f) % 3].fits(p->node[(rot2 + f) % 3]))
            {
                return false;
            }
        }
    }
    return true;
}

That's all there is to it! I probably spent less time writing this program than manually (and frustratingly) trying to find the solution.

In fact with this program I found all 518,469 solutions to the puzzle. Here's the first one:

GDC Online 2011

noreply@blogger.com (Joshua Kriegshauser) — Thu, 21 Jul 2011 21:44:00 +0000

I haven't done a speaking engagement since LOGIN 2009, but I really enjoyed it, so I figured it was high time to give it another shot.

(And no, acting out Beyoncé's Single Ladies dance on stage at the Developer War Stories panel of Fan Faire 2011 doesn't count.)

I've always enjoyed attending GDC Online (formerly GDC Austin or Austin Game Developers' Conference) and since it has always catered to a large crowd of online game developers (and I do miss Austin a bit), it's as good as any a place to foist my shenanigans on the somnolent audience.

This year I'll be talking about the trials and tribulations of taking a square peg never designed for streaming, EverQuest II and inserting it into a round hole. If you've read this blog, I've mentioned things about this before, but this is your opportunity to see the veil ripped away and the nitty-gritty of the good and bad choices that were made.

If you're heading to GDC Online (and you should for this lecture alone!), click here to see the lecture in their Schedule Builder.

Also (and completely to my surprise), Gamasutra listed my lecture as a 'highlight' of GDC Online. Fortunately they don't know me that well yet. ;D

Philosophy of Code

noreply@blogger.com (Joshua Kriegshauser) — Fri, 01 Apr 2011 01:09:00 +0000

Programming in a business environment requires creating a product or service that is intended to produce a higher profit than cost. However, I believe that few programmers understand this or think about it on a daily basis. At the end of the day, we must be working towards making a profit.

I'll be the first to tell you that I'm not a business major. I'm not an economist. I love programming and was best friends with a keyboard in the third grade. I can write code like the dickens but I'm no Wizard of Business. However, throughout the past year working on Clone Wars Adventures I've had time (while my code is compiling) and inclination to reflect on the nature of programming in a business environment.

I've basically come to the conclusion that programming is a balance of three distinct yet intertwined facets: Developer Efficiency, Code Correctness and Performance. I call this the Philosophy of Code:

Performance - How quickly the code executes.
Developer Efficiency - How quickly developers are able to complete tasks.
Code Correctness - Adherence to best practices (avoiding global memory, avoiding macros, namespaces, templates, etc.).

These three aspects are not necessarily mutually exclusive. Every programming task that we work on has some balance of the above. However, when evaluating this philosophy from a business perspective, I've come to believe that the most important element of the triad is Developer Efficiency. Developing a Philosophy of Code that puts emphasis on Developer Efficiency will allow your programmers (and incidentally your entire development team) to work faster and smarter. It can also require less code to be written and fewer bugs.

Mutual Exclusivity
In some cases, an Efficiency-based Philosophy of Code will compromise the Performance and Code Correctness aspects. For instance, EverQuest II has a console-variable system. With one line of code in an implementation file I can add a semi-constant: a named value that can be changed by typing a slash-command into the chat window:

CV_FLOAT(max_radius, 30.0);

Presto. This is like saying float max_radius = 30.0; but I can also change it in real-time by typing "/max_radius 25" into the chat window. This typically is frowned upon from Code Correctness aspects for a few reasons:

It uses macros
It uses global memory
It causes code to execute before main()

If your Philosophy of Code leans towards Code Correctness, doing it the Right Way™ would entail at least:

Creating a manager object as a member of your application manager class
Writing explicit code to register a member of your class with the manager object
Writing explicit code to unregister that member when your class instance is destroyed
A lot more than one line of code

Leaning towards Code Correctness over Developer Efficiency in this case would require that your programmers spend more time writing code and compiling (since members are typically declared in header files) to accomplish a very simple task.

Compile Times
In some cases, Code Correctness philosophies can institute policies that work to the detriment of Developer Efficiency:

Extensive use of templates
Excessive class declarations
Lack of forward declarations

Excessive templatization typically means that header files are included in more places and more code is written in header files. When header files are changed, they require more of the code to be rebuilt. More code written in header files can also contribute to longer link times.

Time spent compiling and linking can't necessarily be taken at face value. As programmers wait for a rebuild they tend to do something else which probably takes longer than the rebuild. The shorter the rebuild time, the more likely the programmer is going to stay focused. From a Developer Efficiency perspective, it's in your best interest to keep compile times as low as possible.

Code Bloat
The less code that is required to perform a task, the more efficiently a developer can implement said code. I'll give another practical example from EverQuest II. I've previously mentioned a bit about how the designer data system works. Every server-side data file uses the same data format. As such, no special code is required to load each type of file. Weapons, quests, characters, everything is all defined by the same generic data description language. To load data from any data file uses a simple interface:

DataObject* pObject = DataLoader::Load("weapons/sword_of_awesomesauce");
if (pObject->IsA("Weapon"))
{
  String name = pObject->GetField("Name").AsString();
}

Due to data object inheritance, pObject may actually be a Sword, but inherits from Weapon. The server's object model is further generified so that instantiating any object requires just providing the type:

Item* pItem = ObjectFactory::Spawn(Item::Type, "weapons/sword_of_awesomesauce");
if (pItem && pItem->IsA(Weapon::Type))
{
 // Successfully spawned and is actually a Weapon.
}

In other words, there is very little code that needs to be written to add a new game object type.

Conclusion
Programmers should consider their Philosophy of Code. I believe that focusing on Developer Efficiency in a business setting makes the most sense given the deadlines, the complexity of the tasks at hand, and the goal to make a profit.

Debugging information cannot be found? No Problem!

noreply@blogger.com (Joshua Kriegshauser) — Wed, 23 Mar 2011 16:50:00 +0000

In my last post, I discussed the frustrations of Visual Studio 2005 (and later versions) not being able to locate debugging information, even though it was present and fully usable by other tools.

I believe I have discovered a workaround that works nearly all the time: Remote Debugging.

It turns out that running the Remote Debugging Monitor on the same machine and setting up the project to use Remote Debugging seems to work around whatever issue Visual Studio is experiencing.

Remote Debugging is really useful if another machine is experiencing a problem that you can't reproduce locally. The Remote Debugging Monitor is primarily intended to run on a different machine than Visual Studio, but can also run on the same machine.

Here is how to set up Remote Debugging:

Generally, the machine running the Remote Debugging Monitor will need the files. These are found under the Visual Studio install location: C:\Program Files (x86)\Microsoft Visual Studio 8\Common7\IDE\Remote Debugger\x86 (for 32-bit) or C:\Program Files\Microsoft Visual Studio 8\Common7\IDE\Remote Debugger\x64 (for 64-bit).
Copy the files from the above directory to the machine that will run the Remote Debugging Monitor (skip if you are running the Monitor locally).
To start the Remote Debugging Monitor, run msvsmon.exe. If you are running locally, there should be shortcuts in the start menu:
Configure the options if necessary. Take note of 'Server name'.
Configure your project to do Remote Debugging. Change the 'Debugger to launch' to 'Remote Windows Debugger'. The 'Remote Server Name' must match the 'Server name' configured above if using Windows Authentication. If you are running the Monitor on a remote machine, the Remote Command and Working Directory will be paths on the remote machine.

When you Start Debugging, Step Into or Step Over to start debugging the application, Visual Studio will now connect to the Remote Debugging Monitor. You should be able to verify this by looking at the Remote Debugging Monitor and seeing how many connections it has.

So far this appears (for me at least) to be a successful work around to the 'Debugging information for 'X.exe' cannot be found or does not match. No symbols loaded.' error message. There have only been about two times in the past month where a problem occurred. In those cases, a restart of Visual Studio (and killing mspdbsrv.exe) fixed it.

Please let me know if this worked for you!

The (current) Bane of my Existence

noreply@blogger.com (Joshua Kriegshauser) — Fri, 04 Feb 2011 01:23:00 +0000

Yes, Microsoft Visual Studio 2005, I'm looking at you.

Whenever I try to run the Clone Wars Adventures AdminClient in the debugger, I have about an 80% chance of seeing this:

This is a debug build. I most assuredly have debug symbols turned on:

And I'm not the only one to ever have this problem. People have also reported this problem on VS2008.

Oddly enough, no one else on my team has been complaining about this problem. When I start VS2005, I can generally run the client in debug once or twice and then I perpetually get this error.

Sometimes, exiting VS2005 and killing mspdbsrv.exe followed by a restart of VS2005 usually allows me to run a couple more times. However, with our huge solution (112 projects), this takes a few minutes or so. Definitely not conducive to small changes.

Some of the links above have responses from MS folks who state that they aren't able to reproduce the problem, but there is most definitely a problem.

I've only experienced this problem on our internal AdminClient, which, unfortunately, is the project that I'm most often trying to run. Other projects in the solution file seem to work just fine. I've tried several suggestions from the above links, including others like replacing dbghelp.dll with the latest version, altering the symbol search paths, trying to manually load symbols, and so on.

As a last-ditch effort, some of the links above suggest re-installing VS2005. I'll give that a shot.

If that doesn't work, I may have to become a Pirate or something.

Update: (3/23/2011): I believe I have found a work-around by using the Remote Debugging Monitor. More info in this post.

Ladies and Gentlemen, we are LIVE!

noreply@blogger.com (Joshua Kriegshauser) — Wed, 15 Sep 2010 14:14:00 +0000

(Read the title in your best Bruce Buffer voice).

My new game, Clone Wars Adventures, is now LIVE and out of Beta! It's free to play and easy to download so head on over to the website and check it out!

Open Beta!

noreply@blogger.com (Joshua Kriegshauser) — Sat, 28 Aug 2010 05:01:00 +0000

My new game, Clone Wars Adventures, is now in Open Beta! Head on over, create an account and let us know what you think on the forums (must sign in with your Station name)!

Finally!

noreply@blogger.com (Joshua Kriegshauser) — Tue, 01 Jun 2010 16:48:00 +0000

We just announced the new game that I'm working on. Finally I can talk about it!

So, without further ado:

This is a new online free-to-play PC game targeted to kids (and adults) due out this fall. It is built upon the technology first developed for Free Realms. It will be largely mini-game based allowing things from Lightsaber Dueling to Speederbike Racing, the obligatory Starfighter missions and even a 3D tower defense game called Republic Defender. However, there is still a large social aspect with friends, housing, leaderboards and even a kid-friendly Facebook-inspired profile page.

On a personal note, this is a great project to be on. I am a huge Star Wars geek (over 15,000 LEGO bricks in my office representing different Star Wars ships) and my son loves Star Wars and the Clone Wars (and, incidentally, this game too!).

I hope you enjoy the teaser site and video. I look forward to actually being able to show in-game demos (*ahem* E3 *cough*)!

Update 6/1/2010 1:47PM PST:

/resurrect iPhone

noreply@blogger.com (Joshua Kriegshauser) — Thu, 15 Apr 2010 07:51:00 +0000

I broke my iPhone 3G. Again.

A few months ago I dropped it in the supermarket. It landed flat on the screen and when I picked it up I was horrified to discover a spiderweb-shaped crack in the screen. Fortunately, everything still worked. For $70 I had it repaired at Volt Mobile. They did pretty good work, but the touchscreen was intermittent (I'd have to flex the phone to make it work again).

Last week, I dropped it again. This time the touchscreen was completely broken--I couldn't even turn the phone off or enter my passcode to do a backup.

This time, I figured I'd try my own repair. Hey, it's worked in the past.

A quick look online shows several places that sell digitizers (touchpads), LCD screens, batteries, you name it. I ended up going with a digitizer sold from AccessoryOne (which purports to be OEM) for less than $20 shipped and taxed. There is also a three-part video series on cracking open the iPhone and swapping out the digitizer. The videos are made by http://www.directfix.com/ who also have parts but tend to charge a bit more.

This blog basically chronicles my repair. If you're doing this yourself, watch the videos; they're much more informative. Also, there is no guarantee that this will work, and it will void your warranty (mine has already expired). I just figured that I'll be upgrading to the 4th-generation iPhone when it comes out anyways.

The first step was pulling out the screen assembly. Two screws from the base (near the speakers) are all that is holding the screen assembly on. Unlike the videos, I used a suction cup on the screen near the home button to pull the screen out. I believe this works better and doesn't molest the rubber seal around the screen assembly. This picture shows the screen assembly removed from the base:

This picture shows the new digitizer/glass on the left top, the removed LCD screen on the left bottom and the old frame/digitizer assembly on the right bottom:

Removing the LCD screen is tricky and must be done carefully. I've read posts from people who crack their LCD screens at this step and it's a much more expensive component. I was very gentle.

The digitizer that I ordered was just the glass/digitizer combo; it didn't include the screen frame or the components that are mounted to it (speaker, skin sensor, home button, etc). Therefore, the frame must be removed from the original glass/digitizer and attached to the new one. This was probably the most tricky part. It involves using a hair dryer to weaken the glue and pry the frame off. Then new two-sided tape must be applied to the frame and attached to the new glass/digitizer.

This picture shows the removed frame (bottom center) and the old cracked digitizer on the bottom right:

After a few minutes of work, the frame was attached to the new glass/digitizer:

The new glass had an appropriate amount of protective film, so it was fairly easy to minimize dust getting in between the screen and the glass. The new screen assembly with LCD installed is now shown on the bottom:

After getting the screen cables connected I powered on the phone and was able to enter my passcode to unlock the phone (note that the protective film is still on the screen, hence the sticker in the middle of the screen):

Yay! All-in-all, a very successful repair for under $20 and about an hour.

Now... to find a better case...

Be Careful with Default Arguments

noreply@blogger.com (Joshua Kriegshauser) — Tue, 16 Mar 2010 06:08:00 +0000

CRC16::computeMemory( const char* data, unsigned length, uns16 crc = 0 );
CRC16::computeString( const char* data, uns16 crc = 0 );

This little gem caused quite a headache. Allow me to explain.

EQII's streaming client uses 16-bit CRCs to tell if an asset has changed. All 500,000 individual assets have a 16-bit CRC calculated and stored in the master asset list (manifest). When an asset is downloaded, it is cached on disk and stored with the 16-bit CRC. To save time, the client doesn't calculate the CRC on each asset that it downloads, it just uses the CRC stored in the manifest.

Every time the client runs, we download the manifest and check the CRCs in the manifest against the stored CRCs for our cached assets to see if any changed. If an asset has changed (the CRC is different), we delete the cached copy and request the replacement, even if it's not immediately needed.

When the streaming client launched, everything worked as planned. It worked great! Little did we know that a particularly evil bug was lurking.

I discovered a problem when I wrote a utility to convert old PAK files (the game data shipped on the DVD) to cached streaming assets. NOTHING matched the CRCs in the manifest. Every asset was wrong. I looked over the code several times and everything looked fine. This bug didn't make sense.

And then it hit me.

The code that was building the manifests was doing this:

uns16 crc = CRC16::computeString( data, dataLength );

Talk about /facepalm. The function I meant to call was CRC16::computeMemory(). The function I actually called treated the input like a null-terminated string. This means that the CRC was only calculated up to the first NUL character and the dataLength parameter was actually being treated as a starting CRC value. This was a bug that had to get fixed. Someday, perhaps many years from now, this would be a huge bug that would waste a lot of someone's time to hunt down.

Oh, but the fun doesn't end there. I couldn't just change the function to fix the bug. Doing that would mean that every streaming client user would have to re-download everything that they had already downloaded. Every CRC would change and the naïve client would happily delete everything and start over. To fix this properly would take a highly-synchronized effort to fix and push the manifests while deploying a one-time-only tool that would re-calculate the CRC for all assets that people had already downloaded.

The moral of the story: be careful with default arguments. They can really hurt if misused.

Evolution of a Streaming Client

noreply@blogger.com (Joshua Kriegshauser) — Wed, 10 Feb 2010 03:35:00 +0000

It's funny how many things in the game industry start out as "I wish..."
... I wish we had Guild Halls.
... I wish we had Shader 3.0 support.
... I wish we had Battlegrounds.

... I wish our game was easier to download.

It's equally funny how many things are started by people in their own time just trying to make the game better. That's how EverQuest II's streaming client started out.

Taking an existing game (with 12GB of client assets no less) and streaming it is no simple task. I started off with a "proof of concept" just to prove that it could be done with EverQuest II. As I got into it, the concept became a full fledged project. It wasn't officially on the schedule, so it was really a labor of love on my part. After a few weeks of silently working on it, I called the producer into my office and said, "Hey, check this out." Needless to say he was pretty surprised.

There are three major conversion steps for a streaming system.

Serving the assets

EverQuest II has roughly 500,000 client-side asset files: meshes, textures, collision meshes, shaders, data files, sounds, music, you name it. Have you ever tried putting half-a-million tiny files in a directory? Take my word for it: Don't.

My first inclination was to build a custom server. The server would run off of the PAK files that we already ship with the DVD-based game client. I had grandiose plans about how to track files that clients were downloading and automatically send assets to clients that they didn't know they needed.

But alas, it was not to be. A custom server means that every client would have to be talking to our server. We would have to think about where to place the server geographically, handling varying load characteristics, availability, bandwidth, etc. These were all questions that had already been answered; we didn't need to ask them again and try to come up with our own answers.

What else is great at serving files to a large number of clients all over the world? Web servers! Specifically, HTTP servers. We already used a CDN for patching purposes--we just needed to serve all the game assets individually and on-demand now.

This caused another wrinkle. The client needs to know a list of all the assets that are available and whether the assets that it has previously downloaded are out of date. We call this the "manifest." This manifest must be fully up-to-date before the client tries to load ANY assets. My custom server knew how to negotiate a manifest with the client in a fairly bandwidth-friendly way because it was smart. CDNs are less smart--they just serve files. EQII's manifest is about 6MB, which you definitely don't want to download every time you run the game. The solution I developed involves parts of the manifest available as separate files and an overarching CRC file that is requested first. The CRC file is always requested, but it's only about 8KB. Based on comparisons with the CRC file, the client reconstructs the full manifest by grabbing parts that it needs.

Requesting the assets

Compared to everything else, serving the assets is the "easy" part. Requesting the assets is far more difficult. You're essentially replacing file system access with a network connection. That sounds a lot easier than it is. File system access is inherently goverened by the Operating System and allows any thread to open nearly any file and read data from it. A network connection is a single pipe (or in our case, a collection of pipes) that must well-defined and tightly-controlled access. Any thread that could just expect to read from a file at any point must now be synchronized with other threads requesting assets from a network resource.

Another major difference is that file system access is synchronous from an application's perspective. This means that while waiting for the Operating System to read data from a file, the thread goes to sleep and allows the system to do other things. Generally this happens so quickly that you barely notice, but network connections aren't nearly as fast as your local hard disk. For this reason, we want most of our asset requests to be asynchronous: we send the asset request and go about doing other things until it finishes at some later time.

Unfortunately, it's much easier to do synchronous reads than asynchronous. The EverQuest II client had many synchronous reads that you didn't even notice because the file system is fast enough. If they weren't made asynchronous, a streaming client would appear to 'lock up' while waiting for an asset to be fetched. Obviously, this is undesirable, and nearly unavoidable in some cases.

Furthermore, network connections in games are usually given time by the main thread to do their work (colloquially referred to as "pumping"). That won't work in this system. What if the main thread needs to synchronously load an asset (which still happens occasionally, especially on client startup)? It would be waiting for an asset to finish loading and wouldn't be able to update the network connection that it is effectively waiting on.

Clearly, a system is needed that can pump itself. Any thread can request an asset synchronously or asynchronously and the network connection continues updating as long as the client is running. The system should be able to determine if a request for an asset has already been sent and we don't need to waste bandwidth by requesting it again. The system should be able to recognize and quickly send higher priority requests. And, oh yes, let's not forget about failure cases. This piece of technology is the very heart of the streaming client.

Storing the assets

Obviously, once an asset has been downloaded, we don't want to waste bandwidth downloading that asset again. It might take minutes to enter a zone for the first time, but we don't want to take that long every time we enter that zone. Therefore, that asset must be stored locally.

A possibility is to store each asset as its own file, but this fails in practice. Operating Systems are not optimized for hundreds of thousands of tiny files. No, these files must be stored in a larger file, packed together and easily accessible.

EQII already has a packed file format. Unfortunately, the way it's set up does not lend itself to modification. When EQII's packed files are written, they're never intended to change. With new assets being downloaded constantly, these files will be changing, and often.

My solution was to develop a new type of asset database specifically suited to our needs. These database files can store a large number of tiny assets, rapidly add and remove assets and quickly retrieve individual assets.

Other Considerations

The most difficult part of building a streaming system for an existing client has been trying to change synchronous asset requests into asynchronous. Consider the following simple example:

Animation* pAnim = pAssetSystem->LoadAnimation( "animation/player_anim1" );
if ( pAnim )
{
    // Do something with loaded asset
}

The above example would need to fetch player_anim1 synchronously. Changing this to be asynchronous might look like the following example:

Asset<Animation> anim( &myAnimLoadHandler );
pAssetSystem->StartLoad( &anim, "animation/player_anim1" );
...

void AnimLoadHandler::OnLoaded( Asset<Animation>& a )
{
    // Do something with loaded asset
}

There's much complexity missing from the second example, but the point should be clear: making something asynchronous is much more difficult than making something synchronous.

Conclusion

Working on the streaming client was one of the most fun projects that I've ever worked on in a technical sense. It was challenging, but the results are a huge payoff.

Dr. Laura: Dr Jekyll and Mr. Video Gamer

noreply@blogger.com (Joshua Kriegshauser) — Wed, 11 Nov 2009 19:54:00 +0000

Dr. Laura has a video blog about a man who plays video games for his down time:

Now, I actually enjoy reading most Dr. Laura articles. Her common-sense approach to most family psychology issues provides both entertainment and self-reflection.

However, sometimes she's just a little too old-fashioned for me. She seems to come off in this video as entirely anti-video-game. I'll grant that the guy mentioned in the video is acting like a complete idiot, but not all video games are bad. Consoles like the Wii consistently encourage family gameplay.

Maybe it's just because I'm in the video game industry, but if a guy wants to play video games for his downtime, that seems fine. Of course, you have to look at your priorities. Personally, family comes first. Always. I will usually sit down to play games after the rest of my family has turned in for the night. If the rest of the family is napping, occasionally my son and I will enjoy LEGO Star Wars or some other innocuous game.

Everything in moderation, but please don't demonize all video games because some idiot guy can't put down the controller and spend time with his family.

Keep Designer Data in Files (not Databases)

noreply@blogger.com (Joshua Kriegshauser) — Sat, 24 Oct 2009 17:26:00 +0000

Whoa! Did I just fall off the deep end?! Designer Data in ... files?! Data... doesn't that belong in a database?! There are those who say that it does, but I disagree, at least when talking about development.

In MMO terms, Designer Data is data that our Design team creates: Quests, Spells, NPCs, Paths, Items, Recipes, Locations, etc. Tons and tons of data that, together with art, is really the lifeblood of the game.

Designer Data is to Designers as Source Code is to Programmers. It's constantly changing and growing. Different people own different parts of it. Everyone on the dev team needs all of it and as up-to-date as possible to do their current tasks. Servers need it in a highly-optimized form to run the game. There are many parallels between Designer Data and Source Code.

Which brings me to my first major point. As files, Designer Data can be stored in Source Control (we use Perforce, and I love it). This gives an amazing amount of incredibly important functionality and basically for free:

Revision history - As text (EQII uses XML) files, anyone on the team can go back and see (through the same tool that everyone must use) all previous changes to a file. Anyone can see exactly what changed between each version or between multiple versions and who made the changes. Also, you can go back in time and grab previous file revisions.
Changelists - Most source control systems group together file changes. Perforce calls these Changelists. Grouping files together is an effective tool for seeing relative changes based on concept. One changelist might be labeled "Zone 1 population" and contain NPCs, Quests that those NPCs give out, Paths that those NPCs follow, etc. If a Changelist breaks the game, it can be rolled back wholesale (and you can see who made it and go pound them).
Integration - Changes are made in branches and we have branches for each distribution of the game. As a group of changes become ready to go Live, they are integrated into the next distribution (Main goes to QA, QA goes to Staged, Staged goes to Live). With Code and Data both in the same system, integration to the next distribution becomes a one-step process.
Code/Design in sync - Since Source Code and Design Data are both stored in the same system, they are always in sync. If a Programmer makes changes that affect both (which often happens), he can rest assured that everyone will easily get the latest in both.
Sandboxing - Designers are only affecting their own local version of design data until they check it in. They can do testing and make tweaks before checking in something that could potentially break everyone else.
Blame - It's so easy to see who made a change (and confront them if necessary).

If you were doing Design development in a database, you would have to develop your own solution around each of these (or use database tools that not everyone would have access to). And since the database is always up-to-date, and everyone is generally working out of the same database, problems could arise from changing formats or unexpected data.

Furthermore, Designer Data in files are free to have complex formats. For instance, in EQII the Designer Data is object oriented. Data definitions specify that a Character inherits from Entity and Entity inherits from a Base type. This also allows us to do things like have a base Predicate type and more complicated types like CharacterHasQuestPredicate that inherits from Predicate but has additional data members that only make sense for CharacterHasQuestPredicate (like the Quest name). In a database, you might have a Predicate table with a type column that is a number. You would have to look up what that number means from somewhere or write special tools that understand the relationship. Additionally, that Predicate table would have to include all of the options that any types could have in a very generic fashion. So you might have columns called "StringParam1" and "NumParam1". In the database then, you might have a row with type set to 12 and StringParam1 set to a quest name (or more likely NumParam1 set to a unique ID for a particular Quest). If you were looking at raw data, what would you rather see:

<object name="CharacterHasQuestPredicate">
  <string field="sQuest">quests/heritage/dwarven_work_boots</string>
</object>

Or:

Type     IntParam1    IntParam2
12       1243         <null>

The EQII Designer Data tool is very generic as it knows how to read the game's data definition. To actually add a whole new data type (Achievement for instance) actually takes zero changes to the Designer Data tool. It just takes writing a small text file that describes the Data Definition such as this one for our aforementioned CharacterHasQuestPredicate:

<objectdef name="CharacterHasQuestPredicate" inherits="Predicate">
  <fields>
    <fielddef name="sQuest" type="String" require_dir="quests/" default="" />
  </fields>
</objectdef>

However, reading XML files isn't the fastest thing to do. Server startup is fairly slow when reading from XML files, but EQII has a utility that converts the myriad XML files into a single file that contains all of the data in a highly optimized binary format (I've actually written about this file before). This file is mapped into virtual memory allowing all server processes running on the same physical machine to share one copy of the file in memory. For development purposes, developers can run their own servers against the XML data (and both internal development servers and rapidly changed external servers such as a Beta server could run against XML as well for fast turn around). Plus, there are enough options for converting XML data to databases that you could still use XML files for development and run production servers against a database.

The only major shortcoming of keeping Designer Data in files as opposed to a database is for searching and updating large amounts of data--things that a database is designed to do.

For searching data, EQII actually has a very workable solution. The EQII team has developed a system called VooDLe (a name playing off of Google and VDL--the internal name for EQII's data library). This is a very simple web solution that syncs to the latest data and indexes it for searching. It also detects file references and generates links. However, it doesn't help if you'd want to find all of the shields that have a block value higher than 300. For this, you can search VooDLe for the field that declares shield block value and quickly scan through the results. (Rarely is searching for a numeric value so cut and dried in EQII though with level scalars and combat scalars that affect everything.)

Updating large amounts of data is actually something that (shouldn't) happen very often. Furthermore, updating large amounts of data is error-prone and should be limited. You might even call this an inherent benefit to having designer data in files. When this is necessary, it's possible with a simple Perl script. If something does go wrong (even later) the Changelist can easily be reverted.

Based on all this, I feel it's more beneficial to a development team to use files for Designer Data during development rather than a database.

EverQuesting

noreply@blogger.com (Joshua Kriegshauser) — Tue, 25 Aug 2009 07:33:00 +0000

It has been a busy time for me. For the past few weeks I've been splitting my time at SOE between three different game projects.

Two of them are new projects that I can't talk about yet. I'm very excited about both of them (and ~~think~~ know you will be too!) and look forward to being able to talk more freely about them. One was a temporary post while waiting for the second to ramp up. Now that it has I will be transitioning to it full time.

The third is the project that I've been working on for over four years: EverQuest II. However, with the new project my involvement on EverQuest II is shrinking. My official title has moved away from Technical Director on EverQuest II to being the Technical Director on one of the new projects. Don't worry though: the EverQuest II programming team is in the hands of the very capable Greg "Rothgar" Spence. Plus I fully expect to be available to the EverQuest II team for questions and technical direction for a while to come.

I'm currently finishing up my last task with EverQuest II. This last hurrah is designed to do something very important--increase exposure to EverQuest II. I've been personally involved with nearly every change to EQII's trial program over the past four years, but this is the one I'm the most excited about.

EverQuest II is a very large game. Overwhelming content from the get-go followed by five (Soon™ to be six) expansions have conspired to create a client footprint of about 10GB. Yikes! That takes hours upon hours to download even on pretty fast connections. As my last task, I'm working on reducing the initial download down to about 60MB (which is barely a blip with broadband) and streaming the rest as the client needs it.

A few things make this possible. First, the fetching technology that we're using was first pioneered by the incredible talent on the Free Realms team. This made it much faster for us to get on-demand fetching up and running since they had already done the legwork and experimentation. Second, the fetches are nothing more than HTTP GETs which allows us to distribute all of EverQuest II's 500,000+ individual assets over a very fast CDN. Using a CDN means that we don't have to develop, test, distribute and manage our own file serving solution which obviously would take more time. Third, EverQuest II already has a fairly robust asynchronous resource-loading system that was fairly easy to extend with remote file fetching.

Getting asset fetching in place was really only the beginning of the story. My time since then has been focused on heuristics for prefetching the next assets the client will need and reducing some dependencies on synchronous IO (which would appear to "lock up" the client until the needed assets were fetched). These challenges are far more complicated, but the challenge is welcome!

It's been a great four+ years on EverQuest II, and I look forward to getting people playing after downloading a mere 60MB.

Interview of Yours Truly

noreply@blogger.com (Joshua Kriegshauser) — Mon, 13 Apr 2009 23:25:00 +0000

I was recently interviewed (a month ago, heh) on SOE Podcast #58. The interview starts at about 1:19:44. Whew, long podcast!

SOE does a podcast about every two weeks and feature interviews, goofy ads and exciting news about current and upcoming SOE games. You can also follow SOE_Podcast on Twitter for news and notification.

Lost in Translation

noreply@blogger.com (Joshua Kriegshauser) — Thu, 09 Apr 2009 06:51:00 +0000

EverQuest II currently runs in five languages: English, German, French, Japanese and Russian. However, all of the programmers and designers actually build the game in English. To accomplish the translation, we use a proprietary SOE library: the Text Translation and Templating Tool, or T4 for short. T4 is a very powerful tool that allows us to do translation through anything from dictionary lookups to macro expansion. Our Internationalization department (i18n for short) is responsible for maintaining the T4 library and the various language modules for it.

Unfortunately, sometimes we write things in a way that isn't easily language-agnostic. Take the following example for instance:

"Rothgar's Touch of Pestilence critically double attacks Autenil for 38 disease damage."

It's a common bit of text that appears in the combat chat when you're fighting in EverQuest II.

Let's break it down a bit.

First of all, there's the actor performing the action. This can be you or someone else; Rothgar in this example. There's also the target which can be you or someone else; Autenil in this example. There's an optional spell name (Touch of Pestilence) and how much of which kind of damage. Oh, and the action -- double attack in this case -- and actions may or may not be critical.

With the way T4 works with insertion macros, we use a base string like this:
"^1 $2 critically $3 $4 for +5 $6 damage"

But this really doesn't work, at least not for anything but English. That pesky verb needs context in other languages to be conjugated properly. We currently put in either "double attack" or "double attacks" based on who the source and target actors are. It works fine in English but comes out in other languages like gibberish.

The way to fix this is to build base strings that include the verbs, but this can explode quickly. Say there are five different verbs that could be used in that case. To make base strings that include the verbs with all of the other possibilities you end up with about 640 strings, and that's assuming that there is only one damage type (EQII allows multiple per attack).

In the end, I went with using a generic verb for non-English languages ("hit") and put special attacks or critical status parenthetically on the end:
Rothgar's Touch of Pestilence hits Autenil for 38 disease damage. (critical double attack)

This will be much easier on our translators and will make sense for our players. It's been a long time coming.

LOGIN 2009

noreply@blogger.com (Joshua Kriegshauser) — Thu, 12 Feb 2009 21:42:00 +0000

I'm going to be speaking at the LOGIN 2009 conference in Seattle this year:

Unfortunately, client crashes are bound to occur during the course of a live game. While prevention is definitely preferable, how quickly they are detected and resolved helps to form a positive opinion of the development team in the players’ minds. This session is a technical discussion surrounding generation, retrieval and processing of client crash logging. Though many concepts presented are fairly generic and may apply to other platforms and languages, examples will be given in C++ on the Windows platform.

Additionally, one of my programmers is also speaking:

This lecture will be a technical discussion about the Bayesian spam filtering solution used by various SOE MMOs to block over half a million spams per day per game. The lecture will discuss SOE spam filter implementation including what can be done beyond pure Bayesian filtering to help MMOs increase their filters accuracy and reduce feedback to the spammers. We will cover the general theory behind the filter, as well as the mathematical theory behind it and real-world examples of how it is working today.

Be sure to stop by and visit our lectures if you're going to LOGIN 2009 this year!

Meme'd

noreply@blogger.com (Joshua Kriegshauser) — Sat, 31 Jan 2009 09:23:00 +0000

Several people have tagged me with the "25 things" meme, so I figured I'd satisfy the adoring masses:

I’m a science fiction geek. My favorite Star Trek series is The Next Generation and I’ve seen every episode at least twice. I also like Star Wars and Return of the Jedi is finishing up on my TV as I write this. I’ve even gone as far as to draw up deck plans for starships… Snow Crash by Neal Stephenson is one of my favorite books.
My favorite genre of music is Country, much to the chagrin of my family and my co-workers. I do also like Classic Rock and some Oldies, so I can usually find something mutually pleasing to the people around me.
Tests show that I’m allergic to peanuts, but I’ve never had a problem eating them. My kids, however...
My family is very involved politically, and I have some strong political convictions, though I’m not very vocal about them... usually.
I would play Rock Band until my arms fell off if I was ever uninterrupted for a long enough period. I never am though (darnit).
I used to play first-chair alto saxophone in the high school band… while in elementary school. I’ve done solos and performances. I still have my sax and could probably play it, but not very well anymore.
I’ve driven 157mph. In a car. On the road. In real life.
I’ve lived completely on my own since I was 19, except for a few months living with an aunt and uncle while looking for a place after moving to CO.
I’ve slept in the bottom of the Grand Canyon and on 14,000 ft mountain peaks in Colorado.
I almost never dream while sleeping.
Unlike my dad, mom and brother, I don't wear glasses or contacts. My vision is 20/15.
I started programming computers in BASIC in the third or fourth grade. I got my first C compiler before graduating elementary school. I would design simple games with my brother and then write them. One early Christmas I painstakingly programmed several Christmas carols to play over the 3-voice music synthesizer on a TI-99/4a. My whole extended family was present for the concert.
I love cycling and enjoy commuting to work by bicycle when I have the time.
A friend and I nearly died climbing down cliffs while lost in the Gila Wilderness of New Mexico. My Ham Radio was useless in the mountains. We had to abandon our equipment and wade through a torrent of snow melt runoff. After finding our way to a highway, we had to hitchhike for 17 miles to get back to my car, which had a flat tire.
I’ve worked at McDonalds, CompUSA, an indoor minigolf place, and as a self-employed consultant.
My dad, mom, sister and brother all have a college or trade degree. I don’t, though not for lack of trying. I just kept getting hired away from school...
I’ve been to Mexico several times and Canada, but I’d really love to see parts of every other continent.
I’ve been skydiving and loved it. If I were independently wealthy and didn’t have kids, I’d make a hobby out of it.
My love of electronics goes hand-in-hand with my love of computers. In elementary school, I walked around with a 40-pin IC in my pocket. I etched my own circuit boards and built an adjustable power supply in junior high. I built a turbo timer and air/fuel ratio indicator for my Supra. I was the only kid I knew with an o-scope.
I’ve logged a few hours towards my private pilot’s license. I’d love to complete it despite the impracticality.
My faith in Jesus Christ has affected nearly every part of my life in some way.
When I proposed to my (now) wife, I arrived 3 hours before I was supposed to, snuck up behind her and surprised her while holding the open ring box. When she whirled around she knocked the ring out of my hand. I had to crawl around on the floor for a few minutes to find it. We’ve been married eight years as I write this.
I had lunch with Curt Schilling of the Boston Red Sox when he was interested in having me join the team at his game studio, 38 Studios. Good guy, but I respectfully declined.
I have a pencil stab wound in my hand that is still visible after 15 years.
I collect Ultimate Collector Series LEGOs. The models in my office at work total over 15,000 bricks alone.

UOForums Interview

noreply@blogger.com (Joshua Kriegshauser) — Mon, 12 Jan 2009 19:18:00 +0000

UOForums asked me for an interview a while back. I finally obliged:

What has been your most memorable accomplishment in your career?

Making Technical Director before 30? :) Getting hired by Origin is probably the most memorable accomplishment as it was my first gig in the game industry. It was an amazing experience: I got to meet and work with the people behind the names on the forum that I idolized. The whole experience was surreal.

Tsk, tsk, Microsoft

noreply@blogger.com (Joshua Kriegshauser) — Fri, 02 Jan 2009 03:06:00 +0000

This is awesome.

Thousands of Zune portable media players made by Microsoft Corp. suddenly froze up early Wednesday, Dec. 31, labeling Internet wits to label the phenomenon "Z2K."

It goes without saying that I'm quite happy with my iPod Touch and iPhone, neither of which locked up at 12:01am yesterday.

Good-Bye T-Mobile (and Good Riddance)

noreply@blogger.com (Joshua Kriegshauser) — Mon, 22 Dec 2008 07:47:00 +0000

I just received a $446 bill from T-Mobile. To say that I'm disenchanted with T-Mobile would be an understatement.

I suppose I should rewind a little bit. I was a T-Mobile customer for over five years. Back in 2003 I signed up with T-Mobile because I was moving to Austin, TX to work for the now-defunct Origin Systems and they had the best plan for me at the time. My wife and I mostly use our cell phones to call each other, so the cheapest no-frills family plan usually suffices for me.

Fast forward to 11/27/2006. I was sick of using the bottom-of-the-barrel free no-camera monochrome Nokia phone that I got for free when signing up in 2003. My original two-year contract had long since expired. Verizon was offering the inexplicably popular RAZR phone for some ridiculously low price. However, having been a loyal T-Mobile customer for over three years, I decided that I'd give them the chance to beat Verizon's deal and compete for my business. The "Customer Loyalty" representative that I talked to jumped at the opportunity. Not only did they give me better RAZRs than Verizon was offering at the same price (and the same two-year committment), he also changed my phone numbers and gave me some text messages for free, waived all of the upgrade fees AND put me on an "unlisted" family plan that was slightly cheaper. Wow! That's customer service!

And then followed four months of hell.

They sent me the wrong phones. They charged me full price. They wouldn't reimburse me to ship them back. Every representative that I talked to showed a new previously-unheard-of level of incompetence and screwed something else up, making it all the more difficult to explain my plight to the next representative. Untold hours on the phone forever lost arguing with people, explaining my situation and fighting to get my bill fixed and figured out. Pages and pages of notes with a myriad of representatives' and supervisors' names weaving a trail of regret and resentment. For four months.

Had it not been for that damned two-year contract I would've flushed them right then and there, but eventually the dust settled and things were worked out.

Two years later, my contract was nearing its end, though I didn't know the exact date it was up. I once again figured that I'd give T-Mobile every opportunity to keep my business. I went into their stores looking at various Blackberrys and the G1. I was interested in a phone that would give me access to my corporate email and the Internet. I was asking for a little bit better price on the phone and the plan. They wouldn't budge. I called "Customer Loyalty" again and they were resilient against my requests. I told them that I really wanted the iPhone and was willing to go to AT&T unless T-Mobile would give me a better deal but instead got stuck talking to some blatherskite who insisted on hammering me on the irrelevant topic that the iPhone was available through T-Mobile--in Germany. I feel that I gave T-Mobile every opportunity to keep my business. Suffice to say, now I'm with AT&T and proud to walk around with my Apple iPhone (I have an iPod Touch too, but adding a phone to it is just brilliant).

Now, about this $446 bill. You'll notice that I upgraded (and started a new two-year contract) on 11/27/2006. I switched to AT&T on 11/23/2008. Four days away from two years and T-Mobile slaps me with two $200 early terminations fees--one for each of my two lines. Four days! At the very least paying the whole amount for my last month would fulfill my obligation to the two-year contract.

Needless to say, I immediately got T-Mobile customer service on the phone. Despite the lividity coursing through my veins I managed to remain level-headed. The "Customer Loyalty" representative offered to cut the $200 per-line fee down to $50 per-line. "That is unacceptable," was my reply. Her next response was cut short as I quipped, "I'll need to speak to your supervisor." The merry Christmas tunes that filled my ear while I was waiting filled me with a sense of irony. Finally the woman came back and told me that her supervisor was busy on another call but she could finagle it so that I'd just finish paying for the full final month, dropping $384 from my bill and returning sanity to the evening. Another 30 minutes of my life wasted on the phone with T-Mobile to combat utter, inane stupidity.

To T-Mobile, if you happen to be listening:

Either allow "customer loyalty" more authority to please customers (especially on plan prices) or lose them.
Pro-rate the early termination fee or at the very least, change your system so customers who are within the billing cycle of their end-of-contract just pay out the rest of their month to fulfill their obligations.
Recognize the Charlie Foxtrot cases and assign a single person be your customer's advocate and to sort the problem out. Dealing with one competent person who understood my problem after upgrading in 2006 would've been very nice, but alas, it was not so.
You can do better than the G1. It doesn't even natively support Microsoft Exchange email.

To everyone else, I'd have to recommend against T-Mobile. By all means, use a different cell phone provider. If you're with T-Mobile now, get out as soon as you can. If you're not big on data, you can probably save a bundle by buying individual minutes and not having a plan.

Memory-Mapping Files for Fun and Profit

noreply@blogger.com (Joshua Kriegshauser) — Sat, 20 Dec 2008 06:33:00 +0000

It's amazing that I still meet programmers who don't understand the benefits of memory-mapping files. If you're unaware of what that means, let me explain it a little bit. Traditional reading from a file involves several system calls: opening the file, seeking to the desired position and then reading or writing to the file. System calls can be slow as the operating system may have to switch to kernel mode and call into drivers to perform the IO operations. Memory-mapping a file usually has just one call, and then you are able to access the file as if the entire file had been read into a contiguous block of memory. But here is the greatest benefit (at least to me as a MMO server programmer): all processes accessing a file can use the same virtual memory.

Take the EverQuest II server for instance. The (binary) data file that describes nearly everything except collision geometry runs about 460MB. Every zone server uses that same file and we run several zone servers on one physical machine. With memory-mapping, the OS uses 460MB of virtual memory (assuming the entire file is used) just once and all zone server instances can use that same virtual memory without having to read the file into each individual instance.

Like anything, there are drawbacks. Most modern operating systems use demand paging, so if you try and access a page of memory representing a part of the file that hasn't loaded yet, a page fault will be triggered and the OS will have to perform kernel-mode IO to load that page from the file. Depending on how much virtual memory your application has access to (and how spread out your accesses are), this could potentially trigger a very high number of page faults.

Another drawback is address space. A 32-bit application will only have access to less than 4GB of address space (Windows has a 2GB address space by default). If you map entire large files into memory, you are consuming this address space. This has become more and more important on the EQII servers. As I mentioned, our data file is 460MB. Since shortly after the game launched, this file has always been fully mapped into memory. That was fine back then as it was much smaller than it is today. Now, after launching our fifth expansion, the data file is now nearly one quarter of our allotted address space (and not getting any smaller).

Fortunately, the APIs for Linux (mmap) and Windows (MapViewOfFile) allow an offset and a length to be specified. This opens the door to partial memory-mapped files. However, there are some caveats. The offset cannot be just any offset; it must be aligned. On Linux the offset must be a multiple of the page size (found by getpagesize), but on Windows the offset must be a multiple of the "allocation granularity" (found by calling GetSystemInfo). The length of the mapping usually does not need to be aligned, but if you're planning a generic partial mapping solution, it's probably best to use the same alignment. Another thing to consider is that mapping parts of files as you need them will spread them all over your address space; you cannot assume that page 1 and page 2 of a file will be placed next to each other in memory if you map them separately.

Here are some of the design goals for my partial memory-mapping implementation:

Phase sections out as they are no longer used (start-up data is only needed at start-up)
Reduce thrashing (phasing out a section and then mapping it back in)
Similar performance to the current full-file implementation
Reduce memory usage!
Ability to permanently map/unmap sections (i.e. sections that don't phase out)
Ability to automatically re-size sections on demand

Allow me to touch a bit on that last point. For my interface, given an offset and a length, I wanted to return a pointer to contiguous data rather than copy data into a provided buffer. Say some previous access forced you to load page 10 (but not page 11) and now you want to read some data that spans pages 10 and 11. This presents a problem for the contiguous data interface. I can't just map in page 11 and hope that it ends up next to page 10 (I will point out that there are 'hints' that can be passed to the OS APIs to attempt address space positioning, but these are discouraged). Do you leave page 10 mapped and create a new mapping that combines pages 10 and 11? Since my interface always required an offset and a length for every access, I could safely unmap the existing page 10 and map pages 10 and 11 together. Data requests for data on page 10 would now refer to the joint mapping. However, this did greatly expand the number of test cases I needed and complicated the logic.

This nifty little piece of technology is currently running on our live game servers and doing very well. Instead of 460MB, we now keep a pool of about 20-30MB mapped from the file and generally enjoy a 0.1% or lower miss rate. Best of all, we still have all the benefits of memory-mapped files.

(Country) Rock Band!

noreply@blogger.com (Joshua Kriegshauser) — Tue, 09 Dec 2008 22:26:00 +0000

Oh my gosh:

Consisting of five tracks, it'll be out on December 18, and will feature tracks by Brad Paisley, Brooks & Dunn, Dierks Bentley, Miranda Lambert and the Dixie Chicks. Pricing is fairly standard, at $2/160MS for a song or $8.50/680MS for all five.

As I've stated before, I love Country Music. Maybe I'll play hooky on December 18th.

Ok, I probably won't, but I'm still excited. Harmonix, if you're listening: MOAR PLZ! KTHXBYE

/resurrect Xbox-360

noreply@blogger.com (Joshua Kriegshauser) — Mon, 01 Dec 2008 07:42:00 +0000

I sat down on Saturday to enjoy some Lego Star Wars with my son, but discovered a different feeling welling up inside me instead: dread. My Xbox-360 had fallen victim to every Xbox owner's nightmare--The Red Rings of Death.

He opted to play Super Mario Galaxy on the much more reliable Wii instead, while I googled everything I could about the RROD.

It's interesting to note that Microsoft extended the warranty on the 360 to 3 years. However, I purchased my xbox used from a friend and don't have the receipt from the original purchase. Additionally, the date of manufacture shows as 11/03/2005, so warranty repair seemed like a non-option to me. Plus, I've had friends send their xbox in for warranty repair and it's taken them over a month to get them back. I'm impatient when it comes to gaming! But if you are reading this and have a xbox that is still under warranty, please consider the options carefully before breaking that silver warranty sticker! There is no going back!

I found a guide that provided an at-home remedy for repairing the RROD. A good theory about what causes the RROD is a design flaw leading to flexing the motherboard. This warping leads to microscopic breaks in the tiny surface-mount solder connections exacerbated by numerous heat cycles. The guide directs you to fix the problem by removing the x-shaped brackets holding the heat-sinks to the CPU and GPU and replacing the mounts with screws from any old hardware store.

I thought, "Eh, why not."

So I tore down my xbox:

Getting the heat-sinks off was a pain, but persistence pays off:

The guide I was using didn't tell me this, but you'll also need a 1/4" socket or nut driver to get the posts out of the heat-sinks.

The next step was to clean off the old thermal paste from the chips so that new thermal grease could be applied:

To do this, I used left-over ArctiClean from my last project of this nature. Using the ArctiClean produced a very high-quality mirror shine from the CPU, GPU and heat-sinks:

I staged my bolts according to the guide, put the washers on the motherboard and applied the directed amount of Arctic Silver 5 (about .5 - .75 the size of a grain of rice) to the GPU right before replacing the heat-sink. I then spread the thermal paste out over the chip with the edge of an old plastic gift (credit) card:

The GPU heatsink was then applied, careful to make sure that I had all screws started before allowing the heatsink to contact the surface of the GPU. I very carefully tightened the screws until they were just snug, but evenly snug. Repeat the whole ordeal for the CPU. Here's what the bottom of the motherboard looks like now without the x-brackets:

Note the eight hex cap screws. I recommend using normal phillips machine screws if you can find them. Unfortunately, my local Home Depot didn't. This was all I could find. Originally I had washers on both sides of the motherboard, but the taller hex cap screws had major clearance problems trying to fit back in the metal case. I had to (carefully) remove each screw, remove the washers on the bottom of the motherboard and then replace the screw. I was very glad that I had only snugged the screws earlier.

According to the guide, at this point you should place the motherboard in the case, hook up the necessities and fire it up without the fans to purposely overheat the system and cause the solder to re-melt back into place. However, when I booted it up at this point, there were no more red rings!

Apparently, between the new fastenings for the heatsinks and the better thermal grease on the chips, the problem was fixed! I finished re-assembling the chassis and decided it was time for a real test. I took it back downstairs and hooked it up to the TV, re-inserted the hard disk and memory card and grabbed a controller.

I played Braid for over a half hour with no problems, though I do wonder how permanent this solution will be. If it does break down again, I'll come back and update.

8/9/2010: After 21 months the RROD have returned. I haven't actually pulled the machine apart again to check it out, but it might be worth buying a refurbished base model at this point!

The Shadow Odyssey

noreply@blogger.com (Joshua Kriegshauser) — Thu, 20 Nov 2008 07:01:00 +0000

Well, the launch was a success! As I promised, I tweeted (through my twitter account) the happenings of launch day as they occurred. Here's the full compilation:

11/17 2:19am: Final green-light from QA regarding EQII:TSO is in. Critical mass building... Later today we'll be staging the code to all the servers.
11/17 9:46am: At work on the day before EQII:TSO launches. Feels like i didn't get a weekend. Oh wait, that would be because I didn't. :)
11/17 10:16am: Wow, 15 minute leads meeting. I think that's the fastest it has ever been #shadowodyssey
11/17 2:26pm: Leaving the office now and returning at 3am. Requests to have the Ops dept bring servers down at 12am have been set. cya@3! #shadowodyssey
11/17 6:57pm: I better hop in game and finish the D.I.R.T.Y. Quests before midnight! #shadowodyssey
11/18 3:05am: *yawn* 3am. Servers came down at 12am and back up running TSO at about 12:45am. QA doing smoke tests now (will be a while) #shadowodyssey
11/18 3:09am: i'm patching up now. luckily, I sneakily pre-copied all the expansion assets from the patcher (yay for being internal) #shadowodyssey
11/18 3:28am: Unbeknownst to most, Vivox is using the opportunity of all of EQII being down to do some voice chat maintenance #shadowodyssey
11/18 5:24am: Smoke test on production servers is going great. Vivox maintenance is done. #shadowodyssey
11/18 6:17am: QA still testing strong. Platform QA is testing to make sure that production keys can be consumed properly. Getting closer! #shadowodyssey
11/18 7:29am: Breakfast brought in. QA is still testing strong. Funny to see everyone queued up on the login servers. Getting closer... #shadowodyssey
11/18 [8am]: And We're Live! Devs are on the server (incognito) playtesting and reporting any issues. #shadowodyssey is smooth so far! [twitter was down at 8am]
11/18 10:11am: I (and other EQII team members) are running around Moors of Ykesha on various servers doing quests. Enjoying the expansion! #shadowodyssey
11/18 11:37am: Reports of a few minor issues with the broker. We're looking into them. #shadowodyssey
11/18 1:55pm: Been here 11 hours (and counting). May head to the launch party. Some minor issues with Ykesha, but I made some tweaks #shadowodyssey
11/18 2:40pm: Almost 12 hours here. Heading to the launch party and then home for some Zzzz. /yawn. Great launch so far! #shadowodyssey
11/18 4:59pm: Enjoyed seeing @tenamdar and others at the #shadowodyssey launch party! It was a very smooth launch. Now: sleep!

We really enjoyed working on this expansion! Enjoy!