Algorithma Path Finding #5: Membuat karakter berjalan mengikuti jalur yang dibuat oleh algorithma path-finding

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

Dalam tulisan sebelumnya Kita telah membahas tentang penerapan algoritma path-finding untuk mencari jalur pada daerah yang di klik di layar pada layar yang bersifat responsif.

Dalam tulisan kali ini, Kita akan membahas bagaimana membuat karakter berjalan mengikuti jalur yang telah dibuat oleh algoritma path-finding tersebut, tentu saja pada kanvas yang responsif karena kita akan mencobanya bukan hanya di PC tapi juga di telepon gengam.

Demonya bisa dilihat disini:

Kode sumbernya bisa di unduh disini:

Videonya juga tersedia di youtube:



Penjelasan kode sumber:

Pembahasan sekarang lebih kompleks dari sebelumnya sehingga sekarang file javascript-nya Kita pisah menjadi beberapa bagian antara lain:

• Pathfinder.js: menangani algorithma path finding
• Game.js: file utama 
• Peta.js: menangani peta
• Window.js: menangani segala yang berhubungan dengan window seperti saat window di- resize.

Untuk selanjutnya Saya akan memakai file js terpisah.

Struktur Object Karakter:

Dalam pembahasan kali ini kita akan memiliki sebuah karakter yang berjalan mengikuti jalur path finding. Untuk itu kita perlu menyusun struktur untuk karakter ini.

let karakter = {

    jalur: [],

    jalurn: 0,

    pos: {

        x: 1,

        y: 1

    },

    status: st_idle

};

Struktur karakter ini adalah struktur minimal untuk karakter yang bisa berjalan. 

jalur: berisi informasi jalur hasil path-finding. Jalur disimpan dalam bentuk Array.
jalurn: informasi index ke berapa dari jalur di atas.
pos: berisi informasi posisi x dan y
status: status karakter saat ini

Karakter memiliki status yang didefinisikan dalam konstanta sbb:

const st_idle = 1;
const st_jalan = 2;

window.onload()

Saat saat event window.onload() Kita membuat interval untuk proses perulangan. Dalam perulangan ini kita memanggil fungsi update() dan render(). Fungsi update() akan memperbaharui informasi karakter sedangkan fungsi render() akan melakukan proses penggambaran.

setInterval(() => {
  update();
  render();
}, 100);


canvas.onclick()

Pada saat kanvas diklik, kita melakukan pengecekan terdahulu apakah saat ini status karakter sedang berjalan atau tidak. Bila karakter sedang berjalan maka kita langsung mengakhiri fungsi ini. Kita harus menunggu karakter selesai berjalan sebelum memberi perintah baru.

  if (karakter.status != st_idle)
    return;

Bila ternyata karakter sedang diam, maka kita lanjutkan prosesnya. Kita mencari posisi klik di layar. Metodenya sama dengan tulisan sebelumnya.

let rect = canvas.getBoundingClientRect();
let poslx = (e.clientX - rect.x) * canvasScaleX;
let posly = ((e.clientY - rect.y) * canvasScaleY);
let posx = Math.floor(poslx / 32);
let posy = Math.floor(posly / 32);

Kemudian kita mencari jalur ke posisi tersebut dari posisi karakter yang terakhir.

let hasil = pfCariJalan(karakter.pos.x, karakter.pos.y, posx, posy);

Kemudian kita mengubah status karakter dengan mengisi informasi yang dibutuhkan agar karakter mulai berjalan.

karakter.status = st_jalan;
karakter.jalur = hasil;
karakter.jalurn = -1;

Kita mengubah status karakter yang awalnya diam ke berjalan. Kita juga memasukkan jalur hasil algoritma path-finding.
Saat karakter belum berjalan, isi dari variable jalurn adalah -1. Saat karakter berjalan, maka jalurn akan mulai berjalan dari angka 0 dst. Hal ini karena Array dimulai dari angka 0.

fungsi Update():

Fungsi update berisi proses untuk memperbaharui informasi karakter.

