Game Design Prog

Game Design Programming Blog

2301857720 - Octavionus Chandra

Technical Specifications

Game Name:

Vampire's Lair

View:

3rd Person View

Platform:

Windows PC

Language:

C#

Device:

PC

GAME PLAY 

Game Play Outline 

The outline of this game will be a basic shooter game. Where Player have to shoot the mobs to survive, the mobs in this game are vampires that can give damage and kill the player. Not only that, the player will also have to find a way out of the lair by exploring the whole map. That way, they can win the game. 

Key Features 

Player will need to shoot at the vampires to survive, and find their way out through the map to win the game.

DESIGN DOCUMENT 

- Players will be seen in third person view, and can got hurt if they did not protect themselves from the vampires. 

- Vampires will be coming towards the player, even if they were being shot until they die. They will die when they get shot with a lot of damage.

Design Guidelines 

The design guidelines for this game for the assets needed will have to be a rather filthy looking place, to make sure the player can feel like this place had been abandoned, and now is infested with vampires. The vampires need to be a different colour, not too bright, but has enough contrast to make sure player can know what to shoot and what not to shoot. The weapon designs are also chosen to be similar to what the weapons in real life are supposed to be. That way, the player will know what the weapon can do, and they can estimate the damage output of each different weapons.

Game Design Definitions 

Player will win if they find a way out and defeat the boss vampire without having their HP go under 0. They will have to explore the map to find out where the final boss is, so they can escape the lair and win the game. Also, they will have to survive while exploring the map by killing the vampires that goes through their way

Game Flowchart

Player Definition

Player is a woman who is trapped in a lair filled with vampires. With the help of a few weapons, she will be able to escape through the lair by defeating a huge amount of vampires. Player can also get a replenish of their HP and Ammo by going through the map. 

Player Definitions:

• Health: 

Player will get 100 HP, in which they will have to protect themselves so they won’t get killed off by the Vampires

• Weapons:

The weapon given will be a rifle, the player will shoot the vampires with the said rifle.

• Actions:

The vampires will come and hunt the player down, so the player will have to keep shooting the vampires while looking for a way out of the lair to stay alive

Player Properties 

Player gets to choose a weapon when they approach a certain barrel, from a rapid gun, grenade launcher, or flamethrower. They can also replenish their ammo there. If the ammo were to run out, they will return to using a single shot pistol with low damage.

Player Rewards (power-ups and pick-ups) 

- Player can get different weapons in the game when they approach a certain barrel 

- Player can also replenish ammo when they approach a certain barrel 

- Player can also get their health regenerated along the way 

- Different weapons have different effects, such as rapid gun, grenade launcher, or flamethrower 

Link Youtube : https://youtu.be/-yyZnUC5ip4 

Link Game, Code & Asset : https://drive.google.com/drive/folders/1Km983p8x6IBkhZlhv08JnDVA9Nq_y25?usp=sharin

AVL Tree

AVL TREE

AVL Tree adalah bentuk dari Binary Search Tree(BST) yang telah dikembangkan untuk dapat menyeiambangkan dirinya sendiri secara otomatis saat memasukkan data didalamnya dan juga masih memiliki semua sifat dan ciri dari BST.

AVL Tree juga memiliki ciri seperti, setiap root pastinya berada di paling atas; setiap root bisa memiliki nol, satu maupun dua child nodes; setiap child node bisa memiliki nol, satu atau lebih dari satu child node lainnya; dan biasanya setiap node yang berada di posisi kanan memiliki nilai yang relatif kecil daripada node yang berada di kanan yang nilainya relatif lebih besar.

Namun AVL Tree memiliki ciri khasnya yaitu, perbedaan kedalaman antara node kiri dan node kanan tidak boleh melebihi satu, dimana dalam pemrograman AVL Tree harus memiliki kode yang dapat mengatur/mengubah/menyeimbangkan tree pada saat nilai yang baru dimasukkan kedalam node yang baru.

                             
Metode yang ada pada AVL Tree mencakup Insertion dan Deletion

INSERTION

  1. Single LEFT Rotation (LL Rotation)
