I'm Coming in With the Flag

I got so excited about my success with modding Sauerbraten and adding XInput support that I decided to add the gamepad code to AssaultCube as well. Because Cube1 and Cube2 engines are similar in many ways, doing so was a breeze (took me a bit to figure that the Y axis is reversed in AssaultCube but other than that it worked great). Since my last post I also made some enhancements to the controller code, such as the ability to bind buttons and triggers to arbitrary script code. Actions can now be bound to the analog trigger half-presses which is extremely useful for engaging the aim-assist code. Yeah, I wrote my own aim-assist to compensate for the game controller's lack of precision and maybe it is best I do not elaborate any further on that, the fine line between aim assist and aim bots being a controversial one.

Controller in hand and cold beer in reach, I sat down for a single-player session of AC only to realize that the AI is not as capable as Sauerbraten's and the bots have many limitations. For example they cannot play Capture the Flag (CTF) and cannot navigate the underground sewage system in the ac_aqueous map. It also seemed a little strange that the AC bots use a configuration file with a syntax of its own instead of using the powerful Cubescript language.

I could not pass the challenge and decided to look into writing my own AI code. I have never tackled this kind of stuff before. As a professional programmer I worked with compilers, debuggers and touched databases; I worked for Amazon.com and for Microsoft (yeah, I did write a few thousand lines for Windows 8, guilty as charged). But I have no game development experience, aside of a lame Python implementation of Reversi I wrote a few years back.

Naturally I got very excited about experimenting with an AI system. My goal was to come up with playable, good-enough code that could coexist with the current AI. I did not want to overhaul the entire bot code and disturb other parts of the game that depend on it. I just wanted to add a side-by-side AI, and I must admit the thought of having the two AIs fight each-other while I spectate crossed my evil mind. I aimed for keeping the code small and compact, in the minimalist tradition of the Cube engines.

