Click here to Skip to main content
15,867,141 members
Articles / Multimedia / GDI+

2D "Nim" Game Development and Animation in C# (Part 2)

Rate me:
Please Sign up or sign in to vote.
5.00/5 (25 votes)
16 Aug 2007CPOL5 min read 66.1K   2.1K   49   11
Part 2 in a series of articles on a two-player mathematical game of strategy

  

Screenshot - blue_pencil_step.jpg

After the player has chosen some blue pencils (by means of a rubber rectangle).

Screenshot - red_pencil_step.jpg

Further, the program paints in red color some pencils and remove them from one heap.

Introduction

What is the Nim Game

Nim is a two-player mathematical game of strategy in which players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap.

Variants of Nim have been played since ancient times. The game is said to have originated in China (it closely resembles the Chinese game of "Jianshizi", or "picking stones"), but the origin is uncertain; the earliest European references to Nim are from the beginning of the 16th century.

Its current name was coined by Charles L. Bouton of Harvard University who also developed the complete theory of the game in 1901, but the origins of the name were never fully explained. The name is probably derived from German nimm! meaning "take!", or the obsolete English verb nim of the same meaning. Some people have noted that turning the word NIM upside-down and backwards results in WIN.

Nim is usually played as a misere game, in which the player to take the last object loses. Nim can also be played as a normal play game, which means that the person who makes the last move (i.e., who takes the last object) wins. This is called normal play because most games follow this convention, even though Nim usually does not.

XOR Tricks for Win at Nim

Although it takes some high-level math to find the secret strategy of Nim, employing that strategy really only requires an understanding of binary numbers.

In order to win at Nim, you have to know how to use the binary operation XOR, which stands for "exclusive or". What XOR really means is "x XOR y = 1 if either x or y is 1, but not if they are both 1." So, 0 XOR 0 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, and 1 XOR 1 = 0. Or, more simply, the result of the XOR operation is 0 if both arguments are the same and 1 if the arguments are different.

For any given situation in Nim, there is a number which determines whether or not that situation is a losing one. To find that number, you have to perform the XOR operation on the number of objects in each row successively. For example, the position is:

Screenshot - nim.jpg

So to see if this is a losing position, we have to XOR the number of objects in each row, as follows:

1 XOR 3 XOR 5 

which when shown in binary is:

001 XOR 011 XOR 101

Now we have to XOR each digit in each number and put each result below the column for that digit. Let's start with the rightmost digits.

1 XOR 1 XOR 1   is the same as   (1 XOR 1) XOR 1

1 XOR 1 = 0, and 0 XOR 1 = 1. So 1 XOR 1 XOR 1 = 1.

Now continue with the rest of the columns until we have a new binary number.

001 XOR 011 XOR 101 = 111 

If all the digits of this final number are zero, the position is a losing position!!!!!!! If it's your turn and the position is a losing position, you're in trouble. However, in this example, the number is non-zero, so we can turn the position into a losing position for our opponent.

Let's take the number 111 that we got from XORing the rows and try to find a row which, when XORed with 111, gives us a lower number than the row previously had. Well, we know if we do 001 XOR 111 it will be greater than 1, and 011 XOR 111 will be greater than 3, so we must do 101 XOR 111, which is 010, or in decimal 2, and is less than 5. So in order to give your opponent a losing position, you just have to remove 3 objects from the row of 5, leaving 2.

Summary

The steps needed to win are:

  1. When it is your turn, convert the number of objects in each row into binary numbers and XOR them.
  2. If the resulting number is 0, there's not much you can do to win. If it isn't 0, XOR it with a row and make a move so as to leave that many objects in that row.

For more information about Mathematical theory of game, see the Wikipedia article.

Using the Code

