Pacman: bagaimana mata menemukan jalan kembali ke lubang monster?

321

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?

RoflcoptrException
sumber
11
Apakah Anda yakin hardcoding di sudut cukup baik? Ini tidak menjamin rute terbaik. Bayangkan hantu itu menghadapi jalan sempit yang panjang. Dengan algoritme Anda, ia harus menelusuri seluruh bagian itu, mencapai sudut, dan kemudian mengambil rute tercepat. Jika Anda membuat hard-kode pada setiap kotak ke arah mana harus pergi, dia mungkin tahu untuk berbalik dulu.
Mark Peters
3
@ Mark, tergantung pada definisi Anda di sudut. Jika ini adalah koneksi T walaupun Anda langsung berada di baris teratas, tidak apa-apa.
Thorbjørn Ravn Andersen
1
@ Thorbjørn: Saya bahkan tidak berbicara tentang persimpangan. Lihatlah papan ini: en.wikipedia.org/wiki/File:Pac-man.png . Jika hantu itu bergerak ke kanan dan diposisikan di titik kedua dari kiri bawah, itu tidak akan bertemu persimpangan untuk sementara waktu. Itu akan menyebabkannya melakukan perjalanan 10 kotak lebih jauh daripada jika itu telah berbalik ke belakang (kiri) dan mengambil jalan terpendek.
Mark Peters
6
solusi Anda menggunakan titik jalan (atau remah roti), dan saya pikir itu teknik yang umum digunakan untuk mempercepat algoritma pencarian jalur.
Nick Dandoulakis
1
terima kasih atas semua jawabannya! Saya hanya berpegang teguh pada solusi saya sebelumnya dan mengkodekan arah di setiap sudut. Untuk melakukannya secara umum, diperlukan leveldesigner / file level yang mendefinisikan informasi ini dalam definisi level.
RoflcoptrException

Jawaban:

152

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:

  • terus bergerak menuju persimpangan berikutnya (meskipun ini pada dasarnya adalah kasus khusus 'ketika diberi pilihan, pilih arah yang tidak melibatkan membalikkan arah Anda, seperti yang terlihat pada langkah berikutnya);
  • di persimpangan, lihat kotak keluar yang berdekatan, kecuali yang baru saja Anda datangi;
  • memilih satu yang terdekat dengan tujuan. Jika lebih dari satu sama-sama dekat dengan tujuan, pilih arah yang valid pertama dalam urutan ini: atas, kiri, bawah, kanan.
Kylotan
sumber
16
Saya pikir dia berarti Anda bisa menghitungnya saat runtime (ketika level dimuat tetapi sebelum Anda mulai memainkannya) tetapi hanya sekali. Itu tidak sulit untuk dipertahankan.
Mark Peters
3
Ya, atau jika ada alat untuk membuat peta, sebagai bagian dari itu.
Kylotan
6
Tidak ada yang salah dengan mengkomputasi jalur pengembalian. Anda memperdagangkan penyimpanan (jalur) untuk kinerja runtime.
Steve Kuo
6
Terima kasih. Saya pikir saya akan tetap dengan solusi ini. Adakah yang tahu bagaimana hal itu dilakukan dalam Pacman asli?
RoflcoptrException
4
Tidak, saya tidak. Pertanyaan aslinya menggunakan istilah itu tetapi tidak secara hukum mengikat.
Kylotan
85

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.

Erich Kitzmueller
sumber
15
Iya. Floodfill sangat baik untuk merintis jalan dalam situasi apa pun di mana dunia tidak terlalu besar untuk membuatnya layak. Saya akan berpikir itu bisa digunakan bahkan di dunia besar dengan memaksakan kisi-kisi kasar yang konektivitasnya sudah dihitung sebelumnya. Ini akan membuat hal-hal sedikit keluar dari jalan tapi itu akan lebih baik daripada kemacetan lalu lintas yang pernah saya lihat dalam permainan seperti itu.
Loren Pechtel
1
Untuk menghemat ruang (untuk dunia yang lebih besar, atau sistem terbatas), Anda bisa menyimpan arah untuk melakukan perjalanan di setiap persimpangan, daripada menyimpan nilai untuk setiap ubin. Ini pada dasarnya yang disarankan OP.
BlueRaja - Danny Pflughoeft
BlueRaja: Tentu, tapi ini lebih kompleks untuk melakukan itu dan hasilnya tidak optimal - hantu dimakan antara dua persimpangan, jadi dia mungkin akan lari ke arah yang salah untuk beberapa waktu. Solusi saya bekerja dengan baik di en.wikipedia.org/wiki/HP_200LX jadi berapa banyak lagi yang bisa didapat?
Erich Kitzmueller
5
(Saya terlambat ...) Ya banjir-mengisi baik, namun Anda sebenarnya tidak membutuhkan angka penuh, hanya arah (dua bit) di setiap kotak untuk menunjuk ke kotak berikutnya untuk digunakan.
Matthieu M.
Matthieu: Ya, itu mungkin optimasi.
Erich Kitzmueller
42

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 ...

Dan Vinton
sumber
2
ini akan menjadi jawaban saya. Ini sama dengan ammoQ pada dasarnya, tapi saya selalu ingat tentang aroma pacman :)
Luke Schafer
Sepertinya artikel wikipedia sudah mati / dihapus. Hasil teratas Google adalah utas ini, tetapi saya pikir ini sudah dekat.
David
2
Saya sempat bingung sebentar tapi kemudian langsung mengerti apa yang dimaksud dengan "aroma". Ini cara yang bagus untuk menggambarkan hal-hal bidang skalar ini!
Steven Lu
18