I decided to use a waypoint system for navigating the maps, similar to what the existing bots use. I am aware that better systems can be devised (http://www.ai-blog.net/archives/000152.html) but I wanted to keep the code very simple. The waypoints are created by a greedy algorithm that tries to span trees to cover the entire map using a collision detection scheme. A second pass ads a few more edges and attempts to connect together unconnected sub-graphs. This work is not spread across several frames so depending on how fast (or slow) the computer is the game may seem to "freeze" for a short moment when it loads the map. I added a variable named wpxautosave which when set causes the waypoints to be written to a file named the same as the map (plus the .wpx extension). This file is automatically loaded if present, so the short "freeze" inconvenience can be alleviated this way. I preferred this over a more complicated code that spreads the work over several frames.

The problem I grappled with for many weekends is that using the game physics for collision detection is not a precise business. Trying to move the player's character on all possible edges in order to validate them is expensive. Cutting some corners (pun well intended) may yield graphs that are incorrect and cause the AI to bump into walls. On the other hand, being too conservative may end up in disconnected graphs. I decided to go with a hybrid approach were waypoints can be generated automatically (with a somewhat conservative take on collisions) but also manually, by running over the map and dropping waypoints in Sauerbraten's style. This way, if I have time to kill I can make my own waypoints (manually and accurately) for a given map, or if I just want instant gratification I let the machine generate them, and more are added as I play. The latter approach has an interesting side-effect. As new waypoints are added, the bots appear as they "learn" new ways around the map. I added a variable (exposed to the user via Cubescript) to limit the growth of the graph, and thus the computational effort required for path finding during game play.

The bots use the Dijkstra algorithm for their path finding instead of A*. I thought this was more convenient in situations where they are not interested in finding their way from point A to a specific point B, but rather to the nearest of any points that satisfy certain criteria (any health pickup, or any Kevlar or helmet, or any ammo pickup, for example).

I wrote the code using Visual Studio 2010 to take advantage of the C++11 features that it supports, such as lambda functions. I guess GCC would've worked just fine but these days I have no compelling reason to boot up Ubuntu, thanks to how badly Gnome 3 managed to disgust me; but that's a story for another day.

Each bot implements a simple state machine in the form of a stack of std::function<void()>. The function at the top of the stack represents the current state; when it is popped off the stack the bot returns to executing its previous state. If the stack is empty, it executes an idle() routine. The stack is populated by the think() routine, which sets a long term goal and optionally some short-term goals, following the wisdom of the Quake Arena AI design. In a Team Death Match game, the long term goal is to seek and engage enemy units. In a CTF game the goal is to locate and retrieve a flag.

Because the collision detection is not perfect and because of using a waypoint system for navigation, the bots may get stuck every once in a while. I added some heuristics to resolve the collisions by jumping, crouching, or rotating around the obstacle which so far seems to work well with solid obstacles but requires more future tweaking for things such as link fences or light posts; overall I am pretty pleased with the result and last night I was able to play CTF on ac_aqueous with the bots chasing me through water underground.

And I could not resist wiring in some sound bytes since they are already present in the game. Your bot team mates will complain when shot at accidentally, or may brag about their kills.

For the curious and courageous that want to play with the code: first, get the latest AssaultCube 1.2 source from http://sourceforge.net/projects/actiongame/. Then get my hacks from my SkyDrive:
http://sdrv.ms/VEU0f0 and http://sdrv.ms/VEU12G and follow the instructions in the comments at the top of the ai.cpp file. Adapting the code so that it builds under Linux is possible but I have not tried it, VisualStudio 2010 is the only environment under which I built the code. You can also grab the Windows binary file from here and overwrite your AssaultCube 1.2 (make sure you get the latest bits from sourceforge, the mod may not work with older versions).

Currently there is not a lot of magic in the bots decision making process. It is by and large driven by their health, armor, ammunition, who they may cross paths with, and plain randomness. I plan to experiment with genetic algorithms once I get a good feel for the quality of the existing code (got a couple of bugs to address before I move on).

There are other interesting features in the relatively small code (around 2600 lines of C++), such as team collaboration. The bots ask for help when attacked or when going for the enemy team's flag. I could go on and on about how much fun I had with this experiment. But I've a game to play!

Hackenbraten: Native XInput Support for Sauerbraten

Although I've been programming professionally for eighteen years I've very little to no experience with video game development and I always wanted to get  my hands dirty messing with a FPS engine. An open source game is a great place to start so I checked out Sauerbraten from http://sauerbraten.sourceforge.net/.

The rain was back in Seattle this past weekend. An excellent excuse to cozy up indoors and hack Sauerbraten.

I must say that I am quite impressed with the no-fuss, minimalistic coding style of the authors and by how well the code reads. I was able to find my way around it fairly quickly. As a professional developer I have seen way too many over-complicated code bases, polluted with "clever" design patterns and unnecessary C++ - isms that nobody under an IQ of 300 understands. Heck, I wrote my own fair share of inscrutable C++ templates. Saurebraten's style is all about self-explanatory short functions that focus on the algorithms. The scripting engine is very efficient and elegant.

Because I type all day for a living when I play videogames I prefer giving the keyboard a rest and  use a controller.

Although Sauerbraten has no native support for gamepads it can be played with controllers that know how to emulate keyboard and mouse events (such as the Logitech F510, which comes with software for customizing it). This is okay, albeit not the best experience you can get.

In particular you miss on the rumble / vibration feedback, and shooting things is all that Sauer is all about. There are other potentially cool things such as analog triggers with configurable threshold. And how about some finesse and control the speed of your movement with the thumbstick (move faster when it is pushed farther out)?

I was curious if I could improve my gaming experience (and maybe learn a thing or two about the Sauerbraten engine in the process). Since I was doing this on Windows 7 and the game engine works on Linux and Mac as well one goal was to make a minimal impact on the overall portability.

I ended up with a "hybrid" implementation, in the sense that for some gamepad actions I directly interact with the engine (for moving the player I mess with the move, strafe, and velocity data) and for  others (such as mouse motion) I just push SDL_Events into the event queue.

Overall I am pretty pleased with the result. At the high level, the "mod" I came up with consists of:

• a change to weapons.cpp so that custom actions can be performed upon firing a gun;
• one C++ file for the gamepad module proper;
• two function declarations (the "entry points" into the module), one for polling the controller state and the other for writing back the bindings to the config file when the game exits, and
• changes to main.cpp and console.cpp to call the functions above.

The first item on the list is orthogonal to the rest of the gamepad code and it could be useful in its own right for example to play the sound of an empty cartridge hitting the floor.

The gamepad can be turned on or off with the gamepadon variable, and gamepadbind allows for extra tweaking. One kludge that I am not particularly proud of is that gamepad buttons cannot be bound directly to cubescript, instead they have to be bound to a key, like in this example:

sound_drop = ( registersound "cristiv/dropcartridge" )
bind F8 [ sound $sound_drop ]
gamepadbind right_trigger_release F8

it would be nicer to  simply say:

gamepadbind right_trigger_release [ sound $sound_drop ]

But this is an exercise for another rainy day. By the way, it is so cool being able to map separate actions to analog trigger presses and releases. For example, in my implementation the default mapping of the left trigger is to zoom in when pressed, and zoom out when released. One idea I'd like to try out some day is to make my player character start jumping when the left trigger is pressed, and stop when it is released.

I am right handed. My default bindings are to control movement with the left thumbstick or D-pad, look around with the right stick, and shoot with the right analog and digital triggers. This scheme can be easily reversed by using the gamepadbind command to remap the triggers and thumbsticks.

One thing I did before proceeding with implementing the gamepad input code, was to add some triggers for the guns, so that I can call custom cubescript when the weapons are fired. In weapons.cpp I added this block (right before the shoteffects function):

    VAR(gun_trigger_debug, 0, 0, 1);

    static void doguntrigger(const fpsent* d, int gun)
    {
        defformatstring(aliasname)("gun_fired_%d", gun);
        if(gun_trigger_debug) conoutf(CON_DEBUG, "%s:%s", name, aliasname);
        if(identexists(aliasname)) execute(aliasname);
    }

And then I added a line at the end of the shoteffects function:

    if (d==player1) doguntrigger(d, gun);

The gamepad code exposes a function called vibrate to cubescript which takes three parameters: the speed for left vibrate motor, speed for right motor, and the duration in milliseconds. The above plumbing allows for  it to be called from my configuration script:

// guns feedback
gun_fired_0 = [ vibrate 20000 20000 500 ]
gun_fired_1 = [ vibrate 5000 35000 200 ]
gun_fired_2 = [ vibrate 10000 25000 300 ]
gun_fired_3 = [ vibrate 32000 64000 360 ]
gun_fired_4 = [ vibrate 0 30000 200 ]
gun_fired_5 = [ vibrate 0 25000 200 ]
gun_fired_6 = [ vibrate 0 25000 200 ]
gun_fired_7 = [ vibrate 2000 10000 200 ]

The next thing to do was to add two function declarations to engine.h (towards the end of the file, right before the closing #endif):

namespace gamepad
{
#if _WIN32
    extern void checkinput(dynent*);
    extern void writebinds(stream*);
#else
    inline void checkinput(dynent*) {}
    inline void writebinds(stream*) {}
#endif
}

These two entry points are called right at the beginning of checkinputs (in main.cpp), and at the end of writebinds (in console.cpp), respectively:

void checkinput()
{
    gamepad::checkinput(player);

    SDL_Event event;
    int lasttype = 0, lastbut = 0;
// etc...

void writebinds(stream *f)
{
 // ...snip...
    gamepad::writebinds(f);
}

Finally, I "just" added a file to the Visual Studio project (the most recent development version of Sauerbraten comes with a solution file in src/vcpp which plays nice with Vistual Studio 2010) called xinputpad.cpp, and then edited its properties so that it uses the engine.h / engine.pch files for precompiled headers (rather than cube.h / cube.pch).

I think this approach is minimally invasive as the code sits nicely in its own file, and the changes to engine.h, main.cpp and console.cpp are tiny. I also tried imitating the terse coding style of Sauerbraten rather than using my own (C++ politically correct and at times bombastic) pen.

I am having a blast (rumble rumble) with this game. Boy I love that rocket launcher!


This is the full xinputpad.cpp code. Be careful when copying and pasting, some characters that are "unsafe" for HTML might have been encoded.

// Experimental support for Microsoft XInput-compatible gamepads in Sauerbraten.
// Zlib license. Copyright (c) 2012  cristi.vlasceanu@gmail.com
#include "engine.h"
#include <XInput.h>
#if defined(_MSC_VER)
 #pragma comment(lib, "XInput.lib")
#endif
#ifndef _countof
 #define _countof(a) sizeof(a)/sizeof(a[0])
#endif

#define DECLARE_XINPUTS \
    XINPUT(none, action_none), \
    XINPUT(left_stick, action_move), \
    XINPUT(right_stick, action_mouse), \
    XINPUT(left_trigger, action_key, "z"), \
    XINPUT(right_trigger, action_key, "MOUSE1"), \
    XINPUT(left_trigger_release, action_key, "z"), \
    XINPUT(right_trigger_release, action_none ), \
    XINPUT(dpad_up, action_key, "w"), \
    XINPUT(dpad_down, action_key, "s"), \
    XINPUT(dpad_left, action_key, "a"), \
    XINPUT(dpad_right, action_key, "d"), \
    XINPUT(start, action_none), \
    XINPUT(back, action_none), \
    XINPUT(left_thumb, action_none), \
    XINPUT(right_thumb, action_none), \
    XINPUT(left_shoulder,  action_key, "c"),\
    XINPUT(right_shoulder, action_key, "MOUSE1"), \
    XINPUT(button_a, action_key, "0"),\
    XINPUT(button_b, action_key, "F10"), \
    XINPUT(button_x, action_key, "F9"), \
    XINPUT(button_y, action_key, "SPACE")

#define XINPUT(i,...) x_##i
enum { DECLARE_XINPUTS };

#undef XINPUT
#define STRINGIZE(i) #i
#define XINPUT(i,...) STRINGIZE(i)
static const char* inputs[] = { DECLARE_XINPUTS };

// bind to keyboard, mouse motion or player movement
enum actiontype
{ 
    action_none,
    action_mouse,
    action_move,
    action_key,
};
static const char* actions[] = { "none", "mouse", "move" };

struct keym;  // defined in console.cpp
extern keym* findbind(char* key);
extern void execbind(keym &k, bool isdown);

#undef XINPUT
#define XINPUT(i,...) { __VA_ARGS__ }

static struct action
{
    actiontype type;
    const char* def;
    keym* km;
    Uint8 prevstate;
    string name;
}
const defaultbinds [] = { DECLARE_XINPUTS };

static void bindaction(action& a, actiontype type, const char* key)
{
    a.type = type;
    a.def = NULL;
    a.km = NULL;
    a.prevstate = 0;

    if (type==action_key && key)
    {
        copystring(a.name, key);
        a.km = findbind(const_cast<char*>(key));
        if(!a.km) conoutf(CON_ERROR, "unknown key \"%s\"", key);
    }
}

// used when synthesizing mouse events, affects how fast the player turns
VARP(gamepadspeed, 0, 32, 512);
// invert y axis when emulating mouse motion events
VARP(gamepadinverty, 0, 0, 1);

VARP(triggerthreshold, 0, XINPUT_GAMEPAD_TRIGGER_THRESHOLD, 255);


struct controller
{
    enum thumb { left, right };
    int id, vibratemillis;
    bool bounded;
    action binds[_countof(defaultbinds)];
    static int count;

    controller() : id(count++), vibratemillis(0), bounded(false) { }
    ~controller() { XINPUT_STATE state; if (getstate(state)) vibrate(0, 0); }

    void resetbinds()
    {
        loopi(_countof(binds))
            bindaction(binds[i], defaultbinds[i].type, defaultbinds[i].def);
        bounded = true;
    }

    void vibrate(int left, int right, int duration = 0)
    {
        XINPUT_VIBRATION vibration = { min(left, 65535), min(right, 65535) };
        XInputSetState(id, &vibration);
        vibratemillis = duration + lastmillis;
    }

    bool getstate(XINPUT_STATE& state)
    {
        ZeroMemory(&state, sizeof state);
        bool result = (XInputGetState(id, &state) == ERROR_SUCCESS);
        if (lastmillis > vibratemillis) vibrate(0, 0);
        return result;
    }

    void motionevent(int x, int y, int dx, int dy)
    {
        SDL_Event e = { };
        e.type = SDL_MOUSEMOTION;
        e.motion.x = x;
        e.motion.y = y;
        e.motion.xrel = dx;
        e.motion.yrel = gamepadinverty ? dy : -dy;
        SDL_PushEvent(&e);
    }

    int inline mousedelta(int x, int xmax, int speed)
    {
        if (x >= xmax) return speed;
        if (x < -xmax) return -speed;
        return 0;
    }

    // compute the delta that we're going to use in constructing a fake mouse motion event
    int mousedelta(thumb t, int x)
    {
        static const int xmax = 32767;
        const int speed = gamepadspeed;
        int dx = mousedelta(x, xmax, speed);
        for (int i = 2; i != 32; i *= 2)
            if (dx == 0) dx = mousedelta(x, xmax / i, speed / i);
        return dx;
    }

    void checkthumbstick(thumb t, int x, int y, dynent* player)
    {
        static const int deadzone[] = { XINPUT_GAMEPAD_LEFT_THUMB_DEADZONE, XINPUT_GAMEPAD_RIGHT_THUMB_DEADZONE };

        int dx, dy;

        switch (binds[t + x_left_stick].type)
        {
        case action_mouse:
            dx = mousedelta(t, x);
            dy = mousedelta(t, y);
            if (dx || dy) motionevent(0, 0, dx, dy);
            break;

        case action_move:
            if (player->k_up || player->k_down || player->k_left || player->k_right) break;
            player->move = y > deadzone[t] ? 1 : (y < -deadzone[t] ? -1 : 0);
            player->strafe = x > deadzone[t] ? -1 : (x < -deadzone[t] ? 1 : 0);
            if (player->move || player->strafe) player->vel.mul(sqrtf(x*x + y*y) / 32767);
            break;
        }
    }

    void checkbindkey(action& a, Uint8 on)
    {
        if (a.type != action_key) return;
        if (on != a.prevstate)
        {
            if (a.km) execbind(*a.km, on != 0);
            a.prevstate = on;
        }
    }

    void checktrigger(thumb t, BYTE level)
    {
        const bool pressed = level > triggerthreshold;
        // check for trigger release
        if (!pressed && binds[t + x_left_trigger].prevstate)
        {
            auto& release = binds[t + x_left_trigger + 2];
            if (release.type==action_key && release.km) execbind(*release.km, true);
        }
        checkbindkey(binds[t + x_left_trigger], pressed);
    }

    void checkbuttons(WORD b)
    {
        checkbindkey(binds[x_dpad_up], (b & XINPUT_GAMEPAD_DPAD_UP) != 0);
        checkbindkey(binds[x_dpad_down], (b & XINPUT_GAMEPAD_DPAD_DOWN) != 0);
        checkbindkey(binds[x_dpad_left], (b & XINPUT_GAMEPAD_DPAD_LEFT) != 0);
        checkbindkey(binds[x_dpad_right], (b & XINPUT_GAMEPAD_DPAD_RIGHT) != 0);

        checkbindkey(binds[x_start], (b & XINPUT_GAMEPAD_START) != 0);
        checkbindkey(binds[x_back], (b & XINPUT_GAMEPAD_BACK) != 0);
        checkbindkey(binds[x_left_thumb], (b & XINPUT_GAMEPAD_LEFT_THUMB) != 0);
        checkbindkey(binds[x_right_thumb], (b & XINPUT_GAMEPAD_RIGHT_THUMB) != 0);
        
        // these are the digital triggers on some Logitech controllers
        checkbindkey(binds[x_left_shoulder], (b & XINPUT_GAMEPAD_LEFT_SHOULDER) != 0);
        checkbindkey(binds[x_right_shoulder], (b & XINPUT_GAMEPAD_RIGHT_SHOULDER) != 0);

        checkbindkey(binds[x_button_a], (b & XINPUT_GAMEPAD_A) != 0);
        checkbindkey(binds[x_button_b], (b & XINPUT_GAMEPAD_B) != 0);
        checkbindkey(binds[x_button_x], (b & XINPUT_GAMEPAD_X) != 0);
        checkbindkey(binds[x_button_y], (b & XINPUT_GAMEPAD_Y) != 0);
    }    
};
int controller::count = 0;

static controller c;

ICOMMAND(vibrate, "iii", (int* left, int* right, int* millisec), {
    c.vibrate(*left, *right, *millisec);
});

void gamepadbind(const char* name, const char* act)
{
    if (!c.bounded) c.resetbinds();
    if (strcasecmp(name, "reset") == 0) { c.resetbinds(); return; }

    int a = 0, n = 1;
    for (; a != _countof(actions) && strcasecmp(actions[a], act); ++a);
    for (; n != _countof(inputs) && strcasecmp(inputs[n], name); ++n);
    if (a == _countof(actions)) a = action_key;
    if (n == _countof(inputs)) conoutf(CON_ERROR, "gamepad input %s is not defined", name); 
    else if (a == action_key && (n == x_left_stick || n == x_right_stick))
        conoutf(CON_ERROR, "Cannot bind thumbsticks to key presses");
    else if ((a == action_move || a == action_mouse) && n != x_left_stick && n != x_right_stick)
        conoutf(CON_ERROR, "Cannot bind mouse or movement to key presses");
    else bindaction(c.binds[n], actiontype(a), act);
}
COMMAND(gamepadbind, "ss");

VARP(gamepadon, 0, 0, 1);

namespace gamepad
{
    void checkinput(dynent* player)
    {
        if (!gamepadon) return;
        if (!c.bounded) c.resetbinds();
    
        XINPUT_STATE state;
        if (!c.getstate(state)) return;

        c.checkthumbstick(controller::left, state.Gamepad.sThumbLX, state.Gamepad.sThumbLY, player);
        c.checkthumbstick(controller::right, state.Gamepad.sThumbRX, state.Gamepad.sThumbRY, player);
        c.checktrigger(controller::left, state.Gamepad.bLeftTrigger);
        c.checktrigger(controller::right, state.Gamepad.bRightTrigger);
        c.checkbuttons(state.Gamepad.wButtons);
    }

    void writebinds(stream* f)
    { 
        for (int i = 1; i != _countof(c.binds); ++i)
        {
            action& a = c.binds[i];
            f->printf("gamepadbind %s %s\n", inputs[i], a.type==action_key ? a.name : actions[a.type]);
        }
    }
}

ZeroBUGS Lambda Fun

A friend of mine tried to compile the code from my previous post using GCC, only to get a bunch of error messages. As I suspected, the fix was to specify -std=c++0x on the command line. But before answering my friend's G+ message, I had to verify that the code worked with GCC. And one thing lead to another. After compiling, I was curious to see how my ZeroBUGS debugger copes with lambdas. What else to do on a rainy Sunday afternoon in Seattle, other than playing with some old C++ code while listening to Judas Priest?

ZeroBUGS is a visual debugger for Linux, a project that ate up all of my spare time between 2004 and 2008. I kept making small changes to it since, but very limited in scope. For some reason, since the Big Recession I found myself having lesser and lesser time for on-the-side projects. I tried for a while making ZeroBUGS a commercial enterprise, hoping to leave my day time job(s) and become self employed. I learned the hard way that selling proprietary software to Linux geeks is not very lucrative. Or maybe I should have partnered with a savvy sales guy, the kind that can sell refrigerators to penguins.

In late 09 I put ZeroBUGS on ice and went working on Microsoft Windows for a short bit (just long enough to write a few lines of code that will hopefully make it into the upcoming Windows 8.)

After leaving Microsoft and joining TableauSoftware, I yanked the closed source product off my web site, and re-released ZeroBUGS as open source (and free as in free beer under the Boost License.)

I have not come upon major bugs in the debugger since a few years ago, when I discovered that the "step-over" functionality was broken for recursive functions.

So I was pretty confident the debugger will handle the new C++0X just fine. Except it didn't!

After some debugging, I traced the problem to the unnamed classes that the compiler generates to capture the surrounding variables. My debugger cashes data types by name for performance reasons. Unnamed classes normally occur in some scope, and thus there is no clash. Except that in the case of lambda functions, GCC generates unnamed classes at the outer most scope (i.e. the DWARF entries describing their type is at level 1, immediately nested in the compilation unit scope.) The data structures visualization was completely off, because the debugger used the wrong datatype (the first "unnamed" always won).

A simple hack that appends the file index and the line number to the offending "unnamed" solves the problem for now, as the snapshot above can testify.

While I think of a better solution this one will have to do. I am done with the computer for now, off to enjoy the weather and barbecue in the rain for the rest of the night!

Template Template Method

I recently had to write a bunch of C++ functions that shared a common pattern:

1) acquire a resource lock
2) TRY
3) do some work
4) CATCH exceptions of interest, and log them
5) release resource lock