The following code demonstrates how to create a Form. Let us draw something on a Form's Client Area.

  • The following code illustrates the process of dynamic creation and initialization of these heaps of pencils. For save and display images, we use Jagged array:
    C#
    private Bitmap[][] images;   // Bitmap Jagged Arrays
      /**************************************************************************/
     /* The method creates a matrix in the size 7 on 30 for the pencils        */ 
    /**************************************************************************/
    void CreateNew_Images()
    {
        //Allocation of memory for array bitmap
        images = new Bitmap[8][];
    
        for(int i=0; i<8; i++)
        {
          images[i] = new Bitmap [30];
    
          for(int j=0; j<30; j++)
          {
                   images[i][j]= new Bitmap(tempImage); //Load empty image
                   images[i][j].MakeTransparent();      //Without background
          }
        }
     } 
      /****************************************************************** ******/
     /* The method fills the matrix with gray pencils                         */
    /*************************************************************************/
    void Fill_Images()
    {
        int new_number_elements;
        Random rdm;
    
        for(int i=0; i < numberOfColumns; i++)
        {
            rdm =
                newRandom(unchecked((int)DateTime.Now.Ticks)); 
                new_number_elements =  rdm.Next(1,30);
            SumOfImages+ =  
                new_number_elements;   for(int
                j=
                0;j <  new_number_elements; j++)
            {
                images[i][j]= bitmapGray;
                images[i][j].MakeTransparent(); //Without background
            }
            numberLoadImages.SetValue(new_number_elements,i);
            System.Threading.Thread.Sleep(35);
        }
        Invalidate();
    }
  • Overriding appropriate method

    The OnPaint method for a form or a control is called by the operating system whenever part or all of that form or control is obscured by another form or control and needs to be redrawn. A Graphics object is passed as part of the PaintEventArgs parameter to the OnPaint method. Using this Graphics object, you redraw the portion of the display that has been obscured.
    Why OnPaint method? The main reason is we can get Graphics object easily in OnPaint method. In this method, I draw objects rotation after mouse click.

    C#
          /*********************************************************************/
         /* The OnPaint method also allows derived classes to handle the event*/
        /* without attaching a delegate. This is the preferred technique for */
       /* handling the event in a derived class                             */ 
      /* One of the most responsible functions in this program!!!!         */
     /* This function re-draw the image on the main form !!               */
    /*********************************************************************/
    protected override void OnPaint(PaintEventArgs e) 
    {
        bool flag=false;
        //Output image for background
        e.Graphics.DrawImageUnscaled(PictureBitmap, 0, 0);
        //Output a sharper
        if(flag_colors==ColorsPen.Blue)
        {    
            //Output Blue Sharper
            bitmapBlueSharper.MakeTransparent(Color.White);
            e.Graphics.DrawImage(bitmapBlueSharper,((int)Xposition.GetValue(
                current_column)),0);
        }
        else if(flag_colors==ColorsPen.Red)
        {
            bitmapRedSharper.MakeTransparent(Color.White);
            e.Graphics.DrawImage(bitmapRedSharper,((int)Xposition.GetValue(
                current_column)),0);
        }
        //Output other pencils  
        int x=-160;
    
        for(int i= 0;i<8; i++,x+=120)
        {
            int y=-18;
            for(int j= 0;j<((int)numberLoadImages.GetValue(i)); j++)
            { 
                if(i==current_column && j==current_element_in_column)
                //if found pen for rotate   
                {    
                    flag=true;                        
                }
                else
                {
                    if(i== current_column &&j>current_element_in_column)
                    {
                        images[i][j]=this.bitmapGray;
                        e.Graphics.DrawImageUnscaled(images[i][j], xCurrentTop+x, 
                            yCurrentTop+y+posDown);
                        y-=18;
                        e.Graphics.ResetTransform();
                    }
                    else
                    { 
                        e.Graphics.DrawImageUnscaled(images[i][j], 
                            xCurrentTop+x, yCurrentTop+y);
                        y-=18;
                        e.Graphics.ResetTransform();
                    }
                }
            }                    
            yCurrentTop = yPrevTop;                    
        }    
        ///  Rotate the chosen pen  //////
        if(flag)
        {
            positionY=yCurrentTop+posY+
                images[current_column][current_element_in_column].Height/2;
            //Rotate pen
            e.Graphics.TranslateTransform( xCurrentTop+posX+
            images[current_column][current_element_in_column].Width/2,positionY); 
    
            e.Graphics.RotateTransform(angle);
            e.Graphics.ScaleTransform(1,(float) delta);
    
            images[current_column][current_element_in_column].MakeTransparent(
                Color.White);
    
            e.Graphics.DrawImage(
                images[current_column][current_element_in_column],
                new Rectangle(-images[current_column]
                [current_element_in_column].Width,
                -images[current_column][current_element_in_column].Height,
                images[current_column][current_element_in_column].Width,
                images[current_column][current_element_in_column].Height));
    
            //again output  sharper (Red/Blue)
            e.Graphics.ResetTransform();
            bitmapBlueSharper.MakeTransparent(Color.White);
            if(flag_colors==ColorsPen.Blue)
                e.Graphics.DrawImage(this.bitmapBlueSharper,
                    ((int)Xposition.GetValue(current_column)),0);
            else if(flag_colors==ColorsPen.Red )
                e.Graphics.DrawImage(this.bitmapRedSharper,
                    ((int)Xposition.GetValue(current_column)),0);
        }
        //When overriding OnPaint in a derived class, be sure to call the base 
        //class's 
        //OnPaint method so that registered delegates receive the event.
        base.OnPaint(e);        
    }
  • Also, I want to explain how to draw a rubber band rectangle.

    Screenshot - rubber_rect.jpg

    Rubber rectangle is a Grouping object.

    Group uses rubber band to collect a set of objects (pencils).
    In other words, the pencil objects are completely independent of one another (rubber rectangle can always be ungrouped - each member maintains almost complete autonomy from the other members of its group).

    Figure on the left includes a set of grouped objects (pencils);

