laporan rancang bangun permainan snake versus dengan algoritma a star

8/20/2019 Laporan Rancang Bangun Permainan Snake Versus dengan Algoritma A Star

1/42

LAPORAN PENGEMBANGAN APLIKASI

PERMAINAN ‘SNAKE VERSUS ’ DENGAN ALGORITMA A*

Diajukan sebagai tugas pengganti Ujian Akhir Semester (UTS) Genap 2014-2015

Mata Kuliah Kecerdasan Buatan

Disusun oleh:

Aliffahri Saputra (081211631013)

Kusumaningtyas Aditya Putri (081211632010)

Tiara Ratna Sari (081211632014)

S1 SISTEM INFORMASI

DEPARTEMEN MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS AIRLANGGA

2015


2/42


3/42

makanan. Computer akan secara kontinyu menghitung jalur terpendek dari

posisinya menuju makanan sehingga diharapkan permainan ini akan menjadi lebih

menarik dan menantang. Permainan yang akan dikembangkan ini dinamakan

permainan ‘Snake Versus’.

1.2 Rumusan Masalah

Adapun rumusan masalah dari penulisan laporan ini adalah:

1. Bagaimana menerapkan algoritma A* dalam permainan?

1.3 Tujuan

Adapun tujuan yang akan dicapai dari laporan ini adalah:

1. Menerapkan algoritma A* dalam sebuah permainan, yaitu permainan

‘Snake Versus’.

1.4 Batasan Masalah

Adapun batasan masalah dari pengembangan permainan ini adalah:

1.

Permainan akan dikembangkan dengan bahasa pemrograman Java.

2. Penerapan algoritma A* terbatas pada penentuan rute terpendek dari posisi

ular computer pada saat itu menuju makanannya, sedangkan optimalisasi

pada permainan (menghindari badannya sendiri, menghindari boundary

area permainan) belum dikembangkan lebih lanjut.


4/42


5/42

d.

Sebuah sistem yang dapat berperilaku secara rasional

Lebih jauh lagi, berikut adalah beberapa definisi mengenai

kecerdasan buatan yang dapat diketahui, yaitu:

a.

Menurut Rich dan Knight (1991, p3)

Kecerdasan buatan merupakan ilmu yang mempelajari

bagaimana membuat sebuah komputer dan mengerjakan

sesuatu yang masih lebih baik dikerjakan manusia.

b. Menurut Rolston (1988, p15)

Kecerdasan buatan merupakan solusi berbasis komputer

terhadap masalah yang ada, yang menggunakan aplikasi

yang mirip dengan proses berpikir menurut manusia.

c. Menurut Setiawan (1993, p1)

Kecerdasan buatan dapat didefinisikan sebagai cabang ilmu

komputer yang mempelajari otomatisasi tingkah laku

cerdas.

2.1.2

Konsep Kecerdasan Buatan

Terdapat dua bagian utama yang diperlukan agar dapat melakukan

aplikasi kecerdasan buatan, seperti dapat terlihat pada Gambar 2.1, yaitu:

a. Basis pengetahuan (knowledge base), yang berisi fakta,

teori, pemikiran, dan hubungan satu dengan yang lainnya,

b. Motor inferensi (inference engine), yang berupa

kemampuan mesin untuk menarik kesimpulan berdasarkan

pengalaman.

Gambar 2.1 Penerapan Konsep Kecerdasan Buatan di Komputer (Turban dan

Frenzel, 1992, p12)


6/42

2.1.3 Bidang-bidang Terapan pada Kecerdasan Buatan

Kecerdasan buatan adalah sebuah ilmu pengetahuan dan teknologi

yang berisikan ide-ide dan konsep yang diperuntukkan untuk sebuah

penelitian dan tidak untuk dipasarkan (Turban dan Aronson, 2001, p402-

406). Namun kecerdasan buatan menyediakan dasar-dasar ilmu

pengetahuan pada beberapa bidang teknologi yang dapat digunakan secara

komersial, di antaranya adalah:

a.

Sistem pakar (expert system)

Sebuah sistem komputer yang digunakan sebagai sarana

untuk menyimpan pengetahuan yang dimiliki oleh seorang

atau lebih pakar dengan tujuan agar komputer memiliki

keahlian untuk menyelesaikan permasalahan dengan meniru

keahlian yang dimiliki pakar tersebut.

b. Pengolahan bahasa alami (natural language processing )

Pemrograman sistem komputer dimana pengguna dapat

berkomunikasi dengan komputer dengan menggunakan

bahasa sehari-hari.

c. Pengenalan suara/ucapan ( speech recognition)

Pengguna dapat berkomunikasi dengan komputer/memberi

perintah kepada komputer untuk melakukan suatu

pekerjaan.

