Algoritma Breath First Search (BFS) dalam Game Tebak Kata

Game Tebak Kata

Permainan kata merupakan salah satu jenis permainan yang menarik karena dapat menantang pemainnya untuk mengeluarkan kreativitasnya dalam mengolah kata. Rangkai kata merupakan salah satu contohnya. Rangkai kata merupakan kata acak yang dibentuk  dari kata lain yang telah   diubah susunan atau jumlah karakter di dalamnya. Pada pengolahan kata  ini,  pemain  akan  memasukan  kata  awal  yang ingin  dibangkitkan  Rangkai  kata  nya. Kemudian pemain akan menebak kata yang merupakan Rangkai kata dari kata awal. Algoritma Breadth First Search yang mengeksplorasi setiap cabang   dari setiap node sangat tepat untuk diterapkan pada permasalahan ini. Algoritma ini akan membangkitkan pohon solusi secara dinamis bersamaan dengan  dilakukannya proses pencarian solusi.

Peraturan permainan

Pertama pemain akan diminta untuk memasukkan kata yang ingin dibangkitkan Kata Acaknya. Setelah itu pemain akan memasukkan tebakan kata yang diasumsikan sebagai kata yang dibangkitkan dari kata awal. Pemain akan mendapat nilai apabila kata tebakannya merupakan salah satu kata yang dibangkitkan oleh algoritma BFS. Nilai yang didapat bergantung dari jumlah karakter kata tebakan. Semakin  banyak karakter tebakan, semakin sulit dan apabila jawaban benar, pemain akan memperoleh nilai yang tinggi pula. Dalam implementasinya, diperlukan struktur data Queue dan pohon.

Graf Ruang Solusi

Agar lebih jelas, akan digunakan contoh untuk menentukan Graf Ruang Solusinya

Misal :

Kata awal yang ingin dibangkitkan  : katakana

Tebakan pemain  : anak

Setiap karakter dalam kata awal diwakili oleh satu symbol status. Dalam hal ini setiap karakter diberi penomoran sebagai berikut :

Tabel 1 Tabel pemetaan status karakter

K	A	T	A	K	A	N	A
1	2	3	4	5	6	7	8

 Dari penomoran status di atas dapat dibentuk graf ruang solusi sebagai berikut :

Setelah melihat graf tersebut, terdapat banyak sekali kemungkinan solusi, maka saya menggunakan algoritma Breadth First Search untuk mencari solusinya.

 

Penjelasannya adalah sebagai berikut

Fungsi Utama :

Prosedur WordUnscrambler(Tebakan : String, node: int)

Prekondisi :

Dalam prosedur ini kami mengambil asumsi bahwa setiap node telah merepresentasikan karakter yang diwakilinya, Perubahan dari status ke status (dari node ke anaknya) diasumsikan sebagai operasi string untuk membentuk kata. Kemudian kata tebakan harus lebih kecil dari kata awal.

1. Masukkan node awal ke Queue
2. Set Kedalaman dengan 0
3. Ambil kepala Queue
4. Bangkitkan semua anak
5. Jika anak memenuhi syarat push ke Queue
6. Jika memenuhi solusi stop, jika tidak ulangi langkah 3 sampai kedalaman maks
7. Cetak solusi dan perhitungan skor berdasarkan kedalaman 

Fungsi Bantuan :

1.    Bangkitkan anak

Prosedur ini membangkitkan anak dari Node dengan elemen status yang tersisa

2.   Fungsi isBagian(input : String,String) Fungsi ini memeriksa apakah Node tersebut memenuhi syarat atau merupakan bagian kata dari tebakan

Sebagai contoh, Saya akan  menggunak contoh persoalan yang telah ada di atas. Secara umum pohon yang dibentuk adalah sebagai berikut