A rubber rectangle technique is commonly used to delimit a selection in response to user mouse-pointer input. This term is used to describe the situation where:

  1. the left mouse button is held down, defining one corner of the rectangle
  2. the mouse is dragged and released at the point defining the opposite corner
    of the rectangle
  3. the rectangle is drawn while the mouse is being dragged, so that it looks like the
    rectangle is being stretched and contracted, like a rubber band

For more information about Rubber rectangle, visit MSDN at Microsoft here.

The following sample code demonstrates how to use the rubber rectangle:

C#
    /**********************************************************************/
   /*The method takes the p1 and p2 coordinates of the starting and      */
  /*ending points  converts and normalizes the points and draws the     */ 
 /*rubber rectangle                                                    */ 
/**********************************************************************/    
private void MyDrawReversibleRectangle( Point p1, Point p2 )
{
    // Convert the points to screen coordinates.
    p1 = PointToScreen( p1 );
    p2 = PointToScreen( p2 );

    Rectangle rc = new Rectangle(p1.X, p1.Y, p2.X - p1.X, p2.Y - p1.Y);
    // Draw the reversible frame.
    ControlPaint.DrawReversibleFrame( rc, Color.Black, FrameStyle.Thick );
}          
  /**********************************************************************/
 /* Event of moving the mouse-device                                   */ 
/**********************************************************************/
private void Form1_MouseMove(object sender, 
    System.Windows.Forms.MouseEventArgs e)
{
    if(this.timer1.Enabled==true || this.timer2.Enabled==true)
        return;
    //  called when the mouse is moved                  
    if( rubber_rect_flag ) // if it is required to draw rubber rectangle 
    {
        MyDrawReversibleRectangle( FirstPoint, SecondPoint );
        // Update last point.
        SecondPoint = new Point(e.X,e.Y); 
        MyDrawReversibleRectangle( FirstPoint, SecondPoint );
    }
}

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer
Canada Canada
Mr.Volynsky Alex is a Software Engineer in a leading software company. Alex is skilled in many areas of computer science. He has over 14 years of experience in the design & development of applications using C/C++/STL, Python, Qt, MFC, DirectShow, JavaScript, VBScript, Bash and of course - C#/.NET.

In addition, Alex is the active member of Intel® Developer Zone (he was awarded by Intel® Green Belt for his active contribution to the Intel Developer Zone community for developers using Intel technology).

Alex is also interested in the Objective-C development for the iPad/iPhone platforms and he is the developer of the free 15-puzzle game on the App Store.

Overall, Alex is very easy to work with. He adapts to new systems and technology while performing complete problem definition research.

His hobbies include yacht racing, photography and reading in multiple genres.
He is also fascinated by attending computer meetings in general, loves traveling, and also takes pleasure in exercising and relaxing with friends.

Visit his C++ 11 blog

Comments and Discussions

 
GeneralMy vote of 5 Pin
mk4you713-Jun-12 4:52
mk4you713-Jun-12 4:52 
GeneralRe: My vote of 5 Pin
Volynsky Alex14-Jun-12 14:56
professionalVolynsky Alex14-Jun-12 14:56 
GeneralMy vote of 5 Pin
Steph_Iv28-May-12 10:29
Steph_Iv28-May-12 10:29 
GeneralRe: My vote of 5 Pin
Volynsky Alex14-Jun-12 14:55
professionalVolynsky Alex14-Jun-12 14:55 
Thanks
ale44ko

GeneralMy vote of 5 Pin
EMogilevsky26-May-12 4:24
EMogilevsky26-May-12 4:24 
GeneralRe: My vote of 5 Pin
Volynsky Alex26-May-12 10:38
professionalVolynsky Alex26-May-12 10:38 
GeneralMy vote of 5 Pin
Gerard Forestier24-May-12 22:09
Gerard Forestier24-May-12 22:09 
GeneralRe: My vote of 5 Pin
Volynsky Alex26-May-12 10:39
professionalVolynsky Alex26-May-12 10:39 
GeneralMy vote of 5 Pin
jfriedman20-May-12 8:45
jfriedman20-May-12 8:45 
GeneralRe: My vote of 5 Pin
Volynsky Alex23-May-12 4:10
professionalVolynsky Alex23-May-12 4:10 
GeneralRe: My vote of 5 Pin
jfriedman23-May-12 4:17
jfriedman23-May-12 4:17 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.