Penerapan algorithma path-finding dalam game onet [Draft]

Agorithma Path Finding #9: Config [DRAFT]

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

Pada pembahasan sebelumnya kita membahas tentang refaktoring kode sumber kita untuk persiapan pembahasan selanjutnya yang akan banyak membahas tentang variasi dalam path finding. Kita akan membuat algorithma kita lebih fleksibel dengan konfigurasi yang bisa diubah-ubah sesuai kebutuhan.

Kode sumber bisa di download disini

Video Youtube:

(https://www.youtube.com/embed/NVe-ASdHAJ0 )

Anda juga bisa mencoba secara daring disini.

Bila Anda mencoba demo di atas, maka Anda akan melihat di pojok kanan atas ada menu kecil. Saat ini  pilihannya hanya ada dua: yaitu Fast dan A star. Untuk melihat perbedaan keduanya silahkan lihat pada videonya. Perilaku algorithma akan terlihat berubah pada kondisi-kondisi tertentu.

Apa yang berubah?

Perubahan pertama yang terlihat adalah adanya tambahan menu. Pembuatan menu sendiri sebenarnya bukan termasuk pembahasan dari algorithma path finding, namun diperlukan untuk membantu agar aplikasinya bisa berjalan.

Perubahan kedua adalah penambahan konfigurasi pada algorithma yang kita pakai. Dengan adanya konfigurasi ini kita tidak perlu membuat algorithma terpisah untuk masing-masing perilaku. 

Perubahan pada file PathFinder.js

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

    };

    if (PF_CEPAT == pfConfig.mode) {

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

    }

    else if (PF_A_STAR == pfConfig.mode) {

        cell.jarak += (cell.g * 1.1);

    }

    return cell;

}

Fungsi cellBuat memiliki sedikit perubahan untuk menghitung jarak.

Pada fungsi sebelumnya jarak kita hitung dengan menghitung jarak horizontal dan vertikal. Sekarang jarak ditentukan tergantung dari modenya. Bila mode-nya adalah PF_CEPAT maka penghitungannya sama dengan sebelumnya, bila tidak maka penghitungannya ditambah dengan menambahkan faktor g.

HAGL - Library WebGL Sederhana

Awalnya Saya hanya ingin mencari library WebGL yang fokus ke rendering, dan sudah nemu juga, namanya PIXI.js. PIXI.js sangat bagus sekali, sangat recomended. Tapi PIXI punya masalah yang Saya kurang sreg, yaitu ukurannya yang terlalu besar, yaitu hampir 1/2 MB. Terlau besar, menurut Saya untuk sebuah library. Padahal target saya, ukurannya gak lebih besar dari 100 kb. 

Setelah mempertimbangkan masak-masak, akhirnya Saya memutuskan untuk membuat library WebGL sendiri. Library ini Saya beri nama HAGL.

HAGL adalah sebuah library sederhana untuk menggambar menggunakan WebGL di browser.

HAGL bukan game enggine, tapi bisa digunakan untuk merender game, khususnya game 2D.

HAGL bisa untuk menggambar image, tileset, ataupun spritesheet.

HAGL bukan 3d enggine. HAGL hanya memfokuskan pada fungsi utama dari WebGL sebagai rasterising engine. Cocok untuk game 2D di browser yang butuh performa tambahan untuk menggambar.

Cara penggunaannya sangat sederhana:

var gl = new Hagl(canvas);
gl.drawImage(image, x, y);

Atau bisa juga pakai pilihan

var gl = new Hagl(canvas);
gl.drawImage(image, x, y, {pilihan})

pilihan yang tersedia antara lain:
skala, rotasi, alpha, offset, dan textureUV.

Contoh penggunaan tersedia dalam demo yang bisa dicoba disini:
https://hagarden.blogspot.com/p/blog-page.html

Saat ini fitur dan demonya masih sedikit. Saya akan menambahkan sedikit demi sedikit pada update-update selanjutnya.

