PENGEMBANGAN SISTEM VIRTUAL ROOM NAVIGATOR DENGAN ALGORITMA DIJKSTRA UNTUK PENCARIAN JALUR TERPENDEK (STUDI KASUS : GEDUNG PERPUSTAKAAN IPB)
Oleh : KHAMAMUDIN G64101064
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2007
ABSTRAK KHAMAMUDIN. Pengembangan Sistem Virtual Room Navigator dengan Algoritma Dijkstra untuk Pencarian Jalur Terpendek (Studi Kasus : Gedung Perpustakaan IPB). Dibimbing oleh KUDANG BORO SEMINAR dan AZIZ KUSTIYO. Virtual Room Navigator (VRN) adalah sebuah sistem navigator ruangan interaktif dengan visualisasi tiga dimensi (3D). Sistem ini telah dibangun oleh Nugroho (2004) untuk membantu pengunjung gedung UPT Perpustakaan Pusat IPB, dalam menjelajah dan mengenali ruanganruangan di dalamnya. Sistem ini dipasang sebagai sumber informasi alternatif bagi pengunjung baru tentang tata ruangan dan tata letak di dalam bangunan. Akan tetapi sistem ini masih mempunyai banyak kekurangan, sehingga perlu dikembangkan lebih lanjut. Pengembangan yang dilakukan di sini diantaranya adalah penambahan denah yang akan menginformasikan posisi dan arah pengguna, sehingga pengguna tidak akan tersesat di dalam sistem. Pengembangan yang lain adalah penambahan fungsi pencarian jalur terpendek menuju ruangan/lokasi tertentu untuk membantu pengguna yang ingin mencari ruangan/lokasi tertentu secara cepat, tanpa perlu menjelajah ruangan satu persatu. Untuk mengimplementasikan fungsi pencarian jalur terpendek ini dibutuhkan sebuah algoritma yang dapat menyelesaikan problem shortest path. Algoritma yang akan digunakan adalah algortima Dijkstra. Hasil dari penelitian ini adalah perbaikan dari sistem VRN sebelumnya dengan penambahan beberapa fungsi baru, yaitu fungsi pencarian jalur terpendek menuju lokasi/ruangan tertentu dan penambahan denah/peta untuk membantu pengguna mengetahui posisi dan arah pengguna saat itu dalam sistem. Dengan penambahan beberapa fungsi baru tersebut, diharapkan sistem ini lebih dapat memenuhi kebutuhan pengguna dalam mengenali tata letak ruangan dalam suatu bangunan. Kata Kunci : Virtual Room Navigator, komputer grafik, shortest path, algoritma Dijkstra
PENGEMBANGAN SISTEM VIRTUAL ROOM NAVIGATOR DENGAN ALGORITMA DIJKSTRA UNTUK PENCARIAN JALUR TERPENDEK (STUDI KASUS : GEDUNG PERPUSTAKAAN IPB)
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Oleh : KHAMAMUDIN G64101064
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2007
Judul Skripsi : Pengembangan Sistem Virtual Room Navigator dengan Algoritma Dijkstra untuk Pencarian Jalur Terpendek (Studi Kasus: Gedung Perpustakaan IPB) Nama : Khamamudin NRP : G64101064
Menyetujui,
Pembimbing I
Pembimbing II
Prof. Dr. Ir. Kudang B. Seminar, M.Sc. NIP 131 475 575
Aziz Kustiyo, S.Si, M.Kom. NIP 132 206 241
Mengetahui, Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Dr. drh. Hasim, DEA NIP 131 578 806
Tanggal Lulus:
PRAKATA Alhamdulilahirobbil’alamin Segala puji dan syukur penulis panjatkan kehadirat ALLAH SWT atas segala rahmat dan karunia-Nya telah memberikan kekuatan dan kelancaran kepada penulis selama menyelesaikan studi hingga tersusunnya skripsi ini. Penelitian Tugas Akhir yang berjudul Pengembangan Sistem Virtual Room Navigator dengan Algoritma Dijkstra untuk Pencarian Jalur Terpendek ini, merupakan syarat penulis untuk menyelesaikan studi di Departemen Ilmu Komputer IPB. Penyelesaian tulisan ini tidak terlepas dari keterlibatan berbagai pihak yang turut andil demi kelancaran penelitian ini. Sebagai penghargaan terhadap pihak-pihak yang telah berjasa tersebut, penulis menyampaikan terimakasih yang sebesar-besarnya kepada: • Kedua orangtua serta adik-adik penulis yang telah memberikan semangat, do’a dan dukungan demi kelancaran penulis dalam penelitian. • Prof. Dr. Ir. Kudang Boro Seminar, M.Sc. dan Aziz Kustiyo, S.Si, M.Kom. selaku pembimbing skripsi, serta Hari Agung, S.Kom, M.Si. selaku penguji. Terima kasih atas bimbingan, waktu, pikiran, dan perhatian yang diberikan kepada penulis. • Segenap pimpinan dan staf Perpustakaan IPB. Terima kasih atas bantuan kemudahan, fasilitas, dan keramahan selama penulis berada di sana. • Seluruh dosen dan staf departemen Ilmu Komputer atas segala bantuannya. • Wisnu Adi Nugroho atas source code dan bahan-bahan yang penulis butuhkan dalam penelitian ini. • Hartini yang selalu memberi semangat serta impian masa depan. • Temen-temen satu kost, Didik, Bagus, Ranggo, Gianto, dan Voltak atas bantuan dan dukungannya. • Wahyudi, kakak kelas dan teman seperjuanganku, terima kasih atas semua dorongan semangatnya. • Teman-teman statistik 38, Mas Mamay, Asep, terima kasih atas perhatian dan kebersamaannya. • Yani, Liesca, Novi, Toto, Supri, Made, Jawa, Yoki, Erwin, Rades, dan seluruh temanteman ilkom angakatan 38 yang tidak dapat penulis sebutkan satu persatu, terima kasih atas segala bantuan, dorongan semangat, dan kerbesamaannya. • Sanda, Faiq, David, adik-adikku ilkom 39 dan 40, terima kasih atas segala dukungan dan bantuannya. • Semua pihak yang tidak bisa disebutkan satu persatu. Akhirnya, penulis mohon maklum jika tulisan ini tidak dapat memenuhi kesempurnaan yang diharapkan. Penulis sadar bahwa masih banyak kekurangan dalam tulisan ini. Semoga penelitian ini dapat bermanfaat bagi diri penulis sendiri, pembaca, dan juga masyarakat pada umumnya. Amin.
Bogor, September 2007
Penulis
RIWAYAT HIDUP Penulis dilahirkan di Kebumen pada tanggal 10 Mei 1981 sebagai anak keempat dari tujuh bersaudara, putra dari pasangan Bapak M. Ma’lif Yani dan Ibu Turaesih. Penulis menempuh pendidikan di SDN 3 Jogosimo Kecamatan Klirong Kabupaten Kebumen lulus pada tahun 1995, SMP Negeri 1 Klirong lulus tahun 1998, SMUN 1 Kebumen lulus pada tahun 2001. Pada tahun yang sama penulis diterima di Jurusan Ilmu Komputer FMIPA IPB melalui jalur UMPTN. Pada bulan Februari-April 2005, penulis melaksanakan praktek lapang di Balai Penelitian dan Pengembangan Bioteknologi dan Sumber Daya Genetik Cimanggu, Bogor. Selain menjalani kewajiban sebagai mahasiswa, sejak tahun 2006 penulis bekerja sebagai IT Administrator pada sebuah perusahaan yang bergerak di bidang telekomunikasi di Jakarta. Penulis juga pernah terlibat dalam berbagai project pembuatan software, di antaranya adalah sistem pengolah data calon pemilih untuk KPUD Kabupaten Bogor dan Padang.
DAFTAR ISI Halaman DAFTAR GAMBAR .................................................................................................................... viii DAFTAR LAMPIRAN................................................................................................................. viii PENDAHULUAN......................................................................................................................... 1 Latar Belakang .................................................................................................................. 1 Tujuan ................................................................................................................................ 1 Ruang Lingkup .................................................................................................................. 1 TINJAUAN PUSTAKA................................................................................................................ 1 Objek Tiga Dimensi (3D) .................................................................................................. 1 Sistem Koordinat 3D .......................................................................................................... 2 3D Engine........................................................................................................................... 2 3D State Engine.................................................................................................................. 2 Graph ................................................................................................................................. 2 Path .................................................................................................................................... 3 Shortest Path ...................................................................................................................... 3 Algoritma Dijkstra.............................................................................................................. 3 Sistem Development Life Cycle .......................................................................................... 4 Model Waterfall ................................................................................................................. 4 METODE PENELITIAN.............................................................................................................. 4 Fase Analisis kebutuhan dan definisi (Requirements analisys and definition)................... 4 Fase Desain sistem dan perangkat lunak (System and software design)............................. 5 Fase Implementasi dan pengujian unit (Implementation and unit testing) ......................... 5 Fase Integrasi dan pengujian sistem (Integration and system testing)................................ 5 HASIL DAN PEMBAHASAN..................................................................................................... 5 Fase Analisis Kebutuhan dan Definisi................................................................................ 5 Lingkup Masalah ..................................................................................................... 5 Analisis Pengguna ................................................................................................... 5 Fungsi Sistem .......................................................................................................... 6 Kebutuhan Antarmuka Eksternal............................................................................. 6 Kebutuhan Fungsional ............................................................................................. 6 Fase Desain Sistem dan Perangkat Lunak .......................................................................... 6 Desain Basis Data .................................................................................................... 7 Navigator ................................................................................................................. 7 Editor ....................................................................................................................... 7 Fase Implementasi dan Pengujian Unit .............................................................................. 8 Navigator ................................................................................................................. 9 Implementasi Algoritma Dijkstra dalam VRN ........................................................ 9 Ilustrasi Pencarian Jalur Terpendek pada VRN ....................................................... 11 Kontrol Navigasi...................................................................................................... 11 Implementasi Denah ................................................................................................ 11 Editor ....................................................................................................................... 12 Pengujian Unit ........................................................................................................ 12 Fase Integrasi dan Pengujian Sistem ................................................................................. 12 KESIMPULAN DAN SARAN..................................................................................................... 12 Kesimpulan......................................................................................................................... 12 Saran................................................................................................................................... 12 DAFTAR PUSTAKA ................................................................................................................... 12 LAMPIRAN.................................................................................................................................. 14
vii
DAFTAR GAMBAR Halaman 1 2 3 4 5 6 7 8
Sistem koordinat 3D .............................................................................................................. 2 Perbandingan World Space dan Object Space dalam sistem koordinat 3D ........................... 2 Model waterfall ..................................................................................................................... 4 Diagram Konteks VRN ......................................................................................................... 7 Rancangan antar muka navigator........................................................................................... 7 Rancangan antar muka login ................................................................................................. 7 Rancangan antarmuka Editor ................................................................................................ 8 Rancangan antarmuka form ganti password.......................................................................... 8
DAFTAR LAMPIRAN Halaman 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
Diagram Alir Data (DAD) level 1 Administrator ................................................................ 15 Diagram Alir Data (DAD) level 2 Administrator proses 1.Login ....................................... 15 Diagram Alir Data (DAD) level 2 Administrator proses 2. Manajemen VRN.................... 16 Diagram Alir Data (DAD) level 3 Administrator proses 2.1. Edit miniatur........................ 16 Diagram Alir Data (DAD) level 3 Administrator proses 2.2. Edit graph ............................ 17 Diagram Alir Data (DAD) level 3 Administrator proses 2.3. ganti password ..................... 17 Diagram Alir Data (DAD) level 1 Pengguna Biasa............................................................. 18 Diagram Alir Data (DAD) level 2 Pengguna biasa proses 2. Navigasi ............................... 18 Tabel Basis Data untuk Graph ............................................................................................ 19 Hasil implementasi bagian navigator................................................................................... 19 Diagram UML ..................................................................................................................... 20 Ilustrasi pencarian jalur terpendek (awal)............................................................................ 21 Ilustrasi pencarian jalur terpendek (akhir) ........................................................................... 21 Dialog box pencarian jalur terpendek.................................................................................. 22 Implementasi Denah............................................................................................................ 22 Implementasi bagian editor ................................................................................................. 23 Implementasi Form Login untuk editor............................................................................... 23 Implementasi Form Ganti Password ................................................................................... 23 Hasil pengujian untuk unit (bagian) navigator .................................................................... 24 Hasil pengujian untuk unit (bagian) editor .......................................................................... 25 Hasil pengujian form login .................................................................................................. 27 Hasil pengujian form ganti password .................................................................................. 28
viii
1
PENDAHULUAN Latar Belakang Suatu bangunan/gedung yang berukuran besar dan memiliki banyak ruangan, misalnya perpustakaan, sering menghadapi masalah yang berkaitan dengan kemudahan pengunjung barunya dalam menjelajah ruangan yang ada untuk pertama kalinya. Tidak semua orang bisa memberikan informasi sesuai dengan yang diinginkan pengunjung baru. Dalam banyak hal pengalaman bisa menjadi guru yang paling berharga. Dalam hal ini pengalaman yang diberikan melalui sistem adalah berupa informasi tata letak dalam bangunan/gedung. Untuk itu dibutuhkan sistem yang dapat merepresentasikan bangunan/gedung sesuai dengan keadaan di dunia nyata dan kehidupan manusia sehari-hari. Sistem yang demikian memberikan pengalaman virtual dan kesan lebih kuat bagi pengunjung. Sebuah sistem navigasi ruangan interaktif dengan visualisasi virtual tiga dimensi (3D) dengan nama Virtual Room Navigator (VRN) telah dikembangkan oleh Nugroho (2004) untuk memenuhi kebutuhan tersebut. Studi kasus yang diambil adalah gedung Unit Pelaksanaan Teknis (UPT) Perpustakaan Pusat IPB. Sistem ini dibangun dengan tujuan untuk membantu pengunjung baru gedung UPT Perpustakaan Pusat IPB untuk menjelajah dan mengenali ruangan-ruangan di dalamnya. Akan tetapi, sistem tersebut dirasa kurang interaktif karena pengguna diharuskan menjelajah sendiri ruangan-ruangan yang ada tanpa ada informasi tata letak ruang terlebih dahulu. Untuk itu ditambahkan beberapa fitur yang akan membantu dalam melakukan navigasi. Diantaranya adalah fitur untuk mencari jalan terpendek dari posisi sekarang menuju ke suatu ruangan tertentu. Selain itu, kekurangan-kekurangan sistem yang lain seperti tidak adanya petunjuk arah mata angin dan peta yang akan menunjukkan posisi pengguna berada, dapat menyebabkan pengguna tersesat di dalamnya. Sehingga penambahan arah mata angin dan peta dirasa sangat perlu dilakukan. Disamping itu, editor yang telah disediakan sebelumnya dirasa terlalu rumit, dan banyak fitur-fitur yang tidak diperlukan. Untuk itu perlu dibuatkan editor yang lebih sederhana dan sesuai dengan kebutuhan.
Tujuan Tujuan dari penelitian ini adalah menyempurnakan sistem Virtual Room Navigator yang telah ada, tanpa menghilangkan fungsi sebelumnya. Perbaikan yang dilakukan diantaranya adalah: 1 Menambahkan fungsi pencarian jalan terpendek (shortest path) untuk menuju ruangan tertentu dengan menggunakan algoritma Dijkstra. 2 Menambahkan denah/peta dan arah mata angin yang akan menginformasikan posisi pengguna saat itu. 3 Membuatkan editor untuk meng-update kondisi ruangan dan graph yang digunakan dalam pencarian jalan terpendek. Ruang Lingkup Ruang lingkup penelitian ini dibatasi pada: 1 Sistem yang dikembangkan, yaitu Virtual Room Navigator, mengambil studi kasus gedung UPT Perpustakaan Pusat IPB. 2 Kemampuan editor terbatas pada: a editing terbatas pada penambahan/pengurangan objek, dan pemindahan tata letak objek. Objek bisa berupa: meja, kursi, komputer, rak buku, dll b editing graph (terdiri dari kumpulan node dan edge) yang akan digunakan dalam pencarian jalur terpendek c bentuk bangunan, dinding, ruangan, pintu, jendela, lampu, dll yang bersifat permanen tidak bisa diedit 3 Algoritma pencarian jalur terpendek (shortest path) yang digunakan adalah algoritma Dijkstra. 4 Jenis graph yang dibuat melalui editor adalah digraph.
TINJAUAN PUSTAKA Objek Tiga Dimensi (3D) Objek 3D atau mesh adalah sekumpulan face/poligon yang digabung menjadi objek baru. Pada dasarnya objek-objek yang kompleks terdiri dari poligon-poligon sederhana. Umumnya poligon yang menjadi dasar pembentukan bagi objek-objek lain adalah segitiga (Susanto 2000). Poligon sendiri tersusun dari sekumpulan vertek. Bentuk poligon dintentukan dari posisi vertek-verteknya. Vertek-vertek ini menentukan titik sudut dari poligon tersebut. Vertek tak lain adalah titik pada dunia tiga dimensi. Setiap vertek mempunyai nilai x, y, dan z.
2
Sistem Koordinat 3D Objek 3D dibangun dalam sistem koordinat yang mempunyai 3 sumbu yaitu x, y dan z, atau disebut dengan sistem koordinat 3D. Aplikasi grafik 3D biasanya menggunakan dua jenis sistem koordinat Cartesian, yaitu aturan tangan kiri dan aturan tangan kanan (Microsoft 2001). Dalam kedua sistem koordinat ini, arah dari sumbu x positif adalah ke kanan, dan arah dari sumbu y positif adalah ke atas. Yang membedakan dua sistem koordinat ini adalah arah sumbu z positifnya. Koordinat sistem dengan aturan tangan kiri arah sumbu z positif adalah menjauhi bidang gambar atau pengamat. Sedangkan aturan tangan kanan, sumbu positif z mengarah ke pengamat. Ilustrasi dari kedua sistem tersebut dapat dilihat pada Gambar 1.
Gambar 1 Sistem koordinat 3D (Microsoft 2001). Dalam graifk 3D, terdapat tiga macam ruang (space) (Buchanan et al. 1997), yaitu 1 Ruang Dunia (World Space), yaitu koordinat dari semua titik yang ada dalam dunia 3D. Koordinat World Space bersifat absolut, tidak pernah berubah, dan tidak terpengaruh dari arah objek atau kamera. 2 Ruang Objek (Object Space), yaitu titik koordinat pada objek yang relatif terhadap posisi dan sudut putarnya. Koordinat Ruang Objek mengikuti objeknya, kemanapun arah objek dalam dunia 3D. 3 Ruang Kamera (Camera Space), yaitu ruang 3D yang merepresentasikan kamera dari pengguna, atau layar komputer, dimana objek masih mempunyai kedalaman (koordinat z). Koordinat ruang kamera adalah seperti ruang objek, tetapi objeknya adalah kamera itu sendiri. Pada Gambar 2 diilustrasikan perbandingan antara World Space dan Object Space dalam sistem koordinat 3D.
Gambar 2 Perbandingan World Space dan Object Space dalam sistem koordinat 3D (Buchanan et al. 1997). 3D Engine Software yang memproses struktur data bangun 3D, termasuk seluruh pencahayaan, aksi-aksi, dan informasi keadaan secara umum, dan me-render (menterjemahkan) dunia 3D dari sudut pandang pemain atau kamera disebut 3D Engine (LaMothe 2003). 3D Engine digunakan untuk mempercepat pembuatan aplikasi 3D, misalnya game. Contoh 3D Engine yang sering digunakan dalam pembuatan game adalah Valve, Quake Engine, dan Unreal Engine. 3D State Engine 3D State Engine adalah salah satu 3D Engine yang dibuat oleh 3DState Ltd, Israel. 3D Engine ini dapat di-download secara gratis di alamat www.3dstate.com untuk keperluan pendidikan. Engine ini dikeluarkan dalam beberapa versi bahasa pemrograman. Diantaranya adalah versi 3D State untuk Visual Basic 6.0. Sistem koordinat 3D yang digunakan dalam 3D State adalah sistem koordinat kartesian dengan aturan tangan kanan (Buchanan et al. 1997). Dalam paketnya, 3D State juga menyediakan beberapa tools, diantaranya adalah 3D Webmaker, yaitu sebuah tool world builder. World Builder adalah tools yang digunakan untuk membangun dunia 3D yang cukup kompleks. Graph Sebuah graph G berisi himpunan V, yang merupakan vertek-vertek dari G, bersama dengan himpunan E yang merupakan pasangan-pasangan dari vertek-vertek (V) yang berbeda-beda. Pasangan-pasangan ini disebut edge-edge dari G. Jika e=(v, w) adalah sebuah edge dengan vertek v dan w, maka v dan w dikatakan berada di atas e, dan e
3
dikatakan incident dengan v dan w. Jika pasangan tersebut (v, w) tidak diperhatikan urutannya, maka G disebut undirected graph. Namun jika diperhatikan urutannya, maka G disebut directed graph. Directed graph sering disingkat dengan digraph (Kruse 1989). Path Path adalah sebuah graph tidak kosong P=(V,E), dimana V={x0, x1, ..., xk} dan E={x0x1, x1x2, ..., xk-1xk}, dimana seluruh xi adalah berbeda. Vertek x0 dan xk dihubungkan oleh P dan mereka disebut ujung-ujung path, sedangkan x1, ..., xk-1 adalah vertek-vertek tengah dari P. Panjang dari sebuah path adalah jumlah dari edge-edge pada suatu path (Diestel 2005). Shortest Path Problem sorthest path melibatkan sebuah graph terboboti yang digambarkan oleh sekumpulan tepi dan titik {E, V}. Diberikan sebuah titik awal, s, tujuannya adalah menemukan jalur terpendek yang ada antara s dengan sembarang titik dalam graph tersebut. Oleh karena itu, setiap jalur akan memiliki penjumlahan terkecil yang mungkin dari komponen tepi (u, v) dan bobotnya (w [u, v]) (Freeland et al. 1997). Algoritma yang dapat digunakan untuk mencari shortest path diantaranya adalah algoritma Floyd dan algoritma Dijkstra. Algoritma Dijkstra Algoritma Djikstra (diambil dari nama penemunya, E.W. Dijkstra) digunakan untuk menyelesaikan masalah pencarian jalur terpendek (shortest path) dari suatu vertek ke vertek-vertek lainnya dalam suatu graph G=(V, E). Di dalam hal ini edge-edge dalam graph G tersebut mempunyai bobot yang berbeda (weighted graph) (Morris 1998). Algoritma Djikstra menjaga dua kumpulan vertek: S = kumpulan vertek yang telah ditemukan jalur terpendeknya dari vertek awal V-S = sisa vertek yang lain (disimbolkan juga dengan Q). Struktur data lain yang diperlukan d = array yang berisi perkiraan jalur terpendek untuk tiap-tiap vertek pi = array yang berisi predecessor untuk tiap vertek
Operasi dasarnya adalah sebagai berikut 1 Inisialisasi d dan pi 2 Set S = kosong. 3 Selama ada vertek dalam V-S a Urutkan vertek-vertek dalam V-S berdasarkan perkiraan jarak terpendek dengan sumber. b Tambahkan u ke dalam S, dengan u adalah vertek dalam V-S yang terpendek. c Lakukan prosedur relaxation untuk semua vertek-vertek dalam V-S yang terhubung lewat vertek u. Algoritma Dijkstra dalam pseudo-code menurut Morris (1998) adalah sebagai berikut shortest_paths( Graph g, Node s ) initialise_single_source( g, s ) S := { 0 } /* Make S empty */ Q := Vertices( g ) /* Put the vertices in a PQ */ while not Empty(Q) u := ExtractCheapest( Q ); AddNode( S, u ); /* Add u to S */ for each vertex v in Adjacent( u ) relax( u, v, w )
Inisialisasi Prosedur ini menginisialisasi graph sehingga semua vertek tidak mempunyai predecessor (pi[v]=nil) dan perkiraan cost (jarak) untuk tiap vertek menuju s adalah tak terhingga atau infinite (d[v]=∞). initialise_single_source( Graph g, Node s ) for each vertex v in Vertices( g ) g.d[v] := infinity g.pi[v] := nil g.d[s] := 0;
Relaxation Proses relaxation memperbaharui seluruh cost (d) dalam himpunan vertek V-S yang terhubung melalui vertek u. Prosedur ini memeriksa, apakah cost atau perkiraan jarak terpendek dari vertek v dapat diperbaiki melalui vertek u (dengan membuat u sebagai predecessor dari vertek v). Algoritma dari prosedur relaxation adalah sebagai berikut relax( Node u, Node v, double w[][] ) if d[v] > d[u] + w[u,v] then d[v] := d[u] + w[u,v] pi[v] := u
4
System Development Life Cycle Pada awalnya, pengembangan software hanya dilakukan oleh seorang programmer dengan menuliskan kode program untuk menyelesaikan suatu masalah. Sekarang, sistem yang dibangun sangat besar dan kompleks sehingga perancang, analis, programmer, tester, dan pengguna harus bekerja bersama untuk membuat jutaan kode program. Untuk mengatur semua ini, berbagai macam model System Development Life Cycle (SDLC) telah dibuat. Diantaranya, waterfall, fountain, spiral, build and fix, rapid prototyping, incremental, dan synchronize and stabilize (Kay 2002). Model Waterfall Model SDLC yang paling tua, dan terkenal paling baik, adalah waterfall: serangkaian fase dimana output dari setiap fase menjadi input bagi fase berikutnya (Kay 2002). Model ini terbagi kedalam beberapa fase, yaitu (Somerville 2001): 1 Analisis kebutuhan dan definisi (Requirements analisys and definition) Kegunaan sistem, batasan, dan tujuan ditentukan dengan melakukan konsultasi dengan pengguna sistem, yang kemudian akan didefinisikan secara detail dan disajikan sebagai spesifikasi sistem. 2 Desain sistem dan perangkat lunak (System and software design) Proses desain sistem membagi-bagi kebutuhan baik dalam kebutuhan hardware maupun software, yang akan menyusun keseluruhan arsitektur sistem. Desain software melibatkan pengidentifikasian dan pendeskripsian dasar abstraksi sistem software dan hubungan mereka. 3 Implementasi dan pengujian unit (Implementation and unit testing) Selama fase ini, desain software diwujudkan sebagai sebuah set program atau unit-unit program. Pengujian unit melibatkan pengujian bahwa tiap unit bekerja sesuai dengan spesifikasinya. 4 Integrasi dan pengujian sistem (Integration and system testing) Unit-unit program tersebut digabungkan dan diuji sebagai sebuah sistem yang lengkap untuk menjamin bahwa kebutuhan perangkat lunak telah terpenuhi. Setelah pengujian, sistem perangkat lunak diserahkan kepada pengguna.
5 Penggunaan dan perawatan (Operation and maintenance) Biasanya, ini adalah fase paling lama. Sistem dipasang dan digunakan dalam praktek. Perawatan melibatkan perbaikan kesalahan-kesalahan (error) yang belum ditemukan pada proses sebelumnya, meningkatkan implementasi unit-unit sistem dan melakukan penambahan kegunaan sistem apabila ditemukan kebutuhan baru. Pada Gambar 3 diilustrasikan fase-fase dalam model waterfall tersebut. Requirements definition System and software design Impelentation and unit testing Integration and system testing Operation and maintenance
Gambar 3 Model waterfall (Somerville 2001).
METODE PENELITIAN Metode pengembangan sistem yang akan digunakan dalam penelitian ini adalah System Development Life Cycle (SDLC) dengan model waterfall. Metodologi pengembangan ini terbagi ke dalam lima fase, yaitu fase analisis kebutuhan dan definisi, fase desain sistem dan perangkat lunak, fase implementasi dan pengujian unit, fase integrasi dan pengujian sistem, dan fase penggunaan dan perawatan. 1 Fase Analisis kebutuhan dan definisi (Requirements analisys and definition) Fase ini dimulai dengan identifikasi permasalahan, alternatif solusi yang ada, menentukan tujuan sistem, dan mengidentifikasikan kendala-kendala sistem. Pada sistem VRN, permasalahan yang timbul adalah kurangnya fasilitas yang ada pada sistem sehingga pengguna akan kesulitan mendapatkan informasi yang diinginkan. Untuk itu perlu ditambahkan beberapa fasilitas yang dapat membantu pengguna selama menggunakan sistem tersebut
5
diantaranya adalah penambahan fasilitas peta atau denah, arah mata angin, dan pencarian jalur terpendek. Diharapkan dengan penambahan fasilitas-fasilitas baru tersebut pengguna akan lebih mudah menggunakan sistem dan mendapatkan informasi yang diinginkan secara cepat. 2 Fase Desain sistem dan perangkat lunak (System and software design) Dalam fase ini dilakukan kebutuhan sistem diabagi dalam kebutuhan hardware dan kebutuhan software. VRN adalah sistem yang menggunakan Engine 3D yang membutuhkan dukungan hardware yang cukup tinggi. Dalam sistem yang telah dibuat oleh Nugroho (2004), disebutkan bahwa kebutuhan minimal hardware adalah sebagai berikut: • Prosesor 1 GHz • Memori internal 256 MB • Kartu VGA 32 MB mendukung 3D • Monitor resolusi 800x600 pixel (24 bit) • Hardisk 70 MB • Keyboard sedangkan kebutuhan software untuk sistem ini adalah Sistem Operasi Microsoft Windows 98 Desain perangkat lunak melibatkan pengiden-tifikasian dan pendeskripsian dasar abstraksi sistem perangkat lunak dan hubungan mereka. 3 Fase Implementasi dan pengujian unit (Implementation and unit testing) Selama fase ini, desain software diwujudkan sebagai sebuah set program atau bagian-bagian program. Pengujian unit melibatkan pengujian bahwa tiap unit telah bekerja sesuai dengan spesifikasinya. Sistem VRN yang baru, akan diimplementasikan dalam 2 unit program. Yaitu Editor, yang berguna untuk mengedit dunia 3D agar tata letak ruangannya selalui sesuai dengan kondisi dan tata letak ruangan pada dunia sebenarnya. Unit tersebut akan dibatasi penggunaannya oleh orang tertentu saja, yang berhak untuk melakukan perubahan-perubahan pada dunia 3D. Unit kedua adalah sistem navigasi itu sendiri, dimana user secara umum bisa berinteraksi dengan sistem. Dalam pengembangan yang dilakukan untuk saat ini, ditambahkan beberapa fungsi yang belum ada pada sistem sebelumnya, yaitu penambahan denah atau peta yang menginformasikan lokasi pengguna dalam sistem berserta arahnya, dan fungsi untuk mencari ruangan-
ruangan tertentu algoritma Djikstra.
dengan
menggunakan
4 Fase Integrasi dan pengujian sistem (Integration and system testing) Fase ini menggabungkan unit-unit program yang ada pada fase sebelumnya, menjadi satu kesatuan sistem yang lengkap. Dalam hal ini, sistem VRN yang terdiri dari 2 unit, yaitu unit editor dan navigasi, akan dikemas menjadi sebuah paket program yang lengkap. Selanjutnya, akan dilakukan testing atau pengujian terhadap sistem sebelum sistem diserahkan kepada pengguna.
HASIL DAN PEMBAHASAN Fase Analisi Kebutuhan dan Definisi Lingkup Masalah Virtual Room Navigator adalah suatu perangkat lunak yang digunakan untuk merepresentasikan suatu bangunan atau gedung dalam miniatur 3D. Tujuannya adalah untuk memenuhi kebutuhan pengguna akan informasi tata ruang dan tata letak suatu bangunan atau gedung. Sistem ini telah diterapkan pada Gedung Perpustakaan IPB berupa miniatur gedung dalam bentuk objek 3D, yang penerapannya dilakukan pada lantai dua, tiga, dan empat. Analisis Pengguna Pengguna dari sistem VRN dapat dibagi menjadi dua, yaitu 1 Pengelola perpustakaan IPB selaku administrator. Administrator mempunyai tugas untuk melakukan perubahan yang berkaitan dengan tata letak pada ruangan yang ada. Setiap ada perubahan tata letak ruangan, operator harus melakukan update terhadap objek 3D pada sistem. Sehingga sistem akan selalu sesuai dengan kondisi sebenarnya. 2 Pengunjung perpustakaan. Pengunjung perpustakaan (pengguna) dapat menggunakan sistem ini untuk menjelajahi gedung perpustakaan secara virtual. Pengguna juga dapat melakukan pencarian jalur terpendek yang bisa ditempuh dari suatu lokasi ke lokasi yang lainnya.
6
Fungsi sistem Fungsi sistem secara umum adalah sebagai sarana informasi tata letak suatu bangunan kepada khalayak. Sistem ini juga dapat digunakan untuk mempromosikan suatu gedung yang baru dibangun. Sehingga ada gambaran secara umum bagi pengguna akan bangunan baru tersebut. Fitur-fitur utama yang ada pada sistem adalah • Tampilan ruangan dalam bentuk 3D yang dapat dikendalikan oleh pengguna untuk melakukan eksplorasi terhadap seluruh ruangan-ruangan yang ada. • Tampilan denah yang berguna untuk membantu pengguna untuk mengetahui posisi dan arah pengguna saat ini dalam sistem, sehingga pengguna tidak akan tersesat didalamnya. • Pencarian jalur terpendek. Dengan fitur ini, pengguna dapat mencari jalur terpendek yang dapat ditempuh dari posisi saat ini menuju lokasi tertentu yang diinginkan pengguna. • Editor Editor adalah fitur yang hanya bisa diakses oleh administrator. Editor ini berguna untuk memperbaharui kondisi suatu ruangan, dan juga digunakan untuk menentukan jalur yang dapat dilalui oleh pengguna melalui fitur pencarian jalur terpendek. Kebutuhan Antarmuka Eksternal A Antarmuka Pengguna Antarmuka pengguna untuk perangkat lunak ini dikembangkan dengan menggunakan modus grafik. Perangkat lunak ini menerima masukan dari pengguna melalui perintah klik pada tetikus (mouse) atau yang diketikkan melalui papan kunci (keyboard). Keluaran dari perangkat lunak ini dapat dilihat pengguna dengan menggunakan monitor secara langsung. B
Antarmuka Perangkat Keras Kebutuhan minimum perangkat keras yang digunakan untuk menjalankan sistem VRN adalah sebuah PC dengan spesifikasi: • Prosesor Intel Pentium 4 • Memori internal 256 MB • Kartu VGA 32 MB yang mendukung aplikasi 3D • Monitor dengan resolusi 1024 x 768 pixel
• Hard disk 70 MB. C
Antarmuka Perangkat Lunak Kebutuhan perangkat lunak dibutuhkan adalah • Microsoft Windows XP • 3D State Engine
yang
Kebutuhan Fungsional Kebutuhan fungsional sistem meliputi • Fungsi untuk menampilkan navigator. Ini adalah fungsi utama yang dapat diakses oleh pengguna biasa. Fitur ini akan langsung ditampilkan pada saat sistem dijalankan. • Fungsi navigasi. • Fungsi ini merupakan fungsi utama sistem, yaitu untuk menjelajah ruangan-ruangan di dalam bangunan virtual. Navigasi dilakukan dengan menekan tombol pada keyboard. Fungsi ini memiliki kemampuan untuk menggerakan pandangan user untuk maju, mundur, dan juga untuk memutar. Selama bernavigasi, posisi dan arah user dapat dilihat pada denah yang tersedia. • Fungsi pencarian jalur terpendek. • Fungsi ini digunakan oleh user untuk mencari rute terpendek yang dapat ditempuh dari posisi user menuju lokasi yang diinginkan user. • Fungsi untuk mengedit objek 3D. • Fungsi ini hanya dapat diakeses oleh administrator, dengan melakukan proses login terlebih dahulu. Disini operator dapat pembaharuan terhadap tata letak dan objek-objek yang ada dalam dunia 3D agar sesuai dengan kondisi yang sesungguhnya. Dalam editor ini, administrator juga dapat menentukan jalur-jalur yang dapat ditempuh dalam pencarian jalur terpendek. • Fungsi untuk validasi pengguna. • Fungsi untuk validasi, apakah user dapat masuk sebagai administrator yang dapat mengakses fungsi editor. • Fungsi untuk mengubah password. • Fungsi yang digunakan untuk mengubah password yang diperlukan untuk masuk dalam editor. Fungsi ini hanya dapat diakses oleh administrator yang telah melakukan proses login terlebih dahulu. Fase Desain Sistem dan Perangkat Lunak Sistem VRN mempunyai dua kategori pengguna, yaitu pengguna biasa dan administrator. Oleh karena itu, sistem akan dibagi dalam dua unit, yaitu navigator dan
7
editor. Navigator adalah sistem yang digunakan oleh pengguna biasa. Editor adalah unit yang digunakan oleh administrator untuk melakukan pembaharuan terhadap objekobjek pada miniatur 3D. Diagram konteks sistem dapat dilihat pada Gambar 4. Untuk memperjelas Diagram Konteks atau Diagram Aliran Data (DAD) level 0 tersebut, dibuatlah DAD level 1, DAD level 2, dan DAD level 3 untuk proses yang terjadi pada Administrator, yang dapat dilihat pada Lampiran 1, Lampiran 2, Lampiran 3, Lampiran 4, Lampiran 5, dan Lampiran 6. Sedangkan DAD level 1 dan DAD level 2 Pengguna biasa dapat dilihat pada Lampiran 7 dan Lampiran 8. pilihan menu
pilihan menu VRN hasil manajemen
tampilan miniatur 3D
Pengguna biasa
Administrator
Gambar 4 Diagram Konteks VRN. Desain Basis Data Sistem VRN memerlukan dua basis data, yang masing-masing digunakan untuk menyimpan miniatur 3D dan menyimpan graph. Basis data yang digunakan untuk menyimpan miniature 3D telah disediakan oleh Engine 3DState. Sedangkan basis data yang digunakan untuk menyimpan graph, digunakan Microsoft Access. Tabel yang dibuat adalah tabel Node dan Edge, yang definisinya dapat dilihat pada Lampiran 9.
Menu-menu yang ada pada form navigator • File Digunakan untuk mengakses menu exit, untuk keluar dari sistem. • Go to Menu yang digunakan untuk melakukan pencarian jalur terpendek. • Administrator Menu untuk masuk ke dalam mode editor. • Help Menampilkan bantuan singkat tentang bagaimana cara menggunakan sistem ini. Perancangan Fungsi/Proses Fungsi/proses dari Navigator adalah 1 Fungsi menampilkan miniatur 3D dari suatu bangunan. 2 Fungsi/proses melakukan navigasi. 3 Fungsi/proses mencari jalur terpendek 4 Fungsi/proses menampilkan posisi dan arah user pada denah. 5 Fungsi/proses menampilkan halaman petunjuk penggunaan. 6 Fungsi/proses untuk login ke mode editor. 7 Fungsi/proses untuk keluar dari sistem. Dalam form navigator, terdapat fungsi untuk melakukan login ke dalam mode editor. Perancangan antarmuka untuk form login dapat dilihat paga Gambar 6 Form Login Username: Password: OK
Navigator Perancangan antarmuka Rancangan antarmuka untuk form Navigator dapat dilihat pada Gambar 5. Form Navigator File
Go to
Denah
Administrator
Help
Tampilan miniatur 3D
Gambar 5 Rancangan antar muka navigator.
Gambar 6 Rancangan antar muka login. Editor Perancangan antarmuka Rancangan antarmuka untuk form Editor dapat dilihat pada Gambar 7 Menu-menu yang ada pada form Editor: • File Menu untuk mengakses sub menu untuk menyimpan hasil perubahan, dan menu untuk keluar dari sistem. • Password Menu untuk mengakses form untuk mengganti password untuk masuk dalam form Editor
8
• Logout Menu untuk keluar dari mode Editor, dan kembali ke mode Navigator. • Help Menu untuk menampilkan form yang berisi petunjuk singkat cara pengoperasian program.
Perancangan form untuk ganti password dapat dilihat pada Gambar 8 Form Ganti Password Username: Password lama:
Form Editor File
Password
Password baru:
Logout Help Ulang password baru:
Objek browser
Tampilan miniatur 3D
Objek View
Gambar 7 Rancangan antarmuka Editor. Perancangan Fungsi/Proses Fungsi/Proses dari editor adalah 1 Fungsi/proses melakukan proses editing pada miniatur 3D, yang bisa berupa a Menggeser objek b Memutar objek c Merubah ukuran objek (perbesar atau perkecil) d Menambahkan objek baru. e Menghapus objek. 2 Fungsi/proses menambah atau mengurangi jalur yang akan digunakan dalam proses pencarian jalur terpendek. Fungsi/proses ini bisa dibagi menjadi beberapa fungsi/proses lagi yaitu: a Menambahkan node b Menggeser posisi node c Memberi nama node d Menghapus node e Menambah edge f Menghapus edge 3 Fungsi/proses untuk menyimpan hasil perubahan yang telah dilakukan oleh administrator. 4 Fungsi/proses untuk mengubah password yang digunakan untuk masuk kedalam mode editor 5 Fungsi atau proses untuk keluar dari mode editor, dan kembali ke mode navigator 6 Fungsi/proses untuk menampilkan halaman petunjuk penggunaan editor. Dalam form editor, terdapat fungsi/proses untuk melakukan perubahan password.
OK
Gambar 8 Rancangan antarmuka form ganti password. Fase Implementasi dan Pengujian Unit Kedua bagian yang telah dirancang, yaitu navigator dan editor diimplementasikan menggunakan komputer dengan spesifikasi sebagai berikut: • Prosesor Intel Pentium D 2.8 GHz • Memori internal DDR2 1 GB • Kartu VGA 256 MB • Monitor 17” resolusi 1024x768 pixel • Hardisk 250 GB Perangkat lunak yang digunakan dalam implementasi dapat dilihat pada Tabel 1. Tabel 1 Perangkat lunak dan fungsinya dalam implementasi Perangkat Lunak Fungsi Microsoft Sistem Operasi Windows XP Professional SP2 3Dstate 3D 3D Engine yang Engine SDK memuat fungsi-fungsi pemrosesan objek 3D 3D Webmaker 2.0 Editor miniatur 3D bangunan Microsoft Visual Bahasa pemrograman Basic 6.0 untuk implementasi sistem Microsoft Office Berkas data untuk Access 2003 penyimpanan password dan graph Adobe Photoshop Pengolah gambar 7.0 tekstur 2D Microsoft Paint Pengolah gambar tekstur 2D
9
Navigator Navigator diimplementasikan menggunakan bahasa pemrograman Microsoft Visual Basic 6.0 pada lingkungan Microsoft Windows XP. Tampilan layar navigator ini dapat dilihat pada Lampiran 10. Implementasi Algoritma Dijkstra dalam VRN Algoritma Dijkstra adalah algoritma untuk mencari jalur terpendek pada suatu graph. Graph terdiri dari kumpulan vertek dan edge. Dalam sistem VRN ini, algoritma Djikstra diimplementasikan menggunakan pendekatan Objek Oriented Programming (OOP). Sehingga akan dibentuk beberapa Class, yaitu 1 cPoint 2 cNode 3 cNodes 4 cEdge 5 cGraph Hubungan keterkaitan antara 5 class ini digambarkan dengan diagram UML yang dapat dilihat pada Lampiran 11. cPoint cPoint adalah class untuk titik atau vertek dalam dunia 3D. Titik dalam dunia 3D dinyatakan dalam 3 koordinat, yaitu x, y dan z. Sehingga struktur class cPoint secara garis besar adalah sebagai berikut: Class cPoint Atribut: • X Ækoordinat x • Y Æ koordinat y • Z Æ koordinat z Prosedur • setPoint • getPoint cNode cNode sebenarnya adalah cPoint yang telah ditambah dengan atribut-atribut yang berguna dalam pencarian shortest path. Salah satunya adalah d, yaitu atribut yang berisi nilai perkiraan jarak terpendek sementara dari node yang bersangkutan terhadap node source. Class cNode Atribut • Point Æ class cPoint • ID Æ id node • Nama Æ nama node • d Æ perkiraan jalur terpendek
cNodes cNodes class yang berisi kumpulan class cNode. Class ini dibuat untuk memudahkan implementasi kumpulan vertek S dan Q. Dalam class ditambahkan prosedur ExtractNode, yang berfungsi untuk mengambil node yang mempunyai cost (nilai d) paling kecil. ExtractNode d = Nodes.Item(1).d For each node in Nodes If node.d < d d=node.d ExtractNode = node Nodes.remove node Sehingga struktur class cNodes secara garis besar adalah Class cNodes Atribut • Nodes Æ kumpulan class cNode Prosedur • addNode Æ menambahkan node • ExtractNode Æ mengambil node dengan d terkecil cEdge Sesuai dengan namanya, cEdge adalah class untuk edge, yaitu garis yang menghubungkan antara 2 node. Karena graph yang akan dibentuk adalah graph yang mempunyai arah, maka node dibedakan jadi node awal dan node akhir. Untuk mengetahui jarak antara dua node tersebut digunakan rumus jarak Jarak=
( x 2 − x1 ) 2 + ( y 2 − y1 ) 2 + ( z 2 − z1 ) 2 Struktur dari Class cEdge adalah sebagai berikut: Class cEdge Atribut • Node1 Æ node awal • Node2Æ node akhir Prosedur • getJarak cGraph Ini adalah class untuk implementasi graph, beserta pencarian shortest path-nya menggunakan algoritma Dijkstra. Strukturnya secara umum adalah sebagai berikut:
10
Class cGraph Atribut • myNodes Ækumpulan semua node • myEdges Æ kumpulan semua edge • myPath Æ urutan node yang merupakan hasil path terpendek dari suatu vertek ke vertek yang lain • S Æ instance dari cNodes, merupakan kumpulan vertek yang telah ditemukan jalur terpendeknya • Q Æ instance dari cNodes, merupakan kumpulan vertek yang belum ditemukan jalur terpendeknya • pi Æ array yang berisi predecessor untuk tiap vertek Prosedur • Dijkstra Æ proses utama dari algoritma Djikstra • InitDijkstra Æ inisialisasi Dijkstra • Relaxation Æ proses relaxation • setSourceNode • getShortestPath Æ mencari path terpendek dari source node ke node tertentu Dijkstra Prosedur utama untuk algoritma Dijkstra. Source code-nya adalah sebagai berikut: Private Sub Djikstra() Dim u As cNode 'inisialisasi InitDjisktra While Q.Count <> 0 'ambil node dengan d (cost) paling kecil Set u = Q.ExtractNode 'tambahkan node u ke S S.addNode u 'untuk semua node (vertices) yang terhubung dengan u dan berada dalam list Q, ‘hitung ulang d (cost) -> relaxation Relaxation u Wend End Sub
InitDijkstra Ini adalah implementasi dari algoritma Dijkstra untuk bagian inisialisasi. Implementasinya dalam VB adalah sebagai berikut:
Private Sub InitDjisktra() Dim i As Integer 'd (cost untuk node) = tak hingga (Infinite) selain node source (0) For i = 1 To myNodes.Count If i <> sNode.ID Then myNodes(i).d = Infinite Else myNodes(i).d = 0 End If Next i 'init pi (predecessor) untuk tiap node ReDim pi(myNodes.Count) As cNode 'kosongkan S, dengan cara set S sebagai instance baru Set S = New cNodes 'isi Q dengan seluruh nodes pada graph Set Q = New cNodes For i = 1 To myNodes.Count Q.addNode myNodes(i) Next i End Sub
Relaxation Implementasi dari algoritma relaxation, yaitu proses menghitung ulang semua cost (d) dalam himpunan vertek Q (V-S) yang terhubung dengan node u. Private Sub Relaxation(u As cNode) Dim i As Integer Dim j As Integer Dim tEdge As cEdge 'untuk tiap2 node dalam Q For i = 1 To Q.Count 'cari node yang terhubung melalui node u For j = 1 To myEdges.Count Set tEdge = myEdges(j) If tEdge.Node1.ID = u.ID And tEdge.Node2.ID = Q.Nodes(i).ID Then 'jika terhubung melalui node u, ubah d jika lebih besar dari d(u)+w(u,v) If Q.Nodes(i).d > u.d + tEdge.getJarak Then myGraph.Nodes(Q.Nodes(i).ID).d = u.d + tEdge.getJarak Set pi(Q.Nodes(i).ID) = u End If End If Next j Next i End Sub
11
setSourceNode dan getShortestPath Sepasang prosedur ini digunakan untuk mencari jalur terpendek dari source node ke node-node yang lainnya. Sebelum memanggil prosedur getShortestPath, harus dijalankan dulu setSourceNode dengan input salah satu node pada graph sebagai source node. Kemudian akan dijalankan prosedur Dijkstra untuk mencari seluruh jalur terpendek yang bisa ditempuh dari source node menuju nodenode yang lain. Selanjutnya, prosedur getShortestPath akan mengembalikan nilai jalur terpendek dari source node menuju node yang diinginkan. Public Sub setNodeSource(sourceNode As cNode) Set myPath = New Collection Set sNode = sourceNode 'lakukan algoritma djisktra Djikstra End Sub Public Function getShortestPath(nodeAkhir As cNode) As Boolean Dim nodePath As cNode Dim tempPath As New Collection 'temporari path (dalam urutan terbalik) Set myPath = New Collection Set nodePath = nodeAkhir 'jika tidak ditemukan path If nodePath.d = Infinite Then dSP = 0 getShortestPath = False Exit Function End If 'jika ditemukan path tempPath.Add nodePath While nodePath.ID <> sNode.ID Set nodePath = pi(nodePath.ID) tempPath.Add nodePath Wend dSP = nodeAkhir.d Dim i As Integer 'buat path dari node awal ke node akhir For i = 0 To tempPath.Count - 1 myPath.Add tempPath.Item(tempPath.Count - i) Next i getShortestPath = True End Function
Ilustrasi Pencarian Jalur Terpendek pada VRN Ilustrasi pencarian jalur terpendek menuju ruangan/lokasi yang diinginkan dapat dijelaskan sebagai berikut. Pada Lampiran 12, diilustrasikan proses awal pencarian jalur terpendek, dimana user berada pada ruangan E (diilustrasikan sebagai kotak hijau) dan akan mencari jalur yang bisa ditempuh untuk menuju ruangan C. Garis-garis warna biru beserta titik-titik warna merah adalah hasil implementasi graph pada ruangan tersebut. Pada kasus ini, dapat dilihat bahwa node tujuannya adalah c1. Permasalahan yang timbul adalah menentukan node awal (source node) untuk pencarian shortest path, karena user tidak tepat berada di atas sebuah node. Untuk mengatasi masalah ini, penulis membuat sebuah node baru yang bersifat sementara dengan lokasi tepat pada lokasi user. Setelah itu dibuat beberapa edge yang bersifat sementara juga dari node baru tersebut menuju node-node lain yang masih berdekatan. Setalah node dan edge baru tersebut terbentuk, sekarang dapat ditentukan bahwa node awal dari pencarian shortest path ini adalah node yang baru tersebut. Kemudian akan dijalankan algoritma Dijkstra untuk menentukan path terpendek yang dapat ditempuh menuju c1. Ilustrasinya dapat dilihat pada Lampiran 13. Kontrol Navigasi Pada bagian navigator ini, pengguna dapat melakukan navigasi dengan menggunakan tombol-tombol keyboard. Tombol yang digunakan adalah tombol panah atas untuk maju, tombol panah bawah untuk mundur, dan tombol kiri dan kanan untuk gerak berputar ke kiri dan ke kanan. Fungsi pencarian jalur terpendek, diimplementasikan melalui menu Go To. Pengguna dapat memilih pilihan ruangan/lokasi yang ada, atau dapat juga dengan mengetikkan secara langsung pada form yang disediakan. Tampilan form untuk pencarian jalur terpendek menuju suatu ruangan/lokasi tertentu dapat dilihat pada Lampiran 14. Implementasi denah Denah ditampilkan dalam sebuah area kecil disamping tampilan miniatur 3D. Tampilan ini akan merepresentasikan posisi dan arah dari pengguna dalam sistem miniatur 3D. Implementasi tampilan layar denah dapat dilihat pada Lampiran 15.
12
Editor Sama halnya dengan navigator, editor juga diimplementasikan menggunakan bahasa pemrograman Microsoft Visual Basic 6.0. Untuk keperluan penyimpanan password dan graph digunakan database Microsoft Office Access 2003. Tampilan implementasi layar editor dapat dilihat pada Lampiran 16. Sebelum pengguna dapat menggunakan fungsi-fungsi dalam editor, pengguna diharuskan memasukkan kata sandi (password) terlebih dahulu. Tampilan implementasi form login ini dapat dilihat pada Lampiran 17. Untuk melakukan penggantian password, pengguna dapat menggunakan menu Change Password. Implementasi form penggantian password ini dapat dilihat pada Lampiran 18. Pengujian Unit Setelah bagian navigator dan editor selesai diimplementasikan, selanjutnya masingmasing bagian akan diuji apakah fungsi/proses pada masing-masing bagian tersebut telah berjalan sebagaimana mestinya. Hasil pengujian untuk bagian navigator dapat dilihat pada Lampiran 19. Sedangkan hasil pengujian bagian editor dapat dilihat pada Lampiran 20. Fase Integrasi dan Pengujian Sistem Setalah semua bagian-bagian sistem telah selesai diimplementasikan dan diuji, dan telah berjalan sesuai dengan fungsi yang diharapkan, selanjutnya masing-masing bagian ini, yaitu navigator dan editor disatukan menjadi satu kesatuan paket program. Pengujian sistem (sistem testing) dilakukan untuk memastikan apakah semua kebutuhan fungsional sistem telah terpenuhi. Hasil uji sistem menggunakan metode black box dapat dilihat pada Lampiran 21 dan Lampiran 22.
KESIMPULAN DAN SARAN Kesimpulan Sistem Virtual Room Navigator (VRN) yang dikembangkan kali ini merupakan kelanjutan dari sistem VRN sebelumnya, yang telah dikembangkan oleh Nugroho (2004). Pengembangan dilakukan berdasarkan saransaran yang diberikan oleh pengembang sebelumnya. Fasilitas-fasilitas yang telah ditambahkan pada sistem VRN yang baru ini diantaranya adalah:
• Penambahan fasilitas denah 2D untuk mengetahui lokasi aktual tampak dari atas. • Fasilitas pencarian jalur terpendek untuk mempermudah pencarian ruangan tertentu. • Fasilitas editor untuk mempermudah sistem administrator dalam melakukan update miniatur 3D agar selalu sesuai dengan kondisi sesungguhnya. Saran Meskipun sistem ini merupakan perbaikan dari sistem sebelumnya, namun sistem ini masih mempunyai banyak kekurangan dan perlu pengembangan lebih lanjut. Pengembangan yang masih perlu dilakukan diantaranya adalah: • Petunjuk ruangan terdekat yang berubahubah sesuai dengan lokasi aktual. • Integrasi sistem VRN dengan sistem yang lainnya, misalnya dengan sistem pencarian buku. • Penggantian engine 3D State dengan engine yang lebih baru agar bisa menghasilkan visualisasi yang lebih mendekati kenyataan.
DAFTAR PUSTAKA Buchanan B, Pawaskar C, Hauck M, Mouton O. 1997. 3D Programming Guide. 3Dstate Ltd, Israel. Diestel R. 2005. Graph Theory. SpringerVerlag Heidelberg, New York. Freeland S, Thomas C, Robert L. 1997. Data Structures and Algorithms. McGill University: School of Computer Science. http://www.cs.mcgill.ca/~cs251/OldCo urses/1997/topic29/index.html. [7 Desember 2004] Hadwiger M. 2001. Design and Architecture of a Portable and Extensible Multiplayer 3D Game Engine. Thesis. Institute of Computer Graphics Vienna University of Technology. Kay R. 2002. System Development Life Cycle. Computer World Inc. http://www.computerworld.com/action /article.do?command=viewArticleBasi c&articleId=71151&pageNumber=1. [21 Maret 2007]
13
Kruse RL. 1989. Data Structures and Program Design. Prantice Hall, India. LaMothe A. 2003. Tricks of the 3D Game Programming Gurus. Sams Publishing, United States of America. [Microsoft] Microsoft. 2001. Microsoft DirectX 8.1 Programmer’s Reference. Microsoft Corporation. Morris
J. 1998. Data Structures and Algorithms. http://ciips.ee.uwa.edu.au/%7Emorris/ Year2/PLDS210/dijkstra.html. [28 September 2005]
Nugroho WA.2004. Pengembangan Sistem Virtual Room Navigator dengan Visualisasi 3D (Studi Kasus UPT Perpustakaan Pusat IPB). Skripsi. Departemen Ilmu Komputer FMIPA IPB, Bogor. Sommerville I. 2001. Software Enginering. Ed. ke-6. Pearson Education Limited. Susanto R. 2000. Tuntunan Pemrograman Grafik 3D Direct3D. PT Elex Komputindo, Jakarta.
Praktis dengan Media
LAMPIRAN
15
Lampiran 1 Diagram Alir Data (DAD) level 1 Administrator Administrator pilihan menu
1. Login
data user tervalidasi
2. Manajemen VRN hasil manajemen
Administrator
Lampiran 2 Diagram Alir Data (DAD) level 2 Administrator proses 1.Login
pilihan menu
1.1. Input Password
password user
1.2. validasi password
data user tervalidasi
database
15
16
Lampiran 3 Diagram Alir Data (DAD) level 2 Administrator proses 2. Manajemen VRN
2.1. edit miniatur data user tervalidasi
2.2. edit graph hasil manajemen
2.3. ganti password
Administrator
Lampiran 4 Diagram Alir Data (DAD) level 3 Administrator proses 2.1. Edit miniatur
2.1.2. add objek
data user tervalidasi
2.1.1. load miniatur
data miniatur 3D
2.1.3. edit objek 2.1.4. delete objek
data miniatur 3D
hasil manajemen miniatur 3D
File 3DState
2.1.5. save miniatur
data miniatur 3D
hasil manajemen
Administrator
File 3DState
16
17
Lampiran 5 Diagram Alir Data (DAD) level 3 Administrator proses 2.2. Edit graph
2.2.2. edit node
data user tervalidasi
2.2.1. load graph
data graph
2.2.3. edit edge
data graph
hasil manajemen graph
Database
2.1.4. save graph
hasil manajemen
data graph
Administrator
database
Lampiran 6 Diagram Alir Data (DAD) level 3 Administrator proses 2.3. ganti password
data user tervalidasi
2.3.1. Validasi Password
password tervalidasi
2.3.2 Penggantian password hasil manajemen Password baru
Database
Administrator
17
18
Lampiran 7 Diagram Alir Data (DAD) level 1 Pengguna Biasa
Pengguna biasa pilihan menu
1. Load miniatur 3D
Data miniatur 3D
2. Navigasi Tampilan miniatur 3D
Pengguna biasa File 3DState
Lampiran 8 Diagram Alir Data (DAD) level 2 Pengguna biasa proses 2. Navigasi
data miniatur 3D
2.1. navigasi manual
Tampilan miniatur 3D 2.2. pencarian jalur terpendek
Pengguna biasa
18
19
Lampiran 9 Tabel Basis Data untuk Graph 1. Tabel Node merupakan tabel yang menyimpan informasi node-node dalam graph Nama kolom
Tipe Data
Id Nama X Y Z
Number Text Number Number Number
2. Tabel Edge merupakan tabel yang menyimpan informasi edge-edge dalam graph Nama kolom
Tipe Data
Id Node1 Node2 Jarak
Number Number Number Number
Lampiran 10 Hasil implementasi unit navigator
19
20
Lampiran 11 Diagram UML
cGraph myNodes : cNode myEdges : cEdge myPath : cNode S : cNodes Q : cNodes p : cNode
cEdge 0..*
Node1 : cNode Node2 : cNode getJarak
Dijkstra InitDjikstra Relaxation setSourceNode getShortestPath
0..*
cNode
cNodes 0..*
Nodes : cNode addNode ExtractNode
Point : cPoint ID : Long Nama : String d : Double
cPoint X : Double Y : Double Z : Double setPoint getPoint
20
21
Lampiran 12 Ilustrasi pencarian jalur terpendek (awal)
tujuan
user
Lampiran 13 Ilustrasi pencarian jalur terpendek (akhir)
tujuan
user
21
22
Lampiran 14 Dialog box pencarian jalur terpendek
Lampiran 15 Implementasi Denah
22
23
Lampiran 16 Implementasi unit editor
Lampiran 17 Implementasi Form Login untuk editor
Lampiran 18 Implementasi Form Ganti Password
23
24
Lampiran 19 Hasil pengujian untuk unit (bagian) navigator No
Deskripsi Uji
Kondisi Awal
Skenario Uji
1
Menguji fungsi untuk menampilkan miniatur 3D Menguji fungsi navigasi
Sistem belum dijalankan
Jalankan program navigator
Sistem navigator telah dibuka
Tekan tombol panah atas Tekan tombol panah bawah Tekan tombol panah kiri
2
4
5
6
7
Menguji fungsi pencarian jalur terpendek
Menguji fungsi menampilkan posisi dan arah user pada denah Menguji fungsi menampilkan halaman petunjuk penggunaan Menguji fungsi untuk login ke mode editor Menguji fungsi untuk keluar dari sistem
Hasil Uji sukses
Kamera bergerak maju kedepan Kamera bergerak mundur Kamera berputar ke kiri (berlawanan arah jarum jam) Kamera berputar ke kanan (searah jarum jam) Kamera akan bergerak sendiri menuju lokasi yang dituju dengan melawati jalur yang terpendek Tampil jalur terpendek pada denah 2D
sukses
Mencari jalur terpendek dengan mengetikan lokasi yang dituju lewat menu Go To Æ Go To ...
Kamera akan bergerak sendiri menuju lokasi yang dituju dengan melawati jalur yang terpendek Tampil jalur terpendek pada denah 2D
sukses
Sistem navigator telah dibuka
Pengguna melakukan navigasi
Pada denah ditunjukan posisi pengguna dan arahnya
sukses
Sistem navigator telah dibuka
Klik menu Æ Help Manual
Tampil halaman petunjuk penggunaan sistem navigator
-
Sistem navigator telah dibuka
Klik menu Administrator Æ Login
Tampil form login untuk administrator
sukses
Sistem navigator telah dibuka
Klik Exit
Keluar dari aplikasi dan kembali ke sistem Windows
sukses
Tekan tombol panah kanan 3
Hasil yang diharapkan Muncul miniatur 3D perpustakaan pada form navigator
Sistem navigator telah dibuka
Mencari jalur terpendek dengan memilih lokasi-lokasi yang telah tersedia lewat menu Go To
menu
sukses sukses
sukses
sukses
sukses
sukses
24
25
Lampiran 20 Hasil pengujian untuk unit (bagian) editor No
Deskripsi Uji
Kondisi Awal
Skenario Uji
1
Menguji fungsi editing miniatur 3D
Objek yang akan di-edit telah dipilih
Menggeser objek dengan menggunakan mouse Memutar objek dengan menekan tombol RotL atau RotR Merubah ukuran objek dengan menekan tombol Dec atau Inc Menambah objek baru dengan cara memilih objek dari objek browser kemudian menyeretnya ke tampilan editor Menghapus objek dengan cara menekan tombol Delete Menambahkan node baru dengan posisi tombol node terpilih, kemudin klik pada lokasi yang diinginkan Menggeser posisi node menggunakan mouse Memberi nama node dengan cara klik kanan pada node terpilih, kemudian klik menu Name
2
Menguji fungsi editing graph
Node atau edge yang akan di-edit terlah terpilih
Hasil yang diharapkan Objek yang terpilih bergeser lokasinya menuju tempat yang diinginkan Objek yang terpilih berubah arahnya
Hasil Uji sukses
sukses
Objek yang terpilih berubah ukurannya menjadi lebih kecil atau lebih besar
sukses
Tampil objek baru pada tampilan miniatur 3D
sukses
Objek yang terpilih terhapus dari tampilan miniatur 3D
sukses
Tampil node baru pada tampilan miniatur 3D
sukses
Node yang terpilih bergeser posisinya
sukses
Tampil nama node disebelah titik yang merepresentasikan node
sukses
25
26
Lampiran 20 lanjutan No
3
4
5
6
Deskripsi Uji
Menguji fungsi untuk menyimpan hasil perubahan yang telah dilakukan Menguji fungsi untuk mengubah password Menguji fungsi untuk keluar dari editor dan kembali ke mode navigator Menguji fungsi untuk menampilkan halaman petunjuk penggunaan
Kondisi Awal
Miniatur 3D dan graph telah selesai diperbarui
Skenario Uji Menghapus node dengan cara menekan tombol Delete Menambahkan edge baru dengan cara menekan tombol Edge, kemudian klik node awal dan node akhir Menghapus edge dengan cara klik tombol Delete Klik tombol Save
Hasil yang diharapkan Node yang terpilih menghilang dari tampilan miniatur 3D
Hasil Uji sukses
Tampil edge baru yang menghubungkan node awal dan node akhir yang dipilih
sukses
Edge yang terpilih menghilang dari tampilan miniatur 3D
sukses
Miniatur 3D dan graph tersimpan perubahannya
sukses
Sistem editor telah terbuka
Klik menu Password
Tampil form untuk mengubah password
Sukses
Sistem editor telah terbuka
Klik menu Logout
Keluar dari aplikasi editor dan kembali ke aplikasi navigator
Sukses
Sistem editor telah terbuka
Klik menu Help Æ Manual
Tampil halaman petunjuk penggunaan editor
-
26
27
Lampiran 21 Hasil pengujian form login No
Deskripsi Uji
Kondisi Awal
Skenario Uji
1
Validasi login
Form login telah terbuka
Pengguna tidak mengisi password, atau mengisi password yang salah, kemudian menekan tombol OK Pengguna menekan tombol Cancel Pengguna mengisi password yang benar kemudin menekan tombol OK
Hasil yang diharapkan Muncul pesan bahwa password salah dan harus mengulanginya lagi
Hasil Uji sukses
Form login tertutup lagi, tanpa masuk ke form Editor
sukses
Form login tertutup, dan masuk ke form Editor
sukses
27
28
Lampiran 22 Hasil pengujian form ganti password No
Deskripsi Uji
Kondisi Awal
Skenario Uji
1
Menguji fungsi ganti password
Form ganti password telah terbuka
Pengguna tidak mengisi password lama dengan benar Pengguna tidak mengisikan password baru Password baru tidak sama dengan konfirmasi password baru Pengguna menekan tombol Cancel Pengguna mengisi password lama dengan benar, password baru sama dengan konfirmasi password baru, kemudin menekan tombol OK
Hasil yang diharapkan Muncul pesan bahwa password lama salah
Hasil Uji sukses
Tombol OK tidak aktif
sukses
Tombol OK tidak aktif
sukses
Form ganti password tertutup, tanpa merubah password
sukses
Muncul konfirmasi penggantian password
Sukses
28
