PENERAPAN ALGORITMA COLUMN BY COLUMN DAN DEPTH-FIRST SEARCH DALAM PERMAINAN BABYLON TOWER SKRIPSI HARRY

PENERAPAN ALGORITMA COLUMN BY COLUMN DAN DEPTH-FIRST SEARCH DALAM PERMAINAN BABYLON TOWER

SKRIPSI

HARRY 111402046

PROGRAM STUDI S1 TEKNOLOGI INFORMASI FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015

Universitas Sumatera Utara

PENERAPAN ALGORITMA COLUMN BY COLUMN DAN DEPTH-FIRST SEARCH DALAM PERMAINAN BABYLON TOWER

SKRIPSI

Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah Sarjana Teknologi Informasi

HARRY 111402046

PROGRAM STUDI S1 TEKNOLOGI INFORMASI FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015

Universitas Sumatera Utara

ii

PERSETUJUAN

Judul

: PENERAPAN ALGORITMA COLUMN BY COLUMN DAN DEPTH-FIRST SEARCH DALAM PERMAINAN BABYLON TOWER

Kategori

: SKRIPSI

Nama

: HARRY

Nomor Induk Mahasiswa

: 111402046

Program Studi

: S1 TEKNOLOGI INFORMASI

Departemen

: TEKNOLOGI INFORMASI

Fakultas

: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA

Komisi Pembimbing

:

Pembimbing 2

Pembimbing 1

Romi Fadillah Rahmat, B.Comp.Sc M.Sc

Prof. Dr. Opim Salim Sitompul, M.Sc

NIP. 19860303 201012 1 004

NIP. 19610817 198701 1 001

Diketahui/disetujui oleh Program Studi S1 Teknologi Informasi Ketua,

Muhammad Anggia Muchtar, ST., MM.IT NIP. 19800110 200801 1 010

Universitas Sumatera Utara

iii

PERNYATAAN

PENERAPAN ALGORITMA COLUMN BY COLUMN DAN DEPTH-FIRST SEARCH DALAM PERMAINAN BABYLON TOWER

SKRIPSI

Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.

Medan, 17 Desember 2015

Harry 111402046

Universitas Sumatera Utara

iv

UCAPAN TERIMA KASIH

Puji dan syukur penulis sampaikah kehadirat Tuhan Yang Maha Esa yang telah memberikan rahmat serta restu-Nya sehingga penulis dapat menyelesaikan skripsi ini sebagai syarat untuk memperoleh gelar Sarjana Teknologi Informasi. Pertama, penulis ingin mengucapkan terima kasih kepada Bapak Prof. Dr. Opim Salim Sitompul, M.Sc selaku pembimbing pertama dan Bapak Romi Fadillah Rahmat, B.Comp.Sc. M.Sc selaku pembimbing kedua yang telah membimbing penulis dalam penelitian serta penulisan skripsi ini. Tanpa inspirasi serta motivasi yang diberikan dari kedua pembimbing, tentunya penulis tidak akan dapat menyelesaikan skripsi ini. Penulis juga mengucapkan terima kasih kepada Bapak Dedy Arisandi, ST. M.Kom sebagai dosen pembanding pertama dan Bapak Dr. Sawaluddin, M.IT sebagai dosen pembanding kedua yang telah memberikan masukan serta kritik yang bermanfaat dalam penulisan skripsi ini. Ucapan terima kasih juga ditjukan kepada semua dosen serta semua pegawai pada program studi S1 Teknologi Informasi, yang telah membantu serta membimbing penulis selama proses perkuliahan. Penulis tentunya tidak lupa berterima kasih kepada kedua orang tua penulis, Alm. Bapak Hermanto Tahir, serta Ibu Narina Salimin yang telah membesarkan penulis dengan sabar dan penuh cinta. Terima kasih juga penulis ucapkan kepada adik penulis, Roderick, yang selalu memberikan dukungan kepada penulis. Penulis juga berterima kasih kepada seluruh anggota keluarga penulis yang namanya tidak dapat disebutkan satu persatu. Terima kasih juga penulis ucapkan kepada seluruh teman-teman angkatan 2011 yang telah bersama-sama penulis melewati perkuliahan pada program studi S1 Teknologi Informasi, serta teman-teman mahasiswa Teknologi Informasi lainnya.

Universitas Sumatera Utara

v

ABSTRAK

Babylon Tower merupakan permainan puzzle tiga dimensi yang terdiri dari enam buah cakram yang disusun menumpuk ke atas. Setiap cakram terdiri dari enam kolom bola kecil di sepanjang sisinya dengan enam jenis warna yang berbeda. Babylon Tower dapat dimainkan dengan cara diputar dan digeser. Tujuan dari permainan Babylon Tower adalah mengurutkan setiap bola dengan warna yang sama pada kolom yang sama serta mengurutkan setiap kolom berdasarkan tingkat kecerahan warna bola. Terdapat dua metode yang dapat digunakan untuk menemukan solusi permainan Babylon Tower, yaitu disc by disc dan column by column. Metode yang diajukan pada penelitian ini adalah algoritma column by column dan depth-first search. Pada penelitian ini ditunjukkan bahwa metode yang diajukan mampu menemukan langkah demi langkah untuk mencapai solusi dari permainan Babylon Tower.

Kata kunci: Babylon Tower, puzzle tiga dimensi, column by column, depth-first search.

Universitas Sumatera Utara

vi

IMPLEMENTATION OF COLUMN BY COLUMN AND DEPTH-FIRST SEARCH ALGORITHM IN THE GAME OF BABYLON TOWER

ABSTRACT

