Sabtu, 04 Juli 2020

Algorithma Path Finding #2: Penerapan kode algorithma path finding

Pada tulisan sebelumnya, kita telah membahas tentang algorithma path-finding dalam bentuk pengenalan konsep dasar tanpa ada code pemrograman sama sekali. Disini kita akan membahas algorithma tersebut dari sisi pemrograman.

Bahasa pemrograman yang dipakai adalah javascript, dan applikasinya bisa dijalankan di browser.

Source Code bisa didownload disini:. Cukup jalankan saja file index.html di browser. Bila berhasil, maka hasil akhirnya akan tampak seperti gambar di bawah ini.


Gambar diatas menunjukkan jalur pencarian yang dihasilkan dari algorithma path-finding. Pencarian bergerak dari kiri ke kanan. Jalur yang dihasilkan bukanlah jalur yang optimal, karena algorithma yang kita pakai disini adalah algorithma fast-path-finding. Pencarian jalur yang menghasilkan jalur yang optimal bisa didapat dengan menggunakan algorithma path-finding yang lain seperti A*. Kita akan membahasnya di tulisan mendatang.  

Anda juga bisa mencoba secara langsung melalui editor di bawah ini.   
 


Penjelasan kodenya adalah sebagai berikut:

A.  HTML 


<html>

<head>
  <link rel="stylesheet" href="css/css.css">
  <script src="js/js.js"></script>
</head>

<body>
  <div style='display:none'>
    <img src='imgs/bola.png' id='img-bola'>
    <img src='imgs/box.png' id='img-box'>
  </div>
  <canvas width="320" height="320"></canvas>
</body>

</html>

Disini kita menggunakan dua buah gambar: gambar bola untuk jalur dan gambar balok untuk tembok/penghalang.
Kita menaruh gambar dalam div yang memiliki style display='none' agar tidak tampil di layar. Kita akan memulai program saat semua gambar sudah selesai di muat.

Elemen lain selain gambar adalah kanvas sebagai tempat menggambar.

B. Javascript 

Kita mulai kodenya dengan pendeklarasian variable. Ada beberapa variable yang kita pakai, antara lain:

let cellMax = 100; //maksimum cell boleh dibuat 

Variable cellMax berisi Jumlah cell maksimal yang boleh dihasilkan selama algorithma berlangsung, kita bisa mengeset sebanyak yang kita mau, namun sebaiknya jangan banyak-banyak. 100 sudah cukup menurut Saya.

let cellAr = [];

Variable cellAr menyimpan semua cell-cell yang dihasilkan selama algorithma berlangsung.

let peta = [
    "XXXXXXXXXX",
    "X        X",
    "X    X   X",
    "X    X   X",
    "X    X   X",
    "X        X",
    "XXXXXXXXXX"
];

Variable peta berisi informasi tentang peta. Kita menggunakan struktur data berupa array yang berisi string. Ada banyak struktur data yang bisa dipakai untuk mendefinisikan peta. Ini adalah yang paling saya sukai karena mudah dibaca.

Variable selanjutnya dibawah ini adalah variable tambahan. 

let canvas;
let canvasCtx;
let gbrBox;
let gbrBola;

Variable-variable di atas dipakai untuk menggambar di layar.

window.onload = () => {
    //persiapan canvas
    canvas = document.body.querySelector('canvas') as HTMLCanvasElement;
    canvasCtx = canvas.getContext("2d");
    gbrBola = document.body.querySelector("img#img-bola") as HTMLImageElement;
    gbrBox = document.body.querySelector("img#img-box") as HTMLImageElement;
    let hasil: number[][] = pfCariJalan(2, 2, 8, 3);
    gambarTembok();
    gambarJalan(hasil);
    console.log(JSON.stringify(hasil));
}

Applikasi dimulai saat event window.onload(), untuk memastikan apakah semuanya sudah sudah diload. Pada fungsi window.onload, kita melakukan beberapa hal antara lain:

  • Menyiapkan canvas, 
  • Mengambil referensi untuk gambar bola dan tembok. 
  • Mencari jalur dari posisi 2,2 ke posisi 8,3 hasilnya kita simpan di variable hasil. 
  • Memanggil fungsi untuk menggambar tembok dan menggambar jalan. 
  • Berikut adalah fungsi untuk menggambar tembok.
