Kinerja lambat pada implementasi A * dalam game menara pertahanan

9

Saya membuat game Tower Defense di Flash tanpa jalur yang telah ditentukan.

Meskipun kisi saya adalah 40x40 (kecil?), A * berjuang ketika menghitung ulang setiap waktu. Jadi saya membuat modifikasi sendiri untuk memudahkan perhitungan ulang dan jumlah sel yang disentuh turun menjadi sekitar 900 (ketika memodifikasi di dekat root). Itu masih membeku untuk waktu yang sangat singkat, tetapi dapat terdeteksi, ketika menara baru ditempatkan.

Apakah ini masalah implementasi, atau 40x40 terlalu banyak?

Edit:

Struktur kode saya:

  • Semua data disimpan dalam array sel 2d.
  • Setiap sel berisi induknya dalam arah jalur (1-8 searah jarum jam) dan larik dikodekan bitwise dari anak-anaknya di jalur (setiap bit mewakili anak).
  • Pencarian dilakukan oleh A * dengan perkiraan jarak euclidian.
flash algorithm path-finding tower-defense Dani
sumber
Anda harus lebih spesifik di sini. Kami tidak tahu seperti apa kode Anda, bagaimana terstruktur, dll, jadi kami tidak dapat menarik kesimpulan tentang apa yang membuatnya lambat.
Sean James
1
Ketika saya menerapkan A * untuk terakhir kalinya saya ingat itu berjalan melalui kotak 64x64 paling banyak 1ms. Jadi ya, tampaknya ada masalah dengan implementasi Anda. Saya sarankan memposting kode Anda atau intinya sehingga kami dapat membantu Anda lebih lanjut.
Marc Müller
Lihat hasil edit yang saya tambahkan
Dani
1
Jika 40x40 terlalu lambat, kemungkinan besar Anda melakukan sesuatu yang sangat salah. Entah memposting kode Anda atau profil itu. Atau, skalakan dan lihat apa yang terjadi - jika kisi 80x80 membutuhkan waktu lebih dari empat kali, Anda memiliki sesuatu yang sangat rusak di sana.
ZorbaTHut
Bisakah judulnya sedikit lebih informatif?
Tenpn

Jawaban:

4

Saya tidak bisa berkomentar, tetapi profil pertama di Flex, yang lainnya adalah dugaan.

Jonathan Fischoff
sumber
Bagaimana saya bisa memproyeksikan proyek flash dengan fleksibel?
Dani
Iya dan tidak. Saya tidak berpikir Anda memuat proyek flash secara langsung. Saya pikir Anda mungkin dapat membuat profil swf tanpa sumber dan masih mendapatkan info tingkat fungsi. Saya akan melakukan pencarian google untuk "profil proyek flash dengan fleksibel" atau sejenisnya. Saya lakukan dan mendapatkan ini: flexblog.edchipman.ca/… yang terlihat menjanjikan.
Jonathan Fischoff
Terima kasih, benar-benar membantu saya menemukan bagian yang bermasalah (tidak ada dalam algoritme, lihat komentar pada pertanyaan)
Dani
13

Saya berasumsi bahwa TD adalah 'Tower Defense'

Saya pikir A * agak berlebihan untuk ini.

Di awal permainan, banjir memenuhi area permainan dari titik keluar untuk membuat peta pergerakan:

 |---------|
 |5|4|3|3|3|
 |5|4|3|2|2|
->5|4|3|2|1->
 |5|4|3|2|2|
 |5|4|3|3|3|
 |---------|

dan pergerakan selalu menuju kotak dengan nilai yang lebih rendah.

Ketika pemain menempatkan menara, perbarui masing-masing dari delapan kotak yang berdekatan: untuk setiap kotak, tetapkan nilai gerakannya menjadi satu lebih dari nilai berdekatan terendah. Jika nilainya berubah, ulangi proses yang berpusat pada kotak yang diperbarui. Kemudian, untuk memeriksa bahwa rute ke pintu keluar tidak diblokir, pastikan semua kotak berdekatan dengan kuadrat dengan nilai yang lebih rendah.

Saat pemain memindahkan menara, atur nilai gerakan ke satu lebih dari kotak terdekat yang berdekatan dan ulangi proses di atas.

Pendekatan yang lebih sederhana adalah dengan mengisi ulang banjir.