Pada kedalaman 1, anak yang memenuhi kriteria akan  dimasukan  ke dalam  queue.  Lalu  dari  anak  yang masuk queue tadi dibangkitkan anaknya. Dalam gambar di atas status 2 akan dimasukkan ke queue karena memenuhi criteria. Namun sebenarnya yang dibangkitkan anaknya bukan  cuma  status 2, namun  juga  status 4,6,8.  Namun karena status­status itu merepresentasikan hal yang sama, maka tidak saya gambarkan, karena saya anggap hasilnya akan  sama  dengan  anak­anak  yang  dibangkitkan  oleh status ke 2.Setiap kedalaman akan dilakukan operasi yang sama, sampai kedalaman maksimal atau saat CurrentNode adalah solusi.

Dengan melihat gambar di atas terlihat jelas keuntungan BFS dalam pencarian solusi ini, karena BFS mengunjungi anak secara melebar. Sehingga untuk kasus dimana  tebakan  yang  lebih  sedikit  dimasukkan  pohon statsu akan berhenti pada node tersebut tanpa harus melangkah lebih dalam.

sumber :  informatika.stei.itb.ac.id/~rinaldi.../MakalahSTMIK2007-084.pdf

Membuat Meja Menggunakan Blender

Blender adalah perangkat lunak untuk grafis 3 dimensi yang gratis dan populer di kalangan desainer. Blender dapat digunakan untuk membuat animasi 3 dimensi. Perangkat lunak ini juga memiliki fitur untuk membuat permainan. Blender tersedia untuk berbagai sistem operasi, seperti: Microsoft Windows, Mac OS X, Linux, IRIX, Solaris, NetBSD, FreeBSD, OpenBSD. Perangkat lunak ini berlisensi GPL dan kemudian kode sumbernya tersedia dan dapat diambil siapa saja.

Disini saya akan menjelaskan mengenai langkah-langkah untuk membuat sebuah objek pada Blender. Objek yang akan dibuat yaitu sebuah objek sederhana yaitu sebuah meja. Berikut langkah-langkahnya yang dapat dilakukan untuk membuat sebuah objek pada Blender :

* Langkah yang pertama yang harus dilakukan untuk membuat sebuah objek pada Blender, pastinya yaitu kita buka terlebih dahulu software blender tersebut.

* Kemudian setelah kita berada pada tampilan awal dari blender tersebut, kita tambahkan sebuah objek untuk kita jadikan sebagai mejanya. Kita pilih add > mess > cube . kemudian akan muncul bentuk kubus pada blender. tampilannya adalah sebagai berikut :

* untuk merubah bentuk kubus menjadi persegi panjang, kita harus mengatur ukurannya terlebih dahulu yaitu dengan menggunakan scale dengan mode (ctrl + alt + s). dengan menggunakan mode ini maka tanda vektor panah akan mengalami perubahan. Klik pada arah vektor mana kita mau memanjangkan kubus tersebut. Klik panah atau vektor x ke kanan untuk memanjangkannya ke kanan, lalu klik panah biru atau vektor y ke bawah untuk menipiskan kubus tersebut.

Ž * Langkah yang ketiga yaitu kita tambahkan sebuah objek untuk kita jadikan sebagai kaki mejanya. Kita pilih add -> mesh -> cilinder. atur ukuran agar menyerupai kaki meja seperti langkah sebelumnya. untuk membuat kaki meja lainnya cukup dengan menduplikat kaki meja yang sudah dibuat yaitu dengan cara (shift + D ) atau dengan edit -> duplicate.

 * Jika kita telah selesai mendesain keseluruhan objek hingga objek-objek tersebut meyerupai sebuah meja pada umumnya, maka akan terlihat seperti pada tampilan berikut.

Untuk dapat melihat hasil akhir dari objek meja yang tadi telah kita desain tekan f12 lalu akan tampil seperti berikut :

Pemodelan Grafis

