5
BAB II
LANDASAN TEORI
2.1 Game
Game merupakan bentuk partisipatif, interaktif dan hiburan. Menonton televisi,
membaca, dan pergi ke teater merupakan bentuk hiburan pasif. Sedangkan ketika
seseorang bermain game, mereka terhibur dengan berpartisipasi secara aktif. Game
dibuat dengan adanya aturan-aturan tertentu. Aturan tersebut menentukan tindakan
atau langkah yang dapat dan tidak dapat dilakukan oleh pemain dalam sebuah game.
Game dapat diklasifikasikan menjadi beberapa jenis, yaitu berdasarkan platform yang
digunakan, dimensi, dan genre dari game itu sendiri.
2.1.1 Platform
Merupakan kombinasi spesifik dari komponen elektronik atau perangkat keras
komputer dengan perangkat lunak yang memungkinkan game untuk beroperasi.
Berdasarkan platform yang digunakan, game dapat dibagi menjadi beberapa jenis,
diantaranya:
a. Arcade games, yaitu game yang biasanya memiliki box atau mesin yang
memang khusus di desain untuk jenis video games tertentu, bahkan memiliki fitur yang
dapat membuat pemainnya lebih merasa masuk dan menikmati, seperti pistol, kursi
khusus, sensor gerakan, sensor pijakan dan stir mobil. Arcade games biasanya berada
di daerah/tempat khusus, sebagai contoh di Indonesia dikenal dengan sebutan ding-
dong.
b. PC games, yaitu game yang dimainkan menggunakan komputer pribadi.
c. Console games, yaitu game yang dimainkan menggunakan konsol tertentu,
seperti Playstation 2, Playstation 3, XBOX 360, dan Nintendo Wii.
d. Handheld games, yaitu game yang dimainkan di konsol khusus video game
yang dapat dibawa kemana-mana (portable), sebagai contoh Nintendo DS dan Sony
PSP.
6
e. Mobile games, yaitu game yang dapat dimainkan khusus untuk mobile phone
atau PDA.
2.1.2 Dimensi
Adalah angka yang berhubungan dengan sifat metrik atau topologi dari suatu objek.
Berdasarkan dimensi dari objek-objeknya, game dapat dibagi menjadi beberapa jenis,
diantaranya:
a. Game 2D
Game dua dimensi atau 2D merupakan suatu konsep dimana semua objek berada
pada satu bidang datar. Gerakan pada game 2D dibatasi hanya horizontal dan vertikal
atau secara koordinat gerakan pemain dibatasi hanya dapat bergerak pada sumbu X
danY. Pada game 2D terdapat dua pergerakan kamera. Pertama adalah kamera statis
dimana gambar latar (backround) dan tempat game 2D tidak bergerak sama sekali,
contoh dalam jenis ini adalah tetris. Kedua adalah Side Scrolling dimana game yang
kita mainkan mempunyai kamera yang dapat bergeser ke kanan atau ke kiri dengan
kecepatan sesuai dengan gerakan dan kecepatan karakter yang kita mainkan/gerakkan
pada game tersebut, contoh game yang termasuk pada jenis ini adalah Super Mario
Bross, Sonic dan Megaman.
b. Game 2.5D
Setelah game 2D, muncul game dengan tampilan 3D datar (3D Plane). Game
seperti ini bukan 2D tapi tidak juga full 3D. Teori grafik seperti ini disebut dengan
2.5D atau pseudo-3D, sedangkan pada istilah game lebih dikenal dengan istilah
isometric, diametric atau trimetric projection. Biasanya gameplay dari game 2.5D
mirip 2D dimana kita hanya bisa bergerak secara horizontal dan vertikal, namun
beberapa objek menggunakan teknik rendering secara 3D. Salah satu hal yang
membuat developer game membuat game seperti ini karena pemrosesan 3D secara total
memerlukan banyak waktu dan biaya untuk membuatnya.
c. Game 3D
Game 3D menggunakan tiga dimensional representasi geometris data (X, Y, Z)
yang disimpan dalam komputer untuk keperluan perhitungan dan rendering gambar
7
2D. Dalam sebuah game 3D, pemain bisa melihat sebuah objek dari sudut 360°.
Terdapat tiga dasar dalam pembuatan sebuah objek 3D, yaitu 3D modeling, 3D
rendering, dan 3D computer graphics software.
2.1.3 Genre
Genre pada suatu game memperlihatkan pola umum tantangan dari game
tersebut. Dengan perkembangan informasi seperti sekarang, genre dari game masih
terus berkembang, sebagai contoh simulasi menari (dance simulation) yang
diperkenalkan oleh desainer game dari Jepang. Namun secara umum game dapat dibagi
menjadi beberapa jenis berdasarkan genre yang diterapkannya, yaitu:
a. Game Strategi (Strategy Games)
Asal-usul dari game strategi berasal dari game papan seperti catur dan Othello.
Pada game strategi biasanya pemain dapat mengendalikan tidak hanya satu karakter,
melainkan beberapa karakter dalam game tersebut dengan berbagai jenis tipe
kemampuan, kendaraan, hingga pembuatan berbagai bangunan, pabrik dan pusat
pelatihan tempur, tergantung dari tema ceritanya. Game strategi dibagi menjadi 2
bentuk utama, yaitu classical turn-based strategy dan real-time strategy.
b. Role-Playing Games (RPG)
Game RPG sama seperti game strategi, yaitu salah satu genre yang dibuat dari game
yang berasal dari kertas dan pena. Dua hal yang hampir sama pada semua game RPG,
yaitu konfigurasi dari karakter pemain yang meningkat berdasarkan experience dan
jalan cerita (storyline) yang kuat. Oleh karena itu, terdapat dua elemen utama yang
menjadi kunci suksesnya sebuah game RPG. Fitur yang pertama adalah cerita (story)
dan fitur yang kedua adalah pembangunan karakter (character development).
c. Game Olahraga (Sports Games)
Game olahraga mempunyai tantangan yang tidak biasa bagi seorang desainer game.
Tidak seperti game-game yang lain, dimana pemain memiliki sedikit pengetahuan
mengenai dunianya, tetapi game olahraga meniru aturan pada olahraga di kehidupan
nyata.
d. Simulasi Kendaraan (Vehicles Simulation)
8
Pada simulasi kendaraan, pemain dihadapkan dalam suatu kondisi seolah-olah
pemain mengemudikan atau menerbangkan sebuah kendaraan, secara nyata atau
imajinasi. Pada simulasi kendaraan yang nyata, salah satu tujuan yang harus dicapai
adalah kemiripan kendaraan, seperti karakteristik kinerja mesin (kecepatan dan
manuver) dengan kendaraan yang sebenarnya. Namun, jika mendesain kendaraan
imajinasi, kita bebas untuk membuat driving experience untuk pemain, tanpa harus
terbatas oleh gravitasi, G-forces, kapasitas bensin, dan lainnya.
e. Game Petualangan (Adventure Games)
Game petualangan bukan merupakan sebuah kompetisi atau simulasi seperti game
yang lainnya. Game jenis ini tidak menawarkan proses untuk dikelola atau
mengalahkan musuh melalui strategi dan taktik. Game petualangan merupakan cerita
interaktif mengenai karakter yang dikontrol oleh pemain.
f. Game Puzzle (Puzzle Games)
Game puzzle merupakan game yang bertujuan untuk memecahkan sebuah puzzle,
terkadang tanpa menyatukan dengan jalan cerita atau tujuan yang lebih besar. Game
jenis ini biasanya bervariasi pada satu tema saja. Untuk kesuksesan secara komersil,
sebuah game puzzle haruslah memiliki tantangan, visual yang atraktif, dan disamping
itu nyaman untuk dimainkan.
g. Game Aksi (Action Games)
Games aksi merupakan sumber yang baik bagi elemen desain dari sebuah game.
Game ini relatif sederhana karena membuat analisis dari game tersebut lebih mudah,
jika dibandingkan dengan genre lain. Aturan dari sebuah game action menjelaskan
dasar dari mekanika game. Mereka biasanya lebih simpel dalam aturan, karena
kealamian dari gameplay-nya. Intinya, game action merupakan game yang
membutuhkan keterampilan seperti pengolahan informasi sensorik dan tindakan secara
cepat. Hal ini memaksa pemain untuk membuat keputusan dan melakukan tanggapan
pada kecepatan yang jauh lebih besar.
9
2.2 Labirin
Labirin adalah salah satu bagian permainan teka-teki yang memiliki
percabangan yang kompleks dan pemain harus dapat menemukan rute keluar. Sejak
zaman dahulu, labirin telah digunakan dalam berbagai kepentingan, mulai dari proteksi
keamanan hingga hiburan. Pada umumnya, labirin dibuat untuk tujuan hiburan. Dalam
kehidupa nyata, labirin dapat ditemukan pada susunan jalan kecil atau gang-gang di
kawasan perumahan. Sangat sulit bila seseorang yang asing dengan daerah tersebut
untuk mencari jalan.
Labirin dalam dunia nyata banyak dibuat di taman atau ruangan-ruangan
dengan pembatas berupa pagar tanaman, tembok atau pagar. Ukurannya bervariasi,
tergantung ukuran ruangan atau taman tersebut. Labirin ini biasanya memang
dirancang untuk menjadi sebuah atraksi permainan (misalnya rumah kaca) atau hanya
sebagai hiasan saja. Selain itu banyak labirin yang terbentuk secara “tidak sengaja”.
Contohnya jalan-jalan kecil atau gang-gang yang terbentuk diantara rumah-rumah pada
kawasan pemukiman.
Salah satu bentuk Maze adalah labirin(Labyrinth). Labirin adalah nama
bangunan pada mitos Yunani. Labirin dibangun oleh Daedalus atas perintah raja
Minos. Labirin dibangun untuk mengurung Minotaur, monster setengah manusia
setengah sapi. Daedalus membangun labirin bersama anaknya Icarus. Untuk keluar dari
labirin, Daedalus dan Icarus membuat sayap dari bulu dan lilin.
2.3 Blender
Blender adalah salah satu software open source yang digunakan untuk
membuat konten multimedia khusunya 3 Dimensi, ada beberapa kelebihan yang
dimiliki Blender dibandingkan software sejenis. Berikut beberapa kelebihannya:
a. Open Source
Blender merupakan salah satu software open source, dimana kita bisa bebas
memodifikasi source codenya untuk keperluan pribadi maupun komersial, asal tidak
melanggar GNU General Public License yang digunakan Blender.
b. Multi Platform
10
Karena sifatnya yang open source, Blender tersedia untuk berbagai macam operasi
sistem seperti Linux, Mac dan Windows. Sehingga file yang dibuat menggunakan
Blender versi Linux tak akan berubah ketika dibuka di Blender versi Mac maupun
Windows.
c. Update
Dengan status yang Open Source, Blender bisa dikembangkan oleh siapapun.
Sehingga update software ini jauh lebih cepat dibandingkan software sejenis lainnya.
Update Blender tak tersedia di situs resmi blender.org melainkan di graphicall.org.
d. Free
Blender merupakan sebuah software yang gratis. Blender gratis bukan karena tidak
laku, melainkan karena luar biasanya fitur yang mungkin tak dapat dibeli dengan uang,
selain itu dengan digratiskannya software ini, siapapun bisa berpartisipasi dalam
mengembangkannya untuk menjadi lebih baik.
e. Lengkap
Blender memiliki fitur yang lebih lengkap dari software 3D lainnya, tersedia fitur
Video editing, Game Engine, Node Compositing, Sculpting.
f. Ringan
Blender relatif ringan jika dibandingkan software sejenis. Hal ini terbuti dengan
sistem minimal untuk menjalankan Blender.
Blender memiliki ukuran instalasi yang relatif kecil dan dapat
diimplementasikan di semua platform komputer. Walaupun sering didistribusikan
tanpa adanya dokumentasi yang cukup atau tanpa contoh yang jelas, software ini
mengandung beberapa fitur yang hampir sama dengan software modelling terbaru.
Beberapa kemampuan dari blender adalah mendukung ke-anekaragaman dari bentuk
geometri primitif, termasuk polygon yang tak beraturan, fast subdivision, surfaced
modeling, kurva bezier, metalballs dan lain-lain.
Blender memiliki kemampuan rendering internal yang cukup handal dan
terintregrasi dengan YafRay yaitu Free Software untuk ray tracer. Didukung dengan
keyframed animation tools termasuk kinematic invers, armature (skeleton), shape keys
11
(morphing), animasi nonlinier, pemberian bobot pada vertex, pendeteksian mesh
colution, particle based hair, dan partikel sistem dengan collution detection.
Didukung oleh phyton scripting untuk menciptakan tools baru dan prototyping,
game logic, import dan export dari format lain seperti OBJ, FBX, DFX dan task
automation. Memiliki kemampuan untuk editing video atau audio yang nonlinier dan
masih banyak lagi fitur yang lain yang merupakan teknologi high-end.
2.4 Algoritma A* dan Dijkstra
a. A*
Algorima A* dapat juga disebut sebagai Algoritma A Star, merupakan salah satu
contoh algoritma pencarian yang cukup populer di dunia. Beberapa terminologi dasar
yang terdapat pada algoritma ini adalah starting point, simpul (nodes), A, open list,
closed list, harga (cost), halangan (unwalkable).
1. Starting point adalah sebuah terminologi untuk posisi awal sebuah benda.
2. A adalah simpul yang sedang dijalankan dalam algortima pencarian jalan
terpendek.
3. Simpul adalah petak-petak kecil sebagai representasi dari area pathfinding.
Bentuknya dapat berupa persegi, lingkaran, maupun segitiga.
4. Open list adalah tempat menyimpan data simpul yang mungkin diakses dari
starting point maupun simpul yang sedang dijalankan.
5. Closed list adalah tempat menyimpan data simpul sebelum A yang juga
merupakan bagian dari jalur terpendek yang telah berhasil didapatkan.
6. 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
perkiraan dari sebuah simpul ke simpul tujuan.
7. Simpul tujuan yaitu simpul yang dituju.
8. Rintangan adalah sebuah atribut yang menyatakan bahwa sebuah simpul tidak
dapat dilalui oleh A.
12
Prinsip algoritma ini adalah mencari jalur terpendek dari sebuah simpul awal (starting
point) menuju simpul tujuan dengan memperhatikan harga (F) terkecil.
Pseudocode algoritma A*
Gambar 2.1 Pseudocode Algoritma A*
Diawali dengan menempatkan A pada starting point, kemudian memasukkan seluruh
simpul yang bertetangga dan tidak memilik atribut rintangan dengan A ke dalam open
list. Kemudian mencari nilai H terkecil dari simpul-simpul dalam open list tersebut.
Kemudian memindahkan A ke simpul yang memiliki nilai H terkecil. Simpul sebelum
A disimpan sebagai parent dari A dan dimasukkan ke dalam closed list. Jika terdapat
simpul lain yang bertetangga dengan A (yang sudah berpindah) namun belum termasuk
ke dalam anggota open list, maka masukkan simpul-simpul tersebut ke dalam open list.
OPEN
CLOSED
add the start node to OPEN
loop
current = node in OPEN with the lowest f_cost
remove current from OPEN
add current to CLOSED
if current is the target node
return
foreach neighbour of the current node
if neighbour is not traversable or neighbour is in CLOSED
skip to the next neighbour
if new path to neighbour is shorter or neighbour is not in OPEN
set f_cost of neighbour
set parent of neighbour to current
if neighbour is not in OPEN
add neighbour to OPEN
13
Setelah itu, bandingkan nilai G yang ada dengan nilai G sebelumnya (pada langkah
awal, tidak perlu dilakukan perbandingan nilai G). Jika nilai G sebelumnya lebih kecil
maka A kembali ke posisi awal. Simpul yang pernah dicoba dimasukkan ke dalam
closed list. Hal tersebut dilakukan berulang-ulang hingga terdapat solusi atau tidak ada
lagi simpul lain yang berada pada open list.
b. Dijkstra
Algoritma Dijkstra merupakan algoritma yang paling sering digunakan dalam
pencarian rute terpendek, sederhana penggunaannya dengan menggunakan simpul-
simpul sederhana pada jaringan jalan yang tidak rumit (Chamero, 2006). Adapun nama
algoritma Dijkstra sendiri berasal dari penemunya yaitu Edsger Dijkstra.
Dalam mencari solusi, algoritma Dijkstra menggunakan prinsip greedy, yaitu
mencari solusi optimum pada setiap langkah yang dilalui, dengan tujuan untuk
mendapatkan solusi optimum pada langkah selanjutnya yang akan mengarah pada
solusi terbaik. Hal ini membuat kompleksitas waktu algoritma Dijkstra menjadi cukup
besar, yaitu sebesar O (V * Log (v + e)), dimana v dan e adalah simpul dan sisi pada
graf yang digunakan.
Input dari algoritma Dijkstra berupa sebuah graf berbobot G(e , v), sedangkan
outputnya berupa rute terpendek dari simpul awal (start) ke masing-masing simpul
yang ada pada graf. Dengan demikian algoritma Dijkstra dapat menemukan solusi
terbaik.
Cara kerja algoritma Dijkstra hampir sama dengan cara kerja algoritma BFS
yaitu dengan menggunakan prinsip antrian (queue), akan tetapi yang digunakan
algoritma Dijkstra adalah antrian berprioritas (priority queue). Jadi hanya simpul yang
memiliki prioritas tertinggi yang akan ditelusuri. Dalam menentukan simpul yang
berprioritas, algoritma ini membandingkan setiap nilai (bobot) dari simpul yang berada
pada satu level. Selanjutnya nilai (bobot) dari setiap simpul tersebut disimpan untuk
dibandingkan dengan nilai yang akan ditemukan dari rute yang baru ditemukan
kemudian, begitu seterusnya sampai ditemukan simpul yang di cari.
14
Berikut ini pseudocode algoritma Dijkstra dalam mencari rute terpendek pada sebuah
graf.
Pseudocode algoritma Dijkstra
Gambar 2.2 Pseudocode Algoritma Dijkstra
function Dijkstra(Graph, source):
dist[source] := 0
prev[source] := undefined
for each vertex v indexer Graph:
if v != source
dist[v] := infinity
prev[v] := undefined
end if
add v to Q
end for
while Q is not empty:
u := vertex in Q with min dist[u]
remove u from Q
for each neighbour v of u :
alt := dist[u] + length(u,v)
if alt < dist[v]:
dist[v] := alt
prev[v] := u
end if
end for
end while
return dist[], prev[]
end function
15
Pada pseudocode Dijkstra tersebut terdapat tiga elemen utama yang menggambarkan
kondisi status dari setiap simpul yang sedang ditelusuri. Adapun tiga kondisi tersebut
yaitu:
1. Kondisi node yang belum ditemukan dan belum dikunjungi.
2. Kondisi node yang sudah ditemukan tetapi belum dikunjungi.
3. Kondisi node yang telah detemukan dan sudah dikunjungi.
Dalam hal ini node yang dikunjungi merupakan node yang terpendek dari setiap
tahap algoritma Dijkstra. Jadi jalur atau rute yang dibentuk oleh algoritma Dijkstra
tersusun dari node yang telah ditemukan dan telah dikunjungi.
Adapun langkah-langkah dari algoritma Dijkstra sesuai pseudocode di atas yaitu:
1. Langkah pertama yaitu menetapkan node awal sebagai status ditemukan
(found) dan kemudian dikunjungi atau ditangani (handled).
2. Langkah kedua yaitu dilakukan pencarian terhadap setiap node yang dapat
dicapai secara langsung dari node yang sedang dikunjungi.
3. Langkah ketiga yaitu:
a.) Apabila node yang didapatkan pada langkah kedua belum pernah dite-
mukan, maka rubah statusnya menjadi ditemukan.
b.) Apabila node yang didapatkan sudah pernah ditemukan maka lakukan
update pada bobotnya, ambil bobot yang lebih kecil.
4. Langkah keempat yaitu dilakukan pencarian terhadap node yang memiliki
bobot paling kecil dari semua node yang berada pada status ditemukan kemudian
mengunjunginya.
5. Lakukan looping secara berurutan pada langkah kedua, ketiga dan keempat
sampai semua node ditemukan.
Algoritma ini adalah salah satu algoritma greedy. Pada algoritma ini
pemeriksaan simpul akan dilakukan ke segala arah yang dimungkinkan yang pada
akhirnya seluruh simpul pada sebuah graf akan diperiksa. Hal ini menyebabkan
algoritma ini bekerja dengan lambat dan menggunakan memori yang besar sehingga
waktu yang diperlukan untuk menemukan solusi akan semakin besar pula.
16
2.5 Unity3D Engine
Unity Engine merupakan game engine yang terus berkembang. Engine ini
merupakan salah satu game engine dengan lisensi source proprietary, namun untuk
lisensi pengembangan dibagi menjadi 2, yaitu free (gratis) dan berbayar sesuai
perangkat target pengembangan aplikasi. Unity tidak membatasi publikasi aplikasi,
pengguna Unity dengan lisensi gratis dapat mempublikasikan aplikasi yang dibuat
tanpa harus membayar biaya lisensi atau royalti kepada Unity. Tetapi penggunaan versi
free dibatasi dengan beberapa fitur yang dikurangi atau bonus modul/prefab tertentu
yang ditiadakan dan hanya tersedia untuk pengguna berbayar.
Seperti kebanyakan game engine lainnya, Unity Engine dapat mengolah
beberapa data seperti objek tiga dimensi, suara, tekstur, dan lain sebagainya.
Keunggulan dari unity engine ini dapat menangani grafik dua dimensi dan tiga dimensi.
Namun engine ini lebih konsentrasi pada pembuatan grafik tiga dimensi. Dari beberapa
game engine yang sama-sama menangani grafik tiga dimensi, Unity Engine dapat
menangani lebih banyak. Beberapa diantaranya yaitu Windows, MacOS X, iOS, PS3,
wii, Xbox 360, dan Android yang lebih banyak daripada game engine lain seperti
Source Engine, GameMaker, Unigine, id Tech 3 Engine, id Tech 4 Engine, Blender
Game Engine, NeoEngine, Unity, Quake Engine, C4 Engine atau game engine lain.
Unity Engine memiliki kerangka kerja (framework) lengkap untuk
pengembangan profesional. Sistem inti engine ini menggunakan beberapa pilihan
bahasa pemrograman, diantaranya C#, javascript maupun boo. Unity3D editor
menyediakan beberapa alat untuk mempermudah pengembangan yaitu Unity Tree dan
terrain creator untuk mempermudah pembuatan vegetasi dan terrain serta
MonoDevelop untuk proses pemrograman.
Dalam pengerjaan, aplikasi ini menggunakan library Unity AR. UnityAr
menyediakan sebuah interface ke ARToolkit yang dikemas secara menarik oleh
unity3D. Webcam yang terhubung lokal digunakan sebagai sumber masukan untuk
pengenalan pola. Interface ini memungkinkan untuk mendeteksi beberapa source dari
aplikasi yang berjalan. Melalui UnityAR pengguna akan diberikan informasi tentang
posisi dan rotasi suatu pola yang telah terdaftar sebelumnya.
17
Dengan adanya gabungan antara ARToolkit dan Unity, dapat mempermudah pengguna
untuk mengembangkan aplikasi berbasis augmented reality.