Introduction:

Pac-Man  is an arcade game developed by Namco and licensed for distribution in the United States by Midway, in October 1980 and first released in Japan on May 22, 1980. Immensely popular from its original release to the present day, Pac-Man is considered one of the classics of the medium, virtually synonymous with video games, and an icon of 1980s popular culture Upon its release.

This article describes and explains a near replica of the classic pacman game, throughout the article different code sections are explained and the whole source code alongwith the executable is provided at the end of the article. The Code is written in Visual Studio 2012 using .Net 4.5 Framework. In order to compile and execute, the .Net Runtime 4.5 is required.

Basic WorkFlow Abstraction:

The Flow control undergoes a complex path during the execution of the game. but we’ll be looking at it in abstract way.

1) Present The Menu.
    1.1) Load the Desired Map or Saved Game.
    1.2) Load the Sprites and other files.
    1.3) Build the game environment.
    1.4) Play Intro music.
2) Start the Timer
    2.1) Move the Pacman according to user input.
    2.2) Move the Ghosts.
    2.3) Check for collisions between the character types.
    2.4) check for game over events.
3) Timer Call starts again and control jumps to location 2.

Obviously we have tried to keep it to the minimum detail, but don’t panic, the rest of the article presents all the nitty grifty details about the program.

Diving Right Into The Code:
When the game starts, the background of the menu is animated. It actually is the game engine running and the characters move around randomly in the default map. the area of map and the characters have a light grey overlay. The method responcible for this is InitializeIdleScreen.

public void InitializeIdleScreen()
{
    this.IntroPlaying = false;
    this.SpriteShifter.Enabled = false;
    this.IntroMusicTimer.Enabled = false;
    this.FruitPlacementTimer.Enabled = false;
    Program.OverLayEnabled = true;
    LoadMapToArray("defaultmap.map");
    InitializeCharacters();
    ReallocateAllSprites();
    OverLayAllSprites();
    this.BackGroundImage = new Bitmap(640, 504);
    BackImageGfx = Graphics.FromImage(BackGroundImage);
    BuildBackGroundImage();
    this.BackgroundImage = this.BackGroundImage;
    this.Controls.Clear();
    this.Controls.Add(LogoBox);
    this.MainPanel.Enabled = true;
    this.Controls.Add(MainPanel);
    this.SoundFxPlayer.Stream = global::PACMAN.Properties.Resources.Intro;
    this.PacManMoveDelegate = new NoParaNoReturn(BlankFun);
    Red.SetPathDelegate = new NoParaNoReturn(Red.SetRandomTargetPath);
    Red.CheckCollisionDelegate = new NoParaNoReturn(this.BlankFun);
    Blue.CheckCollisionDelegate = new NoParaNoReturn(this.BlankFun);
    Pink.CheckCollisionDelegate = new NoParaNoReturn(this.BlankFun);
    Yellow.CheckCollisionDelegate = new NoParaNoReturn(this.BlankFun);
    FirstPac.ClearBackImageDelegate = new TwoIntParaNoReturn(FirstPac.ClearBackGroundImageOneBlockOverLayed);
    this.KeyPreview = false;
    if(Program.HighPerformance==true)
    FormRefreshDelegate = new NoParaNoReturn(Refresh);
    else
    FormRefreshDelegate = new NoParaNoReturn(Invalidate);
    this.Mover.Enabled = true;
}

