## Tuesday, June 14, 2016

### Design a Snake Game

OO Design for Snake and Ladder Game:
http://www.programcreek.com/2014/08/leetcode-design-snake-game-java/

Related Problems:
Given a snake and ladder board, find the minimum number of dice throws required to reach the destination or last cell from source or 1st cell. Basically, the player has total control over outcome of dice throw and wants to find out minimum number of throws required to reach last cell.

Variation:
Design a Snake Game found in Mobiles
http://massivetechinterview.blogspot.in/2016/05/design-snake-game.html

Description of the game:
1. Players play alternately (turn by turn).
2. A player throws a dice.
3. His pebble is moved on the board depending on the dice value.
4. If the pebble is at the bottom of the ladder, move it to the top of the ladder.
5. If the pebble is at the mouth of the snake, move it to the tail of the snake.
6. If any player reaches Home (H100) he wins. Play ends.
7. If pebble tries to move ahead of Home, it reverses its direction. For example, from H98 two moves take pebble to home, but three moves take it to H99.
A project starts with the problem analysis. A complex problem is required to be thoroughly analysed before any design or coding starts. It is expected that “requirements gathering” is done before hand

Requirement analysis:

We may start with studying the snake and ladder board and the rules of playing and specify what the software should do:
Let us first concentrate on the board:
• A board with 100 houses, numbered from 1 to 100.
• Numbering in a particular sequence.
• H1 is start H100 is the Home.
• Snakes = 11, Ladders = 11
Other details:
• Number of players 2
• A dice with 6 faces
• Two color pebbles, one for each player
When a process of analysis starts, we know what we are expected to develop. In simple words, this involves two steps
1. Identify all objects
2. Study its interaction
Another aspect of the analysis is the goal. What the software is going to achieve? When the program is going to end?

Let us scan the problem specifications and list all possible objects:
Board, house, snake, ladder, player, dice and pebbles.
Let us collect other keywords:
Start, home, six faces, colour (pebble), throw, move (pebble), mouth, tail, top, bottom, win and 100.
It is very easy to understand that these keywords are either attributes or methods related to objects. These are summarized in Table 22.1.

Table 22.1 Attributes and Methods Related to Objects

Design:

#### 22.4.1 Design of classes

In the analysis, we have identified seven objects. Now we can group the objects:
Group 1: Board, House, Snake, Ladder, Pebbles
Group 2: Dice
Group 3: Player
A careful analysis will reveal that though snakes and ladders are objects they do not move or change state. Hence, the class board should include snakes, ladders, houses, and pebbles as its integral part and not separate objects.
It leaves us at only three basic objects namely board, dice, and player. Figure 22.2 shows the class diagrams.

#### 22.4.2 Interaction

Now we have to study the interaction between the classes. In the game, player throws the dice. Hence, in the program player will send message “throw” to dice. Dice will turn and assume a new value. Now Dice will tell (send message) the player to calculate. After calculation player will instruct the board to move the pebble. This has been illustrated in Figure 22.3

22.4.3 Sequence of actions
When the pebble moves, it may land at the mouth of a snake or at the bottom of the ladder. In that case, player has to calculate again and then move the pebble accordingly. By this action, it is possible that the pebble may have reached the end. So we have to check for the end of game. Hence, the actual sequence of actions will be:
1. Player to dice -> throw()
2. Dice to player -> calculate1()
3. Player to Board move_pebble()
4. If needed { mouth of snake or base of ladder}
5. Calculate2()
6. Player to Board move_pebble()

For simplicity, Figure 22.4 shows only actions of player1. In actual program actions of player1 will be followed by identical actions by player2.

Strategy to develop complete Program:
How do we go about developing the actual program?
We should start with an empty prototype say lad1.cpp1. As we progress, we should rename program files as lad2.cpp, lad3.cpp. It helps us in keeping track of development. For any reason if we are required to backtrack, it is a painless job. Now you will appreciate why the name of the main file is kept as “lad9A.cpp”.
Next we have to decide initial conditions.
• Pebbles initialized with colours.
• Players associated with pebbles.
• Board drawn with houses, snakes, ladders, and pebbles.
• Both pebbles at house1.