Babylon Tower is a three-dimensional puzzle which consists of six discs that are arranged piled up. Each discs consists of six columns of small balls along the side in six kinds of different colors. Babylon Tower can be played by rotating and sliding it. The goal of the game of Babylon Tower is to sort each ball of the same color on the same column and sort the balls in each column based on the brightness of the color of the ball. There are two methods that can be used to find a solution of the game of Babylon Tower, namely disc by disc and column by column. The methods proposed in this research are column by column and depth-first search. In this research, it is shown that the proposed methods are capable of finding step by step to reach a solution of the game of Babylon Tower.

Keywords: Babylon Tower, three-dimensional puzzle, column by column, depth-first search.

Universitas Sumatera Utara

vii

DAFTAR ISI

Hal. Persetujuan

ii

Pernyataan

iii

Ucapan Terima Kasih

iv

Abstrak

v

Abstract

vi

Daftar Isi

vii

Daftar Tabel

x

Daftar Gambar

xi

BAB 1 Pendahuluan

1

1.1. Latar Belakang

1

1.2. Rumusan Masalah

2

1.3. Batasan Masalah

3

1.4. Tujuan Penelitian

3

1.5. Manfaat Penelitian

3

1.6. Metodologi Penelitian

4

1.7. Sistematika Penulisan

5

BAB 2 Landasan Teori

6

2.1. Babylon Tower

6

2.2. Game Architecture

8

2.3. Struktur Data dan Algoritma dalam Game

9

2.3.1. Struktur Data dan Algoritma

10

2.3.2. Struktur Data dalam Game

10

2.4. Path Finding

11

2.4.1. Game Tree

12

2.4.2. Search Tree

13

Universitas Sumatera Utara

viii

2.5. Blind Search

14

2.5.1. Breadth-First Search

15

2.5.2. Depth-First Search

16

2.6. Kecerdasan Buatan dalam Game

18

2.7. Penelitian Terdahulu

19

BAB 3 Analisis dan Perancangan

21

3.1. Arsitektur Umum

21

3.2. Modelling

23

3.2.1. Model Cakram

23

3.2.2. Model Bola

25

3.2.3. Model Babylon Tower

26

3.3. Struktur Data

27

3.3.1. Ball

27

3.3.2. Disc

28

3.3.3. Inner Gap

29

3.3.4. Babylon Tower

29

3.4. Game Mechanic

31

3.4.1. Touch Handling

31

3.4.2. Moves Handling

35

3.5. AI

38

3.5.1. Sorting dengan depth-first search

39

3.5.2. Swapping

42

3.5.3. Parity

44

BAB 4 Implementasi dan Pengujian

47

4.1. Implementasi

47

4.1.1. Spesifikasi perangkat keras

47

4.1.2. Spesifikasi perangkat lunak

48

4.1.3. Eksekusi aplikasi

48

4.2. Pengujian

52

Universitas Sumatera Utara

ix

4.2.1. Hasil dari Tahap Sorting

53

4.2.2. Hasil dari Tahap Swapping

53

4.2.3. Hasil dari Tahap Parity

54

4.2.4. Hasil Pengujian

55

BAB 5 Kesimpulan dan Saran

56

5.1. Kesimpulan

56

5.2. Saran

56

Daftar Pustaka

58

Universitas Sumatera Utara

x

DAFTAR TABEL

Hal. Tabel 3.1. Daftar variabel pada class Ball

27

Tabel 3.2. Nama-nama warna bola dalam array

28

Tabel 3.3. Daftar variabel pada class Disc

29

Tabel 3.4. Daftar variabel pada class Babylon Tower

30

Tabel 3.5. Daftar method pada class Babylon Tower

30

Tabel 3.6. Nilai yang disimpan serta proses undo dan redo pada gerakan rotate

36

Tabel 3.7. Nilai yang disimpan serta proses undo dan redo pada gerakan push

37

Tabel 3.8. Nilai yang disimpan serta proses undo dan redo pada gerakan slide

38

Tabel 4.1. Hasil pengujian terhadap banyak langkah yang dibutuhkan untuk menemukan solusi

54

Universitas Sumatera Utara

xi

DAFTAR GAMBAR

Hal. Gambar 2.1. Game tree pada Tic-Tac-Toe (Millington & Funge, 2009)

12

Gambar 2.2. Search tree pada permainan Babylon Tower

13

Gambar 2.3. Breadth-first search pada permainan Babylon Tower

15

Gambar 2.4. Depth-first search pada permainan Babylon Tower

17

Gambar 3.1. Arsitektur Umum

22

Gambar 3.2. Model cakram (disc) pada posisi paling atas

24

Gambar 3.3. Model cakram (disc) pada posisi paling bawah

24

Gambar 3.4. Model cakram (disc) yang posisinya diapit oleh dua cakram yang lain

25

Gambar 3.5. Tiga puluh enam buah bola yang digunakan dalam Babylon Tower

25

Gambar 3.6. Babylon Tower dalam Model 3D

26

Gambar 3.7. Tampilan scene sebelum dan sesudah bola merah pada posisi paling bawah ditekan masuk ke dalam cakram

34

Gambar 3.8. Tampilan scene sebelum dan sesudah bola merah pada baris keempat dari atas digeser menuju celah yang ada di posisi paling atas

34

Gambar 3.9. Tampilan scene ketika jari user sedang memutar salah satu cakram dan tampilan scene setelah jari user meninggalkan layar

35

Gambar 4.1. Tampilan Main Menu

49

Gambar 4.2. Tampilan Game Scene

50

Gambar 4.3. Tampilan Help dan About

52

Universitas Sumatera Utara