function update() {
  if (karakter.status == st_idle) {}
  else if (karakter.status == st_jalan) {
    if (karakter.jalurn >= (karakter.jalur.length - 1)) {
      karakter.status = st_idle;
    }
    else {
      karakter.jalurn++;
      karakter.pos.x = karakter.jalur[karakter.jalurn][0];
      karakter.pos.y = karakter.jalur[karakter.jalurn][1];
   }
  }
}

Kita mengecek status dari karakter.
Bila statusnya st_idle, maka tidak ada yang dilakukan.
Bila statusnya st_jalan maka kita memperbaharui proses jalan.
Saat berjalan, kita mengecek apakah proses jalan sudah selesai. Hal ini ditandai dengan jalurn yang sudah melebihi panjang dari jalur path-finding.

Bila karakter sudah selesai berjalan, maka statusnya kita rubah ke st_idle.

if (karakter.jalurn >= (karakter.jalur.length - 1)) {
  karakter.status = st_idle;
}

Bila proses jalan belum selesai, maka kita menambah isi dari jalurn. Kemudian kita mengubah posisi karakter sesuai dengan informasi dari jalur path finding.

karakter.jalurn++;
karakter.pos.x = karakter.jalur[karakter.jalurn][0];
karakter.pos.y = karakter.jalur[karakter.jalurn][1];

Fungsi Render():

Fungsi ini berisi proses pengambaran. Kita menggambar peta, jalan dan jalur sesuai informasi yang ada. Kita tidak membahas terlalu dalam mengenai fungsi ini karena isinya Saya rasa sudah cukup jelas dan sudah sering dibahas di tulisan-tulisan sebelumnya.


Terima kasih sudah mampir dan membaca. Bila ada pertanyaan, jangan sungkan untuk bertanya.

Algorithma Path Finding #4 Mencari posisi klik pada kanvas yang di skala

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

Pada tulisan sebelumnya kita telah membahas bagaimana menggunakan algorithma path-finding untuk mencari jalan pada posisi yang di klik pada kanvas. Dan kita juga membahas bagaimana membuat kanvas bersifat responsif, agar bisa menyesuaikan dengan ukuran layar.

Sekarang kita akan melanjutkan dengan menggabungkan keduanya. Kita akan mencari jalur pada posisi yang diklik pada kanvas yang bersifat responsif.

Hasil nya bisa Anda dicoba di sini.

Silahkan buka linknya, dan ubah ukuran browsernya kemudian klik pada kanvas.  Anda bisa lihat bagaimana algorithma path-finding ini bekerja pada ukuran kanvas yang berbeda-beda.

Kode sumber bisa diunduh di sini

Atau Anda bisa mencoba mengedit kodenya secara langsung disini:

Mendeteksi posisi yang di klik pada kanvas yang bersifat responsif memiliki tantangan tersendiri. Hal ini karena kanvas tidak hanya memiliki ukuran yang berbeda-beda namun juga memiliki posisi yang berbeda-beda pula.

Kode sumber dari pembahasan kali diambil dari dua tulisan sebelumnya dengan sedikit perubahan. Disini saya akan membahas perubahannya saja. Sisanya sama saja dan bisa dilihat pada artikel sebelumnya, atau anda bisa mengunduh kode sumbernya.

canvas.onclick = (e) => {
    let rect = canvas.getBoundingClientRect();
    let poslx = (e.clientX - rect.x) * canvasScaleX;
    let posly = ((e.clientY - rect.y) * canvasScaleY);
    let posx = Math.floor(poslx / 32);
    let posy = Math.floor(posly / 32);
    bersihkanLayar();
    hasil = pfCariJalan(1, 1, posx, posy);
    gambarPeta();
    gambarJalan(hasil);
};

Perubahan yang paling mendasar adalah pada saat canvas.onclick(). Pada tulisan sebelumnya kita mencari posisi klik di kanvas dengan menggunakan e.clientX dan e.clientY saja. Hal ini tidak berlaku untuk kanvas yang responsif.

Proses penghitungannya sbb:

Pertama kita mencari dulu posisi kanvas dilayar. Posisi kanvas sekarang selalu berada di tengah menyesuaikan dengan dimensi layar.

    let rect = canvas.getBoundingClientRect();