We know that program size is moderately large. So we have to decide on using appropriately designed header files. Since screen has to be in the graphical mode, we should include our much used file bpgraph1.h. Now we should develop header file which generates images of pebbles. We can call it as snlgraph.h. Thereafter, we should develop file board.h. It should include routines related to board. As board.h starts getting bulky, we may develop header file sn_ld.h to contain elementary things regarding snakes and ladder. File board.h can use this file. The Box 22.3 describes the General Strategy about Header Files.

Whenever we develop a header file, we should write a test routine for it. This routine should be included in main file. Main file should be compiled and executed. If we are satisfied withthe header file, the test routine should be commented out. It should not be deleted! When the trials of the program are satisfactory, only at that time these routines should be deleted and main file saved.
With this much preparation, let us see the actual solution.
Problem: Develop complete snake and ladder simulation program.
Solution: The program will be developed using strategy discussed earlier.
• Throwing of dice will be done using random number generation.
• To observe the movements clearly, program will be sprinkled with function delay() at many places.
• To observe movement of pebbles with snakes and ladder a special function named beep_and_pause() will be used. As the name suggests it beeps and waits for pressing of any key. If players get tired, escape key may be pressed to quit simulation. This facility is inbuilt in both functions pause() and beep_and_pause().

Complete Program
##### PROGRAM 22.1 SNAKE AND LADDER
// snake and ladder program main file
typedef char Astring[40] ;
// co-ordinates for dispalying board
const int XX0 = 100;
const int YY0 = 30;
const int SIZE = 30;
#include“BPgraph1.h”
canvas *c1;
#include “snlgraph.h” // graphics routines
#include “snlboard.h” // board related routine
#include “sn_ld.h” // snake and ladder information
Board board(XX0,YY0);
class Player
{   int position ;
Astring name;
public:
int oldpos,newpos; // moved
void update1();
Player(Astring name1);
void calculate_1(const int k);
void calculate_2();
void check_end(int & i);
} ;
Player player1(“Ramesh”), player2(“Suresh”);
int main()
c1->draw();
c1->end_graph();
return 0;
}
void canvas::draw()
{ int end_flag = 0;
Astring msg1;
int step=0;
Dice d1;
int k;
board_graphics_init();
board.draw_board();
board.put_pebble1(1);
board.put_pebble2(1);
c1->message(“press a key to start the game”);
// delay(1000);
// beep_and_pause();
while ( ! end_flag )
{// player1 dice throw
k=d1.throw_dice();
strcpy(msg1,d1.show_dice());
message(msg1); //method from BPgraph1.h showing dice value
// dice to player
player1.calculate_1(k);
// player to dispaly
board.move_pebble1(player1.oldpos, player1.newpos);
player1.update1();
delay(300); //300
board.move_pebble1(player1.oldpos, player1.newpos);
player1.update1();
player1.check_end( end_flag) ;
if (end_flag)
{ //Declare winner
message(“The winner is Player 1” );
delay(1000);
break;
}
delay(300);//300
// player2 to dice throw
k=d1.throw_dice();
strcpy(msg1,d1.show_dice());
message(msg1);
// dice to player
player2.calculate_1(k);
board.move_pebble2(player2.oldpos, player2.newpos);
player2.update1();
delay(300);
board.move_pebble2(player2.oldpos, player2.newpos);
player2.update1();
player2.check_end( end_flag) ;
if(end_flag)
{ //Declare winner
message(“The winner is Player 2”);
delay(2000);
}
else
if(++step > 150)
{ message(“Too long simulation program terminated ”
end_flag =1;
}
delay(1000);
// pause(); // for debugging
}
};
void Player::calculate_1(const int k)
{   int temp;
temp = position + k ;
if( temp <= 100) position =temp;
else position = 100+100 -temp;
newpos=position;
};
void Player::calculate_2()
{ switch (position)
{ // snakes
case 46 : position = 15;beep_and_pause();break;
case 48 : position = 9; beep_and_pause();break;
case 52 : position = 11;beep_and_pause();break;
case 59 : position = 18;beep_and_pause();break;
case 64 : position = 24;beep_and_pause();break;
case 68 : position = 2; beep_and_pause();break;
case 69 : position = 33;beep_and_pause();break;
case 83 : position = 22;beep_and_pause();break;
case 89 : position = 51;beep_and_pause();break;
case 93 : position = 37;beep_and_pause();break;
case 98 : position = 13;beep_and_pause();break;
case 8 : position = 26 ;beep_and_pause();break;
case 19 : position = 38;beep_and_pause();break;
case 21 : position = 82;beep_and_pause();break;
case 28 : position = 53;beep_and_pause();break;
case 36 : position = 57;beep_and_pause();break;
case 43 : position = 77;beep_and_pause();break;
case 50 : position = 91;beep_and_pause();break;
case 54 : position = 88;beep_and_pause();break;
case 61 : position = 99;beep_and_pause();break;
case 62 : position = 96;beep_and_pause();break;
case 66 : position = 87;beep_and_pause();break;
}
newpos = position;
// beep_and_pause(); // useful for debugging
};
void Player::check_end( int & i)
{ if (position == 100) i = 1 ;
};
Player::Player(Astring name1)
{   position = 1;
oldpos = 1;
newpos = 1;
strcpy (name, name1);5};
void Player::update1()
{ oldpos = newpos;
}
Include file snlgraph.h

// snlgraph.h
// routines for capturing pebbles and other graphic images
#include<string.h>
unsigned int Dsize;
void * cube2 ,*cube1;
void * blank,*blank1 , * pebble1, * pebble2;
void pause()
{ char ch1;
ch1 = getch();
if (ch1== 27) exit(0);
};
void beep_and_pause()
{ char ch1;
beep();
c1->message(“press a key to continue”);
ch1 = getch();
if (ch1== 27) exit(0);
}
void grab_image(int x,int y, void *cube2)
{ getimage(x, y, x+ SIZE, y+ SIZE, cube2);
}
void put_image(int x,int y, void *cube2,int z)
{ putimage(x, y, cube2, z);
};
void draw_cube( int x , int y , int z )
{ int i, j ;
for(i=x; i<x+z; i++)
for(j=y; j<;y+z; j++)
putpixel(i,j,YELLOW);
};
void draw_cube1( int x , int y , int z )
{ int i, j ;
for(i=x; i<;x+z; i++)
for(j=y; j<;y+z; j++)
putpixel(i,j,BLUE);
void draw_pebble(int x, int y, int z)
{ int i;
setcolor(z);
for(i=0;i<;10;i++)
circle(x,y,i);
};
void init();
void NtoXY(int n, int & x, int & y) ;
void move_pebble1(int oldpos,int newpos);
void move_pebble2(int oldpos,int newpos);
char str_pointer[3];
void board_graphics_init()
{ int x=100, y=100, i, j;
// calculate the size of the image
Dsize = imagesize(x, y, x+ SIZE, y+ SIZE);
// allocate memory to hold the image
cube2 = malloc(Dsize);
cube1 = malloc(Dsize);
blank = malloc(Dsize);
blank1 = malloc(Dsize);
pebble1 = malloc(Dsize);
pebble2 = malloc(Dsize);
// draw the image to be grabbed
draw_cube(x,y,SIZE);
// grab the image
grab_image(x, y, cube2);
draw_cube1(x,y,SIZE);
// grab the image
grab_image(x, y, cube1);
put_image(130, 130, cube2, COPY_PUT);
putimage(70,70, cube1,COPY_PUT);
draw_pebble (30,30,RED);
grab_image(30-11 ,30-11 , pebble2 );
draw_pebble (30,30,GREEN);
grab_image(30-11 ,30-11 , pebble1 );
putimage(100,100,pebble1,COPY_PUT);
putimage(130,130,pebble2,COPY_PUT);
pause(); // for debugging
clearviewport();
grab_image(0,0,blank);
grab_image(0,0,blank1);
};
Include file snlboard.h

//snlboard.h
#define no_rows 10
#define no_cols 10
#define TEN 10
int SHT[11][2] = { 46,15, 48,9, 52,11, 59,18, 64,24, 68,2, 69,33,
83,22, 89,51, 93,37, 98,13 };
int LTB[11][2]= { 8,26, 19,38, 21,82, 28,53, 36,57, 43,77,
50,91, 54,88, 61,99, 62,96, 66,87 } ;
int status[101];
class Board
{ int x0,y0;
int a[TEN][TEN];
public:
void draw_board();
Board( int a, int b );
void put_pebble1( int z);
void put_pebble2( int z);
void draw_ladder(int topx, int topy, int botomx,int botomy) ;
void draw_snake(int topx, int topy, int botomx,int botomy) ;
void hor_line(int tempx,int i,int lim ) ;
friend void draw_all_snakes();
// revised
void move_pebble1(int oldpos,int newpos);
void move_pebble2(int oldpos,int newpos);
void remove_pebble1( int z) ;
void remove_pebble2( int z) ;
};
extern Board board;
void Board::draw_board()
{ int i,j; int col ;
int ax,ay; int SIZE2 =SIZE+2 ;
int SIZE1= SIZE/2;
//    part1 squares
for (i=0;i<;no_rows;i++)
for (j=0;j<;no_rows;j++)
{ if ((i+j)%2 )
put_image(x0+i*(SIZE2),y0+j*(SIZE2), cube2, COPY_PUT);
else
put_image(x0+i*(SIZE2),y0+j*(SIZE2), cube1, COPY_PUT);
}
// part III numbers
col=getcolor();
setcolor(BLACK);
for( i =2;i<; 100;i++)
{ sprintf(str_pointer, “%2d”,i);
NtoXY(i,ax,ay);
outtextxy( x0+ay*(SIZE2), y0+(ax-1)*(SIZE2)+SIZE1 ,str_pointer);
}
sprintf(str_pointer, “%s”, “ST”);
NtoXY(1,ax,ay); // 1= start
outtextxy( x0+ay*(SIZE2), y0+(ax-1)*(SIZE2)+SIZE1 ,str_pointer);
sprintf(str_pointer, “%s”,”HM”);
NtoXY(100,ax,ay); // 100 = home
outtextxy( x0+ay*(SIZE2), y0+(ax-1)*(SIZE2)+SIZE1 ,str_pointer);
setcolor(col);
draw_all_snakes();
}
void Board::put_pebble1( int z)
{ int ax,ay;
NtoXY(z,ax,ay);
if (status[z]==0)
{  grab_image(x0+ay*(SIZE+2), y0+(ax-1)*(SIZE+2),cube1);
put_image(x0+ay*(SIZE+2), y0+(ax-1)*(SIZE+2),pebble1,COPY_PUT);
status[z] = 1;
}
else if (status[z]==1)
{ memcpy(cube1,cube2,Dsize);
put_image(x0+ay*(SIZE+2), y0+(ax-1)*(SIZE+2),
pebble1,COPY_PUT);
status[z] = 2;
} ;
};
void Board::put_pebble2( int z)
{ int ax,ay;
NtoXY(z,ax,ay);
if (status[z]==0)
{ grab_image(x0+ay*(SIZE+2),y0+(ax-1)*(SIZE+2),cube2);
put_image(x0+ay*(SIZE+2),y0+(ax-1)*(SIZE+2),pebble2,COPY_PUT);
status[z] = 1;
}
else if (status[z]==1)
{ memcpy(cube2,cube1,Dsize);
put_image(x0+ay*(SIZE+2),y0+(ax-1)*(SIZE+2),pebble2,COPY_PUT);
status[z] = 2;
} ;
};
void Board::remove_pebble1( int z)
{ int ax,ay;
NtoXY(z,ax,ay);
if (status[z] ==1)
{ put_image(x0+ay*(SIZE+2),y0+(ax-1)*(SIZE+2),cube1,COPY_PUT);
status[z]=0;
}
else if(status[z]==2)
{ // no put
status[z]= 1;
}
};
void Board::remove_pebble2( int z)
{ int ax,ay;
void Board::remove_pebble2( int zNtoXY(z,ax,ay);
if (status[z] ==1)
{ put_image(x0+ay*(SIZE+2), y0+(ax-1)*(SIZE+2),cube2,COPY_PUT);
status[z]=0;
}
else if(status[z]==2)
{ // no put
status[z]= 1;
}
};
Board::Board ( int a , int b)
{ int i;
x0= a ;
y0 = b ;
for (i=0;i<;101;i++)
status[i] = 0;
}
void NtoXY(int n, int & x, int & y)
{ int x1,y1;
y1= (n-1)_N;
x1=(n-1) /TEN;
x= TEN -x1;
if ( ( x %2 == 1) )
y= (TEN -1) -y1;
else
y= y1;
} ;
void Board::move_pebble1(int oldpos,int newpos)
{ remove_pebble1( oldpos);
put_pebble1( newpos);
};
void Board::move_pebble2(int oldpos,int newpos)
{ remove_pebble2( oldpos);
put_pebble2( newpos);
};
class Dice
{ private:
int val;
public:
Dice();
int throw_dice();
char * show_dice();
} ;
int Dice::throw_dice()
{ int temp;
temp = 1 + random(6);
val = temp;
return temp;
};
char * Dice::show_dice()
{ //char abc[40];
Astring abc ;
sprintf(abc,“%d”, val);
return abc;
}
Dice::Dice() //int x,int y)
{ randomize();
val =1 ;
};
Include file sn_ld.h

// sn_ld.h
void Board::hor_line(int tempx,int i,int lim =5)
{ int k;
for(k=0;k<;lim;k++)
putpixel(x0+tempx+k, y0+i, GREEN );
}
int tail[] = {1,1,2,2,2,3,3,3,4,4,5,4,5 };
void Board::draw_ladder(int topx, int topy, int botomx,int botomy)
{ int temp_col;int i,tempx;
int step = 5;
int SIZE1 = SIZE /2;
topx += SIZE1; topy += SIZE1;
botomx += SIZE1; botomy +=SIZE1;
temp_col=getcolor();
setcolor(BROWN);
for(i=topy +3; i<;botomy; i=i+step )
{ tempx = topx+ (topx-botomx)*(i-topy)/( topy-botomy);
line(x0+tempx, y0+i, x0+tempx+6, y0+i);
}
line(x0+topx,y0+topy, x0+botomx, y0+botomy);
line(x0+topx+6,y0+topy, x0+botomx+6, y0+botomy);
setcolor(temp_col);
void Board::draw_snake(int topx, int topy,int botomx, int botomy)
{ int temp_col;int i,tempx,one=1;
int count;
int SIZE1 = SIZE /2;
topx += SIZE1; topy += SIZE1;
botomx += SIZE1; botomy +=SIZE1;
float slope,Cslope,slopeplus,slope5; //slope for 5 pixels
float disp;
//body
slope = float(topx -botomx) / (topy-botomy);
slopeplus = slope* 0.5 ;
if (slopeplus == 0.0) slopeplus =0.50/2.0;
Cslope=slope;
tempx=topx; disp=0; // 5 for head and tail
const int twelve = 12;
count = 0 ;
for(i=topy ;i<;topy+twelve ;i++)
{ count++;
if (i_==0)
{ Cslope= slope + slopeplus;
slopeplus= - slopeplus ;
one = -one;
};
disp= disp + Cslope;
tempx = tempx + int(disp ) ;
disp = disp-int(disp);
}
// body
for(i=topy+ twelve ;i<;botomy-twelve ;i++)
{ if (i_==0)
{ Cslope= slope + slopeplus;
slopeplus= - slopeplus ;
one = -one;
};
board.hor_line(tempx,i ) ;
disp= disp + Cslope;
tempx = tempx + int(disp ) ;
disp = disp-int(disp);
}
// tail
count = twelve ;
for(i=botomy-twelve ; i<;botomy ;i++)
{ --count;
if (i_==0) { Cslope= slope + slopeplus;
slopeplus= - slopeplus ;
one = -one;
};
board.hor_line(tempx,i,tail[count] ) ;
disp= disp + Cslope;
tempx = tempx + int(disp ) ;
disp = disp-int(disp);
}
} ;
void draw_all_snakes()
{ int i, ax, bx;
int x1,y1,x2,y2;
int SIZE2 = SIZE + 2;
for(i=0;i<;11;i++)
{ ax= SHT[i][0] ;
NtoXY(ax,x1,y1 ); // xy reversal
bx= SHT[i][1] ;
NtoXY(bx,x2,y2);
board.draw_snake(y1*SIZE2,(x1-1)*SIZE2, y2*SIZE2, (x2-1)*SIZE2);
}
} ;
{ int i, ax, bx;
int x1,y1,x2,y2;
int SIZE2 = SIZE + 2;
for(i=0;i<;11;i++)
{ ax= LTB[i][1] ;
NtoXY(ax,x1,y1 ); // xy reversal
bx= LTB[i][0] ;
NtoXY(bx,x2,y2);