Pemodelan adalah membentuk suatu benda-benda atau obyek. Membuat dan mendesain obyek tersebut sehingga terlihat seperti hidup. Sesuai dengan obyek dan basisnya, proses ini secara keseluruhan dikerjakan di komputer. Melalui konsep dan proses desain, keseluruhan obyek bisa diperlihatkan secara 3 dimensi, sehingga banyak yang menyebut hasil ini sebagai pemodelan 3 dimensi (3D modelling).

Ada beberapa aspek yang harus dipertimbangkan bila membangun model obyek, kesemuanya memberi kontribusi pada kualitas hasil akhir. Hal-hal tersebut meliputi metoda untuk mendapatkan atau membuat data yang mendeskripsikan obyek, tujuan dari model, tingkat kerumitan, perhitungan biaya, kesesuaian dan kenyamanan, serta kemudahan manipulasi model. Proses pemodelan 3D membutuhkan perancangan yang dibagi dengan beberapa tahapan untuk pembentukannya. Seperti obyek apa yang ingin dibentuk sebagai obyek dasar, metoda pemodelan obyek 3D, pencahayaan dan animasi gerakan obyek sesuai dengan urutan proses yang akan dilakukan.

a. Motion Capture/Model 2D

Yaitu langkah awal untuk menentukan bentuk model obyek yang akan dibangun dalam bentuk 3D. Dalam tahap ini proses penentuan obyek 2D memiliki pengertian bahwa obyek 2D yang akan dibentuk merupakan dasar pemodelan 3D. Tahap rekayasa hasil obyek 2D dapat dilakukan dengan aplikasi program grafis seperti Adobe Photoshop dan lain sebagainya, pada tahap pemodelan 3D, pemodelan yang dimaksud dilakukan secara manual. Dengan basis obyek 2D yang sudah ditentukan sebagai acuan. Pemodelan obyek 3D memiliki corak yang berbeda dalam pengolahannya, corak tersebut penekanannya terletak pada bentuk permukaan obyek.

b. Dasar Metode Modeling 3D

Ada beberapa metode yang digunakan untuk pemodelan 3D. Ada jenis metode pemodelan obyek yang disesuaikan dengan kebutuhannya seperti dengan nurbs dan polygon ataupun subdivision. Modeling polygon merupakan bentuk segitiga dan segiempat yang menentukan area dari permukaan sebuah karakter. Sedangkan Modeling dengan NURBS (Non-Uniform Rational Bezier Spline) merupakan metode paling populer untuk membangun sebuah model organik. Kurva pada Nurbs dapat dibentuk dengan hanya tiga titik saja. Dibandingkan dengan kurva polygon yang membutuhkan banyak titik (verteks) metode ini lebih memudahkan untuk dikontrol. Satu titik CV (Control verteks) dapat mengendalikan satu area untuk proses tekstur.

c. Proses Rendering

Rendering adalah proses akhir dari keseluruhan proses pemodelan ataupun animasi komputer. Dalam rendering, semua data-data yang sudah dimasukkan dalam proses modeling, animasi, texturing, pencahayaan dengan parameter tertentu akan diterjemahkan dalam sebuah bentuk output. Dalam standard PAL system, resolusi sebuah render adalah 720 x 576 pixels. Bagian rendering yang sering digunakan:

· Field Rendering. Field rendering sering digunakan untuk mengurangi strobing effect yang disebabkan gerakan cepat dari sebuah obyek dalam rendering video.

· Shader. Shader adalah sebuah tambahan yang digunakan dalam 3D software tertentu dalam proses special rendering. Biasanya shader diperlukan untuk memenuhi kebutuhan special effect tertentu seperti lighting effects, atmosphere, fog dan sebagainya.

d. Texturing
Proses texturing ini untuk menentukan karakterisik sebuah materi obyek dari segi tekstur. Untuk materi sebuah object bisa digunakan aplikasi properti tertentu seperti reflectivity, transparency, dan refraction. Texture kemudian bisa digunakan untuk meng-create berbagai variasi warna pattern, tingkat kehalusan/kekasaran sebuah lapisan object secara lebih detail.