Bila Anda menggunakan editor online, maka Anda bisa mengganti posisi awal dan akhir untuk mleihat hasilnya.

 function gambarTembok() {
    for (let jx = 0; jx < peta.length; jx++) {
        for (let ix = 0; ix < peta[jx].length; ix++) {
            if (petaKosong(ix, jx)) {
            }
            else {
                canvasCtx.drawImage(gbrBox, ix * 32, jx * 32);
            }
        }
    }
}

Fungsi gambarTembok() akan menggambar tembok sesuai informasi di peta. Fungsi petaKosong() akan memberitahu apakah posisi x,y di peta kosong atau tidak. Fungsi ini akan dibahas nanti

function gambarJalan(hasil) {
    hasil.forEach((item) => {
        canvasCtx.drawImage(gbrBola, item[0] * 32, item[1] * 32);
    });
}

Fungsi gambarJalan() akan menggambar hasil dari pencarian pada kanvas. Fungsi ini memiliki parameter hasil yang bertipe array dua dimensi yang tiap entry-nya berisi informasi posisi x dan y dari tiap2 itemnya. Detailnya akan dibahas di bawah.

Selanjutnya Saya akan membahas fungsi pfCariJalan().

function pfCariJalan(sx, sy, tx, ty) {
    let cellCr;
    let res = [];
    cellAr = [];
    //bila posisi tujuan sama dengan awal
    //kembalikan array kosong
    if ((sx == tx) && (sy == ty)) {
        return [];
    }
    cellAr.push(cellBuat(null, sx, sy, tx, ty));
    while (true) {
        //bila jumlah cell yang dihasilkan melebihi maksimum
        //kembalikan array kosong
        if ((cellAr.length >= cellMax)) {
            return [];
        }
        //cari cell yang masih terbuka (Langkah 2)
        cellCr = cellCariYangTerbuka();
        //bila ada cell yang masih terbuka
        if (cellCr) {
            //ubah status jadi tutup (Langkah 2)
            cellCr.buka = -1;
            //check jika sudah sampai tujuan (Langkah 12)
            if (pfCheckSampaiTujuan(cellCr.x, cellCr.y, tx, ty)) {
                res = pfTelusurBalik(cellCr);
                return pfRes2Array(res);
            }
            //(Langkah 1)
            pfBukaCellBaru(cellCr, tx, ty);
        }
        else {
            //Tidak ada cell yang terbuka
            //Jalur tidak ketemu
            //Kembalikan array kosong
            return [];
        }
    }
}

Ini adalah fungsi utama dari algorithma ini. Fungsi inilah yang akan mencari jalan. Fungsi ini menghasilkan sebuah array yang berisi hasil  jalur pencarian, dan akan menghasilkan array kosong bila jalur tidak ditemukan. Fungsi ini memilik 4 parameter yaitu: sx dan sy untuk posisi awal, tx, dan ty untuk posisi target.

Pembahasan isi dari fungsi ini adalah sebagai berikut:

cellAr = [];

Kita menghapus isi dari cellAr dengan cara membuat array baru. Setiap cell yang dihasilkan selama algorithma berlangsung akan disimpan di cellAr . Kita harus membersihkannya setiap kali akan memulai algorithma baru agar tidak tercampur dengan data sebelumnya

if ((sx == tx) && (sy == ty)) { 
    return [];
}

Selanjutnya kita mengecek apakah posisi target dan posisi awal adalah sama. Bila ya, maka kita akan langsung mengembalikan array kosong. Karena jalurnya sudah pasti tidak ada.

cellAr.push(cellBuat(null, sx, sy, tx, ty)); 

Selanjutnya kita membuat cell pertama dan disimpan di variable cellAr.

while (true) {
    ...
}

Selanjutnya kita mulai masuk ke perulangan. Bila Anda membaca artikel sebelumnya, maka Anda akan mendapati perulangan. Ini adalah implementasi dari perulangan tersebut.

