Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/articles/cpp-tutorials/)
-   -   Tic Tac Toe game using graphs (http://www.go4expert.com/articles/tic-tac-toe-game-using-graphs-t15237/)

sun_kangane 24Nov2008 21:14

Tic Tac Toe game using graphs
 
I just try to implement the TIC TAC TO GAME USING GRAPHS (ADJACENCY LIST).............

Code: Cpp

/*========================================================================
** DSF MINI_PROGECT **

TITAL : - TIC TAC TOE
NAME  : - KANGANE SANTOSH (VIT, PUNE)

DATA STUCTHER USED :- GRAPH ( ADJACENCY LIST )

=========================================================================*/

#include <iostream.h>
#include <conio.h>
#include <string.h>
#include "graphics.h"
#include "ctype.h"

typedef struct TicTacToe
{
    int blockNo;
    struct TicTacToe *next;
}Alist;

//FUNCTION PROTOTYPE

void draw(void);                //Drawing the required table
void play(void);
void compVSplayer(Alist *[]);
void playerVSplayer(Alist *[]);
void make_list(Alist **);
void printplayer(int );
void printcomp(int );
int compwin(Alist ** ,int []);
void rules(void);
void help(void);

char name[10];
char name1[10];


int main()
{
    int ch;

    /* request auto detection */
    int gdriver = DETECT, gmode;

    /* initialize graphics mode */
    initgraph(&gdriver, &gmode, "E:\\tc\\bgi");

    do
    {

        gotoxy(5,2);
        cleardevice();
        setbkcolor(1);
        settextstyle( 7 , HORIZ_DIR, 3);
        outtextxy(5,4,"Welcome ! \"Let's Play the Game \"TIC TAC TOE\"");
        cout<<"\n\n**** MENU *****\n"
            <<"1. RULES\n"
            <<"2. PLAY\n"
            <<"3. HELP\n"
            <<"4. QUIT\n";
        cout<<"\n\nEnter your choice: ";
        cin>>ch;

        switch(ch)
        {
        case 1:
            rules();
            break;
        case 2:
            play();
            break;
        case 3:
            help();
            break;
        case 4:

            cleardevice();
            closegraph();
            return 0;

        default :
            play();
            break;
        }

    }while(1);
}

void play(void)
{

    int ch;
    Alist *GRAPH[10];
    make_list(GRAPH);
    do
    {
        cleardevice();
        gotoxy(5,1);
        cout<<"*** GAME TYPE ***\n"
            <<"1.COMP Vs PLAYER\n"
            <<"2.PLAYER Vs PLAYER\n"
            <<"3.BACK TO MAIN MENU \n";
        cout<<"\nEnter you'r choice: ";
        cin>>ch;
        switch(ch)
        {
        case 1:

            cout<<"\nEnter your Name : ";
            cin>>name;
            name[0] = toupper(name[0]);
            draw();
            gotoxy(5,1);
            cout<<"ALL THE BEST Ms."<<name;
            cout<<"\n\t Plz play First ";
            compVSplayer(GRAPH);
            break;
        case 2:
            cout<<"\nEnter First player Name : ";
            cin>>name;
            name[0] = toupper(name[0]);
            cout<<"\nEnter Second Player Name : ";
            cin>>name1;
            name1[0] = toupper(name1[0]);
            draw();
            gotoxy(5,1);
            cout<<"\n\nALL THE BEST TO BOHT OF YOU ";
            cout<<"\n\tMr. "<<name<<" Plz play First ";
            playerVSplayer(GRAPH);
            break;
        default:
            ch = 0;
            break;
        }
    }while(ch!=0);

}
/*****************************************************
void compVSplayer() function to play Game
comp VS player main logic function

CALL BY:  play();
CALL'S : printplayer(),printcomp(),compwin();
*****************************************************/


void compVSplayer(Alist *GRAPH[])
{
    Alist * node;
    int i,flag[10],Num,block1,block2,pwin=0,compNo=0,cwin=0;

    Alist *ptr=GRAPH[5];
    // TEMPORARY DE-BUGGING STATEMENTS
    // DISPLAY LINK LIST
    /*   for(i=1;i<10;i++)
    {
    cout<<"\n\n";
    node=GRAPH[i];
    for(;node!=NULL;node=node->next)
    {
    cout<<node->blockNo<<",";
    }
    }
    getch(); */

    /*
    FLAG ARRAY TO INDICATE WHO VISITED THE BLOCK
    0 : NO ONE
    1 : PLAYER
    2 : COMP
    */

    for(i=0;i<10;i++)
    {
        flag[i]=0;             //SET ALL FLAG'S TO ZERO
    }
    gotoxy(1,20);
    cout<<"Enter Block No :";

    for(i=1;i<5;i++)          //PLYER HAS TO ENTER 4 NO.
    {
        gotoxy(20,20);
        cout<<"         ";
        gotoxy(20,20);
        cin>>Num;
        if(flag[Num]==0 && Num > 0 && Num < 10 )    // CHECK FOR VACANCY
        {
            flag[Num] = 1;
            printplayer(Num);

            /*
            WHEN PLAYER SELECT ANY NO THEN HIS WINING CHANGES ARE MORE IN IT's
            ADJACENCY LIST HENCE CHECK PLAYERS WINING CONDITION IN THE SAME LIST
            here let list plyar select no 7 then :-
            we have 7's list 5,3,4,1,8,9
            so camper flag[5] & flag[3] with 1
            if they are equle then player win
            else select next two no 4 & 1 and so on

            */

            for(node = GRAPH[Num];node!=NULL;node=node->next->next)
            {
                block1 = node->blockNo;
                block2 = node->next->blockNo;
                if(flag[block1]==1&&flag[block2]==1)
                {
                    gotoxy(20,22);
                    cout<<"\""<<name<<"\"You win the Game !";
                    pwin=1;
                    break;
                }

                /*
                IF PLAYER HAS VISITED BLOCK1 THEN TO BREAK HIS PATH PUT COMP's
                NO ON BLOCK2 AND VISE VARSA
                */

                if(flag[block1]==1 && flag[block2]==0)
                {
                    compNo = block2;
                }
                if(flag[block2]==1 && flag[block1]==0)
                {
                    compNo = block1;
                }
            }

            if(pwin==1)       //IF PLAREY WIN THEN BREAK
                break;

            /*
            AS 5 IS CENTRAL BLOCK AND MAX. PAYTH ARE GOING THROUE IT SO
            IF PLARER HAS NOT VISITED IT THEN VISIT IT FIRST
            */

            if(flag[5]==0)
            {
                printcomp(5);
                flag[5] = 2;
            }
            else
            {
                //CHEACK FOR COMP WIN

                cwin = compwin(GRAPH,flag);

                if(cwin == 1)   //IF COMP WIN THEN BREAK
                    break;

                /*
                IF PLAYER & COMP ARE NOT IN A POSITION TO WIN THE GAME THEN
                COMP HAS TO PLAY ANY NON VISITED BLOCK
                */

                if(compNo==0)
                {
                    while(ptr)
                    {
                        if(flag[ptr->blockNo] == 0)
                        {
                            compNo = ptr->blockNo;
                            break;
                        }
                        ptr = ptr->next;
                    }
                }

                printcomp(compNo);
                flag[compNo] = 2;
            }
            compNo = 0;    //RESET COMP NO.

        }
        /*
        IF USER TRY TO REPET THE BLOCK THEN DISPLAY ERROR MASSEGE
        */

        else
        {
            gotoxy(10,22);

            cout<<"Sorry ! \""<<name;
            cout<<" \" you are trying to overlod the block ! or Invalid Input";
            getch();
            gotoxy(10,22);
            cout<<"                                                                           ";
            --i;
            Num = 0;
        }
    }

    if(i==5 && cwin == 0 && pwin == 0)
    {
        gotoxy(20,22);
        cout<<" Draw Match ! Try Again !";
    }
    getch();
}

/*****************************************************
int compwin() function to check comp wining condition

FUNCTION: scan throue all graph and check for comp's
wining condition
CALL BY: play()
CALL'S : printcomp();
*****************************************************/


int compwin(Alist **GRAPH ,int flag[])
{
    int i,cwin=0,block1,block2;
    Alist *node;
    for(i=1;i<10;i++)
    {
        if(flag[i] == 2)   //if starting flag is not 2 then there is
        {                 //no wining chance for comp.
            for(node = GRAPH[i]; node!=NULL ; node = node->next->next)
            {
                block1 = node->blockNo;
                block2 = node->next->blockNo;
                /*
                IF COMP HAS VISITED iTH & ETHER OF BLOCK1 || BLOCK 2 & ONE OF THEM
                IS NON VISITED THEN COMP CAN WIN BY VISITING NON VISITED BLOCK
                */

                if((flag[block1]== 2 && flag[block2] ==0)||((flag[block2] == 2)&&flag[block1] == 0))
                {
                    if(flag[block1] == 2)
                        printcomp(block2);
                    else
                        printcomp(block1);

                    settextstyle( 4 , HORIZ_DIR, 2);
                    outtextxy(100,400,"\"Yo !\" I win's the Game !");
                    cwin=1;
                    break;
                }
                if(cwin == 1)
                    break;
            }
        }
    }
    return cwin;
}
/*****************************************************
void make_list() function to creat adjucency list

CALL BY: play()
CALL'S : NON;
*****************************************************/


void make_list(Alist ** GRAPH)
{
    int i,j;
    Alist *node;
    /*
    THIS ARE THE PATH PASSING THROUE EACH BLOCK
    A1[0] is the no of node in the list......
    */

    int A1[] = {6,5,9,2,3,4,7};
    int A2[] = {4,5,8,1,3};
    int A3[] = {6,5,7,1,2,6,9};
    int A4[] = {4,5,6,1,7};
    int A5[] = {8,2,8,4,6,1,9,3,7};
    int A6[] = {4,5,4,3,9};
    int A7[] = {6,5,3,4,1,8,9};
    int A8[] = {4,5,2,7,9};
    int A9[] = {6,5,1,6,3,8,7};

    for(i=0;i<10;i++)     // MAKE ALL ELEMENT OF GRAPH ARRAY TO NULL
    {
        GRAPH[i] = NULL;
    }
    // SELECT ONE BY ONE STATIC ARRAY AND CREAT IT's LIST

    for(i=A1[0];i>=1;i--)
    {
        node = new Alist;
        node ->blockNo = A1[i];
        node->next = GRAPH[1];
        GRAPH[1]   = node;
    }

    for(i=A2[0];i>=1;i--)
    {
        node = new Alist;
        node ->blockNo = A2[i];
        node->next = GRAPH[2];
        GRAPH[2]   = node;
    }
    for(i=A3[0];i>=1;i--)
    {
        node = new Alist;
        node ->blockNo = A3[i];
        node->next = GRAPH[3];
        GRAPH[3]   = node;
    }
    for(i=A4[0];i>=1;i--)
    {
        node = new Alist;
        node ->blockNo = A4[i];
        node->next = GRAPH[4];
        GRAPH[4]   = node;
    }
    for(i=A5[0];i>=1;i--)
    {
        node = new Alist;
        node ->blockNo = A5[i];
        node->next = GRAPH[5];
        GRAPH[5]   = node;
    }
    for(i=A6[0];i>=1;i--)
    {
        node = new Alist;
        node ->blockNo = A6[i];
        node->next = GRAPH[6];
        GRAPH[6]   = node;
    }
    for(i=A7[0];i>=1;i--)
    {
        node = new Alist;
        node ->blockNo = A7[i];
        node->next = GRAPH[7];
        GRAPH[7]   = node;
    }
    for(i=A8[0];i>=1;i--)
    {
        node = new Alist;
        node ->blockNo = A8[i];
        node->next = GRAPH[8];
        GRAPH[8]   = node;
    }
    for(i=A9[0];i>=1;i--)
    {
        node = new Alist;
        node ->blockNo = A9[i];
        node->next = GRAPH[9];
        GRAPH[9]   = node;
    }

}

/*****************************************************
void playerVSplayer() function to play Game
player VS player main logic function

CALL BY:  play();
CALL'S : printplayer(),printcomp();
*****************************************************/


void playerVSplayer(Alist *GRAPH[])
{
    int i,Num,p1win = 0 ,p2win =0 , flag[10];
    int block1,block2,cr = 0;
    Alist *node;

    /*
    FLAG ARRAY TO INDICATE WHO VISITED THE BLOCK
    0 : NO ONE
    1 : PLAYER1
    2 : PLAYER2
    */


    for(i=0;i<10;i++)
        flag[i] = 0;       //SET ALL FLAG TO ZERO

    gotoxy(1,20);
    cout<<"Enter Block No :";
    for(i=0;i<9;)
    {
        gotoxy(20,20);
        cout<<"         ";
        gotoxy(20,20);
        cin>>Num;

        if(flag[Num]==0 && Num > 0 && Num < 10 )    // CHECK FOR VACANCY
        {
            ++i;
            flag[Num] = 1;
            printplayer(Num);

            /*
            WHEN PLAYER SELECT ANY NO THEN HIS WINING CHANGES ARE MORE IN IT's
            ADJACENCY LIST HENCE CHECK PLAYERS WINING CONDITION IN THE SAME LIST
            here: let list plyar select no 7 then :-
            we have 7's list 5,3,4,1,8,9
            so camper flag[5] & flag[3] with 1
            if they are equle then player win
            else select next two no 4 & 1 and so on

            */

            //FOR PLAYER name
            for(node = GRAPH[Num];node!=NULL;node=node->next->next)
            {
                block1 = node->blockNo;
                block2 = node->next->blockNo;
                if(flag[block1]==1&&flag[block2]==1)
                {
                    gotoxy(20,22);
                    cout<<"\""<<name<<"\"You win the Game !";
                    p1win=1;
                    break;
                }
            }
            if(p1win == 1)
                break;
            if(i == 9)
                break;
            do
            {
                gotoxy(20,20);
                cout<<"         ";
                gotoxy(20,20);
                cin>>Num;

                if(flag[Num]==0 && Num > 0 && Num < 10 )    // CHECK FOR VACANCY
                {
                    ++i;
                    flag[Num] = 2;
                    printcomp(Num);
                    cr = 1;          //if user enters carect no then set cr
                    //FOR PLAYER name1
                    for(node = GRAPH[Num];node!=NULL;node=node->next->next)
                    {
                        block1 = node->blockNo;
                        block2 = node->next->blockNo;
                        if(flag[block1]==2 && flag[block2]==2)
                        {
                            gotoxy(20,22);
                            cout<<"\""<<name1<<"\"You win the Game !";
                            p2win=1;
                            break;
                        }
                    }
                }
                else
                {
                    gotoxy(10,22);

                    cout<<"Sorry ! \""<<name1;
                    cout<<" \" you are trying to overlod the block ! or Invalid Input";
                    getch();
                    gotoxy(10,22);
                    cout<<"                                                                           ";
                    cr = 0;   //if user enters incarect no then Reset cr
                    Num = 0;
                }
            }while(cr == 0); //repet till player 2 enters carect No.
            if(p2win == 1)
                break;
        }
        else
        {
            gotoxy(10,22);

            cout<<"Sorry ! \""<<name;
            cout<<" \" you are trying to overlod the block ! or Invalid Input";
            getch();
            gotoxy(10,22);
            cout<<"                                                                           ";
            Num = 0;
        }
    }
    if(i == 9 && p1win == 0 && p2win == 0) //check for Draw match
    {
        gotoxy(20,22);
        cout<<" Draw Match ! Try Again !";
    }
    getch();
}
/*************************************************************
void draw() to Draw the Game box
by seting cursor position and printing = sigen

CALL BY: main();
*************************************************************/


void draw(void)
{
    int i,j;                    //Looping variables
    int num=1;                  //Number displaying function
    char h=205;                 //Horizontal lines
    char v=186;                 //Vertical lines
    char c=206;                 //center symbol like +
    cleardevice();
    for(i=6;i<12;i+=5)
    {
        gotoxy(25,i+3);
        for(j=0;j<=30;j++)
            cout<<h;
    }
    for(j=10;j<=20;j+=10)
    {
        for(i=2;i<17;i++)
        {
            gotoxy(25+j,i+3);
            cout<<v;
        }
    }
    for(i=35;i<=45;i+=10)
        for(j=9;j<=14;j+=5)
        {
            gotoxy(i,j);
            cout<<c;
        }
        for(j=0;j<=10;j+=5)
            for(i=0;i<=20;i+=10)
            {
                gotoxy(34+i,8+j);
                cout<<num++;
            }
}
/*****************************************************
void printplayer() function to display the player's
visited block

CALL BY: play()
CALL'S : NON;
*****************************************************/


void printplayer(int place)
{
    if(place==1)
    {
        gotoxy(30,6);
        cout<<"X";
        gotoxy(10,20);
    }
    else if(place==2)
    {
        gotoxy(40,6);
        cout<<"X";
        gotoxy(10,20);
    }
    else if(place==3)
    {
        gotoxy(50,6);
        cout<<"X";
        gotoxy(10,20);
    }
    else if(place==4)
    {
        gotoxy(30,11);
        cout<<"X";
        gotoxy(10,20);
    }
    else if(place==5)
    {
        gotoxy(40,11);
        cout<<"X";
        gotoxy(10,20);
    }
    else if(place==6)
    {
        gotoxy(50,11);
        cout<<"X";
        gotoxy(10,20);
    }
    else if(place==7)
    {
        gotoxy(30,16);
        cout<<"X";
        gotoxy(10,20);
    }
    else if(place==8)
    {
        gotoxy(40,16);
        cout<<"X";
        gotoxy(10,20);
    }
    else if(place==9)
    {
        gotoxy(50,16);
        cout<<"X";
        gotoxy(10,20);
    }
}

/*****************************************************
void printcomp() function to display the comp's
visited block

CALL BY: play()
CALL'S : NON;
*****************************************************/


void printcomp(int place)
{
    if(place==1)
    {
        gotoxy(30,6);
        cout<<"O";
        gotoxy(10,20);
    }
    else if(place==2)
    {
        gotoxy(40,6);
        cout<<"O";
        gotoxy(10,20);
    }
    else if(place==3)
    {
        gotoxy(50,6);
        cout<<"O";
        gotoxy(10,20);
    }
    else if(place==4)
    {
        gotoxy(30,11);
        cout<<"O";
        gotoxy(10,20);
    }
    else if(place==5)
    {
        gotoxy(40,11);
        cout<<"O";
        gotoxy(10,20);
    }
    else if(place==6)
    {
        gotoxy(50,11);
        cout<<"O";
        gotoxy(10,20);
    }
    else if(place==7)
    {
        gotoxy(30,16);
        cout<<"O";
        gotoxy(10,20);
    }
    else if(place==8)
    {
        gotoxy(40,16);
        cout<<"O";
        gotoxy(10,20);
    }
    else if(place==9)
    {
        gotoxy(50,16);
        cout<<"O";
        gotoxy(10,20);
    }
}
/*************************************************************
void rules() to show the rules of the Game

CALL BY: main();
*************************************************************/


void rules(void)
{

    cout<<"\n\n\nThe rules of the game are as follows:-\n\n"
        <<"Press the number indicated near the playing box \n"
        <<"to put the symbol \" X \" in the playing box.\n"
        <<"\nDo not press a number in which a symbol such as\n"
        <<"\"'X' or 'O'\" already exist. If you do so the\n"
        <<"program will give error due to illegal inputs\n"
        <<"\nYour aim is to get a line containing 3 'X'\n"
        <<"either horizontally or vertically or diagonally\n"
        <<"with alternative inputs by you and computer\n";
    settextstyle( 5 , HORIZ_DIR, 2);
    outtextxy(100,430,"press any key to continue...........");
    getch();
}
/*************************************************************
void help() to show the help for the Game

CALL BY: main();
*************************************************************/


void help(void)
{
    cout<<"\n\nAs the rule of the Game get a line containing 3 'X'\n"
        <<"either hrizontally or vertically or diagonally\n"
        <<"with alternative inputs by you and computer.\n"
        <<"\nAlways try to occupy the middle box and\n"
        <<"then the corners for confusing the computer\n";
    settextstyle( 5 , HORIZ_DIR, 2);
    outtextxy(100,310,"Press any key to continue..........");
    getch();
}

//end of program
 


xpi0t0s 24Nov2008 23:49

Re: Tic tac to game using graphs(c/c++)
 
Good stuff. Why not post it as an article instead, with code commenting and explaining how you did the design and implementation? This would be of interest to beginner programmers, I'm sure, as it is good to see how a program is built up from scratch.

shabbir 25Nov2008 09:01

Re: Tic tac to game using graphs(c/c++)
 
Quote:

Originally Posted by xpi0t0s (Post 39392)
Good stuff. Why not post it as an article instead, with code commenting and explaining how you did the design and implementation? This would be of interest to beginner programmers, I'm sure, as it is good to see how a program is built up from scratch.

Done that.

Also here are some more similar programs but different approaches.
Tic-Tac-Toe Game in C
TicTacToe in Plain C without using BGI graphics

sun_kangane 25Nov2008 17:48

Re: Tic Tac Toe game using graphs
 
thanks xpi0t0s and shabbir..............

actually i view the tic tac to game table as a graph, where each block is a vertex of a graph and the all possible paths are connected to it
ex: there is edge between 1 to 9 , 1 to 5 , 1 to 3, 1 to 2 , 1 to 7 , 1 to 4 etc.

so the ADJACENCY LIST of graph is :

1=> 5 -> 9 -> 2 -> 3 -> 4 -> 7
2 => 5 -> 8 -> 1 -> 3
3 => 5 -> 7 -> 1 -> 2 ->6 ->9
4 => 4 -> 5 -> 6 -> 1 -> 7
5 => 2-> 8 -> 4 -> 6 -> 1 -> 9 -> 3 -> 7
6 => 5 -> 4 -> 3 -> 9
7 => 5 -> 3 -> 4 -> 1 -> 8 -> 9
8 => 5 -> 2 -> 7 -> 9
9 => 5 -> 1 -> 6 -> 3 -> 8 -> 7

win:
when user or comp. select 1 then his wining chances are:
he all ready taken (5, 9) or (2, 3) or ( 4 ,7)

comp next move:
if user has taken 2 successive places, then put X on the 3rd place.

hkp819 4Dec2008 18:17

Re: Tic Tac Toe game using graphs
 
That game is wonderful.
Your graphic design is wonderful. But you can make it more better by some modifications.
But you did great job.

sun_kangane 4Dec2008 23:51

Re: Tic Tac Toe game using graphs
 
thanks "hkp819"


All times are GMT +5.5. The time now is 19:20.