How does car physics work in the original Death Rally? Part one, background extraction, background position tracking. (C++, OpenCV)

Likely the original Death Rally is my favourite game of all time. Okay, maybe I loved other games too, I grew up with Lara Croft and I played through all the classic Tomb Raider games at least three times (by the way, I didn’t consider this sentence, I’m sure I never will grow up), but Death Rally just calm my nerves. I just feel the speed and I’m able to keep the whole race under control and the world seems even-handed and fair again. Action, ultra-violence, good cars.

Maybe you think that Death Rally is just one of these ordinary 2D top-down car games, like the Micro Machine series or Super Cars II or Slicks (talking about them makes me feel old, especially because I played all of these very-very old games), but I don’t think so. If you don’t want to try the original Death Rally, you could give a chance to the modern remake of Death Rally (or to the movie Death Race).

I’ve been planning to reverse-engineer the in-game car physics of Death rally for a long time, but I never took a crack at it. My biggest motivation is that it is not an easy problem. Actually, I tried to code car physics once, later I will upload this try, it is a mini-car game written in C++ (and Windows API). It was my student class project when I took my first C++ course. (Good old days.) Frankly, its physics is just terrible. Now, I want to understand how Death Rally works and why its physics is so cool. Car physics is an important part of the “unique game experience”, because players can push other cars, players can learn how to drift their car and with the best driving style, a very good player beats all the quiche eaters even if they have much better cars than him.

*** Part one: Background/foreground segmentation ***

In this article, I introduce my approach to extract the background of a track in Death Rally. I want to measure the position and the orientation of the cars with minimum error and in order to achieve this, I will extract the background first. When I will have the background, then a simple subtraction will solve the problem of the foreground/background segmentation. In this concrete case, the foreground/background segmentation is much easier than in general, because the track below the cars or the background behind the car’s pictures is only one simple picture, and we see it through a small window, they are in the same plane and they are able to move only in the same plane.

If you think, that we don’t need to write programs to extract the background, all we need is a video editor, a gimp and enough patience, then you are right. But I chose a different way, I implemented a small OpenCV program which extracts the background. Why? Maybe because I’m a programmer, or because we can reuse it in other programs. So I did the following steps:

Step 1: Install OpenCV, go to the folder ‘samples’, then create your own copy of the file ‘starter_video.cpp’ to your own working directory. After than install something like an Automake script+Emacs/VI (or an integrated GUI if you feel like having one) that makes possible to compile the modified files in  a simple way.

It is not complicated, especially when you are using Linux, so if you like challenges, then forget Linux and buy a Windows before this step. Here is a good installation guide. Writing an Automake script for that is also not hard, check this before you write it, it could save time (and it contains the necessary commands).

Step 2: Download the shareware version  of the original Death Rally and a DOSBox, and create two or three videos from your favourite race track (it is Rock Zone in my case) using DOSBox and Ctrl+F5.

Step 3: Determine the absolute position of the images of the videos (regarding to the background).

I determined the shift vector between the images to calculate it. In Death rally, the picture of the race track is one big image and the camera shows always a small portion of that, so if you examine a picture and the next picture after than, then you see almost the same content but this content is a bit shifted on the second image. I used a very simple algorithm to determine the shift vector. (There are existing very sophisticated methods.) It just takes all possible shift vectors (it starts with (0,0) then it takes (0,1), it always takes the vectors by length in ascending order), it always shifts the first image according to the current vector and it calculates the number of pixels that have different colors on the shifted first and on the not-shifted next image. When this number is more than 10,000 then the algorithm thinks it’s OK and it returns the shift vector.

shift_vectorFigure 1: An illustration of the shift vector between the images.
The red vector is the shift vector.

This method works because the coordinates of the shift vectors are always integer numbers in Death Rally. (It allows higher performance, no filtering needed.) And this method isn’t painfully slow because the coordinates of the shift vectors are usually small numbers. (However, there are also exceptions, for example, at car crashes – once I measured the vector (15, 3), and 15 is not a small number in this case.) I calculated the shift vectors image by image. The sum of the shift vectors resulted the absolute position of the current image regarding to the first image without error. Step 3 accomplished.