d.

Robotika dan sistem sensorik (robotic and sensory systems)

Sebuah organ tubuh robotik yang dilengkapi oleh berbahai

sensor yang diprogram untuk mampu mendeteksi jenis

pekerjaan yang perlu dilakukan oleh organ tubuh tersebut.

e. Computer vision

Pemrograman sistem yang bertujuan untuk

menginterpretasikan gambar dan objek tampak melalui

komputer untuk proses lebih jauh.

f.

Intelligent computer-aided instruction


7/42

Sistem komputer yang digunakan untuk proses

pembelajaran/sebagai tutor yang dapat melatih dan

mengajar.

g.

Game playing

2.14 Kelebihan Kecerdasan Buatan

Kecerdasan buatan memiliki beberapa kelebihan dibandingkan

dengan kecerdasan yang dimiliki oleh manusia (Kusumadewi, 2003, p3-4),

yaitu:

a.

Bersifat lebih permanen. selama sistem dan program tidak

berubah, maka kecerdasan buatan tersebut tidak akan

berubah;

b. Lebih mudah untuk diduplikasi dan disebarkan dari satu

komputer ke komputer lain dibandingkan dengan

memindahkan pengetahuan dari satu manusia ke manusia

yang lain;

c.

Lebih murah dibandingkan dengan mendatangkan seorang

ahli;

d. Konsisten. Kecerdasan buatan merupakan sebuah teknologi

komputer sedangkan kecerdasan alami memiliki

kecenderungan untuk berubah;

e. Bisa didokumentasi. Tiap aktivitas yang dilakukan oleh

kecerdasan buatan dapat dilacak dengan mudah sedangkan

kecerdasan alamai termasuk sulit untuk direproduksi.

f. Mengerjakan pekerjaan dengan waktu lebih cepat dan lebih

baik.

2.2 Algoritma A*

2.2.1 Pengertian Algoritma A*

A* (A Star) adalah algoritma komputer untuk pncarian jarak

terdekat dan penelusuran rute yang dipublikasikan pada tahun 1968 oleh


8/42


9/42

Pada algoritma ini pencarian node yang paling mendekati solusi

nantinya akan disimpan suksesornya ke dalam list sesuai dengan ranking

yang paling mendekati hasil terbaik. Algoritma ini akan mengunjungi

setiap node selama node itu adalah yang terbaik. Bila node yang

dikunjungi ternyata tidak mengarah ke hasil yang diinginkan, maka akan

melakukan penelusuran balik ke arah node yang terakhir dikunjungi.

Apabila tidak dapat ditemukan juga, maka akan terus menelusuri ulang

mencari ke arah node awal sampai dapat ditemukan node yang lebih baik

kemudian untuk dibandingkan dengan suksesornya (Phaneendhar R V,

2011).

2.2.2 Cara Kerja Algoritma A*

Dalam penerapannya, untuk merepresentasikan node-node pada

graph/tree, maka digunakan dua buah himpunan, yaitu open list dan close

list. Setiap kali menelusuri sebuah node yang baru, maka node tersebut

dibandingkan dengan node-node lain yang berada di dalam open list dan

close list, untuk memeriksa apakah node baru tersebut sudah pernah

ditelusuri atau belum. Open list berisi node-node yang telah ditelusuri dan

telah dihitung nilai heuristic-nya, tetapi belum diperiksa (misalnya

suksesor suatu node). Sedangkan close list berisi node-node dari open list

yang telah diperiksa.

Menurut Rich dan Knight (1001, p76), cara kerja Algoritma A*

adalah:

1.

Dimulai dengan open list yang hanya berisi initial node. Set nilai g

dari node tersebut menjadi 0, dan nilai h sesuai heuristic sehingga

nilai f adalah h-0 = h. Set close list berupa list kosong.

2. Hingga node tujuan ditemukan, ulangi prosedur berikut:

Jika tidak ada node yang terdapat pada open list, maka laporkan

kekeliruan. Jika tidak, ambil node pada open list yang memiliki

nilai f terendah dan namakan sebagai best node. Pindahkan lagi

dari open list, masukkan ke close list. Periksa apakah best node


10/42

merupakan node tujuan. Jika ya, maka keluar dari prosedur ini dan

laporkan hasilnya (termasuk node yang telah dihasilkan dari node

awal ke node tujuan). Jika tidak, buat suksesor-suksesor dari best

node, tetapi jangan menentukan best node menunjuk ke mereka.

Suksesor-suksesor tersebut perlu diperiksa apakah pernah dibuat

sebelumnya. Untuk setiap suksesor, lakukan langkah-langkah

berikut:

● Set suksesor menunjuk kembali ke best node. Link ke

belakang ini memungkinkan jalur yang terbentuk

