Rabu, 04 Juli 2012

Game : Horrible racing

1.1. Konsep AI Smiley adalah karakter yang dimainkan oleh pemain dalam permainan ini. Pemain harus bisa menghindari rintangan yang ada dan menyelesaikan level permainan untuk menuju garis finish. Penyelesaian : 1. Identifikasi ruang keadaan Permasalahan ini dapat dilambangkan dengan ( 1 karakter smiley yang berbentuk kotak dan banyak karakter yang digunakan untuk menjadi halangan atau rintangan ). 2. Keadaan awal & tujuan Keadaan awal = halangan ada di setiap jalur atau jalan dengan posisi yang mengacak, 1 smiley atau pemain. Keadaan tujuan = smiley atau pemain harus terus menghindar dari tabrakan sampai score tertinggi. 3. Aturan-aturan a. Pemain harus melewati jalan atau jalur sampai menuju finish. b. Pemain tidak boleh bertabrakan dengan rintangan yang ada. c. Untuk menang dalam permainan ini, life point minimal 1. 1.2. Algoritma Penulisan ini akan membahas implementasi algoritma A* dan algoritma Branch and Bound dalam pemodelan AI dalam permainan Horrible Racing. 1.2.1. Algoritma A* Algoritma A* ( A-star algorithm ) dipakai untuk pathfinding. Pathfinding dilakukan untuk mencari jalan paling dekat yang dapat ditempuh dari satu tempat ke tempat yang lain. Algoritma A* didasari oleh sebuah persamaan sebuah empat benda yang sedang berjalan dari satu tempat ke tempat yang lain : F(s) = G(s) + H(s). Dimana : F(s) adalah jarak dari awal ke tempat akhir, G(s) adalah jarak yang sudah ditempuh oleh benda itu dari tempat awal, dan H(s) adalah jarak yang sudah ditempuh oleh benda itu berada ke tempat akhir. Beberapa terminologi dasar yang terdapat pada algoritma ini adalah starting point, simpul (nodes), A, open list, closed list, harga (cost), halangan (unwalkable). • Starting point adalah sebuah terminologi untuk posisi awal. • A adalah simpul atau node yang sedang dijalankan dalam algoritma. • Open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting point. • Closed list adalah tempat menyimpan data simpul sebelum A. • Harga (F) adalah nilai yang diperoleh dari penjumlahan nilai G, jumlah nilai tiap simpul dalam jalur terpendek dari starting point ke A, dan H, jumlah nilai perkira dari sebuah simpul sampai di simpul terakhir atau tujuan. • Simpul tujuan yaitu simpul yang dituju. • Rintangan atau halangan adalah sebuah atribut yang menyatakan bahwa sebuah simpul tidak dapat dilalui oleh A. 1.2.2. Algoritma Branch and Bound Persoalan pencarian jalan (path-finding) adalah persoalan mencari lintasan dari titik awal menuju titik akhir yang ditentukan melewati hambatan yang ada. Cara penyelesaian persoalan path-finding dengan menggunakan algoritma brounch and bound dengan menggunakan suatu fungsi heuristic sederhana. Algoritma branch and bound juga merupakan metode pencarian di dalam ruang solusi secara sistematis. Pada algoritma B&B, pencarian ke simpul solusi dapat dipercepat dengan memilih simpul hidup berdasarkan nilai (cost). Pada praktiknya, nilai batas untuk setiap simpul umumnya berupa perkiraan. Fungsi heuristic untuk menghitung perkiraan nilai dapat dinyatakan secara umum sebagai berikut : c(i) = f(i) + g(i) dimana : c(i) = ongkos untuk simpul i f(i) = ongkos mencapai simpul i dari akar g(i) = ongkod mencapai simpul tujuan dari simpul akar i Nilai c digunakan untuk mengurutkan pencarian. Simpul berikutnya yang dipilih untuk diekspansi adalah simpul yang memiliki c minimum. Algoritma B&B jika ditulis secara prosedural : 1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul solusi (goal node), maka solusi telah ditemukan. Stop. 2. Jika Q kosong, tidak ada solusi. Stop. 3. Jika Q tidak kosong, pilih dari antrian Q simpul i yang mempunyai c(i) paling kecil. Jika terdapat beberapa simpul i yang memenuhi, pilih satu secara sembarang. 4. Jika simpul i adalah simpul solusi, berarti solusi sudah ditemukan, stop. Jika simpul i bukan simpul solusi, maka bangkitkan semua anak-anaknya. Jika i tidak mempunyai anak, kembali ke langkah 2. 5. Untuk setiap anak j dari simpul i, hitung c(i), dan masukkan semua anak-anak tersebut ke dalam antrian Q. 6. Kembali ke langkah 2. Berikut ini adalah algoritma yang digunakan dalam permainan ini : 1. Buat jalur serta pasang karakter di tengah jalur dan pasang juga rintangan di dalam jalur. 2. Acak angka untuk menentukan posisi awal karakter dan rintangan. 3. Rintangan bergerak mendekati untuk menabrakan ke pemain menggunakan jalur terpendek untuk menghampirinya. 4. Karakter bergerak ke kanan atau ke kiri untuk menghindari tabrakan. 5. Jika karakter tertabrak maka point untuk nyawa dari pemain akan berkurang. 6. Jika karakter terus menghindar dari tabrakan maka score akan terus bertambah. 1.3. Konsep Permainan Konsep permainan yang diterapkan dalam permainan ini adalah pemain harus berjalan melalui jalur atau track sampai menuju finish, namun terdapat rintangan yang harus dilewati pemain yaitu harus menghindari musuh dan jangan sampai tertabrak. Dalam permainan ini musuh pemain adalah semua karakter yang digunakan sebagai penghalang. Agar tidak bertabrakan, pemain harus berhati-hati. Hal yang harus dilakukan adalah menghindari rintangan tersebut dengan bergerak ke kiri dan ke kanan dengan menggunakan tombol panah kiri () dan panah kanan () yang ada pada keyboard. Ketika pemain berhasil berjalan tanpa hambatan atau melewati satu rintangan maka poin akan bertambah satu poin, poin ini akan terus bertambah sesuai dengan kelipatannya dan disaat nilai yang didapat mencapai poin 50 dan kelipatannya, maka kecepatan rintangan tersebut akan semakin bertambah. Namun apabila pemain bertabrakan, maka life point akan berkurang satu, permainan akan berhenti jika pemain bertabrakan dengan rintangan sebanyak nyawa yang dimiliki. Jika sisa nyawa pemain habis, maka pemain dinyatakan kalah. Pemain dinyatakan menang jika semua rintangan dapat dilewati dengan baik, sisa nyawa yang dimiliki minimal satu. Jika ingin tambah seru bisa memilih menu +level dalam menu bar yang ada, maka kecepatan rintangan tersebut akan bertambah. . Implementasi Kode Program Pada bagian ini penulis akan membahas dalam pembuatan aplikasi game Horrible Racing yaitu implementasi kode program. Penulis hanya menyediakan potongan kode program dalam implementasi kode program. Untuk melihat program lengkap dapat dilihat pada lampiran program dan output. Tampilan awal dan proses program Koding berikut adalah untuk menentukan ukuran window, warna background, posisi awal pemain, dan proses permainan. Di kondisi awal sebelum dimodifikasi ,permainan horribel racing disini memiliki warna backgroud biru muda danjumlah life point sebanyaksepuluh kali. Setelahdimodifikasibackgroundmenjadiwarnabiru muda. ?- G_Lifes:=10, G_Counter:=0, G_Times:=5, G_Score:=0, G_Depth:=10, G_Crashed:=0, G_Col1:=0, G_Col2:=0, G_Col3:=0, G_Pos:=2, G_OldPos:=GPos, G_Pen0:= pen(1, rgb(155, 155, 255)), G_Pen1:= pen(1, rgb(255, 255, 255)), G_Brush0:= brush(rgb(233, 250, 230)), G_Brush1:= brush(rgb(100, 0, 0)), G_Brush2:= brush(rgb(19, 248, 8)), G_Brush3:= brush(rgb(231, 19, 201)), G_Brush4:= brush(rgb(255, 255, 255)), G_Brush5:= brush(rgb(0, 0, 0)), window(G_Wnd, _, win_func(_), "Horrible Racing", 120, 0, 220, 620). Tampilan Pilihan menu serta kendali Koding berikut kita gunakan untuk menambahkan pilihan pada menu barnya.Pada program awalnya,menu tersebut belum tersedia,tetapi setelah di modifikasi ada penambahan pada menu barnya yang antara lain tambah level,keluar dan info mengenai kelompok yang mengerjakan projek ini. win_func(init):- G_Timer:=set_timer(G_Wnd, 0.15, time_func), menu(normal, _, _, menu_baru(_), "&+Level"), menu(normal, _, _, menu_keluar(_), "&Keluar"), menu(right,_,_,info(_),"&info"). menu_baru(press) :- G_P = 0, G_Clicked = 0, G_Timer:=set_timer(G_Wnd, 0.15, time_func). menu_keluar(press) :- close_window(_). info(press):- message("Info", "Kelompok:\nDhimas\nFany\nDeshita\nDhieta", i), write("OK"), nl. win_func(key_down(37, _)) :- (G_Pos> 1 -> G_OldPos:=G_Pos, G_Pos:=G_Pos - 1), draw_car. win_func(mouse_click(_, _)) :- (G_Pos> 1 -> G_OldPos:=G_Pos, G_Pos:=G_Pos - 1), draw_car. win_func(key_down(39, _)) :- (G_Pos< 3 -> G_OldPos:=G_Pos, G_Pos:=G_Pos + 1), draw_car. win_func(r_mouse_click(_, _)) :- (G_Pos< 3 -> G_OldPos:=G_Pos, G_Pos:=G_Pos + 1), draw_car. win_func(paint):- draw. Tampilan saat karakter di gerakkan Koding berikut ini merupakan koding yang digunakan untuk membentuk karakter saat karakter tersebut berpindah tempat.Pada awalnya tampilan pada karakter masih berbentuk bulat saat di gerakkan,tetapi setelah di modifikasi maka karakter disesuaikan dengan keinginan pengedit. draw_car:- pen(G_Pen0), brush(G_Brush0), Pos:=G_Pos*60- 40, pen(G_Pen1), brush(G_Brush1), rect(Pos, 420, Pos+40, 460), Pos:=G_OldPos*60- 40, brush(G_Brush5), rect(Pos+7- G_Crashed, 428- G_Crashed, Pos+15+G_Crashed, 439+G_Crashed), brush(G_Brush5), rect(Pos+25- G_Crashed, 428- G_Crashed, Pos+33+G_Crashed, 439+G_Crashed), brush(G_Brush4), rect(Pos+13- G_Crashed, 447- G_Crashed, Pos+27+G_Crashed, 453+G_Crashed). Tampilan Untuk Karakter Diam dan Karakter Rintangan Koding berikut ini merupakan koding yang digunakan untuk membentuk karakter diam dan karakter yang digunakan untuk membuat rintangan. Bentuk dari karakter yang digunakan untuk rintangan dengan bentuk ellipse dan kotak. draw:- pen(G_Pen0), brush(G_Brush0), rect(0, 0, 300, 600), color_text_back(G_Wnd, rgb(155, 155, 255)), color_text(G_Wnd, rgb(255, 255, 0)), text_out(10, 512, "Score : "+print(G_Score)), text_out(10, 530, "Lifes : "+print(G_Lifes)), Pos:=G_Pos*60- 40, pen(G_Pen1), brush(G_Brush1), rect(Pos, 420, Pos+40, 460), brush(G_Brush2), ellipse(Pos+7- G_Crashed, 428- G_Crashed, Pos+15+G_Crashed, 439+G_Crashed), brush(G_Brush2), ellipse(Pos+25- G_Crashed, 428- G_Crashed, Pos+33+G_Crashed, 439+G_Crashed), brush(G_Brush3), ellipse(Pos+13- G_Crashed, 447- G_Crashed, Pos+27+G_Crashed, 453+G_Crashed), Mask:= 1<< (G_Depth- 1), for(I, 1, G_Depth), ( (G_Col1 /\ Mask> 0 -> ellipse(20, I*40- 25, 47, I*40, 10, 10)), (G_Col2 /\ Mask> 0 -> round_rect(80, I*40- 20, 120, I*40, 10, 10)), (G_Col3 /\ Mask> 0 -> ellipse(140, I*40- 20, 170, I*40, 20, 70)), Mask:= Mask>> 1, fail Tampilan Untuk Menggerakkan Rintangan dan Penentuan Score Berikutadalahkoding yang digunakanuntukmenggerakkanbalok yang dijalankanolehkomputerdengankonsep AI untukmenghalangipergerakanpemainsertapenambahan level saatnilaipemainberadapadaposisi yang ditentutkanuntukmenambah level. time_func(end):- G_Counter:=G_Counter+1, (G_Counter>= G_Times -> G_Score:=G_Score+1, G_Crashed:=0, Pos:=random(300) // 100 + 1, put_trap(Pos), once(crash(Z)), (Z =:= G_Pos -> beep, G_Lifes:= G_Lifes- 1, G_Crashed:=3), (G_Lifes =< 0 -> kill_timer(G_Wnd, G_Score=20)), G_Col1:=G_Col1>>1, G_Col2:=G_Col2>>1, G_Col3:=G_Col3>>1, G_Counter:=0, G_Times:= (200- G_Score) // 40, draw ). Tampilan Untuk Menentukan Posisi Rintangan Program inidigunakanuntukmenetukanposisibaloksecaraacakdanjugamembuatposisilawandanpemainberadapadaposisi yang samaakandinyatakanmenabrakdanlife point akanberkurang. put_trap(1):- G_Col1:= G_Col1 \/ (1<< G_Depth). put_trap(2):- G_Col2:= G_Col2 \/ (1<< G_Depth). put_trap(3):- G_Col3:= G_Col3 \/ (1<< G_Depth). crash(1):- G_Col1 /\ 1> 0, G_Pos =:= 1. crash(2):- G_Col2 /\ 1> 0, G_Pos =:= 2. crash(3):- G_Col3 /\ 1> 0, G_Pos =:= 3. crash(4).