Bagaimana cara mengoptimalkan fungsi jarak?

23

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?

Grimshaw
sumber
Jika Anda memiliki objek yang tidak Anda harapkan untuk dipindahkan, seperti bangunan, misalnya, mungkin layak untuk mengambil rangkaian taylor 2D dari fungsi jarak, memotongnya pada kuadrat, dan kemudian menyimpan fungsi yang dihasilkan sebagai fungsi jarak dari gedung tertentu. Itu akan memindahkan beberapa pekerjaan kasar ke inisialisasi dan dapat mempercepat sedikit.
Alexander Gruber

Jawaban:

26

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.

concept3d
sumber
2
Saya percaya kalimat terakhir dari pertanyaan mengatakan OP mencari alternatif lain (mereka tahu tentang menggunakan jarak kuadrat).
MichaelHouse
@ Byte56 ya Anda benar, saya tidak membacanya.
concept3d
Terima kasih atas jawaban Anda. Apakah Anda menambahkan kalimat yang mengonfirmasi bahwa meskipun metode itu tidak memberi kami jarak euclidean, itu sangat akurat dalam perbandingan? Saya pikir itu akan menambah sesuatu kepada seseorang yang datang ke sini dari mesin pencari.
Grimshaw
@ Grimshaw Saya mengedit jawaban untuk mengatasi masalah aslinya.
concept3d
@ Byte56 terima kasih telah menunjukkan. Saya mengedit jawabannya.
concept3d
29

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 :

Contour Plot

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

Plot Kesalahan

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)

masukkan deskripsi gambar di sini

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.

bcrist
sumber
3
Menarik, belum pernah melihat ini sebelumnya! Apakah itu memiliki nama, atau hanya "rata-rata Chebyshev dan Manhattan"?
congusbongus
@congusbongus Mungkin memiliki nama, tapi saya tidak tahu apa itu. Jika tidak, mungkin suatu hari akan disebut Jarak Crist (hah ... mungkin tidak)
bcrist
1
Perhatikan bahwa perkalian floating-point tidak terlalu efisien. Itu sebabnya pendekatan lain menggunakan 1007/1024 (yang akan diimplementasikan sebagai perkalian integer diikuti oleh bit shift).
MSalters
@MSalters Ya, operasi floating point seringkali lebih lambat daripada operasi integer, tapi itu tidak relevan - 0,4 dan 0,56 bisa dengan mudah dikonversi untuk menggunakan operasi integer. Lebih jauh, pada perangkat keras x86 modern, sebagian besar operasi floating point (selain FDIV,, FSQRTdan fungsi transendental lainnya) harganya pada dasarnya sama dengan versi integernya: 1 atau 2 siklus per instruksi.
bcrist
1
Ini terlihat sangat mirip dengan Alpha max + Beta Min: en.wikipedia.org/wiki/Alpha_max_plus_beta_min_algorithm
drake7707
21

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!)

joeytwiddle
sumber
7
Ini jawaban terbaik. Tidak ada yang dioptimalkan dalam fungsi jarak; seseorang hanya perlu menggunakannya lebih jarang.
sam hocevar
3
Jawaban yang diterima juga mencakup pembagian ruang, jika tidak, jawaban Anda benar-benar optimal. Terima kasih.
Grimshaw
Waktu saya dihabiskan dengan sangat baik untuk membaca jawaban Anda. Terima kasih, Joey.
Patrick M
1
Ini adalah jawaban terbaik dan satu - satunya yang berfokus pada masalah nyata daripada red-herring kinerja fungsi jarak. Jawaban yang diterima mungkin juga mencakup partisi spasial, tetapi itu sebagai tambahan; itu berfokus pada perhitungan jarak. Perhitungan jarak bukanlah masalah utama di sini; optimalisasi perhitungan jarak adalah non-solusi brute-force yang tidak skala.
Maximus Minimus
Bisakah Anda jelaskan mengapa jumlah perbandingan akan eksponensial? Saya pikir itu akan kuadratik, membandingkan setiap aktor satu sama lain selama setiap jangka waktu.
Petr Pudlák
4

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

jarak

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:

jarak2

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!

Tetrinity
sumber
1
Anda juga bisa menggunakan jarak Manhattan sebagai bagian atas.
congusbongus
1
Cukup benar. Saya kira dari sana hanya melompat, melompat dan melompat ke "rata-rata Chebyshev dan Manhattan" seperti yang disarankan oleh bcrist.
Tetrinity
2

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.

Keith
sumber
2

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.

joeytwiddle
sumber
2
Ini bukan optimasi yang bermanfaat lagi. Hampir semua arsitektur PC tingkat konsumen yang dapat Anda beli saat ini memiliki instruksi sqrt yang dioptimalkan untuk perangkat keras yang melakukan root kuadrat dalam siklus clock atau kurang. Jika Anda benar-benar membutuhkan sqrt tercepat, Anda menggunakan instruksi sqrt floating point x86 simd: en.wikipedia.org/wiki/... Untuk hal-hal seperti shader pada GPU, memanggil sqrt akan secara otomatis menghasilkan instruksi seperti itu. Pada CPU, saya menganggap banyak kompiler mengimplementasikan sqrt melalui SIMD sqrt jika tersedia.
TravisG
@ TravisG Ya itu layak disebut, jadi saya telah memperbarui jawabannya. Jawaban ini diberikan hanya untuk kesenangan dan kepentingan sejarah!
joeytwiddle