Algorithma Path Finding #7: A Star

In adalah pembahasan ke 7 dari seri Algorithma Path Finding. Pembahasan pertama bisa Anda baca pada tautan ini.

Pada pembahasan sebelumnya kita membahas tentang bagaimana membuat karakter berjalan lebih halus dalam penerapan algorithma path-finding. 

Pada tulisan kali ini kita akan membahas tentang A * (A Star) Path finding. A * Pathfinding adalah penyempurnaan dari algorithma path finding sebelumnya yang biasa dikenal dengan istilah fast-path-finding. 

A * Path finding akan menghasilkan jalur yang lebih optimal.

Perhatikan perbedaan keduanya dalam kedua gambar berikut.

Jalur yang dibuat dari algorithma sebelumnya hasilnya tidak optimal. Karakter menempuh jalur yang lebih panjang. 

Jalur yang dihasilkan dari algorithma A* jauh lebih optimal. Jalurnya lebih pendek.

Demonya bisa dicoba online di tautan ini:

Kode sumber bisa di unduh di tautan ini:

Video Youtube:

Apa yang berubah?

Dalam pembahasan kali ini kita mengenalkan konsep G. G adalah 'jarak' dari posisi awal ke posisi sekarang. G dihitung dengan cara berbeda dengan jarak sebelumnya (H) yang dihitung dari posisi sekarang ke posisi tujuan.

G tidak dihutung secara kira-kira/heuristic seperti H. G adalah jarak sebenarnya. Kita mendapatkan G dengan cara menambahkan nilai G dari cell parent. Cell parent mendapatkan nilai G dari parent sebelumnya, hingga ke cell yang pertama.  Dengan cara ini, maka nilai G tidak dikira-kira.

Sebenarnya istilah 'jarak' kurang cocok untuk G, namun untuk menyamakan dengan H, maka saya pakai istilah jarak. G sebenarnya lebih cocok disebut biaya perjalanan dari titik awal ke titik sekarang.

Pada pembahasan sebelumnya kita menghitung jarak dengan cara mengira-ira dari posisi sekarang keposisi target. 

Jarak(F) = H          ...1)

Dengan adanya G maka perhitungannya jadi:.

Jarak(F) = G + H      ...2)

G biasanya tidak berdiri sendiri tapi diberi pemberat.

Jarak (F) = G * P + H ...3)

P adalah pemberat. Bila nilainya satu maka G * P = G, (persamaan 2).

P bernilai lebih dari atau sama dengan satu. Semakin besar P, maka G akan semakin berat, dan hal ini akan mempengaruhi penghitungan jarak. Semakin besar pengaruh G, maka jarak yang dihasilkan akan semakin optimal, namun waktu yang dibutuhkan untuk menyelesaikan algorithma juga semakin lama. 

Perubahan kode sumber

Kita melakukan perubahan pada kode sumber untuk mengenalkan G.

Perubahan pertama ada pada fungsi cellBuat().

function cellBuat(parent, x, y, tx, ty) {
    ...
    let cell = {
        x: x,
        y: y,
        buka: 1,
        jarak: -1,
        induk: parent,
        g: parent ? parent.g + 1 : 0
    };

    cell.jarak = Math.abs(tx - x) + Math.abs(ty - y);
    cell.jarak += (cell.g * 1.1);

    return cell;
}

Kita menambahkan property g. Nilainya dihitung dari parent sebelumnya ditambah satu. Bila parentnya tidak ada, karena ini adalah cell yang pertama, maka g diisi dengan nol.

Selanjutnya pada penghitungan jarak kita tambahkan jarak yang dihasilkan dengan perhitungan sebelumnya dengan g. Kita juga memberi pemerat pemberatnya 1.1 pada g. Anda bisa mengisi pemberat dengan angka berapa saja asal lebih dari satu. Namun harus diperhatikan bahwa semakin besar pengaruh g, maka semakin lama waktu yang dibutuhkan untuk menyelesaikan algorithma.


Terima kasih sudah mampir dan membaca