C+Objects: A Python-esque Library for C/C++

Not so long ago, I wrote a rather large Python code, which turned out to be a very useful tool. It was thousands of lines of Python, but I wrote it in only a couple of weeks. I wrote it "with my eyes closed", churning out the code at a high rate, and yet the number of bugs was small and they were always easy to resolve whenever problems did occur. This is the power of Python. The ease at which you can produce useful, working code is simply amazing. Writing such a program in C or C++ would take much longer, months, maybe as long as a year. Skill has little to do with it. The language simply is easy on the developer. It makes things easy.

Python is a fine language, and while its performance is quite alright, when compared to the raw power of C or C++ it just doesn't compare. Neither would I be comfortable creating something like a game in Python. While this is perfectly possible, my personal experience directs me to libraries like SDL, OpenGL, OpenAL, and what not.

At the same time, a language like C++ is perfectly suited for creating games, except that the language itself is the cause of lots of stress. C++ is not an easy language. It is overly politically type-safe correct, to the point where a little word like 'const' or a wrongly placed & sign has a completely different meaning and makes your program do weird unintended things. C++ pros may laugh at me, but consider the fact that I'm actually using C++ professionally, too.

In C++, I can almost philosophically ponder all day long whether a certain class should be implemented this way or another. While the beauty of the design is worth investing precious time in, are you getting any work done? And time is precious indeed. If I had to choose between easily writing a working program in Python, or struggling with C++ just to make the compiler happy, I'd choose Python any day. If only I could bend C++ to make it play nice, make it see things my way ... and you actually can. C++ is a very odd (but cool) language, which lets you redefine operators to make it behave the way you want. Insanity, it even lets you redefine the "()" parens and the "->" deference 'operator' ! (gasp!)

The past weeks I've been working on this library which implements some basic objects like a Number, a String, an Array, a List, and a Dictionary. These exist in the STL, but are not quite like how I would like them to be -- like Python. Anyway, what an adventure..! The undertaking was heavier than anticipated. Each class is derived from a base class named Object, which is the base of everything.

C++ has this cool feature that when a local instance goes out of scope, it calls the destructor. So you have some kind of automatic memory management. But wait, it's much more complicated than this. What if we added our String to a List and the String goes out of scope? Boom, the program would break. Oddly, when you use new to allocate an Object, it remains in existence and the destructor is not being called. Of course, you say, this is basic C++. Now, we use this feature to allocate a backend for our String 'proxy' object. The proxy may go out of scope, but the backend remains. The backend is not deallocated until a reference count drops to zero. Yes, adding it to the List increments the reference count in the backend of the added Object.

Using this library, we can now write code that looks a lot like Python code, but is really compiled by a C++ compiler. The performance is less than optimal, but surely better than Python's. Is everything ideal now? Umm no, I ran into a problem where the compiler lost track what type of object it was really dealing with, and I had to resort to static_cast<>()ing the thing to the correct type. C++'s type-correctness is really annoying. One other thing is that adding a new class is hell. You need to implement both a proxy and a backend class, and you need to implement lots of methods (low-level stuff like operator=(const Object&)) to make it work. Of course, your new class will have new methods, and you will have to use dynamic_cast<>() on the pointer to the derived backend a lot, which is coding hell.

Although I succeeded (more or less) in implementing a Python-esque library to ease writing C++ code, I'm now considering dropping the idea of mimicking Python and moving away from a copy-by-value paradigm to a more efficient pointer-oriented solution, much like Objective-C has. In Objective-C, everything is a pointer to an instance -- you just hardly realize it due to its syntax. Objective-C code is not as easy to write as Python, but I really dig its nice API and its convention of having really long descriptive names for members.

In Objective-C, everything is an Object, and it has 'manual' reference counting via two calls: retain and release. Retain/release is not super-easy but it does help a lot when compared to old-fashioned C memory management. This may be combined with an autorelease pool to easily deallocate unused objects. Objective-C has another feature that is extremely useful: calling a non-existant method in an instance (because the var is nil, for example) results in nothing being done. No program crash, it simply ignores the fact. I yet have to think about how one could mimic this behavior efficiently. This time my weapon of choice would be standard C. Ah, the joys of good old plain C.