getBoundingClientRect() akan menghasilkan posisi, panjang dan lebar kanvas. Kemudian kita menggunakan nilainya untuk melakukan perhitungan selanjutnya.

    let poslx = (e.clientX - rect.x) * canvasScaleX;
    let posly = (e.clientY - rect.y) * canvasScaleY;

e.clientX dan e.clientY adalah posisi diklik di layar, bukan di kanvas.. 

rect.x dan rect.y adalah posisi kanvas.

canvasScaleX dan canvasScaleY adalah skala dari kanvas yang dihitung saat kanvas diskala mengikuti ukuran layar. Anda bisa melihat pada fungsi resize() saat kanvas diskala

let posx = Math.floor(poslx / 32);
let posy = Math.floor(posly / 32);

Karena kita menggunakan grid dengan panjang dan lebar 32 maka nilai posisi akhirnya kita bagi 32.

Selanjutnya seperti biasa, kita melakukan proses pencarian jalur, update kanvas, dst seperti pada tulisan sebelumnya.

Pada tulisan berikutnya, Saya akan membahas bagaimana membuat karakter berjalan mengikuti jalur yang telah dibuat oleh algorithma path-finding.

Terima kasih sudah mampir dan membaca. Bila ada pertanyaan, silahkan bertanya di komentar

Macam kanvas responsif

Tulisan ini akan membahas macam kanvas responsif. Responsif disini maksudnya adalah kanvas itu akan berubah ukurannya mengikuti resolusi layar. Hal ini sangat penting dalam pembuatan aplikasi pada telepon genggam karena banyaknya resolusi yang dimiliki.

Secara umum ada empat macam pendekatan untuk responsif yang pernah Saya temui. Tiga pertama sering dipakai di applikasi umum sedangkan yang terakhir hanya saya temukan di aplikasi Animate. Saya tidak membahas yang terakhir karena penggunaannya kurang umum dan Saya kurang paham juga.

Yang pertama disebut letterbox, pan atau kotak. Memiliki ciri-ciri sebagai berikut:
Rasio kanvas tetap
Kanvas diskala hingga memenuhi layar, tapi tidak sampai membuat gambar melebihi layar.
Ada jeda kosong di pinggir samping atau atas, karena rasio kanvas dan layar kadang tidak sama.

Yang kedua disebut strecth atau melar.
Rasio kanvas tidak dijaga, membuat gambar tampak melar tidak merata.
Kanvas diskala hingga memenuhi layar.
Tidak ada jeda kosong.

Yang ketiga disebut background atau cover, atau layar-penuh
Rasio kanvas tetap
Kanvas diskala memenuhi layar hingga melebihi layar dan gambar terpotong.
Tidak ada jeda kosong.

Penjelasan Saya cukupkan sampai sini dulu, berikutnya kita akan membahas yang pertama di tulisan berikutnya.

Algorithma Path Finding #3: Mencari jalur pada posisi yang di klik di layar.

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

Pada tulisan sebelumnya kita telah membahas penerapan algorithma path finding dalam bahasa pemrograman.

Tulisan sekarang akan membahas penggunaan algorithma path finding untuk mencari jalur ke posisi yang di-klik di layar. Hal ini banyak ditemui pada banyak game seperti RTS, RPG, Point and Click adventure, dsb.

Saya biasa melakukan hal ini untuk mengetest algorithma apakah sudah berjalan dengan benar. Dengan mengetest berkali-kali di posisi berlainan akan diketahui kalau ada masalah, seperti saat jalur yang dihasilkan tidak sesuai harapan, atau jalurnya malah tidak ada.

Hasilnya bisa dilihat secara daring di sini.

Kode sumbernya bisa di unduh disini.

Setelah di unduh., buka file index.html di browser, kemudian klik pada posisi acak di layar untuk melihat apakah algorithma ini sudah benar apa belum. 

Atau anda bisa mencoba codenya secara daring di bawah ini:

Contoh hasilnya akan tampak seperti dibawah ini.

Setiap kali kita klik di layar, maka algorithma path finding ini akan mencari jalur ke posisi tersebut.