I was eager to implement the "do some work" bits but did not want to bore myself silly by repeating the steps 1, 2, 4, 5 in each function (about thirty or so of them.) Now, you may recognize the problem, it is what the Template Method Design Pattern solves: "avoid duplication in the code: the general workflow structure is implemented once in the abstract class's algorithm, and necessary variations are implemented in each of the subclasses."

I could not however apply the Template Method pattern "as is" because my functions did not share a common signature. So wrapping them with a non-virtual function and then implement the "do some work" as virtual methods would not work in my case.

One alternative was to code steps 1 and 2 above as a BEGIN_CALL macro, wrap up steps 4 and 5 into a END_CALL and decorate each of my methods with these archaic C-isms. The approach would indeed work for C, but it is utterly indecorous in C++.

The spirit of the Template Method pattern can be preserved very elegantly by making the template method a C++ template method, and wrap the variant "do some work" bits into a lambda block.

The code sample below illustrates the idea (I added some mock objects to give more context).

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

// Mock a resource that needs exclusive locking
//
// -- think CComCriticalSection for example:
// http://msdn.microsoft.com/en-us/library/04tsf4b5(v=vs.80).aspx
class Resource
{
public:
void Lock() { cout << "Resource locked." << endl; }
void Unlock() { cout << "Resource unlocked." << endl; }
};

