As an academic exercise, I put together some code to create a “interleaved threads”: i.e. create two threads each with a manual yield() function that “swaps” the current thread to the other thread.

The trivial example I used was to print all the numbers from 0 to 99 with each thread counting one digit then transferring to the other thread: i.e. one thread prints all the evens and the other prints all the odds. The threading code then synchronizes things such that the numbers come out in order. It uses a common “yield” pattern to notify when the active thread should be swapped.

Before we get any further, two major caveats:

• I’m not sure what a good real world application for this would be. This completely defeats the purpose of using threads to run things in parallel, though it might be useful for the code architecture since each thread still has it’s own stack and instruction pointer and might be used for something akin to what corountines are sometimes used for?
• I’m pretty sure the implementation wastes a bit of time in the scheduler since it doesn’t really “swap” the current thread, but rather thread A simply refuses to run until the scheduler decides to let thread B run

As I said, an academic exercise. However, I thought it still might be worth sharing. I’d be very interested in hearing feedback if someone is aware of a case where this stratagem might be useful in practice.

Counting Evens and Odds

Here’s what the code looks like to produce an output of:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99,

#include <boost/thread.hpp>
#include <boost/thread/mutex.hpp>
 
void count_odds (YieldFunc yield)
{
    for (int i = 1; i < 100; i += 2)
    {
        std::cout << i << ", ";
        std::cout.flush();
        yield();
    }
}
 
void count_evens (YieldFunc yield)
{
    for (int i = 0; i < 100; i += 2)
    {
        std::cout << i << ", ";
        std::cout.flush();
        yield();
    }
}
 
int 
main (int argc, char** argv)
{
    InterleavedThreads(count_evens, count_odds);
    return 0;
}

I’m not sure how generally useful it is, but it is surprisingly clean, right? Not a lot of unreadable threading code in there.

(This might actually be far more efficient if fibers where used rather than threads since that would allow an explicit “swap” from one execution context to the other. However, I know very little about fibers other than vague reports that they are easy to misuse. Here’s a link that suggests fibers may not be the best idea.)

InterleavedThreads

If there’s any magic to the above, it’s all wrapped up in the InterleavedThreads implementation. Without much commentary, here it is:

typedef std::function<void()>  YieldFunc;
 
struct InterleavedThreads
{
    InterleavedThreads (std::function<void(YieldFunc)> f0, std::function<void(YieldFunc)> f1)
    {
        volatile int start0 = 0;
        volatile int start1 = 0;
        boost::mutex    active;
        boost::mutex    waiting;
 
        auto yield = [&]() 
        {
            active.unlock();
            waiting.lock();
            active.lock();
            waiting.unlock();
        };
 
        boost::thread_group group;
        group.create_thread( [&]() {
 
            active.lock();
            start0 = 1;
            while (!start1) {}
 
            f0(yield);
 
            active.unlock();
        });
        group.create_thread(  [&]() {
 
            while (!start0) {}
 
            waiting.lock();
            start1 = 1;
 
            active.lock();
            waiting.unlock();
 
            f1(yield);
 
            active.unlock();
        });
        group.join_all();
    }
};

There’s a tiny, little busy wait to ensure thread 0 starts before thread 1 (that’s part of the implicit contract I had in mind when throwing this example together). Feel free to substitute a “real” threading primitive in there to accomplish the same if you are allergic to busy waits.

Then the basic mechanism is accomplished via handshaking of an “active” mutex (held by the thread that’s actively running) and a “waiting” mutex (held by the thread waiting for to be active). Using the initial busy wait we ensure an initial state where thread 0 has the “active” mutex while thread 1 has the “waiting” mutex. The exchange of the ownership of the two mutexes is handled by the yield lambda. We two mutexes to accomplish the handshake, otherwise active.unlock() followed directly by active.lock() would likely mean the active thread would reacquire the mutex immediately without the waiting thread having a chance to acquire it.

Conclusion

I’m not sure there’s a conclusion. I’d love to hear some feedback if you find this at all interesting or can imagine a potential use for it.

I recently added NifLib to the set of automatically built external libraries included with LxEngine.  My motivation is to test out some “real-world” data with LxEngine in order to identify the most pressing holes in the architecture.  The dependency builder now automatically builds numerous useful libraries, making LxEngine a useful build platform, even if you’re not interested in the slightest about the LxEngine code itself…

The dependency builder is Windows only – which is okay, given that the dependencies are most problematic on Windows.  What the dependency build does is this: download the external library, build it, and copy the resulting files to a uniform sdk structure (i.e. use the same convention for each library).  A cmake file then sets up the correct include and lib directories – which is relatively easy given that everything is now in a uniform structure.  Lastly, since all the dependencies are built locally, the source is on the local system along with PDB debugging file, allowing you to step through the external library source while debugging. You can modify the source and rebuild the library(s) if necessary as well. Any Windows developer who has ever worked on an open source project with numerous external library dependencies can likely appreciate how incredibly useful this is.

Invoking the dependency builder is as easy as:

    cd dependencies
    build_vs.bat

(wait several hours as all the libraries download and build)

Bottom-line: these external libraries just build and work.  No worrying about Windows build configuration hassles.