Jika diperhatikan jalur yang dihasilkan mungkin agak sedikit aneh.Seperti tampak pada gambar no 2. Jalurnya terkesan sangat boros dan tidak optimal.

Hal ini karena algorithma ini adalah aglorithma path finding yang paling sederhana dari jenisnya. Saya akan membahas algorithma path-finding dari jenis yang lain pada tulisan berikutnya.

Berikut adalah penjelasan tentang kodenya:

window.onload = () => {
    canvas = document.body.querySelector('canvas');
    canvasCtx = canvas.getContext("2d");
    gbrBola = document.body.querySelector("img#img-bola");
    gbrBox = document.body.querySelector("img#img-box");

    gambarPeta();

    canvas.onclick = (e) => {
        let posx = Math.floor((e.clientX) / 32);
        let posy = Math.floor((e.clientY) / 32);
        bersihkanLayar();
        let hasil = pfCariJalan(1, 1, posx, posy);
        gambarPeta();
        gambarJalan(hasil);
    };
};

Kodenya tidak jauh berbeda dengan kode pada tulisan sebelumnya. Kita cuman menambahkan fungsi onclick() pada canvas yang akan mendeteksi event mouse diklik.

Posisi diklik di layar ditentukan oleh e.clientX dan e.clientY.  Setiap kali layar diklik, maka algorithma path finding akan mencari jalur ke posisi tersebut, kemudian hasilnya digambar di layar.

Sisanya adalah sama dengan kode pada tulisan sebelumnya.

Pada tulisan ini, kita menggunakan kanvas yang statis yang ukurannya tidak berubah mengikuti ukuran browser. Pada tulisan berikutnya, Saya akan membahas bagaimana mengaplikasikan algorithma ini pada kanvas yang berubah-ubah. Namun sebelumnya Saya akan membahas dulu bagaimana membuat kanvas bersifat responsif.

Terima kasih sudah mampir dan membaca.

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. 

Pada tulisan berikutnya, akan dibahas bagaimana mengetest algorithma ini dengan cara meng-klik pada posisi acak di layar untuk melihat apakah algorithma ini bisa mencari jalur untuk berbagai macam posisi target yang terbeda.

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

Enable GingerCannot connect to Ginger Check your internet connection
or reload the browserDisable in this text fieldEditEdit in GingerEdit in Ginger×Enable GingerCannot connect to Ginger Check your internet connection
or reload the browserDisable in this text fieldEditEdit in GingerEdit in Ginger×

Algorithma Path Finding #1: Pengenalan konsep dengan gambar sederhana

Tulisan ini akan membahas konsep algorithma path finding. Algorithma path-finding adalah algorithma untuk mencari jalan. 

Disini kita akan membahas algorithma path finding yang paling sederhana,  tidak memiliki fungsi yang bermacam-macam, yang penting bisa menemukan jalan. Jalan yang dihasilkan juga bukan jalan yang paling efisien, yang penting ketemu. 

Mari kita mulai pembahasannya dengan gambar berikut ini. Gambar ini menggambarkan permasalahan dasar dalam path-finding. Kita akan mencari jalur dari A ke B. Di tengah-tengah ada halangan, berupa kotak berwarna coklat. Kita tidak mungkin mengambil jalan lurus, karena pasti akan menabrak. Jadi kita harus jalan memutar. Suatu hal yang simple bagi kita, tapi sebenarnya sangat rumit apabila harus diimplementasikan dengan komputer.

Peta yang kita gunakan sebagai model berbentuk grid yang terdiri dari kotak-kotak yang akan kita namakan cell. Ini adalah permodelan yang paling sederhana. Algorithma path finding yang ada sekarang bisa memiliki peta berbentuk macam-macam, mulai dari vector sampai dengan mesh, dll. Namun intinya sama saja. Dasarnya sama, bila Anda bisa memahami dasarnya maka berikutnya akan lebih mudah untuk dipelajari.

Gambar berikut ini menunjukkan jalur yang dihasilkan dari algorithma ini. Jalur ini bisa menghubungkan titik A ke B.