// Generic stack-based lock. Works with any resource
// that implements Lock() and Unlock() methods.
// See:
// http://en.wikipedia.org/wiki/Resource_Acquisition_Is_Initialization
template<typename T>
class Lock
{
Lock(const Lock&);              // non-copyable
Lock& operator=(const Lock&);   // non-assignable

T&  m_resource;                 // Lock MUST NOT outlive resource

public:
explicit Lock( T& resource ) : m_resource( resource )
{
    m_resource.Lock( );
}

~Lock( )
{
    m_resource.Unlock( );
}
};

/////////////////////////////////////////////////////////////////////////////
// Template Method Wrapper for an arbitrary lambda block:
//  1) lock a resource
//  2) log exceptions
// This is a variant of the Template Method Design Pattern
// -- implemented as a C++ template method.
template<typename F>
auto Execute(Resource& r, F f) -> decltype(f())
{
Lock<Resource> lock(r);
try
{
    return f();
}
catch (const exception& e)
{
    // log error
    clog << e.what() << endl;
}
typedef decltype(f()) result_type;
return result_type();
}
/////////////////////////////////////////////////////////////////////////////

// Usage example:

static Resource globalResource;


int f (int i)
{
return Execute(globalResource, [&]()->int
{
    return i + 1;
});
}

