Selamat datang di tutorial ini, kali ini saya akan memberikan tutorial tentang pengimplementasian struktur data stack (tumpukan) dalam sebuah game. Game yang saya angkat kali ini adalah game tower of hanoi.

Implementasi Struktur Data Stack (Tumpukan) dalam Tower of Hanoi Game

Selamat datang di tutorial ini, kali ini saya akan memberikan tutorial tentang pengimplementasian struktur data stack (tumpukan) dalam sebuah game. Game yang saya angkat kali ini adalah game tower of hanoi. 

The Tower of Hanoi (juga disebut Menara Brahma atau Lucas 'Tower) adalah permainan matematika atau teka-teki. Ini terdiri dari tiga batang, dan sejumlah piringan dengan ukuran yang berbeda yang dapat berpindah ke batang lainnya. Teka-teki dimulai dengan tumpukan piringan dalam urutan ukuran pada satu batang, yang terkecil di bagian atas, sehingga membuat bentuk kerucut. 

Tujuan dari teka-teki adalah untuk memindahkan seluruh tumpukan ke batang lain, dan harus mematuhi aturan sederhana berikut ini:

  1. Hanya satu piringan dapat dipindahkan pada satu kali langkah.
  2. Setiap langkah terdiri dari mengambil satu piringan paling atas dari salah satu tumpukan dan meletakkannya di paling atas tumpukan lain yaitu piringan hanya dapat dipindahkan jika piringan ada di paling atas suatu tumpukan. 
  3. Tidak ada piringan yang dapat ditempatkan di atas piringan yang lebih kecil.

Sedangkan algoritma yang kita gunakan dalam membuat game ini adalah algoritma Stack (tumpukan) dalam teori Struktur Data. Stack (tumpukan) adalah salah satu model struktur data yang tersusun secara LIFO (Last In First Out) dimana penyisipan elemen selalu dilakukan di atas (TOP) dan penghapusan elemen selaku dilakukan pada TOP. Stack disini diimplementasikan dengan single link list dinamis.

Dalam membuat game ini, saya menggunakan tipe data ADT (Abstract Data Type). Abtract Data Type merupakan suatu konsep pemrograman yang terkait dengan pendefinisian TYPE dan kumpulan PRIMITIF terhadap TYPE tersebut. TYPE dapat dikatakan sebagai hasil proses Abstraksi awal data dari permasalahan (studi kasus) yang sedang dihadapi. Sedangkan PRIMITIF adalah operasi dasar terhadap TYPE tersebut. 

Oke tidak usah panjang lebar lagi, mari kita buat game ini :D Langkah pertama yang harus kamu lakukan adalah membuat file header.h untuk membuat spesifikasi yang dibutuhkan dalam game ini.

Spesifikasi yang harus kamu buat adalah:

  • Infotype (info suatu elemen, dalam hal ini bertipe integer)
  • Elemen stack
  • Stack
#ifndef HEADER_H_INCLUDED
#define HEADER_H_INCLUDED

// definisikan properti dari list biar lebih mudah dibaca
#define Info(P)  (P)->Info
#define Next(P)  (P)->Next
#define Top(S)   (S).Top
#define Max(S)   (S).Max
#define Count(S) (S).Count
#define Nil     NULL

#define bool unsigned short int
#define False 0
#define True  !False

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

// ini adalah infotype yang ada pada elemen
typedef int InfoType;

// membuat elemen stack untuk single link list
typedef struct tElmStack *Address;
typedef struct tElmStack {
    InfoType Info;
    Address  Next;
} ElmStack;

// list
typedef struct {
    Address Top;
    int     Count;
} Stack;

void CreateStack(Stack *S);
// I.S. Sembarang
// F.S. Terbentuk Stack kosong

bool IsEmpty(Stack S);
// Menghasilkan True jika Stack kosong, dan False jika Stack tidak kosong

Address Allocate(InfoType X);
// Menghasilkan Address dari alokasi sebuah elemen dengan InfoType X
// Jika alokasi berhasil maka nilai Address tidak Nil dan jika gagal nilai Address Nil

void DeAllocate(Address P);
// I.S. P terdefinisi
// F.S. Memori yang digunakan oleh P dikembalikan ke sistem

void Push(Stack *S, Address P);
// I.S. Sembarang, P terdefinisi
// F.S. Menempatkan P pada Top dari S

void Pop(Stack *S, Address *P);
// I.S. Stack tidak kosong
// F.S. Mengambil P dari Top dari S

void ViewStack(Stack S);
// I.S. Sembarang
// F.S. Menampilkan semua Info dari masing-masing elemen dari Stack

void ViewVisual(Stack S[3], int TotalDisk);
// I.S. Tiga Stack, Total Disk > 0
// F.S. Menampilkan visualisasi Menara Hanoi dari 3 Stack tersebut

#endif // HEADER_H_INCLUDED

Setelah selesai membuat spesifikasi program yang dibutuhkan, kini saatnya masuk ke langkah kedua yaitu pembuatan implementasi dari abstract type yang sudah dibuat. Kamu perlu membuat file baru yaitu implementasi.c. Pada file ini kamu harus mengimplementasikan prosedur dan function yang sudah kamu definisikan di file header.h yang sudah dibuat, maka kamu harus meng-include file header.h di file ini.

 

#include "header.h"

void CreateStack(Stack *S)
{
    Top(*S) = Nil;
    Count(*S) = 0;
}

bool IsEmpty(Stack S)
{
    return Top(S) == Nil;
}

Address Allocate(InfoType X)
{
    Address P = (Address)malloc(sizeof(ElmStack));
    if (P != Nil)
    {
        Info(P) = X;
        Next(P) = Nil;
    }
    return P;
}

void DeAllocate(Address P)
{
    free(P);
}

void Push(Stack *S, Address P)
{
    Next(P) = Top(*S);
    Top(*S) = P;
    Count(*S)++;
}

void Pop(Stack *S, Address *P)
{
    *P = Top(*S);
    Top(*S) = Next(*P);
    Count(*S)--;
}

void ViewStack(Stack S)
{
    Address P;
    InfoType X[Count(S)];
    int i = 0;
    for (P = Top(S); P != Nil; P = Next(P))
    {
        X[i] = Info(P);
        i++;
    }
    for (i = Count(S) - 1; i >= 0; i--)
        printf("%d ", X[i]);
}

void ViewVisual(Stack S[3], int TotalDisk)
{
    int i, j, k;
    Address P;
    InfoType X[3][TotalDisk];
    for (i = 0; i < 3; i++)
    {
        for (j = 0; j < TotalDisk - Count(S[i]); j++)
            X[i][j] = 0;
        for (P = Top(S[i]); P != Nil; P = Next(P))
        {
            X[i][j] = Info(P);
            j++;
        }
    }
    for (i = 0; i < TotalDisk; i++)
    {
        for (j = 0; j < 3; j++)
        {
            printf(" ");
            if (X[j][i] == 0)
                for (k = 0; k < 2 * TotalDisk - 1; k++)
                    printf(" ");
            else
            {
                for (k = 0; k < TotalDisk - X[j][i]; k++)
                    printf(" ");
                for (k = 0; k < 2 * X[j][i] - 1; k++)
                    printf("=");
                for (k = 0; k < TotalDisk - X[j][i]; k++)
                    printf(" ");
            }
        }
        printf("\n");
    }
    for (i = 1; i <= 3; i++)
    {
        printf(" ");
        for (j = 0; j < TotalDisk - 1; j++)
            printf(" ");
        printf("%d", i);
        for (j = 0; j < TotalDisk - 1; j++)
            printf(" ");
    }
    printf("\n");
}

 

fiuuhh.... Setelah selesai membuat implementasi dari abstract data type yang dibuat, kini saatnya kamu masuk ke langkah ketiga yaitu membuat driver atau main program yang kamu akan buat ini, maka kamu perlu membuat file main.c yang didalamnya adalah file utama yang akan dijalankan oleh compiler.  Sebelumnya kamu harus include file header.h. Namun, ada beberapa compiler yang meminta include file implementasinya (implementasi.c). Kali ini saya include file headernya (header.h).

#include "header.h"

int main()
{

    int i;

    int CMain, TotalDisk, MFrom, MTo, MCount;
    Address P;

    // membuat 3 stack (tower)
    Stack Tower[3];
    for (i = 0; i < 3; i++)
        CreateStack(&Tower[i]);

    // membuat menu program
    do
    {
        system("cls");
        printf("================\n");
        printf(" TOWER OF HANOI\n");
        printf("================\n");
        printf(" 1. New Game\n");
        printf(" 2. Credits\n");
        printf(" 3. Quit\n");
        printf("================\n\n");
        printf(" Your Input: ");
        scanf("%d", &CMain);
        switch (CMain)
        {
        case 1:
            do
            {
                system("cls");
                printf("================\n");
                printf("    NEW GAME\n");
                printf("================\n");
                printf(" Total Disk: ");
                scanf("%d", &TotalDisk);
                if (TotalDisk <= 0)
                {
                    printf("\n Invalid input. Please input again.\n");
                    getch();
                }
            }
            while (TotalDisk <= 0);

            // menyisipkan piringan yang telah diinput kedalam stack (tower) pertama
            for (i = 0; i < TotalDisk; i++)
                Push(&Tower[0], Allocate(TotalDisk - i));

            // obey the rule
            MCount = 0;
            do
            {
                system("cls");
                for (i = 0; i < 3; i++)
                {
                    printf("\n Tower %d: ", i + 1);
                    ViewStack(Tower[i]);
                }
                printf("\n\n");
                ViewVisual(Tower, TotalDisk);
                printf("\n\n Move Count: %d\n\n", MCount);
                printf("\n Move From : ");
                scanf("%d", &MFrom);
                printf("\n      To   : ");
                scanf("%d", &MTo);
                MFrom--;
                MTo--;

                if (MFrom >= 0 && MFrom <= 2 && MTo >= 0 && MTo <= 2)
                {
                    if (!IsEmpty(Tower[MFrom]))
                    {
                        if (IsEmpty(Tower[MTo]))
                        {
                            Pop(&Tower[MFrom], &P);
                            Push(&Tower[MTo], P);
                            MCount++;
                        }
                        else if (Info(Top(Tower[MTo])) > Info(Top(Tower[MFrom])))
                        {
                            Pop(&Tower[MFrom], &P);
                            Push(&Tower[MTo], P);
                            MCount++;
                        }
                        else
                        {
                            printf("\n Invalid move. Please input your move again.\n");
                            getch();
                        }
                    }
                    else
                    {
                        printf("\n Invalid move. Please input move again.\n");
                        getch();
                    }
                }
                else
                {
                    printf("\n Invalid move. Please input move again.\n");
                    getch();
                }
            }
            while (Count(Tower[1]) != TotalDisk && Count(Tower[2]) != TotalDisk);
            system("cls");
            for (i = 0; i < 3; i++)
            {
                printf("\n Tower %d: ", i + 1);
                ViewStack(Tower[i]);
            }
            printf("\n\n");
            ViewVisual(Tower, TotalDisk);
            printf("\n\n Move Count: %d\n", MCount);
            printf("\n Congratulation, you win!\n");
            getch();

            while (!IsEmpty(Tower[1]))
            {
                Pop(&Tower[1], &P);
                DeAllocate(P);
            }
            while (!IsEmpty(Tower[2]))
            {
                Pop(&Tower[2], &P);
                DeAllocate(P);
            }

            break;
        case 2:
            system("cls");
            printf("==================================\n");
            printf("        TOWER OF HANOI\n");
            printf(" Copyright @ndhaperdana\n");
            printf("==================================\n\n");
            getch();
            break;
        case 3:
            printf("\n Thanks for playing.\n");
            getch();
            break;
        default:
            printf("\n Invalid input. Please input again.\n");
            getch();
        }
    }
    while (CMain != 3);


    return 0;
}

Akhirnya selesai sudah kamu membuat game ini, tinggal di compile kemudian jalankan, dan kamu bisa mencoba mengasah otak kamu dengan bermain game yang sudah kamu buat sendiri

Jalankan kodenya, maka akan muncul seperti ini, selamat bermain

Hasil Run Program

Sekian tutorial dari saya


About Author

Adnan w Anadrep


Comment & Discussions

  • hallo , saya sudah mencoba script nya , tapi kenapa masih error saat di run , kesalahan nya terletak di header nya ( #define Nil NULL ) di nyatakan error : ''before numeric constant'' mohon bantuannya

  • dimas maendra utomo
    mas bisa njelasin yang #define #define Info(P) (P)->Info
    #define Next(P) (P)->Next
    #define Top(S) (S).Top
    #define Max(S) (S).Max
    #define Count(S) (S).Count
    itu artinya apa?

  • Please LOGIN before if you want to give the comment.