Bagaimana cara mengoptimalkan fungsi jarak?

Saat mengembangkan game mirip RTS yang cukup sederhana, saya perhatikan perhitungan jarak saya menyebabkan dampak dalam kinerja.

Setiap saat, ada pemeriksaan jarak untuk mengetahui apakah suatu unit berada dalam jangkauan ke targetnya, apakah proyektil telah mencapai targetnya, apakah pemain telah melindas pickup, tabrakan umum, dll. Daftar berjalan, dan memeriksa untuk jarak antara dua titik banyak digunakan.

Pertanyaan saya persis tentang itu. Saya ingin tahu apa yang dimiliki pengembang game alternatif untuk memeriksa jarak, selain dari pendekatan sqrt (x * x + y * y) yang biasa, yang cukup memakan waktu jika kami melakukannya ribuan kali per frame.

Saya ingin menunjukkan bahwa saya mengetahui jarak manhattan dan perbandingan jarak kuadrat (dengan melewatkan hambatan sqrt). Ada yang lain?

TL; DR; Masalah Anda bukan dengan melakukan fungsi jarak. Masalah Anda berkali-kali melakukan fungsi jarak. Dengan kata lain Anda membutuhkan optimasi algoritmik daripada yang matematis.

[EDIT] Saya menghapus bagian pertama dari jawaban saya, karena orang-orang membencinya. Judul pertanyaan menanyakan fungsi jarak alternatif sebelum diedit.

Anda menggunakan fungsi jarak di mana Anda menghitung akar kuadrat setiap kali. Namun, Anda bisa menggantinya tanpa menggunakan akar kuadrat sama sekali dan menghitung jarak kuadrat saja. Ini akan menghemat banyak siklus berharga Anda.

Jarak ^ 2 = x * x + y * y;

ini sebenarnya trik umum. Tetapi Anda perlu menyesuaikan perhitungan Anda dengan tepat. Ini juga dapat digunakan sebagai pemeriksaan awal sebelum menghitung jarak yang sebenarnya. Jadi sebagai contoh alih-alih menghitung jarak aktual antara dua titik / bola untuk tes persimpangan, kita dapat menghitung Distance Squared sebagai gantinya dan membandingkan dengan radius kuadrat alih-alih radius.

Edit, setelah @ Byte56 menunjukkan bahwa saya tidak membaca pertanyaan, dan bahwa Anda mengetahui optimasi jarak kuadrat.

Nah dalam kasus Anda, sayangnya kita berada dalam grafik komputer yang hampir secara eksklusif berurusan dengan Euclidean Space , dan jarak didefinisikan dengan tepat seperti Sqrt of Vector dot itselfdalam ruang euclidean.

Jarak kuadrat adalah perkiraan terbaik yang akan Anda dapatkan (dalam hal kinerja), saya tidak bisa melihat apa pun mengalahkan 2 perkalian, satu tambahan, dan tugas.

Jadi Anda bilang saya tidak bisa mengoptimalkan fungsi jarak apa yang harus saya lakukan?

Masalah Anda bukan dengan melakukan fungsi jarak. Masalah Anda berkali-kali melakukan fungsi jarak. Dengan kata lain Anda membutuhkan optimasi algoritmik daripada yang matematis.