string g (unsigned j)
{
return Execute(globalResource, [&]()->string
{
    ostringstream ss;
    ss << '[' << j << ']';
    return ss.str();
});
}

int main()
{
cout << f(41) << endl;
cout << g(42) << endl;

return 0;
}

Update: to compile the code above using GCC you may need to specify "-std=c++0x" on the command line.

One thing that I grappled with for a bit was how to make the Execute template function figure out the return type of the wrapped lambda. After pinging Andrei Alexandrescu at Facebook (or is it "on Facebook"? No matter -- my English as a second language works either way, because Andrei does work for Facebook) and some googling around, I found the magic incantation: decltype(f()).

A Voyage to the Center of the Borg

A great while has passed since my last blog post. To my defense: I had been very busy playing Locutus of Borg. Microsoft bought out my employer back in 2007, and consequently I spent the past three years working in their Online Services Division, and Windows Server (yes, I did contribute a few lines of code to the upcoming version of Windows).

For months, if not years of my being a Redmondite I envisioned how I was going to blog about the strange and at times surreal experience of working for Microsoft. After all, I am the kind of geek who did not use Windows on his home machines. I only installed it after the acquisition, so that I could work from home every once in a while. I had imagined how the day would look like, when free of the Borg, I was going to report on how life on the inside felt like. I yearned to write about Microsoft politics, coding style and culture, the famous never-ending meetings and (some really amazing) people that I met there. I thought that I should document how their caste system (oops, I mean, career path model) twists people.