As seen in the code, the method first does some initial work, then loads the default map into a 2D array of characters (because the ghost characters roam around in defaultmap in idle screen). then all the characters are initialized according to the map and sprites are assigned (sprites are sequences of images that show a moving or animating object). it then overlays a grey color over all the sprites. then the background image is built (the map is drawn as an image in memory rather than being re-drawn in each Paint() call. Further in the method some more initialization is done which will become clear in the upcoming sections.

The code above called a method BuildBackGroundImage, so here we take a look at what it does actually.

 public void BuildBackGroundImage()
        {
            Image PalletImg = global::PACMAN.Properties.Resources.pallet;
            Image PowerPalletImg = global::PACMAN.Properties.Resources.powerpallet;
            SolidBrush b = new SolidBrush(Color.FromArgb(0, 51, 255));
            Pen p = new Pen(b, 5);
            for (int row = 0; row < 24; row++)
            {
                for (int col = 0; col < 32; col++)
                {
                    if (ExistsInMap(row, col))
                    {
                        bool drawn = false;
                        if (ExistsInMap(row, col + 1))
                        {
                            if (ExistsInMap(row + 1, col))
                            {
                                this.BackImageGfx.DrawArc(p, (20 * col) + 7, (20 * row) + 5, 15, 25, 180, 100);
                                drawn = true;
                            }
                            if (ExistsInMap(row - 1, col))
                            {
                                this.BackImageGfx.DrawArc(p, (20 * col) + 7, (20 * row) - 20, 25, 25, 90, 90);
                                drawn = true;
                            }
                        }
                        else if (ExistsInMap(row, col - 1))
                        {
                            if (ExistsInMap(row + 1, col))
                            {
                                this.BackImageGfx.DrawArc(p, (20 * col) - 8, (20 * row) + 5, 15, 22, 270, 100);
                                drawn = true;
                            }
                            if (ExistsInMap(row - 1, col))
                            {
                                this.BackImageGfx.DrawArc(p, (20 * col) - 18, (20 * row) - 20, 25, 25, 360, 90);
                                drawn = true;
                            }
                        }
                        if (!drawn)
                        {
                            if (ExistsInMap(row, col + 1) || ExistsInMap(row, col - 1))
                                this.BackImageGfx.DrawLine(p, 20 * col - 4, (20 * row) + 5, (20 * col) + 20, (20 * row) + 5);
                            else if (ExistsInMap(row + 1, col) || ExistsInMap(row - 1, col))
                                this.BackImageGfx.DrawLine(p, (20 * col) + 7, (20 * row) - 7, (20 * col) + 7, (20 * row) + 18);
                        }
                    }
                    else if (Map[row, col] == '|')
                    {
                        p.Brush = new SolidBrush(Color.FromArgb(255, 189, 228));
                        if (Map[row, col - 1] == '|' || Map[row, col + 1] == '|')
                            BackImageGfx.DrawLine(p, 20 * col - 4, (20 * row) + 5, (20 * col) + 20, (20 * row) + 5);
                        else if (Map[row + 1, col] == '|' || Map[row - 1, col] == '|')
                            BackImageGfx.DrawLine(p, (20 * col) + 7, (20 * row) - 7, (20 * col) + 7, (20 * row) + 18);
                        p.Brush = b;
                    }
                    else if (Map[row, col] == ' ')
                        BackImageGfx.DrawImage(PalletImg, new Point((20 * col) - 5, (20 * row) - 6));
                    else if (Map[row, col] == 'V')
                        BackImageGfx.DrawImage(PowerPalletImg, new Point((20 * col) - 5, (20 * row) - 6));
                }
            }
            if(Program.OverLayEnabled==true)
            BackImageGfx.FillRectangle(new SolidBrush(OverLayColor), new Rectangle(new Point(0, 0), BackGroundImage.Size));
        }

The method basically reads the map from the 2D array of characters and draws accordingly to a Bitmap. That Bitmap is used in game as the background image. Another way to do this could have been to put all these lines of code in the Paint() event. but that would have eaten up a major chunk of performance. (Drawing an image to screen takes lesser performace than evaluating 1900+ conditions and drawing to screen).

The constructor of the GameForm class does some basic initialization job and is not explained in this article, but these three lines from the constructor worth mentioning them.

            SetStyle(ControlStyles.UserPaint, true);
            SetStyle(ControlStyles.AllPaintingInWmPaint, true);
            SetStyle(ControlStyles.DoubleBuffer, true);

These lines of code actually enable Double Buffering. Double Buffering is necessary for games that require smooth visual experience. Moving something on the screen requires first clearing it and then reprinting it on the new location, between the process there comes a moment when the screen is blank, which is commonly reffered to as flicker, Double buffering tries to solve the issue by managing two video memory locations, The display device reads the data from one location while the program draws to other, when the drawing process is complete the display device is directed to read from the second location. and vice versa.

Another important method is the FindPath method that helps Ghosts find their path to their destination.

public static List FindPath(Point StartPoint, Point DestinationPoint)
       {
           BlockMap = new BlockOnMap[24, 32];
           BlockOnMap StartBlock = new BlockOnMap(StartPoint, null, BlockStatus.Open, 0, 0);
           BlockOnMap DestinationBlock; 
           BlockOnMap SelectedBlock = StartBlock;
           List SelectedPath = new List();
           ///////////Initialize Block Map//////////////
           for (int row = 0; row < 24; row++)
               for (int col = 0; col < 32; col++)
                   BlockMap[row, col] = new BlockOnMap(new Point(col, row), null, Program.GameWindow.Map[row, col] == '#' ? BlockStatus.Wall : Program.GameWindow.Map[row, col] == '|' ? BlockStatus.Wall : BlockStatus.Unexplored, 0, 0);
           BlockMap[StartPoint.Y, StartPoint.X] = StartBlock;
           DestinationBlock = BlockMap[DestinationPoint.Y, DestinationPoint.X];
           ////////////////////////////////////////////
           while (true)
           {
               SelectedBlock.Status=BlockStatus.Closed;
               if (DestinationBlock.Status==BlockStatus.Closed)
                   break;
               List SurroundingBlocks=GetSurrounding(SelectedBlock);
               foreach(BlockOnMap adjacentblock in SurroundingBlocks)
               {
                   if (adjacentblock.Status == BlockStatus.Open)
                   {
                       if (adjacentblock.G+1 < SelectedBlock.G)
                       {
                           SelectedBlock.Parent = adjacentblock;
                            SetFGH(SelectedBlock, DestinationBlock);
                       }
                   }
                   else
                   {
                       adjacentblock.Status = BlockStatus.Open;
                       adjacentblock.Parent = SelectedBlock;
                       SetFGH(adjacentblock, DestinationBlock);
                   }
               }
               SurroundingBlocks = (from n in SurroundingBlocks where n.Status == BlockStatus.Open orderby n.F select n).ToList()/*[0]*/;
                   if (SurroundingBlocks.Count == 0)
                       break;
                   else
                       SelectedBlock = SurroundingBlocks[0];

           }
           BlockOnMap pathblock = DestinationBlock;
           while (pathblock != null)
           {
               SelectedPath.Add(pathblock.LocationOnActualMap);
               pathblock = pathblock.Parent;
           }
           return SelectedPath;
       }

The method takes 2 points as paramters and uses the A* Search Algorithm to find the shortest (in most cases) path from StartPoint to EndPoint. Not All gohsts chase pacman, only the Red ghost actually chases pacman, rest of them just travel to random locations in map.

Conclusion:

The article described the important parts of source code, the whole of it could take days to write (and possibly exceed the max length of the post set by the admin of blog). The game is developed using GDI+, which wasn’t really meant for games. so the game eats up a major chunk of CPU time.

the source code can be downloaded from here while the game executable can be downloaded from here.

Introduction:

            This article describes and explains a simple program that animates bar-like objects inside a console window. The whole program works in simple text mode (we’ll be dealing with characters, not pixels directly). The visualization is purely random and will not show any synchrony to the music being played in the background (if any). Although there will be multiple objects being animated on the screen at the same time, the program is not multithreaded and it just gives an illusion of actually animating multiple objects at the same time. Source code is written in Visual C++ 2012 so it will not compile in some other compilers without some minor modifications.

Workflow Abstraction:

           Let’s look at how the control flows throughout the program, we’ll be looking at the actions rather than code directly.

1) Start Main Procedure.
   1.1) Initialize array of Bar(s).
   1.2) Initialize Screen.
   1.3) Enter a loop Terminated by keypress only.
      1.3.1) Manipulate all the Bar objects and update the screen.
      1.3.2) Freeze the program (Sleep) for ~60 Milliseconds.
      1.3.3) Jump back to 1.3.1.