e. Image dan Display

Merupakan hasil akhir dari keseluruhan proses dari pemodelan. Biasanya obyek pemodelan yang menjadi output adalah berupa gambar untuk kebutuhan koreksi pewarnaan, pencahayaan, atau visual effect yang dimasukkan pada tahap teksturing pemodelan. Output images memiliki Resolusi tinggi berkisar Full 1280/Screen berupa file dengan JPEG,TIFF, dan lain-lain. Dalam tahap display, menampilkan sebuah bacth Render, yaitu pemodelan yang dibangun, dilihat, dijalankan dengan tool animasi. Selanjutnya dianalisa apakah model yang dibangun sudah sesuai tujuan. Output dari Display ini adalah berupa *.Avi, dengan Resolusi maksimal Full 1280/Screen dan file *.JPEG.

Ada beberapa metode yang digunakan untuk pemodelan 3D. Metode pemodelan obyek disesuaikan dengan kebutuhannya seperti dengan nurbs dan polygon ataupun subdivision. Modeling polygon merupakan bentuk segitiga dan segiempat yang menentukan area dari permukaan sebuah karakter. Setiap polygon menentukan sebuah bidang datar dengan meletakkan sebuah jajaran polygon sehingga kita bisa menciptakan bentuk-bentuk permukaan. Untuk mendapatkan permukaan yang halus, dibutuhkan banyak bidang polygon. Bila hanya digunakan sedikit polygon, maka object yang didapatkan akan terbagi menjadi pecahan-pecahan polygon.

Sedangkan Modeling dengan Nurbs (Non-Uniform Rational Bezier Spline) adalah metode paling populer untuk membangun sebuah model organik. Hal ini dikarenakan kurva pada Nurbs dapat dibentuk dengan hanya tiga titik saja. Dibandingkan dengan kurva polygon yang membutuhkan banyak titik (verteks) metode ini lebih memudahkan untuk dikontrol. Satu titik CV (Control verteks) dapat mengendalikan satu area untuk proses tekstur.

Desain permodelan grafik sangat berkaitan dengan grafik komputer. Berikut adalah kegiatan yang berkaitan dengan grafik komputer:

1. Pemodelan geometris : menciptakan model matematika dari objek-objek 2D dan 3D.

2. Rendering : memproduksi citra yang lebih solid dari model yang telah dibentuk.

3. Animasi : Menetapkan/menampilkan kembali tingkah laku/behaviour objek bergantung waktu.

4. Graphics Library/package (contoh : OpenGL) adalah perantara aplikasi dan display hardware(Graphics System).

5. Application program memetakan objek aplikasi ke tampilan/citra dengan memanggil graphics library.

6. Hasil dari interaksi user menghasilkan/modifikasi citra.

7. Citra merupakan hasil akhir dari sintesa, disain, manufaktur, visualisasi dll.

* Membentuk karakter 3D

Sebelum membuat karakter, kita harus menentukan terlebih dahulu bentuk/benda apa yang ingin kita buat. kita juga harus mengetahui karakteristik dari benda tersebut seperti bentuk, sifat dan warnanya. Apabila bentuk tersebut berupa benda seperti pohon, maka bentunya adalah pipa padat. Sifat yang dimilikinya adalah sifat kayu yaitu kuat, tinggi dan memiliki daun dan akar. Apabila bentuknya berupa manusia maka bentuknya seperti manusia, mempunyai tangan, kaki, mata, hidung mulut, badan, rambut, dan lain-lain. Karakter manusia bermacam-macam jika dilihat dari sifat ada yang pemarah, lembut, baik, jahat, genit, pemalu, penakut, pemberani dan lain-lain. Jika dilihat dari fisik ada yang tinggi, pendek, rambut panjang, putih, hitam, mata sipit, dan lain-lain. Bisa karakteristik dilihat dari gaya bicara sesuai bahasa daerahnya.
Pembuatan karakter 3D dapat menggunakan aplikasi 3D MAX, AUTOCAD, Blender, dan lain-lain