dipulihkan setelah hasilnya ditemukan.

● Hitung g(suksesor) = g(best node) + biaya yang diperlukan

untuk mencapai dari best node ke suksesor.

● Lihat apakah suksesor sama dengan node yang berada di

open list. Jika ya, maka namakan sebagai old. Bila node ini

ada dalam tree, maka suksesor dapat dikeluarkan dari tree

dan ditambahkan old dalam daftar suksesornya best node.

Sekarang harus ditentukan apakah link ke parent dari old

perlu diubah menjadi menunjuk ke best node. Hal ini dapat

terjadi bila rute yang baru saja ditemukan menuju suksesor

lebih murah atau lebih baik dari rute terbaik yang ada

sekarang ke old (bila old dan suksesor adalah titik yang

sama). Jadi lihat apakah lebih murah untuk menuju ke old

melalui parent yang sekarang atau ke suksesor melalui best

node dengan membandingkan nilai g-nya. Jika old lebih

murah atau sama, maka tidak dilakukan apapun. Jika

suksesor lebih murah, maka ubah link parent dari old

menunjuk ke best node lalu simpan rute ke dalam g(old )

dan perbarui f(old ).

● Jika suksesor tidak terdapat pada open list, lihat apakah

terdapat pada close list. Jika ya, maka namakan sebagai

close list old dan tambahkan ke daftar suksesor dan best


11/42

node. periksa apakah rute yang baru ini lebih baik daripada

rute pada langkah 2(c) dan set link parent, nilai g dan f. Jika

rutenya lebih baik, maka lakukan perbaikan pada suksesor

dari old dengan pergerakan secara depth-first dimulai dari

old, ubah nilai g dan f tiap node, akhiri tiap cabang bila

telah mencapai nodeyang tidak memiliki suksesor atau

menentukan rute yang lebih baik dari sebelumnya. Tiap link

parent dari node menunjuk ke parent terbaiknya. Saat

menyebarkan node ke bawah, lihat apakah parent-nya

menunjuk ke titik awal. Jika ya, maka lanjutkan

penyebaran. Jika tidak, maka nilai g-nya mencerminkan

rute yang lebih baik dan penyebaran dihentikan di sini.

Tetapi mungkin dengan nilai baru g yang node-nya

disebarkan ke bawah menjadi rute yang lebih baik dari rute

yang melalui parent yang sekarang. Jika dibandingkan

keduanya. Jika rute melalui parent yang sekarang masih

lebih baik, maka hentikan penyebaran.

● Jika suksesor tidak pernah ada di open list atau close list,

maka masukkan ke open list dan tambahkan ke daftar

suksesor dari best node. Hitung f(suksesor) = g(suksesor) +

h(suksesor).

2.2.3 Contoh Algoritma A*

Gambar 2.2 Kondisi Awal


12/42

Posisi node awal = Ax : 0, Ay : 0

Posisi node tujuan = goal.x : 2, goal.y : 2

a. Langkah kesatu

n (1,1) : g (1,1) = 1

h_orthogonal(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))

h_orthogonal(1,1) = (abs(1 - 2) + abs(1 - 2))

= (abs(-1) + abs(-1))

= 2

h_diagonal(n) = min(abs(n.x-goal.x) + abs(n.y-

goal.y))

h_diagonal(1,1) = min(abs(1 - 2)+abs(1 - 2))

= min(abs(-1)+abs(-1))

= min 2

h(n) = h_diagonal(n) + (h_orthogonal (n) – (2 * h_diagonal(n)))

h(1,1) = (-2) + (2-(2*(-2)))

= -2 + 6

= 4

f (1,1) = g (1,1) + h (1,1)

= 1 + 4

= 5

n (1,0) : g (1,0) = 1



= (abs(-1) + abs(-2))

= 3

h_diagonal(n) = min(abs(n.x-goal.x), abs(n.y-

goal.y))




13/42


14/42

Gambar 2.3 Langkah Pertama

Pada Gambar 2.3 terdapat tiga node yang mungkin menjadi

best node, yaitu (1,0) dengan f(n) = 1, (1,1) dengan f(n) = 5, dan

(0,1) dengan f(n) = 7. Maka dipilih node (1,1) dengan biaya

terkecil, yaitu 5.

b. Langkah kedua

n (2,2) : g (2,2) = 2



= (abs(0) + abs(0))

= 0

h_diagonal(n) = min(abs(n.x-goal.x) + abs(n.y-

goal.y))


= min(abs(0)+abs(0))

= min 0


h(0,1) = (-0) + (0-(2*(-0)))

= 0 + 0

= 0

f (2,2) = g (2,2) + h (2,2)

= 2 + 0

= 2


15/42

Gambar 2.4 Langkah Kedua