Perulangan ini akan berlangsung terus sampai selesai. Isi dari perulangan ini adalah sebagai berikut:

 if ((cellAr.length >= cellMax)) {
     return [];
 }

Pertama kita mengecek apakah jumlah cell yang dihasilkan sudah mencapai maksimal. Bila ya, maka kita akhiri algorithma ini, dan menghasilkan array kosong. Ini berarti jalurnya tidak ditemukan.

cellCr = cellCariYangTerbuka(); 

Kemudian kita mencari cell yang terbuka yang posisinya paling dekat ke target. Langkah ini adalah penerapan langkah ke 2 dari penjelasan pada artikel sebelumnya.

Perhatikan gambar di bawah ini yang diambil dari tulisan sebelumnya. Pada langkah ini kita mencari kotak terbuka yang terdekat ke target. Kotak yang dipilih adalah kotak sebelah kanan dengan jarak 3 langkah. Anda bisa membaca tulisan sebelumnya untuk penjelasan lebih jelas.



Pencarian cell yang terbuka ini menghasilkan dua kemungkinan: ketemu atau tidak.
Bila pencarian tidak ketemu maka pencarian kita hentikan dan kita mengembalikan array kosong sebagai hasilnya.

Bila pencarian cell ketemu, maka langkah selanjutnya adalah menutup cell ini.

cellCr.buka = -1; 

Kita menutup cell dengan memberi nilai -1 pada property buka.

function pfCheckSampaiTujuan(x, y, tx, ty) {
    if ((x == tx) && (y == ty))
        return true;
    return false;
}

Selanjutnya kita melakukan pengecekan apakah kita sudah sampai atau belum.

Bila hasilnya tidak, maka kita akan membuka cell baru, dari cell sekarang dengan memanggil fungsi pfBukaCellBaru(). 

Disini proses akan berulang lagi sampai kita sampai ke target. 
Bila hasilnya ya, artinya kita sudah sampai, maka saatnya melakukan rekapan. Perhatikan gambar berikut. Ini adalah gambar saat kita sudah sampai ke target. Setelah kita sampai di target, maka selanjutnya kit akan melakukan penelusuran jalur dari cell tujuan kembali ke cell awal, untuk mendapatkan rute yang sebenarnya. 



Gambar ini diambil dari tulisan sebelumnya. Tidak semua cell yang dihasilkan melalui algorithma ini akan dipakai, kita hanya pakai cell-cell yang dilalui oleh garis ungu saja.

Kita memanggil fungsi pfTelusurBalik(cellCr). untuk melanjutkan penelusuran sampai ke posisi awal dan menghasilkan jalur pencarian.

return pfRes2Array(res);

Setelah itu kita memanggil fungsi pfRes2Array(res) yang akan mengubah hasil pencarian menjadi array biasa, dengan struktur yang lebih sederhana. Hal ini dikarenakan, algorithma ini sebenarnya menghasilkan data yang cukup kompleks. Kita perlu merubah hasilnya ke struktur yang lebih sederhana agar mudah digunakan kemudian.

Contoh hasil pencariannya adalah sebagai berikut:

[[2,2],[2,3],[3,3],[4,3],[4,2],[4,1],[5,1],[6,1],[6,2],[6,3],[7,3],[8,3]]

Tiap item dari array berisi posisi x dan y. Kita akan menggunakan posisi ini untuk menggambar jalur di layar.

Dalam penjelasan di atas, Saya telah menyebutkan banyak fungsi-fungsi yang belum dijelaskan secara detail. Berikut ini adalah penjelasan singkat dari fungsi-fungsi tersebut.

Fungsi cellbuat();

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

Fungsi ini untuk membuat cell baru. Sebuah cell adalah sebuah object dengan beberapa property. jarak menunjukkan jarak dari cell ini ke target. Perhitungannya dilakukan secara sederhana dengan menghitung jarak horizontal dan vertikal. Property induk berisi referensi ke cell induk yang sudah dibuat sebelumnya. Fungsi ini adalah penerapan dari langkah 1 pada tulisan sebelumnya. 