Jika terjadi ketidak seimbangan pada child node kanan pada subtree kanan maka perlu dilakukan  sebuah Left Rotation.
Hal ini dapat dilakukan dengan cara mengubah satu posisi tiap node dari posisi awalnya ke bagian kirinya.
Seperti contoh:
                                       
Pada contoh tersebut, diambil node yang berisi nilai 85 dan dijadikan sebagai poros agar semua nodenya dapat melakukan Left Rotation sekali.

  2. Single RIGHT Rotation (RR Rotation)
Jika terjadi ketidak seimbangan pada child node kiri pada subtree kiri maka perlu dilakukan  sebuah Right Rotation.
Hal ini dapat dilakukan dengan cara mengubah satu posisi tiap node dari posisi awalnya ke bagian kanannya.
Seperti contoh:
                                             

Pada contoh tersebut, diambil node yang berisi nilai 44 dan dijadikan sebagai poros agar semua nodenya dapat melakukan Right Rotation sekali.

  3. LEFT-RIGHT Rotation (LR Rotation)
Jika terjadi ketidak seimbangan pada child node kiri pada subtree kanan maka perlu dilakukan  sebuah Left-Right Rotation.
Hal ini dapat dilakukan dengan cara menggunakan kombinasi dari Left Rotation kemudian Right Rotation. Dengan setiap node bergeser 1 posisi ke sebelah kiri dari posisi awalnya dan kemudian bergeser sekali lagi ke posisi kanannya. 
Seperti contoh:
                                             
Pada contoh tersebut, diambil node yang berisi nilai 39 menjadi poros kemudian dilakukan Left Rotation dan dilanjutkan dengan mengambil nilai 39 lagi menjadi porosnya dan dilakukan Right Rotation.
  4. RIGHT-LEFT Rotation (RL Rotation)
Jika terjadi ketidak seimbangan pada child node kanan pada subtree kiri maka perlu dilakukan  sebuah Right-Left Rotation.
Hal ini dapat dilakukan dengan cara menggunakan kombinasi dari Right Rotation kemudian Left Rotation. Dengan setiap node bergeser 1 posisi ke sebelah kanan dari posisi awalnya dan kemudian bergeser sekali lagi ke posisi kirinya. 
Seperti contoh:
                                             
Pada contoh tersebut, diambil node yang berisi nilai 40 menjadi poros kemudian dilakukan Right Rotation dan dilanjutkan dengan mengambil nilai 40 lagi menjadi porosnya dan dilakukan Left Rotation.

DELETION
Biasanya dalam operasi Deletion dalam AVL Tree memiliki 2 kasus yaitu,
1. Ketika yang akan dihapus adalah node yang tidak memiliki anak, maka dari itu penghapusan dapat segera dilakukan tanpa mengubah Tree-nya.
2. Ketika yang akan dihapus adalah node yang memiliki anak, maka dari itu proses harus dilakukan  penyeimbangkan Tree-nya setelah melakukan penghapusan.

Hashing and Hash Tables

Hashing

Hashing merupakan teknik untuk menyimpan dan mengambil key dengan cara yang cepat.

Dalam Hashing, string karakter akan diubah value yang lebih pendek, atau menjadi sebuah key yang merepresentasikan string yang asli.

Hashing juga dilakukan untuk mengambil data dari suatu database yang besar, karena mencari data yang diinginkan lebih mudah dengan menggunakan key daripada mencarinya menggunakan valuenya yang asli.

Hashing juga dapat didefinisikan sebagai konsep dari mendistribusikan key-key dalam suatu array yang disebut hash table menggunakan fungsi yang sudah ditentukan sebelumnya yang disebut hash function

Hash Table

Hash Table adalah tabel ( array ) dimana kita menyimpan string yang asli.

Contoh :

Kita mau menyimpan 5 string : define, float, exp, char, atan menjadi hash table berukuran 26. Hash function yang akan kita gunakan adalah "transform the first character of each string into a number between 0..25" ( a --> 0, b --> 1, c --> 2, ..., z --> 25)