Step 4: Segment out the background of the images and merge the portions of the background considering their absolute position.

My solution is not perfect, however, it works more or less. I always took two images, an image and the next image after than. I shifted the first image with the calculated shift vector, then I took the pixels that were the same on the shifted first and on the next image. I though the other pixels cannot belong to the background because they changed in the fraction of a second. And when the intersection of the two images had too much points (the difference of the number of the pixels of the original and the intersection image was less than 1,000), then I dropped it, because it was suspicious. (For example, at the start of the game, cars and camera don’t move, all images are very – and too – similar.) I used weighted average to merge the intersection images.

imgFigure 2: The application extract_background in action,
that determines also the absolute position of images

These are the necessary steps, with these four steps I could estimate the image of the track background. Here is the source code of the app ‘extract_background’, you can download it if you want to. I executed it on more videos, I generated more track background Images  and then I merged them with Gimp only the track. At the end, I removed the 3d objects of the track and the background manually:

sum01sum03

Figure 3: On the left, there is a generated image, on the right,
there is the result of the merge of generated images after some edit

In the next article, I will use the image on the right side of Figure 3 in order to segment out the foreground. I will take the image of the cars and I will write a program that will be able to measure the position and the orientation of the cars in Death Rally, and after than I will try to reverse-engineer the car physics.

Advertisements
Posted in C++, OpenCV | Tagged , , , , ,

What is the difference between a junior and a senior programmer? (Personal)

Nowadays, I don’t feel like writing, but yesterday a funny idea came up to my mind. Once – it happened not so long time ago – I was in the running for a simple job, a determined guy prepared to give 10 dollars per hour to a handsome programmer, who could teach him programming. I admit that I wanted to be the teacher and the winner of the job, but I just wasn’t handsome enough. It was my first job interview in English – okay, it is a slight exaggeration, I talked to a teenager who was maybe more unemployed than me at that time. Anyway, it was a funny situation and I was so embarrassed that I wasn’t able to tell what distinguish a senior programmer from a junior programmer.

Well, it is not a real hard question, there are complicated and detailed explanations all over the internet. (Try this thread on stack exchange or read Jeffry R. Fisher’s opinion, or visit Jeff Atwood’s Coding Horror again and look for The Eight Level Of Programmers.) But believe me, it is much easier. What distinguish a world chess champion from a grandmaster and what is the difference between a chess master and an amateur? I’m sure you know something about that even if you cannot formulate it in an accurate way. What is the difference between a seasoned professional and a tenderfoot? As far apart as the poles. I don’t want to formulate the difference (as I mentioned, I don’t feel like writing), but I try to show it:

animation
Yes, it is so simple, seasoned players are just better players, and they hide more aces under their sleeves and/or their belts. I experience it nowadays many-many times, and that’s why I feel lucky. (The picture comes from the famous game Railroad Tycoon. Thank you for that, Sid Meier.)

Posted in Personal | Tagged , , ,

How to write your own AS3 project using VI and how to compile it under Ubuntu linux (ActionScript 3.0)

Once I thought Adobe Flash CS5 was the only one way to write ActionScript 3.0 programs. Well, it is not true, but I didn’t know that. I’m a programmer and my profession is not drawing and animating things, I’m working with alphabets and text editors. I tried the trial version of Adobe Flash CS5 and it was a torture. It was completely inconvenient. Why? Because it was designed for writing short scripts which could be attached to dozens of drawings and animated characters, and that’s why this software is almost unusable if you want to do the opposite. Besides it is expensive. (Or at least in those days when I wanted to buy it it seemed so expensive to me like a gold bar). Using an illegal copy of Adobe Flash CS5 to write programs is something like stealing a Lamborghini to transport pigs to the market. Maybe you think that Lamborghini is a cool car and using a cool car must be cool, but the inappropriate usage reveals that you are an amateur.

