Apakah penelusuran jalan prakomputasi masih relevan?

12

Konteks

Old Lucas Arts (era ScummVM) menunjuk dan mengklik game petualangan grafis menggunakan perintis jalan yang diperhitungkan. Inilah garis besar kasar teknik ini.

Langkah 1

Lantai di setiap kamar dibagi menjadi apa yang mereka sebut "kotak berjalan", yang cukup banyak setara dengan node dalam navigasi mesh, tetapi terbatas pada bentuk trapesium. Misalnya:

 ______ _____ _________ _____
\   A  |  B  |    C    |  D   \
 \_____|     |         |_______\
       |_____|         |
             |_________|

Langkah 2

Algoritma offline (misalnya Dijkstra atau A *) akan menghitung lintasan terpendek antara setiap dan setiap pasangan node, dan menyimpan langkah pertama lintasan dalam matriks 2D, diindeks dalam setiap dimensi dengan simpul awal dan akhir yang digunakan. Misalnya menggunakan kotak jalan di atas:

      ___ ___ ___ ___
     | A | B | C | D | <- Start Node
  ___|___|___|___|___|
 | A | A | A | B | C |  ---
 |___|___|___|___|___|     |
 | B | B | B | B | C |     |
 |___|___|___|___|___|     |-- Next node in shortest path
 | C | B | C | C | C |     |   from Start to End
 |___|___|___|___|___|     | 
 | D | B | C | D | D |  ---
 |___|___|___|___|___| 
   ^
   |
End Node

Seperti yang Anda tebak, kebutuhan memori meningkat dengan cepat seiring dengan meningkatnya jumlah node (N ^ 2). Karena pendek biasanya akan cukup besar untuk menyimpan setiap entri dalam matriks, dengan peta kompleks 300 simpul yang akan menghasilkan penyimpanan tambahan:

300^2 * sizeof(short) = 176 kilobytes

Langkah 3

Di sisi lain, menghitung jalur terpendek antara dua node sangat cepat dan sepele, hanya serangkaian pencarian ke dalam matriks. Sesuatu seperti:

// Find shortest path from Start to End
Path = {Start}
Current = Start
WHILE Current != End
    Current = LookUp[Current, End]
    Path.Add(Current)
ENDWHILE

Menerapkan algoritma sederhana ini untuk menemukan jalur terpendek dari C ke A menghasilkan:

1) Path = { C }, Current = C
2) Path = { C, B }, Current = B
3) Path = { C, B, A }, Current = A, Exit

Pertanyaan

Saya curiga bahwa dengan perangkat keras yang kuat saat ini, ditambah dengan persyaratan memori untuk melakukan ini untuk setiap level, manfaat apa pun yang dimiliki teknik ini sekarang dikalahkan dengan hanya melakukan A * saat runtime.

Saya juga mendengar bahwa saat ini pencarian memori bahkan mungkin lebih lambat daripada perhitungan umum, itulah sebabnya membuat sinus dan cosine look up tables tidak lagi populer.

Tetapi saya harus mengakui bahwa saya belum terlalu berpengetahuan tentang masalah-masalah efisiensi perangkat keras tingkat rendah ini, jadi saya mengambil kesempatan ini untuk menanyakan pendapat mereka yang lebih akrab dengan subjek tersebut.

Di mesin saya, saya juga membutuhkan kemampuan untuk secara dinamis menambah dan menghapus node ke grafik saat runtime ( lihat ini ) sehingga rute yang dikomputasi hanya membuat hal-hal lebih rumit, jadi saya membatalkannya (belum lagi solusi runtime A * saya sudah berjalan dengan sempurna ). Namun, saya masih bertanya-tanya ...

Intinya, apakah teknik ini masih relevan saat ini dalam skenario apa pun?

David Gouveia
sumber
2
Saya pikir itu masih relevan jika Anda memiliki anggaran CPU yang ketat. Tetapi begitu Anda menginginkan jalur dinamis, itu tidak lagi berguna. Tapi saya melihat dari mana Anda mendapatkan algoritma A * dan Anda dapat mengoptimalkannya lebih jauh menggunakan minheap dan beberapa trik lainnya. Saya telah melakukan beberapa iterasi untuk meningkatkan A * di C # yang dapat Anda lihat di sini: roy-t.nl/index.php/2011/09/24/… mungkin bermanfaat.
Roy T.
1
Terima kasih, saya telah menandai dan akan melihatnya ketika saya mulai mengoptimalkan aplikasi saya. Saya cukup banyak menggunakan solusi Eric Lippert dengan beberapa modifikasi kecil karena sangat bersih dan mudah diikuti ... Dan untuk semua kasus pengujian saya berjalan cukup banyak "langsung" jadi saya bahkan tidak repot-repot mengoptimalkannya.
David Gouveia
1
BTW jika Anda memutuskan untuk mengejar perhitungan, Anda mungkin ingin melihat algoritma Floyd-Warshall . Itu membangun "langkah selanjutnya" matriks lebih efisien daripada berulang kali menggunakan Dijkstra / A *.
amitp
@amitp Terima kasih atas tipnya, selalu baik untuk mengetahui tentang alternatif ini! Meskipun, karena dalam kebanyakan kasus perhitungan awal akan dilakukan secara offline, tidak akan banyak yang dapat diperoleh dari membuatnya lebih efisien. Kecuali Anda benar-benar tidak sabar. :-)
David Gouveia
Setuju, meskipun Floyd-Warshall juga jauh lebih mudah diimplementasikan daripada algoritma Dijkstra, jadi jika Anda belum menerapkan Dijkstra, ada baiknya dilihat :)
amitp