But now that I am on the outside, I cannot think of anything interesting to write about my days at Microsoft. Life goes on.

I'd rather blog on what a great product Tableau Software (my new employer) has. Or I could write about what an exciting weekend this one was, living on the web with my new Chrome OS laptop from Google (thanks again Sorin for the great surprise that got delivered Friday night!) Or I could write about enjoying the great read that the D Programming Language is.

Later.

The Power of Foreach

In D, arrays can be traversed using the foreach construct:

int [] a = [1, 5, 10, 42, 13];
foreach (i;a) {
    writefln(“%d”, i);
}

The array of integers in this example is traversed and each element printed, in the natural order in which elements appear in the sequence. To visit the elements in reverse order, simply replace foreach with foreach_reverse. It is as intuitive as it gets.

Moreover, linear searches can be implemented with foreach: simply break out of the loop when the searched-for value is found:

foreach (i;a) {
    writefln(“%d”, i);
    if (i == 42) {
        break;
    }
}

Consider now a tree data structure where a tree node is defined as:

class TreeNode {
 TreeNode left;
 TreeNode right;
 int value;
}

What is the meaning of a statement such as foreach (node; tree) { … }? The simple answer is that with the above definition of TreeNode, the code does not compile.

But if it were to compile, what should it do? Visit the nodes in order, or in a breadth-first fashion? No answer is the right one, unless we get to know more about the problem at hand. If we’re using a binary search tree to sort some data, then foreach would most likely visit the nodes in-order; if we’re evaluating a Polish-notation expression tree, we might want to consider post-order traversal.