Jalurnya tidak sempurna. Tidak ada pergerakan diagonal, padahal kalau kita bergerak diagonal tentu jalurnya akan semakin pendek. Kita akan membahas pergerakan diagonal di tulisan berikutnya. Seperti yang Saya bilang sebelumnya, algorithma yang dibahas disini adalah yang paling dasar. Mari kita mulai algorithma ini selangkah demi selangkah 🚶🏽‍♀️🚶🏽‍♀️🚶🏽‍♀️.

🍕 Langkah 1:

Kita akan berjalan dari A ke B. Yang kita lakukan pertama adalah menentukan kemana akan melangkah selanjutnya. Kita punya 4 pilihan: atas, bawah, kiri dan kanan.Kita tidak membahas langkah diagonal ke kanan atas atau yang lainnya, terlalu rumit. Kita bahasnya yang dasar-dasar saja. 

Algorithma path finding bersifat heuristic, atau kira-kira. Mengiranya juga tidak terlalu jauh, hanya mengira selangkah kedepan saja. Walau cuman kira-kira, tapi kesempatan suksesnya besar. Seperti ketika kita ujian dulu, jawabnya kira-kira, tapi dapat 100 🏆 

Perhatikan gambar di bawah. Cell berwarna biru muda adalah cell kandidat kemana kita akan melangkah selanjutnya. Karena kita tidak tahu kemana harus melangkah, maka kita buat semua kemungkinan.

Cell berwana biru muda ini kita sebut cell terbuka. Kita sebut demikian karena cell ini adalah cell dimana terbuka kemungkinan untuk melangkah. 

Perhatikan angka-angka yang tertera di tiap cell ini. Angka itu menunjukkan perkiraan jauhnya jarak dari cell tersebut ke tujuan. Jaraknya dihitung dengan cara menghitung jarak vertikan dan horizontal.

Cell sebelah atas berjarak lima, karena untuk sampai ke B dibutuhkan 4 langkah ke kanan dan 1 langkah ke bawah. Jarak ini adalah jarak kira-kira, tanpa memperhatikan ada halangan atau tidak, benar atau tidak, akurat atau tidak. Yang penting adalah cara hitungnya konsisten.

Cell sebelah kiri juga berjarak lima, karena untuk sampai ke B dibutuhkan 4 langkah ke kanan. Perhatikan bahwa kita tidak mempedulikan ada halangan atau tidak. Kita hanya mengira-ngira saja.

Cell A berwarna hijau muda menunjukkan cell aktif saat ini yaitu dimana kita berada saat ini. 

Panah merah menunjukkan arah dari cell baru ke cell awal. Semua cell baru dibuat dari cell A sehingga arah panah menunjuk ke cell A. 

Dalam membuka cell baru ini ada beberapa hal yang perlu diperhatikan antara lain:

A. Cell baru tidak boleh keluar dari peta.
B. Cell baru tidak boleh bertumpuk dengan cell yang sudah ada.
C. Cell baru tidak boleh menempati cell yang sama dengan cell yang lain.
D. Cell baru tidak boleh menempati posisi yang diisi oleh element lain seperti halangan, dsb

🍔 Langkah ke 2:

Langkah berikutnya adalah mengumpulkan semua cell yang terbuka kemudian kita tentukan cell yang paling dekat ke target. Saat ini baru ada 4 cell yang terbuka, karena kita baru melangkah. Bila kita sudah melangkah jauh, maka jumlahnya akan semakin banyak. Kemungkinannya jadi banyak dan kita harus memilih salah satu.

Bila diperhatikan dari cell-cell tersebut, maka cell di kanan memiliki jarak terdekat, yaitu 3. Kita akan melangkah kesini. Saat ini kita hanya tahu bahwa cell ini yang paling dekat ke tujuan. Jadi ya, kita melangkah ke sini aja. 

Perhatikan bahwa saat kita memilih cell, yang kita pilih adalah cell yang jaraknya paling kecil. Cell tersebut tidak harus berada di sebelah cell yang aktif.  Yang terpenting jaraknya paling kecil, dan statusnya masih terbuka, masih ada kesempatan, masih jomblo :D. Disinilah anak panah akan memiliki peran yang sangat penting. Karena panah ini menunjukkan arah kembali ke titik awal.