the loop at 1.3 scans for a keypress in each iteration. when found one, it terminates the loop which in turn causes the program to terminate because there are no further instructions to be executed.

Diving into the Code:

Major part of the source code is dominated by the Bar class.  The Bar Class has some properties and methods as listed below. The only user-defined data type other than Bar class is the behave enum.

Let’s start by looking at the Constructor of Bar class

bar ()
{
      bar_height_limit=5;
      max_height=4+rand()%(bar_height_limit-1);
      barpos=1;
      upperbar_limit=3;
      upperbar_pos=barpos+1;
      upperbar_max_height=max_height+upperbar_limit;
}

As obvious from the code above, the max height a bar can achieve is set to 5 blocks (A block on console is typically a 8×10 block of pixels). the second statement inside the constructor sets a random height greater or equal to 4. the current printing position is set to 1. the max height of the upper bar (represented by a “=”) from the top of the lower bar (white bar) is set to 3. the position of the upper bar is set on top of the lower bar.  and the last line is quite obvious.

An Important method of the Bar class is the Print method.

void print_bar ()
{
   oldx=wherex();
   oldy=wherey();
   set_behaviour();
       if (behaviour==up)
	   printup();
       else if(behaviour==down)
	   printdown();
   print_upperbar();
   gotoxy(oldx+2,oldy);
}

Print method manipulates only one block of bar in each call. the procedure involves either printing a new block over the top of bar or removing a block from the top. during the procedure the position of the cursor (text cursor) is manipluated to print at specific locations. Three user-defined methods are called in print method, those are explained below.

let’s look at the wherex method