Berikut adalah tabel dari permasalahan tersebut :

h[ ]	Value
0	atan
1
2	char
3	define
4	exp
5	float
6
…
25

    

atan disimpan di h[0] karena a adalah 0

char disimpan di h[2] karena c adalah 2

define disimpan di h[3] karena d adalah 3

dan seterusnya

kita hanya mengambil karakter pertama dari masing2 string

Hash Function

Ada banyak cara untuk meng-hash string menjadi sebuah key. Berikut adalah beberapa metode yang penting untuk membuat hash function.

• Mid-square
• Division ( ini merupakan fungsi yang paling umum)
• Folding
• Digit Extraction
• Rotating Hash

1. Mid-square

Kalikan kuadrat string / identifier lalu gunakan bits di tengah2 hasil perkalian kuadrat yang tepat untuk mendapatkan hash-key

Apabila keynya merupakan string, ubahlah ke angka

Langkah-langkah : 

1. Kalikan Kuadrat nilai dari key (k x k)
2. Keluarkan bits tengah dari hasil perkalian di langkah 1

Function : h(k) = s

k = key

s = hash key yang didapatkan melalui memilih bits tengah dari k2

  2. Division

Bagi string / identifier dengan operator modulus. Ini merupakan metode yang paling sederhana untuk meng-hash integer x

  3. Folding

Partisikan string / identifier menjadi beberapa bagian, lalu sambungkan bagian-bagian itu untuk mendapatkan hash key-nya

  1. Divide the key value into a number of parts

  2. Add the individual part (usually the last carry is ignored)

  4. Digit Extraction

Digit tertentu dari angka yang sudah diberikan akan dianggap sebagai hash address

Contoh : 

x = 14,568

Apabila kita extract digit ke-1, 3, dan 5, kita akan mendapatkan hash code 158

  5. Rotating Hash

Gunakan method hash apapun ( seperti division atau mid-square )

Setelah mendapatkan hash code atau alamat dari hash method, lakukan rotasi

Rotasi dilakukan dengan menggeser digit-digit untuk mendapatkan hash address yang baru

Contoh :
hash address : 20021

hasil rotasi    : 12002 (digit-digit tersebut difold)

Collision

Apabila kita memilikki hash function : define, float, exp, char, atan, ceil, acos, floor.

Collision terjadi apabila ada beberapa string yang memilikki hash-key yang sama 

Ada beberapa string yang memilikki hash-key yang sama, seperti : atan, acos, char, ceil, float, floor.

Ada 2 cara yang dapat kita lakukan : 

  1. Linear Probing

h[ ]	Value
0	atan
1	acos
2	char
3	define
4	exp
5	float
6	ceil
7	floor

Ini merupakan hash-table dari string-string tersebut, ceil diletakkan di h[6] dan floor diletakkan di h[7] karena char sudah ada di h[2] dan float sudah ada di h[5], maka ceil dan floor diletakkan di slot yang kosong

h[ ]	Value	Step
0	atan	1
1	acos	2
2	char	1
3	define	1
4	exp	1
5	float	1
6	ceil	5
7	floor	3

Linear probing tidak efektif apabila banyak collision yang terjadi, tabel di atas (step) menunjukan berapa looping yang diperlukan untuk mencari string tersebut

  2. Chaining

0	atan --> acos
1	NULL
2	char --> ceil
3	define
4	exp
5	float --> floor
6	NULL
7	NULL

Dalam chaining, kita menyimpan setiap string di linked list, jadi apabila ada collision, kita hanya peru mengulang di chain itu

Rangkuman Materi Data Structures Sesi 6 (Stack and Queue)

Stack and Queue

1. Stack
Stack adalah Data Structure dengan elemen yang disimpan secara berurutan (ditumpuk).

Analogi :

Contohnya kita menaruh tumpukan piring dalam satu kontainer, pasti akan ada suatu saat kontainer itu penuh dan tidak dapat ditambahkan piring yang lain. Untuk mengubah komponen dari kontainer itu, kita dapat menambahkan atau mengganti piring yang paling atas dengan piring yang lain. AKAN TETAPI proses pengubahan komponen itu hanya dapat kita lakukan di piring yang paling atas