🍝 Langkah ke 2a:

Setelah memilih cell baru, ada hal yang harus kita lakukan, yaitu menutup cell yang sekarang sedang aktif. Perhatikan gambar dibawah. cell A sekarang berwarna abu-abu. Cell ini kita sebut cell tertutup. Kita menutup kemungkinan untuk melangkah kembali ke sini. Sekali melangkah pantang mundur ke belakang. 

🍠 Langkah ke 2b:

Setelah menutup cell yang sedang aktif, kita pindah ke kanan, yaitu ke tempat cell yang telah kita pilih tadi. Cell sebelah kanan sekarang berubah warnanya menjadi hijau.

🍟 Langkah 3:

Langkah ini adalah perulangan dari langkah 1. Kita membuka cell baru, menghitung jarak dan menambahkan arah panah kembali ke cell sekarang. Kita tidak membuka cell baru di arah kanan karena cell tersebut berupa cell halangan yang tidak bisa dilewati.

🌭 Langkah 4:

Mulai sekarang, maka proses akan berulang terus sampai akhir. Langkah 4,6,8 dst, atau langkah genap akan sama dengan langkah 2. Sedangkan langkah 5, 7, 9 dst akan sama dengan langkah 1. Saya tidak akan menjelaskan panjang lebar lagi karena isinya bakal mirip.

Kita berpindah ke cell baru, dan menutup cell yang sekarang. Cell baru yang kita pilih adalah cell bawah, karena nilainya paling kecil. Sebenarnya ada dua cell terbuka yang nilainya paling kecil. Satu berada di atas, dan satu lagi berada di bawah. Kita boleh memilih yang mana saja. Namanya juga mengira-ngira. Yang penting jalan dulu, gak usah ragu-ragu, gak usah bingung, jalan terus. 🚧🚧🚧

🍿 Langkah 5:

Langkah ini mirip dengan langkah 1. Bedanya kali ini kita akan membuka langkah ke kanan. Karena dikiri sudah ditempati, sudah ada yang punya, di atas juga. Yang ada di syukuri, 

🥓 Langkah 6:

Kita pindah ke kanan. 

🥚 Langkah 7:

Kita membuka kotak yang dikanan.

🥞 Langkah 8:

.

Kita pindah ke kanan

🍳 Langkah 9:

Kita buka cell baru. Tinggal sedikit lagi.

🍞 Langkah 10:

Kita melangkah ke kanan. Perhatikan bahwa kita memilih kotak di kanan bukan di atas. Hal ini sama saja. Yang penting adalah kita tetap memilih, tidak golput.

🥐 Langkah 11:

Kita membuka kotak baru dan ternyata sudah sampai, sehingga kita tidak perlu membuka kotak sebelah kanan lagi.

🥖 Langkah 12

Kita melangkah terakhir dan akhirnya sampai ke tempat tujuan.

Padah langkah terakhir ini, kita sudah berhasil sampai tujuan. Tugas selanjutnya adalah menarik jalur dari B ke A dengan mengikuti anak panah. Jalur yang dihasilkan adalah jalur yang terbalik karena mengikuti anak panah. Namun tidak masalah karena kita tinggal membaliknya lagi. 

Sekarang kita sudah punya jalur dari A ke B. Algorithma ini telah selesai dan bisa dipakai untuk masalah-masalah yang lain yang berhubungan dengan pencarian jalan. Anda bisa mengubah struktur peta dengan memindahkan halangan, atau membuat petanya semakin kompleks. 

Algorithma yang dijelaskan disini sangat banyak kekurangannya, karena hanya membahas hal yang pokok saja. Algorithma path-finding jenis ini juga sering disebut dengan speed path-finding, karena bisa menemukan jalur dengan cepat namun hasilnya tidak maksimal.

Pada tulisan berikutnya Saya akan membahas penerapan algorithma path-finding ini dalam bentuk kode pemrograman.

Terima kasih telah datang dan membaca. Silahkan ambil pisangnya satu-satu 🍌🍌🍌.

Enable GingerCannot connect to Ginger Check your internet connection
or reload the browserDisable in this text fieldEditEdit in GingerEdit in Ginger×