Mendesis
sumber
6
Melakukan ulang pengisian banjir lebih mahal daripada melakukan A * untuk sejumlah kecil unit - kira-kira, panjang papan - setidaknya dalam istilah algoritmik (dan karena ini adalah Flash, konstanta non-algoritmik seperti tata letak memori mungkin bisa ' t digunakan sangat efektif). Namun, ini adalah model yang sangat bagus untuk banyak unit komunikasi, dan disebut difusi kolaboratif - scalablegamedesign.cs.colorado.edu/wiki/Collaborative_Diffusion .
@ Jo Wreschnig: wow tautan yang bagus. Saya telah menggunakan teknik itu sebelumnya tetapi tidak pernah tahu apa namanya. Terima kasih.
Tenpn
@ Jo, asalkan ada setidaknya beberapa hambatan di peta saya tidak berpikir ini akan lebih tidak efisien daripada memanggil A *. Artinya, saya percaya hanya untuk peta bebas terbuka lebar, hampir penghalang dengan beberapa unit mungkin lebih buruk.
edA-qa mort-ora-y
@EDA: Menurut definisi, pengisian banjir pada akhirnya harus menyentuh setiap titik yang dapat diakses di peta; A * memberikan batas atas yang teruji untuk berapa banyak titik yang harus disentuh, yang paling banyak di setiap titik yang dapat diakses di peta dan biasanya jauh lebih sedikit. Isi banjir adalah algoritma yang lebih sederhana untuk mengoptimalkan hal-hal seperti tata letak memori, tetapi seperti yang saya katakan, di Flash yang mungkin tidak masalah.
@ Jo, itulah yang saya maksudkan adalah bahwa bahkan hanya dengan beberapa menara A * kemungkinan akan menyentuh hampir semua ruang. Tetapi untuk N monster itu hanya perlu melebihi total_squares / N untuk menjadi kurang efisien daripada mengisi banjir.
edA-qa mort-ora-y
2

Aneh, saya pikir saya membalas ini, tetapi jawabannya sepertinya hilang. Buat algoritma pencarian Anda sedemikian rupa sehingga dapat diperbarui dalam beberapa langkah, sehingga ketika Anda menempatkan menara dan memainkan animasi, Anda dapat melakukan sedikit setiap frame dan Anda akan memiliki tempat antara setengah detik dan satu detik untuk memperbarui Anda A * tanpa jeda yang nyata. Ini latensi - Jika Anda tidak dapat mempercepatnya, temukan cara untuk menyembunyikannya. Bermain animasi sambil menempatkan menara adalah hal yang wajar untuk sebuah game dan merupakan tempat yang bagus untuk menyembunyikannya.

Kaj
sumber
Ini adalah ide yang baik secara umum, tetapi buruk untuk pertanyaan khusus ini. A * pada grid kecil seperti itu harus hampir instan, tidak memakan banyak waktu.
davr
Cukup adil. Itu satu-satunya jawaban yang bisa saya berikan yang akan memecahkan masalah tanpa mengetahui detail implementasi yang akan menyebabkan perlambatan.
Kaj
0

Sebagai permulaan Anda bisa mengubah array Anda menjadi vektor - seharusnya memberi Anda beberapa peningkatan kecepatan. Poskan kode dan kami mungkin dapat menyarankan lebih banyak optimisasi.

Iain
sumber
0

Saya kira perlambatan Anda adalah karena Anda menghitung jalur untuk semua karakter secara bersamaan. Menghitung jalur untuk satu karakter adalah cepat tetapi jika ada dua lusin karakter dalam adegan maka itu dapat menghalangi.

Alih-alih, Anda harus menyebar beban beberapa frame. Singkirkan pembaruan AI Anda sehingga karakter yang berbeda memperbarui jalurnya pada bingkai yang berbeda. Akan sangat terlihat jika karakter tidak bereaksi sampai sedetik kemudian, tetapi hanya satu frame tidak akan menyebabkan reaksi buruk.

jhocking
sumber
Ini dijawab hampir setahun yang lalu, dan hanya terbentur karena pekerjaan penyuntingan Grace. (Itu tidak ada hubungannya dengan terlalu banyak karakter.)
Terima kasih telah memberi tahu saya. Saya tidak melihat tanggalnya.
jhocking