Intinya adalah, alih-alih memeriksa persimpangan pemain dengan setiap objek dalam adegan, setiap frame. Anda dapat dengan mudah menggunakan koherensi spasial untuk keuntungan Anda, dan hanya memeriksa objek yang berada di dekat pemain (yang paling mungkin untuk mengenai / berpotongan.

Ini dapat dengan mudah dilakukan dengan benar-benar menyimpan info spasial tersebut dalam struktur data partisi spasial . Untuk permainan sederhana, saya akan menyarankan Grid karena pada dasarnya mudah diterapkan dan cocok dengan adegan dinamis dengan baik.

Setiap sel / kotak berisi daftar objek yang dilampirkan oleh kotak pembatas kisi. Dan mudah untuk melacak posisi pemain di sel-sel itu. Dan untuk perhitungan jarak, Anda hanya memeriksa jarak pemain dengan benda-benda di dalam sel tetangga atau yang sama, bukan semua yang ada di layar.

Pendekatan yang lebih rumit adalah dengan menggunakan BSP atau Octrees.

Jika Anda membutuhkan sesuatu yang tetap linier pada jarak berapa pun (tidak seperti distance^2) dan belum tampak melingkar samar-samar (tidak seperti Chebyshev kuadrat dan jarak Manhattan seperti berlian), Anda dapat meratakan dua teknik terakhir untuk mendapatkan perkiraan jarak berbentuk oktagon:

dx = abs(x1 - x0)
dy = abs(y1 - y0)

dist = 0.5 * (dx + dy + max(dx, dy))

Berikut ini visualisasi (alur kontur) dari fungsi, terima kasih kepada Wolfram Alpha :

Dan di sini adalah plot fungsi kesalahannya jika dibandingkan dengan jarak euclidean (radian, kuadran pertama saja):

Seperti yang Anda lihat, kesalahan berkisar dari 0% pada sumbu hingga sekitar + 12% di lobus. Dengan memodifikasi koefisien sedikit kita bisa turun ke +/- 4%:

dist = 0.4 * (dx + dy) + 0.56 * max(dx, dy)

Memperbarui

Menggunakan koefisien di atas, kesalahan maksimum akan berada dalam +/- 4%, tetapi kesalahan rata-rata akan tetap + 1,3%. Dioptimalkan untuk kesalahan rata-rata nol, Anda dapat menggunakan:

dist = 0.394 * (dx + dy) + 0.554 * max(dx, dy)

yang memberikan kesalahan antara -5% dan + 3% dan kesalahan rata-rata + 0,043%

Saat mencari nama untuk algoritma ini di web, saya menemukan perkiraan segi delapan yang serupa ini :

dist = 1007/1024 * max(dx, dy) + 441/1024 * min(dx, dy)

Perhatikan bahwa ini pada dasarnya setara (meskipun eksponennya berbeda - eksponen ini memberikan kesalahan -1,5% hingga 7,5%, tetapi dapat dipijat hingga +/- 4%) karena max(dx, dy) + min(dx, dy) == dx + dy. Dengan menggunakan formulir ini, panggilan mindan maxdapat difaktorkan mendukung:

if (dy > dx)
    swap(dx, dy)

dist = 1007/1024 * dx + 441/1024 * dy

Apakah ini akan lebih cepat daripada versi saya? Siapa tahu ... tergantung pada kompiler dan bagaimana ia mengoptimalkan masing-masing untuk platform target. Dugaan saya adalah akan sangat sulit untuk melihat perbedaan.

Terkadang pertanyaan ini dapat timbul bukan karena biaya melakukan perhitungan jarak, tetapi karena berapa kali perhitungan dilakukan.

Dalam dunia gim besar dengan banyak aktor, tidak mungkin untuk terus memeriksa jarak antara satu aktor dan yang lainnya. Sebagai pemain lebih, NPC dan proyektil memasuki dunia, jumlah perbandingan yang harus dibuat akan tumbuh kuadratik dengan O(N^2).

Salah satu cara untuk mengurangi pertumbuhan itu adalah dengan menggunakan struktur data yang baik untuk dengan cepat membuang aktor yang tidak diinginkan dari perhitungan.

Kami mencari cara untuk secara efisien mengulangi semua aktor yang mungkin berada dalam jangkauan, sementara tidak termasuk mayoritas aktor yang jelas berada di luar jangkauan .

Jika aktor Anda tersebar merata di ruang dunia, maka kotak ember harus menjadi struktur yang sesuai (seperti yang disarankan jawaban yang diterima). Dengan menyimpan referensi ke aktor dalam kotak kasar, Anda hanya perlu memeriksa beberapa ember terdekat untuk mencakup semua aktor yang mungkin berada dalam jangkauan, mengabaikan sisanya. Saat aktor bergerak, Anda mungkin perlu memindahkannya dari ember lamanya ke yang baru.

Untuk aktor yang penyebarannya kurang merata, quadtree mungkin lebih baik untuk dunia dua dimensi, atau satu octree akan cocok untuk dunia tiga dimensi. Ini adalah struktur tujuan yang lebih umum yang dapat secara efisien membagi area yang luas dengan ruang kosong, dan area kecil yang mengandung banyak aktor. Untuk aktor statis ada partisi ruang biner (BSP), yang sangat cepat untuk mencari tetapi terlalu mahal untuk memperbarui secara realtime. BSP memisahkan ruang menggunakan pesawat untuk berulang kali memotongnya menjadi dua, dan dapat diterapkan ke sejumlah dimensi.

Tentu saja ada overhead untuk menjaga struktur aktor Anda seperti itu, terutama ketika mereka bergerak di antara partisi. Tetapi di dunia yang besar dengan banyak aktor tetapi rentang minat yang kecil, biayanya harus jauh lebih rendah daripada yang dikeluarkan oleh perbandingan naif terhadap semua objek.

Pertimbangan bagaimana biaya suatu algoritma tumbuh saat menerima lebih banyak data sangat penting untuk desain perangkat lunak yang dapat diskalakan. Terkadang cukup memilih struktur data yang benar sudah cukup. Biaya biasanya dijelaskan menggunakan notasi O Besar .

(Saya menyadari ini bukan jawaban langsung untuk pertanyaan itu, tetapi mungkin bermanfaat bagi beberapa pembaca. Maaf jika saya membuang-buang waktu Anda!)

Bagaimana dengan jarak Chebyshev? Untuk poin p, q didefinisikan sebagai berikut:

Jadi untuk poin (2, 4) dan (8, 5), jarak Chebyshev adalah 6, seperti | 2-8 | > | 4-5 |.

Selanjutnya, biarkan E menjadi jarak Euclidean dan C menjadi jarak Chebyshev. Kemudian:

Batas atas mungkin tidak banyak digunakan karena Anda harus menghitung akar kuadrat, tetapi batas bawah bisa membantu - setiap kali jarak Chebyshev cukup besar untuk berada di luar jangkauan, jarak Euclidean juga harus, menghemat Anda dari harus menghitungnya.

Pertukarannya, tentu saja, adalah bahwa jika jarak Chebyshev berada dalam jangkauan, Anda harus tetap menghitung jarak Euclidean, membuang-buang waktu. Hanya satu cara untuk mengetahui apakah itu akan menjadi kemenangan bersih!

Optimalisasi lokal yang sangat sederhana adalah dengan hanya memeriksa satu dimensi terlebih dahulu.

Itu adalah :

distance ( x1, y1 , x1, y2) > fabs (x2 - x1)

Jadi hanya memeriksa fabs (x2 - x1)sebagai filter pertama dapat memberikan keuntungan yang cukup besar. Berapa banyak akan tergantung pada ukuran dunia versus rentang yang relevan.

Selanjutnya, Anda dapat menggunakan ini sebagai alternatif untuk struktur data partisi spasial.

Jika semua objek yang relevan diurutkan dalam daftar dalam urutan x koordinat, maka objek terdekat harus berada di dekatnya dalam daftar. Bahkan jika daftar menjadi rusak karena tidak dipelihara sepenuhnya saat benda bergerak, maka mengingat batas kecepatan yang diketahui Anda masih dapat mengurangi bagian daftar yang akan dicari untuk objek terdekat.

Upaya dilakukan di masa lalu untuk mengoptimalkan sqrt. Meskipun tidak lagi berlaku untuk mesin saat ini, berikut adalah contoh dari kode sumber Quake, yang menggunakan angka ajaib 0x5f3759df :

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // what the hell?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration (optional)
  // ...
  return y;
}

Sebuah penjelasan rinci tentang apa yang terjadi di sini dapat ditemukan di Wikipedia.

Singkatnya, ini adalah beberapa iterasi dari metode Newton (algoritma numerik yang secara iteratif meningkatkan estimasi), dengan angka ajaib yang digunakan untuk memberikan estimasi awal yang masuk akal.

Seperti yang ditunjukkan Travis, optimisasi semacam ini tidak lagi berguna pada arsitektur modern. Dan bahkan jika itu, itu hanya bisa memberikan peningkatan kecepatan konstan untuk kemacetan Anda, sementara desain ulang algoritmik mungkin mencapai hasil yang lebih baik.