int wherex()
{
	CONSOLE_SCREEN_BUFFER_INFO SBInfo;
	GetConsoleScreenBufferInfo(consolehandle, &SBInfo);
	return SBInfo.dwCursorPosition.X;
}

the method declares a variable for the struct CONSOLE_SCREEN_BUFFER_INFO, calls the library method that gathers the information about console screen buffer. the wherex method returns the X property of the current location of the text cursor in the console.

the wherey method does the same the only exception is that it returns the Y property of the  location of the text cursor in the console.

the gotoxy method plays an important role in the program.

void gotoxy(int x,int y)
{
	_COORD cord= {x,y};
	SetConsoleCursorPosition ( consolehandle, cord );
}

the method declares a variable for struct _COORD and initializes it using the values from the parameters. then it passes the variable to the SetConsoleCursorPosition method from the library.

THE MAIN METHOD:

let’s look right into the code!

int _tmain(int argc, _TCHAR* argv[])
{
   consolehandle=GetStdHandle(STD_OUTPUT_HANDLE);
   srand(time(NULL));
   const int size=30;
   SetConsoleTextAttribute (consolehandle, FOREGROUND_GREEN|FOREGROUND_BLUE|FOREGROUND_RED |FOREGROUND_INTENSITY );
   CONSOLE_CURSOR_INFO cci;
   GetConsoleCursorInfo(consolehandle,&cci);
   cci.bVisible=false;
   SetConsoleCursorInfo(consolehandle,&cci);
   bar bars[size];
   gotoxy(10,20);
   for (int i=0;i<size;i++)
      cout<<(const char)(219)<<' ';
   while(!_kbhit())
    {
	gotoxy(10,20);
	for (int i=0;i<size;i++)
        	bars[i].print_bar();
        Sleep(60);
    }
   return 0;
}

The main method starts by initializing the global variable consolehandle, the handle to the console window is used throughout the program to manipulate various properties like the text color or the position of the cursos etc. the second line initializes the random number pattern which will be used by the rand method, intially the text color is set to white (using RED|GREEN|BLUE|INTENSITY flags), and important thing to notice when the program is executed is that the text cursor is not visible, that is because the main method sets the appropriate console attributes to set it to invisible.

Although only one bar is manipulated at a time, it doesn’t look so, this happens because the bars are manipulated in a fraction of second and then the program is frozen for some time, then the bars are manipulated again and frozen again, this goes on till a keypress is recieved.

Conclusion:

This tiny program does present some nice animation on the screen. it can be further tweaked to work in synchrony with the actual music. Plus this little exercise just taught you how to animate more than one objects on the screen while living in single thread.

Source Code and Executable can be downloaded by following this link.

Background:

When the idea of neural networks came in Artificial intelligence then there was need of constructing a neuron on the basis of a human brain neuron. the idea was to create an artificial neuron that will receive some data do some processing on it and then pass it on to next neuron , of course making a ditto copy of human brain neuron was not possible so some modifications were made in the main working to make it achievable.

Introduction:

Back propagation Module is software for simulating the learning of an artificial neural network. Its prime objective is to calculate the total no of iterations required for a neural network to perform learning on a specific data.

Objective:

Its prime objective is to calculate the total no of iterations required for a neural network to perform learning on a specific data.

Secondary objective is that it outputs the ideal weights that can be used in the real world problem.

Principles of BP:

   Overview:

There are three layers in the network namely initial layer, hidden layer and output layer. As their name suggests initial layer is responsible for receiving data. It initiates the learning process then the data is passed on to the hidden layer. This layer is not visible to the outer world as it has no connection to the output nor input. Then there is output layer it function is to perform final calculations and output the final result as required. The program keeps running until error value is reduced to the value of biased value or to 0 in ideal case which is impossible to achieve.

   Biased Value:

The neural network is never perfect. It’s never outputs the 100 % accurate result so we require a biased value to determine how accurate result we want. The less the value of biased value the more time network requires to train on a data. It is just like narrowing down the requirements when we are trying to determine a best option from a choice of many options.

   Weights:

Weight represent the actual data in the real world that any robot encounter as this process is specially designed for robot to learn something. There can be any no weights that can be used on any layer but for the time being the software uses 2 weights for input layer 3 for hidden and 2 for output layer.

   Input:

Input values are just like flags in microprocessors. One input can contain value 1 or 0 just like a flag can be on or off. A set of inputs in provided to system to use in its learning.

   Output:

Output value can also be 0 or 1. Output is represented by Y.

   Net Value:

Net value is used for determining error in the layer. If there are two weights and two inputs values i.e. there are two neurons then net will be calculated by formula

