Memahami Pathfinding Game: DFS, BFS, Dijkstra, dan A*

Pernahkah Anda bertanya-tanya bagaimana musuh dalam game bisa menavigasi labirin yang rumit untuk menemukan pemain, atau bagaimana unit permainan strategi mencari rute terbaik untuk menghindari rintangan? Jawabannya ada pada Algoritma Pathfinding.

Dalam panduan ini, kita akan menjelajahi empat algoritma pathfinding paling umum yang digunakan dalam pengembangan game, dari yang paling sederhana hingga standar industri saat ini.

1. Dunia Sebagai Graph atau Grid

Sebelum sebuah algoritma dapat menemukan jalur, algoritma tersebut harus memahami simulasi dunia game. Sebagian besar game merepresentasikan area yang bisa dipijak sebagai Grid (kotak-kotak, heksagon) atau NavMesh (poligon). Semua ini pada dasarnya bisa disederhanakan menjadi Graph (Graf): sekumpulan titik (node) yang dihubungkan oleh garis (edge).

Tujuan utama kita sangat jelas: menemukan urutan titik dari titik awal (start) menuju titik tujuan (target).

2. Depth-First Search (DFS)

Bayangkan Anda sedang berjalan di dalam labirin. Anda memilih satu lorong, menelusurinya terus sampai menemui jalan buntu, lalu kembali ke persimpangan terakhir dan mencoba lorong lain. Ini adalah cara kerja DFS secara harfiah.

Cara kerja: Menjelajah "sedalam" mungkin ke dalam rute graf sebelum akhirnya mundur (backtracking) jika menemui kegagalan.
Kelebihan: Menggunakan sangat sedikit memori.
Kekurangan: Algoritma ini tidak menjamin rute terpendek. Pada ruang terbuka, DFS bisa mengambil jalur zig-zag ekstrem ke seluruh penjuru ruangan sebelum menemukan targetnya.
Cocok untuk: Pembuatan labirin acak (procedural generation) atau memeriksa apakah sebuah jalur itu ada, tetapi amat sangat buruk untuk pergerakan karakter.

Contoh Kode (Berbasis Grid):

function dfs_grid(grid, start, target) {
  let stack = [start];
  let visited = new Set();
  
  while (stack.length > 0) {
    let current = stack.pop(); // Ambil dari urutan paling akhir (LIFO)
    let key = `${current.x},${current.y}`;
    
    if (current.x === target.x && current.y === target.y) return true; // Ketemu
    
    if (!visited.has(key)) {
      visited.add(key);
      let neighbors = getNeighbors(grid, current); // cth: atas, bawah, kiri, kanan
      for (let neighbor of neighbors) stack.push(neighbor);
    }
  }
  return false;
}

3. Breadth-First Search (BFS)

Berbeda dengan DFS, BFS menjelajahi dunia secara merata. Bayangkan Anda menjatuhkan batu ke dalam kolam; riaknya melebar ke segala arah secara bersamaan.

Cara kerja: Algoritma memeriksa semua area sekitarnya terlebih dahulu (radius 1 langkah), kemudian area di sekitar area tersebut (radius 2 langkah), dan terus melebar selangkah demi selangkah.
Kelebihan: Secara otomatis menjamin rute terpendek, dengan syarat setiap langkah punya bobot kesulitan yang sama (unweighted graph).
Kekurangan: BFS menjelajah ke segala penjuru arah. Ia tidak peduli di mana target berada hingga secara tidak sengaja "menabrak" target tersebut. Karena itu, kinerjanya lambat memproses banyak petak dan boros memori.
Cocok untuk: Mencari jalur terpendek pada grid kotak yang polos, di mana setiap area memakan usaha langkah yang sama (misalkan game puzzle tile base sederhana).

Contoh Kode (Berbasis Grid):

function bfs_grid(grid, start, target) {
  let queue = [start];
  let visited = new Set();
  visited.add(`${start.x},${start.y}`);
  
  while (queue.length > 0) {
    let current = queue.shift(); // Ambil dari urutan paling awal (FIFO)
    
    if (current.x === target.x && current.y === target.y) return true; // Ketemu
    
    let neighbors = getNeighbors(grid, current);
    for (let neighbor of neighbors) {
      let key = `${neighbor.x},${neighbor.y}`;
      if (!visited.has(key)) {
        visited.add(key);
        queue.push(neighbor);
      }
    }
  }
  return false;
}

4. Algoritma Dijkstra

Bagaimana jika dunia tidak sepenuhnya rata? Bagaimana bila berjalan melewati rawa membutuhkan waktu dua kali lipat dibanding berjalan di aspal? BFS mengasumsikan setiap langkah berharga sama (cost = 1). Algoritma Dijkstra memperbaiki kelemahan ini dengan memperkenalkan movement cost (bobot graf/weighted graph).

Cara kerja: Melacak "akumulasi biaya perjalanan" dari titik awal ke semua titik yang sedang dijelajahi. Dijkstra akan selalu memprioritaskan penjelajahan ke titik berikutnya yang memiliki total poin/biaya perjalanan terendah.
Kelebihan: Dijkstra menjamin jalur dengan rintangan/biaya termurah (terpendek atau termudah) di peta dengan medan yang bervariasi (gunung, jalan raya, air).
Kekurangan: Sama seperti BFS, Dijkstra melebar secara radial (walau ia akan lebih dulu menjelajah daratan yang mudah). Ia tidak "membidik" ke arah tujuan. Pada ukuran map yang masif, melakukan ini terlalu intensif secara komputasi.
Cocok untuk: Permainan strategi (RTS) dengan banyak jenis medan, tapi hanya efisien bila posisi target tidak diketahui pasti atau ketika mencari rute ke banyak objek sekaligus.