Pada Gambar 2.4 terdapat satu node yang mungkin menjadi

best node, yaitu (2,2) dengan f(n) = 2 dan dikenali sebagai node

tujuan, yaitu (2,2). Maka solusi telah ditemukan.

Gambar 2.5 Hasil


16/42

16

BAB III

PERANCANGAN SISTEM

3.1 Perancangan Sistem

‘Snake’ adalah salah satu contoh permainan paling populer di dunia. Awalnya,

permainan ‘Snake’ adalah permainan bawaan dari telepon genggam merek Nokia.

Walaupun dengan layar monokrom berwarna kuning dan/atau biru, permainan ini

berhasil menjadi ‘candu’ bagi pengguna telepon genggam dari berbagai usia. Sampai

dengan saat ini, permainan ini masih dikembangkan sehingga dapat dimainkan di

perangkat-perangkat yang lebih modern dengan berbagai pengembangan, baik dari

sisi visual, audio, maupun teknis permainannya sendiri (penambahan tingkat

kesulitan, penambahan rintangan, penambahan bonus, dan sebagainya).

Konsep permainan ‘ Snake’ sangat sederhana. Pada awal permainan, terdapat

seekor ular yang berupa garis sepanjang kurang-lebih 3-4 blok dan sebuah makanan

yang berupa sebuah blok. Tugas pemain adalah mengarahkan ular kepada

makanannya. Pada telepon genggam, pemain dapat menggunakan tombol 2 untuk

bergerak ke atas, 4 untuk berbelok ke kiri, 6 untuk berbelok ke kanan, dan 8 untuk

bergerak ke bawah (pada pengembangan versi desktop, dapat menggunakan tombol-

tombol arrow atau WASD). Setelah berhasil mendapatkan makanannya, akan muncul

makanan baru di tempat lain dan tubuh ular akan bertambah panjang sehingga pemain

harus semakin berhati-hati agar ular tidak menabrak badannya sendiri atau dinding

(batas layar). Selain itu, dengan mendapatkan makanan pemain akan mendapatkan

poin. Total poin inilah yang menjadi acuan rangking permainan.

Perancangan permainan ini dibangun bertujuan untuk memodifikasi

permainan ‘ Snake’ sekaligus mengimplementasikan algoritma A*. Karena sejatinya

permainan ini merupakan single player game atau permainan yang dimainkan sendiri,

tetapi pada tugas kali ini, permainan ‘ Snake’ ini akan dikembangkan untuk double


17/42

17

player game dengan komputer sebagai lawannya. Komputer inilah yang dibenamkan

dengan algoritma A* sehingga dapat mencari jalur terpendek dari posisinya saat itu

menuju makanan secara kontinyu. Dengan demikian, diharapkan permainan ini akan

menjadi lebih menarik dan menantang.

Permainan yang akan dikembangkan ini bersifat bersifat object oriented

(berorientasi objek) dengan bahasa pemrograman Java. Adapun tools utama yang

digunakan adalah IDE NetBeans 8.0.

3.2 Model Use Case

Model use case menjelaskan mengenai aktor yang terlibat dengan permainan

yang akan dibangun beserta proses-proses yang ada didalamnya.

3.2.1 Use Case Diagram

Diagram use case dari permainan adalah sebagai berikut:

Gambar 3.1 Use Case Diagram Permainan ‘Snake Versus’


18/42

18

3.2.2 Definisi Aktor

Definisi aktor merupakan penjelasan dari apa yang dilakukan oleh

aktor yang terlibat dalam permainan yang dibangun. Adapun deskripsi dari

aktor yang terlibat dalam permainan sebagai berikut:

No. Aktor Deskripsi

1 User 1. Memilih level kecepatan.

2. Membaca instruksi bagaimana cara menjalankan

permainan.

3.

Memainkan permainan.4. Menghentikan permainan sementara ( pause) dan

melanjutkan kembali permainan (resume).

5. Memilih menggunakan musik atau mute.

Tabel 3.1 Definisi Aktor

3.2.3 Definisi Use Case

Berdasarkan Gambar 3.1, setiap use case yang dapat dideskripsikansebagai berikut:

No. Use Case Deskripsi

1. Pilih level kecepatan Pemain dapat memilih kecepatan berjalan

ular yang akan dimainkan. Terdapat 3 level

kecepatan, yaitu level 1, 2, dan 3. Semakin

tinggi level yang dipilih, maka semakin

tinggi pula kecepatan ular.

2. Membaca instruksi Pemain dapat membaca instruksi bagaimana

cara memainkan/ menjalankan ular pada side


19/42

19

panel di sebelah kanan.

3. Main Pemain memainkan permainan dan

mengarahkan ular menuju makanannya.