weight_1 * input_1 + weight_2 * input_2;

    Neuron:

A neuron is composed of two things a weight and input value.

   Threshold value:

Also called theta is used when calculating output.

Its formula is

net >= theta_threshold ? 1 : 0;

   Learning Rate:

Also called alpha is used to specify how fast or slow network train on a set of values.

   Weight Update:

A weight is updated of a layer when there is error against an input.

Implementation:

   Classes:

There are three classes representing each of one layer. Each class almost similar to other. There are only few differences in the formulas of calculation. Initial layer has no error value.

Each layer has these fields depending on the layer no of fields may differ.

double weight;

public double input{get ; set;}

double net;

one method net calculate to calculate the net value of layer

private double netcalculate()

{

return weight_1 * input_1 + weight_2 * input_2 + weight_3 * input_3;

}

Two read only properties to get output value and error value.

public double output

{

get

{

return net >= Program.theta_threshold ? 1 : 0;

}

}

public double error

{
get

{

return ((input_1 + input_2 == 2 ? 1 : 0) - output) * output * (1 - output);}}

Main Class:

Then there is a main program class that is responsible to run the network. All the calculation is done in main class.

Some values which are same for each layer are defined in main class.

Such as

public static double theta_threshold;

public static double alpha_learningrate;

public static double BiasedValue;

Putting everything together:

      Working of code:

All the process is concerned with main class.

First 7 neurons are declared

initiallayer neuron1_1 = null;

initiallayer neuron1_2 = null; 

innerlayer neuron2_1 =null;

innerlayer neuron2_2 = null;

innerlayer neuron2_3 = null;

outerlayer neuron3_1 = null;

outerlayer neuron3_2 = null;

then a open while loop is started .this loop only stops when the error in all classes is eliminated.

if (checkError()) break;

the method checkError checks that weather for all the given inputs error is eliminated or not.

static bool checkError()

{

for (int i = 0; i < 4; i++)

{

if (Errors[i])

return false;

}

return true;

}

After that weights are assigned to all neurons .

neuron1_1 = new initiallayer(0.1, x1[i]);

neuron1_2 = new initiallayer(0.3, x2[i]);

neuron2_1 = new innerlayer(0.4, 0.5, neuron1_1.output, neuron1_2.output);

neuron2_2 = new innerlayer(0.5, 0.6, neuron1_1.output, neuron1_2.output);

neuron2_3 = new innerlayer(0.3, 0.5, neuron1_1.output, neuron1_2.output);

only the weights of output layer are updated because this layer weights are going to be the final output so its weights are not initialized every time rather its weight only change when the weight update occurs.

That’s why we need this condition in the loop.

if (neuron3_1 == null || neuron3_2 == null)

{

neuron3_1 = new outerlayer(0.4, 0.5, 0.4, neuron2_1.output, neuron2_2.output, neuron2_3.output);

neuron3_2 = new outerlayer(0.6, 0.7, 0.1, neuron2_1.output, neuron2_2.output, neuron2_3.output);

}

else

{

neuron3_1.input_1 = neuron2_1.output;

neuron3_1.input_2 = neuron2_2.output;

neuron3_1.input_2 = neuron2_3.output;

 neuron3_2.input_1 = neuron2_1.output;

neuron3_2.input_2 = neuron2_2.output;

neuron3_2.input_2 = neuron2_3.output;

}

After that net calculated for each layer and its error is determined and then the output is transferred to the next layer and finally weights of output layer are updated if there is still error.

 if (neuron2_1.error(neuron3_1.error, neuron3_2.error) > BiasedValue)

weightupdate(1, neuron2_1.delta(), neuron3_1, neuron3_2);

else if (neuron2_2.error(neuron3_1.error, neuron3_2.error) > BiasedValue)

weightupdate(2, neuron2_2.delta(), neuron3_1, neuron3_2);

else if (neuron2_3.error(neuron3_1.error, neuron3_2.error) > BiasedValue)

weightupdate(3, neuron2_3.delta(), neuron3_1, neuron3_2);

If there is error then weight update is called static void weightupdate(int neuron , double delta , outerlayer neuron3_1  , outerlayer neuron3_2){switch (neuron){

case 1:

{

neuron3_1.weight_1 += delta;

neuron3_2.weight_1 += delta;

break;

}

case 2:

{

neuron3_1.weight_2 += delta;

neuron3_2.weight_2 += delta;

break;

}

case 3:

{

neuron3_1.weight_3 += delta;

neuron3_2.weight_3 += delta;

break;

}

}

}

Delta is property defined in inner layer

public double delta()

