pengantar teori gamefarhana.salim.staff.gunadarma.ac.id/downloads/files/62061...1--1=30 f — 40...

PATH FINDING

PENGERTIAN

PATH FINDING

cara mendapatkan route

untuk 2 point

Brute Force

BFS DFS

Branch and Bound

dan A*

?

PENGERTIAN

REPRESENTASI

GRAPH

REPRESENTASI GRAPH

menyatakan suatu relasi

sekumpulan node

dihubungkan dengan edge

Adjacency List Adjacency Matriks List of Edge

ALGORITMA

DIJKSTRA

PENGERTIAN

REPRESENTASI

GRAPH

ALGORITMA DIJKSTRA

EDSGER DIJKSTRA

memecahkan permasalahan jarak terpendek (shortest path)

dari harga yang terkecil

ALGORITMA

A*

ALGORITMA

DIJKSTRA

PENGERTIAN

REPRESENTASI

GRAPH

ALGORITMA A*

mencari langkah terpendek

x diberikan nilai

menentukan jalur terpendek ke sasaran

dengan pendekatan heuristic h(x)

1 2

G=10 (horizontal & vertikal)

G=14 (diagonal)

3

Nilai jarak = H

4

F = Scoring

F=G+H

5

pergerakan

berdasarkan F

6

looping

titik yang dituju

ALGORITMA

A*

ALGORITMA

DIJKSTRA

PENGERTIAN

REPRESENTASI

GRAPH

HIRARKI

PATH FINDING

membagi peta menjadi beberapa cluster

HIRARKI PATH FINDING

pencarian jalan urutan/tingkatan

pencarian jalan

berdasarkan tingkatan

menentukan jalan masuk tiap cluster

mencari jalur optimal per cluster

mencari jalur optimal antar cluster

menyederhanakan

kompleksitas

mempercepat

pencarian

ALGORITMA

A*

ALGORITMA

DIJKSTRA

PENGERTIAN

REPRESENTASI

GRAPH

HIRARKI

PATH FINDING