3. Pause/ resume permainan Pemain dapat menghentikan permainan

sementara ( pause) dan melanjutkan kembali

permainan (resume).

4. Mute background music Pemain dapat memilih untuk menghentikan

background music (mute) atau tetap

memainkannya.

Tabel 3.2 Definisi Use Case

3.3 Perangkat Lunak

Adapun kebutuhan perangkat lunak utama yang dibutuhkan dalam

pengembangan permainan ini adalah sebagai berikut:

1.

Sistem operasi minimal Windows 72. IDE NetBeans 8.0

3. SDK Java

3.4 Perangkat Keras

Adapun spesifikasi perangkat keras minimum yang digunakan pada

pengembangan permainan ini adalah sebagai berikut:

1. Processor Intel Dual Core 1,9 GHz

2.

RAM 2 GB

3. Harddisk 320 GB

4. Keyboard, monitor


20/42

20

3.5 Layout Antarmuka

Layout antarmuka merupakan rancangan antarmuka yang akan digunakan

sebagai perantara user dengan permainan yang dikembangkan. Layout antarmuka dari

permainan ‘Snake Versus’ adalah sebagai berikut:

3.5.1 Antarmuka Halaman Utama

Gambar 3.2 Antarmuka Halaman Utama

3.5.2 Antarmuka Area Permainan

Gambar 3.3 Antarmuka Area Permainan


21/42

21

Gambar 3.4 Antarmuka Akhir Permainan

Gambar 3.5 Antarmuka Permainan Paused


22/42

22

3.6 Implementasi A*

Gambar 3.6 Kondisi awal

Posisi node awal = Ax : 1, Ay : 1

Posisi node tujuan = goal.x : 3, goal.y : 3

a.

Langkah kesatu

n (1,0) : g (1,0)= 1



= (abs(-2) + abs(-3))

= 5

h_diagonal(n) = min(abs(n.x-goal.x) + abs(n.y-goal.y))



= min 5



23/42

23

h(1,0) = (-5) + (5-(2*(-5)))

= -5 + 15

= 10

f (1,0) = g (1,0)+ h (1,0)

= 1 + 10

= 11

n (2,1) : g (2,1) = 1



= (abs(-1) + abs(-2))

= 3




= min 3


h(2,1) = (-3) + (3-(2*(-3)))

= -3 + 9

= 6

f (2,1) = g (2,1) + h (2,1)

= 1 + 6

= 7

n (1,2) : g (1,2) = 1



= (abs(-2) + abs(-1))


24/42

24

= 3

h_diagonal(n) = min(abs(n.x-goal.x), abs(n.y-goal.y))



= min 3


h(1,2) = (- 3) + (3-(2*(-3)))

= -3 + 9

= 6

f (1,2) = g (1,0) + h (1,0)

= 1 + 6

= 7

Gambar 3.7 Langkah Pertama

Pada Gambar 3.5 terdapat tiga node yang mungkin menjadi best node, yaitu

(1,0) dengan f(n) = 11, (2,1) dengan f(n) = 7, dan (1,2) dengan f(n) = 7. Maka dipilih

node (2,1) dengan biaya terkecil, yaitu 7.


25/42

25

b. Langkah kedua

n (2,0) : g (2,0) = 2


h_orthogonal(2,0) = (abs(2 - 3) + abs(0- 3))

= (abs(-1) + abs(-3))

= 4




= min 4


h(2,0) = (-4) + (4-(2*(-4)))

= -4 + 12

= 8

f (2,0) = g (2,0) + h (2,0)

= 2 + 8

= 10

n (3,1) : g (3,1) = 2



= (abs(0) + abs(-2))

= 2



= min(abs(0)+abs(-2))

= min 2


26/42

26


h(3,1) = (-2) + (2-(2*(-2)))

= -2 + 6

= 4

f (3,1) = g (3,1) + h (3,1)

= 2 + 4

= 6

n (2,2) : g (2,2) = 2



= (abs(-1) + abs(-1))

= 2




= min 2


h(2,2) = (-2) + (2-(2*(-2)))

= -2 + 6

= 4

f (2,2) = g (2,2) + h (2,2)

= 2 + 4

= 6


27/42

27

Gambar 3.8 Langkah Kedua



node (3,1) dengan beberapa pertimbangan, yaitu biaya terkecil (f(n) = 6) dan tidak

menabrak badan snake lawannya.

c. Langkah ketiga

n (3,0) : g (3,0) = 3



= (abs(0) + abs(-3))

= 3




= min 3


28/42

28


h(3,0) = (-3) + (3-(2*(-3)))

= -3 + 9

= 6

f (3,0) = g (3,0) + h (3,0)

= 3 + 6

= 9

n (4,1) : g (4,1) = 3



