Tutorial Pencarian Rute ( Pathfinding ) dengan Algoritma A* di Unity Menggunakan Library Arongranberg

Mungkin sobat sudah bisa menduga, kenapa saya pajang gambar game lawas, pacman, sebagai pembukaan artikel ini. Yaa.. Karena memang tujuan kita di artikel ini adalah membuat simple AI yang memiliki sifat mirip dengan karakter musuh dalam game pacman, yaitu dapat mencari jalan untuk mencari objek tertentu kemanapun obyek tersebut bersembunyi.

Artikel ini sebenarnya adalah artikel lanjutan dari artikel pembuatan simple AI untuk mengikuti obyek tertentu yang pernah saya tulis sebelumnya disini. Namun jika sobat lihat pada artikel sebelumnya yang ada hanyalah karakter mengikuti player hanya dalam ruangan kosong tanpa ada halangan sama sekali. Coba lihat gambar di bawah

Kemudian pertanyaanya, bagaimana jika arena berupa labirin atau memiliki penghalang seperti pada gambar di bawah? Pasti algoritma sederhana seperti algoritma sebelumnya tidak dapat menyelesaikan ini dan dijamin akan terjadi berbagai tubrukan.

Jika arena berbentuk labirin atau memiliki penghalang maka tentu diperlukan suatu algoritma tertentu agar AI yang mengejar tidak membentur tembok. Selain itu, karakter AI seharusnya juga dapat memutuskan rute mana yang harus ditempuh agar pergerakan semakin realistis dan optimal.

Terdapat berbagai algoritma pencarian jalur ayng dapat dipakai, sebut saja djikstra, A*, dsb. Namun pada artikel kali ini kami akan membahas algoritma A*, kenapa A* yang saya pilih karena di Unity telah tersedia extension arongranberg untuk memudahkan kita dalam menemukan jalur terpendek menggunakan algoritma A*. Adapun jika Sobat ingin tahu apa itu algoritma A* dan bagaimana cara kerjanya silahkan baca artikel saya sebelumnya tentang algoritma A* untuk pencarian jalur terpendek.

Namun pada tutorial kali ini kita tidak terlalu membahas bagaimana cara kerja algoritma A* karena kita akan memakai library arongranberg. Dengan library ini kita cukup menentukan dimana saja posisi node dan arongranberg akan mencari sendiri rute terdekat menggunakan algoritma A*. Ok.. Langsung saja kita coba, mari siapkan alat dan bahannya sbb :

1. Game engine Unity yang sudah terinstall di PC. Adapun Unity dapat di download disini. Jika sobat ingin belajar lebih jauh tentang unity silahkan mengunjungi halaman kumpulan link tutorial disini.
2. Extension Arongranberg sebagai extension unity untuk mencari jalur terpendek. Versi terbaru arongranberg dapat di download di situs resminya disini. Namun untuk menghindari perbedaan cara, jika Sobat ingin mendownload versi yang sama dengan tutorial ini (versi 3.2.5.1) maka dapat di download disini.
3. Project membuat simple AI yang pernah saya buat di tutorial sebelumnya disini. Adapun projectnya dapat di download disini.

Oke jika alat dan bahan sudah siap mari langsung saja ita mulai percobaannya. Berikut adalah step by step pembuatan aplikasi ini :

1. Buka project dan import arongranberg

Pertma buka project yang telah Sobat download pada alat & bahan di step 3. Buka scene Main Scene pada folder _Scenes. Setelah dibuka maka tampilannya seperti pada gambar di bawah.

Selanjutnya import library arongranberg dengan membukanya dan lakukan double klik

Import semua elemen maka di window project akan ditambahkan

2. Buat graph

Setelah project dan lib bisa di import makan langkah selanjutnya dalah membuat graph. Ada beberapa jenis graph yang dapat dibuat di arongranberg, namun kali ini saya akan membahas yang paling mudah yaitu grid graph. Caranya buat empty game object dengan nama A*. Kemudian drag & drop script AStarPath ke dalam object A*.

Kemudian buat GridGraph pada object A*

Selanjutnya lakukan konfigurasi seperti di bawah

Nilai-nilai dalam tutorial ini bisa saja berbeda sesuai dengan luas arena. Silahkan mainkan sendiri ya nilai nilai width, depth, node size, dsb. Lihat-lihat sendiri apa efeknya, yang jelas berkaitan dengan ukuran arena, banyaknya node dalam graph, dan letak center dari graph. Tempatkan tepat di atas arena.Jika sudah diatur klik tekan seperti pada gambar di bawah 

Jika sudah di scan maka seharusnya hasilnya adalah seperti pada gambar di bawah

Kotak-kotak merah pada gambar diatas menunjukkan daerah yang tidak dapat dilewati atau illegal. Jika sobat tidak menemukan kotak-kotak merah atau dengan kata lain penghalang tidak dapat dideteksi maka coba mainkan variabel Erode Iteration dengan memperbesar nilainya. Semakin besar nilai Erode Iteration maka akan memperbesar daerah terlarang. Jika semakin kecil maka penghalang tidak dapat dideteksi.

Jika kita tengok lebih dekat maka player dan enemy juga akan dideteksi sebagai penghalang. Lihat gambar di bawah 

Yang perlu kita lakukan adalah membatasi hanya tembok, bangunan dan arena yang dideteksi oleh arongranberg, adapun lainnya tidak. Yang perlu kita lakukan adalah memisahkan tembok dan arena pada layer yang berbeda, misal kita taruh dalam layer "Arena Collider". Lihat gambar di bawah 