Work, stress, and management

Now that we have entered the multi-core age, we should all be writing multi-threaded code. Even though it's nothing new, I'd still like to devote a (another) blog post to it. I came up with an extremely generic model that applies in most cases. It is based on the producer-consumer model, but with a twist. The standard producer-consumer is often a bit too simplistic in practice.

The Worker

Suppose we have a main thread that has a bunch of work to do. The work must be a number of tasks that are all the same, like for instance scaling a number of images. It doesn't really matter what kind of work it is, as long as you have a number of units that must be processed.

A single work unit is abstracted into a work object. This single work object will be processed by a process function. The process will be executed by a worker thread, who handles the work units. The work will be given to the worker by the main thread; the main thread acts like a manager.

This is a standard producer-consumer paradigm where the producer injects work, while the consumer takes work.

The Stressful Worker

Now imagine that processing a work unit takes some time, and the main thread doesn't have much else to do. This will mean that the main thread will be quick to hand out more work, piling it up for the worker as it is processing each unit one by one. This is overburdening the worker.

A solution to this problem is to have the manager wait until the worker is finished. You can optimize this and hand out a number of work units to a worker before waiting until the workload drops below a certain threshold. Note that the workload is really the length of the work queue (in the case where all work units are alike).

Another solution is to have the manager co-operate and let him do some work himself. This changes the model (and the code!) a lot since in this case, it's better to have the worker take on work by itself rather than being a slave.

Another solution is to have the manager manage multiple worker threads, one for each available core in the system of course. Depending on the type of work, it may or may not be easily possible to make use of multiple threads.

Some pseudo-code

Here's some pseudo-code to illustrate what I've been talking about.

1. The naive implementation, which causes overburdening the worker:

# the manager (producer)

for work in pile_of_work {

worker.give_work(work)

}

worker.time_to_go_home = 1

# the worker (consumer)

forever {

work = get_work()

if not work {

if time_to_go_home {

exit

}

continue

}

process(work)

}

2. The stressful worker, with a kind manager:

# the manager (producer)

for work in pile_of_work {

while worker.workload >= max_load {

sleep a bit or do something else

}

worker.give_work(work)

}

worker.time_to_go_home = 1

# the worker (consumer)

forever {

work = get_work()

if not work {

if time_to_go_home {

exit

}

continue

}

workload += 1

process(work)

workload -= 1

}

Clever people will note that sleeping is ugly and the manager should block instead until it is notified by the worker that it is done doing its job. This is best implemented using condition variables:

# the manager (producer)

for work in pile_of_work {

worker.give_work(work)

manager_condition.wait()

}

worker.time_to_go_home = 1

# the worker (consumer)

forever {

work = get_work()

if not work {

if time_to_go_home {

exit

}

continue

}

workload += 1

process(work)

workload -= 1

if workload < maxload {

# signal I'm ready for more

manager_condition.signal()

}

}

In this last case, I let the worker decide if he's ready to take on more work.

Python programmers get away easy: there happens to be a standard Queue class that implements the above workqueue, complete with a maximum workload that blocks the producer when the worker is being overburdened.

tutorial: Key Value Coding done right

In MacOS X / Cocoa, there is this concept of "Key Value Coding". It allows you to loosely couple objects together in a flexible way. For example, this is used by NSCollectionView to glue the interface (the GUI) of the program to the actual code of the program.

Key Value Coding means that you can get the value of a property by its key (which is a string). Note that this is exactly what a NSDictionary does, so making your custom class work with KVC, is a lot like making it look like a NSDictionary.

If you are still confused about what KVC is and want to know more, you may read the excellent page on KVC at MacResearch.

Turning a class into a KVC class

