Peta kerusakan

> Pemrograman

Dengan evaluasi gerakan dan pengelolaan kombinasi serangan, peta kerusakan sangat penting dalam LeekWars. Tujuan utamanya adalah untuk dapat menilai, tergantung pada musuh, tingkat bahaya dari setiap kotak agar dapat mundur ke kotak yang kurang berbahaya di akhir belokan. Cara termudah adalah membuat larik asosiatif: dangerMap=[ cell1:danger1 , cell2:danger2 , ... ], mungkin terbatas pada sel Anda yang dapat diakses. Untuk tujuan ini, beberapa algoritma dimungkinkan

Algoritme "naif".

Ini biasanya ide pertama yang muncul di benak saat membuat algoritme penilaian bahaya. Idenya adalah sebagai berikut:

/* -untuk setiap sel saya yang dapat diakses -untuk setiap lawan -untuk setiap sel lawan yang dapat diakses -untuk setiap senjata lawan -jika dia bisa menembak sel saya dari selnya tambahkan "skor bahaya" ke sel saya */

Pilihan skor adalah bagian integral dari algoritme Anda: Anda dapat memasukkan "+1" di dalamnya, atau menghitung potensi kerusakan yang ditimbulkan, ... Ada banyak cara untuk menyempurnakan evaluasi ini sebanyak jumlah pemain 😉

Masalah besar dengan algoritma ini adalah sangat rakus dalam operasi! Oleh karena itu umumnya diperlukan untuk mengoptimalkannya dengan sangat cepat.

Trek pengoptimalan

Hal pertama yang harus dilakukan adalah mencegah daun bawang Anda "menabrak"... Jadi, Anda harus, di suatu tempat dalam kode, melakukan pengujian pada getOperations() dan keluar dari loop jika jumlah operasi terlalu dekat dengan batas: Anda hanya akan memiliki penilaian sebagian dari bahaya, tetapi daun bawang Anda masih bisa bergerak minimal 😉

Untuk pengoptimalan itu sendiri, salah satu prinsip pertama yang harus memandu pendekatan Anda di atas segalanya adalah untuk menghindari pengulangan operasi yang sama beberapa kali dalam loop: lebih baik dalam hal ini menyiapkan hal-hal dalam tabel kemudian mengingat. Jadi, misalnya, di loop terdalam yang menghitung "skor bahaya", jika Anda tetap memanggil getStrength(Enemy) di dalamnya, Anda akan memanggil kembali fungsi itu ribuan kali. Idenya kemudian menghitung kekuatan musuh hanya sekali dan menyimpannya dalam variabel sebelum melakukan loop internal. Anda sudah akan mulai menghasilkan beberapa ratus ribu perdagangan! Jadi berburu elemen loop "internal" yang tidak bergantung pada variabel loop, tetapi hanya pada loop "eksternal": Anda kemudian dapat melacak elemen ini kembali ke loopnya.

Jika algoritme Anda tetap mahal, jalan lain yang agak estetis untuk pengoptimalan adalah menurunkan resolusi evaluasi ini. Anda dapat, misalnya, tidak menguji semua kotak yang dapat diakses (milik Anda dan/atau milik lawan), tetapi, misalnya, hanya yang membutuhkan jumlah titik pergerakan yang genap. Itu "cukup" kemudian untuk mengisi celah yang diperoleh dengan interpolasi nilai-nilai pada kuadrat tetangga (rata-rata tetangga, maksimum tetangga, maksimum rata-rata antara dua garis, dll.). Pendekatan ini kurang akurat, tetapi, dengan contoh PM genap, mengkonsumsi sekitar 4x lebih sedikit daripada algoritma pertama.

Untuk melanjutkan pengoptimalan, Anda harus memikirkan hal-hal pra-komputasi, biasanya di babak pertama, menyimpan dalam array besar (atau banyak) hal-hal tertentu yang harus Anda hitung ulang dan yang tidak pernah berubah, atau bahkan memperbarui nilai tertentu setiap belokan (dalam contoh kita, kekuatan daun bawang musuh).

Algoritma "sekali dan untuk semua".

Algoritma ini menghitung peta bahaya satu kali di awal pertarungan. Murah, ini kurang tepat tetapi memungkinkan Anda dengan cepat memiliki daftar area peta pertempuran yang umumnya berbahaya. Ini terdiri dari mengevaluasi, pada awal belokan, untuk setiap sel peta pertempuran, semua sel yang memungkinkan Anda menembaknya dengan senjata yang dimiliki musuh: kotak yang hanya dapat dijangkau dari 5 kotak lain akan memiliki skor yang jauh lebih rendah daripada kotak yang dapat dicapai oleh 200 kotak lainnya! Mungkin bijaksana untuk mencoba mundur ke area "berbahaya rendah", dan membuat musuh tetap berada di area "berbahaya tinggi".