Algorithma Path Finding #8: Refaktor

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

Pada pembahasan sebelumnya kita membahas tentang A * (Star). A Star path finding menghasilkan jalur yang lebih optimal dari sebelumnya.

Pada pembahasan kali ini, Saya tidak membahas hal yang baru. Saya hanya melakukan bersih-bersih rumah. Pembahasan kita sampai saat ini sudah semakin kompleks dan sudah mencapai titik dimana kita perlu mengadakan perapihan sebelum membahas pembahasan yang lebih mendalam lagi.

Kode sumber yang sudah dirapikan bisa di unduh disini.

Apa saja yang berubah?

Perubahan pada file index.html

Saya merapikan css nya, dan menambahkan style baru pada elemen kanvas. Saya suka dengan style piksel dan senang bekerja pada resolusi rendah. Selama ini tampilannya cenderung nge-blur karena hal ini. Untuk itulah Saya menambahkan style pada canvas agar lebih ber-piksel

canvas {
position: absolute;
image-rendering: -moz-crisp-edges;
image-rendering: -webkit-crisp-edges;
image-rendering: pixelated;
image-rendering: crisp-edges;
}

Kemudian saya menyederhanakan struktur html dengan menghapus semua atribut pada elemen kanvas.

<canvas></canvas>

Semua atribut pada kanvas akan diatur dari pemrograman.

Penambahan file Data.js

Saya menambahkan file Data.js yang akan menampung semua variabel. Awalnya variabel dismpan jadi satu dengan file Game.js. Kita sekarang memisahkan antara data dengan logika dan alur dari program.

Pada file ini, Saya juga menambahkan variabel baru yaitu gp dan gl. Masing-masing berisi informasi mengenai resolusi game. Sekarang kita akan mengontrol resolusi dari sini.

Dan beberapa perubahan kecil lainnya yang tidak bisa dibahas satu persatu.

Sekarang struktur kita sudah siap, dan kita siap untuk membahas algorithma ini ke arah yang lebih kompleks lagi. 

Terima kasih sudah mampir dan membaca.

.

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

Membuat kanvas bersifat responsif #2: Layar Penuh

Pada pembahasan kali ini kita akan membahas bagaimana membuat kanvas yang bersifat responsif dengan cara men-skala kanvas agar bisa memenuhi layar, dengan tetap menjaga rasio agar tampilan tidak melar. 

Sebelumnya kita sudah membahas tentang macam-macam skala dan bagaimana men-skala kanvas dengan menjaga agar tidak ada bagian yang terpotong.

Kode sumber bisa diunduh di tautan ini:

Demo bisa dilihat di tautan ini. Silahkan ubah-ubah ukuran browser untuk melihat hasilnya.

Contoh hasilnya adalah seperti gambar di bawah ini:


Tampilan landskape


Tampilan portrait

Dari kedua tampilan di atas terlihat bagaimana kanvas akan selalu terlihat memenuhi layar.

Penjelasan Kode:
Bisa dibilan 99% kode pada pembahasan sekarang sama persih dengan kode pada pembahasan sebelumnya. Yang membedakan hanyalah satu baris saja. Perhatikan fungsi resize berikut:

function resize() {
    let cp = 360;
    let cl = 218;
    let wp = window.innerWidth;
    let wl = window.innerHeight;
    let ratio = Math.max((wp / cp), (wl / cl));
    let cp2 = Math.floor(cp * ratio);
    let cl2 = Math.floor(cl * ratio);
    canvas.style.width = cp2 + 'px';
    canvas.style.height = cl2 + 'px';
    canvas.style.top = ((wl - cl2) / 2) + 'px';
    canvas.style.left = ((wp - cp2) / 2) + 'px';
    gambarCanvas(canvasCtx);
}

Perbedaannya adalah dalam mencari ratio.

    let ratio = Math.max((wp / cp), (wl / cl));