Thank God for you I had good luck, I discovered FlashDevelop. (I found the idea on Stack Overflow, of course: http://stackoverflow.com/questions/5418058/free-flex-ides.) Wow, it was much better. FlashDevelop is a customized Eclipse, so if you like IDE then it is exactly what you need. At least it dosn’t seem like GIMP (Flash CS5 does) and you start to feel yourself like a programmer immediately if you start using it.

I thought I saw the whole picture, I had only the following choices if I wanted to develop AS3 programs:

  1. Using Adobe Flash CS5
  2. Using Flex IDE
  3. Using Flash Develop or FDT

Yesterday I read a forum topic (see here)  and I discovered that there was also a fourth alternative and likely it is the best way for a weird guy like me to write AS3 programs. Flex SDK contains a platform independent AS3 compiler (mxmlc), and that allows you to write AS3 program with your favourite text editor. (VI or Emacs, that is the question.) It doesn’t sound complicated, I tried it, it worked, and I wrote my own tutorial about it. So, how to write and compile your own AS3 project under Ubuntu linux using VI, gentle reader, just follow the following steps:

  1. [Prepare] Suppose you have a brand new Ubuntu Linux (12.10 in these days) and you don’t have a Java JDK. If you have Java JDK, just omit the second step. And etcetera.

  2. [Install Java JDK] I didn’t want to struggle installing the newest Java JDK, because it was meaningless to me. Currently I don’t have enough time to develop Java programs on my own machine. (Because I want to develop an AS3+Box2D platform game engine in my free time or something like that.) So I installed an older Java JDK using the synaptic package manager.

    sudo apt-get install synaptic
    sudo synaptic
    

    And after than, I installed the package oracle-java6-installer with only a simple mouseclick.

  3. [Download and unzip Flex SDK] I downloaded the newest Flex SDK (http://www.adobe.com/devnet/flex/flex-sdk-download.html), and I unzipped it into the directory /opt/flex_sdk_4.6. I used unzip and sudo, because writing anything into /opt is not allowed for non-super users.

  4. [Set PATH] After than I set the PATH. I used Thomas Deuling’s tutorial. First I just edited the good old .bashrc:

    vim ~/.bashrc
    

    Then I added the following line to that:

    export PATH=/opt/flex_sdk_4.6/bin:$PATH
    

    The next best thing that the AS3 compiler works after these steps, if you did the same steps like me, then just try this (according to Thomas Deuling’s tutorial again):

    source ~/.bashrc
    mxmlc -version
    

    And you will see some kind of magic:

    Version 4.6.0 build 23201
    

    The compiler reacts, so it works. Do you feel that you can compile your AS3 project under your Ubuntu Linux without any kind of IDE? I hope you feel the sound of music.

  5. [Create a project template (or templates)] It is pretty meticulous to write a program from zero and it is also meaningless in the most of cases. For example, I’m sure if I develop anything in AS3 then it uses embedded images and embedded sounds, and I don’t want to code the necessary classes again and again (because DRY=don’t repeat yourself). That’s why I wrote the template project SimpleAS3Project. I coded also a small automake script which allows to compile/delete the swf file with typing make/make clean. I’m sure I will write more templates later (Box2D project, project with animated gif files, etc.), but one template is enough for testing.

  6. [Set syntax highlighting in vim] First, download the file actionscript.vim. Then copy it into the directory /usr/share/vim/vimcurrent/syntax with the following commands:

    sudo mv actionscript.vim /usr/share/vim/vimcurrent/syntax
    

    Now the file is at its place, but it doesn’t work yet because first we need to set it in the file filetype.vim, so use the following command:

    sudo vim /usr/share/vim/vim73/filetype.vim
    

    and add the following lines to this file:

    " ActionScript
    au BufNewFile,BufRead *.as      setf as
    

    After than, vim will use syntax highlighting on as files automatically.

  7. Install completed. Enjoy it!
Posted in AS3 | Tagged , , , , ,

About middle-test loops

Ordinary program loops can be cathegorized into the following two cathegories: pre-test loops and post-test loops. For example, in C++ for loops and while loops are pre-test loops, do-while loops are post-test loops. (It isn’t very hard to find out whether a concrete loop construction is pre-test or post-test. If you can define a such loop using this concrete construction which body isn’t invoked at all, then this loop construction must be pre-test. Just try it: for(0;0;0) doSomething(); and while (0) doSomething(); show immediately that for and while constructions are absolutely pre-test.)

These facts are simple and well-known. Why is it interesting? Because newbies can ask weird questions related to this topic. Yesterday I’ve found the following thread on Stack overflow. (For your information, gentle reader, stack overflow is one of my stamping grounds. When I am a big and strong real programmer, I will collect some gold medals.) Here is it: http://stackoverflow.com/questions/1807110/is-it-possible-to-have-a-while-loop-in-c-that-makes-the-check-in-the-middle-of. I like the pure naivety of the question „is it possible to have a while loop in c++ that makes the check in the middle of the loop instead of the beginning or end?”, especially because it isn’t dummy at all. A typical reaction for a question like this is always something like „there is no (and can’t be) language constructs for every possible use case you can imagine”.  (Note: If you are a Perl programmer, you never answer something like that. In Perl, actually we have language constructs for every possible use case. 😉 )

Before we start thinking about the theoretical problem of  middle-test loops by ourself, it is better to make some researches first. The idea of „loop with test in the middle” is a pretty old idea, it was proposed by Dahl in 1972, see the relevant articles on Wikipedia, for example, this: http://en.wikipedia.org/wiki/Control_flow. Dahl invented a new loop construction and he wrote his loop in the following form:

loop
   ...
while condition;
   ...
repeat;

The first remarkable thing, that pre-test loops and post-test loops can be emulated with Dahl’s loop. If the tag ‘loop’ is omitted, we get a pre-test loop. If the tag ‘repeat’ is omitted, we get a post-test loop. If the tag ‘while’ is omitted, we get an infinite loop. This connection between infinite loops and Dahl’s super loop is especially interesting, because, if we use our imagination, Dahl’s loop seem like an infinite loop with a conditional break. (The instruction „break” helps us to leave the current loop in C++. So while is something like a  „conditional break” in this case, because it terminates the loop only when its condition is true.) In C++, we don’t have loop-while-repeat loop, but we can emulate it with an infinite loop and with a conditional break:

for (;;) {
   ...
   if ( !condition ) break;
   ...
}

or

while (true) {
   ...
   if ( !condition ) break;
   ...
 }

Of course there is not a such reason which is in the way of inserting more than one conditional break into this lovely construction. We can do it: 

while (true) {
   ...
   if ( !condition1 ) break;
   ...
   if ( !condition2 ) break;
   ...
   if ( !condition3 ) break;
 }

And frankly, we do it all the time. If you examine main loops of big software projects, you will see that they are infinite loops in the most of cases, and you will find much of conditional breaks in these infinite loops. For example in OpenGL, glutMainLoop() uses an infinite loop and about the same construction.


do {
   ...
   exit if (condition1);
   ...
   exit if(condition2);
   ...
 }

Sad, but it is not so elegant like Dahl’s loop, because we cannot omit the keyword ‘do’ and the main block of the infinite loop, if we want to. That’s why the following notation is more cool than the previous:

do {
   ...
}  while (condition1) {
   ...
}  while (condition2) {
   ...
}

I feel that it is awsome, not just because of cascading while loops. If we omit some parts of it, we can specify all possible C –style conditional loops plus we can specify the infinite loop with my favourite do{} notation. The only problem that it is a bit hard to read. And the other problem that it is something like reinventing the wheel – I’m sure that this theoretical construction is well-known in certain circles.

Posted in Theory | Tagged , , ,

Another annoying mistake (ActionScript 3.0)

Debugging is not always a torture. It is when we have to beat a deadline and when eliminating bugs from a new product is matter of life and death, but when we have enough time and we are enthusiastic enough, then every new bug is an opportunity to learn something important and useful. Mistakes are essential part of going forward, that’s why we have to enjoy it. Some esoteric masters tell that “perfection is not an end but a journey to become better” which is a bit corny but there is some truth in that. (And it remembers me of the quote “each man, one way; each horse; one stance; each church; one Buddha… each master to his own technique”.)

Today I’ve been debugged an error for hours in my current AS3 project, because I had an array that remained empty, and I didn’t know, why. Those functions, that were responsible for the construction of the content of the array, were similar to the following short function:

...

function createArrayOfPersons(n: int) : Array {
  var retval : Array = new Array();
  for (var iii : int = 0; iii < n; iii++) {
    retval.push(new Array());
    Array(retval[iii]).push("John Doe");
    Array(retval[iii]).push(0);
    Array(retval[iii]).push("unknown");
  }
  return retval;
}

...

I was a bit clueless, I didn’t understand what the problem is, and then I had an epiphany. It is the well-known issue of the dangerous static cast that can be problematic also in C++. Static cast tend to create new, temporary objects, so if you perform operations on the result of a static cast, then you typically change just a temporary copy and the original object doesn’t change at all.

I don’t know, why, but I always try to be as clear as possible when I’m coding, and I like to write more when it helps to express my ideas in a more clear way. For example, in C++, when I create a new object, I prefer the style Something s1 = Something(10); instead of Something s1(10);. (Both of them call the same conversion constructor, but 1.) the longer version is easier to understand 2.) it helps to avoid the issue with the Something s1();, because Something s1 = Something(); works well. The longer and shorter style do the same thing even if we call the copy constructor in these ways.) I tend to be a big mouth, but being a big mouth is not always good, the problem of static cast shows that.