Gambar di atas merupakan representasi dari Stack

Kita juga dapat mengrepresentasikan Stack dengan Array.

Stack dalam Array memiliki 2 variabel : TOP & MAX

TOP : Posisi elemen terakhir dari suatu Stack. Apabila TOP = NULL, stack dikatakan kosong.

MAX : Ini merupakan batas penambahan elemen array dari suatu stack

Berdasarkan gambar di atas

MAX (batas penambahan elemen) dari stack tersebut adalah 8.

TOP (posisi elemen terakhir) dari stack tersebut adalah 4, dimana penambahan dan pengurangan elemen akan terjadi.

Stack juga dapat direpresentasikan dengan Linked List. Metode ini lebih sulit daripada Array, namun lebih efektif, karena dengan metode Array, kita harus mendeklarasikan ukurannya yang tetap.

Dalam Linked List Stack, setiap node memilikki 2 bagian ; Bagian yang menyimpan data, dan bagian yang menyimpan alamat ke node berikutnya

Pointer START dari linked list akan digunakan sebagai TOP, dan semua proses penambahan dan pengurangan  elemen akan dilakukan disini.

Stack Operations

Ada juga Stack Operations, yang merupakan fungsi-fungsi dalam memanipulasi Stack.

1. push(x) : menambahkan elemen x ke TOP dari suatu Stack

2. pop()    : menghapus elemen dari TOP dalam suatu Stack

3. top()     : menyatakan elemen di urutan tertentu sebagai TOP

Untuk lebih jelasnya, dapat dilihat dari gambar berikut

2. Queue

Perbedaan utama antara Stack dan Queue adalah : Elemen yang keluar.

Dalam Stack diterapkan sistem First In Last Out (FILO), yang artinya data yang pertama kali masuk ke dalam stack akan menjadi data yang terakhir untuk keluar.

Sedangkan dalam Queue diterapkan sistem First In First Out(FIFO), yang artinya data yang pertama kali masuk ke dalam queue juga akan menjadi data yang pertama kali keluar dari queue.

Analogi sederhananya bisa dilihat dari orang yang mengantri untuk ke bus (masuk ke tempat menunggu bus), orang yang berada di paling depan barisan akan menjadi yang pertama untuk masuk ke dalam bus (meninggalkan tempat menunggu bus).

Variabel dalam Stack terdiri atas TOP dan MAX, sedangkan variabel dalam Queue terdiri atas Front dan Rear

Dalam Linked List, pointer START akan digunakan sebagai Front.

Penambahan akan dilakukan di Rear.

Penghapusan akan dilakukan di Front.

Apabila FRONT = END = NULL, queue dapat dikatakan kosong.

Queue Operations

1. push(x) : untuk menambahkan sebuah elemen ke Rear dari Queue.

2. pop() : untuk menghilangkan sebuah elemen di Front dari Queue.

3. front() : fungsi ini mirip dengan fungsi top() dari Stack, yaitu untuk menyatakan elemen di urutan tertentu sebagai Front.

Berikut adalah contoh penggunaan Queue Operation dalam suatu Queue (Front = L ; Rear = R).

Kita juga dapat melakukan Circular Queue. Apa itu Circular Queue?

Bayangkan kasus dimana kita terus melakukan pop push, index array akan terlampaui sehingga data baru akan disimpan di luar jangkauan array, yang merupakan cara yang tidak efektif.

Untuk mengatasi ini, kita dapat melakukan Circular Queue, dalam Circular Queue, apabila R sudah mencapai index array yang terakhir, kita akan mengubah R menjadi index 0, lakukan hal yang sama terhadap L.

Gambar di bawah merupakan representasi dari Circular Queue

Terima Kasih.

Linked List

Linked List

Linked list adalah data structure yang linear, dimana data-data tidak disimpan berdempetan diantara data-data yang lainnya, melainkan disambungkan oleh suatu pointer.