Fungsi cellCariYangTerbuka():

function cellCariYangTerbuka() {
    let i = 0;
    let cell = null;
    let maxLen;
    let cellTemp;
    let len = 0;
    maxLen = 10000;
    len = cellAr.length - 1;
    for (i = len; i >= 0; i--) {
        cell = cellAr[i];
        if (1 == cell.buka) {
            if (cell.jarak < maxLen) {
                cellTemp = cell;
                maxLen = cell.jarak;
            }
        }
    }
    return cellTemp;
}

Fungsi ini mencari cell yang statusnya masih terbuka dan terdekat ke target. Cell yang terbuka memilki property buka yang bernilai 1. Fungsi adalah penerapan dari langkah ke 2 dari tulisan sebelumnya.

Fungsi pfCheckSampaiTujuan():

function pfCheckSampaiTujuan(x, y, tx, ty) {
    if ((x == tx) && (y == ty))
        return true;
    return false;
}

Fungsi ini mengecek apakah kita sudah sampai di tujuan apa belum, dengan membandingkan posisi cell dengan posisi target.

Fungsi cellCheckDouble():

function cellCheckDouble(x, y) {
    let res = false;
    cellAr.forEach(cell => {
        if (cell.x == x && cell.y == y) {
            res = true;
        }
    });
    return res;
}

Mengecek apakah sebuah cell sudah ada di cellAr atau belum, untuk menghindari cell yang double. Funsgi ini adalah penerapan dari langka ke 1 point B dari tulisan sebelumnya.

Fungsi pfPosBisa():

function pfPosBisa(x, y) {
    //check cell
    if (cellCheckDouble(x, y)) {
        return false;
    }
    //check block peta
    if (!petaPosValid(x, y)) {
        return false;
    }
    return true;
}

Fungsi ini mengecek apakah kita bisa berjalan menuju posisi tertentu. Kita memanggil fungsi cellCheckDouble() dan petaPosValid() untuk mengecek apakah posisi valid apakah tidak.

Fungsi pfRes2Array():

function pfRes2Array(res) {
    let ar = [];
    res.forEach(cell => {
        ar.push([cell.x, cell.y]);
    });
    return ar;
}

Fungsi ini akan merubah cellAr yang berisi cell-cell menjadi array dua dimensi biasa. Tujuannya agar hasil algorithma ini bisa dibaca lebih mudah. Ini adalah penerapan dari langkah terakhir dari tulisan sebelumnya.

Fungsi pfTelusurBalik():

function pfTelusurBalik(cell) {
    let res = [];
    let i = 0;
    let cellTemp = null;
    let cellParent = null;
    res.unshift(cell);
    while (true) {
        //cari parent dari cell yang sedang di check
        cellParent = null;
        for (i = 0; i < cellAr.length; i++) {
            cellTemp = cellAr[i];
            if (cell.induk == cellTemp) {
                cellParent = cellTemp;
                break;
            }
        }
        //parent gak ada, berarti cell sekarang adalah cell awal, penelusuran selesai;
        if (cellParent == null) {
            return res;
        }
        else {
            //hasilnya di masukkan ke let res
            //update cell dengan cellParent
            res.unshift(cellParent);
            cell = cellParent;
        }
    }
}

Fungsi ini untuk menelusuri balik dari cell akhir ke cell awal. Hasil dari penelurusan disimpan di variable res.

Fungsi petaKosong():

function petaKosong(x, y) {
    return (peta[y].charAt(x) == " ");
}

Fungsi ini mengecek apakah posisi di peta kosong atau tidak.

Pada tulisan ini kita telah membahas bagaimana pengaplikasian algorithma path finding dalam kode pemrograman. Penjelasan saat ini masih belum begitu lengkap. Saya akan berusaha melengkapinya pada update mendatang. 


Terima kasih sudah mampir dan membaca. Bila ada pertanyaan, jangan sungkan untuk bertanya, agar tulisan ini jadi semakin lengkap.
Diposting oleh di
Label:

Tidak ada komentar:

Posting Komentar

Langganan: Posting Komentar (Atom)