- Untuk mengimplementasikan pengejaran monster dalam game 8-bit top-down bergaya Zelda, gerakan lurus sederhana saja tidak cukup, sehingga artikel ini membandingkan Dijkstra dan A* untuk mencari titik kompromi pathfinding yang cocok untuk game
- Gerakan lurus akan berhenti saat terhalang dinding, tetapi dengan wall-sliding gerakan bisa mengikuti dinding sehingga kontrol terasa lebih baik dan juga memungkinkan unsur strategi dengan menjebak monster pada medan tertentu
- Algoritme Dijkstra menjamin jalur terpendek, tetapi karena menjelajah luas di sekitar node awal, pada game yang tujuan per frame-nya berubah ia melakukan terlalu banyak komputasi dibanding hanya menentukan arah berikutnya yang dibutuhkan
- A* menentukan prioritas pencarian berdasarkan jarak ke tujuan sehingga lebih dulu memeriksa arah menuju tujuan, lalu saat menemui dinding ia menyelidiki node di sekitarnya dan tidak mengunjungi ulang node yang sudah dilihat, sehingga bisa menemukan jalur memutar
- Pada peta game, kecepatan dan tingkat kesulitan implementasi bisa diatur dengan graf implisit yang tidak membuat adjacency list sebelumnya, pencarian per tile, dan heuristik berbasis geometri seperti batas kedalaman iterasi
Konteks game dan kebutuhan dasar
- Dalam game 8-bit top-down bergaya Zelda berbasis PPU466, monster perlu mengejar pemain
- PPU466, mirip fantasy console seperti PICO-8, memiliki keterbatasan berupa grafis 8-bit, 4 warna per tile, latar belakang tetap, dan jumlah sprite yang sedikit
- Tujuannya adalah membuat monster mengikuti pemain tanpa sekadar berhenti saat menabrak dinding atau terjebak dengan cara yang tidak diinginkan
Gerakan lurus dan wall-sliding
- Pendekatan paling sederhana adalah menarik garis lurus antara monster dan pemain lalu bergerak ke arah tersebut
- Jika hanya memakai cara ini, monster langsung berhenti saat menyentuh dinding
- Dengan menerapkan wall-sliding, saat menabrak dinding monster tidak berhenti, melainkan bergerak mengikuti dinding
- Pada pergerakan pemain, ini adalah teknik yang membuat kontrol di dekat dinding dan sudut terasa lebih responsif, dan dipakai di hampir semua game
- Teknik ini telah digunakan sejak Pac-Man, dan Pac-Man Championship Edition DX+ bahkan menambahkan efek percikan saat pemain melakukan wall-slide
- Jika wall-sliding ditambahkan ke gerakan lurus, monster bisa dijebak pada bentuk medan tertentu
- Beberapa game memakai ini sebagai unsur strategi, misalnya safespotting di Runescape
- Dalam game ini perilaku tersebut tidak diinginkan, sehingga algoritme pathfinding yang sebenarnya mulai dipertimbangkan
Keterbatasan algoritme Dijkstra
- Algoritme Dijkstra mudah dipahami untuk diimplementasikan dan menjamin jalur terpendek
- Masalahnya, ia melakukan terlalu banyak pekerjaan dibanding yang dibutuhkan
- Dari node awal, ia mencari jalur terpendek ke semua node lain dalam graf
- Memang bisa berhenti saat node tujuan ditemukan, tetapi tidak ada cara untuk mengarahkan pencarian secara khusus ke arah tujuan tertentu
- Dalam video game, pemain terus bergerak sehingga tujuan monster berubah setiap frame
- Yang dibutuhkan monster bukan seluruh jalur, melainkan lebih dekat ke keputusan arah gerak saat ini
- Jalur terpendek untuk semua piksel atau tile pada peta memang bisa dipra-hitung, tetapi akan memakan banyak memori
- Pada platform lama atau platform dengan sumber daya terbatas, Dijkstra kurang cocok
Mengapa A* cocok untuk pathfinding game
- A* Search Algorithm menggunakan informasi jarak dari node awal ke tujuan untuk menentukan prioritas pencarian
- Pada langkah pertama, algoritme ini lebih dulu mencoba arah yang mengarah lurus ke tujuan
- Berbeda dari Dijkstra, jika tidak perlu ia tidak akan banyak menghabiskan waktu menjelajah arah sebaliknya
- Jika dinding menghalangi jalur, ia memeriksa node-node di sekitarnya untuk mencoba memutari dinding
- Seperti Dijkstra, ia tidak mengunjungi ulang node yang sudah pernah dilihat, sehingga bahkan bila perlu banyak langkah mundur, pada akhirnya ia tetap bisa menemukan jalur memutar
- Dalam contoh, monster yang memakai A* tidak terjebak di balik dinding
Struktur data graf implisit
- Dalam buku teks, graf biasanya direpresentasikan sebagai daftar node dan adjacency matrix atau adjacency list, tetapi dalam game node bertetangga bisa dibuat lebih fleksibel
- Misalnya, pada layar 256×240 piksel, setiap koordinat piksel bisa dianggap sebagai satu node
- Piksel bertetangga mencakup atas, bawah, kiri, kanan, dan 4 diagonal, jadi total 8 arah
- Bobot gerakan atas-bawah-kiri-kanan adalah 1, sedangkan bobot diagonal adalah √2, yaitu sekitar 1,4
- Daripada membuat adjacency list raksasa terlebih dahulu, node tetangga bisa dibuat saat dibutuhkan hanya untuk node yang benar-benar dikunjungi
- Piksel yang berada di atas dinding atau ditempati sprite lain bukan posisi monster yang valid, jadi bisa dikeluarkan secara dinamis dari adjacency list
- Dengan cara ini, tidak perlu mengecualikan node yang tidak bisa bertetangga secara manual di map editor
Heuristik yang mencerminkan geometri peta
- Beberapa elemen A* bisa disesuaikan langsung dengan struktur geometri peta
-
Ukuran langkah
- Alih-alih memakai piksel sebagai node, dalam game 2D berbasis tile kita bisa memakai tile sebagai node
- Pencarian per tile sangat mengurangi jumlah iterasi yang diperlukan untuk menemukan jalur ke pemain, sehingga pencarian lebih cepat
- Dalam kasus ini, jalurnya bukan lagi daftar gerakan presisi per frame, melainkan lebih dekat ke urutan arah yang harus ditempuh monster
- Monster biasanya tidak bergerak dengan kecepatan 1 tile per frame, jadi bahkan pada jalur berbasis tile, informasi yang benar-benar dibutuhkan adalah arah yang dapat membawanya mencapai pemain
- Jalur berbasis piksel pun memiliki sifat serupa, karena monster juga belum tentu bergerak 1 piksel per frame atau dalam satuan piksel bulat
-
Kedalaman iterasi
- Dalam A*, ketika sebuah node keluar dari priority queue, node itu adalah langkah terakhir dari jalur terbaik yang diketahui sejauh ini
- Jika algoritme dihentikan pada jumlah iterasi tetap, kita memperoleh perkiraan jalur terbaik saat ini menuju jalur terpendek ke tujuan
- Artinya, bahkan tanpa menjalankan algoritme sampai selesai, kita tetap bisa mendapatkan arah gerak yang masuk akal
- Kedalaman iterasi maksimum harus disetel sesuai geometri level
- Jika terlalu dangkal, monster masih bisa terjebak di balik dinding
- Dalam contoh, pada kedalaman tetap 30 tile, monster bisa terjebak dan gagal maju tergantung posisi pemain
- Karena A* dihitung ulang setiap frame, loop bisa muncul
- Pada frame pertama saat mencapai dinding, hasilnya mengatakan harus bergerak ke bawah
- Pada frame berikutnya, hasilnya mengatakan harus bergerak ke atas
- Pengulangan ini membuat monster terjebak dalam loop
- Jika pemain masuk ke dalam jangkauan pencarian monster, jalur yang benar bisa ditemukan
- Pada kedalaman tetap
1, gejala ini muncul lebih ekstrem, dan monster terus kembali ke piksel dengan jarak Euclidean terpendek ke pemain
Kompromi dengan pra-perhitungan
- Jika ingin lebih canggih, kita bisa pra-menghitung kedalaman maksimum yang dibutuhkan A* untuk menemukan jalur dari posisi mana pun di peta
- Berbeda dari pra-perhitungan seluruh jalur ala Dijkstra, yang perlu disimpan hanya satu nilai maksimum tersebut
- Dengan nilai kedalaman maksimum itu, A* bisa menemukan jalur yang valid secara real-time
1 komentar
Komentar Hacker News
Trik yang pernah dipakai untuk A* di MMO produksi: 1) Dengan memakai graf hierarkis seperti tingkat kota, antar-ruangan di dalam bangunan, dan di dalam ruangan, pencarian dari sebuah titik di kota, bangunan, atau ruangan mana pun ke titik lain bisa dilakukan dalam sebagian kecil milidetik
2) Jika metadata pencarian A* saat ini disimpan langsung di node graf, tidak perlu mempertahankan associative array terpisah
3) Jangan ikuti rute hasilnya mentah-mentah; lebih baik gunakan sebagai input untuk perilaku steering yang mencoba memotong tikungan menuju node rute berikutnya bila memungkinkan. Jika rutenya menuju karakter lain, buat karakter target menjatuhkan “remah roti”, lalu tambahkan ke rute ketika posisi baru tidak bisa dicapai dengan gerak lurus dari node terakhir rute
2b) Ini dikompresi menjadi bitmask 16-bit. Delapan potongan 2-bit, yaitu 8 arah, dan disimpan di hash table
2c) Tiap potongan bit memiliki empat status: FULL_BLOCK(dinding), HARD_BLOCK(objek besar yang membuat tile tidak bisa dilewati dari arah mana pun), SOFT_BLOCK(objek kecil yang menghalangi lewat di salah satu sudut), NO_BLOCK(tile kosong atau tile dengan objek yang sangat kecil)
Dengan begitu, ketika unit di dalam bangunan mencari rute, tidak perlu memeriksa rintangan di setiap tile. Selama objeknya tidak besar dan orientasi rotasinya tidak menutup sudut masuk dan keluar, tile yang berisi objek pun bisa dilewati. Terakhir, agar simulasi tidak rusak seperti saat pemain lupa menempatkan pintu, agen juga dibuat bisa menembus dinding
https://store.steampowered.com/app/2287430/Metropolis_1998/
Selama karakter berada di dalam “gelembung” semacam ini, pemeriksaan collision dengan dunia bisa dilewati sepenuhnya
Saat kuliah saya tidak paham kenapa A* begitu sulit di RTS, tetapi setelah melihat penjelasan bahwa agar unit tidak saling menembus, semua benda bergerak harus terus-menerus menghindari semua unit lain dan mencari ulang rute, saya jadi makin menghormati Command & Conquer
Secara pribadi saya akan menghindarinya kecuali ada alasan yang sangat kuat
Saya banyak memikirkan pencarian rute cepat untuk mempercepat AI Quoridor yang dibuat dengan Scala, dan trik yang saya pelajari adalah sebagai berikut
MPAA(multi-path adaptive A*) bagus ketika rintangan ditambahkan dan area yang sama perlu dicari ulang berkali-kali. Hasil pencarian sebelumnya bisa dimasukkan untuk mempercepat pencarian rute
JPS(jump point search) menarik secara teoretis karena bisa sangat mengurangi jumlah “node” yang perlu dipertimbangkan, tetapi overhead untuk menemukan jump point menjadi besar sehingga tidak ada peningkatan kecepatan nyata. Mungkin ada cara menggabungkan ide MPAA dan JPS, tetapi saat mengutak-atik algoritma secara kreatif, detail konseptual kecil bisa mudah menjebak. Misalnya, jika memakai
>saat yang dibutuhkan adalah>=, dalam situasi tertentu rute terpendek yang sebenarnya bisa tidak terjaminUntuk menyimpan node terbuka, alih-alih heap yang benar, jika nilai prioritas maksimum berupa bilangan bulat yang relatif kecil, bucket priority queue juga layak dipertimbangkan. Karena array internal diindeks berdasarkan prioritas, penyisipan dan pengambilan menjadi cukup cepat
Quoridor dimainkan di grid 9x9, dan pencarian rute berulang sangat penting untuk menilai seberapa dekat pemain ke tujuan serta apakah tujuan masih bisa dicapai. Untuk menilai langkah yang mungkin dari posisi tertentu, harus diperiksa bahwa semua langkah tidak membuat tujuan mustahil dicapai. Saya berencana merilisnya dalam beberapa bulan, dan akan menyertakan setidaknya 3 “engine” pengambil keputusan: mtdf(varian minimax), MCTS(versi paralel dengan beberapa trik), dan hibrida yang mencampurkan catboost
Bagusnya, ini bisa dipakai sebagai lookup table untuk fungsi heuristik, menggantikan jarak garis lurus biasa. Misalnya, pada awal tiap giliran, tabel ini bisa diinisialisasi dengan algoritma Floyd-Warshall sambil memperhitungkan dinding yang sudah ditempatkan. Pada masalah serupa, teknik ini membuat A* jauh lebih cepat dan sangat sederhana. Namun itu A* murni tanpa MPAA atau JPS
Bertahun-tahun lalu saya menambahkan fitur ke implementasi JPS PathFinding.js untuk memvisualisasikan pencarian rekursif yang menemukan jump node. Demo online-nya ada di sini: https://qiao.github.io/PathFinding.js/visual/
Jika ada lebih dari satu musuh, bisa jadi lebih menguntungkan menjalankan Dijkstra sekali saja dari sudut pandang pemain, lalu membuat tiap monster mengambil rute optimal menuju pemain
Biaya komputasi menjadi lebih mudah diprediksi ketika jumlah monster berubah
Masalah kedalaman yang terlalu kecil pada animasi terakhir tampak seperti perilaku yang menarik. Monster terlihat seolah-olah “menunggu untuk melihat kamu akan pergi ke arah mana”
Kalau pura-pura pergi ke satu sisi lalu berbalik arah, bukankah itu bisa mengecohnya? Untungnya manusia cukup toleran terhadap hal seperti ini, dan tampaknya memodelkan apa pun seolah-olah punya kecerdasan
Pada dasarnya, musuh cukup dibuat memperbarui jalurnya hanya setelah jeda singkat, bukan di setiap frame. Dengan begitu, karena “inersia”, ia akan mengikuti jalur lama, sehingga pemain bisa mengecohnya
Sebagai pemanfaatan A* yang menarik dalam konteks game, ada seorang programmer yang harus membuat lawan komputer untuk sebuah game awal 2000-an
Ia mengabstraksikan pilihan-pilihan yang dimiliki AI dalam game, lalu membuatnya mencari jarak terdekat di graf itu dengan A*. Yang keren adalah ini bukan penggunaan tradisional untuk pathfinding dunia, melainkan mencari jalur di atas representasi pilihan yang bisa dilakukan komputer, sehingga jalur terpendek merepresentasikan strategi terbaik yang mungkin
0 - https://www.gamedeveloper.com/design/building-the-ai-of-f-e-...
1 - https://web.archive.org/web/20230804100329/https://alumni.me...
Ada juga referensi (bukan milik saya): https://github.com/agoose77/goap-resources
Manusia tampaknya menganggap dirinya dan manusia lain menggunakan pola pikir yang mirip serta kedalaman berpikir yang serupa bahkan untuk aktivitas yang sama sekali berbeda, seperti perencanaan rute, evaluasi risiko/imbalan, atau merencanakan acara 6 bulan lagi. Jika berbagai “ruang pencarian” bisa dienkode sebagai graf yang cocok untuk algoritma umum, maka saat pemain tenggelam dalam permainan, AI menjadi masuk akal untuk terlihat penuh pertimbangan dan nyaris seperti sosok berkepribadian
Saat belajar A* di universitas, pada waktu yang sama saya mengalami masalah aneh itu di server Minecraft bersama
Server sangat tersendat, jadi setelah ditelusuri, ternyata para zombie terjebak dalam loop mencari jalan untuk masuk ke desa yang sepenuhnya diblokir oleh pagar besar. Artinya implementasi saat itu naif dan tidak pernah menyerah
Saya ingat ada laporan bug yang menjelaskan cukup detail cara memperbaikinya
Ini bisa berdampak sangat terlihat pada fps, terutama ketika banyak hewan semuanya mencoba melewati pintu masuk yang tidak dapat dilewati. Tentu saja, kalau dilihat sebagai perilaku kucing yang sangat keras kepala menuntut melewati pintu tertutup, ini juga bisa dibilang sangat realistis. Akan lebih realistis lagi kalau begitu pintunya dibukakan, kucing itu langsung berubah pikiran dan kehilangan minat untuk lewat!
Anda mungkin tertarik pada makalah tentang sistem multi-agen yang menggunakan A* di medan yang tidak dikenal: https://www.researchgate.net/publication/333917261_Implement...
Artikel ini dan thread HN-nya berisi trik-trik bagus. Saya belum banyak memakai A*, tetapi saya tahu ada library Haskell yang cukup bagus: https://hackage.haskell.org/package/astar-monad-0.3.0.0#read...