OpenGL Pac-Man

Every once in a while I like to re-create an arcade classic game just for fun. Many arcade classics are simple enough to be built by a single person with a reasonable amount of spare time. The game of choice is Pac-Man.

When you think about it, Pac-Man is rather bizarre. You are a pill eating yellow mouth that is being chased through a maze by four ghosts. Their mission: KILL THE PAC-MAN! What makes the game fun is that you may temporarily turn the tables by swallowing down a power-pill, after which you can EAT the ghosts. The hunted becomes the hunter. Combined with cutesy graphics it becomes child's play. This is not an easy game though, Pac-Man is notoriously difficult. Personally, I still can't make it past level five.

Programming a Pac-Man clone isn't particularly hard, but it does take effort to perfect it. There are lots of little tweaks and details that make the original so good. For example, the corners in the maze are rounded. This allows Pac-Man to cut corners and stay ahead of the ghosts that are in close pursuit.

Graphics

Rather than using old-fashioned clunky bitmaps, I went for scalable vector graphics so it neatly scales to any screen resolution. Clearly Pac-Man is depicted as a yellow circle with a pizza slice missing. When you do it this way, you'll notice that it doesn't look as nice. The thing is, Pac-Man's mouth is larger than a clean-cut pizza slice. The center of the circle is slightly off, allowing for a bigger mouth. For OpenGL this is not a problem; the Pac-Man character can be drawn as a triangle fan with circle coordinates, but the first vertex is not at the center of the circle.

The ghosts are drawn with a rectangle and a number of circles and ellipses. Drawing ellipses is not easy, but since these are all perfectly symmetrical ellipses they can be drawn as stretched circles: scale the Y direction and draw a circle; the result is a symmetrical ellipse.

A simple trick for drawing circles in OpenGL: calculate the coordinates for a circle with a radius of 1.0. This we call the unit circle. When drawing a circle with radius r, scale X and Y by r and draw the unit circle.

Movement

In the classic Pac-Man game the ghosts move from tile to tile, and so do they in my implementation. But since we're using OpenGL anyway, it wouldn't be a bad choice to use OpenGL's world coordinates instead and move from corner to corner. This would theoretically allow for ultra-high speeds. Come to think of it, maybe it would be nice if the ghosts would accelerate and hit the brakes before taking a corner. This would subtly change the game, however.

In terms of AI, I always thought that the ghosts moved in predetermined patterns, which is not true. Nor do they turn at random. Each ghost has its own behavioural rules. You can read all about it at the Pac-Man Dossier. This page describes the game in enough detail to allow you to create your very own Pac-Man clone.

Estimating tar size

There's a rather old but interesting question on StackOverflow: Is it possible to estimate how large the tar archive will become before you start packing? Some say yes, some say no. Well, of course it's possible. The exact figure would be given by:

    tar cf - directory/ | wc -c

This can be a rather slow command though, as it already runs tar and reads all data from disk. But can we estimate the archive size, and do so in a more efficient way?
Yes, it's possible, but you have to mimick the tar program really well when adding up all the sizes of the individual files. Unexpectedly, this is kind of hard. Tar is a much more complicated utility than you might think.

In essence, tar concatenates files after one another. The resulting tar file is called an archive, and every file in it is a member. It saves the original file name, size, and other relevant metadata such as ownership in a header directly in front of every member. So the size of the archive will be bigger than the sum of the sizes of the members, but by how much exactly?

Tar works with 512 byte blocks. Every header is in a 512 byte block, padded with null bytes, and all member data is stored in 512 byte blocks. The final member data block is padded with null bytes as necessary. Members like directories and symbolic links do not have data bocks. They are stored in the archive just by their headers. Classic tar ends the archive by appending two blocks filled with null bytes.

With this information you should already be able to get a pretty good estimate of how large the resulting tar archive is going to be.

But it isn't quite right. Why is that? The classical view of the world works but it isn't quite like that anymore.

One of the problems with classic tar was storing long filenames. Tar does not only store the file's name, but also its leading path. As the directory structure gets more deep, the stored filename becomes longer. There was only 100 bytes of room in the tar header for filenames, so storing a file with a longer path was simply not possible using classic tar.
Later, UNIX gained ACLs and high precisicion file access times, and tar should be able to store and restore those.

In order to resolve these issues, extensions to the format were crafted, in which a regular tar header may be followed by an extended header block. The PaX format became a POSIX standard. Archives that use the PaX format may optionally have a global header at the beginning of the archive accounting for two extra blocks (regular header plus an extended header). A PaX extended header is in the form of "key=value" and therefore can contain any kind of information. Tar implementations that encounter unknown keys may ignore them or give warnings.

Meanwhile, GNU crafted their own extensions that work in a similar way. For example, GNU tar has an extension for supporting sparse files with multiple holes.

To estimate the tar archive size, you have to guess (or know) what extended headers are going to be added. By taking filename lengths into account, as well as the destination paths for symbolic links, you can make a good guess of how many blocks of metadata this is going take.

Remember I said that tar archives end with two blocks of null bytes. Well, GNU tar likes working with a blocking factor of 20, meaning that it will do I/Os of 20 blocks at a time. As a consequence, it writes archives by multiples of 20 blocks. So for GNU tar archives there will often be more than just two blocks of null bytes at the end.

I actually implemented all of this in code and it's pretty accurate at estimating tar archive sizes. I have seen cases when it was off, though. The only way you could really get 100% accuracy is to use tar anyway. I suppose tar could use a dry run mode.

When you take a close look at the tar format, you find this hodgepodge of headers and extended headers and slight variations. This is what 30+ years of software evolution does to a program. It's almost poetic, seeing tar as a an organic mass.

For a more detailed description of the tar format, see:

• Wikipedia: tar (computing)
• GNU manual: Basic Tar Format