To make a class KVC compliant, it has to respond to the -valueForKey: method. The quick and dirty way is to implement this by checking the string and returning nil if it's an unknown key. In many cases this will actually work. There are some little extras that you should know, though. They are best explained by example:

@interface Album : NSObject {

NSString *artist, *title;

}

@property (retain) NSString *artist, *title;

// in Album.m

@synthesize artist, title;

-(id)valueForKey:(NSString *)key {

if ([key isEqualToString:@"artist"]) {

if (artist == nil)

return [NSNull null];

return artist;

}

if ([key isEqualToString:@"title"]) {

if (title == nil)

return [NSNull null];

return title;

}
@throw [NSException exceptionWithName:NSUndefinedKeyException reason:[NSString stringWithFormat:@"key '%@' not found", key] userInfo:nil];
return nil;

}

-(NSArray *)allKeys {

return [NSArray arrayWithObjects:@"artist", @"title", nil];

}

-(NSArray *)allValues {

return [NSArray arrayWithObjects:artist, title, nil];

}

Concluding

When making your class KVC compliant, take care of the following:

• implement -valueForKey: and check the name of every property
• if the property is nil, return [NSNull null] to indicate that the value is nil
• throw an NSUndefinedKeyException if the key is not found
• implement -allKeys, returning an array containing all valid keys
• implement -allValues, returning an array containing all values

flocking boids

Hi ... I got a bit stuck with my 3D space game when trying to get real-time impostors right. Impostors are dynamic billboards for rendering hundreds of distant asteroids. After a three week holiday, it was hard getting back into the code, so I put it on hold for now. On the bright side, I started working on a new arcade game that is really 2D, but with a 3D twist. It is inspired by Geometry Wars / |g|ridwars, GridRunner, and another old Jeff Minter game that features four cannons along the screen edges.

An intern that I'm currently working with, pointed out flocking to me. The guy is studying game technolology — you can actually get a master's degree in game technology nowadays, how great is that?

Anyway, flocking, also known as swarming, is a technique reminiscent of particle systems. While particle systems simulate physics models like fireworks, smoke, or fountains (water drops), flocking is an AI system that is great for simulating groups of animals. An impressive YouTube video shows such a simulation of a flock of birds that is under attack by two birds of prey.

On first thought, you might think that group behaviour is programmatically implemented by controlling the group as a whole. This is not true. Every bird (or boid, as the bots are called) in the flock is an autonomous entity sporting its own artificial intelligence.

How is this implemented? Each boid has an area of sight. If it sees it is going to collide with another boid (or object), it will adjust its heading to avoid collision.

At the same time, the boid wants to stay with the group. It does this by adjusting its heading, to get close to others, while trying to match the heading of a boid that is near. As a consequence, the boid will follow others.

Coming from an age when computers were slow, I first thought that this would be too slow to do in real-time. As it turns out, a modern cpu has no problems whatsoever with the little bit of math required for directing each boid. A pitfall is to have a boid influence another, and recursing because this action influences another, and ... You should not try to solve a mathematical puzzle here. Instead, focus on only one boid at a time and have it make the decision of how to adjust its heading. Do this for every boid, every discrete time step.

I implemented the AI rules in 2D in a game, and while the result is not as impressive as the flock of birds video, it is kind of cool. I started out by making sure that the monsters (or boids) would no longer pass through each other. This is done with a simple circle collision test. When a monster collides, it chooses another direction to move in. Once this was working, changing the code to get flocking behaviour was rather easy: increase the collision radius (area of sight) and adjust the direction only slightly rather than choosing an entirely different direction.

One problem I ran into was that the play area in this game is small and I don't want monsters to fly off the screen. So, the monster had to turn at the edges. Again, increase the area of sight, and have it adjust the direction.

In the game, the gliders (paper airplane models) flock together, while the magenta thargoids are going around like bumper cars, and are disturbing the gliders. The yellow cubes are stationary obstacles in the arena.

Note that it is possible to extend the AI with more rules, but flocking is a technique that already yields quite amazing results with just a few simple rules.