04 February 2014

Githubbing

I just created a repository on github.

https://github.com/jkriegshauser/fastjson

For a while I've been writing a json parser (fully RFC-4627 compliant) similar in interface to rapidxml as a fun way to write some simple code that ended up being fairly complex. I mean, there's a good bit of template partial specialization in there, exception/non-exception handling, Unicode support, unit-testing, etc.

It even figures out if you've given it UTF-8, UTF-16 or UTF-32 and whether the endianness matches your machine or not.

Yeah, so that's how I have fun. Enjoy, universe!

21 November 2013

Catching Fire

Well, it happened.

Nearly two months ago I took the plunge and left Sony Online Entertainment to be the Director of Technology at Molten Games. Molten is a small but well-funded and growing start-up in the San Diego area.

I. Am. Having. A. Blast.

We're building a rock-star team and making a great game. I can't wait until I can talk about it, but you're going to have to stay tuned for a bit.


08 January 2013

Getting Ripped

For the past few weeks I've been converting my DVD and Blu-ray Disc (BD) collection to MP4 format so everything can be easily viewed on the Apple TV. Generally, this has been fairly painless (especially for DVDs), but there is one thing that I desire that most people probably don't care about: captions.

Maybe I'm getting old, but for about a decade I've preferred to watch shows with captions. There are basically three types of captions present on DVD and BD media:

  1. Closed Captions - text-based captions that may include hard-of-hearing information.
  2. Bitmap Captions - bitmaps that are overlaid on the screen.
  3. Forced Bitmap Captions - technically a subset of (2). Typically shown for foreign languages.
Bitmap Captions allow the DVD/BD publisher to ensure that captions look the same on every player, whereas text-based Closed Captions can look and perform differently on different players, TVs, etc. And in my experience, Bitmap Captions don't display on the Apple TV whereas Closed Captions will. Also of note is that DVD and BD each use a separate type of Bitmap Captions--VobSub for DVD and PGS for BD.

Now, if Bitmap Captions don't show on the Apple TV, why do I care about them? There are two main reasons: 1). If Closed Captions don't exist and 2). Forced Subtitles.

At this point I should mention that I'm using Handbrake to encode my movies for the Apple TV. Several pages exist as guides to using Handbrake, so I'm not going to cover it in much detail, except for dealing with captions.

If Closed Captions Don't Exist

If a DVD has Bitmap Captions (VobSub) but no Closed Caption, then we need to find a way to add text-based Closed Captions. Fortunately, there are a few options.

The first option is my least favorite. Handbrake has the ability to burn-in Bitmap Captions. This means that captions will be present, but there will be no way to turn them off. For all captions, that's not desirable, but as seen below it can be quite handy for Forced Captions.

The second option is to find a SubRipper (SRT) file that someone has created. Fortunately there are some great crowd-sourced resources for this, like Open Subtitles and my personal favorite, SubScene. These sites allow you to search for a SRT file that someone has created and uploaded. Handbrake can import the SRT file by using the Import SRT button (seen in the picture above). The downside to this method is that timing is everything. There can be Special Editions and Director's Cut versions of the movie you're searching for, so ensuring that you have the correct file will involve using Handbrake's Preview feature or using a player (like VLC Media Player) to preview before encoding. Otherwise you could end up with captions that don't match.

The final option is to create your own SRT file from the Bitmap Caption. This can either be done manually (VERY time consuming) or with the aid of OCR software. This was more of a last resort for me, but I did do it for a few of my DVDs. I used a program called Subresync. It is about as naive as OCR software can be, essentially asking the user the first time it encounters a specific pixel pattern:

Forced Captions

This is where things get a bit trickier. Forced captions were typically not a problem for DVDs as all of my DVDs that used Forced Captions actually had them burned in to the video stream. Not so for my BDs. A good example is Star Trek VI: The Undiscovered Country where the Klingon speech is a Forced Caption track and is not burned in to the video stream. And Forced Captions are something that everyone should want as they are essentially part of the movie.

Also complicating this process is the fact that Handbrake does not yet understand PGS-style Bitmap Captions (the system used for BDs). Therefore, the PGS (or 'Sup') Captions must be converted to VobSub before using Handbrake. This involves the following steps:
  1. I use MakeMKV to get the BD data on the hard disk in MKV format.
  2. Load the .mkv file in the mkvmerge tool from MKVToolNix. This will tell you which tracks contain PGS Caption data:

    In this example, IDs 2, 3, 4 and 5 contain PGS subtitle data. Leave this program open as we'll come back to it if we do indeed find Forced Captions.
  3. Extract the subtitle data using mkvextract on the command line:
    mkvextract tracks Star_Trek_VI...mkv 2:sub2.sup 3:sub3.sup 4:sub4.sup 5:sub5.sup
    This will extract tracks 2-5 into files sub2.sup, sub3.sup, sub4.sup and sub5.sup
  4. Open each extracted PGS Subtitle file using BDSup2Sub to see if it contains Forced Captions. In the Star Trek 6 example, we find that track 3 contains nothing but Forced Captions:
  5. Since we've found Forced Captions, we need to convert them to a format that Handbrake understands. Fortunately, this is what BDSup2Sub was designed to do. File->Export gives the following dialog (make sure that 'Export only forced' is checked):

    Interestingly, VobSub is made up of a .idx text file and a .sub binary file.
  6. Now we need to add the newly created VobSub captions and re-mux into a new .mkv file. Go back to the mkvmerge that was open from step 2. Click the Add button and select the new .idx file that was created in step 5, then press Start Muxing:
  7. When the muxing finishes, you can now load the new .mkv file up in Handbrake and burn-in the Forced Captions:

Getting captions to work correctly on the Apple TV with custom-encoded movies can be a bit tricky, but if you're hard-of-hearing or just used to using captions, hopefully this guide can help you.

02 May 2012

New Domain!

Well, I've finally gotten around to registering joshuakriegshauser.com. It's about time. Which means that this blog will appear at blog.joshuakriegshauser.com.

Oddly enough, kriegshauser.com is considered a premium domain and is listed for about $1600. I honestly hope whoever is holding it never gets that.

05 January 2012

1 in 600,000

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:

If you'd like the full C++ source: Go here.

21 July 2011

GDC Online 2011

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

31 March 2011

Philosophy of Code

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.