Untuk membuat suatu desain grafis, kita membutuhkan suatu software untuk memudahkannya. Banyak software yang bisa digunakan untuk membuat suatu desain grafis. Ini merupakan salah satu jenis software yang bisa digunakan untuk desain pemodelan grafis dari segi grafik dan juga dimensinya yaitu AutoCAD.

AutoCAD adalah perangkat lunak komputer CAD untuk menggambar 2 dimensi dan 3 dimensi yang dikembangkan oleh Autodesk. Keluarga produk AutoCAD, secara keseluruhan, adalah software CAD yang paling banyak digunakan di dunia. AutoCAD digunakan oleh insinyur sipil, land developers, arsitek, insinyur mesin, desainer interior dan lain-lain. Format data asli AutoCAD, DWG, dan yang lebih tidak populer, Format data yang bisa dipertukarkan (interchange file format) DXF, secara de facto menjadi standard data CAD. Akhir-akhir ini AutoCAD sudah mendukung DWF, sebuah format yang diterbitkan dan dipromosikan oleh Autodesk untuk mempublikasikan data CAD. AutoCAD saat ini hanya berjalan disistem operasi Microsoft. Versi untuk Unix dan Macintosh sempat dikeluarkan tahun 1980-an dan 1990-an, tetapi kemudian tidak dilanjutkan. AutoCAD masih bisa berjalan di emulator seperti Virtual PC atau Wine. AutoCAD dan AutoCAD LT tersedia dalam bahasa Inggris, Jerman, Perancis, Italia, Spanyol, Jepang, Korea, Tionghoa Sederhana, Tionghoa Tradisional, Rusia, Ceko, Polandia, Hongaria, Brasil, Portugis, Denmark, Belanda, Swedia, Finlandia, Norwegia dan Vietnam.

Desain Pemodelan Grafis dan Sejarah Perkembangannya