Foreach Over Structs and Classes

Tree data structures and tree traversal occur often in computer science problems (and nauseatingly often in job interviews). Balanced binary trees are routinely used to implement associative containers, as C++ programmers are certainly familiar with the standard template collections set and map.

One difference between sequence containers (such as lists, arrays, and queues) on one hand, and containers implemented with trees on the other, is that there are more ways to iterate over the elements of a tree than there are ways to enumerate the elements of a sequence. A list (for example) can be traversed from begin to end and, in the case of double-linked lists, in reverse, from the end to the beginning; that’s it. But a tree can be traversed in order, in pre-order, post-order, or breadth first.

No built-in traversal algorithm will fit all possible application requirements. D’s approach is to provide the opApply operator as "standard plumbing" where users can plug their own algorithms for iterating over the elements of a class or struct. The operator is supposed to implement the iteration logic, and delegate the actual processing of the objects to a ... delegate:

class TreeNode {
public:
    TreeNode left;
    TreeNode right;
    int value;
    int opApply(int delegate(ref TreeNode) processNode) {
        // ... tree traversal
        // ...
        return 0;
    }
}

When the programmer writes a foreach loop, the compiler syntesizes a delegate function from the body of the loop, and passes it to opApply. In this example, the body of the delegate will have exactly one line that contains the writefln statement:

TreeNode tree = constructTree();
foreach(node; tree) {
    writefln(“%d”, node.value);
}