Contoh Kode (Berbasis Grid dengan bobot bervariasi):

function dijkstra_grid(grid, start, target) {
  // Menggunakan array yang disortir untuk mensimulasikan Priority Queue (Min-Heap)
  let pq = [{ node: start, cost: 0 }];
  let costs = {};
  costs[`${start.x},${start.y}`] = 0;
  
  while (pq.length > 0) {
    pq.sort((a, b) => a.cost - b.cost); // Proses jarak/biaya termurah lebih dulu
    let current = pq.shift().node;
    
    if (current.x === target.x && current.y === target.y) return true; // Ketemu
    
    let currentCost = costs[`${current.x},${current.y}`];
    let neighbors = getNeighbors(grid, current);
    
    for (let item of neighbors) { // item berisi .node dan .weight (kesulitan medan)
      let nextNode = item.node;
      let newCost = currentCost + item.weight; 
      let key = `${nextNode.x},${nextNode.y}`;
      
      // Jika belum dikunjungi atau menemukan rute yang lebih murah
      if (!(key in costs) || newCost < costs[key]) {
        costs[key] = newCost;
        pq.push({ node: nextNode, cost: newCost });
      }
    }
  }
  return false;
}

5. Algoritma A* (A-Star)

Dijkstra cukup pintar, tapi dia buta arah terhadap tujuan akhir. A* lahir dengan cara mengambil pondasi dasar Dijkstra lalu memberikannya semacam "kompas". Algoritma Inilah raja pathfinding yang tak terbantahkan dalam industri game.

Cara kerja: A* menggunakan fitur yang disebut heuristic (perkiraan logis yang cerdas) untuk memperkirakan sisa jarak dari titik saat ini ke garis finish. A* mengevaluasi wilayah berdasarkan rumus: F = G + H
- G: Biaya akurat sesungguhnya dari garis awal ke titik saat ini (seperti Dijkstra).
- H (Heuristic): Estimasi kasar jarak dari titik saat ini ke titik target.
- F: Nilai total biaya. A* akan selalu memprioritaskan mengecek node dengan nilai F terendah terlebih dahulu.
Kelebihan: Sangat cepat dan responsif. Karena algoritma ini secara aktif "meregang" ke arah target, ia mengabaikan jalur yang jelas-jelas bergerak ke arah yang salah. A* tetap menjamin rute pergerakan terpendek (asalkan rumus heuristic di desain dengan benar).
Kekurangan: Bisa memakan jumlah memori yang besar pada lingkungan raksasa (Open world map) sehingga memerlukan optimasi ekstra seperti sistem Hierarchical Pathfinding dan NavMesh poligon khusus.
Cocok untuk: Hampir semua AI modern mutakhir yang memicu pergerakan karakter A-ke-B.

Contoh Kode (Berbasis Grid beserta Heuristic):

// Rumus jarak Manhattan untuk pergerakan 4-arah dalam grid
function heuristic(nodeA, nodeB) {
  return Math.abs(nodeA.x - nodeB.x) + Math.abs(nodeA.y - nodeB.y);
}

function a_star_grid(grid, start, target) {
  let pq = [{ node: start, fCost: 0 }];
  let gCosts = {}; // Biaya (Cost) asli dari lokasi start
  gCosts[`${start.x},${start.y}`] = 0;
  
  while (pq.length > 0) {
    pq.sort((a, b) => a.fCost - b.fCost); // Proses nilai F (F-cost) terendah terlebih dahulu
    let current = pq.shift().node;
    
    if (current.x === target.x && current.y === target.y) return true; // Ketemu
    
    let neighbors = getNeighbors(grid, current);
    for (let item of neighbors) {
      let nextNode = item.node;
      let newGCost = gCosts[`${current.x},${current.y}`] + item.weight; 
      let key = `${nextNode.x},${nextNode.y}`;
      
      if (!(key in gCosts) || newGCost < gCosts[key]) {
        gCosts[key] = newGCost;
        // F = G + H
        let fCost = newGCost + heuristic(nextNode, target); 
        pq.push({ node: nextNode, fCost: fCost });
      }
    }
  }
  return false;
}

Kesimpulan Singkat

DFS: Berjalan tanpa tujuan jelas sampai menabrak finish. Buruk untuk pathfinding.
BFS: Bergerak meluas keluar seperti riak air. Menemukan rute terpendek di jarak kotak yang bobot jalannya rata.
Dijkstra: Meluas namun mengutamakan medan jalan termurah. Menemukan rute berbiaya usaha terendah pada map bergelombang/rintangan.
A:* Secara cerdas membidik ke arah tujuan finish. Solusi terbaik standar perindustrian.

Memahami konsep-konsep ini akan secara dramatis meningkatkan cara Anda merancang pergerakan kecerdasan buatan (AI) buatan sendiri!

Game Pathfinding Explained: DFS, BFS, Dijkstra, and A*