= (abs(1) + abs(-2))

= 3




= min 3


h(4,1) = (-3) + (3-(2*(-3)))

= -3 + 9

= 6

f (4,1) = g (4,1) + h (4,1)

= 3 + 6

= 9

n (3,2) : g (3,2) = 2



= (abs(0) + abs(-1))


29/42

29

= 1




= min 1


h(3,2) = (-1) + (1-(2*(-1)))

= -1 + 3

= 2

f (3,2) = g (3,2) + h (3,2)

= 3 + 2

= 5

Gambar 3.9 Langkah Ketiga



node (3,2) dengan biaya terkecil, yaitu 5.


30/42

30

d. Langkah keempat

n (4,2) : g (4,2) = 4



= (abs(1) + abs(-1))

= 2




= min 2


h(4,2) = (-2) + (2-(2*(-2)))

= -2 + 6

= 4

f (4,2) = g (4,2) + h (4,2)

= 4 + 4

= 8

n (3,3) : g (3,3) = 4



= (abs(0) + abs(0))

= 0h_diagonal(n) = min(abs(n.x-goal.x) + abs(n.y-goal.y))


= min(abs(0)+abs(0))

= min 0


31/42

31


h(3,3) = (-0) + (0-(2*(-0)))

= -0 + 0

= 0

f (3,3) = g (3,3) + h (3,3)

= 4 + 0

= 4

n (2,2) : g (2,2) = 2



= (abs(-1) + abs(-1))

= 2




= min 2


h(2,2) = (-2) + (2-(2*(-2)))

= -2 + 6

= 4

f (2,2) = g (2,2) + h (2,2)

= 2 + 4= 6


32/42

32

Gambar 3.10 Langkah Keempat

Pada Gambar 3.7 terdapat dua node yang mungkin menjadi best node, yaitu


node (3,3) dengan biaya terkecil, yaitu 4 dan karena (3,3) juga dikenali sebagai node

tujuan maka solusi telah ditemukan.

Gambar 3.11 Hasil


33/42

33

BAB IV

HASIL DAN PEMBAHASAN

4.1 Gambaran Umum Permainan

Permainan ‘Snake Versus’ berawal dari permainan ‘Snake’ yang dimodifikasi

menjadi permainan double player, dimana ular milik user akan ‘berebut’ dengan ular

computer yang sudah dibenami dengan Algoritma A* untuk mendapatkan makanan.

Permainan diawali dengan tampilan antarmuka utama berupa area permainan yang

masih kosong dan sebuah panel di sebelah kanan yang berisi tentang informasi

statistik dan kontrol permainan. Informasi statistik meliputi: fruit score (nilai buah),

total score pemain, fruit eaten (jumlah buah yang telah diperoleh pemain), total score

computer, fruit eaten computer (jumlah buah yang telah diperoleh komputer).

Sedangkan informasi kontrol permainan berisi cara memainkan permainan/

mengubah arah jalannya ular, yaitu dengan menekan tombol panah atas/ W untuk

arah atas, tombol panah bawah/ S untuk arah bawah, tombol panah kanan/ D untuk

arah kanan, tombol panah kiri/ A untuk arah kiri, tombol P untuk menghentikan permainan sementara, dan tombol M untuk mematikan background music.

Selanjutnya, untuk memulai permainan, pemain dapat memilih angka 1/ 2/ 3 untuk

memilih level kecepatan dan menekan tombol Enter.

Permainan dimulai dengan kedua ular berada di tengah area permainan

mengarah ke dua arah yang berlawanan (ular pemain berwarna hijau mengarah ke

atas, dan ular komputer berwarna oranye mengarah ke bawah). Panjang badan kedua

ular masih sebanyak 2 tile, termasuk kepala ular. Buah (obyek berbentuk lingkaran

berwarna merah) akan muncul di posisi yang random di area permainan. Pemain

harus mengarahkan ular masing-masing menuju ke buah tersebut untuk mendapatkan

nilai. Sementara ular komputer akan secara otomatis menuju buah, karena telah

ditanami algoritma A* sehingga ia secara kontinyu akan terus menghitung rute


34/42

34

terpendek dari posisinya saat itu menuju buah. Nilai yang dikandung buah bernilai

awal 100, yang selalu berkurang setiap sepersekian detik, dan akan berhenti di angka

10. Maka, semakin cepat mendapatkan buah, maka semakin tinggi pula nilai yang

akan didapatkan. Setiap kali mendapat buah pula ukuran badan ular, baik ular pemain

maupun komputer akan bertambah satu tile.

Permainan akan berakhir ketika terjadi salah satu di antara kondisi-kondisi di

bawah ini:

1. Salah satu atau kedua ular menabrak dinding pembatas area