Jawaban:

3

Di mesin saya, saya juga membutuhkan kemampuan untuk secara dinamis menambah dan menghapus node ke grafik saat runtime (lihat ini) sehingga rute yang dikomputasi hanya membuat hal-hal lebih rumit, jadi saya membatalkannya (belum lagi solusi runtime A * saya sudah berjalan dengan sempurna ). Tetap saja, aku bertanya-tanya ...

Intinya, apakah teknik ini masih relevan saat ini dalam skenario apa pun?

Saya tidak melihat manfaat dari menggunakan teknik seperti itu.

Saya tidak memiliki fleksibilitas Grafik (Anda dapat memiliki LOD yang berbeda, mereka tidak harus berupa bentuk tertentu, dll ...). Juga setiap pengguna mesin Anda akan tahu apa itu grafik dan bagaimana menggunakannya. Jadi, jika mereka ingin menambahkan fungsionalitas tambahan, mereka harus belajar bagaimana menerapkan ekstensi mereka menggunakan situasi yang sama sekali baru bagi mereka.

Seperti yang Anda sebutkan sepertinya akan berskala mengerikan. Juga perlu dicatat bahwa jika grafik cocok dengan uang tunai dan Anda menjalankan semua temuan jalur Anda kembali ke belakang itu benar-benar mengurangi waktu IO. Sepertinya implementasi Anda akan segera tumbuh terlalu besar untuk muat pada cache apa pun.

Saya juga mendengar bahwa saat ini pencarian memori bahkan mungkin lebih lambat daripada perhitungan umum, itulah sebabnya membuat sinus dan cosine look up tables tidak lagi populer.

Kecuali jika Anda dapat memasukkan semua program Anda dan membutuhkan memori dalam cache, Anda akan menggunakan cara ini untuk menarik hal-hal masuk dan keluar dari cara memori sebelum Anda mem-neck prosesor.

Saya curiga bahwa dengan perangkat keras yang kuat saat ini, ditambah dengan persyaratan memori untuk melakukan ini untuk setiap level, manfaat apa pun yang dimiliki teknik ini sekarang dikalahkan dengan hanya melakukan A * saat runtime

Sadari juga bahwa banyak game memiliki loop terpisah untuk memperbarui AI. Saya percaya dia mengatur proyek saya adalah bahwa ada loop pembaruan untuk input pengguna pada 60Hz, AI hanya 20Hz, dan permainan menarik secepat mungkin.

Juga sebagai catatan saya melakukan pemrograman GBA hanya untuk bersenang-senang dan tidak ada transfer sama sekali untuk menggunakan perangkat modern. Untuk GBA semuanya tentang meminimalkan beban kerja prosesor (karena itu menyedihkan). Anda juga harus menyadari bahwa sebagian besar bahasa tingkat tinggi C # dan Java (tidak begitu banyak C ++ atau C) melakukan banyak optimasi untuk Anda. Adapun untuk mengoptimalkan kode Anda mereka tidak banyak melakukan selain mengakses memori sesedikit mungkin dan ketika Anda menjalankan sebanyak mungkin komputasi sebelum memasukkan memori baru yang akan mengeluarkannya dari cache dan memastikan Anda hanya melakukan sesuatu sekali saja.

Sunting: Juga untuk menjawab judul Anda ya. Mempersiapkan jalur yang sering digunakan adalah ide yang bagus dan dapat dilakukan dengan A * di mana saja di luar loop game Anda. Misalnya dari Anda mendasarkan ke sumber daya dalam RTS sehingga pengumpulan tidak harus menghitung ulang setiap kali mereka ingin pergi atau kembali.

Klasik
sumber
Tentang hasil edit Anda, saya tidak benar-benar berbicara tentang mengkomputasi jalur yang sering digunakan, tetapi secara ketat tentang teknik yang diuraikan dalam mengkomputasi setiap jalur yang mungkin . Saya juga agak bingung tentang bagaimana sebagian besar jawaban Anda menentang penggunaan pathfinding yang sudah dikomputasi, tetapi kemudian pada akhirnya Anda mengatakan itu akan menjadi ide yang sangat baik. Jadi, apakah itu berguna pada lingkungan yang dibatasi CPU seperti GBA?
David Gouveia
1
Sayangnya saya mencoba menunjukkan bahwa jawaban untuk judul Anda diambil di luar konteks adalah ya. Sementara jawaban yang berkaitan dengan algoritma spesifik yang dijelaskan dalam pertanyaan Anda adalah tidak. Jadi singkatnya mengkompilasi semua jalur yang mungkin adalah ide yang buruk, tetapi mengkomputasi beberapa jalur yang sangat sering digunakan bisa merupakan ide yang baik.
ClassicThunder
2
@ClassicThunder: Teknik pra-komputasi semua jalur dari beberapa landmark sering disebut sebagai ALT : A-star dengan Landmarks & Triangle-ketidaksetaraan : cs.princeton.edu/courses/archive/spr06/cos423/Handouts/GW05. pdf
Pieter Geerkens