Anda harus melihat algoritma pathfindings, seperti Algoritma Dijsktra atau algoritma A * . Inilah masalah Anda: masalah grafik / jalur.

Clement Herreman
sumber
18

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 ...)

Stephen C
sumber
Ya itu berfungsi. Namun saya ingin menulis kode yang baik dan bukan hanya kode. Dan juga saya menambahkan kalimat terakhir dalam pertanyaan saya, jadi jika memungkinkan algoritma tidak hanya untuk satu labirin tetapi untuk beberapa.
RoflcoptrException
labirin juga dapat dihasilkan (saya memiliki algoritma yang menghasilkan labirin pacman yang terlihat bagus), jadi sedikit otomatisasi adalah cara untuk pergi
Erich Kitzmueller
"... atau pengguna dapat mendesainnya." Dalam hal ini, Anda DO memiliki labirin bazillion.
phuzion
@ phuzion - Saya sadar akan hal itu. Namun, ada perbedaan antara kedua kasus tersebut. Jika OP membuat labirin bazzilion, maka itu adalah ketidaknyamanan untuk membuat routing dengan tangan. Jika ini adalah pengguna akhir ... itu berarti OP harus menulis dokumentasi, melakukan pemecahan masalah tanpa akhir dari labirin pengguna akhir, mengajukan keluhan tanpa akhir tentang betapa tidak ramahnya, dan sebagainya. Dengan kata lain alasan untuk menerapkan pembuatan rute otomatis berbeda .
Stephen C
14

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.

Ivo Wetzel
sumber
Saya sangat suka pendekatan ini dan saya juga akan mencoba yang ini
RoflcoptrException
5
Ini tidak benar; jika mereka semua mengikuti algoritma ini, mereka akhirnya akan mengejar dia satu file. Perilaku setiap hantu berbeda; Anda dapat menemukan lebih banyak info tentang artikel Wikipedia.
pembagi
5

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.

John Gardeniers
sumber
ya saya punya logika untuk mengejar pacman sudah diimplementasikan, tetapi saya juga tidak senang dengan itu;)
RoflcoptrException
Dalam pengalaman saya (saya suka menulis versi pacman hanya untuk bersenang-senang), melakukan hal itu dapat menyebabkan mata terjebak di luar lubang untuk waktu yang lama. Itu karena algoritma pengejaran umumnya berjalan di sepanjang garis "jika pacman ada di utara, pergi ke utara" tetapi labirin bisa berisi "perangkap" di mana mata harus pergi ke selatan terlebih dahulu. Sejak pacman bergerak, hantu itu akan melarikan diri cepat atau lambat, tetapi lubangnya adalah target tetap. (Catatan: Saya sedang berbicara tentang labirin yang dihasilkan)
Erich Kitzmueller
3

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.

mvbl fst
sumber
Saya akan menyarankan ini. Isi banjir mulai dari 'lubang monster'. Saya pikir jawaban Anda akan mendapat manfaat dari gambar.
AjahnCharles
3

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.

Midpipps
sumber
2

Saya pikir solusi Anda tepat untuk masalahnya, lebih sederhana dari itu, adalah membuat versi baru lebih "realistis" di mana mata hantu bisa menembus tembok =)

Hernán Eche
sumber
2
Untuk menambahkan lebih banyak realisme, biarkan hantu itu sendiri dapat bergerak menembus dinding: D
Thomas Eding
3
Itu adalah dinding buram hantu, tetapi hantu orde kedua, (hantu hantu) lebih transparan. (Anda bisa menemukan banyak panduan pengguna dengan fitur bug yang diubah)
Hernán Eche
1
+1 untuk "hantu orde kedua" - oh ya, turunan dari hantu pastilah melampaui objek orde pertama seperti dinding ... :)
Assad Ebrahim
2

Berikut ini adalah analog dan kodesemu untuk gagasan mengisi banjir ammoQ.

queue q
enqueue q, ghost_origin
set visited

