Saya menemukan banyak referensi tentang AI hantu di Pacman, tetapi tidak ada yang menyebutkan bagaimana mata menemukan jalan kembali ke lubang hantu pusat setelah hantu dimakan oleh Pacman.
Dalam implementasi saya, saya menerapkan solusi sederhana namun mengerikan. Saya hanya kode keras di setiap sudut arah mana yang harus diambil.
Apakah ada solusi yang lebih baik / atau yang terbaik? Mungkin yang generik yang bekerja dengan desain level yang berbeda?
artificial-intelligence
path-finding
heuristics
pacman
RoflcoptrException
sumber
sumber
Jawaban:
Sebenarnya, saya akan mengatakan pendekatan Anda adalah solusi yang cukup luar biasa, dengan biaya waktu hampir nol-lari dibandingkan dengan segala jenis pathfinding.
Jika Anda membutuhkannya untuk menggeneralisasi ke peta yang berubah-ubah, Anda bisa menggunakan algoritme pathfinding apa pun - misalnya pencarian pertama sangat mudah diimplementasikan, misalnya - dan menggunakannya untuk menghitung arah mana yang akan dikodekan di setiap sudut, sebelum game dijalankan.
EDIT (11 Agustus 2010): Saya baru saja dirujuk ke halaman yang sangat rinci tentang sistem Pacman: The Pac-Man Dossier , dan karena saya memiliki jawaban yang diterima di sini, saya merasa saya harus memperbaruinya. Artikel itu tampaknya tidak mencakup tindakan kembali ke rumah monster secara eksplisit tetapi menyatakan bahwa penelusuran langsung di Pac-Man adalah kasus berikut ini:
sumber
Saya telah memecahkan masalah ini untuk level umum dengan cara itu: Sebelum level dimulai, saya melakukan semacam "mengisi banjir" dari lubang monster; setiap ubin labirin yang bukan dinding mendapat nomor yang mengatakan seberapa jauh jaraknya dari lubang. Jadi ketika mata berada pada ubin dengan jarak 68, mereka melihat ubin tetangga yang memiliki jarak 67; itulah cara untuk pergi.
sumber
Untuk alternatif dari algoritme pathfinding yang lebih tradisional, Anda bisa melihat pada pola Anti-objek Pac-Man Scent (bernama tepat!) .
Anda bisa meredakan aroma lubang-monster di sekitar labirin saat startup dan membiarkannya mengikutinya pulang.
Setelah bau diatur, biaya runtime sangat rendah.
Edit: sayangnya artikel wikipedia telah dihapus, jadi WayBack Machine untuk menyelamatkan ...
sumber
Anda harus melihat algoritma pathfindings, seperti Algoritma Dijsktra atau algoritma A * . Inilah masalah Anda: masalah grafik / jalur.
sumber
Setiap solusi sederhana yang berfungsi dapat dipertahankan, dapat diandalkan, dan berkinerja cukup baik adalah solusi yang baik. Kedengarannya bagi saya seperti Anda telah menemukan solusi yang baik ...
Solusi pencarian jalan kemungkinan lebih rumit daripada solusi Anda saat ini, dan karenanya lebih mungkin membutuhkan debugging. Mungkin juga akan lebih lambat.
IMO, jika tidak rusak, jangan memperbaikinya.
EDIT
IMO, jika labirin sudah diperbaiki maka solusi Anda saat ini adalah kode yang baik / elegan. Jangan membuat kesalahan dengan menyamakan "baik" atau "elegan" dengan "pintar". Kode sederhana juga bisa "bagus" dan "elegan".
Jika Anda memiliki tingkat labirin yang dapat dikonfigurasi, maka mungkin Anda harus melakukan pathfinding saja saat Anda awalnya mengkonfigurasi labirin. Paling sederhana adalah membuat desainer labirin melakukannya dengan tangan. Saya hanya akan repot mengotomatiskan ini jika Anda memiliki labirin bazillion ... atau pengguna dapat mendesainnya.
(Selain itu: jika rute dikonfigurasikan dengan tangan, perancang labirin dapat membuat level lebih menarik dengan menggunakan rute suboptimal ...)
sumber
Dalam Pacman asli the Ghost menemukan pemakan pil kuning dengan "bau" dia akan meninggalkan jejak di peta, hantu akan berkeliaran secara acak sampai mereka menemukan baunya, maka mereka hanya akan mengikuti jalur bau yang mengarahkan mereka langsung ke pemain. Setiap kali Pacman pindah, "nilai bau" akan berkurang 1.
Sekarang, cara sederhana untuk membalik seluruh proses adalah dengan memiliki "piramida bau hantu", yang memiliki titik tertinggi di tengah peta, maka hantu hanya bergerak ke arah bau ini.
sumber
Dengan asumsi Anda sudah memiliki logika yang diperlukan untuk mengejar pacman mengapa tidak menggunakannya kembali? Ubah saja targetnya. Sepertinya itu akan menjadi jauh lebih sedikit pekerjaan daripada mencoba membuat rutinitas baru menggunakan logika yang sama persis.
sumber
Ini masalah merintih jalan. Untuk algoritme populer, lihat http://wiki.gamedev.net/index.php/A* .
sumber
Bagaimana setiap kotak memiliki nilai jarak ke pusat? Dengan cara ini untuk setiap kotak Anda bisa mendapatkan nilai kotak tetangga langsung di semua arah yang mungkin. Anda memilih kotak dengan nilai terendah dan pindah ke kotak itu.
Nilai akan dihitung sebelumnya menggunakan algoritma yang tersedia.
sumber
Ini adalah sumber terbaik yang bisa saya temukan tentang cara kerjanya.
http://gameai.com/wiki/index.php?title=Pac-Man#Respawn Ketika hantu terbunuh, mata tanpa tubuh mereka kembali ke lokasi awal mereka. Ini hanya dilakukan dengan mengatur ubin target hantu ke lokasi itu. Navigasi menggunakan aturan yang sama.
Ini sebenarnya masuk akal. Mungkin bukan yang paling efisien di dunia tetapi cara yang cukup bagus untuk tidak perlu khawatir tentang keadaan lain atau apa pun di sepanjang garis itu Anda hanya mengubah target.
Catatan: Saya tidak menyadari betapa hebatnya para programmer pac-man itu pada dasarnya mereka membuat seluruh sistem pesan dalam ruang yang sangat kecil dengan memori yang sangat terbatas ... itu luar biasa.
sumber
Saya pikir solusi Anda tepat untuk masalahnya, lebih sederhana dari itu, adalah membuat versi baru lebih "realistis" di mana mata hantu bisa menembus tembok =)
sumber
Berikut ini adalah analog dan kodesemu untuk gagasan mengisi banjir ammoQ.
Idenya adalah bahwa ini adalah pencarian pertama yang luas, jadi setiap kali Anda menemukan kotak baru yang berdekatan, jalur terbaik adalah melalui p. Ini O (N) saya percaya.
sumber
Saya tidak tahu banyak tentang bagaimana Anda menerapkan permainan Anda, tetapi, Anda bisa melakukan hal berikut:
Beberapa pseudocode:
sumber
saran dtb23 tentang hanya memilih arah acak di setiap sudut, dan akhirnya Anda akan menemukan lubang monster terdengar sangat tidak efisien.
Namun Anda dapat menggunakan algoritme kembali ke rumah yang tidak efisien untuk membuat game lebih menyenangkan dengan memperkenalkan lebih banyak variasi dalam kesulitan game. Anda akan melakukan ini dengan menerapkan salah satu pendekatan di atas seperti titik arah Anda atau mengisi banjir, tetapi melakukannya secara non-deterministik. Jadi di setiap sudut, Anda bisa menghasilkan angka acak untuk memutuskan apakah akan mengambil cara optimal, atau arah acak.
Saat pemain naik level, Anda mengurangi kemungkinan arah acak diambil. Ini akan menambah tuas lain pada tingkat kesulitan keseluruhan selain tingkat kecepatan, kecepatan hantu, jeda makan pil (dll). Anda punya lebih banyak waktu untuk bersantai sementara hantu hanya mata yang tidak berbahaya, tetapi waktu itu menjadi lebih pendek dan lebih pendek saat Anda maju.
sumber
Jawaban singkat, tidak terlalu baik. :) Jika Anda mengubah labirin Pac-man mata tidak akan selalu kembali. Beberapa peretas yang mengalami masalah itu. Jadi itu tergantung pada memiliki labirin kooperatif.
sumber
Saya akan mengusulkan bahwa hantu menyimpan jalan yang telah diambilnya dari lubang ke Pacman. Jadi begitu hantu itu mati, ia bisa mengikuti jalan yang tersimpan ini ke arah sebaliknya.
sumber
Mengetahui bahwa jalur pacman adalah non-acak (yaitu, setiap level spesifik 0-255, bertinta, blinky, pinky, dan clyde akan bekerja dengan jalur yang sama persis untuk level itu).
Saya akan mengambil ini dan kemudian menebak ada beberapa jalur master yang membungkus seluruh labirin sebagai "jalur kembali" bahwa objek bola mata tertunda di mana itu ketika pac man memakan hantu.
sumber
Hantu di pacman mengikuti kurang lebih pola yang dapat diprediksi dalam hal mencoba mencocokkan X atau Y terlebih dahulu sampai tujuannya tercapai. Saya selalu berasumsi bahwa ini persis sama dengan mata yang menemukan jalan pulang.
sumber
Nikmati!
sumber
Pendekatan saya adalah sedikit memori intensif (dari perspektif era Pacman), tetapi Anda hanya perlu menghitung sekali dan itu bekerja untuk setiap desain level (termasuk melompat).
Label Node Sekali
Saat Anda pertama kali memuat level, beri label semua node lair monster 0 (mewakili jarak dari lair). Lanjutkan ke pelabelan yang terhubung node 1, node terhubung ke mereka 2, dan seterusnya, sampai semua node diberi label. (catatan: ini bahkan berfungsi jika sarang memiliki beberapa pintu masuk)
Saya berasumsi Anda sudah memiliki objek yang mewakili setiap node dan koneksi ke tetangga mereka. Kode palsu mungkin terlihat seperti ini:
Mata Pindah ke Tetangga dengan Label Jarak Terendah
Setelah semua node diberi label, perutean mata adalah sepele ... pilih saja node tetangga dengan label jarak terendah (catatan: jika beberapa node memiliki jarak yang sama, tidak masalah yang dipilih). Kode palsu:
Contoh Berlabel Sepenuhnya
sumber
Untuk permainan PacMan saya, saya membuat
shortest multiple path home
algoritma yang " " berfungsi untuk labirin apa pun yang saya sediakan (sesuai aturan saya). Ini juga berfungsi di seluruh terowongan mereka.Ketika level dimuat, semua
path home data in every crossroad
kosong (default) dan begitu hantu mulai menjelajahi labirin, merekacrossroad path home information
terus diperbarui setiap kali mereka berjalan ke perempatan "baru" atau dari jalur yang berbeda tersandung lagi pada perempatan yang dikenal.sumber
Pac-man asli tidak menggunakan pencarian jalan atau AI mewah. Itu hanya membuat gamer percaya ada kedalaman lebih dari itu sebenarnya, tetapi sebenarnya itu acak. Seperti yang dinyatakan dalam Artificial Intelligence for Games / Ian Millington, John Funge.
Tidak yakin apakah itu benar atau tidak, tetapi itu sangat masuk akal bagi saya. Jujur, saya tidak melihat perilaku yang dibicarakan orang. Merah / Blinky untuk mantan tidak mengikuti pemain setiap saat, seperti yang mereka katakan. Sepertinya tidak ada yang secara konsisten mengikuti pemain, dengan sengaja. Kemungkinan mereka akan mengikuti Anda terlihat acak bagi saya. Dan sangat menggoda untuk melihat perilaku secara acak, terutama ketika peluang untuk dikejar sangat tinggi, dengan 4 musuh dan opsi belok yang sangat terbatas, dalam ruang kecil. Setidaknya dalam implementasi awalnya, gim ini sangat sederhana. Lihatlah bukunya, itu ada di salah satu bab pertama.
sumber