One can note, that the code above is pretty ugly. When we use two functions and we don’t write to write everything in one function, then the whole issue disappear:

...

function createNewRecordOfPerson() : Array {
  var retval : Array = new Array();
  retval.push("John Doe");
  retval.push(0);
  retval.push("unknown");
  return retval;
}

function createArrayOfPersons(n: int) : Array {
  var retval : Array = new Array();
  for (var iii : int = 0; iii < n; iii++)
    retval.push(createNewRecordOfPerson());
  return retval;
}

...

In this case, the compiler always knows the exact type of the modified object. That’s why they say that good coding style helps to avoid problems, but of course it cannot replace thinking.

Posted in AS3 | Tagged , , ,

Approaches to optimize a small program (C++)

Imagine we have to work on the following problem (because it is our new assignment, our boss is obsessed with this problem, etc.):

We have a text file that’s a few hundred megabytes long. We knows that this text contains the word ‘fiona’ somewhere (its letters are written in lowercase letters), and we want to find its first occurrence in the text file. Suppose the text data is already loaded into the memory (because it is a part of a bigger system, that helps bad novelists to write better books) and all we need is a small C++ function that performs the search and returns the position of the fiona’s f. We need a fast and efficient solution. (Why? Our bigger system uses very much large text files, it loads brand new text files continiuously into the memory and we cannot control the creation of these text files because it belongs to an other system. But we want to replace every instance of the word ‘fiona’ with ‘agnes’, because we knew a Fiona once who had a really bad habit and we knew an Agnes who was a really nice girl. When the subroutine is fast enough, no one will know about our dirty little secrets.)