Bila sebelumnya kita menggunakan Math.min(), maka sekarang kita pakai Math.max().

Dengan menggunakan Math.max(), kita mendapatkan ratio yang paling besar. 

Bila panjang horisontal kanvas hasil skala sama dengan tinggi layar, maka bagian vertikal kanvas akan terpotong. Bila tingginya yang sama, maka bagian panjangnya yang akan terpotong.

Penjelasan lengkapnya untuk bagian yang lain bisa dibaca pada tulisan sebelumnya.

Terima kasih telah mampir dan membaca. Pada tulisan berikutnya Saya akan membicarakan metode responsif yang lain, Insya Allah.

Algorithma Path Finding #6: Jalan yang lebih halus

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

Pada tulisan sebelumnya, kita telah membahas bagaimana membuat karakter yang berjalan mengikuti jalur path-finding. Karakter berjalan dengan cara 'melompat-lompat' dari satu grid ke grid berikutnya.

Pada pembahasan kali ini, kita akan melakukan penyempurnaan cara berjalan. Karakter tidak lagi berjalan secara melompat-lompat, tapi berjalan perlahan-lahan dari satu grid ke grid berikutnya.

Kode sumber nya bisa diunduh di tautan ini:
https://drive.google.com/file/d/1-uGzY1QBcaCyZbUr4SgJSHZyXSQZMMw_/view?usp=sharing

Demo daring bisa dilihat di tautan ini:
https://hagarden.netlify.app/moon/400_jalan/

Video Youtube juga tersedia sbb:



Perubahan kode dari pembahasan sebelumnya.

Perubahan pertama adalah pada struktur data karakter.

let karakter = {
    jalur: [],
    jalurn: 0,
    pindahJml: 4,
    pindahn: 0,
    pos: {
        x: 32,
        y: 32
    },
    status: st_idle
};

Kita tambahkan dua property baru, yaitu pindahJml dan pindahn.
pindahJml berisi informasi jumlah langkah yang dibutuhkan untuk berpindah dari satu grid ke grid berikutnya. pindahn berisi informasi langkah yang ke-berapa.

Posisi karakter sekarang dirubah dari posisi di grid menjadi posisi di layar. Pada tulisan sebelumnya, posisi karakter berada pada posisi 1,1. Posisi ini merujuk pada posisi grid. Sekarang posisi karakter adalah 32, 32 yang merujuk pada posisi di layar. Satu grid adalah 32 x 32 pixel.

Perubahan berikutnya adalah penambahan fungsi-fungsi baru, antara lain:

function krkPosisiGrid(karakter) {
    return {
        x: Math.floor(karakter.pos.x / 32),
        y: Math.floor(karakter.pos.y / 32)
    };
}

Fungsi ini akan menghasilkan informasi posisi grid dimana karakter sekarang berdiri.

Fungsi baru berikutnya adalah fungsi krkCheckPosisiDiGrid().

function krkCheckPosisiDiGrid(karakter) {
    if (karakter.pos.x % 32)
        return false;
    if (karakter.pos.y % 32)
        return false;
    return true;
}

Fungsi ini mengecek apakah karakter sekarang sedang berada di grid atau berada diantara grid. Saat karakter berpindah dari grid satu ke grid berikutnya, maka posisi karakter sedang berada di antara grid sampai karakter tersebut sampai di grid berikutnya.

Fungsi berikutnya adalah fungsi krkPindahGrid()