permainan.

2.

Salah satu ular atau kedua ular saling menabrak badan ular, baik

badannya sendiri maupun badan musuh.

4.2 Implementasi

4.2.1 Implementasi Antarmuka

Gambar 4.1 Tampilan Awal


35/42

35

Gambar 4.2 Permainan Snake Versus

Gambar 4.3 Akhir Permainan

4.2.2 Implementasi Algoritma A*

Algoritma A-Star (A*) ini pertama kali diperkenalkan pada 1968 oleh

Peter Hart, Nils Nilsson, dan Bertram Raphael. Dalam ilmu komputer, A*

(yang diucapkan dengan ― A star) merupakan salah satu algoritma pencarian

graf terbaik yang mampu menemukan jalur dengan biaya pengeluaran paling


36/42

36

sedikit dari titik permulaan yang diberikan sampai ke titik tujuan yang

diharapkan (dari satu atau lebih mungkin tujuan).

Rumus dari Algoritma A-Star sebagai berikut:

f(x) = g(x) + h(x)

dengan h(x) : nilai heuristik yang diterima

g(x) : banyaknya langkah untuk mencapai titik tujuan

Pertama kali yang dilakukan adalah mendapatkan posisi kepala ular

pada saat itu. Selanjutnya agar ular dapat sampai ke titik tujuan (buah), ular

harus menghitung semua kemungkinan jalan, yaitu dengan mencari dan

menghitung nilai f(x) kotak-kotak di sekitarnya. Penentuan kotak-kotak


37/42

37

sekitar berdasarkan arah gerak ular pada saat itu. Apabila ular sedang

mengarah ke atas, maka kotak sekitar yang akan dihitung nilai f(x) nya adalah

kotak di sebelah atas, kanan, dan kiri kepala ular. Apabila ular sedang

mengarah ke bawah, maka kotak sekitar yang akan dihitung nilai f(x) nya

adalah kotak di sebelah bawah, kanan, dan kiri kepala ular. Apabila ular

sedang mengarah ke kanan, maka kotak sekitar yang akan dihitung nilai f(x)

nya adalah kotak di sebelah atas, kanan, dan bawah kepala ular. Apabila ular

sedang mengarah ke kiri, maka kotak sekitar yang akan dihitung nilai f(x) nya

adalah kotak di sebelah atas, kiri, dan bawah kepala ular.

Setelah mendapatkan list semua kotak sekitar yang akan dihitung nilai

f(x) nya, selanjutnya adalah memanggil fungsi hitungNilaiF() untuk masing-

masing kotak sekitar.


38/42

38

Di dalam fungsi hitungNilaiF() memanggil fungsi lain yaitu,

hitungNilaiH() dan hitungNilaiG(). Fungsi hitungNilaiH() adalah untuk

menghitung nilai heuristik yang diterima dengan cara menghitung orthogonal

dan diagonal antara kotakSekitar dengan titik tujuan (buah). Fungsi

hitungNilaiG() merupakan fungsi untuk menghitung banyaknya langkah yang

sedang dipakai untuk mencapai titik tujuan (buah).

Setelah nilai f(x) setiap kotak sekitar telah didapatkan, langkah

berikutnya adalah membandingkan nilai f(x) dari tiap kotak sekitar. Nilai f(x)

yang paling rendah akan dipilih untuk langkah selanjutnya.


39/42

39

Nilai f(x) yang paling rendah akan dipilih dan ular akan diarahkan

menuju kotak sekitar yang nilai f(x) nya lebih rendah menggunakan Direction.

4.4 Evaluasi

Dari permainan yang dikembangkan dilakukan beberapa pengujian, yaitu

pengujian terhadap tampilan, fungsionalitas, dan algoritma A*. Pengujian dilakukan

untuk mengetahui apakah permainan telah sesuai dengan perancangan sistem pada

Bab III/

4.4.1 Pengujian terhadap Tampilan

Pengujian terhadap tampilan yaitu memastikan bahwa keseluruhan

tampilan aplikasi permainan sempurna, antara lain: tidak ada obyek-obyek

yang saling tumpang tindih atau terpotong; pemilihan warna tidak terlalu

kontras sehingga menyebabkan mata cepat lelah ataupun terlalu muda

sehingga sukar dilihat; penulisan istilah sempurna tanpa ada salah eja atau

salah penafsiran. Hasil yang diperoleh dari pengujian terhadap tampilan

adalah sangat baik, karena telah memenuhi setiap aspek yang diuji.

4.4.2 Pengujian terhadap Use Case

Pengujian terhadap use case yaitu untuk memastikan bahwa

keseluruhan fitur yang dirancang telah dapat dipenuhi. Pada permainan ‘Snake