The easiest solution is really easy, every junior C++ programmer of the world (includes me) can code it in 10 minutes, check the following code:

/* ==== version 1 ==== the simple solution ==== */

inline bool match5( const char* big, const char* small )
{
  for ( int iii = 0; iii < 5; iii++ ) {
    if ( *(big + iii) != *(small + iii) )
       return false;
  }
  return true;
}

int find1( const char* big, const char* small, const int bound ) {
  for ( int iii = 0; iii < bound; iii++ ) {
    if ( match5(big + iii, small) ) return iii;
  }
}

...
int main() {
  ...
  find1(test, "fiona", 200000000);
  ...
}

(Note: It is the Boyer–Moore string search algorithm, so I’ve reinvented the wheel, but it is something like 2+2=4, so it doesn’t take much effort to reinvent it.) The function strstr is avaliable in <cstring>, however, it doesn’t work, the good old C function is not ready to process hundred of megabytes. But its re-implementation is simple and nice. The only question is: is there a faster and better algorithm, can we optimize this code? If we don’t like thinking we just take one of these optimization guides and we find out soon that we can optimize this code, for example, using short for loops is never efficient. So we rewrite this code and we get the second version:

/* ==== version 2 ==== traditional optimization ==== */

inline bool match5fast( const char* big, const char* small)
{
  if ( *big != *small )
    return false;
  if ( *(big + 1) != *(small + 1) )
    return false;
  if ( *(big + 2) != *(small + 2) )
    return false;
  if ( *(big + 3) != *(small + 3) )
    return false;
  if ( *(big + 4) != *(small + 4) )
    return false;
  return true;
}