{

return   calculatederror * Program.alpha_learningrate * output ;

 } 

Calulate error method is

 public double error(double Error1 , double Error2)

{

calculatederror = ((1 - output) * output * ((weight_1 * Error1) +  (weight_2*Error2) ));

return calculatederror;

}

And in case there is no error else condition executes which puts false in respective error value

 else Errors[i] = false; 

      Errors is defined in main class

 public static bool[] Errors = {true , true ,true , true };

     and this line ensure the running of loop and iterates over input values again and again until loop breaks.

i = i == 3 ? 0 : i + 1;

Final notes on implementation

In this article only important code is described which is important in understanding the working and concept of B.P

That’s all. Thanks.

M Usman , Roll No: 008

Introduction 

This program generates and solves a maze using depth first search algorithm. It may prove quite sturdy in demonstration of depth first search algorithm for its comprehensive understanding in a graphical way.

Background

The program is written in C# using Visual Studio 2012 as a development tool. It implements pointers, recursion, and GDI+ graphics.

We will normally use the stack and queue data structures. As prompts, evoke that the stack is First-In-Last-Out (FILO), while the queue is First-In-First-Out (FIFO).

Maze Generation 

To generate a maze with DFS, we have this simple algorithm:

• Have all walls in your maze intact (not broken).
• Choose a random start point, push it into the stack. Call this initial square ‘current square’.
• Repeat while the stack is not empty:
• Get list of all neighboring squares to the current square where those neighbors have all their walls intact (unvisited).
• If there are neighbors (i.e., List.Count > 0):
• Choose one of the neighbors at random. Call it ‘temp’.
• Knock the wall between ‘temp’ and the current square.
• Push the current square into the stack.
• Make the current square equals ‘temp’.
• Else if there are no neighbors, pop a square from the stack. Make current square equal to it.

After executing this algorithm, you will have a ‘prefect maze’ which indicates that your maze doesn’t have ‘dead ends’ (i.e., unreachable squares) and has a single solution.

If the generation is with DFS, the program will choose a random wall and knock it, then it moves to the new square. When it reaches an edge (or visited cell), it backs again to the nearest “UNVISITED” square.

Solving Maze

We will now use DFS to solve the maze it created, as in the following backpedaling algorithm:

We have an empty list for the found path. Name it ‘foundPath’.

This algorithm finds the path to the maze end. When it returns true, it adds the current location to ‘foundPath’, causing all other calls in the stack to return true and add their current locations, too. At finish, we will have a complete list of squares between begin and end.

However, we won’t use those recursive versions, since they may cause a StackOverFlowException when the calls are too many for that stack. We will instead use the same algorithms but iteratively (i.e., with a loop). Instead of making every recursive call, add its ‘start’ to ‘foundPath’, and we will have a pointer to the previous one (as we will see later in the article).

For generation, DFS searches at random. When it reaches an edge, it backs to the nearest (unvisited) square and repeats the process until it finds the end.

We have a third method that traverses the maze, the right-hand rule. It considers “putting” your right hand on the wall, never leaving it. Even if this way will be longer, you’ll absolutely reach the end, or back again to the beginning if there is no end. We are sure, however, that we have a path to the end, since we are using DFS that gives perfect mazes. In the right-hand rule, we will consider only traversing the maze without finding the path.

Using the Code

The Cell Struct

We have perceived in the Background section, we need to have walls in order to generate and solve a maze. So let’s have a struct called Cell that encapsulates four boolean variables: RightWall, LeftWall, UpWall, and DownWall. At first, all the walls should be intact, so we initialize them to true. When we knock a wall, we will simply set its boolean variable to false. Cell should have a Visited boolean too, which indicates whether this cell has been visited already. Every cell should draw itself, so every cell has a Draw() method.

If we want to generate a maze of 40 by 40 squares, for example, we will need a container for them. Let’s have a two-dimensional array that carries all the cell instances, call it ‘maze’. For any cell, we have two locations: one that represents its location for the graphics, and another that represents its location in the two-dimensional array. In the previous section, we demonstrated the recursive version of the DFS solution. We stated that we won’t use the recursion. Instead of having every recursive call add its ‘start’ to foundPath, we will have a pointer in every cell to its ‘previous’ cell. A chain of these ‘previous’ pointers will form the complete path. So before we push the ‘temp’ (which indicates the next neighbor of ‘start’ to be visited) to the stack, we set its ‘previous’ pointer to ‘start’.

The Maze Class

