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?
sumber
Jawaban:
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.
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.
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.
sumber