while q has squares
   p <= dequeue q
   for each square s adjacent to p
      if ( s not in visited ) then
         add s to visited
         s.returndirection <= direction from s to p
         enqueue q, s
      end if
   next
 next

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.

Mark Peters
sumber
2

Saya tidak tahu banyak tentang bagaimana Anda menerapkan permainan Anda, tetapi, Anda bisa melakukan hal berikut:

  1. Tentukan lokasi relatif posisi mata terhadap gerbang. yaitu apakah dibiarkan di atas? Tepat di bawah?
  2. Kemudian gerakkan mata yang berlawanan dengan salah satu dari dua arah (seperti membuatnya bergerak ke kiri jika tepat di gerbang, dan di bawah gerbang) dan periksa apakah ada dan dinding yang menghalangi Anda melakukannya.
  3. Jika ada dinding yang mencegah Anda melakukannya maka buatlah bergerak berlawanan arah (misalnya, jika koordinat mata relatif terhadap pin berada di utara dan saat ini bergerak ke kiri tetapi ada dinding di jalan membuatnya pindah ke selatan.
  4. Ingatlah untuk terus memeriksa setiap kali bergerak untuk terus memeriksa di mana mata relatif terhadap gerbang dan periksa untuk melihat ketika tidak ada koordinat latitudinal. yaitu hanya di atas pintu gerbang.
  5. Dalam hal ini hanya di atas pintu gerbang turun jika ada dinding, bergerak ke kiri atau kanan dan terus melakukan nomor ini 1 - 4 sampai mata berada di ruang tengah.
  6. Saya belum pernah melihat jalan buntu di Pacman kode ini tidak akan menjelaskan jalan buntu.
  7. Juga, saya telah memasukkan solusi ketika mata akan "goyah" di antara dinding yang membentang di tempat asalnya di pseudocode saya.

Beberapa pseudocode:

   x = getRelativeOppositeLatitudinalCoord()
   y
   origX = x
    while(eyesNotInPen())
       x = getRelativeOppositeLatitudinalCoordofGate()
       y = getRelativeOppositeLongitudinalCoordofGate()
       if (getRelativeOppositeLatitudinalCoordofGate() == 0 && move(y) == false/*assume zero is neither left or right of the the gate and false means wall is in the way */)
            while (move(y) == false)
                 move(origX)
                 x = getRelativeOppositeLatitudinalCoordofGate()
        else if (move(x) == false) {
            move(y)
    endWhile

sumber
2

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.

imoatama
sumber
2

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.

dwidel
sumber
2

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.

Fischer Ludrian
sumber
2
jalan itu kemungkinan besar akan terlalu panjang
Ahmad Y. Saleh
Setiap kali Anda mengunjungi kembali sebuah simpul, Anda bisa menghilangkan loop dari sejarah. Itu akan membuatnya sedikit lebih langsung. Mungkin lebih menarik daripada selalu mengikuti jalur langsung yang sama, tetapi cukup sering itu akan mencakup beberapa loop hampir konyol (misalnya 3 sisi persegi).
AjahnCharles
1

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.

Penyamaran
sumber
1

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.

alas tiang
sumber
1
  1. Sebelum permainan dimulai, simpan node (persimpangan) di peta
  2. Ketika monster mati, ambil titik (koordinat) dan temukan simpul terdekat di daftar simpul Anda
  3. Hitung semua jalur mulai dari simpul ke lubang
  4. Ambil jalur terpendek menurut panjangnya
  5. Tambahkan panjang ruang antara titik dan simpul terdekat
  6. Menggambar dan bergerak di jalan setapak

Nikmati!

GingerHead
sumber
1

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:

public void fillMap(List<Node> nodes) { // call passing lairNodes
    int i = 0;

    while(nodes.count > 0) {
        // Label with distance from lair
        nodes.labelAll(i++);

        // Find connected unlabelled nodes
        nodes = nodes
            .flatMap(n -> n.neighbours)
            .filter(!n.isDistanceAssigned());
    }
}

Isi banjir dari sarang

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:

public Node moveEyes(final Node current) {
    return current.neighbours.min((n1, n2) -> n1.distance - n2.distance);
}

Contoh Berlabel Sepenuhnya

Peta lengkap

AjahnCharles
sumber
0

Untuk permainan PacMan saya, saya membuat shortest multiple path homealgoritma 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 crossroadkosong (default) dan begitu hantu mulai menjelajahi labirin, mereka crossroad path home informationterus diperbarui setiap kali mereka berjalan ke perempatan "baru" atau dari jalur yang berbeda tersandung lagi pada perempatan yang dikenal.

iNyuu
sumber
-2

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.

pengguna4664601
sumber
ya, memang menggunakan beberapa AI. Dan ya Blinky mengikuti pacman ketika dia dalam mode pengejaran (beralih dari waktu ke waktu), jadi AI baik-baik saja
Jean-François Fabre