We have a class Maze that encapsulates the 2D array maze (of Cell instances). For the array, we represent it as Height x Width, not the reverse. So when we have a position Point of x and y coordinates, we access the array as maze[position.Y, position.X]. We take its maximum width and height in the constructor and reverse the array. Yet we can use any smaller width and height the user selects. This makes more sense because the repeated reserve\release operations are bad in terms of performance. Maze has a method Draw which draws every cell (in the bounds the user selects).

In the method iterativeDepthFirstSearchSolve, we use pointers to refer to the previous cell in the foundPath. To enable pointers usage, those methods must be marked as “unsafe”. The .NET Common Language Runtime usually moves objects from one place to another while the program runs. However, if we want to refer to an object with a pointer, that object must be “fixed” in its place so the pointer can always point to it correctly. Therefore we use the syntax:

to set the previous pointer of “next” to point to “start”.

To use pointers, we must tell the compiler about it. By going to the Properties window in Visual Studio (form Solution Explorer) > Build we can set the option “Allow unsafe code” to enable using pointers.

In the form, we have a picture box which we draw on. Recall that picture boxes are appreciated for graphics, because they are double-buffered which prevents flickering. The user can select the difficulty level of the maze. The more difficult the maze, the larger. The user can select between 1 and 100 difficulties. Let’s call the value the user selects ‘value’. We then calculate the maze width as:

where pictureBoxDraw is the picture we draw on. Similarly, we define the height as:

We then pass them to Maze.Generate which initializes this specific size (resets all cells in the specific bounds). Widthis the number of cells per row, and Height is the number of cells per column. The width\height should be bigger when ‘value’ is bigger, so before calculation, we set the value to:

We use a BackgroundWorker to do the work on another thread, so the GUI doesn’t hang when the maze is being generated and solved. We use a timer to frequently call Maze.Draw while the maze is working.

The user can select the speed of working. The larger the value, the faster the work. We use Thread.SpinWait to slow the operation according to the specific speed.

how to make Generics in C#

Introduction

We (should) always strive for perfection. The very reason for advent of computers is to reduce humane efforts. Although, it has not gone that way but for sure we are capable to handle much more today and a lot more complex things.

Generics in C# isn’t an invention in itself. Something of this sort was expected as template was available there in its predecessor C++.

For some reason I could never understand the real usage of template in C++. It was definitely not as broad as we see today with C#. From 2.0 to 3.5 to 4.0 it has matured a lot – Let’s see what it offers:

There are certain things that will never change.

Like you have n number of objects and you want to place them in an order. In computational term you would like to sort them ascending or descending. If those objects are comparable then with a logic like (bubble, binary..etc.) it can be sorted. So each class doesn’t need to define the sort method. What they need is to implement IComparableinterface.

See the code here:

public class Person : IComparable
{
  public Double NetWorth = 10000;
  public String Name = "xyz";
  public int CompareTo(object obj)
  {
      return NetWorth.CompareTo((obj as Person).NetWorth);
  }
}

public class Individual
{
     public Double NetWorth = 10000;
     public String Name = "abc";
}

These two classes are similar – apart from the IComparable implementation. Now I write a test like following:

List<Person> persons = new List<Person>();
persons.Add(new Person() { Name = "One", NetWorth = 10000 });
persons.Add(new Person() { Name = "Two", NetWorth = 1000 });            

persons.Sort();

List<Individual> individuals = new List<Individual>();

individuals.Add(new Individual() { Name = "One", NetWorth = 10000 });
individuals.Add(new Individual() { Name = "Two", NetWorth = 1000 });
individuals.Sort(); // Invalid operation exception will be thrown here at runtime

The framework developer has written sort functionality in List<T> based on IComparable interface. And we can leverage that by implementing fairly simple IComparable interface in our classes.

Things get easy this way. First we create interfaces based on our understanding/system-requirements and then we build a framework on top of that – which handles all/most of the complexity. And then leveraging the framework we develop our projects – that deals another set of complexity – the real business/functional complexity, and here it should be limited to that.

Nope – the power of Generics has not come so far.

It comes if form of performance, better designing and type safety and blah…blah…

Assume you are walking on a river bridge footpath. It’s easy… but just imagines that without a railing… ok-ok you are smart and you don’t see a problem there – now imagine your ageing parents or your kids are walking there… Hmm – I am sure you will see a problem there now – yes the problem is there because all aren’t smart and most importantly you can’t get confident about smartness of others. So the safety is required and the railing is really necessary. Forget about walking – your kid will run on that and you will still be ok. So Type-Safety provided by .NET is really an important feature.

We deal a lot with collections/arrays in general programming. For that matter the database is also a sort of collections only. A table is collection of rows. A row is collection of cells and likes. Excel sheet is another good example.

