Mengenal Algoritma A* (A-Star): Jantung Navigasi di Game dan Google Maps

11 November 2025   |   Irfan Rizki Aditri   |   Algoritma, GameDev, JavaScript

Ilustrasi Algoritma A-Star

Sebagai *game developer* yang sering berkutat dengan AI (kecerdasan buatan), saya bisa bilang bahwa **A-Star ($\text{A}^{*}$)** adalah algoritma wajib yang harus dikuasai. Algoritma *pathfinding* ini tidak hanya digunakan oleh musuh di game-mu untuk menemukan jalan pintas, tetapi juga oleh aplikasi navigasi seperti Google Maps untuk menentukan rute tercepat.

Filosofi A-Star: Memilih yang Paling Optimal

A-Star adalah perpaduan antara Algoritma Dijkstra (yang menjamin rute terpendek) dan *Best-First Search* (yang menggunakan heuristik untuk mempercepat pencarian). Kombinasi ini menjadikannya cepat dan akurat.

Fungsi Evaluasi $f(n)$:

A-Star bekerja dengan mengevaluasi setiap titik ($n$) menggunakan fungsi $\mathbf{f(n) = g(n) + h(n)}$:

  • $\mathbf{g(n)}$: Biaya (jarak) dari titik awal ke titik $n$ saat ini. (Faktor Real)
  • $\mathbf{h(n)}$: Heuristik. Estimasi biaya (jarak) dari titik $n$ ke titik tujuan. (Faktor Estimasi)

Penerapan dalam Game Development

Bayangkan kamu membuat game strategi, dan musuh harus menghindari sungai atau tebing (obstacle) untuk menyerang markasmu. Peta game diwakilkan sebagai *Graph* (kumpulan node/titik). A-Star memungkinkan musuh memilih jalan:

// Pseudocode A-Star di setiap Node/Titik
while (OpenList is NOT empty):
    current_node = Node dengan F_value TERKECIL
    
    // Jika sudah sampai tujuan, hentikan
    if (current_node == goal_node):
        ReconstructPath() 
        return
        
    for neighbor in current_node.Neighbors:
        tentative_g_score = current_node.g_score + Jarak(current_node, neighbor)
        
        if (tentative_g_score < neighbor.g_score):
            // Path yang lebih baik ditemukan
            neighbor.parent = current_node
            neighbor.g_score = tentative_g_score
            neighbor.h_score = HitungHeuristik(neighbor, goal_node)
            neighbor.f_score = neighbor.g_score + neighbor.h_score
            
            if neighbor is NOT in OpenList:
                Add neighbor to OpenList

Kode di atas menunjukkan esensi dari A-Star: selalu mencari rute yang saat ini terlihat paling menjanjikan (memiliki nilai $\mathbf{f(n)}$ terkecil) sambil tetap memastikan rute tersebut valid.

Heuristik yang Benar (Admissible Heuristic)

Kekuatan A-Star terletak pada fungsi $\mathbf{h(n)}$. Agar algoritma dapat menjamin rute terpendek secara optimal, heuristik yang digunakan harus *admissible* (tidak pernah melebih-lebihkan biaya sebenarnya). Heuristik yang paling umum adalah Jarak Euclidean (garis lurus) atau Jarak Manhattan (pergerakan vertikal/horizontal, seperti di papan catur).

"Jika kamu menggunakan heuristik yang terlalu tinggi (misalnya memprediksi jarak 100km padahal aslinya 50km), A-Star akan berjalan lebih cepat, tetapi rute yang dihasilkan mungkin bukan yang terpendek."

Baik itu dalam game *Arcade Escape* (untuk navigasi musuh) atau simulasi fisika (untuk analisis lintasan), A-Star adalah bukti bagaimana matematika dan coding dapat menghasilkan solusi yang cerdas dan efisien untuk masalah navigasi di dunia nyata dan virtual.

**Sumber Referensi:**
[1] Pearl, J. (1984). *Heuristics: Intelligent Search Strategies for Computer Problem Solving*. Addison-Wesley.
[2] Russell, S. J., & Norvig, P. (2020). *Artificial Intelligence: A Modern Approach*. 4th ed. Pearson Education.
[3] Dijkstra, E. W. (1959). *A note on two problems in connexion with graphs*. Numerische Mathematik.