Berikut adalah gambaran dari linked list :

Kasarnya, linked list terdiri atas simpul-simpul yang di dalamnya terdapat bagian data dan refrensi(link) untuk ke simpul yang berikutnya, yang berdasarkan gambar di atas digambarkan sebagai kotak kosong.

Linked List memberikan kita kebebasan untuk melakukan insertion (pemasukan) dan deletion (penghapusan) elemen dimanapun dalam suatu data

Sebelumnya, kita sudah mempelajari array, yang juga merupakan kumpulan dari elemen-elemen data.

Loh, jadi kenapa kita belajar tentang linked list lagi? Kan sama-sama kumpulan data?

Array dan Linked List mungkin sekilas terlihat mirip. Tetapi apabila kita lihat lebih lanjut lagi, linked list memilikki 3 perbedaan yang signifikan dengan Array. Perbedaan - perbedaan tersebut yakni :

• Array merupakan kumpulan dari elemen-elemen data, dimana Linked List merupakan kumpulan dari elemen data yang dimasukan ke dalam satu simpul bersamaan dengan penyambung ke simpul yang lainnya
• Array menyusun data secara konsekuensial (berurutan). Contoh : {0; 1; 2; 3; 4; 5; NULL}. Sedangkan Linked List tidak menyimpan simpul-simpulnya secara berurutan.
• Dalam Array, kita dapat mengakses data secara acak. Sedangkan dalam Linked List. untuk mengakses data kita harus secara konsekuensial (berurutan).

Linked List sendiri terdiri atas dua jenis, yaitu :

1. Single Linked List, dan
2. Double Linked List.

Berikut adalah source code untuk Single Linked List sederhana ( 3 node) :

#include <bits/stdc++.h>

using namespace std;  

class Node

{

public:

    int data;

    Node* next;

};




{

    Node* head = NULL;

    Node* second = NULL;

    Node* third = NULL;

Node* fourth = NULL;

  

    // buat 3 node baru

    head = new Node();

    second = new Node();

    third = new Node();

fourth = new Node();




head->data = 1; // tentukan data di node pertama

    head->next = second; // sambungkan node pertama dengan node kedua

    second->data = 2; // tentukan data di node kedua

    second->next = third; // sambungkan node kedua dengan node ketiga

    third->data = 3; // tentukan data di node ketiga

    third->next = fourth;




fourth->data = 4;

fourth->next = NULL;

// narasumber : rathbhupendra via geeksforgeeks.org

Hasil Linked List dari code di atas dapat dilihat di gambar di bawah ini :

Akan tetapi Single Linked List (SLL) memilikki beberapa kekurangan daripada Double Linked List (DLL), contohnya adalah

• DLL dapat dilintasi maju maupun mundur 
• Operasi penghapusan di DLL lebih efisien apabila pointer ke node yang hendak dihapus diberikan
• Kita dapat langsung memasukkan node baru ke node yang kita inginkan. Maksudnya, dri SLL kita harus memutari kembali Linked List kita untuk memasukkan node yang baru, dimana DLL ini kita tidak perlu memutari ulang Linked List kita

DLL juga memilikki beberapa kekurangan, diantaranya :

• Setiap node DLL memerlukan tempat lebih untuk pointer ke node sebelumnya, akan tetapi kita masih dapat membuat node DLL dengan 1 pointer.
• Semua operasi memerlukan pointer ke node sebelumnya yang extra. Contohnya di proses Insertion (pemasukan), kita harus mengatur pointer ke node yang sebelumnya dan pointer ke node yang berikutnya secara bersamaan

Gambar berikut merupakan contoh DLL:

Selain SLL dan DLL standar, ada juga Circular Single Linked List dan Circular Double Linked List. Circular Linked List adalah Linked List yang node terakhirnya memilikki pointer ke node yang pertama. Oleh karena itu, tidak ada value NULL di Circular Linked List.

Berikut adalah gambar dari Linked List- Linked List tersebut :

Circular Single Linked List

Circular Double Linked List

Gambar di atas merupakan Double Linked List berdasarkan Binary Tree