.NET 1.0 offered collections like ArrayList and Hashtable and Stack – these deals with objects. As object is base for anything so virtually you can insert, push, add any type in these collections. In normal scenario we rarely need this – what we need is collection of a particular type. For example – a collection of Controls, Datarows, Forecasts, etc. As a developer we know what we are going to store in a collection and what type of object we are going to read. But even if we know it the framework still requires casting because framework is not aware of the object type stored in an Arraylist or Hashtable.

Continuing with the code

ArrayList a = new  ArrayList();
a.Add(new Person());
Person item = (Person)a[0]; // Casting is required

List<T> essentially provides the same feature – with one added thing. It is not bound to 


List<Person> l = new List<Person>();
l.Add(new Person());
Person itm = l[0]; // Casting not required

For performance perspective it’s a big benefit – and the code is also neater.

The other benefit is type safety. In the Arraylist you could add any object but with list you can add only object of type with which it has created. [ or of a derived type ].

public class Politician : Person
{
      public string Speciality = "Nothing";
}

l.Add(new Politician()); // This is valid but while reading it has to be of original type only
Politician sp = l[1]; // invalid operation
Person sp = l[1]; // valid one

The LINQ library created by framework team depends a lot on Generic Interfaces. The full library is set of Extension methods that are created on Interfaces – like IEnumerable<T>

var hni = l.Where(mi => mi.NetWorth > 5000);

The Where is part of LINQ library that takes a function that will accept an argument of type Person and will return true or false. The where will internally iterate in the IEnumerable<person> collection and call this method passing the current item in the argument. If that returns true – that will become part of hni. This is not the exact way how it happens but something very similar. Here we are passing a lambda expression instead of a function.

This is about consuming a Generic Type – we have so many like List, Dictionary, IEnumerable, and so on..; now what about creating a Generic class for our use: – consider following not so ideal example

public interface IDTO { }

public interface IModel {
  IDTO GetData();
  void Persist(IDTO dataObject);
}

public interface IView {
  void BindData(IDTO datasource);
  void SetUpdateEvent(Action<IDTO> updateAction);
}

public abstract class Controller<V, M> where V : IView, new()
                                   where M : IModel, new() 
{
 V view;
 M model;
 public Controller() {
       view = new V();
      model = new M();
 }
 public void Load() {
       var datasource = model.GetData();
      view.BindData(datasource);
      view.SetUpdateEvent(OnUpdate);
  }

 public void OnUpdate(IDTO dataSource) {
      model.Persist(dataSource);
      var datasource = model.GetData();
      view.BindData(datasource);
 }
}
public class MVC<M, V, C> where M : IModel
                          where V : IView
                          where C : Controller<V, M>, new()
{
  C controller = null;
  public void Load()
  {
      controller = new C();
      controller.Load();
  }
}

We are simulating a pattern here – roughly. The main thing here is the Controller class which is a generic one and relies on two types V and M.

There are few constraints we have put with where clause. If we don’t put it there then we can’t write code like

model.GetData();

Because the Controller class will be unaware of the type of M. By default it will treat that as object – so no specific methods would be available there. By putting constraints we say that the M has to be IModel and it must have a default constructor [the new() constraint]. And this opens up a lot of space to code a framework. This was not so with C++ templates

Now the compatibility test

public class Politician : Person
{
 public string Speciality = "Nothing";
}

public class Commonman : Person
{
 public string Occupation = "self employed";
}

Do the following now. It will pop names of Politicians

List<Politician> ms = new List<Politician>();
foreach (Person p in ms) 
{
    MessageBox.Show(p.Name); 
}

We are iterating in the Politicians list as its base type that is Person. It’s allowed – But consider following

List<Politician> ms = new List<Politician>();
foreach (Person p in ms) 
{
  MessageBox.Show(p.Name);
  p = new Commonman(); // not allowed
}

At other places p being a Person Type can have an object of type Commanman – but here in case it is not allowed. Because it can cause potential damage to the actual underlying list that will not accept a Commanman as a Politician and system will throw an exception at runtime

To prevent this runtime behavior the framework doesn’t allow the write operation here and so it goes well – no problem. In other words the List<T> within a foreach loop is treated as IEnumerable<out T> here T is the type we define in the foreach loop for reading current-item. [ this is known as Co-Variant ]. You can get the value but you can’t put in that list.

Action<Person> highlight = p => Console.WriteLine(p.Name);

Now in the above example we are defining an Action on base type Person. If we do a casting like following

Action<Commonman> hcman = highlight;

It’s allowed because Action is Contra-Variant.

BY H M SOHAIL (56-BSCS-2010) SECTION B