Currently the dependency builder includes support for:

• Boost 1.46.1
• GLM 0.9.2.3
• OGRE 1.7.1
• Bullet 2.78
• Google V8
• OpenAL Soft
• LibVorbis 1.3.2
• LibOgg 1.2.1
• FreeType 2.4.2
• NifLib

One last important note, though: since these are built locally on the system, the initial run of the dependency builder takes a long time!

But once it’s done, it just works.

As mentioned in the prior post, I’ve taken a break from the lower-level graphics programming that I’ve been posting about on this blog.

I’ve started a small project creatively called “Adventure”.  The vision (which isn’t very well-defined at this point) is to create a small game that is some sort of cross-breed between a linear, story-driven adventure game (e.g. King’s Quest) and a simulation game (e.g. SimCity).  What exactly this means will evolve, but overaching theme is to create a “complete” engine that heavily utilizes existing third-party toolkits, is part “sim” and part “story.”  I want to take some time away from a single low-level component and spend more time on understanding the big picture – not to mention honing my skills battling the Not Invented Here tendency many developers, my self included, seem to have.

About Adventure…
As I mentioned, completeness is a higher priority than anything else.  Therefore, I’ve start out simple with version 0.0 being a simple text adventure game.  In the current incarnation there are only a half dozen rooms and the player simply needs to figure out the right commands to enter in order to win.

(Needless to say, with a name like “Adventure”, I’ve  put creativity in the game concept and story on the back burner as well.)

About the Technology…
While it is a simple, text-based game at this point, I am trying to build a solid base to expand it into a more technically noteworthy game.  For example, the build system uses a nested CMake hierarchy.  The code is linking against Boost, which opens up a lot of doors for reuse of some solid, useful code.  The game data is loaded from Lua files which allow for custom scripted actions in each room.  

The Adventure code itself is not much, but the intention is to establish a good base to build upon where code is added, to replaced, as more advanced functionality comes on-line.  I intent to spend a significant amount of time building a very clean base so that the architecture evolves fluidly.

Architectural Concepts

The game architecture at this point revolves around three key concepts.  They are fairly simple, but the interesting part is that even though they are simple, it’s quickly apparent how these concepts allow for a fairly complex game system to be constructed.

Cell
A Cell is a self-contained part of the game world.  The player is in one and exactly one Cell at any point during game play.  The only way to exit a Cell is via a well-defined connection to another Cell.   Any actions that take place by the player are local to that Cell.

These restrictions keep the game space well-defined so that the game simple to code for, stable, and logical.  Of course, exceptions to these rules (for example, some actions may affect other Cells) but as a general guideline this works well.

This concept works well for a single text-based game, but it also should works for a  graphical game.  The cell is basically the current “area” whether that’s a single enclosed room or a large outdoor map.  The concept can be expanded upon by making Cells into a heirarchy or expanding the notion of locality of action to chain to neighboring cells to an N-th degree.

Action
The next concept is an Action.  An Action is simply the user doing something that causes the game world to react.  Quite simple.

In the text-based world, the Action is usually just a command like “get”, “look”, “listen”.  It’s a verb that – depending on the verb – may act upon a particular Entity in the Cell or act upon the Cell itself directly.

In a graphical world, the Action may include additional details implicit from where in particular the player is located or looking.  However, the basic notion concept of a single discrete Action, with accompanying Entity and some details about the Action, more or less translate equivalently whether it is text or graphics.

Entity
An Entity is an object in a Cell that can be receive an Action.  This may be a non-playable character, a lamp, a whisp of fog – it’s anything that an Action can be applied to.

State of the Code

The current build has fairly decent starting points defined for Cells and Actions.  Next is a good, generic, scriptable Entity concept.

Recently added the ability to dynamically reload the game data while in game.  It stores the file modification time of each cell it loads and reloads and newly modified files upon an update command.   Given that the system is using reference counted boost::shared_ptr<> objects, this works correctly even if the cell that the player is actively in is reloaded (the old version won’t be discarded until it is no longer referenced).

On a related note, I also updated my perforce server to the latest version (thank you to Perforce for making it so straightforward – server upgrades of personal data always sound like potential for disaster) as part of starting this project.

The problem with a hobby project, which is being done for fun and learning, is that there’s really no reason not to stop what you were doing and start something new, as long as that too is fun and involves some learning.

I’ve spent a bit of time over the last several weeks working on other projects, from learning the basics of git (I’m primarily a perforce user), OGRE (I’ve been writing my own engine from scratch previously), Boost (in particular Boost.Asio for networking, which I’m currently frowning upon as grossly violating the KISS principle) and who knows how many random side projects (e.g. JQuery UI, Google App Engine using Java).  I’ve even spent a bit of time back in the world of playing video games (e.g. I’m very impressed by Batman: Arkham Asylum‘s seemingly choreographed real-time fight sequences – I’m curious what kind of game logic is necessary to drive that.)

I’m toying with the idea of starting a new version of the LxEngine based solely on interconnected open source SDKs (OGRE, Bullet, Lua, Google V8, etc.).  I’m not committed to the idea, but we’ll see…