A tale of two tiny bugs in Linux PAM's pam_access

Recently, a colleague of mine decided to introduce netgroups to our systems. NIS netgroups are a means of logically grouping users. So I reconfigured PAM to use netgroups: users had to be member of a certain netgroup to be granted access to the system. To my surprise, it didn't work on one system, while it did on another. Clearly we hit a bug, and one system was running a different version of the pam_access module. A little digging let to the excavation of an old bug. Interestingly enough, I discovered a second tiny mistake in the code.

First of all, I want it to be clear that I have great respect for all the developers that do the hard work for Linux. Zooming in on this little piece of code is for the love of code, and to illustrate the nature of the bug in detail for educational purposes.

Let us do a bit of NIS programming. You need the innetgr() function to tell whether a user is member of a group. Its signature is:

int innetgr(const char *netgroup, const char *host, const char *user, const char *domain);

The function innetgr() returns 1 for a successful match and 0 otherwise. The host and domain parameters may be NULL. The domain must be set though if a NIS domain has been configured. In order to find out what the NIS domain is, you can use either yp_get_default_domain() or getdomainname().

int yp_get_default_domain(char **domp);
int getdomainname(char *name, int namelen);

Both functions get the domain name, apparently there are systems where only one of these is available. If no domain name is configured, yp_get_default_domain() will set the pointer to NULL. The function getdomainname() may set the name to "\0" (empty string) or it may set it to "(none)".

The pam_access code looked like this:

/* netgroup_match - match group against machine or user */

static int
netgroup_match (pam_handle_t *pamh, const char *netgroup,
        const char *machine, const char *user, int debug)
{
  int retval;
  char *mydomain = NULL;

#ifdef HAVE_YP_GET_DEFAUTL_DOMAIN
  yp_get_default_domain(&mydomain);

#elif defined(HAVE_GETDOMAINNAME)
  char domainname_res[256];

  if (getdomainname (domainname_res, sizeof (domainname_res)) == 0)
    {
      if (strcmp (domainname_res, "(none)") == 0)
        {
  /* If domainname is not set, some systems will return "(none)" */
          domainname_res[0] = '\0';
        }
      mydomain = domainname_res;
    }
#endif

So, suppose you have a system that has no NIS domain name configured and it used getdomainname() to get the domain name. Consequently the name will be either an empty string or the string "(none)". If the domain is "(none)", it will be reset to an empty string. If you pass an empty string as domain to innetgr(), it will fail and report the user is not part of the netgroup. The reason is that the domain parameter of innetgr() must be NULL to indicate any domain name, an empty string will not do.

Note that this is an old version of the code. However, this code was still current for a debian linux system. Debian is known for running ‘stable’ code, as new software is likely to include new and buggy features. This particular bug was fixed over a year ago though.

The second problem with the code was still present, and it is right here:

#ifdef HAVE_YP_GET_DEFAUTL_DOMAIN

which is clearly a typo. When you make typos in code the compiler will usually catch them, but this is a preprocessor statement and it managed to go unnoticed for at least three years. This typo caused yp_get_default_domain() never to be used at all. This wasn't much of a problem since Linux systems typically provide both functions, but ironically, the block with getdomainname() contained a bug. Fixing the typo causes yp_get_default_domain() to be used and effectively discards the block with getdomainname().

Computers are very unforgiving to the mistakes that we humans make. The smallest of mistakes can be of great consequence (like users not being able to authenticate (!)). I was lucky to encounter and fix this problem, and I guess it shows the beauty of open source. Anyone can contribute to open source software, and anyone can help in making the whole a little bit better.

oolib gets notifications

Apple's Cocoa API has an interesting feature named the Notification Center. It enables UI components to communicate by posting messages to whomever is interested. I suppose it's a bit like Twitter in the insides of a computer program; objects may blurt out messages regardless of who is listening, and objects may show interest in receiving messages from other objects.

Notifications allow for loose coupling between objects. Suppose you have two classes A and B, and you want to make a state change in an instance of class A known to an instance of class B. The traditional way of doing that is to have A call a method in B. Now, A depends on B, and they are tightly coupled.
With notifications, the situation changes. A announces its state change to the world. B listens to state change messages, so it picks up the state change. There is no interdependency between the two, they are just handling messages. You can add a third class C that reacts to the message in another way, without touching class A.

This is particularly useful for GUI widgets; for example, a button announces it's been pressed, a scroll bar announces it's been moved, and a movie player announces it's finished playing.

For oolib, my personal C++ framework, I wanted to have this functionality too. It basically works like this: an object may register itself as an observer of certain messages. Whenever that message is sent, the observer will be notified.

class MyObserver : public Observer {
public:
    void notify(const char *event) {
        print("observer: %s", event);
    }
};

const char *Event1 = "This is event #1";
const char *Event2 = "This is event #2";

int main(int argc, char *argv[]) {
    MyObserver o;
    add_observer(o, Event1);
    add_observer(o, Event2);

    notify(Event1);
    notify(Event2);
    return 0;
}

The global notify() function will see to it that observer->notify() will be called for all registered observers.

There is one big difference between oolib's notify() and Cocoa's NSNotificationCenter: Cocoa works with Objective-C, and allows you to supply a selector—which is a function pointer, so it's essentially a callback mechanism.
With oolib, you are required to inherit from Observer and implement the virtual method notify(), which is more like ‘the C++ way’ of doing things.

Finally, I should mention the Qt framework. Qt has a feature called slots and signals, which allows you to connect a slot (class method) to a signal, which can be emitted by some object. It looks like Qt works by virtue of pointers to methods... which is peculiar because C++ does not deal well with pointers to methods. The Qt folks actually use a meta-compiler that generates the code needed to make it work.

This programming trick is also known as the observer pattern.