Kemudian pada bagian Mask pada Collssion testing hanya kita centang bagian Arena Collider

Maka hasilnya player dan enemy tidak lagi dianggap sebagai penghalang. Lihat gambar di bawah

3. Buat karakter AI

Untuk membuat obyek yang menerapkan pathfinding kita daur ulang obyek pada proyek sebelumnya dengan cara remove script AICharacter pada object AI Character. Sekedar info bagi yang belum membaca artikel sebelumnya tentang simple AI. Object AI Character adalah object karakter yang akan mengejar target (player). Di dalam AI Character terdapat script AICharacter untuk mengikuti object. Disini kita tidak membutuhkan script ini sehingga kita perlu me-remove-nya.

Untuk mencari jalur script yang diperlukan adalah Seeker. Kita drag & drop script seeker ke dalam AI Character

Kita biarkan script seeker (WARNING : Jangan pernah mengedit script Seeker kecuali benar-benar mengerti dan dibutuhkan). Kemudian kita buat script baru dengan nama AIPathFindingCharacterBehaviour. Adapun isi dari AIPathFindingCharacterBehaviour adalah sbb :

using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using Pathfinding;

public class AIPathfindingCharacterBehaviour : MonoBehaviour {
    public GameObject target;
    public float movingSpeed = 2f; //kecepatan berpindah
    public float turnSpeed = 0.05f; //kecapatan berbelok

    private Seeker seeker;

 void Start () {
        seeker = this.GetComponent();

        seeker.pathCallback += OnPathComplete; //Jika pencarian complete maka memanggil method OnPathComplete. Fungsi pencarian cari seeker.StartPath

        StartCoroutine(RepeatSearchTarget(0.5f)); //Mencari target setiap 0.5 detik. Semakin cepat repeat rate beban CPU semakin berat, jika terlalu lambat ketika target berpindah tempat jalur tidak berubah
 }

    private Vector3 processedVectorPath; //Node dari path yang sedang di proses >> berelasi dengan vectorPath
 void Update () {
        if (Vector3.Distance(this.transform.position, processedVectorPath) < 1) { //Jika mencapai processedVectorPath, maka node yang di proses (processedVectorPath) adalah node berikutnya (vectorPath[0])
            if (vectorPath.Count > 0) {
                processedVectorPath = vectorPath[0];
                vectorPath.RemoveAt(0); //me remove vectorpath[0]
            }
        }

        Vector3 gapPosition = processedVectorPath - this.transform.position; //Gap antara posisi AI dengan target
        gapPosition = new Vector3(gapPosition.x, 0, gapPosition.z); //Nilai gap y dibuat 0 agar AI mengabaikan posisi atas dan bawah (Y) dari target dan hanya mengikuti arah ke kanan dan ke kiri (X dan Y)
        Quaternion lookRotation = Quaternion.LookRotation(gapPosition); //Rotasi untuk look atau melihat target
        this.transform.rotation = Quaternion.Lerp(this.transform.rotation, lookRotation, turnSpeed); //Membuat rotasi berubah secara smooth menggunakan fungsi lerp dari rotasi awal ke rotasi tujuan lookRotasion

        this.transform.Translate(Vector3.forward * movingSpeed * Time.deltaTime); //Bergerak maju
 }

    private List vectorPath = new List(); //berisi kumpulan node dalam path >> node yang sedang di proses dimasukkan processedVectorPath
    private IEnumerator RepeatSearchTarget(float repeatRate) { 
        while (true) {
            seeker.StartPath(this.transform.position, target.transform.position); //Mulai mencari path path >> lihat OnPathComplete

            yield return new WaitForSeconds(repeatRate);
        }
    }

    private void OnPathComplete(Path path) { //Pencarian selesai
        vectorPath = path.vectorPath; //hasil pencarian berupa kumpulan node dari path, ditampung dalam vectorPath
        processedVectorPath = vectorPath[0]; //ode yang sedang di proses dimasukkan processedVectorPath 
        vectorPath.RemoveAt(0); //menghapus node pada vectorPath[0] karena telah di tampung di processedVectorPath untuk diproses
    }
}

Kemudian kita masukkan script AIPathFindingCharacterBehaviourke dalam object AI Character dengan cara drag & drop.

Selanjutnya kita masukkan Player kedalam variabel target dengan cara drag & drop.

3. Uji Coba
Selanjutnya tinggal uji coba deh semuanya. Klik tombol play dan jalankan program. Adapun hasilnya kurang lebih adalah seperti pada gambar di bawah. Enemy akan mengejar player tanpa menabrak tembok.

Sobat dapat menekan tombol-tombol arrow pada keyboard untuk menggerakkan player.


Mungkin cukup sekian tutorial yang dapat saya sampaikan, project dapat Sobat download pada link di akhir artikel ini. Jangan lupa untuk membaca artikel saya lainnya yaaa... Dan saya harap pengunjung bisa tinggalkan komen, itung-itung biar rame. Hehehe... Kurang lebihnya saya mohon maaf, terima kasih telah membaca artikel ini tetap semangat dan terus berkarya... ^^

PROJECT : 
http://www.4shared.com/zip/wwYLG27U/Pathfinding_arongranberg.html

Baca juga :
Belajar Algoritma A* Untuk Pencarian Jalur / Rute Terdekat
Extension Unity Sering Digunakan (Menurut Saya)