int find2( const char* big, const char* small, const int bound ) {
  for ( int iii = 0; iii < bound; iii++ ) {
    if ( match5fast(big + iii, small) ) return iii;
  }
}

...
int main() {
  ...
  find2(test, "fiona", 200000000);
  ...
}

If we knew more about template metaprogramming, we could write this code in a more elegant way (using recursion), however, let the gentle reader imagine the situation of a junior programmer. If we follow the advice of Pete Isensee’s guide and we “measure, measure and measure” we will see that the second version is approximately 30 percent faster than the first version. It is cool. Could it be even faster? Of course we could use other good advices to rewrite some control structures in the code without the modification of the underlying algorithm. But suppose, we reached the point when this kind of optimizations is not helpful anymore. (It is not true, but please, suppose it.) Could we maybe improve the algorithm?

Maybe we could. The basic idea, that the algorithm, that we’ve used, is just too general. It works for such words like “ababa” or “retret” or “bbbbbbb” (which consist the same, repeated part), but we don’t really need this feature. The letters of ‘fiona’ are unique. We can use this fact, because it has important consequences.

  1. We don’t need always to read each letter of the text file. Suppose, we read the letter ‘e’ somewhere in the text file at the position x. What does it mean? It means that the fiona’s first f cannot be at x, but it cannot be also at the positions (x-4), (x-3), (x-2), (x-1). Why? Examine the figure below:
    fiona1When we find an ‘e’ at the position x, we know that the word ‘fiona’ cannot start at the position (x-2), because in this case, we would see ‘o’ instead of ‘e’ at the position x.
  2. If we find a letter of ‘fiona’ somewhere in the text, there is only one possible starting position that belongs to this letter. For example, if we find an ‘i’ at the position y, then there is only one possible starting position to the corresponding fiona: (y-1).

If we use these observations, we can construct a more intelligent algorithm to solve our problem, and it leads to the third version of the program. Here is its source code:

/* ==== version 3 ==== using better algorithm ==== */

inline bool isLetterOfFiona( char chr ) {
 switch ( chr ) {
   case 'f':
   case 'i':
   case 'o':
   case 'n':
   case 'a':
     return true;
   default:
     return false;
 }
}

inline char relativeDistanceOfFionasEnding( const char chr ) {
  switch ( chr ) {
    case 'f': return 4;
    case 'i': return 3;
    case 'o': return 2;
    case 'n': return 1;
    case 'a': return 0;
    default : exit(-1);
  }
}

int find3( const char* big, const int bound ) {
  for (int iii = 0; iii < bound; ) {
    char letter = *(big + iii + 4);
    if ( isLetterOfFiona( letter ) ) {
      char pl = relativeDistanceOfFionasEnding( letter );
      int jjj = iii + pl;
      if ( match5fast(big + jjj, "fiona") )
        return jjj;
      else
        iii += pl;
    }
    iii += 5;
  }
}

...
int main() {
  ...
  find3(test, 200000000);
  ...
}