function krkPindahGrid(karakter) {

    let posAwalX;

    let posAwalY;

    let posSelanjutnyaX;

    let posSelanjutnyaY;

    let jarakX;

    let jarakY;

    let posBaruX;

    let posBaruY;

    karakter.pindahn++;

    //posisi grid sekarang

    posAwalX = karakter.jalur[karakter.jalurn][0] * 32;

    posAwalY = karakter.jalur[karakter.jalurn][1] * 32;

    //posisi grid target

    posSelanjutnyaX = karakter.jalur[karakter.jalurn + 1][0] * 32;

    posSelanjutnyaY = karakter.jalur[karakter.jalurn + 1][1] * 32;

    //jarak dari grid sekarang ke target

    jarakX = posSelanjutnyaX - posAwalX;

    jarakY = posSelanjutnyaY - posAwalY;

    //posisi karakter baru

    posBaruX = posAwalX + (karakter.pindahn / karakter.pindahJml) * jarakX;

    posBaruY = posAwalY + (karakter.pindahn / karakter.pindahJml) * jarakY;

    karakter.pos.x = posBaruX;

    karakter.pos.y = posBaruY;

}

Fungsi ini adalah fungsi yang menangani perpindahan karakter dari grid satu ke grid berikutnya. Proses penghitungannya adalah sebagai berikut.

Pertama kita tambah nilai dari pindahn. Variable ini berisi informasi kita sedang di langkah ke berapa

    karakter.pindahn++;

Selanjutnya kita dapatkan posisi grid awal sebelum karakter berpindah.

    //posisi grid sekarang

    posAwalX = karakter.jalur[karakter.jalurn][0] * 32;

    posAwalY = karakter.jalur[karakter.jalurn][1] * 32;

Nilainya kita kali 32 untuk merubah dari posisi grid ke posisi di layar.

Setelah itu kita dapatkan posisi grid berikutnya, yang merupakan grid tujuan.

    //posisi grid target

    posSelanjutnyaX = karakter.jalur[karakter.jalurn + 1][0] * 32;

    posSelanjutnyaY = karakter.jalur[karakter.jalurn + 1][1] * 32;

Kemudian kita hitung jarak perpindahan dari grid sekarang ke grid berikutnya.

    //jarak dari grid sekarang ke target

    jarakX = posSelanjutnyaX - posAwalX;

    jarakY = posSelanjutnyaY - posAwalY;

Posisi karakter yang baru dihitung dari posisi awal + posisi perpindahan

//posisi karakter baru

    posBaruX = posAwalX + (karakter.pindahn / karakter.pindahJml) * jarakX;

    posBaruY = posAwalY + (karakter.pindahn / karakter.pindahJml) * jarakY;

Hasil dari posisi baru ini disimpan di karakter.

    karakter.pos.x = posBaruX;

    karakter.pos.y = posBaruY;

Berikutnya Kita akan membahas perubahan pada fungsi berikutnya, yaitu fungsi update():

function update() {

    if (karakter.status == st_idle) {

    }

    else if (karakter.status == st_jalan) {

        if (krkCheckPosisiDiGrid(karakter)) {

            karakter.jalurn++;

            if (karakter.jalurn >= karakter.jalur.length - 1) {

                karakter.status = st_idle;

            }

            else {

                karakter.status = st_jalan;

                karakter.pindahn = 0;

                krkPindahGrid(karakter);

            }

        }

        else {

            krkPindahGrid(karakter);

        }

    }

}

Kita merubah cara karakter berjalan. Tiap kali posisi karakter berada tepat di grid, maka kita tambahkan nilai dari jalurn.

if (krkCheckPosisiDiGrid(karakter)) {

  karakter.jalurn++;

Kemudian kita check apakah jalurn sudah mencapai maksimal, artinya karakter sudah sampai pada index terakhir. Bila ya, maka kita ubah status karakter menjadi idle.

if (karakter.jalurn >= karakter.jalur.length - 1) {

  karakter.status = st_idle;

}

Bila tidak, maka kita ubah statusnya jadi jalan lagi.

karakter.status = st_jalan;

karakter.pindahn = 0;

krkPindahGrid(karakter);

Untuk selanjutnya, maka kode sumbernya sama dengan sebelumnya,

Terima kasih telah mampir dan membaca.