graf, representasi dunia, pengantar pathfinding

TIP 163

Game Engine

Topik 5 (Pert 6)

Graf, Representasi Dunia, dan Algoritma Pencari Jalur (Pathfinding) Dosen: Aditya Wikan Mahastama

Last Week Review

Adakah permasalahan dalam tugas terakhir yang diberikan minggu lalu?

Silakan submit tugas terakhir minggu lalu ke [email protected] dengan subjek:

GAMENG P6 Seperti biasa, isi e-mail adalah anggota kelompok dengan attachment berisi file game

Memodelkan Jalur Gerak Objek

Objek dapat dibiarkan bergerak bebas mengikuti steering behaviour yang diberikan. Misal jika sifat steering yang diberikan adalah seek, secara natural objek akan sampai pada goal yang dituju.

Permasalahan: Penerapan steering behaviour murni berhubungan dengan objek game lainnya, sehingga akan sulit “meminta” objek untuk mengikuti suatu jalur tertentu, atau membuatnya “mampir” melewati rute khusus sebelum sampai pada tujuannya


Jika kita menginginkan objek game untuk menempuh jalur tertentu, kita dapat mendefinisikan “tujuan sementara” atau sering disebut “waypoint” yang berfungsi sebagai advancing goal sebelum menuju ke goal yang sesungguhnya.

Waypoint ini dapat kita modelkan sebagai titik-titik dalam sebuah graf (atau biasa disebut node), dengan satu node awal (start) dan satu node tujuan utama (goal) untuk suatu saat tertentu.


Graf dapat berupa graf tak berarah, atau untuk beberapa algoritma (directed graph) yaitu setiap konektor atau (garis) memiliki arah. Satu edge hanya memiliki satu arah.


dapat berupa graf tak berarah, atau untuk beberapa algoritma harus berupa graf berarah

) yaitu setiap konektor atau (garis) memiliki arah. Satu edge hanya memiliki satu


dapat berupa graf tak berarah, atau untuk harus berupa graf berarah

) yaitu setiap konektor atau edge (garis) memiliki arah. Satu edge hanya memiliki satu

Pemodelan harus menyesuaikan representasi dunia yang dipilih untuk game kita. Sebelumnya, silakan lihat jenis-jenis representasi dunia yang ada pada game.

Peletakan Node

Peletakan node dapat dilakukan dengan dua cara: 1. Pada setiap tile

Untuk cara ini, node dapat diletakkan pada bagian tile yang membawa identitas tile tersebut, misal titik pusat untuk tile segi empat.

2. Pada tile/titik tertentu Untuk cara ini, node diletakkan hanya pada tile tertentu (untuk representasi dengan tile) atau koordinat tertentu untuk sistem koordinat bebas. Sifatnya hanya membantu mengarahkan path atau jalur.

Kekurangan dan Kelebihan Peletakan Node

1. Pada setiap tile Komputasi akan lebih lambat, karena graf menjadi lebih rumit, tetapi perubahan langkah dapat diambil pada level paling immediate (langsung), misalnya keputusan untuk berbelok cabang karena perubahan letak goal node. Oleh karena itu peletakan node semacam ini lebih cocok untuk board game atau game dengan ukuran dunia yang kecil.

2. Pada tile/titik tertentu Komputasi lebih ringan, steering behaviour lebih leluasa untuk dikombinasikan, tetapi perubahan langkah baru “disadari” ketika objek sudah sampai ke sebuah node, karena update dilakukan setelah satu jalur selesai ditempuh. Meski demikian jika engine tidak terlalu kaku, pergerakan dan komposisi objek menjadi fleksibel karena update steering dapat dilakukan sebelum sebuah node dicapai, dan objek tidak benar-benar terikat dengan sebuah node. Peletakan node seperti ini cocok untuk game dengan dunia yang luas.

Pencarian Jalur

Setelah seluruh waypoint atau node dalam graf dimodelkan, diperlukan sebuah cara agar objek dapat memilih jalur yang tepat menuju sebuah node yang telah ditetapkan sebagai goal.

Pemilihan jalur ini dapat dibantu dengan algoritma pathfinding (penemuan jalur) atau pencari jalur terpendek (shortest path) yang telah dikenal selama ini, misalnya:

- Algoritma Dijkstra - Algoritma Floyd - A* - beserta segala macam pengembangannya

Algoritma Dijkstra

Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial

node to Y. Dijkstra's algorithm will assign some initial distance values and will try to improve them step by step.

1. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.

2. Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes.

3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a distance of 6, and the edge

connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6 + 2 = 8. If this distance is less than the previously recorded tentative distance of B, then overwrite that distance. Even though a neighbor has been examined, it is not marked as "visited" at this time, and it remains in the unvisited set.

4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.

5. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited

set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and

remaining unvisited nodes), then stop. The algorithm has finished.

6. Select the unvisited node that is marked with the smallest tentative distance, and set it as the new "current node" then go back to step 3.

See the on-screen example.

Algoritma Floyd-Warshall

Menghitung jarak terpendek setiap pasangan titik dalam graf melalui thorough search replacement yaitu menggantikan nilai awal dengan nilai baru yang lebih kecil serta menyimpan rutenya. Jika menemukan pasangan yang belum tersimpan nilai awalnya, maka pasangan tersebut beserta nilainya disimpan. let dist be a |V| × |V| array of minimum distances initialized

to ∞ (infinity)

let next be a |V| × |V| array of vertex indices initialized to

null

procedure FloydWarshallWithPathReconstruction ()

for each vertex v

dist[v][v] ← 0

for each edge (u,v)

dist[u][v] ← w(u,v) // the weight of the edge (u,v)

for k from 1 to |V|

for i from 1 to |V|

for j from 1 to |V|

if dist[i][k] + dist[k][j] < dist[i][j] then

dist[i][j] ← dist[i][k] + dist[k][j]

next[i][j] ← k

function Path (i, j)

if dist[i][j] = ∞ then

return "no path"

var intermediate ← next[i][j]

if intermediate = null then

return " " // the direct edge from i to j gives the

shortest path

else

return Path(i, intermediate) + intermediate +

Path(intermediate, j)

Algoritma A*

A* dan pengembangannya � minggu depan.

Reminder for Next Week

Telah tiba saatnya minggu depan, kelompok anda mempresentasikan ide game yang akan dibuat sebagai tugas akhir mata kuliah ini. Untuk itu persiapkanlah baik-baik hal-hal berikut:

1. Gambaran kasar (boleh dengan image editor) mengenai dunia game yang akan dibuat.

2. Presentasi mengenai gameplay dan fitur-fitur game yang akan dibuat, maksimal 5 slide saja.

Apa yang anda presentasikan akan menjadi dasar pembuatan game kelompok anda. Be persistent!

graf, representasi dunia, pengantar pathfinding

Documents