Versus’ ini terdapat enam fitur yang ditawarkan, yaitu pilih level kecepatan,

membaca instruksi, main, pause/ resume permainan, dan mute background

music. Hasil yang diperoleh dari pengujian terhadap use case adalah sangat

baik, karena telah memenuhi seluruh fitur yang ditawarkan.

4.4.3 Pengujian terhadap Fungsionalitas

Pengujian terhadap fungsionalitas yaitu memastikan bahwa

keseluruhan fungsi aplikasi permainan sempurna, antara lain: tombol Enter

untuk memulai permainan baru, tombol P untuk menghentikan dan


40/42

40

melanjutkan kembali permainan, tombol M untuk menghentikan background

music, tombol panah atas/ W untuk mengarahkan ular ke atas, tombol panah

bawah/ S untuk mengarahkan ular ke bawah, tombol panah kanan/ D untuk

mengarahkan ular ke kanan, tombol panah kiri/ A untuk mengarahkan ular ke

kiri, nilai awal buah adalah 100, nilai buah akan terus berkurang setiap

sepersekian detik dan berhenti di angka 10, total score pemain maupun

komputer akan bertambah sesuai nilai buah setiap berhasil mendapatkan buah,

jumlah fruit eaten pemain maupun komputer akan bertambah setiap kali

berhasil mendapatkan buah, dan panjang tubuh ular, baik milik pemain

maupun komputer akan bertambah satu tile setiap berhasil mendapatkan buah.

Hasil yang diperoleh dari pengujian terhadap fungsionalitas adalah sangat

baik, karena telah memenuhi setiap aspek yang diuji.

4.4.3 Pengujian terhadap Algoritma A*

Pengujian terhadap algoritma A* yaitu memastikan bahwa ular

komputer secara kontinyu menghitung rute terpendek dari posisi saat itu

menuju posisi buah. Hasil yang diperoleh dari pengujian terhadap algoritma

A* adalah sangat baik, karena ular komputer berhasil menghitung rute

terpendek dan langsung mengarah ke posisi buah secara otomatis, bahkan

setelah buah berpindah posisi.


41/42

41

BAB V

PENUTUP

5.1 Simpulan

Permainan ‘Snake Versus’ berawal dari permainan ‘Snake’ yang dimodifikasi

menjadi permainan double player, dimana ular milik user akan ‘berebut’ dengan ular

computer yang sudah dibenami dengan Algoritma A* untuk mendapatkan makanan.

Computer akan secara kontinyu menghitung jalur terpendek dari posisinya menuju

makanan.

Permainan ini menawarkan enam fitur utama, yaitu pilih level kecepatan,

membaca instruksi, main, pause/ resume permainan, dan mute background music.

Berdasarkan hasil pengujian, permainan ini telah berhasil mengimplementasikan

algoritma A* dan seluruh fitur yang ditawarkan baik secara fungsionalitas sekaligus

melalui tampilan yang menarik.

5.2 SaranBeberapa hal yang masih dapat dikembangkan dari permainan ini adalah:

- Menambahkan level tingkat kecepatan laju ular.

- Menambahkan tingkat kesulitan permainan dengan menambahkan

penghalang-penghalang di area permainan.

- Menambahkan buah bonus dengan nilai yang lebih besar setiap generate

sekian buah sekali, dan dengan batas waktu yang lebih singkat.

- Mengoptimalkan algoritma A* pada ular komputer agar lebih efektif

mendapatkan makanannya.


42/42

DAFTAR PUSTAKA

Setiawan, Willy. (2011) Pembahasan Pencarian Lintasan Terpendek Menggunakan

Algoritma Dijkstra dan A*. Makalah IF3051 Strategi Algoritma STEI ITB:

tidak diterbitkan.

Unknown. (t.thn.). Dipetik May 2015, dari

http://repository.usu.ac.id/bitstream/123456789/42380/4/Chapter%20II.pdf

Unknown. (t.thn.). Dipetik May 2015, dari

http://elib.unikom.ac.id/files/disk1/483/jbptunikompp-gdl-dewinurulr-24110-5-

unikom_d-i.pdf

Unknown. (2008). Dipetik May 2015, dari http://thesis.binus.ac.id/Asli/Bab2/2008-1-

00087-IF%20Bab%202.pdf

Unknown. (2010, 2). Dipetik May 2015, dari

http://library.binus.ac.id/eColls/eThesisdoc/Bab2/2010-2-00250-

if%20bab%202.pdf

Unknown. (2012, November 27). Dipetik May 2015, dari

http://elib.unikom.ac.id/files/disk1/439/jbptunikompp-gdl-dwirezekim-21927-

11-12uniko-i.pdf

laporan rancang bangun permainan snake versus dengan algoritma a star

Documents