Sebelum membahas tentang desain pemodelan grafis sebaiknya kita mengenal lebih dahulu desain grafis. Desain biasa diterjemahkan sebagai seni terapan, arsitekturm dan berbagai pencapaian kreatif lainnya. Grafika adalah segala cara pengungkapan dan perwujudan dalam bentuk huruf, tanda, dan gambar yang diperbanyak melalui proses percetakan guna disampaikan kepada khalyak. Contohnya, adalah: fott, gambar/drawing, Line Art, grafik, diagram, tipografi, angka, simbol, desain geometris, peta, gambar teknik, dan lain-lain. Desain Grafis adalah suatu bentuk komukasi visual yang menggunakan gambar untuk menyampaikan informasi atau [esan seefektif mungkin. Dalam desain grafis, teks juga dianggap gambar karena merupakan hasil abstraksi simbol-simbol yang bisa dibunyikan. Desain Grafis diterapkan dalam desain komunikasi dan fine art, sperti jenis desain lainnya, desain grafis dapat merujuk kepada proses pembuatan, metoda merancang, produk yang dihasilkan(rancangan), atau pun disiplin ilmu yang digunakan(desain).

Gambar maupun tanda yang digunakan bisa berupa tipografi atau media lainnya,seperti gambar atau fotografi.Desain grafis didefinisakan sebagai aplikasi dari keterampilan seni dan komunikasi untuk kebutuhan bisnis dan industri”. Aplikasi – aplikasi ini dapdat meliputi periklanan, packaging, perfilman dan penjualan produk, menciptakan identitas visual untuk insitusi, produk perusahaan, lingkungan grafis, desain informasi, dan secara visual menyempurnakan pesan dalam publikasi. Komputer grafis adalah program – program komputer yang digunakan untuk membuat desain grafis kalau boleh saya memberi contoh seperti misalnya CorelDRAW, Photoshop, Illustrator, dll, singkatnya komputer grafis adalah alat desain grafis. Desain Grafis adalah suatu ilmu atau tekhnik yang digunakan untuk merancang , membuat dan mengolah suatu gambar , tulisan , ataupun karya seni lainnya agar karya seni tersebut memiliki nilai tambah seni yang baik. Untuk dapat menciptakan suatu karya seni dengan menggunakan desain grafis yang baik.

Pemodelan adalah membentuk suatu benda-benda atau obyek. Membuat dan mendesain obyek tersebut sehingga terlihat seperti hidup. Sesuai dengan obyek dan basisnya, proses ini secara keseluruhan dikerjakan oleh komputer.

Sejarah dan Perkembangan Desain Grafis

Sejarah awal perkembangan desain grafis dapat ditelusuri dari jejak peninggalan manusia dalam bentuk lambang-lambang grafis sign dan simbol yang berwujud gambar (pictograf) atau tulisan (ideograf). Gambar dianggap lebih bersifat langsung dan ekspresif, dengan dasar acuan alam. Belum ada yang tahu pasti sejak kapan manusia memulai menggunakan gambar sebagai media komunikasi, tetapi sejak dulu manusia primitif sudah menggunakan coretan gambar di dinding gua untuk kegiatan berburu binatang. Selanjutnya memasuki Era Cetak : Desain grafis berkembang pesat seiring dengan perkembangan sejarah peradaban manusia saat ditemukan tulisan dan mesin cetak. Pada tahun 1447, Johannes Gutenberg (1398-1468) menemukan teknologi mesin cetak yang bisa digerakkan dengan model tekanan menyerupai disain yang digunakan di Rhineland, Jerman, untuk menghasilkan anggur. Ini adalah suatu pengembangan revolusioner yang memungkinkan produksi buku secara massal dengan biaya rendah, yang menjadi bagian dari ledakan informasi pada masa kebangkitan kembali Eropa.
Temuan Gutenberg tersebut telah mendukung perkembangan seni ilustrasi di Jerman terutama untuk hiasan buku.

Pada masa itu juga berkembang corak huruf (tipografi). Ilustrasi pada masa itu cenderung realis dan tidak banyak icon. Seniman besarnya antara lain Lucas Cranach dengan karyanya “Where of Babilon”. Pada perkembangan berikutnya, Aloys Senefelder (1771-1834) menemukan teknik cetak Lithografi. Teknik cetak lithografi menggunakan teknik cetak datar yang memanfaatkan prinsip saling tolak antara air dengan minyak. Teknik ini memungkinkan untuk melakukan penggambaran secara lebih leluasa dalam bentuk blok-blok serta ukuran besar, juga memungkinkan dilakukannya pemisahan warna. Sehingga masa ini mendukung pesatnya perkembangan seni poster. Masa keemasan ini disebu-sebut sebagai “The Golden Age of The Poster”. Nama lithografi tersebut dari master cetak yang menggunakan media batu litho.

Mulainya perkembangan desain grafis mengalami perkembangan pesat yaitu padasaat kejayaan kerajaan Romawi di abad pertama yang telah membawa peradaban baru dalam sejarah peradaban Barat dengan diadaptasikannya kesusasteraan, kesenian, agama, serta alfabet latin yang dibawa dari Yunani. Dan pada saat ini adanya mesin cetak dan komputer juga merupakan dua hal yang secara signifikan yaitu mempercepat perkembangan penggunaan seni desain grafis hingga akhirnya diterapkan dalam dunia periklanan, packaging, perfilman, dan lain-lain. Koran, majalah, tabloid, website dan animasi/kartun yang sehari-hari kita lihat adalah produk desain grafis.

Sumber : http://upamy.blogspot.com/2010/02/disain-pemodelan-grafik.html

http://rereekireii.blogspot.com/2011/10/tentang-desain-pemodelan-grafis-dan.html