Crabs, still a terror for the bitmaps

Hello folks, this post is a proof that this blog isn’t dead at all. Actually I run (and I’m running) into some personal issues which made my mind floating a little bit away from these projects, but I’m trying to recover myself little by little these times.

So, now I want to post something different from the last (and still first) project. I want to post a somewhat forgotten-for-the-most old application which has been really important for me because introduced me, a lot of time ago, to the world of the C programming. I’m talking about Crabs, a program developed in the 80s at the AT&T Bell Labs by Mark Manasse and Luca Cardelli, and actually made famous by an article published on “Scientific American” in September 1985 called “Computer recreations: at Bell Labs work is play and terminal diseases ate benign” written by A.K. Dewdney. It happened to me to have a copy article something like 10-13 years ago and I fall completely in love with it, reading and re-reading it again and again trying to imagine how it was. Successwively I discovered (I was only a kid) that it was written in a language called C. The rest is history, at least for me :-).

So, the program was actually really simple. Described as one example of violation to the windows behaviour (one window should never be affected by the internal activities of another window nor by activities of the window system not concerning it directly), the program drew and managed the movements of some sylized crabs on the screen literally eating every pixel they were passing on and so the windows.Crabs eating windows As the program could be downloaded remotely on other computers, in a few days, this application became a nightmare for a lot of people at the Bell Labs. They then started to develop programs to kill all the crabs on the screen, but, as these anticrabs were too much dependent on the crabs process and structure, it was easy to circumvent them.

The rules for the crabs are simply:

  1. Crabs live on grey screen areas.
  2. On grey areas they move around randomly, but smoothly. The orientation of the crab icon is determined by its direction of movement, so that they always appear to move sidewise.
  3. When they bump into non-grey areas (including other crabs) they bite them by changing a little non-grey region into a grey region. After that they bounce off in a new random direction.

These rules were very simply because the computers were simply, as the screen was only in black and white (we are talking of a Blit!). So the core function to draw what we want on the screen is called BitBlt: given two bitmaps (in this case the crab and the destination portion of screen), it is possible to combine the source and the destination pixel according  to a specified raster operator and to write the result into the destination. The most simple operation is to simply move the source to the destination, but it’s possible to use AND, OR, XOR, NOT and some other operators.

In the article it is said that using the XOR operator is definitely mandatory, in order to restore the background when the crab moves away, as every crab does the following:

  1. Draws itself in the initial position. Starts with a random direction and velocity.
  2. Removes itself from the old position (by drawing itself in XOR mode)
  3. Determines its new position, based on its current direction and velocity
  4. Looks to determine whether it is about to move on a grey area.
    1. Yes: Moves there. Goes to 5.
    2. No: Makes the new position grey by drawing a 4×4 grey pattern. Does not move. Picks a new random velocity, indipendent of the current velocity. Continues at 5.
  5. Draws itself (in XOR mode) in the new position, as determined in 4.1 or 4.2.
  6. Adds a random deviation to its velocity, as described above.
  7. Back to 2.

An implementation of the program can be easily found on the internet, at this address. The problem is that it’s for 5620 DMD and 630 MTG terminals and that there are no other implementation around. So, I thought that I could write my own running on my Windows machine. A lot of the algorithm is taken from the old implementation, but I had to re-adapt the rest to correctly run on a modern machine. I don’t think that using the XOR trick works now: there are a lot of new problems, as the monitors are not anymore in B/W. Anyway nothing that special, as I just had to use some CreateBitmap, CreateCompatibleDC, CreateCompatibleBitmap, etc. Nothing special. One important thing I noticed is that it’s far way better to have Aero and 3D effects disabled, as the CPU goes straight to 100% and the animation is slow.

Here’s a screenshot of my implementation running on Windows 7:

Crabs on Windows

As usual, here’s the code: https://github.com/gbmaster/crabs. Here’s a link to a page containing a couple of interesting PDFs on the subject: http://research.swtch.com/crabs. If you have improvements for the code, just tell me and I’ll appreciate any of it.

Catch you soon and, remember, feel free to comment my post.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s