If we compare the speed of the second and third versions, we will experience that the third version is also 30 percent faster than the second version, so it is about 70 percent faster than the first version. Is it beautiful? In one hand, it is, we wanted to have some speed-up and we’ve done it, yippee ki-ay. In other hand, the last algorithm isn’t flexible anymore. The algorithm of the first version was (more or less) a general algorithm, the second algorithm is more specific and the third algorithm is a very specifical one, if you want to search an other word like ‘rosalinda’, you have to rewrite almost the whole program. Of course even the first version is not a totally general solution because it uses the function match5(), but I’m sure you feel that it is much much more general than the third version.

So, the third version is 70 percent faster than the first, but it wasn’t enough to me. I still wanted to make it faster and I’ve been thought for days how could I still optimize it. I couldn’t sleep. I couldn’t eat. And after than, all of sudden, I had a brand new idea: if the compiler uses five ifs (or compares/jumps) to code the function isLetterOfFiona(), maybe I could write instead of this switch-case something more cool. I’ve implemented the following function:

/* ==== version 4 ==== almost identical to the version 3, but it uses a different isLetterOfFiona() function ==== */

...
inline bool isLetterOfFionaUltrafast( unsigned char chr ) {
  chr ^= 0x60;
  return ( chr < 16? (0xc242 >> chr) & 1 : false );
}
...

I was so proud, because it is so cool. Do you like it? There is a simple idea behind it, we use a lookup table, and we don’t store this lookup table in an array, we code it into just one single unsigned short integer. We can do it, because our table contains in this case less or equal than sixteen boolean values. (Note: We could write it into a more general version with subtraction and 32 bit integers, because there are only 26 lower-case letters in the English alphabet.) I was especially proud because I invented my own magic number which is related to fiona. There is only one small problem: the fourth version is slower than the third, and it spoiled my day. A quick benchmarking showed that it is about 2% slower than the third version. What does it mean? First, the compiler generates a small and nice lookup table automatically, and second, it is more efficient than my version.

Optimization is like motorsport, it is hard to quit at the top, and overdoing optimization is a quite dangerous. The resulting code can be less general, more specific, it is likely harder to maintain and there is no guarantee that our great ideas lead to a better version, only benchmarking can decide whether an idea is useful or not. But the greatest danger is wasting time, optimization can be a great temptation, we have to learn to resist.

***

Small remarks about benchmarking. Because I wanted to compare the speeds of the different versions, I’ve used a subroutine that generates random English letters and the distribution of the generated letters is corresponding to English letter frequency. With this function I’ve created 200 megabytes long text inputs, I’ve removed the occurrences  of ‘fiona’ from it and I’ve placed the word ‘fiona’ at the end. I believe this method produces such text inputs that behaves very similar like real English texts.

double frequency[25] =
{0.08167,
 0.01492,
 ...};

inline char randLetter() {
  double rv = rand() * 1.0 / RAND_MAX;
  char act = 'a';
  double sum = frequency[0];
  while ( act < 'z' && sum < rv ) {
    act++;
    sum += frequency[ act - 'a' ];
  }
  return act;
}

(If you want to know, why we don’t like Fiona, please, watch the movie EuroTrip and/or listen the song Scotty doesn’t know.)

Posted in C++ | Tagged , , , , , , ,

My five most common programming mistakes in C++

I’m a junior programmer. Junior means I don’t have industrial experience, sad, but coding at home and working at a company are entirely different things. Strict deadlines, teamwork with a lots of smart guys, really big source codes and the experience that the small and smart modifications (in other words, the smartness and thinking) can be more valuable than bare coding and reinventing the wheel – I guarantee you won’t experience these things if you are just sitting at home. “Being an amateur at means I can be comfortable. It’s safe. There is no fear of success or failure … Being an amateur is the opposite of going pro.” (I quoted from here.) I’m a junior programmer and junior means I started to acquire the skills that distinguish an amateur and a professional programmer.

But these skills are not about programming basically. If you will be a professional programmer, you will be a more effective programmer but you won’t be a smarter programmer. You will learn to use the things that you know and that you own in a more effective way but you won’t know more about the programming. Likely you cannot practice things you don’t know at all so learning is inevitable. Reading, thinking, talking, debating – these things come always before the practice.