For an in-order traversal, the implementation of opApply may look something like this:

int opApply(int delegate(ref TreeNode) processNode) {
    return (left && left.opApply(processNode)) 
        ||  processNode(this)
        || (right && right.opApply(processNode));
}

The delegate that the compiler synthesizes out of the foreach body returns an integer (which is zero by default). A break statement in the foreach loop translates to the delegate function returning a non-zero value. As you can see in code above, a correct implementation of opApply should make sure that the iteration is "cancelled" when the delegate returns a non-zero value.

The traversal function’s argument must match the delegate argument type in the signature of opApply. In the example above the processNode function could modify the tree node that is passed in. If the TreeNode class writer wanted to outlaw such use, the opApply operator should have been declared to take a delegate that takes a const TreeNode parameter:

class TreeNode {
// …
    int opApply(int delegate(ref const TreeNode) processNode) {
        return processNode(this);      
    }
}

The new signature demands that the client code changes the parameter type from TreeNode to const TreeNode. Any attempt to modify the node object from within the user-supplied traversal function will fail to compile.

Another possible design is to encode all traversal algorithms as TreeNode methods. The following shows an example for the in-order algorithm (other traversal algorithms are left as an exercise for the reader):

class TreeNode {
// …
    int traverseInOrder(int delegate(ref int) dg) {
        if (left) {
            int r = left.traverseInOrder(dg);
            if (r) {
                return r;
            }
        }
        int r = dg(value);
        if (r) {
            return r;
        }
        if (right) {
            r = right.traverseInOrder(dg);
            if (r) {
                return r;
            }
        }
        return 0;
    }
}

foreach(val; &tree.traverseInOrder) {
    Console.WriteLine(val);
}

D Generators

A generator is a function or functor that returns a sequence, but instead of building an array or vector containing all the values and returning them all at once, a generator yields the values one at a time. Languages such as C# and Python have a yield keyword for this purpose. In D a generator can be implemented with foreach and a custom opApply operator. Assume one wants to print the prime numbers up to N, like this:

    foreach (i; PrimeNumbers()) {
        if (i > N) {
            break;
        }
        writeln(i);
    }

To make this work, the PrimeNumbers struct could be implemented like this:

struct PrimeNumbers {
    int n = 1;
    int primes[];

    int opApply(int delegate(ref int) dg) {
loop:
        while (true) {
            ++n;
            foreach (p; primes) {
                if (n % p == 0) {
                    continue loop;
                }
            }
            primes ~= n;
            if (dg(n)) {
                break;
            }
        }
        return 1;
    }
}

Pragma Assembly

Publishing the source code for D.NET on CodePlex in its current (rough) form turned out to be a great idea, as I received very good feedback. Tim Matthews of New Zealand has submitted several bug reports and patches and convinced me to change my stance on the "assembly class hack".

The hack was a very limited solution to the problem of qualifying imported declarations by the name of the assembly where they live. I described the problem and the attempt to hack around it at the end of a post back in December; a diligent reader commented that I should have used the pragma mechanism instead. I resisted the suggestion at the time, mainly because I am trying to avoid changing the compiler front-end if I can help it. (Front-end changes have to ultimately be merged back into Walter' s source tree, and he is a very very busy guy.)

A D implementation on .NET is not going to be of much use without the ability to generate code that imports and interfaces with existing assemblies. Guided by this idea, Tim Matthews did a lot of trail-blazing and prototyping and showed that because in .NET namespaces can span across assemblies, there has to be a way of specifying an arbitrary number of assemblies in one import file. My "assembly class" hack allowed for one and only one assembly name to be specified.

So I had to byte the bullet and do the right thing: assembly names are now specified with a pragma, like this:

pragma (assembly, "mscorlib")
{
// imported declarations here...
}

Any number of such blocks can appear within a D import file. And in the future, the code will be extended to allow a version and a public key to be specified after the assembly name.

Another thing that has to be fixed is to make the compiler adhere to the convention of using a slash between enclosing classes and nested types, as described in Serge Lidin's Expert .NET 2.0 IL Assembler, CHAPTER 7 page 139:

Since the nested classes are identified by their full name and their encloser (which is in turn identified by its scope and full name), the nested classes are referenced in ILAsm as a concatenation of the encloser reference, nesting symbol / (forward slash), and full name of the nested class

Tim also submitted a front-end patch that allows directories and import files of the same name to coexist, so that the code below compiles without errors:

import System;
import System.Windows.Forms;

An alternative solution that I proposed was to create import files named "this.d", so that the above would have read:

import System.this;
import System.Windows.Forms;

After some consideration, I bought Tim's point that this is not what .NET programmers would expect, and went on to apply his patch.