I’ve read an article about common C++ mistakes (you’ll find this article here), and I was a bit surprised, because I notice the most of the mistakes of the article in the most of cases and I don’t notice many other things. For example, it is pretty hard to forget the initialization of variables after some Java coding (Java does not have uninitialized variables), by the way, initialization lists in C++ are lot more fun. I like them because they make possible to perform the base class initialization and variable initialization in the same way and it is so beautiful. (The compulsory definitions of the declared static class variables make the initialization more unforgottable.) Integer division, the operator ==, the myFunction(x, x++, x--) bug (read here about it), lazy evaluation and breaks in switch-case statements aren’t C++ issues, they can be problematic in pure C too, so if you aren’t sure how to use them, all you need is some C practice. And then, when you are coding a C-like function, you just have to use your C knowledges.

No, my C++ mistakes are more typical and more painful. When I get a weird C++ compile-time error, I follow the checklist below to see whether it is a trivial error (oops, I did it again), or not.

  1. Using g++. I’m not very proud of it, but I frequently try to compile my C++ programs with gcc. I don’t know, why. I like to think that I’m absent-minded, evil people like to think that I’m an idiot, only the god knows the truth. Interesting, but it isn’t easy to see in the dump of the gcc that the problem is the wrong compiler, so in one hand, when I have an incomprehensible dumb, then it is my first idea to fix the error. In other hand, that’s why I always create a Makefile (even to the simplest projects), and it is a good programming practice. Writing a Makefile doesn’t take much effort, it makes the whole build trivial and it helps to avoid the first mistake of my checklist. (Of course if you are using Visual C++, it is not an issue. But why are you using Visual C++?)
  2. The semicolon at the end of the class definition. I forget it frequently. Then the g++ inserts my header files into other files and it process the start of the other file as the declarator part of the wrong class definition. (I wrote an article about declarators, do you remember?) Short and sweet, the compiler will show a non-existing error in an irrelevant file and it won’t show the real error in the relevant header file. It is very annoying, and I check the semicolons at the end of my class definitions twice because it makes me always angry.
  3. Public and private inheritance. Likely it is the side effect of  Java and ActionScript 3.0 programming, but I forget the the keyword public and private after the colon again and again. I don’t like this mistake, because it makes me look like a world-class idiot. Why? Because thinking people always know, what they want, ISA relationship (== public inheritance) or the reusing codes of other classes without ISA restriction (== private inheritance). If the ISA issue doesn’t matter you at all, it shows that you aren’t thinking at all and it always causes problems.
  4. The public and private keywords in class definitions. When I’m coding in Java or in ActionScript 3.0, I always write explicitly whether a member is private or public. In C++, it is not possible, so I have to give some attention to the structure of the class definition and to the placing of the private: and public: separators. It is good, because it forces me to order my class members (public and private members won’t be mixed) and my class definitions will be more manageable. And it is bad, because sometimes I forget these separators. It is an other very stupid mistake (a noob error), that’s why it is so painful.
  5. The MyClass class(); misdeclaration and similar misdeclarations. I give much attention to avoid this mistake, but once I did frequently. It is a very famous C++ design issue, variable declaration and function declaration are so similar in C++, that it can cause disambiguation. Of course not to the compiler (it compiles the code always in one way, in the way of the language specification or in its own way), but to the programmer. MyClass myName(); seems like a variable declaration but it is the forward declaration of a function and that’s what I call disambiguation. In the most simple cases, it is easy to avoid this mistake. But there are some rare complicated cases, so alertness is encouraged. I recommend you the book More effective STL, especially the Item 6 (because it deals this mistake).

So, these are my mistakes. I’m not perfect and bulletproof, gentle reader, and those articles like this help me to face my mistakes and to learn from my mistakes. And I think it is a good way to show what kind of people I am. I find it a bit funny when people write a personal blog about their favourite films and foods to show themself – these things seem so irrelevant to me. Just the things that you do (well or badly) show your true colors.

Posted in C++ | Tagged , , , ,